Granted Patent B2

US 7,493,322 · App. 10/605,631 · Granted Feb 17, 2009

Assignee: Xerox Corporation

Abstract

Claims (43)

1. A method for computing a measure of similarity between a first (or input) document and one or more disparate (or search results) documents, comprising:

(a) receiving a first document and identifying the best keywords in the text by recognizing rare and uncommon keywords, including keywords that belong to one or more domain specific or subject matter specific dictionary;

(b) identifying documents similar to the first document using a query by formulating wrappers using the list of the best keywords identified in the first document that also appear in a DS dictionary;

(c) receiving a first list of rated keywords extracted from the first document and a list of rated keywords extracted from each of the one or more disparate documents;

(d) comparing the first list of rated keywords to the list of rated keywords from each of the one or more disparate documents to determine whether the first document forms part of the one or more disparate documents using a first computed percentage indicating what percentage of keyword ratings in the first list also exist in the list of at least one of the one or more disparate documents;

(e) verifying inclusion of the first document in the one or more disparate documents by computing a second percentage for each of the one or more disparate documents indicating what percentage of keyword ratings along with a set of their neighboring keyword ratings in the first list also exist in the list for at least one of the one or more disparate documents when the first computed percentage indicates that the first document is included in at least one of the one or more disparate documents;

(f) using the first computed percentage to specify the measure of similarity when the computed second percentage for at least one of the one or more disparate documents is greater than the first computed percentage;

(g) ranking the one or more disparate documents based on the percentage computed indicating what percentage of keyword ratings along with a set of their neighboring keyword ratings in the first list also exist in the list for at least one of the one or more disparate documents;

(h) if the first computed percentage does not indicate that the first document is included in the second document, computing a third percentage using the Jaccard similarity distance measure, wherein if said Jaccard similarity distance measure is greater than about 90 percent, the second document is identified as a revision of the first document, and if the Jaccard similarity distance measure is less than about 90 percent, said measure is a similarity measure between said first and second document; and

(i) if the third computed percentage indicates that the first document is a revision of the second document, computing a fourth percentage indicating what percentage of keyword ratings along with a set of their neighboring keyword ratings in the second list also exist in the first list.

2. The method according to claim 1 , wherein the second percentage at (c) is computed by giving weight only to those keywords and their set of neighboring keywords in the first list that match in the second list and a threshold percentage of the keywords in their set of neighboring keywords.

3. The method according to claim 2 , wherein the second percentage at (c) is computed by giving full weight to those keywords in the first list of rated keywords that cannot be accurately identified as having a complete set of neighboring keywords in the second set of keywords.

4. The method according to claim 2 , wherein the threshold percentage is reduced when the first list of rated keywords is identified using OCR.

5. The method according to claim 1 , further comprising the fourth computed percentage to specify the measure of similarity except when: (i) the fourth computed percentage is greater than the second computed percentage; (ii) the first list of rated keywords is identified using OCR; (iii) the fourth computed percentage is greater than fifty percent; and (iv) less than twenty percent of the keywords in the first list of keywords are in the second list of keywords.

6. The method according to claim 1 , wherein the first computed percentage indicates that the first document is included in the second document when the percentage defined by ratio of Sum 1 /Sum 2 is greater than approximately ninety percent, where: D 1 is the number of keywords in first list of keywords; D 2 is the number of keywords in the second list of keywords; Sum 1 is the sum of the weights of keywords that appear in D 1 that also appear in D 2 ; Sum 2 is the sum of the weights of keywords in D 1 .

7. The method according to claim 1 , wherein the first list of rated keywords includes one or more keywords translated from a second language different from a first language that is identified as being a primary language of the first document.

8. The method according to claim 1 , wherein the first document is a portion of the second document.

9. A computer-based system for computing a measure of similarity between a first (or input) document and one or more (or search results) documents, comprising:

a processor;

(a) means for receiving a first document and identifying the best keywords in the text by recognizing rare and uncommon keywords, including keywords that belong to one or more domain specific or subject matter specific dictionary;

(b) means for identifying documents similar to the first document using a query by formulating wrappers using the list of the best keywords identified in the first document that also appear in a DS dictionary;

(c) means for receiving a first list of rated keywords extracted from the first document and a list of rated keywords extracted from each of the one or more disparate documents, wherein keywords are rated at least in part by a relevant weight from their associated document language;

(d) means for comparing the first list of rated keywords to the list of keywords from each of the one or more disparate documents to determine whether the first document forms part of the one or more disparate documents using a first computed percentage indicating what percentage of keyword ratings in the first list also exist in the list of at least one of the one or more disparate documents;

(e) means for verifying inclusion of the first document in the one or more disparate documents by computing a second percentage for each of the one or more disparate documents indicating what percentage of keyword ratings along with a set of their neighboring keyword ratings in the first list also exist in the list for at least one of the one or more disparate documents when the first computed percentage indicates that the first document is included in at least one of the one or more disparate documents; and

(f) means for using the first computed percentage to specify the measure of similarity when the computed percentage for at least one of the one or more disparate documents is greater than the first computed percentage;

(g) means for ranking the one or more disparate documents based on the percentage computed indicating what percentage of keyword ratings along with a set of their neighboring keyword ratings in the first list also exist in the list for at least one of the one or more disparate documents;

(h) if the first computed percentage does not indicate that the first document is included in the second document, means computes a third percentage using the Jaccard distance measure, wherein if said Jaccard similarity distance measure is greater than about 90 percent, the second document is identified as a revision of the first document, and if the Jaccard similarity distance measure is less than about 90 percent, said measure is a similarity measure between said first and second document; and

(i) if the third computed percentage indicates that the first document is a revision of the second document, means computes a fourth percentage indicating what percentage of keyword ratings along with a set of their neighboring keyword ratings in the second list also exist in the first list.

10. The system according to claim 9 , wherein the second percentage at (c) is computed by said computing means by giving weight only to those keywords and their set of neighboring keywords in the first list that match in the second list and a threshold percentage of the keywords in their set of neighboring keywords.

11. The system according to claim 10 , wherein the second percentage at (c) is computed by said computing means by giving full weight to those keywords in the first list of rated keywords that cannot be accurately identified as having a complete set of neighboring keywords in the second set of keywords.

12. The system according to claim 10 , wherein the threshold percentage is reduced when the first list of rated keywords is identified using OCR.

13. The system according to claim 9 , further comprising means for using the fourth computed percentage to specify the measure of similarity except when: (i) the fourth computed percentage is greater than the second computed percentage; (ii) the first list of rated keywords is identified using OCR; (iii) the fourth computed percentage is greater than fifty percent; and (iv) less than twenty percent of the keywords in the first list of keywords are in the second list of keywords.

14. The system according to claim 9 , wherein the first computed percentage indicates that the first document is included in the second document when the percentage defined by ratio of Sum 1 /Sum 2 is greater than approximately ninety percent, where: D 1 is the number of keywords in first list of keywords; D 2 is the number of keywords in the second list of keywords; Sum 1 is the sum of the weights of keywords that appear in D 1 that also appear in D 2 ; Sum 2 is the sum of the weights of keywords in D 1 .

15. The system according to claim 9 , wherein the first list of rated keywords includes one or more keywords translated from a second language different from a first language that is identified as being a primary language of the first document.

16. An article of manufacture for computing a measure of similarity between a first (or input) document and one or more disparate (or search results) documents, the article of manufacture comprising computer usable storage media including computer readable instructions embedded therein that causes a computer to perform a method, wherein the method comprises:

(a) receiving a first document and identifying the best keywords in the text by recognizing rare and uncommon keywords, including keywords that belong to one or more domain specific or subject matter specific dictionary;

(b) identifying documents similar to the first document using a query by formulating wrappers using the list of the best keywords identified in the first document that also appear in a DS dictionary;

c) receiving a first list of rated keywords extracted from the first document and a second list of rated keywords extracted from the second document;

(d) using the first and second lists of rated keywords to determine whether the first document forms part of the second document using a first computed percentage indicating what percentage of keyword ratings in the first list also exist in the second list;

(e) verifying inclusion of the first document in the second document computing a second percentage indicating what percentage of keyword ratings along with a set of their neighboring keyword ratings in the first list also exist in the second list when the first computed percentage indicates that the first document is included in the second document;

(f) using the first computed percentage to specify the measure of similarity when the second computed percentage is greater than the first computed percentage;

(g) if the first computed percentage does not indicate that the first document is included in the second document, computing a third percentage using the Jaccard distance measure, wherein if said Jaccard similarity distance measure is greater than about 90 percent, the second document is identified as a revision of the first document, and if the Jaccard similarity distance measure is less than about 90 percent, said measure is a similarity measure between said first and second document; and

(h) if the third computed percentage indicates that the first document is a revision of the second document, computing a fourth percentage indicating what percentage of keyword ratings along with a set of their neighboring keyword ratings in the second list also exist in the first list, the fourth computed percentage is used to specify the measure of similarity except when: (i) the fourth computed percentage is greater than the second computed percentage; (ii) the first list of rated keywords is identified using OCR; (iii) the fourth computed percentage is greater than fifty percent; and (iv) less than twenty percent of the keywords in the first list of keywords are in the second list of keywords.

Assignments (9)

Continuity (1)