- 浏览: 174193 次
- 性别:
- 来自: 青岛
文章分类
最新评论
-
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 2888package B7.general; import ... -
java 读取http url joson 格式
2012-02-28 08:39 1179URL url = new URL("htt ... -
Java 接口和抽象类区别
2011-03-02 08:58 604一个软件设计的好坏, ... -
php 环境搭建
2009-06-17 17:25 1155想学习php。在网上找了个搭建。好多杂的。google一下时间 ... -
abstract class vc interface
2008-12-10 16:24 1441abstract class 和 interface 都提供可 ... -
二分查找vc线性查找
2008-12-10 14:32 1057public static int binarySearch( ... -
java 取字符串中汉字之前的部门
2008-09-03 17:28 1064String dd="ddfdf你好" ... -
java 数组 操作
2008-08-21 17:30 1071public ArrayList zuhe(){ ... -
查询代码网站
2008-08-17 15:55 765<search terms> Search fo ... -
java String to byte[]
2008-07-16 09:01 4502package mobile; /* * T ... -
java pdf
2008-07-13 13:39 1173引用 :http://www.iteye.com/post/5 ... -
java月份时间(第一天,最后一天)
2008-06-13 20:57 7049<% //当前月的最后一天 ... -
java中文件操作大全
2008-05-08 18:07 1015引用: http://www.pben.cn/main.bb ... -
较好的Java网站收集
2008-04-25 14:19 994转自:http://blog.chinaunix. ... -
java 自定义排序
2008-04-21 10:21 2029利用java.util. Comparator接口 和java ... -
2008年Java开发者最迫切的五个期望
2008-03-29 11:28 1220发布日期:2008-1-11 9:11 ... -
Java精华积累:每个初学者都应该搞懂的问题!
2008-03-07 13:20 1079Java精华积累:每个初学 ... -
如何让EditPlus可以编译执行Java程序
2008-02-13 10:51 1817如何让EditPlus可以编译执行Java程序在 USER T ... -
阴阳转换的类! 算法支持1900-2050
2008-02-13 10:49 1381引自: http://www.nqqn.com/ym/68/2 ... -
整理了sun网站java环境下获取网卡信息的资料
2008-02-13 10:14 1588引自:http://www.nqqn.com/ym/68/29 ...
相关推荐
Lucene SpellChecker for Lucene 3.0.2
可以通过阅读`org.apache.lucene.search.spell`包下的源码,特别是`SpellChecker`和`IndexDictionary`类,了解其内部实现细节。 **五、工具使用** 除了源码级的集成,Lucene还提供了一些工具,如`...
jar包,亲测可用
java运行依赖jar包
首先,Lucene的`SpellChecker`类是其拼写纠错功能的核心。这个类允许开发者构建一个拼写字典,并对比用户输入的查询词与字典中的正确拼写,从而找出可能的错误并提供纠正建议。`SpellChecker`基于编辑距离算法,如...
本文将详细介绍如何使用 Compass 和 Lucene 实现一个简单的全文检索功能。 首先,Lucene 是一个高性能、全功能的文本分析库,主要用于信息检索。它提供了索引和搜索大量文本数据的能力,包括分词、分析、存储和搜索...
首先,我们要明白 Lucene 默认的排序机制。默认情况下,Lucene 搜索结果是按照文档的相关性(即查询评分)进行排序的。这个评分是通过 TF-IDF(词频-逆文档频率)算法计算得出的,它反映了文档中关键词出现的频率...
在Java开发中,Lucene被广泛用于实现文件的全文检索功能,包括对doc、docx、pdf、txt等常见格式文档的文本内容检索。在本文中,我们将探讨如何使用Lucene对这些文件类型进行全文检索的实现。 首先,为了实现全文...
在Lucene中,我们可以通过`FuzzyQuery`类来实现这种功能。`FuzzyQuery`基于Levenshtein距离算法,该算法计算两个字符串之间的差异程度,用于衡量它们的相似性。 首先,我们需要了解如何创建一个`FuzzyQuery`。在`...
标题中的“使用Lucene4.7实现搜索功能,分页+高亮”表明我们要讨论的是如何利用Apache Lucene 4.7版本来构建一个具备搜索、分页和高亮显示功能的系统。Lucene是一个高性能、全文本搜索引擎库,它提供了强大的文本...
通过以上步骤,你可以在C#应用中集成Lucene,实现高效的全文搜索功能。这个过程涉及到的关键知识点包括:Lucene.NET的安装与引用、索引的创建与更新、查询的构建与执行以及结果的处理。通过熟练掌握这些,你将能构建...
除了核心模块,Lucene还提供了一些附加功能,如 SpellChecker(拼写检查)、Highlighter(高亮显示搜索结果)和Remote搜索支持。在源码中,你可以找到对应的实现类,如SpellChecker、Highlighter等。 这个压缩包中...
此外,还可以扩展Lucene的功能,比如使用过滤器和评分函数来改进搜索结果的相关性,或者添加faceted search(分面搜索)以提供更细致的分类和导航。 总之,通过Paoding和Lucene的结合,我们可以构建一个高效、精确...
在本文中,我们将深入探讨如何使用Lucene来实现一个类似当当网的企业产品检索系统,特别关注如何结合庖丁解牛分词器提升搜索体验。 首先,我们需要理解Lucene的基本工作原理。Lucene的核心是建立索引,将原始文本...
在搜索功能的实现中,Spring可以帮助管理Lucene的相关组件,如索引目录、搜索引擎实例等,同时通过其强大的数据访问支持与Hibernate协同工作。 **Hibernate** 是一个对象关系映射(ORM)框架,使得Java开发者可以更...
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-...
在搜索引擎和信息检索领域,Apache Lucene 是一个广泛使用的全文索引库,它提供了高效、可扩展的搜索功能。在处理大量数据时,有时我们需要对搜索结果进行分组,以便更好地理解和分析数据。"Lucene group by" 指的...
`lucene-spellchecker-3.6.1.jar`提供了拼写检查功能,能帮助纠正搜索时的拼写错误。`lucene-highlighter-3.6.1.jar`用于高亮搜索结果中的关键词,增强用户体验。`lucene-misc-3.6.1.jar`包含了其他杂项功能,如地理...