Fast identification of complex strings in a data stream
View Patent ↗A method for detecting and locating occurrence in a data stream of any complex string belonging to a predefined complex dictionary is disclosed. A complex string may comprise an arbitrary number of interleaving coherent strings and ambiguous strings. The method comprises a first process for transforming the complex dictionary into a simple structure to enable continuously conducting computationally efficient search, and a second process for examining received data in real time using the simple structure. The method may be realized by an article of manufacture comprising at least one processor-readable medium and instructions carried on the at least one medium. The instructions causes a processor to match examined data to an object complex string belonging to the complex dictionary, where the matching process is based on equality to constituent coherent strings, and congruence to ambiguous strings, of the object complex string.
1. A method of screening a data stream to detect presence of at least one complex string belonging to a predefined complex dictionary, the method being encoded into instructions stored in a processor-readable storage medium coupled to a processor, the method comprising:
transforming said complex dictionary into:
a segmented dictionary comprising a string suffix and string segments of each complex string in said complex dictionary, each string segment comprising a segment prefix and a simple string;
an array of segment descriptors, each segment descriptor defining a content of a corresponding string segment in said segmented dictionary; and
an array of bitmasks, each bitmask indicating a location of a string segment in said segmented dictionary within a respective complex string in said complex dictionary;
performing a simple search in said data stream to produce detected simple strings defined in said segmented dictionary;
selecting candidate string segments, from said segmented dictionary, containing said detected simple strings; and
identifying candidate complex strings for the at least one complex string in said complex dictionary containing said candidate string segments using said array of segment descriptors and said array of bitmasks;
wherein the step of selecting comprises a further step of ascertaining congruence of a portion of said data stream, said portion preceding each said detected simple string, and a segment prefix of a corresponding string segment in said segmented dictionary.
2. The method of claim 1 further comprising:
associating a state variable with each complex string in said complex dictionary;
updating said state variable according to gauged spans between successive positions in said data stream, at which positions simple strings belonging to said each complex string terminate;
determining, at each said position, a subset of said candidate string segments belonging to said each complex string; and
correlating, at each said position, said state variable with locations, within said each complex string, of candidate string segments of said subset of said candidate string segments.
3. The method of claim 2 wherein the step of correlating further comprises:
formulating a composite current mask as a logical OR function of bitmasks of candidate string segments of said subset; and
performing a logical AND operation of said composite current mask and said state variable to produce an updated state variable.
4. The method of claim 1 wherein said simple search is based on a generic trie-based search.
5. The method of claim 1 wherein said simple search is based on an Aho-Corasick automaton.
6. The method of claim 1 , further comprising establishing congruence of said string suffix with a corresponding portion of said data stream by ascertaining that:
said string suffix and said corresponding portion of said data stream have a same number of characters; and
likewise positioned characters in said string suffix and said corresponding portion of said data stream belong to a same character class from among a predefined set of character classes.
7. The method of claim 1 , wherein the step of ascertaining congruence comprises steps of ascertaining that:
said portion of said data stream and said segment prefix have a same number of characters; and
likewise positioned characters in said portion of said data stream and said segment prefix belong to a same character class from among a predefined set of character classes.
8. An article of manufacture comprising:
at least one processor-readable medium; and
processor-readable instructions stored on the at least one processor-readable medium to be executed by a processor;
wherein the instructions cause the processor to:
transform a complex dictionary containing complex strings into:
a segmented dictionary comprising a string suffix and string segments of each complex string in said complex dictionary, each string segment comprising a segment prefix and a simple string;
an array of segment descriptors, each segment descriptor defining a content of a corresponding string segment in said segmented dictionary; and
an array of bitmasks, each bitmask indicating a location of a string segment in said segmented dictionary within a respective complex string in said complex dictionary;
perform a simple search in said data stream to produce detected simple strings defined in said segmented dictionary;
select candidate string segments from among specific string segments containing said detected simple strings; and
identify candidate complex strings in said complex dictionary containing said candidate string segments using said array of segment descriptors and said array of bitmasks; and
ascertain congruence of said segment prefix of said each string segment with a corresponding portion of said data stream.
9. The article of manufacture of claim 8 , further comprising instructions stored on the at least one processor-readable medium causing said processor to operate to ascertain congruence of said string suffix with a corresponding portion of said data stream.
10. The article of manufacture of claim 8 , further comprising additional processor-readable instructions stored on the at least one processor-readable medium which cause said processor to:
associate a state variable with each complex string in said complex dictionary;
update said state variable according to gauged spans between successive positions in said data stream, at which positions simple strings belonging to said each complex string terminate;
determine, at each said position, a subset of said candidate string segments belonging to said each complex string; and
correlate, at each said position, said state variable with locations, within said each complex string, of candidate string segments of said subset of said candidate string segments.
11. The article of manufacture of claim 10 , wherein said instructions causing said processor to correlate said state variable with locations of said candidate string segments causes said processor to:
formulate a composite current mask as a logical OR function of bitmasks of candidate string segments of said subset; and
perform a logical AND operation of said composite current mask and said state variable to produce an updated state variable
12. The article of manufacture of claim 8 , wherein said simple search is based on a generic trie-based search.
13. The article of manufacture of claim 8 , wherein said simple search is based on an Aho-Corasick automaton.
14. A system for screening a data stream to detect presence of at least one complex string belonging to a predefined complex dictionary, comprising:
a processor;
at least one processor-readable medium having stored thereon instructions to cause the processor to:
transform said complex dictionary into:
a segmented dictionary comprising a string suffix and string segments of each complex string in said complex dictionary, each string segment comprising a segment prefix and a simple string;
an array of segment descriptors, each segment descriptor defining a content of a corresponding string segment in said segmented dictionary; and
an array of bitmasks, each bitmask indicating a location of a string segment in said segmented dictionary within a respective complex string in said complex dictionary;
perform a simple search in said data stream to produce detected simple strings, defined in said segmented dictionary;
select candidate string segments from among specific string segments containing said detected simple strings; and
identify candidate complex strings in said complex dictionary containing said candidate string segments using said array of segment descriptors, and said array of bitmasks; and
ascertain congruence of said segment prefix of said each string segment with a corresponding portion of said data stream.
15. The system of claim 14 , further comprising instructions stored on said at least one processor-readable medium causing said processor to operate to ascertain congruence of said string suffix with a corresponding portion of said data stream.
16. The system of claim 14 , further comprising additional processor-readable instructions stored on the at least one processor-readable medium which cause said processor to:
associate a state variable with each complex string in said complex dictionary;
update said state variable according to gauged spans between successive positions in said data stream, at which positions simple strings belonging to said each complex string terminate;
determine, at each said position, a subset of said candidate string segments belonging to said each complex string; and
correlate, at each said position, said state variable with locations, within said each complex string, of candidate string segments of said subset of said candidate string segments.
17. The system of claim 16 , wherein said instructions causing said processor to correlate said state variable with locations of said candidate string segments causes said processor to:
formulate a composite current mask as a logical OR function of bitmasks of candidate string segments of said subset; and
perform a logical AND operation of said composite current mask and said state variable to produce an updated state variable.
18. The system of claim 14 , wherein said simple search is based on a generic trie-based search.
19. The system of claim 14 , wherein said simple search is based on an Aho-Corasick automaton.