Method and device for constructing AC (aho-corasick) state machine
A construction method and state machine technology, applied in the field of pattern matching, can solve problems such as reducing the scope of use of AC state machines
- Summary
- Abstract
- Description
- Claims
- Application Information
AI Technical Summary
Problems solved by technology
Method used
Image
Examples
Embodiment 1
[0045] This embodiment provides a method for constructing an AC state machine. The method is applicable to the construction device of the AC state machine. The construction device of the AC state machine regards the wildcard as a specific character to construct a standard goto function table and an output function table, and disassembles the state node containing the transferred state based on the wildcard. Divide and merge to eliminate uncertain goto functions, modify the output function table at the same time, and finally construct an AC state machine that can handle wildcards.
[0046] Such as Figure 2A As shown, it is a schematic flowchart of the construction method of the AC state machine in this embodiment. The construction method of the AC state machine includes:
[0047] Step 201, setting each wildcard character in each search pattern as a specific character.
[0048] The specific character in this step may be represented by a non-ASCII code value, such as the valu...
Embodiment 2
[0058] This embodiment provides a further supplementary description of the method for constructing the AC state machine in the foregoing embodiments.
[0059] After step 203 and before step 204, the method for constructing the AC state machine in this embodiment further includes: identifying uncertain goto functions in the copied goto function table and the original goto function table of sibling state nodes. This identification duplicates the goto function table and the original goto function table of the brother status node is uncertain. The goto functions include:
[0060] Identify each transfer function expression and transfer function output value of the original goto function table of the duplicated goto function table and sibling state nodes;
[0061] The transfer functions with the same transfer function expression and different transfer function output values are regarded as indeterminate goto functions.
[0062] The construction method of the AC state machine in t...
Embodiment 3
[0064] This embodiment further defines the method for constructing the AC state machine in the foregoing embodiments.
[0065] In this embodiment, after copying the goto function table of the state node corresponding to the output value of the new goto function to the goto function table of the state node corresponding to the output value of the old goto function, after removing the new goto function, and returning to execute the above The identification step, until the unidentified goto function is not identified, also includes:
[0066] Judging whether the state node corresponding to the output value of the new goto function is the final state node, when the judgment result is yes, copy the output function table of the state node corresponding to the output value of the new goto function to the state corresponding to the output value of the old goto function In the output function table of the node, the final state node is the state node corresponding to the last input chara...
PUM
Abstract
Description
Claims
Application Information
- R&D Engineer
- R&D Manager
- IP Professional
- Industry Leading Data Capabilities
- Powerful AI technology
- Patent DNA Extraction
Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.
© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com