Advanced Search
    Sun Decai, Sun Xingming, Zhang Wei, and Liu Yuling. A Filter Algorithm for Approximate String Matching Based on Match-Region Features[J]. Journal of Computer Research and Development, 2010, 47(4): 663-670.
    Citation: Sun Decai, Sun Xingming, Zhang Wei, and Liu Yuling. A Filter Algorithm for Approximate String Matching Based on Match-Region Features[J]. Journal of Computer Research and Development, 2010, 47(4): 663-670.

    A Filter Algorithm for Approximate String Matching Based on Match-Region Features

    More Information
    • Published Date: April 14, 2010
    • Approximate string matching is a basic problem in computer science. It is widely used in various areas. The 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. Firstly, a q-gram index is used to preprocess text. Secondly, 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 criterion by the new features. Finally, the improved method of choosing filtration-region based on QUASARs block addressing is used for filtration. The experimental results demonstrate that the algorithm achieves higher matching speed than that of QUASARs block addressing by way of improving filtration efficiency. In particular, its matching speed is much faster under low error rate. Experiments also reveal the relationship between matching speed and error rate of new algorithm. These results suggest that the algorithm is useful in a system for approximate string matching with low error rate. It is also powerful for long pattern approximate string matching on the condition of fixed edit distance k.
    • Related Articles

      [1]Xie Qin, Zhang Qinghua, Wang Guoyin. An Adaptive Three-way Spam Filter with Similarity Measure[J]. Journal of Computer Research and Development, 2019, 56(11): 2410-2423. DOI: 10.7544/issn1000-1239.2019.20180793
      [2]Song Jinfeng, Wen Lijie, Wang Jianmin. A Similarity Measure for Process Models Based on Task Occurrence Relations[J]. Journal of Computer Research and Development, 2017, 54(4): 832-843. DOI: 10.7544/issn1000-1239.2017.20151176
      [3]Zhao Yongwei, Zhou Yuan, Li Bicheng. Object Retrieval Based on Enhanced Dictionary and Spatially-Constrained Similarity Measurement[J]. Journal of Computer Research and Development, 2016, 53(5): 1043-1052. DOI: 10.7544/issn1000-1239.2016.20150070
      [4]Wang Shaopeng, Wen Yingyou, Zhao Hong. Similarity Query Processing Algorithm over Data Stream Based on LCSS[J]. Journal of Computer Research and Development, 2015, 52(9): 1976-1991. DOI: 10.7544/issn1000-1239.2015.20140479
      [5]Xiao Yu and Yu Jian. A Weighted Self Adaptive Similarity Measure[J]. Journal of Computer Research and Development, 2013, 50(9): 1876-1882.
      [6]Shen Qingni, Du Hong, Wen Han, Qing Sihan. A Data Sealing Approach Based on Integrity Measurement Architecture[J]. Journal of Computer Research and Development, 2012, 49(1): 210-216.
      [7]Zhu Yangyong, Dai Dongbo, and Xiong Yun. A Survey of the Research on Similarity Query Technique of Sequence Data[J]. Journal of Computer Research and Development, 2010, 47(2): 264-276.
      [8]Xing Chunxiao, Gao Fengrong, Zhan Sinan, Zhou Lizhu. A Collaborative Filtering Recommendation Algorithm Incorporated with User Interest Change[J]. Journal of Computer Research and Development, 2007, 44(2): 296-301.
      [9]Liu Bing, Yan Heping, Duan Jiangjiao, Wang Wei, and Shi Baile. A Bottom-Up Distance-Based Index Tree for Metric Space[J]. Journal of Computer Research and Development, 2006, 43(9): 1651-1657.
      [10]Xiu Yu, Wang Shitong, Wu Xisheng, Hu Dewen. The Directional Similarity-Based Clustering Method DSCM[J]. Journal of Computer Research and Development, 2006, 43(8): 1425-1431.

    Catalog

      Article views (793) PDF downloads (613) Cited by()

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return