Generating a fingerprint for a document

• US 20060101069A1
• Filed: 11/01/2005
• Published: 05/11/2006
• Est. Priority Date: 11/05/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Beynon, Margaret A., Delo, Benjamin P., Offermann, Philipp, Friedman, Julian, Flegg, Andrew J., Bell, James
• Granted Patent: US 7,555,489 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

A method for generating a set of one or more elements of a fingerprint for a document, the document comprising a semantic construct having one or more ordered words, the method comprising the steps of: defining a range of sizes for a fingerprint element; dividing the ordered words of the semantic construct into a set of one or more mutually exclusive fingerprint elements, wherein each of the one or more mutually exclusive fingerprint elements includes a number of adjacent words, the number being within the range of sizes for a fingerprint element; and responsive to a determination that the set of mutually exclusive fingerprint elements excludes a word from the semantic construct, discarding the excluded word.

Claims

1. A method for generating a set of one or more elements of a fingerprint for a document, the document comprising a semantic construct having one or more ordered words, the method comprising the steps of:

defining a range of sizes for a fingerprint element;

dividing the ordered words of the semantic construct into a set of one or more mutually exclusive fingerprint elements, wherein each of the one or more mutually exclusive fingerprint elements includes a number of adjacent words, the number being within the range of sizes for a fingerprint element; and

responsive to a determination that the set of mutually exclusive fingerprint elements excludes a word from the semantic construct, discarding the excluded word.

2. The method of claim 1 further comprising the step of:

separating the semantic construct into a plurality of nested semantic constructs, each of the nested semantic constructs having one or more ordered words; and

dividing the ordered words of each of the nested semantic constructs into a set of one or more mutually exclusive fingerprint elements, wherein each of the one or more mutually exclusive fingerprint elements includes a number of adjacent words, the number being within the range of sizes for a fingerprint element.

3. The method of claim 2 further comprising the step of:

defining an order of precedence of semantic constructs within the document,

wherein said dividing the ordered words of the nested semantic constructs step further comprises dividing the ordered words into nested semantic constructs in accordance with the order of precedence of semantic constructs.

4. The method of claim 1 wherein the range of sizes for a fingerprint element includes a minimum number of words and a maximum number of words.

5. The method as claimed in claim 1 further comprising a method for comparing a first document with a second document, the method for comparing comprising the steps of:

generating a first set of fingerprint elements from the first document;

generating a second set of fingerprint elements from the second document; and

calculating a similarity index as the size of the intersect of the first set of fingerprint elements and the second set of fingerprint elements divided by the size of the first set of fingerprint elements.

6. A system for generating a set of one or more elements of a fingerprint for a document, the document comprising a semantic construct having one or more ordered words, the system comprising:

means for defining a range of sizes for a fingerprint element;

means for dividing the ordered words of the semantic construct into a set of one or more mutually exclusive fingerprint elements, wherein each of the one or more mutually exclusive fingerprint elements includes a number of adjacent words, the number being within the range of sizes for a fingerprint element; and

means for, responsive to a determination that the set of mutually exclusive fingerprint elements excludes a word from the semantic construct, discarding the excluded word.

7. The system of claim 6 further comprising:

means for separating the semantic construct into a plurality of nested semantic constructs, each of the nested semantic constructs having one or more ordered words; and

means for dividing the ordered words of each of the nested semantic constructs into a set of one or more mutually exclusive fingerprint elements, wherein each of the one or more mutually exclusive fingerprint elements includes a number of adjacent words, the number being within the range of sizes for a fingerprint element.

8. The system of claim 7 further comprising:

means for defining an order of precedence of semantic constructs within the document,

wherein said dividing the ordered words of the nested semantic constructs step further comprises means for dividing the ordered words into nested semantic constructs in accordance with the order of precedence of semantic constructs.

9. The system of claim 6 wherein the range of sizes for a fingerprint element includes a minimum number of words and a maximum number of words.

10. The system of claim 6 further comprising a system for comparing a first document with a second document, the system for comparing comprising:

means for generating a first set of fingerprint elements from the first document, and means for generating a second set of fingerprint elements from the second document; and

means for calculating a similarity index as the size of the intersect of the first set of fingerprint elements and the second set of fingerprint elements divided by the size of the first set of fingerprint elements.

11. A computer program product comprising computer program code stored on a computer readable storage medium which, when executed on a data processing system, instructs the data processing system to carry out a method for generating a set of one or more elements of a fingerprint for a document, the document comprising a semantic construct having one or more ordered words, the method comprising:

defining a range of sizes for a fingerprint element;

dividing the ordered words of the semantic construct into a set of one or more mutually exclusive fingerprint elements, wherein each of the one or more mutually exclusive fingerprint elements includes a number of adjacent words, the number being within the range of sizes for a fingerprint element; and

responsive to a determination that the set of mutually exclusive fingerprint elements excludes a word from the semantic construct, discarding the excluded word.

12. The computer program product of claim 11 further comprising a computer program product comprising computer program code stored on a computer readable storage medium which, when executed on a data processing system, instructs the data processing system to carry out the method for comparing a first document with a second document, the method for comparing comprising the steps of:

generating a first set of fingerprint elements from the first document;

generating a second set of fingerprint elements from the second document; and

calculating a similarity index as the size of the intersect of the first set of fingerprint elements and the second set of fingerprint elements divided by the size of the first set of fingerprint elements.

13. (canceled)