Matching Engine With Signature Generation

• US 20090193018A1
• Filed: 02/17/2009
• Published: 07/30/2009
• Est. Priority Date: 05/09/2005
• Status: Active Grant

• Current Assignee: Aiguo Dong, Dehua Tan, Fei Huang, Liwei Ren, Shu Huang
• Original Assignee: Aiguo Dong, Dehua Tan, Fei Huang, Liwei Ren, Shu Huang
• Inventors: REN, Liwei, HUANG, Shu, TAN, Dehua, DONG, Aiguo, HUANG, Fei
• Granted Patent: US 8,171,002 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A system and a method generates at least one signature associated with document. In one embodiment, a document comprised of text is received and parsed to generate a token set. The token set includes a plurality of tokens. Each token corresponds to the text in the document that is separated by a predefined character characteristic. A score is calculated for each token in the token set based on a frequency and distribution of the text in the document. Each token is then ranked based on the calculated score. A subset of the ranked tokes is selected and a signature is generated for each occurrence of the selected tokens. The selected list of signatures is then output.

Claims

1-6. -6. (canceled)

7. A method for generating a plurality of signatures associated with a document, the method comprising:

receiving a document comprising a plurality of characters;

normalizing the document to remove non-informative characters from the plurality of characters;

calculating a score for each informative character of the plurality of characters based on an occurrence frequency and distribution in the document;

ranking each informative character of the plurality of characters based on the calculated score;

selecting, from the ranked informative characters, character occurrences; and

generating a signature for each selected character occurrence.

8. The method of claim 7, wherein selecting character occurrences further comprises:

hashing bytes around each character occurrence to generate hash values; and

sorting the hash values into a predefined ranking.

9. The method of claim 7, wherein generating the signature further comprises generating the signature using characters surrounding the selected character occurrences.

10. The method of claim 7, wherein the character is a UTF-8 character.

11. The method of claim 10, wherein the non-informative characters comprise one from a group consisting of an extra space, a control character, or combination thereof.

12. The method of claim 7, further comprising outputting a list of the generated signatures.

25. The method of claim 7, wherein said score for each informative character is proportional to a first quantity divided by a second quantity, further wherein the first quantity comprises a position of a last occurrence of the informative character in the document minus a position of a first occurrence of the informative character in the document, and further wherein the second quantity comprises a square root of a sum of squares of differences in positions between adjacent occurrences of the informative character in the document.

13-18. -18. (canceled)

19. A computer readable storage medium storing instructions executable by a processor, the instructions when executed causing a processor to:

receive a document comprising a plurality of characters;

normalize the document to remove non-informative characters from the plurality of characters;

calculate a score for each informative character of the plurality of characters based on an occurrence frequency and distribution in the document;

rank each informative character of the plurality of characters based on the calculated score;

select, from the ranked informative characters, character occurrences; and

generate a signature for each selected character occurrence.

20. The computer readable storage medium of claim 19, wherein the instructions to cause the processor to select character occurrences further comprises instructions that when executed by the processor cause the processor to:

hash bytes around each character occurrence to generate hash values; and

sort the hash values into a predefined ranking.

21. The computer readable storage medium of claim 19, wherein the instructions to cause the processor to generate the signature further comprises instructions to cause the processor to generate the signature using characters surrounding the selected character occurrences.

22. The computer readable storage medium of claim 19, wherein the character is a UTF-8 character.

23. The computer readable storage medium of claim 22, wherein the non-informative characters comprise one from a group consisting of an extra space, a control character, a return or combination thereof.

24. The computer readable storage medium of claim 19, wherein the instructions when executed by the processor further cause the processor to output a list of the generated signatures.