Methods and apparatus for information indexing and retrieval as well as query expansion using morpho-syntactic analysis

• US 6,101,492 A
• Filed: 07/02/1998
• Issued: 08/08/2000
• Est. Priority Date: 07/02/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Tzoukermann, Evelyne, Jacquemin, Christian
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/109,506
• Time in Patent Office: 768 Days
• Field of Search: 707/3, 707/5, 704/1, 704/4, 706/46, 706/47, 706/11, 716/6
• US Class Current: 707/688
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

An index generator and query expander for use in information retrieval in a corpus. A corpus is provided as an input to an inflectional analyzer, which produces a lemmatized corpus having base forms and associated inflections for each word in the original corpus. The lemmatized corpus is provided as an input to a disambiguator, which performs part of speech tagging and morpho-syntactic disambiguation to produce a disambiguated corpus. The disambiguated corpus is provided as an input to a derivational generator, which produces an expanded corpus having all possible valid derivatives of each word of the disambiguated corpus. The disambiguated corpus is provided as an input to a transformational analyzer, using a grammar and a metagrammar for analyzing syntactic and morphosyntactic variations to conflate and generate variants, producing an index to the corpus having a minimum of variants. Alternatively, a query expander is provided utilizing similar techniques.

Claims

1. An index generator for generation of an index for information retrieval for a corpus, comprising:

an inflectional analyzer for receiving a corpus as an input, the inflectional analyzer producing a lemmatized corpus having an identified base form and associated inflection for each word of the corpus;

a disambiguator for receiving the lemmatized corpus as an input, the disambiguator applying syntactic knowledge to disambiguate identified multiple inflected base forms in the lemmatized corpus representing the same word in the original corpus to produce a disambiguated corpus;

a derivational generator for receiving the disambiguated corpus as an input and produce an expanded corpus including all possible derivations for each word in the disambiguated corpus; and

a transformational analyzer for receiving the expanded corpus as an input and applying a grammar and a metagrammar to the expanded corpus to conflate term variants in the expanded corpus, the transformational analyzer producing an index to the corpus, the index having a minimum number of variants.

2. The index generator of claim 1, wherein the inflectional analyzer includes a finite-state morphological transducer and a lexicon containing all possible transitions between base and inflected forms, the morphological transducer employing morphological information contained in the lexicon to analyze the corpus in producing the lemmatized corpus.

3. The index generator of claim 2, wherein the disambiguator includes a part of speech tagger to tag each word in the lemmatized corpus with its part of speech.

4. The index generator of claim 3, wherein the disambiguator further includes a linguistic knowledge base to provide linguistic knowledge to the tagger to determine which tag to apply to a word of the lemmatized corpus.

5. The index generator of claim 4, wherein the disambiguator further includes a statistical knowledge base to supply statistically determined part of speech information to the tagger for use by the tagger in determining which tag to apply.

6. The index generator of claim 5, wherein the statistical knowledge base is generated by operation on a restricted training corpus to generate statistical knowledge about the words of the corpus for storage in the statistical knowledge base.

7. The index generator of claim 6, wherein the derivational generator includes a set of transducers for producing derivatives of each word of the disambiguated corpus.

8. The index generator of claim 7, wherein the set of transducers includes a prefix transducer, a stem transducer, a derivational suffix transducer, and an inflectional suffix transducer.

9. The index generator of claim 8, wherein the derivational generator also includes a database of stored productive suffixes.

10. The index generator of claim 9, wherein the derivational generator also includes a list of lemmas and derivational suffixes.

11. The index generator of claim 10, wherein the derivational generator also includes a dictionary against which the derivatives produced by the set of transducers are filtered, the derivational generator accepting derivatives appearing in the dictionary.

12. The index generator of claim 11, wherein the derivational generator filters derivatives not appearing in the dictionary against the disambiguated corpus, the derivational generator accepting derivatives appearing in the disambiguated corpus.

13. The index generator of claim 12, wherein the metagrammar includes a first section for analyzing type 1 variants and a second section for analyzing type 2 variants.

14. The index generator of claim 13, wherein the first section analyzes syntactic variations between original terms and variants.

15. The index generator of claim 14, wherein the second section analyzes syntactic and morphological variations between original terms and variants.

16. A method for generating an index for information retrieval from a corpus, comprising the steps of:

performing inflectional analysis on the corpus to identify all associated combinations of base form and inflection for each word of the corpus to produce a lemmatized corpus showing relationships between each word of the corpus and associated combinations of base forms and inflections;

performing disambiguation on the lemmatized corpus applying syntactic knowledge to disambiguate identified multiple inflected base forms in the lemmatized corpus representing the same word in the original corpus to produce a disambiguated corpus;

performing derivational generation on the disambiguated corpus to produce an expanded corpus containing all derivatives which can be produced from each combination of base form and inflection in the lemmatized corpus; and

performing transformational analysis on the expanded corpus using a grammar and a metagrammar to extract variants of terms in the expanded corpus, producing an index with a minimum of term variants.

17. The method of claim 16 wherein the step of inflectional analysis includes morphological analysis to determine relationships between base and inflected forms.

18. The method of claim 17 wherein the step of disambiguation includes tagging each combination of base form and inflection to indicate its part of speech and performing syntactic analysis to identify the combination of base form and inflection having the same part of speech as the corresponding word in the lemmatized corpus.

19. The method of claim 18, wherein the step of derivational generation further includes filtering candidate words against a dictionary and placing in the expanded corpus candidate words which appear in the dictionary.

20. The method of claim 19, wherein the step of derivational generation further includes filtering candidate words which do not appear in the dictionary against the disambiguated corpus, and placing in the expanded corpus candidate words which appear in the disambiguated corpus.

21. The method of claim 20, wherein the metagrammar includes type 1 variant metarules extract syntactic transformations which have contributed to the generation of the variant and type 2 variant metarules extract syntactic and morphological transformations which have contributed to the generation of the variant.

22. A query expander for expansion of a query for information retrieval from a corpus, comprising:

an inflectional analyzer for receiving a query as an input, the inflectional analyzer producing an inflected query having an identified base form and associated inflection for each word of the query;

a disambiguator for receiving the inflected query as an input, the disambiguator applying syntactic knowledge to disambiguate identified multiple inflected base forms in the inflected query representing the same word in the original query to produce a disambiguated query; and

a derivational generator for receiving the disambiguated query as an input and producing an expanded query including all possible derivations for each word in the disambiguated query.

23. The query expander of claim 22, wherein the inflectional analyzer includes a finite-state morphological transducer and a lexicon containing all possible transitions between base and inflected forms, the morphological transducer employing morphological information contained in the lexicon to analyze the query in producing the inflected query.

24. The query expander of claim 23, wherein the disambiguator includes a part of speech tagger to tag each word in the inflected query with its part of speech.

25. The query expander of claim 24, wherein the disambiguator further includes a linguistic knowledge base to provide linguistic knowledge to the tagger to determine which tag to apply to a word of the inflected query.

26. The query expander of claim 25, wherein the disambiguator further includes a statistical knowledge base to supply statistically determined part of speech information to the tagger for use by the tagger in determining which tag to apply.

27. The query expander of claim 26, wherein the statistical knowledge base is generated by operation on a restricted training corpus to generate statistical knowledge about the words of the training corpus for storage in the statistical knowledge base.

28. The query expander of claim 27, wherein the derivational generator includes a set of transducers for producing derivatives of each word of the disambiguated query.

29. The query expander of claim 28, wherein the set of transducers includes a prefix transducer, a stem transducer, a derivational suffix transducer, and an inflectional suffix transducer.

30. The query expander of claim 29, wherein the derivational generator also includes a database of stored productive suffixes.

31. The query expander of claim 30, wherein the derivational generator also includes a list of lemmas and derivational suffixes.

32. The query expander of claim 31, wherein the derivational generator also includes a dictionary against which the derivatives produced by the set of transducers are filtered, the derivational generator accepting derivatives appearing in the dictionary.

33. The query expander of claim 32, wherein the derivational generator filters derivatives not appearing in the dictionary against the disambiguated query, the derivational generator accepting derivatives appearing in the disambiguated query.

34. A method for expanding a query for use in information retrieval from a corpus, comprising the steps of:

performing inflectional analysis on the query to identify all associated combinations of base form and inflection for each word of the query to produce an inflected query showing relationships between each word of the query and associated combinations of base forms and inflections;

performing disambiguation on the inflected query applying syntactic knowledge to disambiguate identified multiple inflected base forms in the inflected query representing the same word in the original query to produce a disambiguated query; and

performing derivational generation on the disambiguated query to produce an expanded query containing all derivatives which can be produced from each combination of base form and inflection in the inflected query.

35. The method of claim 34 wherein the step of inflectional analysis includes morphological analysis to determine relationships between base and inflected forms.

36. The method of claim 35 wherein the step of disambiguation includes tagging each combination of base form and inflection to indicate its part of speech and performing syntactic analysis to identify the combination of base form and inflection having the same part of speech as the corresponding word in the inflected query.

37. The method of claim 36, wherein the step of derivational generation further includes filtering candidate words against a dictionary and placing in the expanded query candidate words which appear in the dictionary.

38. The method of claim 37, wherein the step of derivational generation further includes filtering candidate words which do not appear in the dictionary against the disambiguated query, and placing in the expanded query candidate words which appear in the disambiguated query.