`

【转】用Lucene的SpellChecker实现Google的“您是不是要找”功能

    博客分类:
  • java
阅读更多

引言

很多人在使用搜索引擎的时候,会出于各种原因,拼错想要搜索的关键字,比如键盘有问题(某个按键坏了)、不熟悉国际名称(弗洛伊德的全名 Sigmund Freud)、不小心写错字母(Sinpsons)或多写了一个字母(Frusciaante)。许多用户都很熟悉Google搜索引擎携带的“您是不是 要找”功能。这个功能在检测到搜索关键字有可能拼写错了的时候会提供一些备选建议。

文本搜索在电子商务网站等各类应用中都很常见。电子商务网站通常提供文本搜索功能,用户因此可以自行查找符合关键字的产品目录。一旦用户拼错关键 字,很可能就直接导致销售损失。举例来说,假如你运营一个销售DVD的在线商店。阿诺德·施瓦辛格(Arnold Schwarzenegger)的影迷想在你的网店购买施瓦辛格主演的所有DVD。他首先做的就是在搜索栏键入施瓦辛格的名字,可是如果他把名字拼错了, 拼成了“Arnold Swuazeneger”,假如你的网店没有返回任何相关的结果,那他就会去另一家网店购买。

解决这个问题的其中一个方案就是利用内置的领域知识来实现“您是不是要找”的功能,向用户提供“您是不是要找Arnold Schwarzenegger”的建议。本文将要探讨的就是如何用Java来实现这个功能。

编辑距离算法

在信息论和计算机科学领域,两个字符串之间的编辑距离是指将其中一个字符串用另一个字符来替换所需要的操作次数。定义编辑距离的方式有好几种,使用这些定 义计算编辑距离值的算法也有很多。主要的算法有Levenshtein、Jaro-Winkler和n-gram。Jaro-WinklerJaro距离度量的一个延伸,主要应用于记录连接领域(重复检测)。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距离算法所得到的准确结果最少。

结论

正如你看到的,利用已有的算法使得“您是不是要找”的实现细节出奇的简单。但在现实场景中,要创建支持应用、适用于领域特定关键字的词典则需要花费更多的力气。

参考文献

关于作者

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

分享到:
评论

相关推荐

    Lucene SpellChecker3.0.2

    Lucene SpellChecker for Lucene 3.0.2

    Lucene5学习之SpellCheck拼写纠错

    可以通过阅读`org.apache.lucene.search.spell`包下的源码,特别是`SpellChecker`和`IndexDictionary`类,了解其内部实现细节。 **五、工具使用** 除了源码级的集成,Lucene还提供了一些工具,如`...

    apache-lucene-spellchecker.jar

    jar包,亲测可用

    lucene-spellchecker-3.6.2.jar

    java运行依赖jar包

    lucene拼写纠错代码didyoumean

    首先,Lucene的`SpellChecker`类是其拼写纠错功能的核心。这个类允许开发者构建一个拼写字典,并对比用户输入的查询词与字典中的正确拼写,从而找出可能的错误并提供纠正建议。`SpellChecker`基于编辑距离算法,如...

    使用compass+lucene实现简单的全文检索功能

    本文将详细介绍如何使用 Compass 和 Lucene 实现一个简单的全文检索功能。 首先,Lucene 是一个高性能、全功能的文本分析库,主要用于信息检索。它提供了索引和搜索大量文本数据的能力,包括分词、分析、存储和搜索...

    lucene自定义排序实现

    首先,我们要明白 Lucene 默认的排序机制。默认情况下,Lucene 搜索结果是按照文档的相关性(即查询评分)进行排序的。这个评分是通过 TF-IDF(词频-逆文档频率)算法计算得出的,它反映了文档中关键词出现的频率...

    使用Lucene对doc、docx、pdf、txt文档进行全文检索功能的实现 - 干勾鱼的CSDN博客 - CSDN博客1

    在Java开发中,Lucene被广泛用于实现文件的全文检索功能,包括对doc、docx、pdf、txt等常见格式文档的文本内容检索。在本文中,我们将探讨如何使用Lucene对这些文件类型进行全文检索的实现。 首先,为了实现全文...

    Lucene 搜索方法(模糊搜索)

    在Lucene中,我们可以通过`FuzzyQuery`类来实现这种功能。`FuzzyQuery`基于Levenshtein距离算法,该算法计算两个字符串之间的差异程度,用于衡量它们的相似性。 首先,我们需要了解如何创建一个`FuzzyQuery`。在`...

    使用Lucene4.7实现搜索功能,分页+高亮

    标题中的“使用Lucene4.7实现搜索功能,分页+高亮”表明我们要讨论的是如何利用Apache Lucene 4.7版本来构建一个具备搜索、分页和高亮显示功能的系统。Lucene是一个高性能、全文本搜索引擎库,它提供了强大的文本...

    lucene 全包 包括源码

    除了核心模块,Lucene还提供了一些附加功能,如 SpellChecker(拼写检查)、Highlighter(高亮显示搜索结果)和Remote搜索支持。在源码中,你可以找到对应的实现类,如SpellChecker、Highlighter等。 这个压缩包中...

    paoding+lucene实现全文检索功能简单实例

    此外,还可以扩展Lucene的功能,比如使用过滤器和评分函数来改进搜索结果的相关性,或者添加faceted search(分面搜索)以提供更细致的分类和导航。 总之,通过Paoding和Lucene的结合,我们可以构建一个高效、精确...

    lucene实现企业产品检索

    在本文中,我们将深入探讨如何使用Lucene来实现一个类似当当网的企业产品检索系统,特别关注如何结合庖丁解牛分词器提升搜索体验。 首先,我们需要理解Lucene的基本工作原理。Lucene的核心是建立索引,将原始文本...

    Lucene与SSH2搜索功能

    在搜索功能的实现中,Spring可以帮助管理Lucene的相关组件,如索引目录、搜索引擎实例等,同时通过其强大的数据访问支持与Hibernate协同工作。 **Hibernate** 是一个对象关系映射(ORM)框架,使得Java开发者可以更...

    lucene3.3的全部jar包

    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-...

    Lucene group by ,分组实现

    在搜索引擎和信息检索领域,Apache Lucene 是一个广泛使用的全文索引库,它提供了高效、可扩展的搜索功能。在处理大量数据时,有时我们需要对搜索结果进行分组,以便更好地理解和分析数据。"Lucene group by" 指的...

    C#调用Lucene方法-实现快速搜索

    通过以上步骤,你可以在C#应用中集成Lucene,实现高效的全文搜索功能。这个过程涉及到的关键知识点包括:Lucene.NET的安装与引用、索引的创建与更新、查询的构建与执行以及结果的处理。通过熟练掌握这些,你将能构建...

    lucene 所有jar包 包含IKAnalyzer分词器

    `lucene-spellchecker-3.6.1.jar`提供了拼写检查功能,能帮助纠正搜索时的拼写错误。`lucene-highlighter-3.6.1.jar`用于高亮搜索结果中的关键词,增强用户体验。`lucene-misc-3.6.1.jar`包含了其他杂项功能,如地理...

Global site tag (gtag.js) - Google Analytics