摘要
Multi-pattern matching is a core technique of many applications. However, many of the existing algorithms cannot efficiently deal with large pattern sets or pattern sets with very short patterns. To address these issues, in this paper, an adaptive architecture for multi-pattern matching (AAMPM), which is based on a new data structure called adaptive matching tree (AMT), is proposed. In particular, each tree node in AMT saves only some pattern fragments of the whole pattern set, and the inner data structure of each tree node is adaptively chosen according to the features of those pattern fragments. Due to this adaptivity, each tree node can take as little memory as possible, additionally, matching the text fragments with the pattern fragments in the tree nodes can be very efficient. Based on AMT, AAMPM adopts an effective approach to search patterns in the text string. The experimental results show that, AAMPM has a strong robustness on pattern sets with short patterns. Moreover, due to the good scalability of AMT, AAMPM offers an excellent support for large pattern sets.
延伸閱讀
- 王彥凱（2008）。A Regular Expression Pattern Matching Architecture with Common String Sharing Scheme〔碩士論文，國立臺灣大學〕。華藝線上圖書館。https://doi.org/10.6342/NTU.2008.00673
- Tsai, W. Y. (2006). A Novel Multi-pattern Matching Algorithm and Implementation in SoC System [master's thesis, National Tsing Hua University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0016-1303200709331594
- Lai, S. H. (2007). On the Design of a GPU-based Multiple-Pattern Matching Algorithm [master's thesis, National Tsing Hua University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0016-1411200715162266
- Wei, S. D. (2008). Efficient and Robust Pattern Matching Algorithms for Different Applications [doctoral dissertation, National Tsing Hua University]. Airiti Library. https://doi.org/10.6843/NTHU.2008.00028
- Tai, Y. T. (2007). Optimization of Pattern Matching Algorithm for Memory Based Architecture [master's thesis, National Tsing Hua University]. Airiti Library. https://doi.org/10.6843/NTHU.2007.00105