用Java实现Google的“您是不是要找”功能 - 编程入门网

用Java实现Google的“您是不是要找”功能

引言

很多人在使用搜索引擎的时候，会出于各种原因，拼错想要搜索的关键字，比如键盘有问题（某个按 键坏了）、不熟悉国际名称（弗洛伊德的全名 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实现Google的“您是不是要找”功能(2)

示例

下面是一个简单的代码示例。运行这个例子需要Java 5或更新版本、lucene-core-3.0.0.jar、 lucene-spellchecker-3.0.0.jar，以及一个名为 dictionary.txt的平面文件（一行一个关键字的简单文 本文件，后面有一个例子）。

//创建词典 //实例化拼写检查器 final　SpellChecker　sp　=

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!