EP0583083A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Finite-state transduction of related word forms for text indexing and retrieval
Assignee: Xerox Corp
•
Filing: 1993-07-19
•
Granted: —
•
Expires: 2013-07-19
Abstract
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 (FSTs) 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 merged FST (70) may be produced by simultaneously intersecting (&) and composing (o) a lexicon transducer (65) and a number of rule transducers (61-63). Although the resulting FSTs 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 FST (70) 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.
Inventors
- 👤 Douglass R. Cutting
- 👤 Per-Kristian G. Halvorsen
- 👤 Ronald M. Kaplan
- 👤 Lauri Karttunen
- 👤 Martin Kay
- 👤 Jan O. Pedersen
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-02 07:24
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/33; G06F16/3331; G06F16/3332; G06F16/3338; G06F16/31; G06F16/313; G06F16/3334; G06F16/3335; G06F16/334; G06F16/3344; G06F16/90; G06F16/903; G06F16/90335; G06F16/90344; G06F16/90348; Y; Y10; Y10S; Y10S707/00; Y10S707/99931
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
234 words
A computerized information retrieval or text indexing device, comprising: (a) a database (31), said database comprising a data structure for representing stem-variant relations, said data structure comprising a finite state transducer (FST) encoding along a plurality of branches sets of ordered-pairs of upper and lower strings wherein the upper string of each pair is a word stem (arrive) and the lower string of each pair is a word variant (arriving), whereby traversing a branch of the FST via the upper string of a pair will enable retrieval of the lower string of the pair, or traversing a branch of the FST via the lower string of a pair will enable retrieval of the upper string of the pair, (b) processing means (32) connected to the database, in response to a user query (34) inputting a word incorporating a stem or a variant, for traversing the data structure FST searching for a complete path through an FST branch having a lower string matching the query word, said processing means further comprising means in response to finding a complete path through a branch for outputting the upper string stem represented by that branch and corresponding to the query word or an identification of a document containing the same, or for outputting another word variant represented by that branch and having the same stem as the query word or an identification of a document containing the same.
Claim 2
Dependent Claim
283 words
For use in a computerized information retrieval or text indexing device, memory means (31), a database stored in said memory means, said database comprising a data structure (FST) for representing stem-variant relations, said data structure comprising a single combined finite state transducer (FST) (70), said FST comprising a plurality of branches defining a plurality of FST paths from a single start state (s) via transitions through a succession of intermediate states (o) to different end states, each branch forming a complete path from the start state (s) to the end state representing a string, each of said transitions representing an ordered pair comprising one character (a,r,i,v,e) or null symbol (ε) in an upper string constituting a word stem and one character (a,r,i,v,n,g) or null ε symbol in a lower string constituting a word variant (arriving) of said word stem (arrive), said single FST (70) comprising the merger of a first FST (65) derived from a first list of irregular word stem-variant pairs constituting a morpheme lexicon and of a second FST (61-63) derived from a second list of linguistic rules governing the addition of affixes to word stems (arrive) to form regular word variants (arriving) of said stems, said single FST (70) being adapted for mapping stems of words obeying the linguistic rules to variants of said stems except where the word is an irregular word in the morpheme lexicon and is overridden by the latter, wherein traversing a branch of the FST via the upper string of a pair enables retrieval of the lower string of the pair, or traversing a branch of the FST via the lower string of a pair will enable retrieval of the upper string of the pair.
Claim 3
Dependent Claim
22 words
A merged FST constructed by simultaneously composing a first FST (65) with the intersection (64) of second (61) and third (62) FSTs.
Claim 4
Dependent Claim
35 words
A merged FST constructed by computing the identity transducer (90) for the complement of the domain of a first FST (70), precomposing with a second FST, and then unioning the result with the first FST.
Claim 5
Dependent Claim
33 words
A finite state transducer (95) comprising means in response to the inputting of a stream of characters (91) for outputting normalized text (97) comprising individual words in lowercase free of extraneous punctuation marks.
Claim 6
Dependent Claim
254 words
A computerized language processing device, comprising: (a) a database, said database comprising a data structure for representing stem-variant relations and variant-parts of speech-affix relations, said data structure comprising a combined finite state transducer (FST) encoding along a plurality of branches sets of ordered-pairs of upper (a,r,i,v,e) and lower (a,r,i,v,n,g) labels and parts-of-speech or affix tag (PresPart, Verb) labels wherein the upper string of each pair is a character of a word stem or a part-of-speech or affix tag (PresPart, Verb), and the lower string of each pair is a character of a word variant or nul, whereby traversing a branch of the FST via the upper pair will enable retrieval of the lower pair, or traversing a branch of the FST via the lower pair will enable retrieval of the upper pair, (b) processing means (32) connected to the database, in response to a user query inputting a word incorporating a stem (arrive) or a variant (arriving), for traversing the data structure FST searching for a complete path through an FST branch having a lower pair matching the query word, said processing means (32) further comprising means in response to finding a complete path through a branch for outputting the upper string stem or part-of-speech (PresPart, Verb) represented by that branch and corresponding to the query word or an identification of a document containing the same, or for outputting another word variant represented by that branch and having the same stem as the query word or an identification of a document containing the same.
Claim 7
Dependent Claim
255 words
For use in a computerized language processing device, memory means (31), a database stored in said memory means, said database comprising a data structure for representing stem-variant relations and variant-parts of speech-affix relations as tags, said data structure comprising a single combined finite state transducer (FST), said FST (70) comprising a plurality of branches defining a plurality of FST paths from a single start state (s) via transitions through a succession of intermediate states (o) to different end states, each branch forming a complete path from the start state (s) to the end state representing a string or a string and a tag, each of said transitions representing an ordered pair comprising one character (a,r,i,v,e) or null symbol (ε) in an upper string constituting a word stem (arrive) or a label (PresPart, Verb) representing a part-of-speech or affix relation and one character (a,r,i,v,n,g) or null symbol (ε) in a lower string constituting a word variant (arriving) of said word stem, said single FST (70) comprising the merger of a first FST (65) derived from a first list of irregular word stem-variant pairs constituting a morpheme lexicon and of a second FST (61-63) derived from a second list of linguistic rules, whereby traversing a branch of the FST via the upper string of a pair will enable retrieval of the lower string of the pair, or traversing a branch of the FST via the lower string of a pair will enable retrieval of the upper string of the pair or the upper string with the tag.
Claim 8
Dependent Claim
314 words
A computerized language processing device, comprising: (a) a database, said database comprising a data structure for representing stem-variant relations and variant-parts of speech-affix relations, said data structure comprising a combined finite state machine (FSM) converted from finite state transducers (FST) each encoding along a plurality of branches sets of ordered pairs of upper and lower labels and parts-of-speech or affix tags label wherein the upper string of each pair is character of a word-stem or a part-of-speech or affix tag or null, and the lower string of each pair is a character of a word variant or null, each of said FST transitions from an original to a destination state being replaced in the FSM with an odd-numbered transition labelled to represent the upper string label or tag or null to a new state followed by an even-numbered transition labelled to represent the lower string character or null from the new state to the destination state whereby traversing a branch of the FSM via the odd-numbered transition will enable retrieval of the lower string character, or traversing a branch of the FSM via the even-numbered transition will enable retrieval of the upper string label or tag, (b) processing means connected to the database, in response to a user query inputting a word incorporating a stem or a variant, for traversing the data structure FSM searching for a complete path through an FSM branch having a lower character matching that of the query word, said processing means further comprising means in response to finding a complete path through a branch for outputting the upper string stem or part-of-speech represented by that branch and corresponding to the query word or an identification of a document containing the same, or for outputting another word variant represented by that branch and having the same stem as the query word or an identification of a document containing the same
Claim 9
Independent Claim
260 words
A method for making a database to be used with a computer for information retrieval or text indexing, 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 (65) derived from the first list of the morpheme lexicon, (d) creating a second FST (61-63) 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 (s) via transitions through a succession of intermediate states (o) to different end states, each branch forming a complete path from the ordered pair comprising one character (a,r,i,v,e) or null symbol (ε) in an upper string constituting a word stem (arrive) and one character (a,r,i,v,n,g) or null symbol (ε) in a lower string constituting a word variant (arriving) of said word stem, (f) compiling the first (65) and second (61-63) FSTs using composition and intersecting algorithms to combine the FSTs, (g) merging the compiled first and second FSTs to produce a single FST (70) 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 (70) produced in step (g) as part of the desired database.
Claim 10
Dependent Claim
122 words
In the process of fabricating an FST that maps surface forms to lexical forms of a language for use in text indexing and retrieval from documents in said language, the steps of: (a) constructing a first FST (61) defining one or more rules of the language, (b) constructing a second FST (62) defining one or more other rules of the language, (c) constructing a third FST (65) mapping irregular language words to their stems or defining one or more still other rules of the language, (d) computing simultaneously the composition of the third FST (65) with the intersection of the first (61) and second (62) FSTs to produce a new single fourth FST (70) that merges the first, second and third FSTs.
Claim 11
Independent Claim
144 words
A method of using a database for a language for word indexing and retrieval from words in that language stored in the database with the aid of a FST (70) that maps the surface form (arriving) of words for the language to its lexical stem(s) (arrive), comprising the steps of: (a) inputting a query (34) containing a word in the language requesting identification of any related words in the database or of a document containing such words, (b) operating the FST upward to obtain the query word's stem(s) and then scanning the database looking for words with a matching stem, or (c) operating the FST upwards to obtain the query word's lexical stem(s), then operating the FST downward with the lexical stem(s) to generate all variants of the lexical stem(s) and then scanning the database with each of the variants searching for a match.
Claim 12
Independent Claim
33 words
The method of normalizing text in a document, comprising: (a) constructing a normalizing FST (90), (b) inputting to the FST of step (a) a stream of characters (91) derived from the document text.
Claim 13
Dependent Claim
103 words
In the process of fabricating an FST that maps surface forms (arriving) to lexical forms (arrive) of a language for use in text indexing and retrieval from documents in said language or for other language processing applications, the steps of: (a) constructing a first FST (61-63) defining one or more rules of the language, (b) constructing a second FST (65) mapping surface forms to lexical forms wherein the lexical forms include parts-of-speech or affix tags, (c) computing the composition of the second FST (65)with the first FST (61-63) to produce a new single third FST (70) that merges the first and second FSTs.
Claim 14
Independent Claim
163 words
A method of using a database in a language for word indexing and retrieval from documents in that language or for other language processing applications with the aid of a FST that maps the surface form of words in the language to lexical counterpart forms, comprising the steps of: (a) inputting a query containing a word in the language requesting identification of any related words in the database or of a document containing such words or of the query word's part of speech, (b) operating the FST upward to obtain the query word's stem and then scanning the database looking for a matching stem, or (c) operating the FST upwards to obtain the query word's lexical counterpart, then operating the FST downward with the lexical counterpart to generate all variants of the lexical counterpart and then scanning the database with each of the variants searching for a match, or (d) operating the FST upward to obtain an identification of the query word's part-of-speech.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.