• 中国精品科技期刊
  • 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]Li Ping, Song Shuhan, Zhang Yuan, Cao Huawei, Ye Xiaochun, Tang Zhimin. HSEGRL: A Hierarchical Self-Explainable Graph Representation Learning Model[J]. Journal of Computer Research and Development, 2024, 61(8): 1993-2007. DOI: 10.7544/issn1000-1239.202440142
    [2]Wang Lei, Xiong Yuning, Li Yunpeng, Liu Yuanyuan. A Collaborative Recommendation Model Based on Enhanced Graph Convolutional Neural Network[J]. Journal of Computer Research and Development, 2021, 58(9): 1987-1996. DOI: 10.7544/issn1000-1239.2021.20200617
    [3]Chen Jinyin, Huang Guohan, Zhang Dunjie, Zhang Xuhong, Ji Shouling. GRD-GNN: Graph Reconstruction Defense for Graph Neural Network[J]. Journal of Computer Research and Development, 2021, 58(5): 1075-1091. DOI: 10.7544/issn1000-1239.2021.20200935
    [4]Liu Zitu, Quan Ziwei, Mao Rubai, Liu Yong, Zhu Jinghua. NT-EP: A Non-Topology Method for Predicting the Scope of Social Message Propogation[J]. Journal of Computer Research and Development, 2020, 57(6): 1312-1322. DOI: 10.7544/issn1000-1239.2020.20190584
    [5]Hai Mo, Zhu Jianming. A Propagation Mechanism Combining an Optimal Propagation Path and Incentive in Blockchain Networks[J]. Journal of Computer Research and Development, 2019, 56(6): 1205-1218. DOI: 10.7544/issn1000-1239.2019.20180419
    [6]Liu Linlan, Zhang Jiang, Shu Jian, Guo Kai, Meng Lingchong. Multiple Attribute Decision Making-Based Prediction Approach of Critical Node for Opportunistic Sensor Networks[J]. Journal of Computer Research and Development, 2017, 54(9): 2021-2031. DOI: 10.7544/issn1000-1239.2017.20160645
    [7]Tian Jianwei, Tian Zheng, Qi Wenhui, Hao Hanyong, Li Renfa, Li Xi, Qiao Hong, Xue Haiwei. Threat Propagation Based Security Situation Quantitative Assessment in Multi-Node Network[J]. Journal of Computer Research and Development, 2017, 54(4): 731-741. DOI: 10.7544/issn1000-1239.2017.20161015
    [8]Zhang Yushu, Wang Huiqiang, Feng Guangsheng, Lü Hongwu. Message Dissemination Based on Interest Matching for Opportunistic Social Networks[J]. Journal of Computer Research and Development, 2016, 53(6): 1365-1375. DOI: 10.7544/issn1000-1239.2016.20148412
    [9]Cai Qingsong, Niu Jianwei, Liu Yan. Message Delivery Properties in Opportunistic Networks[J]. Journal of Computer Research and Development, 2011, 48(5): 793-801.
    [10]Niu Jianwei, Zhou Xing, Liu Yan, Sun Limin, Ma Jian. A Message Transmission Scheme for Community-Based Opportunistic Network[J]. Journal of Computer Research and Development, 2009, 46(12): 2068-2075.
  • Cited by

    Periodical cited type(2)

    1. 陶蔚,陇盛,刘鑫,胡亚豪,黄金才. 深度学习步长自适应动量优化方法研究综述. 小型微型计算机系统. 2025(02): 257-265 .
    2. 曲军谊. 基于对偶平均的动量方法研究综述. 计算机与数字工程. 2022(11): 2443-2448 .

    Other cited types(4)

Catalog

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

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return