Massive multi-pattern searching
View Patent ↗To perform multi-pattern searching, a preprocessing engine populates a SUFFIX table, a PREFIX table and a PATTERN table. The SUFFIX table combines data conventionally stored in SHIFT and HASH tables. Pointers in the SUFFIX table refer to corresponding segments in the PREFIX table. Each PREFIX table segment is sorted by a prefix hash. A PATTERN table includes a hash of each full pattern sorted and grouped into segments, with each segment corresponding to a suffix hash and prefix hash combination. Pointers in the PREFIX table refer to corresponding segments in the PATTERN table. The PREFIX and PATTERN can be kept in secondary storage, allowing potentially billions of patterns to be used. After preprocessing, patterns are evaluated against a source file. A document metric is determine to qualitatively describe the similarity between the source file and each pattern file.
1. A method for identifying patterns in a source document, comprising:
for each of a plurality of patterns:
storing in a suffix table a pointer to an entry in a prefix table, the suffix table indexed by a suffix hash of each pattern;
storing in the prefix table a prefix hash of the pattern and a pointer to the pattern, the prefix table indexed and grouped by the suffix hash of the pattern;
storing in a pattern table the pattern and a hash of the pattern;
storing in the suffix table a plurality of shift values in entries to which none of the plurality of patterns hashes; and
a processor determining which of the plurality of patterns appears in the source document, by analyzing the source document with reference to the suffix table, the prefix table and the pattern table.
2. A system for identifying patterns in a source document, the system comprising:
a computer readable storage medium storing a plurality of patterns;
a preprocessing engine configured to:
for each of the plurality of patterns,
store in a suffix table a pointer to an entry in a prefix table, the suffix table indexed by a suffix hash of each pattern;
store in the prefix table a prefix hash of the pattern and a pointer to the pattern, the prefix table indexed and grouped by the suffix hash of the pattern;
store in a pattern table the pattern and a hash of the pattern; and
store in the suffix table a plurality of shift values in entries to which none of the plurality of patterns hashes;
a pattern analysis engine, coupled to the preprocessing engine, configured to determine which of the plurality of patterns appears in the source document, by analyzing the source document with reference to the suffix table, the prefix table and the pattern table.
3. The method of claim 1 , wherein analyzing the source document comprises:
determining a suffix hash at a first position in the source document;
determining presence of a shift value in the suffix table corresponding to the suffix hash; and
proceeding to a second position in the source document separated from the first position by the shift value responsive to the shift value corresponding to the suffix hash.
4. The method of claim 3 , wherein analyzing the source document further comprises:
determining whether a prefix hash of a portion of the source document ending at the first position is present in the prefix table, responsive to the shift value corresponding to the suffix hash not being present in the suffix table;
determining a candidate pattern from the prefix table based on the suffix hash and the prefix hash responsive to the prefix hash of the portion of the source document being present in the prefix table; and
comparing the candidate pattern with the portion of the source document.
5. The method of claim 1 , wherein the pointer in the suffix table comprises a linear residual pointer.
6. The method of claim 1 , further comprising sorting entries of the prefix table by values of prefix hashes.
7. The method of claim 6 , further comprising eliminating duplicative values of prefix hashes in the prefix table.
8. The method of claim 1 , wherein analyzing the source document comprises performing paged interpolation searches on the prefix table.
9. The method of claim 1 , further comprising sorting and grouping the patterns in the pattern table based on suffix hashes and prefix hashes of the patterns.
10. The method of claim 1 , further comprising storing metadata of the patterns in the pattern table.
11. The system of claim 2 , wherein the pattern analysis engine is further configured to:
determine a suffix hash at a first position in the source document;
determine presence of a shift value in the suffix table corresponding to the suffix hash; and
proceed to a second position in the source document separated from the first position by the shift value responsive to the shift value corresponding to the suffix hash being present in the suffix table.
12. The system of claim 11 , wherein the pattern analysis engine is further configured to:
determine whether a prefix hash of a portion of the source document ending at the first position is present in the prefix table, responsive to the shift value corresponding to the suffix hash not being present in the suffix table;
determine a candidate pattern from the prefix table based on the suffix hash and the prefix hash responsive to the prefix hash of the portion of the source document being present in the prefix table; and
compare a candidate pattern with the portion of the source document.
13. The system of claim 2 , wherein the pointer in the suffix table comprises a linear residual pointer.
14. The system of claim 2 , wherein the preprocessing engine is further configured to sort entries of the prefix table by values of prefix hashes.
15. The system of claim 14 , wherein the preprocessing engine is further configured to eliminate duplicative values of prefix hashes in the prefix table.
16. The system of claim 2 , wherein the pattern analysis engine is further configured to perform paged interpolation searches on the prefix table.
17. The system of claim 2 , wherein the preprocessing engine is further configured to sort and group the patterns in the pattern table based on suffix hashes and prefix hashes of the patterns.
18. The system of claim 2 , wherein the preprocessing engine is further configured to store metadata of the patterns in the pattern table.
19. A computer readable storage medium storing instruction configured to identify patterns in a source document, the instructions when executed by a processor causing the processor to:
for each of a plurality of patterns:
store in a suffix table a pointer to an entry in a prefix table, the suffix table indexed by a suffix hash of each pattern;
store in the prefix table a prefix hash of the pattern and a pointer to the pattern, the prefix table indexed and grouped by the suffix hash of the pattern;
store in a pattern table the pattern and a hash of the pattern;
store in the suffix table a plurality of shift values in entries to which none of the plurality of patterns hashes; and
determine which of the plurality of patterns appears in the source document, by analyzing the source document with reference to the suffix table, the prefix table and the pattern table.
20. The computer readable storage medium of claim 19 , wherein the instructions to determine which of the plurality of patterns appears in the source document comprises instructions to:
determine a suffix hash at a first position in the source document;
determine presence of a shift value in the suffix table corresponding to the suffix hash; and
proceed to a second position in the source document separated from the first position by the shift value responsive to the shift value corresponding to the suffix hash, responsive to the shift value.