Method and apparatus for generating a language independent document abstract

• US 8,005,665 B2
• Filed: 07/23/2010
• Issued: 08/23/2011
• Est. Priority Date: 09/28/1998
• Status: Expired due to Fees

• Current Assignee: Callahan Cellular LLC (Intellectual Ventures LLC)
• Original Assignee: Schukhaus Group GmbH LLC (Intellectual Ventures LLC)
• Inventors: Chaney, Garnet R., Rubinstein, Seymour I., Richardson, Robert F.
• Primary Examiner(s): Chawan; Vijay B
• Application Number:
  US12/842,778
• Publication Number:
  US 20100305942A1
• Time in Patent Office: 396 Days
• Field of Search: 704/2, 704/4, 704/9, 704/10, 704/231, 704/251, 704/257, 704/236, 704/245, 704/240, 704/270
• US Class Current: 704/9
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93

Abstract

A method of extracting significant phrases from one or more documents stored in a computer-readable medium. A sequence of words is read from the one or more documents and a score is determined for each word in the sequence based on the length of the word. The score for each word in the sequence is compared against a threshold score. The sequence of words is indicated to be a significant phrase if the number of words in the sequences that have a score greater than the threshold score equals or exceeds a predetermined number. A sentence containing the sequence of words is retrieved from the document, if the sequence of words is a significant phrase. An abstract of the document is searched to determine if the sentence has been previously included in the abstract. If not, the sentence is added to the abstract.

Claims

1. A method of automatic, computer based creation of a cross-index for a set of documents, the method comprising:

accessing a memory to read at least a sequence of words from a document in the set of documents;

determining by a processing unit a respective score for at least a subset of words in the sequence based at least in part on word length;

operating the processing unit to determine a number of the at least a subset of words in the sequence that have a score greater than or equal to a threshold score;

operating the processing unit to determine whether the sequence of words contains a number of words that satisfies a verbosity setting;

determining that the sequence of words is a significant phrase in response to determining that the number of the at least a subset of words in the sequence that have a score greater than or equal to the threshold score equals or exceeds a predetermined number and determining that the number of words in the sequence satisfies the verbosity setting; and

adding the significant phrase to a cross-index for the set of documents in response to determining that the significant phrase has been found in more than one document in the set of documents.

2. The method of claim 1 wherein accessing the memory to read at least the sequence of words from the document in the set of documents comprises accessing a memory to read at least the sequence of words from the document in the set of documents until a phrase delimiter is detected.

3. The method of claim 1 wherein determining by the processing unit the respective score further comprises increasing the respective score in response to detecting at least one capitalized letter in the word.

4. The method of claim 1 wherein determining by the processing unit the respective score further comprises:

determining whether the word exists in a predetermined table; and

retrieving the score for the word from the predetermined table.

5. The method of claim 1 wherein adding the significant phrase to the cross-index for the set of documents further comprises searching the cross-index to determine whether the significant phrase was previously added to the cross-index;

and

the method further comprising discarding the significant phrase in response to determining that the significant phrase was previously added to the cross-index.

6. The method of claim 1 wherein adding the significant phrase to the cross-index for the set of documents further comprises:

retrieving a sentence from the document, the sentence containing the sequence of words; and

adding the sentence to the cross-index for the set of documents.

7. A tangible computer readable medium having instructions stored thereon, the instructions configured to cause a computing device to perform operations comprising:

accessing a memory to read at least a sequence of words from a document in the set of documents;

determining a respective score for at least a subset of words in the sequence based at least in part on word length;

determining a number of the at least a subset of words in the sequence that have a score greater than or equal to a threshold score;

determining whether the sequence of words contains a number of words that satisfies a verbosity setting;

determining that the sequence of words is a significant phrase in response to determining that the number of the at least a subset of words in the sequence that have a score greater than or equal to the threshold score equals or exceeds a predetermined number and determining that the number of words in the sequence satisfies the verbosity setting; and

adding the significant phrase to a cross-index for the set of documents in response to determining that the significant phrase has been found in more than one document in the set of documents.

8. The tangible computer readable medium of claim 7 wherein accessing the memory to read at least the sequence of words from the document in the set of documents comprises accessing a memory to read at least the sequence of words from the document in the set of documents until a phrase delimiter is detected.

9. The tangible computer readable medium of claim 7 wherein determining by the processing unit the respective score further comprises increasing the respective score in response to detecting at least one capitalized letter in the word.

10. The tangible computer readable medium of claim 7 wherein determining by the processing unit the respective score further comprises:

determining whether the word exists in a predetermined table; and

retrieving the score for the word from the predetermined table.

11. The tangible computer readable medium of claim 7 wherein adding the significant phrase to the cross-index for the set of documents further comprises searching the cross-index to determine whether the significant phrase was previously added to the cross-index;

and

the operations further comprising discarding the significant phrase in response to determining that the significant phrase was previously added to the cross-index.

12. The tangible computer readable medium of claim 7 wherein adding the significant phrase to the cross-index for the set of documents further comprises:

retrieving a sentence from the document, the sentence containing the sequence of words; and

adding the sentence to the cross-index for the set of documents.

13. A processing system configured to create a cross-index for a set of documents, the processing system comprising:

a memory device configured to store the set of documents, a threshold score, and a verbosity setting;

a processing device;

a bus operably coupling the processing device to the memory;

the processing device configured to;

access the memory to read at least a sequence of words from a document in the set of documents;

determine a respective score for at least a subset of words in the sequence based at least in part on word length;

determine a number of the at least a subset of words in the sequence that have a score greater than or equal to a threshold score;

determine whether the sequence of words contains a number of words that satisfies a verbosity setting;

determine that the sequence of words is a significant phrase in response to determining that the number of the at least a subset of words in the sequence that have a score greater than or equal to the threshold score equals or exceeds a predetermined number and determining that the number of words in the sequence satisfies the verbosity setting; and

add the significant phrase to a cross-index for the set of documents in response to determining that the significant phrase has been found in more than one document in the set of documents.

14. The processing system of claim 13 wherein a score for a word is proportional to a number of characters in the word.

15. The processing system of claim 14 wherein the number of characters in the word includes the number of numeric digits in the word.

16. The processing system of claim 13 wherein a score for a word comprises a length of the word plus a number of capitalized letters in the word.

17. The processing system of claim 13 wherein the threshold score is based on an average of scores of words in the at least a subset of words.

18. The processing system of claim 17 wherein the threshold score is adjusted by a predetermined value to be different from the average of scores of words in the at least a subset of words.

19. The processing system of claim 13 wherein the cross-index is language independent.

20. The processing system of claim 13 wherein the processing device is configured to access the memory to read at least a sequence of words from a document in the set of documents until a phrase delimiter is reached.

21. The processing system of claim 13 further comprising a phrase buffer configured to accumulate phrases that are conditionally added to a phrase list and a phrase word count configured to determine the total number of qualified words in the phrase buffer.

22. A tangible computer readable medium having instructions store thereon, the instructions configured to cause a computing device to perform operations comprising:

receiving a threshold score;

reading a sequence of words in the document;

determining a score for respective words in the sequence of words based on at least a length of the respective words;

comparing the score to the threshold score; and

terminating the reading of the sequence of words in response to determining that a phrase delimiter has been reached, wherein the phrase delimiter includes at least one of a word longer than a predetermined length or a sequence of a first predetermined number of words having a score less than the threshold score.

23. The tangible computer readable medium of claim 22 further comprising adding the sequence of words as a significant phrase to a significant phrase data structure in response to determining that the number of words in the sequence that have the score greater than the threshold score equals or exceeds a predetermined number.

24. The tangible computer readable medium of claim 23 further comprising:

retrieving a sentence from the document in response to determining that the sentence contains a significant phrase stored in the significant phrases data structure; and

operating the processing unit to search the abstract of the document to determine whether the sentence is included in the abstract.

25. The tangible computer readable medium of claim 22 further comprising identifying a significant phrase in a document with a single pass through the words of the document and the recognition of adjacent pattern comparisons of long words surrounded by short words.

26. The tangible computer readable medium of claim 22 wherein determining a score further comprises:

determining whether the word exists in a predetermined table; and

retrieving the score for the word from the predetermined table.

27. The tangible computer readable medium of claim 22 wherein the threshold score is based on an average of the scores of words in the sequence of words.

28. A processing system configured to create an abstract for a document, the processing system comprising:

a memory device configured to store the document and a threshold score;

a processing device;

a bus operably coupling the processing device to the memory;

the processing device configured to;

access the memory to retrieve the document and the threshold score;

read a sequence of words in the document;

determine a score for respective words in the sequence of words based on at least a length of the respective words;

compare the score to the threshold score; and

terminate the reading of the sequence of words in response to determining that a phrase delimiter has been reached, wherein the phrase delimiter includes at least one of a word longer than a predetermined length or a sequence of a first predetermined number of words having a score less than the threshold score.

29. The processing system of claim 28 wherein the score for the respective words is proportional to a number of characters in the respective words.

30. The processing system of claim 28 wherein the score for the respective words is a length of the respective words plus a number of capitalized letters in the respective words.

31. The processing system of claim 28 wherein the threshold score is based on an average of the scores.

32. The processing system of claim 28 wherein the processing device is further configured to add the sequence of words as a significant phrase to a significant phrase data structure in response to determining that the number of words in the sequence that have the score greater than the threshold score equals or exceeds a predetermined number.

33. The processing system of claim 32 wherein the significant phrase data structure is language independent.

34. The processing system of claim 28 further comprising a phrase buffer configured to accumulate phrases that are conditionally added to a phrase list and a phrase word count configured to determine the total number of qualified words in the phrase buffer.

35. A tangible computer readable medium having instructions stored thereon, the instructions configured to cause a computing device to perform operations comprising:

receiving at least a verbosity score, a threshold score, and a sequence threshold score from a user input;

accessing a memory to read at least a sequence of words from the document;

extracting the sequence of words from the document based upon a determination that the sequence includes a number of words greater than or equal to the verbosity score and a number of words having a score greater than or equal to the threshold score is greater than or equal to the sequence threshold score;

searching the abstract to determine whether the sequence of words is included in the abstract; and

adding the sequence of words to the abstract in response to determining that the sequence was not included in the abstract.

36. The tangible computer readable medium of claim 35 further comprising self-tuning the verbosity setting to the complexity of the document in response to not receiving a verbosity setting from an input device.

37. The tangible computer readable medium of claim 35 wherein determining a score further comprises:

determining whether the word exists in a predetermined table; and

retrieving the score for the word from the predetermined table.

38. The tangible computer readable medium of claim 35 further comprising basing the threshold score on an average of the scores of words in the sequence of words.

39. A processing system configured to create an abstract for a document, the processing system comprising:

a memory device configured to store the document;

a processing device;

a user input;

the processing device configured to;

receive at least a verbosity score, a threshold score, and a sequence threshold score from the user input;

access the memory to read at least a sequence of words from the document;

extract the sequence of words from the document based upon a determination that the sequence includes a number of words greater than or equal to the verbosity score and a number of words having a score greater than or equal to the threshold score is greater than or equal to the sequence threshold score;

search the abstract to determine whether the sequence of words is included in the abstract; and

add the sequence of words to the abstract in response to determining that the sequence was not included in the abstract.

40. The processing system of claim 39 wherein the score for respective words is proportional to a number of characters in the respective words.

41. The processing system of claim 39 wherein the score for respective words comprises a length of the respective words plus a number of capitalized letters in the respective words.

42. The processing system of claim 39 wherein the threshold score is based on an average of the scores.

43. The processing system of claim 39 wherein the abstract is language independent.