• 中国精品科技期刊
  • 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]Wu Jinjin, Liu Quan, Chen Song, Yan Yan. Averaged Weighted Double Deep Q-Network[J]. Journal of Computer Research and Development, 2020, 57(3): 576-589. DOI: 10.7544/issn1000-1239.2020.20190159
    [2]Bai Chenjia, Liu Peng, Zhao Wei, Tang Xianglong. Active Sampling for Deep Q-Learning Based on TD-error Adaptive Correction[J]. Journal of Computer Research and Development, 2019, 56(2): 262-280. DOI: 10.7544/issn1000-1239.2019.20170812
    [3]Zhu Fei, Wu Wen, Liu Quan, Fu Yuchen. A Deep Q-Network Method Based on Upper Confidence Bound Experience Sampling[J]. Journal of Computer Research and Development, 2018, 55(8): 1694-1705. DOI: 10.7544/issn1000-1239.2018.20180148
    [4]Chen Tieming, Yang Yimin, Chen Bo. Maldetect: An Android Malware Detection System Based on Abstraction of Dalvik Instructions[J]. Journal of Computer Research and Development, 2016, 53(10): 2299-2306. DOI: 10.7544/issn1000-1239.2016.20160348
    [5]Fu Ning, Zhou Xingshe, Zhan Tao. QPi: A Calculus to Enforce Trustworthiness Requirements[J]. Journal of Computer Research and Development, 2011, 48(11): 2120-2130.
    [6]Liu Tao, He Yanxiang, Xiong Qi. A Q-Learning Based Real-Time Mitigating Mechanism against LDoS Attack and Its Modeling and Simulation with CPN[J]. Journal of Computer Research and Development, 2011, 48(3): 432-439.
    [7]Zhao Ming, Luo Jizhou, Li Jianzhong, and Gao Hong. XCluster: A Cluster-Based Queriable Multi-Document XML Compression Method[J]. Journal of Computer Research and Development, 2010, 47(5): 804-814.
    [8]Deng Shanshan, Sun yi, Zhang Lisheng, Mo Zhifeng, Xie Yingke. Design of HighSpeed FFT Processor for Length N=q×2\+m[J]. Journal of Computer Research and Development, 2008, 45(8): 1430-1438.
    [9]Han Jingyu, Xu Lizhen, and Dong Yisheng. An Approach for Detecting Similar Duplicate Records of Massive Data[J]. Journal of Computer Research and Development, 2005, 42(12): 2206-2212.
    [10]Li Ronglu, Wang Jianhui, Chen Xiaoyun, Tao Xiaopeng, and Hu Yunfa. Using Maximum Entropy Model for Chinese Text Categorization[J]. Journal of Computer Research and Development, 2005, 42(1): 94-101.

Catalog

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

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return