Method and apparatus for retrieving text using document signatures

• US 6,820,079 B1
• Filed: 01/18/2000
• Issued: 11/16/2004
• Est. Priority Date: 07/25/1997
• Status: Expired due to Fees

• Current Assignee: Justsystems Evans Research Incorporated
• Original Assignee: Claritech Corporation
• Inventors: Evans, David A.
• Primary Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/483,868
• Time in Patent Office: 1,764 Days
• Field of Search: 707/1-531, 711/1, 704/9
• US Class Current: 1/1
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method and apparatus for retrieving similar or identical textual passages among different documents is disclosed. Normal discourse structures along with textual content attributes are used to encode a known passage with “marker sequences” that give a characterizing “signature” to the passage. The encoded known passage is then evaluated against similarly encoded passages appearing in a database of documents. If it is determined that there is a possible match between the encoded known passage and an encoded passage in a database document, a sequential string search is performed to determine whether the two passages are likely to be similar or identical. If the sequential string search records a probable match between the known passage and the database passage, the database passage is displayed for further review.

Claims

1. A method for retrieving text, comprising:

identifying markers in a first text passage;

representing the number of non-marker characters between said identified markers in said first text passage to generate a first marker sequence;

identifying markers in a second text passage;

representing the number of non-marker characters between said identified markers in said second text passage to generate a second marker sequence; and

comparing said first marker sequence to said second marker sequence.

2. A method for retrieving text, as in claim 1, wherein said markers comprise at least one discourse and one content feature.

3. A method for retrieving text, as in claim 2, wherein said discourse feature is chosen from the characters in the ASCII code set.

4. A method for retrieving text, as in claim 2, wherein said content feature is an n-gram sequence of alpha-numeric characters.

5. A method for retrieving text, as in claim 1, wherein said markers comprise one discourse feature.

6. A method for retrieving text, as in claim 5, wherein said discourse feature is chosen from the characters in the ASCII code set.

7. A method for retrieving text, as in claim 1, wherein said markers comprise one content feature.

8. A method for retrieving text, as in claim 7, wherein said content feature is an n-gram sequence of alpha-numeric characters.

9. A method for retrieving text, as in claim 1, wherein said markers comprise a stop character.

10. A method for retrieving text, as in claim 1, wherein said markers comprise a paragraph break.

11. An apparatus for retrieving text, comprising:

a processing unit coupled to an input device and a storage unit for selecting a first text passage, wherein said processor unit identifies markers in said first text passage and represents the number of non-marker characters between said markers in said first text passage to generate a first marker sequence; and

wherein

said processing unit identifies markers in a second text passage and represents the number of non-marker characters between markers in said second text passage to generate a second marker sequence; and

wherein

said processing unit compares said first marker sequence to said second marker sequence to retrieve text.

12. An apparatus, as in claim 11, wherein said markers comprise at least one discourse feature and one content feature.

13. An apparatus, as in claim 12, wherein said discourse feature is chosen from the characters in the ASCII code set.

14. An apparatus, as in claim 12, wherein said content feature is an n-gram sequence of alpha-numeric characters.

15. An apparatus, as in claim 11, wherein said markers comprise one discourse feature.

16. An apparatus, as in claim 15, wherein said discourse feature is chosen from the characters in the ASCII code set.

17. An apparatus, as in claim 11, wherein said marker comprises one content feature.

18. An apparatus, as in claim 17, wherein said content feature is an n-gram sequence of alpha-numeric characters.

19. An apparatus, as in claim 11, wherein said markers comprise a stop character.

20. An apparatus, as in claim 11, wherein said markers comprise a paragraph break.