Realization of regex expression matching algorithm based on list storage

Haoming Liu; Lu Sun; Shaofeng Dong; Enlin Zhang; Wei Hu; Jinsong Zhan

doi:10.1117/12.3014985

4 March 2024 Realization of regex expression matching algorithm based on list storage

Haoming Liu, Lu Sun, Shaofeng Dong, Enlin Zhang, Wei Hu, Jinsong Zhan

Proceedings Volume 12981, Ninth International Symposium on Sensors, Mechatronics, and Automation System (ISSMAS 2023); 129815T (2024) https://doi.org/10.1117/12.3014985
Event: 9th International Symposium on Sensors, Mechatronics, and Automation (ISSMAS 2023), 2023, Nanjing, China

Abstract

Regular expression matching based on FPGA has been widely used in many fields due to its high efficiency. However, FPGA hardware resources are limited, so it is necessary to optimize the utilization of circuit resources by minimizing the number of components and memory resources. When the regular expression has repeated qualification rules and range matching rules, the syntax tree generated by Mcnaughton’s MY algorithm is too long, resulting in the mapped circuit structure being too complex. An improved algorithm based on list storage is presented, which can effectively solve the resource waste caused by repeated qualification and range-matching rules. The implementation process of the MY algorithm was initially introduced in this paper, and the stored table algorithm was proposed. Subsequently, the circuit mapping algorithm was extended, and the accuracy and resource consumption of the algorithm was simulated using the Vivado platform. It is indicated by the results that the resource consumption caused by the repeated constraint rule “{}” and the range matching rule “[]” can be effectively reduced by the list storage algorithm, with the most resource-saving rule achieving up to 95% resource savings.

(2024) Published by SPIE. Downloading of the abstract is permitted for personal use only.

Citation Download Citation

Haoming Liu, Lu Sun, Shaofeng Dong, Enlin Zhang, Wei Hu, and Jinsong Zhan "Realization of regex expression matching algorithm based on list storage", Proc. SPIE 12981, Ninth International Symposium on Sensors, Mechatronics, and Automation System (ISSMAS 2023), 129815T (4 March 2024); https://doi.org/10.1117/12.3014985

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
6 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Field programmable gate arrays

Logic

Computer simulations

Computer intrusion detection

Device simulation

Computer networks

Mathematical optimization

Show All Keywords

Keywords/Phrases

Search In:

Publication Years