Multipattern regular expression search systems and methods therefor
View Patent ↗A tool, system, and method for searching input data includes a pattern input module, configured to receive regular expression patterns of symbols. An interpreter module may be configured to access individual ones of the symbols of the input data and upon accessing each symbol and compare a thread against the symbol. For each pattern, the thread corresponding to the pattern is compared against the symbol prior to the at least one thread being compared against a subsequent symbol of the input data. An output module may be configured to output an indication of ones of the patterns determined to be contained within the input data based on the comparison of the corresponding at least one thread to the symbols of the input data.
1. A system configured to search input data including symbols, comprising:
an electronic data storage configured to store input data having regular expression patterns of symbols; and
a processor, coupled to the electronic data storage, configured to:
receive a first pattern of the regular expression patterns of the input data, the first pattern including at least one code point; and
generate a second pattern by applying the first pattern to a transformation chain, the second pattern including a corresponding sequence of bytes, the transformation chain comprising multiple translations including at least one code point to byte translation;
access individual ones of the symbols of the input data as converted into the second pattern and, upon accessing each symbol, compare at least one thread against the symbol, the at least one thread being based on at least one of the regular expression patterns and each of the regular expression patterns corresponding to at least one of the threads, wherein, for each second pattern, the at least one thread corresponding to the second pattern is compared against the symbol prior to the at least one thread being compared against a subsequent symbol of the second pattern; and
cause a user interface to output an indication of ones of the patterns determined to be contained within the input data based on the comparison of the corresponding at least one thread to the symbols of the second pattern.
2. The system of claim 1 , wherein, for each regular expression pattern, each symbol of the second pattern is compared against the plurality of threads once before any one symbol is compared against the plurality of threads more than once.
3. The system of claim 2 , wherein each symbol of the second pattern is compared against the plurality of threads only once.
4. The system of claim 1 , wherein the thread corresponds to a sequence of commands and wherein the at least one thread is compared against the symbol by implementing individual ones of the plurality of commands.
5. The system of claim 4 , wherein each of the regular expression patterns corresponds to a common automaton corresponding to a plurality of commands, the sequence of commands being a subset of the plurality of commands, and wherein each of the threads is generated based on the plurality of commands.
6. The system of claim 5 , wherein the plurality of commands corresponding to the automaton produces pattern matches for the regular expression patterns that correspond to the automaton.
7. The system of claim 6 , further comprising a pattern analyzer configured to generate the automaton corresponding to the patterns based on common symbols between the patterns.
8. The system of claim 1 , wherein the processor is configured with a plurality of encodings including the code point and the sequence of bytes, each one of the plurality of encodings being a code point or a sequence of bytes, and wherein the processor is configured to generate a plurality of second patterns corresponding to each encoding of the plurality of encodings not corresponding to the encoding of the first pattern as input.
9. The system of claim 1 , wherein at least one of the regular expression patterns comprises a string of at least one symbol and at least one operator, wherein the operator specifies variable combinations of symbols within the at least one of the regular expression patterns.
10. The system of claim 1 , wherein the transformation chain further comprises at least one code point to code point translation or at least one byte to byte translation.
11. A computer readable medium, comprising instructions which, when implemented by a processor, cause the processor to perform operations comprising:
receive a first pattern of at least one code point, the first pattern being a regular expression pattern of symbols;
generate a second pattern by applying the first pattern to a transformation chain, the second pattern including a corresponding sequence of bytes, the transformation chain comprising multiple translations including at least one code point to byte translation;
access the symbols of the input data as converted into the second pattern and, upon accessing each symbol, comparing at least one thread against the symbol based on the patterns as received by the pattern input module and as generated by the coding module, the at least one thread being based on at least one of the regular expression patterns and each of the regular expression patterns corresponding to at least one of the threads, wherein the at least one thread is compared against the symbol prior to the at least one thread being compared against a subsequent symbol of the second pattern; and
output an indication of ones of the regular expression patterns determined to be contained within the input data based on the comparison of the corresponding at least one thread to the symbols of the second pattern.
12. The method of claim 11 , wherein each symbol of the second pattern is compared against the plurality of threads once before any one symbol is compared against the plurality of threads more than once.
13. The method of claim 12 , wherein each symbol of the second pattern is compared against the plurality of threads only once.
14. The method of claim 11 , wherein the thread comprises a sequence of commands and wherein the at least one thread is compared against the symbol by implementing individual ones of the sequence of commands.
15. The method of claim 14 , wherein each of the regular expression patterns corresponds to a common automaton comprising a plurality of commands, the sequence of commands being a subset of the plurality of commands, and wherein each of the threads is generated based on the automaton.
16. The method of claim 15 , wherein the plurality of commands of the automaton produces pattern matches for the regular expression patterns that correspond to the automaton.
17. The method of claim 15 , further comprising generating the automaton corresponding to the regular expression patterns based on common symbols between the regular expression patterns.
18. The method of claim 11 , wherein a plurality of encodings includes the code point and the sequence of bytes, each one of the plurality of encodings being a code point or a sequence of bytes, and wherein generating a plurality of second patterns generates the plurality of second patterns corresponding to each encoding of the plurality of encodings not corresponding to the encoding of the first pattern as input.
19. The method of claim 11 , wherein at least one of the patterns comprises a string of at least one symbol and at least one operator, wherein the operator specifies variable combinations of symbols within the at least one of the regular expression patterns.
20. The method of claim 11 , wherein the transformation chain further comprises at least one code point to code point translation or at least one byte to byte translation.