Text indexing system

• US 5,708,829 A
• Filed: 09/25/1996
• Issued: 01/13/1998
• Est. Priority Date: 02/01/1991
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Wang Laboratories Incorporated
• Inventors: Kadashevich, A. Julie, Harvey, Mary F., Clark, Cheryl
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): Tkacs, Stephen R.
• Application Number:
  US08/721,775
• Time in Patent Office: 475 Days
• Field of Search: 395/751, 395/759, 395/760, 395/761, 395/792, 395/793, 395/794, 395/10, 395/50, 395/60
• US Class Current: 715/236
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms

Abstract

An apparatus for generating an index for a collection of words, the apparatus including means for selecting an input word from the collection of words; means for generating words that are lexically related to the input word, wherein the input word and the lexically related words form a group of words; and an indexing engine for representing the occurrence in the collection of words of any of the members of the group by a single member of the group.

Claims

1. An apparatus for generating an index for a collection of words, the apparatus comprising:

means for selecting an input word from said collection of words;

means for generating words that are lexically related to said input word wherein a word that is lexically related to said input word is a word having a meaning related to a meaning of said input word, and wherein said input word and said lexically related words form a group of words having related meanings,

said means for generating words that are lexically related to said input word comprising a recognition engine including

a means for identifying the underlying lexical form of the input word, the underlying lexical form of the input word being comprised of the lexical morphemes forming the input word,

a means for scanning the lexical form of the input word for finding at least one lexical stem within the lexical morphemes forming said lexical form of the input word wherein a lexical stem of a word has a meaning related to the meaning of the input word, and

a means for identifying suffixes attached to said lexical stem, wherein said suffixes include ending suffixes and continuation suffixes and said stem finding means and suffix identifying means cooperate to conduct morphological analysis of the input word from the root to the affix and wherein said recognition engine performs inflectional and derivational analysis, wherein each derivational analysis is performed recursively using more than two derivational suffixes within each said input word; and

an indexing engine for representing the occurrence in said collection of words of any of the members of said group by a single member of said group.

2. The apparatus of claim 1 wherein said recognition engine returns a base history for said input word, said base history identifying one or more base words for said input word, each of said one or more base words representing the input word with one or more suffixes removed.

3. The apparatus of claim 2 wherein said group comprises at least some of said one or more base words.

4. An apparatus for generating a plurality of topic words from a collection of words having certain informational content, said apparatus comprising:

means for selecting a subset of words from said collection of words;

a morphological analyzer for generating morphological information about each of the words in said subset of words;

said morphological analyzer including a recognition engine including

a means for identifying the underlying lexical form of each of the words, the underlying lexical form of each of the words being comprised of the lexical morphemes forming the word,

a means for scanning the lexical form of each word for finding at least one lexical stem within lexical morphemes forming the lexical form of each of said words wherein each lexical stem has a meaning related to the meaning of each of said words, the scanning means scanning each of said words from the start of the lexical form of the character strings of each of said words, choosing successively longer sequences of characters, and, for each said sequence of characters, determining whether the remaining characters of each of said words contain one or more suffixes, and

a means for identifying suffixes attached to each said lexical stem, wherein said suffixes include ending suffixes and continuation suffixes and said stem finding means and suffix identifying means cooperate to conduct morphological analysis of the input word from the root to the affix and wherein said recognition engine performs inflectional and derivational analysis, wherein each derivational analysis is performed recursively using more than two derivational suffixes within each said input word;

means for evaluating whether a given word of said subset of words conveys information about the content of said collection of words, said evaluation means basing its determination upon the morphological information generated by said morphological analyzer; and

means for generating a topic word corresponding to said given word, if said evaluation means determines that said given word conveys information about the content of said collection of words.

5. The apparatus of claim 4 wherein said collection of words is text.

6. The apparatus of claim 4 wherein said means for selecting comprises a stop list containing words which do not qualify as topic words, wherein said selecting means excludes from said subset those words from said collection of words that fall within said stop list.

7. The apparatus of claim 4 wherein said means for selecting comprises a keep list containing words which automatically qualify as topic words, and wherein said selecting means includes in said subset those words from said collection of words that fall within said keep list.

8. The apparatus of claim 4 further comprising an indexing engine, wherein said indexing engine uses the topic word generated for said given word to create an index for said collection of words.

9. The apparatus of claim 4 wherein said recognition engine recognizes one or more successful parses of said given word, wherein a successful parse exists when said recognition engine is able to decompose the given word into an underlying stem and a sequence of one or more suffixes which when added to said underlying stem form said given word.

10. The apparatus of claim 9 wherein said recognition engine generates a morphological history for each successful parse of said given word.

11. The apparatus of claim 10 wherein the morphological history for a successful parse identifies a part of speech for said given word, one or more base words associated within the given word and a part of speech for each of said one or more base words.

12. The apparatus of claim 11 wherein said evaluating means evaluates whether the given word conveys information about the content of said collection of words based upon the number of successful parses of said given word.

13. The apparatus of claim 11 wherein said evaluating means evaluates whether the given word conveys information about the content of said collection of words based upon the one or more parts of speech identified for the given word.

14. The apparatus of claim 11 wherein said topic word generating means selects as said topic word either said given word or one of the base words identified within a morphological history associated with a successful parse of said given word.

15. A method for generating an index for a collection of words, the method comprising:

selecting an input word from said collection of words;

generating words that are lexically related to said input word wherein a word that is lexically related to said input word is a word having a meaning related to a meaning of said input word, and wherein said input word and said lexically related words form a group of lexically related words by

identifying the underlying lexical form of the input word, the underlying lexical form of the input word being comprised of the lexical morphemes forming the input word, scanning the lexical form of the input word for finding at least one lexical stem within the lexical morphemes forming said lexical form of said input word wherein each lexical stem has a meaning related to the meaning of the input word, and

identifying suffixes attached to said lexical stem, wherein said suffixes include ending suffixes and continuation suffixes and said stem finding and suffix identifying are performed cooperatively to conduct a morphological analysis of the input word from the root to the affix and performing inflectional and derivational analysis, wherein each deftrational analysis is performed recursively using more than two derivational suffixes within each said input word; and

representing the occurrence in said collection of words of any of the members of said group by a single member of said group.

16. A method for generating a plurality of topic words from a collection of words having certain information content, said method comprising:

selecting a subset of words from said collection of words;

using a morphological analyzer to generate morphological information about each of the words in said subset of words;

by

finding a lexical stem among the lexical morphemes within a word of each of said words, and

identifying suffixes attached to said lexical stem, wherein said lexical stem finding and suffix identifying are performed cooperatively to conduct a morphological analysis of the input word from the root to the affix by scanning each said word from the start of the lexical form of the character strings of each said word, choosing successively longer sequences of characters, and, for each said sequence of characters, determining whether the remaining characters of each said word contains one or more suffixes, and

performing inflectional and derivational analysis, wherein each derivational analysis is performed recursively using more than two derivational suffixes within each said input word; and

evaluating whether a given word of said subset of words conveys information about the content of said collection of words, said evaluating step basing its determination upon the morphological information generated by said morphological analyzer; and

generating a topic word corresponding to said given word, if said evaluating step determines that said given word conveys information about the content of said collection of words.