大规模中英文单词模糊搜索问题的分析(二)

deltamaster posted @ Sep 22, 2011 10:39:52 AM in 人工智能 with tags 索引 匹配 模糊搜索 拼写检查 , 2694 阅读

  经过了大约一个星期时间的考虑,也研究了一下各种开源项目的情况。

  本来满怀期待地发现了拼写检查器Jazzy的源码研究起来,不过后来发现Jazzy已经两年无人问津了,还是有那么点失望的,不过总的来讲,从拼写检查这个思路上,还是找到了一点新的思路的。

  原来使用编辑距离的方法计算单词之间的距离,现在这个核心思想还是没有变,在索引的问题上也有了更多一些的考虑。

  目前考虑下来的主要处理流程是这样的:

1. 对所有库中的人名进行分词,英文按照单词边界进行拆分,而中文按照单个汉字进行拆分,拆分完的汉字全部转换为拼音,这一步比较简单。完成以后就产生了两张二维表,分别是单词表(词典,包含单词、引用计数、是否来自黑名单数据)和倒排索引表(包含单词id、数据库原始条目的id、单词index)。这样就完成了类似Lucene的倒排索引。

2. 为了更好地计算编辑距离,需要建立四张编辑距离权值表(二维表replacement、swap和一维表insert、delete),四张表都不是十分精确的,但是作为索引确实没有十分精确的必要,因为具体的相似度还是依赖于对于单条记录的详细检查。

3. 服务器守护进程随时以流水线方式处理单词与单词之间的相似关系,采用拼写检查器的方法找到字典中的近似单词。

4. 实际向服务器送出查找请求时,服务器首先找到能够精确匹配所有单词的条目,逐条进行相似度检查。如果结果已经过多,那么没有必要再进行后续的查找。如结果较少,那么继续匹配部分单词完全匹配的条目。

5. 如果结果仍然较少,则首先根据编辑距离权值表进行短距离的变换,尝试匹配变换后的结果。

6. 如果仍然没有足够的结果,那么去查找单词近似关系表,如果该单词的近似条目可用,则立即查询得到结果。

7. 如果该单词的近似关系表还没有建立完成,那么提高该单词近似关系处理的优先级,使其立即完成,并进行结果查询。

8. 如果根据待测样本中存在于字典中的单词无法找到足够的项,那么进一步查找不存在于字典中的项,查找流程按照5、6、7的方式进行,建立完成后该单词会被增加到字典中,用以加速下一次的查找。

* 本文在CC BY-SA(署名-相同方式共享)协议下发布。

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter