US 5,594,641 A · Finite-state transduction of related word forms for text indexing and retrieval

Abstract

The present invention solves a number of problems in using stems (canonical indicators of word meanings) in full-text retrieval of natural language documents, and thus permits recall to be improved without sacrificing precision. It uses various arrangements of finite-state transducers to accurately encode a number of desirable ways of mapping back and forth between words and stems, taking into account both systematic aspects of a language's morphological rule system and also the word-by-word irregularities that also occur. The techniques described apply generally across the languages of the world and are not just limited to simple suffixing languages like English. Although the resulting transducers can have many states and transitions or arcs, they can be compacted by finite-state compression algorithms so that they can be used effectively in resource-limited applications. The invention contemplates the information retrieval system comprising the novel finite state transducer as a database and a processor for responding to user queries, for searching the database, and for outputting proper responses, if they exist, as well as the novel database used in such a system and methods for constructing the novel database.

Claims20

Dependent claims

A process of fabricating an FST stored upon a computer readable medium, the FST mapping surface forms to lexical forms of a language for use in text indexing and retrieval from documents in said language, the process comprising the steps of:

(a) constructing a first FST defining one or more rules of the language,
(b) constructing a second FST defining one or more other rules of the language,
(c) constructing a third FST derived from a list of identity stem-affix pairs of the language or defining one or more rules of the language other than the rules defined by the first and second FSTS, and
(d) computing simultaneously the composition of the third FST with the intersection of the first and second FSTs to produce a new single fourth FST that merges the first, second and third FSTs.

1 more element

A method for making a database stored upon a computer readable medium used with a computer for information retrieval or text indexing, the method comprising the steps:

(a) creating a morpheme lexicon comprising a first list of irregular word stem-variant pairs,
(b) creating a second list of linguistic rules governing the addition of affixes to word stems to form regular word variants of said stems,
(c) creating a first FST derived from the first list of the morpheme lexicon,
(d) creating a second FST derived from the second list of linguistic rules,
(e) said first and second FSTs each comprising a plurality of branches defining a plurality of FST paths from a single start state via transitions through a succession of intermediate states to different end states, each branch forming a complete path from the start state to the end state representing a string, each of said transitions representing an ordered pair comprising one character or null symbol in an upper string constituting a word stem and one character or null symbol in a lower string constituting a word variant of said word stem,
(f) combining the second FST with a third FST derived from a list of identity pairs of a language,
(g) merging the combined second and third FSTs with the first FST to produce a single FST that maps stems of words obeying the linguistic rules of step (b) to variants of said stems except where the word is an irregular word in the morpheme lexicon and is overridden by the contents of the first FST,
(h) storing the single FST produced in step (g) as part of the desired database.

5 more elements

Dependencies are inferred from the claim text.

Finite-state transduction of related word forms for text indexing and retrieval

Life of this patent

Finite-state transduction of related word forms for text indexing and retrieval

Life of this patent

Abstract

Claims20