Automatically generating a topic description for text and searching and sorting text by topic using the same

US 5,937,422 A
Filed: 04/15/1997
Issued: 08/10/1999
Est. Priority Date: 04/15/1997
Status: Expired due to Term

First Claim

Patent Images

1. A method of automatically generating a topical description of text, comprising the steps of:

a) receiving the text, where the text consists of one or more input words;

b) stemming each input word to its root form;

c) assigning a user-definable part-of-speech score β

_i to each input word;

d) assigning a language salience score S_i to each input word;

e) assigning an input-word score to each input word that is a function of the corresponding input word'"'"'s part-of-speech score β

_i, language salience score S_i, and the number of times the corresponding input word appears in the text;

f) creating a tree structure under each input word, where each tree structure contains the definition of the corresponding input word, where each definition word may be further defined to a user-definable number of levels;

g) assigning a definition-word score A_i,t j! to each definition word in each tree structure based on the definition word'"'"'s part-of-speech score β

_j, the language salience score of the word the definition word defines, a relational salience score R_k,j, and a user-definable factor W;

h) collapsing each tree structure to a corresponding tree-word list, where each tree-word list contains the unique words contained in the corresponding tree structure;

i) assigning a tree-word-list score to each word in each tree-word list, where each tree-word-list score is a function of the scores of the corresponding word that existed in the corresponding uncollapsed tree structure;

j) combining the tree-word lists into a final word list, where the final word list contains the unique words contained in the tree-word lists;

k) assigning a final-word-list score A_fi j! to each word in the final word list, where A_fi j! is a function of the corresponding word'"'"'s dictionary salience and tree-word-list scores; and

l) choosing the top N scoring words in the final word list as the topic description of the input text, where the value N may be defined by the user.

View all claims

1 Assignment

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

A method of automatically generating a topical description of text by receiving the text containing input words; stemming each input word to its root form; assigning a user-definable part-of-speech score to each input word; assigning a language salience score to each input word; assigning an input-word score to each input word; creating a tree structure under each input word, where each tree structure contains the definition of the corresponding input word; assigning a definition-word score to each definition word; collapsing each tree structure to a corresponding tree-word list; assigning a tree-word-list score to each entry in each tree-word list; combining the tree-word lists into a final word list; assigning each word in the final word list a final-word-list score; and choosing the top N scoring words in the final word list as the topic description of the input text. Document searching and sorting may be accomplished by performing the method described above on each document in a database and then comparing the similarity of the resulting topical descriptions.

390 Citations

31 Claims

1. A method of automatically generating a topical description of text, comprising the steps of:
- a) receiving the text, where the text consists of one or more input words;
  
  b) stemming each input word to its root form;
  
  c) assigning a user-definable part-of-speech score β
  
  _i to each input word;
  
  d) assigning a language salience score S_i to each input word;
  
  e) assigning an input-word score to each input word that is a function of the corresponding input word'"'"'s part-of-speech score β
  
  _i, language salience score S_i, and the number of times the corresponding input word appears in the text;
  
  f) creating a tree structure under each input word, where each tree structure contains the definition of the corresponding input word, where each definition word may be further defined to a user-definable number of levels;
  
  g) assigning a definition-word score A_i,t j! to each definition word in each tree structure based on the definition word'"'"'s part-of-speech score β
  
  _j, the language salience score of the word the definition word defines, a relational salience score R_k,j, and a user-definable factor W;
  
  h) collapsing each tree structure to a corresponding tree-word list, where each tree-word list contains the unique words contained in the corresponding tree structure;
  
  i) assigning a tree-word-list score to each word in each tree-word list, where each tree-word-list score is a function of the scores of the corresponding word that existed in the corresponding uncollapsed tree structure;
  
  j) combining the tree-word lists into a final word list, where the final word list contains the unique words contained in the tree-word lists;
  
  k) assigning a final-word-list score A_fi j! to each word in the final word list, where A_fi j! is a function of the corresponding word'"'"'s dictionary salience and tree-word-list scores; and
  
  l) choosing the top N scoring words in the final word list as the topic description of the input text, where the value N may be defined by the user.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)
- - 2. The method of claim 1, wherein said step of receiving the text, is comprised of the step of receiving text wherein said text is selected from the group consisting of speech-based text, optical-character-read text, stop-word-filtered text, stutter-phrase-filtered text, and lexical-collocation-filtered text.
  - 3. The method of claim 1, wherein said step of assigning a language salience score S_i to each input word is comprised of the step of determining the language salience score for each input word from the frequency count f_i of each word in a large corpus of text as follows:
    - space="preserve" listing-type="equation">S.sub.i =0, if f.sub.i >
      
      f.sub.max ;
      space="preserve" listing-type="equation">S.sub.i =log (f.sub.max /(f.sub.i -T.sup.2 +T)), if T.sup.2 <
      
      f.sub.i <
      
      f.sub.max ;
      space="preserve" listing-type="equation">S.sub.i =log (f.sub.max /T), if T<
      
      f.sub.i<
      
      T.sup.2 ; and
      space="preserve" listing-type="equation">S.sub.i =ε
      
      +((f.sub.i /T)(log(f.sub.max /T)-ε
      
      )), if f.sub.i≦
      
      T,
      where ε and
      
      T are user-definable values, and where f_max represents a point where the sum of frequencies of occurrence above the point equals the sum of frequencies of occurrence below the point.
  - 4. The method of claim 3, wherein said step of assigning a language salience score S_i to each input word further comprises the step of allowing the user to over-ride the language salience score for a particular word with a user-definable language salience score.
  - 5. The method of claim 1, wherein said step of assigning an input-word score to each input word is comprised of the step of assigning an input-word score where said input-word score is selecting from the group consisting of mS_i β
    - _i and (S_i m)β
      
      _i, where m is the number of times the corresponding input word occurs in the text.
  - 6. The method of claim 1, wherein said step of creating a tree structure under each input word is comprised of creating a tree structure under each input word using a recursively closed dictionary.
  - 7. The method of claim 1, wherein said step of creating a tree structure under each input word is comprised of creating a tree structure under each input word using a database selected from a group consisting of a thesaurus, an encyclopedia, and a word-based relational database.
  - 8. The method of claim 1, wherein said step of creating a tree structure under each input word is comprised of creating a tree structure under each input word using a recursively closed dictionary that is in a different language than the text.
  - 9. The method of claim 1, wherein said step of assigning a definition-word score to each definition word in each tree structure is comprised of assigning a definition-word score to each definition word as follows:
    - A_i,t j!=W(β
      
      _j,t)Σ
      
      A_i,t-1 k!R_k,j, where R_i,j =D_j /Σ
      
      D_k), where Σ
      
      D_k represents the sum of the dictionary saliences of the words in the definition of word w_i, where D_j =β
      
      _j (S_j log(d_max /d_j)) 0.5, where d_t is the number of dictionary terms that use the corresponding word in its definition, and where d_max is the number of times the most frequently used word in the dictionary is used.
  - 10. The method of claim 1, wherein said step of assigning a definition-word score to each definition word in each tree structure is comprised of assigning a definition-word score to each definition word as follows:
    - A_i,t j!=W(β
      
      _j,t)Σ
      
      A_i,t-1 k!R_k,j, where R_i,j =D_j /Σ
      
      D_k), where Σ
      
      D_k represents the sum of the dictionary saliences of the words in the definition of word w_i, where D_j =β
      
      _j (S_j log(d_m /Δ
      
      _j)) 0.5, where Δ
      
      _j =max(d_j, ε
      
      ), and d_m is chosen such that a fixed percentage of the observed values of the d_j '"'"'s are larger than d_m.
  - 11. The method of claim 1, wherein said step of assigning a definition-word score is comprised of the step of assigning a score to each definition word that is user-definable.
  - 12. The method of claim 1, wherein said step of collapsing each tree structure is comprised of collapsing each tree structure to a corresponding tree-word list, where each tree-word list contains only salient input words and definition words in a particular tree structure having the highest score while ignoring lower scoring definition words in that tree structure even if the lower scoring definition words score higher than definition words contained in other tree structures.
  - 13. The method of claim 1, wherein said step of assigning a tree-word-list score to each word in each tree-word list is comprised of assigning a tree-word-list score that is the sum of the scores associated with the word in its corresponding tree structure.
  - 14. The method of claim 1, wherein said step of assigning a final word list score is comprised of the step of assigning a final word list score according to the following equation
    
    space="preserve" listing-type="equation">A.sub.fi j!=((D.sub.j (f(A.sub.i j!)))Σ
    
    A.sub.i j!).
- 15. The method of claim 1, further comprising the step of translating the topic description into a language different from the input text and the language of the dictionary.
- 16. The method of claim 1, further comprising the steps of:
  - a) receiving a plurality of documents, where one of said plurality of documents is identified as the document of interest;
    
    b) determining a topic description for each of said plurality of documents;
    
    c) comparing the topic descriptions of each of said plurality of documents to the topic description of said document of interest; and
    
    d) returning each of said plurality of documents that has a topic description that is sufficiently similar to the topic description of said document of interest.
- 17. The method of claim 1, further comprising the steps of:
  - a) receiving a plurality of documents;
    
    b) determining a topic description for each of said plurality of documents;
    
    c) comparing the topic descriptions of each of said plurality of documents to each other of said plurality of documents; and
    
    d) sorting said plurality of documents by topic description.
- 18. The method of claim 2, wherein said step of assigning a language salience score S_i to each input word is comprised of the step of determining the language salience score for each input word from the frequency count f_i of each word in a large corpus of text as follows:
  - space="preserve" listing-type="equation">S.sub.i =0, if f.sub.i >
    
    f.sub.max ;
    space="preserve" listing-type="equation">S.sub.i =log (f.sub.max /(f.sub.i -T.sup.2 +T)), if T.sup.2 <
    
    f.sub.i <
    
    f.sub.max ;
    space="preserve" listing-type="equation">S.sub.i =log (f.sub.max /T), if T<
    
    f.sub.i<
    
    T.sup.2 ;
    
    and
    space="preserve" listing-type="equation">S.sub.i =ε
    
    +((f.sub.i /T)(log(f.sub.max /T)-ε
    
    )), if f.sub.i ≦
    
    T,
    where ε and
    
    T are user-definable values, and where f_max represents a point where the sum of frequencies of occurrence above the point equals the sum of frequencies of occurrence below the point.
- 19. The method of claim 18, wherein said step of assigning a language salience score S_i to each input word further comprises the step of allowing the user to over-ride the language salience score for a particular word with a user-definable language salience score.
- 20. The method of claim 19, wherein said step of assigning an input-word score to each input word is comprised of the step of assigning an input-word score where said input-word score is selecting from the group consisting of mS_i β
  - _i and (S_i m)β
    
    _i, where m is the number of times the corresponding input word occurs in the text.
- 21. The method of claim 20, wherein said step of creating a tree structure under each input word is comprised of creating a tree structure under each input word using a recursively closed dictionary.
- 22. The method of claim 21, wherein said step of creating a tree structure under each input word is comprised of creating a tree structure under each input word using a recursively closed dictionary that is in a different language than the text.
- 23. The method of claim 22, wherein said step of assigning a definition-word score to each definition word in each tree structure is comprised of assigning a definition-word score to each definition word as follows:
  - A_i,t j!=W(β
    
    _j, t)Σ
    
    A_i,t-1 k!R_k,j, where R_i,j =D_j /Σ
    
    D_k), where Σ
    
    D_k represents the sum of the dictionary saliences of the words in the definition of word w_i, where D_j =β
    
    _j (S_j log(d_max /d_j)) 0.5, where d_t is the number of dictionary terms that use the corresponding word in its definition, and where d_max is the number of times the most frequently used word in the dictionary is used.
- 24. The method of claim 23, wherein said step of assigning a definition-word score to each definition word in each tree structure is comprised of assigning a definition-word score to each definition word as follows:
  - A_i,t j!=W(β
    
    _j,t)Σ
    
    A_i,t-1 k!R_k, j, where R_i, j =D_j /Σ
    
    D_k), where Σ
    
    D_k represents the sum of the dictionary saliences of the words in the definition of word w_i, where D_j =β
    
    _j (S_j log (d_m /Δ
    
    _j)) 0.5, where Δ
    
    _j =max(d_j, ε
    
    ), and d_m is chosen such that a fixed percentage of the observed values of the d_j '"'"'s are larger than d_m.
- 25. The method of claim 24, wherein said step of assigning a definition-word score is comprised of the step of assigning a score to each definition word that is user-definable.
- 26. The method of claim 25, wherein said step of collapsing each tree structure is comprised of collapsing each tree structure to a corresponding tree-word list, where each tree-word list contains only salient input words and definition words in a particular tree structure having the highest score while ignoring lower scoring definition words in that tree structure even if the lower scoring definition words score higher than definition words contained in other tree structures.
- 27. The method of claim 26, wherein said step of assigning a tree-word-list score to each word in each tree-word list is comprised of assigning a tree-word-list score that is the sum of the scores associated with the word in its corresponding tree structure.
- 28. The method of claim 27, wherein said step of assigning a final word list score is comprised of the step of assigning a final word list score according to the following equation
  
  space="preserve" listing-type="equation">A.sub.fi j!=((D.sub.j (f(A.sub.i j!)))Σ
  
  A.sub.i j!).
29. The method of claim 28, further comprising the step of translating the topic description into a language different from the input text and the language of the dictionary.
30. The method of claim 29, further comprising the steps of:
- a) receiving a plurality of documents, where one of said plurality of documents is identified as the document of interest;
  
  b) determining a topic description for each of said plurality of documents;
  
  c) comparing the topic descriptions of each of said plurality of documents to the topic description of said document of interest; and
  
  d) returning each of said plurality of documents that has a topic description that is sufficiently similar to the topic description of said document of interest.
31. The method of claim 30, further comprising the steps of:
- a) receiving a plurality of documents;
  
  b) determining a topic description for each of said plurality of documents;
  
  c) comparing the topic descriptions of each of said plurality of documents to each other of said plurality of documents; and
  
  d) sorting said plurality of documents by topic description.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
National Security Agency The United States Government As Represented By The Director
Original Assignee
The United States of America As Represented By The Director National Security Agency
Inventors
Bates, Richard Michael, Schone, Patrick John, Nelson, Douglas J.
Primary Examiner(s)
Amsbury, Wayne
Assistant Examiner(s)
CHANNAVAJJALA, SRIRAMA T

Application Number

US08/834,263
Time in Patent Office

847 Days
Field of Search

704/10, 707/512, 707/532, 707/535, 707/531, 707/3-5, 707/7
US Class Current

715/206
CPC Class Codes

G06F 16/353 into predefined classes

Y10S 707/99934 Query formulation, input pr...

Automatically generating a topic description for text and searching and sorting text by topic using the same

First Claim

1 Assignment

0 Petitions

Accused Products

Abstract

390 Citations

31 Claims

Specification

Solutions

Use Cases

Quick Links

Automatically generating a topic description for text and searching and sorting text by topic using the same

First Claim

1 Assignment

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

390 Citations

31 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links