Bit-packing method for lightening NFA data structure in extended regular expression matching process, apparatus and computer program for performing the method

Patent metadata

Field	Value
Publication number	US-12423228-B2
Application number	US-202218061849-A
Country	US
Kind code	B2
Filing date	Dec 5, 2022
Priority date	Oct 21, 2022
Publication date	Sep 23, 2025
Grant date	Sep 23, 2025

Abstract

According to the exemplary embodiment of the present disclosure, according to a bit-packing method for lighting an NFA data structure during a process of matching an extended regular expression, an apparatus and a computer program for performing the same, the nondeterministic finite-state automation (NFA) is bit-packed to be stored during the process of matching the extended regular expression to efficiently store a huge amount of regular equation patterns.

First claim

What is claimed is:

1. A bit-packing method for lightening a nondeterministic finite state automation (NFA) data structure in an extended regular expression matching process, comprising:
generating a nondeterministic finite state automation (NFA) corresponding to an extended regular expression; and
storing the nondeterministic finite state automation (NFA) according to a previously determined bit-packing reference,
wherein the generating of a nondeterministic finite state automation (NFA) is configured by generating the nondeterministic finite state automaton (NFA) corresponding to the extended regular expression using a Glushkov automaton transformed such that trunk lines starting from one vertex have the same label.

2. The bit-packing method according to claim 1 , wherein the storing is configured by storing each vertex of the nondeterministic finite automaton (NFA) in a continuous bit stream, configuring an intermediate vertex with a label and beginning addresses of vertexes adjacent to the intermediate vertex when the vertex is the intermediate vertex rather than a beginning vertex and an ending vertex, configuring the beginning vertex only with a beginning address of a vertex adjacent to the beginning vertex when the vertex is the beginning vertex, and configuring the vertex only with an end label when the vertex is the ending vertex, according to the bit-packing reference.

3. The bit-packing method according to claim 2 , wherein the storing is configured by encoding a label using two most significant bits of a first byte as No-address (N-) flag and a Loop (L-) flag according to the bit-packing reference.

4. The bit-packing method according to claim 3 , wherein the storing is configured by designating six least significant bits of the first byte by 000001, designating the most significant bit of a second byte by 0, according to the bit-packing reference, and encoding a literal label using seven unused bits of the second byte to write the ASCII code.

5. The bit-packing method according to claim 4 , wherein the storing is configured by encoding an anchor label by designating third and fourth most significant bits of the first byte by 00 and four least significant bits of the first byte to one of six values of 0010 by 0111.

6. The bit-packing method according to claim 5 , wherein the storing is configured by encoding a character class label by designating third and fourth most significant bits of the first byte by 01, using a fifth most significant bit of the first byte as Invert (I-) flag, using three least significant bits of the first byte to write a number n of range expressing in the character class, designating three least significant bits of the first byte by 0 when the number of range expressed in the character class exceeds 7 which is a maximum value expressed by three bits, and using a second byte to write the number n of range expressed in the character class, according to the bit-packing reference.

7. The bit-packing method according to claim 6 , wherein the storing is configured by encoding a lookahead label by designating six least bits of the first byte by 000001, designating two most significant bits of the second byte by 10 when the vertex is a beginning vertex, and designating two most significant bits of the second byte by 11 and designating six least significant bits of the second byte by 000000 when the vertex is an ending vertex, according to the bit-packing reference.

8. The bit-packing method according to claim 7 , wherein the storing is configured by encoding a capture group label by designating third and fourth most significant bits of the first byte by 10 and using four least significant bits of the first byte to write a group number, according to the bit-packing reference and
encoding a backreferencing label by designating third and fourth most significant bits of the first byte by 11 and using four least significant bits of the first byte to write a reference number, according to the bit-packing reference.

9. The bit-packing method according to claim 8 , wherein the storing is configured by encoding the end label by designating one byte in which all bits are 1, according to the bit-packing reference.

10. The bit-packing method according to claim 9 , wherein the storing is configured by encoding an address by using one or more bytes to write one address, designating the most significant bit of the last byte for one address by 0, designating the most significant bit of bytes rather than the last byte for one address by 1, designating a second most significant bit of the last byte for an address of a final adjacent vertex to one vertex by 0, and designating a second most significant bit of a last byte for one address of a vertex which is not a final adjacent vertex to one vertex by 1, according to the bit-packing reference.

11. A computer program stored in a non-transitory computer readable storage medium to allow a computer to execute the bit-packing method for lightening an NFA data structure in an extended regular expression matching process according to claim 1 .

12. A bit-packing apparatus for lightening a nondeterministic finite state automation (NFA) data structure in an extended regular expression matching process, comprising:
a memory which stores one or more programs to bit-pack and store the nondeterministic finite state automaton (NFA) in an extended regular expression matching process; and
one or more processors which perform an operation of bit-packing and storing the nondeterministic finite state automaton (NFA) in an extended regular expression matching process according to one or more programs stored in the memory,
wherein the processor is configured to generate a nondeterministic finite state automation (NFA) corresponding to an extended regular expression; and store the nondeterministic finite state automation (NFA) according to a previously determined bit-packing reference,
wherein the processor is configured by generating the nondeterministic finite state automaton (NFA) corresponding to the extended regular expression using a Glushkov automaton transformed such that trunk lines starting from one vertex have the same label.

Assignees

• Uif Univ Industry Foundation Yonsei Univ

Inventors

• Han Yo-Sub
• Hahn Joonghyuk
• Sung Sicheol

Classifications

• G06F2212/1056

  Simplification · CPC title

• G06F16/22

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F16/901

  Indexing; Data structures therefor; Storage structures (for retrieval from the web G06F16/951) · CPC title

• G06F16/24568

  Data stream processing; Continuous queries · CPC title

• G06F12/04

  Addressing variable-length words or parts of words · CPC title