基于多重索引模型的大规模词典近似匹配算法

发布时间：2018-04-19 06:39

本文选题：模式匹配 + 近似匹配　；参考：《计算机研究与发展》2008年10期

【摘要】：编辑器的拼写校正、搜索引擎的查询纠正、光学字符识别的结果检查等领域都用到词典近似匹配算法.传统单索引模式很难在高性能的前提下保证高召回率.词典越大问题越严重.提出了大规模词典近似匹配的多重索引模型,首先将背景词典根据单词长度划分为若干子词典,对各子词典按照一定策略建立unigram,bigram,trigram,quadgram中的一种或若干种索引,当查找用户模式P的近似匹配时,根据模式P检索特定N-gram索引链,从而得到候选近似匹配集合C,对C中每一个单词W,计算P与W的编辑距离即可输出P的所有最终匹配结果R.实验表明,基于多重索引模型的词典近似匹配算法能够大幅度减少候选近似匹配结果的数量,从而提高词典近似匹配的速度.
[Abstract]:Dictionary approximate matching algorithm is used in spelling correction of editor, query correction of search engine and result checking of optical character recognition.It is difficult for traditional single index mode to guarantee high recall rate on the premise of high performance.The bigger the dictionary, the more serious the problem.A multi-index model for approximate matching of large-scale dictionaries is proposed. Firstly, the background dictionaries are divided into several sub-dictionaries according to the word length, and one or more indexes in unigram-bigram-trigram-quadgram are established for each sub-dictionary according to a certain strategy.When the approximate matching of user pattern P is searched, a specific N-gram index chain is retrieved according to pattern P, and the candidate approximate matching set C is obtained. For each word in C, the editing distance between P and W can be calculated and all final matching results of P can be outputted.The experimental results show that the dictionary approximate matching algorithm based on multi-index model can greatly reduce the number of candidate approximate matching results and improve the speed of dictionary approximate matching.
【作者单位】：中国科学院计算技术研究所;北京市计算中心;
【基金】：国家“九七三”重点基础研究发展规划基金项目(2004CB318109,2007CB311100) 国家“八六三”高技术研究发展计划基金项目(2006AA010105,2007AA01Z416)~~
【分类号】：TP301.6

【共引文献】