Character string searching method and device based on non-determined finite automaton

Abstract

The invention discloses a character string searching method based on a non-determined finite automaton. The character string searching method based on the non-determined finite automaton includes: building the non-determined finite automaton and setting a state variable for the non-determined finite automaton; loading a matching expression in the non-determined finite automaton and transforming the matching expression in the non-determined finite automaton into a directed graph according to the operator transformational rule of the directed graph; conducting matching on the characters in the character string of the non-determined finite automaton according to the state position of the state variable; updating the state variable according to the final position directed by the position in the directed graph if the characters are matched successfully, conducting the matching on the next character from the position in the updated state variable and completing the matching till the character string which conforms to the matching expression is obtained or the character matching fails, and placing the state variable as the starting position when the matching is completed. The character string searching method based on the non-determined finite automation can realize more accuracy of the character string searching. The invention further provides a character string searching device based on the non-determined finite automaton.

Description

technical field [0001] The invention relates to the field of data search, in particular to a character string search technology based on non-deterministic finite automata. Background technique [0002] In the process of network element interaction, the program needs to determine its own behavior according to some specific identifiers (that is, specific character strings) in network element messages. Due to the randomness of network transmission, these strings may be received in multiple ways, which requires the ability to shield the diversity of receiving methods at the network transmission level, obtain these specific strings, and send them to the upper-layer business logic. [0003] The traditional cache-based string search uses a fixed-length string array as the receiving cache, searches for the existence of a specific string in the receiving cache, if it exists, the match is successful, and if it does not exist, a new The accepted message is added to the acceptance cach...

AI Technical Summary

Problems solved by technology

The obvious disadvantages of doing this are: 1. Some characters in the specific character string are truncated in the excess part, but this time the matching is unsuccessful, and the matching is continued from the truncated message header, and the truncated message header is not does not contain the complete string, thus causing no matching string to be searched

2. The specific string is located at the end of the message, and it needs to search and match multiple times to match the target string, which is very inefficient

[0005] However, since the message arrives in segments in the network environment, it is impossible to provide it at one time. If a part of the target string arrives, the NFA fails to match it. After a period of time, another part of the target string arrives, and the NFA will restart Match the message, causing the string matching to fail, and the target string cannot be obtained

Images