US5594641A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Finite-state transduction of related word forms for text indexing and retrieval
Assignee: Xerox Corp
•
Filing: 1994-06-08
•
Granted: 1997-01-14
•
Expires: 2014-06-08
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 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.
Inventors
- 👤 Ronald M. Kaplan
- 👤 Lauri Karttunen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 19:03
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: 29
Claim 1
Independent Claim
138 words
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.
Claim 2
Dependent Claim
138 words
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.
Claim 3
Independent Claim
99 words
A method for making a database stored on a computer readable medium used by an information retrieval and text indexing application program executed on a computer system, the method comprising: constructing a first FST derived from identity pairs of a language representing allowable stems of the language; constructing a second FST representing regular rules of the language that map stems to their surface variants; and combining the first and second FSTs using intersecting composition to produce the database which is used by the application program to retrieve only allowable stems or variants based on given variants or stems, respectively.
Claim 4
Independent Claim
99 words
A method for making a database stored on a computer readable medium used by an information retrieval and text indexing application program executed on a computer system, the method comprising: constructing a first FST derived from identity pairs of a language representing allowable stems of the language; constructing a second FST representing regular rules of the language that map stems to their surface variants; and combining the first and second FSTs using intersecting composition to produce the database which is used by the application program to retrieve only allowable stems or variants based on given variants or stems, respectively.
Claim 5
Dependent Claim
22 words
The method of claim 2 further comprising combining the database with a third FST representing irregular word stem-variant pairs for the language.
Claim 6
Independent Claim
274 words
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.
Claim 7
Independent Claim
274 words
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.
Claim 8
Dependent Claim
58 words
The method of claim 4 wherein the step of merging the combined second and third FSTs with the first FST comprises computing an identity transducer for the complement of a domain of the first FST, precomposing the identity transducer with the combined second and third FSTs to produce a result, and unioning the result with the first FST.
Claim 9
Dependent Claim
29 words
The method of claim 4 wherein the step of combining the second FST with a third FST comprises combining the second and third FSTs using composition and intersecting algorithms.
Claim 10
Dependent Claim
30 words
The method of claim 4 further comprising creating a third list of stem-affix pairs and creating the third FST by mapping the stem-affix pairs in the third list into themselves.
Claim 11
Independent Claim
31 words
The method of normalizing text in a document, comprising: (a) constructing a normalizing FST, (b) inputting to the FST of step (a) a stream of characters derived from the document text.
Claim 12
Independent Claim
31 words
The method of normalizing text in a document, comprising: (a) constructing a normalizing FST, (b) inputting to the FST of step (a) a stream of characters derived from the document text.
Claim 13
Dependent Claim
37 words
The method of claim 8, further comprising: (c) composing the normalizing FST of step (a) with a stemming FST to produce a merged FST, (d) inputting the stream of characters to the merged FST of step (c).
Claim 14
Dependent Claim
96 words
A process of fabricating an FST stored on 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 or for other language processing applications, the process comprising the steps of: (a) constructing a first FST defining one or more rules of the language, (b) constructing a second FST mapping stems to lexical variants, (c) computing the composition of the second FST with the first FST to produce a new single third FST that merges the first and second FSTs.
Claim 15
Dependent Claim
96 words
A process of fabricating an FST stored on 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 or for other language processing applications, the process comprising the steps of: (a) constructing a first FST defining one or more rules of the language, (b) constructing a second FST mapping stems to lexical variants, (c) computing the composition of the second FST with the first FST to produce a new single third FST that merges the first and second FSTs.
Claim 16
Dependent Claim
51 words
The process of claim 10 wherein the step of constructing a first FST comprises constructing a first FST defining one or more normalization rules, wherein the lexical forms include parts-of-speech or affix tags, and wherein the third FST produced by the computing step maps unnormalized surface forms to the lexical forms.
Claim 17
Dependent Claim
130 words
A data structure stored on a computer readable medium accessed by an application program executed on a computer system, the data structure comprising a merged FST constructed by simultaneously composing a first FST with the intersection of second and third FSTs, each of said first, second and third FSTs representing a set of ordering string pairs, the ordered string pairs of the first FST comprising identity pairs of a language, the ordered string pairs of the second and third FSTs representing regular rules that map stems of said language to their surface variants, said data structure being usable used by the application program to retrieve stems or variants of the language when variants or stems, respectively, are given to and processed by the application program by traversing the merged FST.
Claim 18
Dependent Claim
130 words
A data structure stored on a computer readable medium accessed by an application program executed on a computer system, the data structure comprising a merged FST constructed by simultaneously composing a first FST with the intersection of second and third FSTs, each of said first, second and third FSTs representing a set of ordering string pairs, the ordered string pairs of the first FST comprising identity pairs of a language, the ordered string pairs of the second and third FSTs representing regular rules that map stems of said language to their surface variants, said data structure being usable used by the application program to retrieve stems or variants of the language when variants or stems, respectively, are given to and processed by the application program by traversing the merged FST.
Claim 19
Dependent Claim
136 words
A data structure stored on a computer readable medium accessed by an application program executed on a computer system, the data structure comprising a merged FST constructed by simultaneously composing a first FST with the intersection of second and third FSTs, each of said first, second and third FSTs representing a set of ordering string pairs, the ordered string pairs of the first FST comprising identity pairs of a language, the ordered string pairs of the second and third FSTs representing regular rules that map lexical forms consisting of stems and morphological tags of said language to their surface variants, said data structure being usable by the application program to retrieve stems or variants of the language when variants or stems, respectively, are given to and processed by the application program by traversing the merged FST.
Claim 20
Dependent Claim
136 words
A data structure stored on a computer readable medium accessed by an application program executed on a computer system, the data structure comprising a merged FST constructed by simultaneously composing a first FST with the intersection of second and third FSTs, each of said first, second and third FSTs representing a set of ordering string pairs, the ordered string pairs of the first FST comprising identity pairs of a language, the ordered string pairs of the second and third FSTs representing regular rules that map lexical forms consisting of stems and morphological tags of said language to their surface variants, said data structure being usable by the application program to retrieve stems or variants of the language when variants or stems, respectively, are given to and processed by the application program by traversing the merged FST.
Claim 21
Dependent Claim
153 words
A data structure stored on a computer readable medium accessed by an application program executed on a computer system, the data structure comprising a merged FST comprising a merger of a first transducer derived from a finite list of irregular word pairs of a language and a second transducer derived from regular rules of the language, said first transducer having a domain, a complement of the domain, and an identity transducer for the complement of the domain, said merged FST being constructed by computing the identity transducer for the complement of the domain of the first transducer, precomposing the identity transducer with the second transducer to produce a result, and unioning the result with the first transducer, said data structure being usable by the application program to retrieve stems or variants of the language when variants or stems, respectively, are given to and processed by the application program by traversing the merged FST.
Claim 22
Dependent Claim
153 words
A data structure stored on a computer readable medium accessed by an application program executed on a computer system, the data structure comprising a merged FST comprising a merger of a first transducer derived from a finite list of irregular word pairs of a language and a second transducer derived from regular rules of the language, said first transducer having a domain, a complement of the domain, and an identity transducer for the complement of the domain, said merged FST being constructed by computing the identity transducer for the complement of the domain of the first transducer, precomposing the identity transducer with the second transducer to produce a result, and unioning the result with the first transducer, said data structure being usable by the application program to retrieve stems or variants of the language when variants or stems, respectively, are given to and processed by the application program by traversing the merged FST.
Claim 23
Dependent Claim
62 words
The data structure of claim 14 wherein the second transducer is derived by combining a third transducer comprising identity pairs of a language with a fourth transducer representing regular rules that map stems of said language to their surface variants, whereby said data structure is usable to retrieve only allowable stems or variants of said language when processing variants or stems, respectively.
Claim 24
Independent Claim
89 words
A method for making a single FST stored on a computer readable medium used by an information retrieval and text indexing application program executed on a computer system, the method comprising: constructing a first FST representing regular word stem-variant pairs for a language; constructing a second FST representing irregular word stem-variant pairs for the language; and combining the first and second FSTs to form the single FST used by the application program to retrieve a regular or irregular stem or variant based on a given variant or stem, respectively.
Claim 25
Independent Claim
89 words
A method for making a single FST stored on a computer readable medium used by an information retrieval and text indexing application program executed on a computer system, the method comprising: constructing a first FST representing regular word stem-variant pairs for a language; constructing a second FST representing irregular word stem-variant pairs for the language; and combining the first and second FSTs to form the single FST used by the application program to retrieve a regular or irregular stem or variant based on a given variant or stem, respectively.
Claim 26
Dependent Claim
29 words
The method of claim 16 wherein the step of constructing the first FST comprises constructing the first FST to be restricted to stems which are allowable in the language.
Claim 27
Dependent Claim
38 words
The method of claim 17 wherein the step of constructing the first FST comprises combining a third FST representing identity pairs of a language with a fourth FST representing regular rules that map stems to their surface variants.
Claim 28
Dependent Claim
20 words
The method of claim 18 wherein the step of combining comprises combining the third and fourth FSTs using intersecting composition.
Claim 29
Dependent Claim
50 words
The method of claim 16 wherein the step of combining comprises computing an identity transducer for a complement of a domain of the first FST, precomposing the identity transducer with the second FST to produce a result, and unioning the result with the first FST to provide the single FST.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-01-14 | 2000-07-15 | 2001-01-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-01-14 | 2004-07-15 | 2005-01-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-01-14 | 2008-07-15 | 2009-01-14 | $7700.00 | Window Closed / Lapsed |