当前位置: 首页 > 搜索 > 正文

搜索引擎纠错设计

1 星2 星3 星4 星5 星 (3 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share
文章目录

上一篇文章:拼写纠错功能实现,比较侧重理论讲解。现在我们来谈谈搜索引擎纠错的工程实现。

一.繁转简

这个比较简单,通过使用繁简转换表转换。

二.拼音转汉字

首先把汉字通过pinyin4j转化成拼音。存储结构由map去实现,key为拼音,value为拼音对应的汉字(一个或多个)。再存储一份常用短语拼音字典。一个拼音组合对应的有多个汉字组合,有很多汉字组合是我们不常用的。通过短语拼音字典,得到我们常用的短语。有点类似拼音输入法的作用。

拼音字典存储可考虑trie树和hash去存储。用trie树更节省空间,但是字典数据量很庞大的时候,hash更方便一些,可以实现多台机器存储。

具体实现可以参考我以前写的文章:拼音转中文简易实现

关于拼音纠错可以使用最短编辑距离去纠错。

三.英文纠错

在lucene中已有贡献者实现了spellchecker模块,主要算法有:Jaro Winkler distanceLevenstein Distance(Edit Distance)NGram Distance

 Solr也有SpellCheckComponent实现

也可以使用LingPipe中的spell模块去实现拼写纠错。

主要使用的方法有:

(1)误拼字典法。这种方法可以理解成穷举法,通过收集大规模真实文本中拼写出错的英文单词并给出相应的正确拼写,建造一个无歧义的误拼字典。在进行英文单词拼写检查时,查找误拼字典,如命中,则说明该单词拼写有误,该词的正确拼写字段为纠错建议。比如在搜索引擎的实现中,通过记录日志的形式,把所有用户的输入都记录下来,提取有拼写错误的输入,形成误拼词典。该方法的特点是算法简单,效率高。但英文拼写错误具有随机性,很难保证误拼字典的无歧义性和全面性,因此查准率低、校对效果差;而且,对于搜索引擎用户海量的误拼输入,空间复杂度也是需要考虑的问题。

(2)最小编辑距离法。通过计算误拼字符串与词典中某个词间的最小编辑距离来确定纠错候选词。所谓最小编辑距离是指将一个词串转换为另一个词串所需的最少的编辑操作次数。在编辑操作中,可以将单次的编辑动作归纳为三种:插入字符、删除字符和替换字符;考虑到在实际计算机输入过程中,字符的颠倒异位也是常见的错误,我们将颠倒异位也算作一种编辑动作。还有人提出了反向最小编辑距离法,这种方法首先对每个可能的单个错误按照编辑距离进行搜索,生成一个候选集,然后,通过查词典看哪些是有效的单词,并将这些有效的单词作为误拼字符串的纠错建议。

(3)词干法。通过构建词干词典,在英文单词出现错误时,先抽取出该错误单词的词干,然后再去查词干词典,将词典中与该单词具有相同词干的正确单词作为该单词的纠错建议。这种方法主要的难度在于构建词干词典上,需要对几乎所有的英文单词都进行分析,提取出每个单词的词干,或者称为骨架词;这种实现的工作量是巨大的,而且词干的选择非常重要,每个词干要有很好的区分度,才能给用户给出良好的纠错建议。

(4)N-gram法。基于n元文法,通过对大规模英文文本的统计得到单词与单词问的转移概率矩阵。当检测到某英文单词不在词典中时。查转移概率矩阵,取转移概率大于某给定阈值的单词为纠错建议。

(5)基于规则的技术。利用规则的形式将通常的拼写错误模式进行表示,这些规则可用来将拼写错误的单词转换为正确有效的单词。对于一个误拼字符串,应用所有合适的规则从词典中找到一些与之对应的单词作为候选结果;然后,对每个结果根据事先赋予生成它的规则的概率估计计算一个数值,依据这个数值对所有候选结果进行排序,把将排序靠前的结果当成纠错结果返回给用户。

关于英文拼写检查实现可参考:怎样写一个拼写检查器

四.中文纠错

主要考虑使用词典的方法和基于文本的分类贝叶斯去实现。

五.方言纠错

中文方言纠错实现比较功能,需要庞大字典,各地方言差异比较大,实现比较困难。

英文方言可以参考:Soundex

本文固定链接: http://www.chepoo.com/search-engine-correcting-design.html | IT技术精华网

【上一篇】
【下一篇】

搜索引擎纠错设计:目前有1 条留言

  1. 沙发
    :

    还不错哦

    [回复]

发表评论