• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
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]Li Yuan, Yang Sen, Sun Jing, Zhao Huiqun, Wang Guoren. Influential Cohesive Subgraph Discovery Algorithm in Dual Networks[J]. Journal of Computer Research and Development, 2023, 60(9): 2096-2114. DOI: 10.7544/issn1000-1239.202220337
    [2]Li Xin, Liu Guiquan, Li Lin, Wu Zongda, Ding Junmei. Circle-Based and Social Connection Embedded Recommendation in LBSN[J]. Journal of Computer Research and Development, 2017, 54(2): 394-404. DOI: 10.7544/issn1000-1239.2017.20150788
    [3]Yuan Xinpan, Long Jun, Zhang Zuping, Luo Yueyi, Zhang Hao, and Gui Weihua. Connected Bit Minwise Hashing[J]. Journal of Computer Research and Development, 2013, 50(4): 883-890.
    [4]Jiao Jian, Yao Shan, Li Xiaojian. Research on Network Bidirectional Topology Discovery Based on Measurer by Spreading[J]. Journal of Computer Research and Development, 2010, 47(5): 903-910.
    [5]Jin Xin, Xiong Yan, Li Min, and Yue Lihua. A Connectible-Cell Based Topology Control Algorithm for Wireless Sensor Networks[J]. Journal of Computer Research and Development, 2008, 45(2): 217-226.
    [6]Liu Wei, Cui Li, Huang Changcheng. EasiFCCT:A Fractional Coverage Algorithm for Wireless Sensor Networks[J]. Journal of Computer Research and Development, 2008, 45(1): 196-204.
    [7]Yang Liu, Li Zhenyu, Zhang Dafang, Xie Gaogang. Topology Discovery with Smallest-Redundancy in IPv6[J]. Journal of Computer Research and Development, 2007, 44(6): 939-946.
    [8]Sun Yantao, Shi Zhiqiang, Wu Zhimei. Automatic Discovery of Physical Topology in Switched Ethernets[J]. Journal of Computer Research and Development, 2007, 44(2): 208-215.
    [9]Zhu Pengfei, Dai Yingxia, and Bao Xuhua. PKI-Based Mutual Connections Constrained with Discrepancy of Trust Domains[J]. Journal of Computer Research and Development, 2006, 43(10): 1804-1809.
    [10]Wen Yingyou, Zhao Jianli, Zhao Linliang, and Wang Guangxing. A Study of the Relationship Between Performance of Topology-Based MANET Routing Protocol and Network Coverage Density[J]. Journal of Computer Research and Development, 2005, 42(4): 684-689.
  • Cited by

    Periodical cited type(0)

    Other cited types(1)

Catalog

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

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return