• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
Liu Yanbing, Liu Ping, Tan Jianlong, Guo Li. A Multiple String Matching Algorithm Based on Memory Optimization[J]. Journal of Computer Research and Development, 2009, 46(10): 1768-1776.
Citation: Liu Yanbing, Liu Ping, Tan Jianlong, Guo Li. A Multiple String Matching Algorithm Based on Memory Optimization[J]. Journal of Computer Research and Development, 2009, 46(10): 1768-1776.

A Multiple String Matching Algorithm Based on Memory Optimization

More Information
  • Published Date: October 14, 2009
  • Multiple string matching algorithms play a fundamental role in many network security systems, such as intrusion detection and prevention systems, anti-virus systems, anti-spam systems, firewall, etc. It has been observed that the memory space usage and cache locality of automata are critical factors affecting multiple string matching algorithms searching speed. As the pattern set size grows larger and larger, classical multiple string matching algorithms suffer from great performance degradation because of the massive storage usage of string matching automata. The authors propose optimization strategies for the classical string matching algorithm SBOM to reduce its automata size and improve its cache locality, which results in a great promotion in searching speed. More specifically, the Factor Oracle of SBOM algorithm is first replaced with a suffix tree structure, and then the rarely accessed automata nodes are removed through the pruning method to reduce suffix tree to nearly linear space complexity, and finally the pruned suffix tree is represented with double-array trie structure to compress its memory space. Compared with SBOM, this algorithm can greatly reduce memory usage and improve searching speed. Experiments on random data sets show that the proposed algorithm uses memory less than 5% of SBOM and achieves 100% performance improvement over SBOM algorithm. The proposed algorithm is especially suitable for high-speed online pattern matching.
  • Related Articles

    [1]Fan Hongbo, Yao Nianmin. Fast Building Method of Advanced AC Automaton[J]. Journal of Computer Research and Development, 2013, 50(12): 2699-2706.
    [2]Xie Zhengwei, Zhai Ying, Deng Peimin, Yi Zhong. Algebraic Properties of Probabilistic Finite State Automata[J]. Journal of Computer Research and Development, 2013, 50(12): 2691-2698.
    [3]Zhou Yousheng, Wang Feng, Qing Sihan, Yang Yixian, Niu Xinxin. Dynamic Multi-Secret Sharing Scheme Based on Cellular Automata[J]. Journal of Computer Research and Development, 2012, 49(9): 1999-2004.
    [4]Fang Min, Niu Wenke, Zhang Xiaosong. Multiple Attractor Cellular Automata Classification Method and Over-Fitting Problem with CART[J]. Journal of Computer Research and Development, 2012, 49(8): 1747-1752.
    [5]Wei Qingting, Guan Jihong, Zhou Shuigeng. A Schema-Based Approach to GML Compression[J]. Journal of Computer Research and Development, 2011, 48(9): 1704-1713.
    [6]Peng Wu, Hu Changzhen, Yao Shuping, Wang Zhigang. A Dynamic Intrusive Intention Recognition Method Based on Timed Automata[J]. Journal of Computer Research and Development, 2011, 48(7): 1288-1297.
    [7]Xi Zhengjun, Wang Xin, and Li Yongming. The Equivalence Between Quantum Mealy Automata and Quantum Moore Automata[J]. Journal of Computer Research and Development, 2009, 46(9): 1523-1529.
    [8]Yao Xinghua, Deng Peimin, Yi Zhong, Jiang Yuncheng. A Decomposition of the Weakly Invertible Linear Finite Automata[J]. Journal of Computer Research and Development, 2009, 46(6): 1043-1051.
    [9]Zhang Junhua, Huang Zhiqiu, and Cao Zining. Counterexample Generation for Probabilistic Timed Automata Model Checking[J]. Journal of Computer Research and Development, 2008, 45(10): 1638-1645.
    [10]Wang Hongji. Two Results of Decomposing Weakly Invertible Finite Automata[J]. Journal of Computer Research and Development, 2005, 42(4): 690-696.

Catalog

    Article views (809) PDF downloads (776) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return