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

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

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

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

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

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

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

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

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

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

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

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

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

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

* 本文在CC BY-SA(署名-相同方式共享)协议下发布。
PFMS Login 说:
Nov 04, 2022 09:36:03 PM

The public financial management system (PFMS) is a scholarship program that helps students from poverty-stricken families. The plan pays fees for the students giving a bright and equal chance to all students. PFMS Login Pfms scholarship 2022 caters to students in the backward category, schedule caste, scheduled tribe, and other different backward castes in the country. The public financial management system initiated this program.


登录 *


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