• 中国精品科技期刊
  • 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]Liu Yanfang, Li Wenbin, Gao Yang. Adaptive Neighborhood Embedding Based Unsupervised Feature Selection[J]. Journal of Computer Research and Development, 2020, 57(8): 1639-1649. DOI: 10.7544/issn1000-1239.2020.20200219
    [2]Yao Sheng, Xu Feng, Zhao Peng, Ji Xia. Intuitionistic Fuzzy Entropy Feature Selection Algorithm Based on Adaptive Neighborhood Space Rough Set Model[J]. Journal of Computer Research and Development, 2018, 55(4): 802-814. DOI: 10.7544/issn1000-1239.2018.20160919
    [3]Zhang Yuanpeng, Deng Zhaohong, Chung Fu-lai, Hang Wenlong, Wang Shitong. Fast Self-Adaptive Clustering Algorithm Based on Exemplar Score Strategy[J]. Journal of Computer Research and Development, 2018, 55(1): 163-178. DOI: 10.7544/issn1000-1239.2018.20160937
    [4]Gu Lianchao, Cui Lizhen. A Scalable and Self-Adjust Multi-Tenant Data Storage Strategy Under Different SLAs[J]. Journal of Computer Research and Development, 2014, 51(9): 2058-2069. DOI: 10.7544/issn1000-1239.2014.20131339
    [5]Bi Xiaojun, Liu Guo'an, Xiao Jing. Dynamic Adaptive Differential Evolution Based on Novel Mutation Strategy[J]. Journal of Computer Research and Development, 2012, 49(6): 1288-1297.
    [6]Gong Maoguo, Cheng Gang, Jiao Licheng, and Liu Chao. Nondominated Individual Selection Strategy Based on Adaptive Partition for Evolutionary Multi-Objective Optimization[J]. Journal of Computer Research and Development, 2011, 48(4): 545-557.
    [7]Fan Xiaoqin, Jiang Changjun, Fang Xianwen, Ding Zhijun. Dynamic Web Service Selection Based on Discrete Particle Swarm Optimization[J]. Journal of Computer Research and Development, 2010, 47(1): 147-156.
    [8]Zeng Zhiqiang, Wu Qun, Liao Beishui, Zhu Shunzhi. An Improved Working Set Selection Strategy for Sequential Minimal Optimization Algorithm[J]. Journal of Computer Research and Development, 2009, 46(11): 1925-1933.
    [9]Liu Anfeng, Chen Zhigang, Long Guoping, and Zeng Zhiwen. A Resource Optimizing Scheduling Algorithm of Differentiated Service of Double Minimum Balance in Web Clusters[J]. Journal of Computer Research and Development, 2005, 42(11): 1969-1976.
    [10]Xu Mingwei, Hu Chunming, Liu Xudong, and Ma Dianfu. Research and Implementation of Web Service Differentiated QoS[J]. Journal of Computer Research and Development, 2005, 42(4): 669-675.

Catalog

    Article views (805) PDF downloads (617) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return