Determining a document similarity metric

• US 7,565,348 B1
• Filed: 03/24/2006
• Issued: 07/21/2009
• Est. Priority Date: 03/24/2005
• Status: Active Grant

• Current Assignee: Palamida, Inc. (Flexera Software LLC)
• Original Assignee: Palamida, Inc. (Flexera Software LLC)
• Inventors: Zhang, Jing, Waldin, Ray
• Primary Examiner(s): Le; Debbie M
• Application Number:
  US11/277,486
• Time in Patent Office: 1,215 Days
• Field of Search: 707 1- 7
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

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.

Claims

1. A method for determining similarity of a source document to a pattern file by a computer, comprising:

creating a plurality of tables storing data associated with a plurality of patterns included in a pattern file;

determining which of the plurality of patterns in the pattern file exists in the source document, by analyzing the source document with reference to the plurality of tables;

determining a coverage metric, a count metric, a clustering metric and a uniqueness metric responsive to determining which of the patterns exist in the source document, the coverage metric indicative of the frequency of patterns in the pattern file appearing in the source document, the count metric indicative of a count of the patterns in the pattern file existing in the source document, the clustering metric indicative of the degree of proximity between the patterns of the pattern file in the source document, the uniqueness metric indicative of the frequency of a pattern in the pattern file appearing in other pattern files; and

determining a document similarity metric for each pattern file based on the coverage metric, the count metric, the clustering metric and the uniqueness metric, the document similarity metric indicative of the degree of similarity between the source document and the pattern file.

2. The method of claim 1, wherein creating the plurality of tables comprises:

for each of the plurality of patterns in the pattern file;

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; and

storing in the suffix table a plurality of shift values in entries to which none of the plurality of patterns hashes.

3. The method of claim 2, wherein analyzing the source document comprises generating the match information by performing paged interpolation searches on the prefix table.

4. The method of claim 1, further comprising:

displaying in a first area of a screen an identity of the pattern file and at least one of the coverage metric, the clustering metric and a uniqueness metric associated with the pattern file and the source document; and

displaying in a second area of the screen portions of the source document matching the patterns in the pattern file.

5. A system for determining similarity of a source document to a pattern file, the system comprising:

a computer readable storage medium storing a plurality of pattern files, each pattern file including a plurality of patterns;

a preprocessing engine adapted to create a plurality of tables storing data associated with a plurality of patterns included in a pattern file;

a pattern analysis engine, coupled to the preprocessing engine, adapted to determine which of the plurality of patterns in the pattern file exists in the source document, by analyzing the source document with reference to the plurality of tables, the pattern analysis engine further adapted to generate match information identifying a pattern of the pattern file existing in the source document and a position of the pattern in the source document; and

a document similarity engine, coupled to the pattern analysis engine, adapted to determine a coverage metric, a count metric, a clustering metric and a uniqueness metric based on the match information, the coverage metric indicative of the frequency of patterns in the pattern file appearing in the source document, the count metric indicative of a count of the patterns in the pattern file existing in the source document, the clustering metric indicative of the degree of proximity between the patterns of the pattern file in the source document, the uniqueness metric indicative of the frequency of a pattern in the pattern file appearing in other pattern files, the document similarity engine further adapted to determine a document similarity metric for each pattern file based on the coverage metric, the count metric, the clustering metric and the uniqueness metric, the document similarity metric indicative of the degree of similarity between the source document and the pattern file.

6. The system of claim 5, wherein the preprocessing engine is adapted to:

for each of the plurality of patterns in the pattern file,

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.

7. The system of claim 6, wherein the preprocessing engine is further adapted to generate the match information by performing paged interpolation searches on the prefix table.

8. The system of claim 5, wherein the document similarity engine is further adapted to:

display in a first area of a screen an identity of the pattern file and at least one of the coverage metric, the clustering metric and the uniqueness metric associated with the pattern file and the source document; and

display in a second area of the screen portions of the source document matching the patterns in the pattern file.

9. A computer readable storage medium storing instructions adapted to identify patterns in a source document, the instructions when executed by a processor causing the processor to:

create a plurality of tables storing data associated with a plurality of patterns included in a pattern file;

determine which of the plurality of patterns in the pattern file exists in the source document, by analyzing the source document with reference to the plurality of tables;

generate match information identifying a pattern of the pattern table existing in the source document and a position of the pattern existing in the source document;

determine a coverage metric, a count metric, a clustering metric and a uniqueness metric based on the match information, the coverage metric indicative of the frequency of patterns in the pattern file appearing in the source document, the count metric indicative of a count of the patterns in the pattern file existing in the source document, the clustering metric indicative of the degree of proximity between the patterns of the pattern file in the source document, the uniqueness metric indicative of the frequency of a pattern in the pattern file appearing in other pattern files; and

determine a document similarity metric for each pattern file based on the coverage metric, the count metric, the clustering metric and the uniqueness metric.

10. The computer readable storage medium of claim 9, further comprising instructions to:

for each of the plurality of patterns in the pattern file;

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.

11. The computer readable storage medium of claim 10, instructions to analyze the source document comprises instructions to generate the match information by performing paged interpolation searches on the prefix table.

12. The computer readable storage medium of claim 9, further comprising instructions to:

display in a first area of a screen an identity of the pattern file and at least one of the coverage metric, the clustering metric and a uniqueness metric associated with the pattern file and the source document; and

display in a second area of the screen portions of the source document matching the patterns in the pattern file.