Method and device to estimate similarity between documents having multiple segments

• US 9,892,111 B2
• Filed: 10/26/2012
• Issued: 02/13/2018
• Est. Priority Date: 10/10/2006
• Status: Expired due to Fees

• Current Assignee: ABBYY Development LLC
• Original Assignee: ABBYY Production LLC (ABBYY Software)
• Inventors: Danielyan, Tatiana, Zuev, Konstantin
• Primary Examiner(s): Corrielus, Jean M
• Application Number:
  US13/662,272
• Publication Number:
  US 20130054612A1
• Time in Patent Office: 1,936 Days
• Field of Search: None
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Described herein are methods for finding substantially similar/different sources (files and documents), and estimating similarity or difference between given sources. Similarity and difference may be found across a variety of formats. Sources may be in one or more languages such that similarity and difference may be found across any number and types of languages. A variety of characteristics may be used to arrive at an overall measure of similarity or difference including determining or identifying syntactic roles, semantic roles and semantic classes in reference to sources.

Claims

1. A method for comparing a first document and a second document, the method comprising:

associating, by a processor, a respective weight with each of a plurality of information types including text-based information, graphical information, audio information, or video information;

identifying, for each of the first document and the second document, by the processor, one or more segments each corresponding to one of the plurality of information types; and

estimating, by the processor, a similarity value between the first document and the second document, by comparing each segment of the first document with a segment of the second document that corresponds to a same information type, wherein the similarity value is based on a distance, in a semantic hierarchy, between a first semantic class associated with the first document and a common ancestor, in the semantic hierarchy, of the first semantic class and a second semantic class associated with a second document; and

combining results of the comparison based on the respective associated weights.

2. The method of claim 1, wherein estimating the similarity value further comprises:

constructing a first language-independent semantic structure (LISS) for a first sentence of the first document; and

identifying the first semantic class using the language-independent semantic structure.

3. The method of claim 2, further comprising:

displaying through a user interface a portion of the first document and a portion of the second document;

identifying fragments of the first and the second documents that are related to said similarity value; and

aligning, using the user interface, the identified fragments with respect to each other.

4. The method of claim 3, further comprising:

constructing a second language-independent semantic structure for a second sentence of the second document; and

aligning identified fragments of the first document and the second document based on a comparison of the first language-independent semantic structure and the second language-independent semantic structure.

5. The method of claim 2, further comprising:

indexing the first sentence.

6. The method of claim 5, wherein the first index includes an index of lexical features.

7. The method of claim 5, wherein the first index includes an index of grammatical features.

8. The method of claim 5, wherein the first index includes an index of syntactical features.

9. The method of claim 5, wherein the first index includes an index of semantic features.

10. The method of claim 2, further comprising:

constructing a second language-independent semantic structure for a second sentence of the second document;

indexing the first language-independent semantic structure to produce a first index; and

indexing the second language-independent semantic structure to produce a second index.

11. The method of claim 10, wherein said estimating the similarity value between the first and second documents comprises comparing the first index and the second index.

12. The method of claim 2, wherein the first sentence is in a different language than a second sentence of the second document.

13. The method of claim 2, further comprising:

indexing semantic classes of the first sentence of the first document and a second sentence of the second document, and wherein said estimating the similarity value comprises comparing indexes of the semantic classes.

14. The method of claim 1, further comprising:

performing optical character recognition (OCR) on the one or more segments that include text in the form of graphical information.

15. The method of claim 14, wherein the method further comprises:

converting each of the segments that correspond to non-text-based information to one or more text-based source sentences thereby creating a text-based equivalent block for each of the segments that correspond to non-text-based information.

16. The method of claim 1, further comprising:

displaying the estimated similarity value through a user interface.

17. The method of claim 16, wherein said displaying the similarity value includes:

determining that the similarity value exceeds a similarity threshold value.

18. The method of claim 16, wherein said displaying the estimated similarity value between the first and second documents includes:

performing at least one of;

highlighting, underlying, or changing a font of respective pairs of similar portions of text-based information in the first and the second documents, wherein each of the respective pair of similar portions of text-based information includes a portion in the first document and a portion in the second document that are associated with a respective similarity value.

19. The method of claim 1, further comprising:

determining a logical structure of each of the first document and the second document, and wherein said estimating the similarity value is further based on said logical structures.

20. An electronic device for comparing documents, the electronic device comprising:

a memory; and

a processor communicatively coupled to the memory, the processor configured to;

associate a respective weight with each of a plurality of information types including text-based information, graphical information, audio information, or video information;

identify, for each of the first document and the second document, one or more segments each corresponding to one of the plurality of information types; and

estimate a similarity value between the first document and the second document, by comparing each segment of the first document with a segment of the second document that correspond to a same information type, wherein the similarity value is based on a distance, in a semantic hierarchy, between a first semantic class associated with the first document and a common ancestor, in the semantic hierarchy, of the first semantic class and a second semantic class associated with a second document; and

combine results of the comparison based on the respective associated weights.

21. The electronic device of claim 20, wherein the method further comprises:

construct a first language-independent semantic structure (LISS) for a first sentence of the first document; and

identify the first semantic class using the language-independent semantic structure.

22. The electronic device of claim 21, wherein the processor is further configured to:

display through a user interface a portion of the first document and a portion of the second document;

identify fragments of the first and the second documents that are related to said similarity value; and

align, using the user interface, the identified fragments with respect to each other.

23. The electronic device of claim 20, wherein the processor is further configured to:

perform optical character recognition (OCR) on the one or more segments that include text in the form of graphical information.