大规模中英文单词模糊搜索问题的分析（二）
经过了大约一个星期时间的考虑，也研究了一下各种开源项目的情况。
本来满怀期待地发现了拼写检查器Jazzy的源码研究起来，不过后来发现Jazzy已经两年无人问津了，还是有那么点失望的，不过总的来讲，从拼写检查这个思路上，还是找到了一点新的思路的。
原来使用编辑距离的方法计算单词之间的距离，现在这个核心思想还是没有变，在索引的问题上也有了更多一些的考虑。
目前考虑下来的主要处理流程是这样的：
1. 对所有库中的人名进行分词，英文按照单词边界进行拆分，而中文按照单个汉字进行拆分，拆分完的汉字全部转换为拼音，这一步比较简单。完成以后就产生了两张二维表，分别是单词表（词典，包含单词、引用计数、是否来自黑名单数据）和倒排索引表（包含单词id、数据库原始条目的id、单词index）。这样就完成了类似Lucene的倒排索引。
2. 为了更好地计算编辑距离，需要建立四张编辑距离权值表（二维表replacement、swap和一维表insert、delete），四张表都不是十分精确的，但是作为索引确实没有十分精确的必要，因为具体的相似度还是依赖于对于单条记录的详细检查。
3. 服务器守护进程随时以流水线方式处理单词与单词之间的相似关系，采用拼写检查器的方法找到字典中的近似单词。
4. 实际向服务器送出查找请求时，服务器首先找到能够精确匹配所有单词的条目，逐条进行相似度检查。如果结果已经过多，那么没有必要再进行后续的查找。如结果较少，那么继续匹配部分单词完全匹配的条目。
5. 如果结果仍然较少，则首先根据编辑距离权值表进行短距离的变换，尝试匹配变换后的结果。
6. 如果仍然没有足够的结果，那么去查找单词近似关系表，如果该单词的近似条目可用，则立即查询得到结果。
7. 如果该单词的近似关系表还没有建立完成，那么提高该单词近似关系处理的优先级，使其立即完成，并进行结果查询。
8. 如果根据待测样本中存在于字典中的单词无法找到足够的项，那么进一步查找不存在于字典中的项，查找流程按照5、6、7的方式进行，建立完成后该单词会被增加到字典中，用以加速下一次的查找。
大规模中英文单词模糊搜索问题的分析
最近有一个关于在大规模的中英文词库中的模糊搜索问题。
这个问题具有几个特点：
- 每条记录都比较短。
- 记录的数量多，大约600万条记录。
- 对解的数量要求高于对解的质量要求。
- 有对中英文支持的要求。
对于单一的字符串模糊匹配问题，实际上是单纯的人工智能问题，站在模式识别的角度，就是计算与目标单词的距离，我们实际上需要通过求最一般合一来算出单词之间的编辑距离，这个编辑距离越大，匹配度就越低。如果想更进一步，那么借助遗传算法的思想，随着用户的操作来动态调整每一步编辑的权值（默认所有编辑行为的权值都为1），如果用户认可某次匹配，则对此次匹配所用到的所有编辑行为降低权值。
而对于这样的一个实际问题，首先我们不可能将600万条记录全部取出逐一检测匹配度，势必要进行一个事先的筛选。因此，大致的流程应该是这样：
- 针对所有数据建立倒排索引。
- 从索引查找到疑似的匹配项。
- 对疑似匹配项的匹配度进行逐个检查，去掉匹配度低的结果。
- 按匹配度从高到低输出结果。
针对此问题，还有以下一些问题需要解决。
而求编辑距离必须使用基于代价函数的广度优先搜索，否则，无法保证最优解，在权值全部相同的情况下，就等同于一般的广度优先搜索，修改步数增加以后，内存开销明显增加。
为了减小索引，加快索引速度，必须要合并类似的索引项，对于中文，根据拼音-汉字库将汉字一律合并至为对应拼音是可行的。
但是对于英文，不可能以字符为单位进行索引，而如果以单词为单位进行索引，拼写错误就无法从索引中找出相应项。如果对无法找到的项进行广度优先的编辑，试图从索引中找出最近似的条目，对于索引查询的开销也是极高的。
单词拆分对索引也是一个考验，因为如果某个单词无法匹配，其实则可能可以进行拆分，比如helloworld，有9种方法分成两个单词，那么需要对9种拆分方法逐个进行查询，开销也是很大的。如果在这个基础上再考虑拼写错误，那么开销就是平方级的增长了。
