- 浏览: 169017 次
- 性别:
- 来自: 青岛
文章分类
最新评论
-
hugang357:
...
java String to byte[] -
lyzhu:
winstr
使用JAVASCRIPT实现弹出框,过一段时间自动消失 -
laoliu.org:
要是稍微整理一下成一个健全类就更好了,呵呵。
我把它转到IT民 ...
java月份时间(第一天,最后一天) -
kaituozhe6666:
...
使用JAVASCRIPT实现弹出框,过一段时间自动消失 -
damocreazy:
试一试
如何让EditPlus可以编译执行Java程序
引言
很多人在使用搜索引擎的时候,会出于各种原因,拼错想要搜索的关键字,比如键盘有问题(某个按键坏了)、不熟悉国际名称(弗洛伊德的全名 Sigmund Freud)、不小心写错字母(Sinpsons)或多写了一个字母(Frusciaante)。许多用户都很熟悉Google搜索引擎携带的“您是不是 要找”功能。这个功能在检测到搜索关键字有可能拼写错了的时候会提供一些备选建议。
文本搜索在电子商务网站等各类应用中都很常见。电子商务网站通常提供文本搜索功能,用户因此可以自行查找符合关键字的产品目录。一旦用户拼错关键 字,很可能就直接导致销售损失。举例来说,假如你运营一个销售DVD的在线商店。阿诺德·施瓦辛格(Arnold Schwarzenegger)的影迷想在你的网店购买施瓦辛格主演的所有DVD。他首先做的就是在搜索栏键入施瓦辛格的名字,可是如果他把名字拼错了, 拼成了“Arnold Swuazeneger”,假如你的网店没有返回任何相关的结果,那他就会去另一家网店购买。
解决这个问题的其中一个方案就是利用内置的领域知识来实现“您是不是要找”的功能,向用户提供“您是不是要找Arnold Schwarzenegger”的建议。本文将要探讨的就是如何用Java来实现这个功能。
编辑距离算法
在信息论和计算机科学领域,两个字符串之间的编辑距离是指将其中一个字符串用另一个字符来替换所需要的操作次数。定义编辑距离的方式有好几种,使用这些定 义计算编辑距离值的算法也有很多。主要的算法有Levenshtein、Jaro-Winkler和n-gram。Jaro-Winkler是Jaro距离度量的一个延伸,主要应用于记录连接领域(重复检测)。Levenshtein算法中,两个字符串之间的距离定 义为将一个字符串转换为另一字符串所需的最少编辑次数,允许的编辑操作有插入、删除、单个字符的替换。该算法由Vladimir Levenshtein在1965年提出,并以作者名来命名。n-gram是一个概率模型,按顺序预测下一个编辑项,这一模型广泛用于统计自然 语言处理和基因序列分析的各个领域。
本文并非要研究如何从头实现这些算法,我们要关注的是如何借助Apache Lucene中已有的实现——SpellChecker项目来应用这些算法。
简单来说,Lucene SpellChecker实现包括主类SpellChecker,主类SpellChecker用到了Directory、Dictionary、以及三个StringDistance算法之一。SpellChecker类使用策略模式(GoF)选 择StringDistance算法,内置的StringDistance算法实现有JaroWinklerDistance、 LevenshteinDistance、NGramDistance,缺省为LevenshteinDistance。你还可以调整精度,精度的取值范 围在0到1之间,缺省为0.5。精度的设置对结果有很大影响,也许你会觉得精度应当设置得比缺省值要高一些,但也许你会发现设置得过高时算法却不会返回任 何结果。拿我的词典来说,精度取0.749时得到的结果最好。Dictionary接口有两个直接实现,你也可以编写自己的实现。
对我们的“您是不是要找”实现来说,我们在词典中搜索关键字的子集,根据选定的字符串距离算法查找“相近”的关键字,而且距离要与预先设置的精度相匹配。图1是Lucene SpellChecker的类图概览。
示例
下面是一个简单的代码示例。运行这个例子需要Java 5或更新版本、lucene-core-3.0.0.jar、lucene-spellchecker-3.0.0.jar,以及一个名为 dictionary.txt的平面文件(一行一个关键字的简单文本文件,后面有一个例子)。
//创建词典 //实例化拼写检查器 final SpellChecker sp = new SpellChecker(directory); //对词典进行索引 sp.indexDictionary(new PlainTextDictionary(new File("dictionary.txt"))); //“错误”的搜索 String search = "Arnold Swuazeneger"; //建议个数 final int suggestionNumber = 5; //获取建议的关键字 String[] suggestions = sp.suggestSimilar(search, suggestionNumber); //显示结果 System.out.println("Your Term:" + search); for (String word : suggestions) { System.out.println("Did you mean:" + word); } //再创建一个拼写错误的搜索 search = "bava"; suggestions = sp.suggestSimilar(search, suggestionNumber); System.out.println("Your Term:" + search); for (String word : suggestions) { System.out.println("Did you mean:" + word); }
给定的dictionary.txt文件如下所示:
Seth MacFarlane
Arnold Schwarzenegger
Scarlett Johansson
Rodrigo Santoro
java
lava
bullet
程序的输出为:
Your Term: arnold swuazeneger
Did you mean: Arnold Schwarzenegger
Your Term: bava
Did you mean: java
Did you mean: lava
Did you mean: bullet
Benchmarking测试
为了对性能有所了解,我们在具备以下配置的机器上将示例运行了十五次,取其平均值:
操作系统:Windows XP Professional SP3
处理器:Intel Core 2 Duo E6550 @2.33GHz
内存:1.96GB
测试
测试编号 | 关键字长度 | 词典大小 | 精度 | 算法 | 索引时间 | 获得建议的时间 | |
T1 | 17 | 5 | 0,5 | Levenshtein | 73,0136214 | 25,036049 | |
T2 | 17 | 81000 | 0,5 | Levenshtein | 3402,293693 | 27,7293112 | |
T3 | 17 | 5 | 0,5 | JaroWinkler | 69,53269 | 24,232477 | |
T4 | 17 | 81000 | 0,5 | JaroWinkler | 3356,016059 | 26,287849 | |
T5 | 17 | 81000 | 0,5 | NGram | 3353,633583 | 26,580123 | |
T6 | 17 | 81000 | 0,9 | Levenshtein | 3325,310027 | 26,96378 | |
T7 | 17 | 81000 | 0,3 | Levenshtein | 3408,072786 | 24,723142 | |
T8 | 4 | 81000 | 0,67 | Levenshtein | 3328,584784 | 25,363586 | |
T9 | 28 | 81000 | 0,67 | Levenshtein | 3354,5943 | 31,284672 |
图表
其中:
关键字长度是关键字包含的字母个数。
词典大小是文件行数。
精度由setAccuracy方法设置。
根据测试结果,我们可以得出这样的结论:精度对时间的影响不大,关键字长度对时间却有很大影响——包含四个字符的关键字大约2ms就能获得结果。测 试的三种算法中,NGramDistance略快于另外两个。在测试中我还发现,JaroWinkler距离算法所得到的准确结果最少。
结论
正如你看到的,利用已有的算法使得“您是不是要找”的实现细节出奇的简单。但在现实场景中,要创建支持应用、适用于领域特定关键字的词典则需要花费更多的力气。
参考文献
- http://lucene.apache.org/java/docs/
- http://today.java.net/pub/a/today/2005/08/09/didyoumean.html
- http://archsofty.blogspot.com/2009/12/adicione-o-recurso-voce-quis-dizer-nas.html
- http://lucene.apache.org/java/3_0_0/api/contrib-spellchecker/index.html
- http://en.wikipedia.org/wiki/Edit_distance
- http://en.wikipedia.org/wiki/Levenshtein_distance
- http://en.wikipedia.org/wiki/Jaro-Winkler_distance
关于作者
Leandro R. Moreira从2002年开始参与软件开发,目前是巴西政府机构的一名软件开发人员。他参与很多开源项目的开发,包括Jpcsp。在Mudno Java第30期上,他发表了文章《面向对象的世界:实现内部DSL》,此外,他还有一个用母语葡萄牙语维护的博客。
查看英文原文:Implementing Google's "Did you mean" Feature In Java。
注:以上转自http://www.infoq.com/cn/articles/lucene-did-you-mean
http://www.infoq.com/cn/articles/lucene-did-you-mean
发表评论
-
java调用google map api 根据经纬度读取经纬度地址
2012-02-28 08:42 2776package B7.general; import ... -
java 读取http url joson 格式
2012-02-28 08:39 1131URL url = new URL("htt ... -
Java 接口和抽象类区别
2011-03-02 08:58 569一个软件设计的好坏, ... -
php 环境搭建
2009-06-17 17:25 1085想学习php。在网上找了个搭建。好多杂的。google一下时间 ... -
abstract class vc interface
2008-12-10 16:24 1411abstract class 和 interface 都提供可 ... -
二分查找vc线性查找
2008-12-10 14:32 1018public static int binarySearch( ... -
java 取字符串中汉字之前的部门
2008-09-03 17:28 1034String dd="ddfdf你好" ... -
java 数组 操作
2008-08-21 17:30 1030public ArrayList zuhe(){ ... -
查询代码网站
2008-08-17 15:55 740<search terms> Search fo ... -
java String to byte[]
2008-07-16 09:01 4421package mobile; /* * T ... -
java pdf
2008-07-13 13:39 1103引用 :http://www.iteye.com/post/5 ... -
java月份时间(第一天,最后一天)
2008-06-13 20:57 7017<% //当前月的最后一天 ... -
java中文件操作大全
2008-05-08 18:07 949引用: http://www.pben.cn/main.bb ... -
较好的Java网站收集
2008-04-25 14:19 935转自:http://blog.chinaunix. ... -
java 自定义排序
2008-04-21 10:21 2000利用java.util. Comparator接口 和java ... -
2008年Java开发者最迫切的五个期望
2008-03-29 11:28 1189发布日期:2008-1-11 9:11 ... -
Java精华积累:每个初学者都应该搞懂的问题!
2008-03-07 13:20 1019Java精华积累:每个初学 ... -
如何让EditPlus可以编译执行Java程序
2008-02-13 10:51 1709如何让EditPlus可以编译执行Java程序在 USER T ... -
阴阳转换的类! 算法支持1900-2050
2008-02-13 10:49 1265引自: http://www.nqqn.com/ym/68/2 ... -
整理了sun网站java环境下获取网卡信息的资料
2008-02-13 10:14 1551引自:http://www.nqqn.com/ym/68/29 ...
相关推荐
Lucene SpellChecker for Lucene 3.0.2
jar包,亲测可用
java运行依赖jar包
使用compass+lucene实现简单的全文检索功能
使用compass+lucene实现简单的全文检索功能
C#调用Lucene方法-实现快速搜索
lucene自定义排序实现,大家有兴趣关注我的博客http://blog.csdn.net/wuyinggui10000/article/category/3173543
Lucene实现全文检索
lucene-spellchecker-3.3.0.jar lucene-stempel-3.3.0.jar lucene-test-framework-3.3.0.jar lucene-wordnet-3.3.0.jar lucene-xml-query-parser-3.3.0.jar maven-ant-tasks-2.1.1.jar xercesImpl-2.9.1-patched-...
最受欢迎的java开源全文搜索引擎开发工具包。提供了完整的查询引擎和索引...Lucene的目的是为软件开发人员提供一个简易用的工具包,以方便在目标系统中实现全文检索功能,或者是以此为基础建立起完整的全文检索引擎。
在lucene中使用庖丁解牛的分词器,实现类似当当网站的功能实现一个对企业内部产品的检索功能
java代码 结合 lucene 实现的 公交搜索系统 java代码 结合 lucene 实现的 公交搜索系统 java代码 结合 lucene 实现的 公交搜索系统 java代码 结合 lucene 实现的 公交搜索系统 java代码 结合 lucene 实现的 公交...
这是lucene的使用案例,实现了对word文档中的关键字检索,并将检索出的内容高亮打印出来
用lucene3实现搜索多字段并排序功能(设置权重)
Lucene,实现了带有歧义消除功能的正向最大匹配算法.在系统评测方面,比较了该方法与现 有方法的区别,对于如何构建一个高效的中文检索系统,提出了一种实现. 关键词:中文分词;搜索引擎;Lucene;正向最大匹配
SSH整合lucene4.2 并实现搜索框autocomplete功能,需新建一个search0数据库,接着部署项目,再将压缩包内的hotkey.sql item_category.sql items.sql 插入到数据库就可以正常运行了
lucene,lucene教程,lucene讲解。 为了对文档进行索引,Lucene 提供了五个基础的类 public class IndexWriter org.apache.lucene.index.IndexWriter public abstract class Directory org.apache.lucene.store....
Lucene 实现的 搜索引擎 例子 ,里面有索引的生成 检查 等等
lucene实例lucene实例lucene实例lucene实例lucene实例lucene实例lucene实例lucene实例lucene实例
最后,虽然Lucene使用Java语言写成,但是开放源代码社区的程序员正在不懈的将之使用各种传统语言实现(例如.net framework[14]),在遵守Lucene索引文件格式的基础上,使得Lucene能够运行在各种各样的平台上,系统...