拼写纠错设计 - quweiprotoss的日志 - 网易博客
一．计划解决的问题
1. 繁简转换
2. 拼音转汉字
3. 同音词拼写错误
4. 英文拼写错误
5. 形近词错误
6. 方言纠错
二. 核心思路
1. 繁体转简体是可以独立出来，最先处理。
2. 其它的4步从查询日志中找出纠错的候选查询词，全部在线下计算。
多数拼写纠错算法基于2 个基本原则(Introduction to IR 3.3.1节)：
1. 在多个拼写纠错的可选结果中，选择与原term 最相似的一个，当然这就要求有一个相似的标准。
2. 当两个候选term 与要纠错的term 一样相似时，选择最常见的那个term，比如，grunt和grant，都与grnt 差不多相似，最简单的办法就是看grant 和grunt 在文档中的各出现了多少次，将出现次数多的返回。另一种更常见的做法是把用户最常搜索的查询返回。再讨论一下纠错的功能如何展示的方案：
数据的问题：
要进行纠错，首先要确定什么是正确的查询，最简单的想法就是确定一个阈值，比如说前80%的搜索查询算是正确的搜索词，但这有一个问题，比如在Introduction to IR里的一个例子，如果很多用户不太确定一个热搜词，britney spears，很多人搜索时用的是britian spears, britney’s spears, brandy spears, prittany spears，这些词都有可能是前80%的，所以最先就要对搜索查询进行过滤后，才能认为它们是正确的，过滤的方法可以是下面介绍的方法之一。
三．具体步骤
1. 繁简转换
使用繁简转换表转换。
2. 拼音转汉字
拼音转汉字想法是较为直接的，建立一个以拼音为term的查询词索引，posting list中只保存查询频率最高的K个查询词。
|
zhijiucaotang |
子九草堂, 子久草堂 |
|
xufuniuza |
徐福牛杂, 许府牛杂, 徐府牛杂 |
|
shoujichongzhi |
手机冲值, 手机充值 |
这一步可以在自动提示中使用，但自动提示与它的区别是，自动提示在拼音输入了一部分的情况下也要提示，比如输入 “xufu”就要提示“许府牛杂”。
3. 同音词拼音写
同音词拼音写也基于同样的想法，但是需要一个可能出错的查询词列表，这个列表可以为借鉴于下列几种情况 (Introduction to IR 3.3.1节)
1. 以carot为例，返回有carot的文档，也返回一些包含纠错后的term carrot和torot的文档。
2. 与(1)相似，但仅当carot不在词典中时，返回纠错后的结果。
3. 与(1)相似，但仅当包含carot的文档数小于一个预定义的阈值时。
4. 当原始查询返回文档数小于预定义的阈值时，搜索引擎给出纠错后的词列表。
情况(1)相当于是对所有查询都进行纠错处理，发现那些搜索比较少的，就给出一个纠错提示，比如“天浴”搜索次数比较少，而“天娱”搜索次数比较多，那么在用户搜索“天浴”时就提示“天娱”，即使“天娱”也是一个正常的查询词。
情况(2)就是得到所以没有返回结果的查询列表。
情况(3)是一个查询它返回的文档数少于一个预定义阈值时，我认为这个是最合适的，因为文档中也可能有人把字写错，这样就有可能漏掉一些应该纠错的词，但这需要搜索引擎结合，看到底有多少返回了。
情况(4)就是我想应该用的表现形式。
4. 英文拼写错误
在lucene中已有贡献者实现了spellchecker模块，主要算法有：Jaro Winkler distance，Levenstein Distance(Edit Distance)，NGram Distance。
但Lucene中的实现过于简单，使用两两比较，时间复杂性是O(n2)，可以用Introduction to IR中的3.3.4节中介绍的，k-gram与编辑距离结合的方法算。
5. 形近字错误
形近字一般是用户记错了形声字，或是使用五笔的用户输入错误。在网上可以下载SunWb_mb文件，它里面包含五笔的编码和笔画的编码，但字根比如“马”比“口”笔画更多，也更有代表性，但在这种方法中却是相同的。
6. 方言纠错
可以用soudex进行纠错，Introduction to IR 3.4节。