Hardware Architecture for High-Performance Regular Expression Matching

檔案

日期

2009-07-01

類型

期刊名稱

IEEE TRANSACTIONS ON COMPUTERS

卷期與頁次

第 58 卷第 7 期,頁 984–993

ISSN

0018-9340

語言

英文

摘要

This paper presents a bitmap-based hardware architecture for the Glushkov nondeterministic finite automaton (G-NFA), which recognizes a given regular expression. We show that the inductions of the functions needed to construct the G-NFA can be generalized to include other special symbols commonly used in extended regular expressions such as the POSIX 1003.2 format. Our proposed implementation can detect the ending positions of all substrings of an input string T, which start at arbitrary positions of T and belong to the language defined by the given regular expression. To achieve high performance, the implementation is generalized to the NFA, which processes K symbols in each operation cycle. We provide an efficient solution for the boundary condition when the length of the input string is not an integral multiple of K. Compared with previous designs, our proposed architecture is more flexible and programmable because the pattern matching engine uses memory rather than logic.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Lee, T.-H. (2009). Hardware Architecture for High-Performance Regular Expression Matching. IEEE TRANSACTIONS ON COMPUTERS, 58(7), 984–993. https://doi.org/10.1109/TC.2008.145

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/7073