一种基于匹配区域特征的相似字符串匹配过滤算法

he aim of this study is to improve the speed of approximate string matching. Filter algorithm for approximate string matching is discussed because it is suitable for large-scale text searching. A novel filter algorithm based on Match-Region features is presented. First, a q-gram index is used to preprocess text. Second, both pattern and text are logically divided into blocks of fixed size kq+1, and then new Match-Region features are extracted from blocks, and the algorithm optimizes the fundamental q-gram filtration lemma by the new features. Last, the improved method of choosing Filtration-Region based on blocks is used for filtration. The experimental results demonstrate that the algorithm achieves higher matching speed by way of improving filtration efficiency, and they also reveal the relationship between matching speed and error rate of new algorithm. In particular, its matching speed is faster than that of QUASAs’s Block Addressing under low error rate. These results suggest that the algorithm is useful in a system for approximate string matching with low error rate.