Regular expression compressing method for DFA (Discriminant Function Analysis)

A compression method and expression technology, which is applied in the field of DFA regular expression compression, can solve the problems of DFA space explosion and difficulty in supporting regular expressions, and achieve the effect of reducing storage space

Inactive Publication Date: 2011-05-18
DAWNING INFORMATION IND BEIJING
View PDF3 Cites 6 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

Various state machines are mainly used to achieve regular expression matching, but DFA has the problem of space explosion, and it is difficult to support more regular expressions

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Regular expression compressing method for DFA (Discriminant Function Analysis)
  • Regular expression compressing method for DFA (Discriminant Function Analysis)
  • Regular expression compressing method for DFA (Discriminant Function Analysis)

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0013] First give an example of regular expression and DFA.

[0014] Suppose the regular expression is: \$[0-9]+(\.[0-9]{2}){0, 1}

[0015] The function of this expression is to identify the number of dollars (beginning with $, followed by multiple). Figure (a) is a state transition diagram, and Figure (b) is a state transition table. The transfer table has a total of 256 columns, each corresponding to 256 values ​​of a byte; the ~... in the last column in the figure represents all letters except 0~9, ., $. In state D, if you input ".", you will enter state C; if you input a value between 0 and 9, you will remain in state D.

[0016] The present invention adopts hardware to perform regular expression matching, specifically, FPGA (Field Programmable Gate Array, Field Programmable Gate Array) programmable logic device can be used but not limited to.

[0017] Most states of DFA have only a few different values ​​(for example, although each row has 256 values ​​in the example, ...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

PUM

No PUM Login to view more

Abstract

The invention provides a regular expression compressing method for DFA (Discriminant Function Analysis), comprising the following steps of: compressing each state of each row or column of regular expressions in a way similar to run length coding; and if states with unique state skip condition exist in each row or column of coded regular expressions, forming a hash table by using the states. The invention has the advantages of greatly reducing the storage space required by DFA storage and storing more regular expressions within a limited space.

Description

technical field [0001] The invention relates to the field of regular expressions, in particular to a DFA regular expression compression method. Background technique [0002] Regular expressions are widely used in the field of network information processing, such as protocol identification, intrusion detection, etc. Various state machines are mainly used to achieve regular expression matching, but DFA has the problem of space explosion, and it is difficult to support more regular expressions. The invention adopts a space compression method, which greatly reduces the storage space required for storing the DFA state. [0003] There are several regular expression matching schemes using DFA at present. One is to appropriately rewrite regular expressions to improve storage efficiency; the second is to mine the characteristics of state transitions. For example, the next state of most states has only a few different values. Delayed transfer and other methods can be used to reduce ...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

Application Information

Patent Timeline
no application Login to view more
Patent Type & Authority Applications(China)
IPC IPC(8): H03M7/30
Inventor 刘兴奎李锋伟纪奎赵喜全
Owner DAWNING INFORMATION IND BEIJING
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap