US5937422A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automatically generating a topic description for text and searching and sorting text by topic using the same
Assignee: NATIONAL SECURITY AGENCY UNITED STATES GOVERNMENT AS REPRESENTED BY DIRECTOR
•
Filing: 1997-04-15
•
Granted: 1999-08-10
•
Expires: 2017-04-15
Abstract
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.
Inventors
- 👤 Douglas J. Nelson
- 👤 Patrick John Schone
- 👤 Richard Michael Bates
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 05:45
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/35; G06F16/353; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
333 words
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.
Claim 2
Independent Claim
333 words
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.
Claim 3
Dependent Claim
41 words
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.
Claim 4
Dependent Claim
117 words
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: S.sub.i =0, if f.sub.i >f.sub.max ; S.sub.i =log (f.sub.max /(f.sub.i -T.sup.2 +T)), if T.sup.2 <f.sub.i <f.sub.max ; S.sub.i =log (f.sub.max /T), if T<f.sub.i<T.sup.2 ; and 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.
Claim 5
Dependent Claim
44 words
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.
Claim 6
Dependent Claim
63 words
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.
Claim 7
Dependent Claim
33 words
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.
Claim 8
Dependent Claim
46 words
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.
Claim 9
Dependent Claim
42 words
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.
Claim 10
Dependent Claim
124 words
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.
Claim 11
Dependent Claim
120 words
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 .
Claim 12
Dependent Claim
29 words
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.
Claim 13
Dependent Claim
73 words
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.
Claim 14
Dependent Claim
43 words
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.
Claim 15
Dependent Claim
37 words
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 A.sub.fi j!=((D.sub.j (f(A.sub.i j!)))ΣA.sub.i j!).
Claim 16
Dependent Claim
28 words
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.
Claim 17
Dependent Claim
90 words
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.
Claim 18
Dependent Claim
58 words
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.
Claim 19
Dependent Claim
117 words
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: S.sub.i =0, if f.sub.i >f.sub.max ; S.sub.i =log (f.sub.max /(f.sub.i -T.sup.2 +T)), if T.sup.2 <f.sub.i <f.sub.max ; S.sub.i =log (f.sub.max /T), if T<f.sub.i<T.sup.2 ;and 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.
Claim 20
Dependent Claim
44 words
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.
Claim 21
Dependent Claim
63 words
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.
Claim 22
Dependent Claim
33 words
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.
Claim 23
Dependent Claim
42 words
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.
Claim 24
Dependent Claim
125 words
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.
Claim 25
Dependent Claim
123 words
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 .
Claim 26
Dependent Claim
29 words
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.
Claim 27
Dependent Claim
73 words
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.
Claim 28
Dependent Claim
43 words
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.
Claim 29
Dependent Claim
37 words
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 A.sub.fi j!=((D.sub.j (f(A.sub.i j!)))ΣA.sub.i j!).
Claim 30
Dependent Claim
28 words
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.
Claim 31
Dependent Claim
90 words
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.
Claim 32
Dependent Claim
58 words
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.
References Cited (Backward Citations)
US4965763A
Cited
US5371673A
Cited
US5434962A
Cited
US5619410A
Cited
US5384703A
Cited
US5873660A
Cited
US5845278A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-08-09 | 2003-02-08 | 2003-08-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-08-09 | 2007-02-08 | 2007-08-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-08-09 | 2011-02-08 | 2011-08-10 | $7700.00 | Window Closed / Lapsed |