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

Claim 2

A computerized information retrieval or text indexing device, comprising: (a) a database stored on a computer readable medium, said database comprising a data structure for representing stem-variant relations of a language, 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 valid word stem and the lower string of each pair is a valid word variant, said data structure being constructed such that 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 connected to the computer readable medium, in response to a user query 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 3

The device of claim 1, wherein the FST transducer comprises a merger of a first transducer derived from a finite list of irregular word pairs and a second transducer derived from regular linguistic rules and stems by computing the identity transducer for the complement of the domain of the first transducer, precomposing the identity transducer with the second transducer, and then unioning the result with the first transducer.

Claim 4

The device of claim 2, wherein the second transducer comprises a merger of a third transducer derived from a list of regular linguistic rules and a fourth transducer derived from a list of allowable stems of the language.

Claim 5

The device of claim 3, wherein the second transducer was produced using composition and intersecting algorithms to combine the third and fourth transducers.

Claim 6

The device of claim 1, further comprising means for backtracking through the found branch to where the stem begins to identify another stem of a word variant, and means for traversing the data structure FST searching for a complete path through a second branch of the FST having the same another stem and outputting the word variant represented by the second branch.

Claim 7

The device of claim 1, wherein the FST comprises branches of only stem/variant pairs.

Claim 8

The device of claim 1, wherein the FST incorporates systematic inflectional and derivational word alterations describable by linguistic rules, and wherein the FST incorporates compiled versions of said linguistic rules.

Claim 9

The device of claim 1, further comprising memory means, said database being stored in said memory means.

Claim 10

The device of claim 1, wherein the FST is compressed.

Claim 11

The device of claim 1, wherein the FST comprises a merger of a first transducer derived from a list of regular linguistic rules and a second transducer derived from a list of allowable stems of the language, the FST being produced using composition and intersecting algorithms to combine the first and second transducers.

Claim 12

A data structure stored on a computer readable medium used in a computerized device executing an information retrieval or text indexing application program, said data structure representing stem-variant relations of a language, said data structure comprising a single combined finite state transducer (FST), said FST comprising a plurality of branches defining a plurality of FST paths from a start state via transitions to different end states, each branch forming a 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 valid word stem and one character or null symbol in a lower string constituting a valid word variant of said word stem, said single FST comprising the merger of a first FST derived from a first list of irregular word stem-variant pairs constituting a morpheme lexicon and of a second FST derived from at least a second list of linguistic rules governing the addition of affixes to word stems to form regular word variants of said stems, said single FST 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, said data structure being constructed such that traversing a branch of the FST via the upper string of a pair will enable retrieval by the program of the lower string of the pair, or traversing a branch of the FST via the lower string of a pair will enable retrieval by the program of the upper string of the pair.

Claim 13

A data structure stored on a computer readable medium used in a computerized device executing an information retrieval or text indexing application program, said data structure representing stem-variant relations of a language, said data structure comprising a single combined finite state transducer (FST), said FST comprising a plurality of branches defining a plurality of FST paths from a start state via transitions to different end states, each branch forming a 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 valid word stem and one character or null symbol in a lower string constituting a valid word variant of said word stem, said single FST comprising the merger of a first FST derived from a first list of irregular word stem-variant pairs constituting a morpheme lexicon and of a second FST derived from at least a second list of linguistic rules governing the addition of affixes to word stems to form regular word variants of said stems, said single FST 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, said data structure being constructed such that traversing a branch of the FST via the upper string of a pair will enable retrieval by the program of the lower string of the pair, or traversing a branch of the FST via the lower string of a pair will enable retrieval by the program of the upper string of the pair.

Claim 14

The data structure of claim 11, wherein the second FST comprises a merger of a third FST derived frown the second list of linguistic rules and a fourth FST derived from a third list of allowable stems of the language.

Claim 15

The data structure of claim 12, wherein the second FST was produced by using composition and intersecting algorithms to combine the third and fourth FSTs.

Claim 16

The data structure of claim 11, wherein the merger was carried out by computing the identity transducer for the complement of the domain of the first FST, precomposing the identity transducer with the second FST, and then unioning the result with the first FST.

Claim 17

The data structure of claim 11, wherein the data structure is a compressed FST.

Claim 20

The method of claim 16 wherein, if a match is found, outputting the match or an identification of a document containing the match.

Claim 21

A computerized language processing device, comprising: (a) a database stored on a computer readable medium, said database comprising a data structure for representing stem-variant relations and variant-parts of speech-affix relations of a language, said data structure comprising a combined finite state transducer (FST) 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 a character of a valid word stem or a part-of-speech or affix tag, and the lower string of each pair is a character of a valid word variant or nul, said data structure being constructed such that 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 connected to the computer readable medium, in response to a user query 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 pair 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 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 22

A computerized language processing device, comprising: (a) a database stored on a computer readable medium, said database comprising a data structure for representing stem-variant relations and variant-parts of speech-affix relations of a language, said data structure comprising a combined finite state transducer (FST) 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 a character of a valid word stem or a part-of-speech or affix tag, and the lower string of each pair is a character of a valid word variant or nul, said data structure being constructed such that 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 connected to the computer readable medium, in response to a user query 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 pair 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 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 23

A data structure stored on a computer readable medium used in a computerized device executing a language processing application program, said data structure representing stem-variant relations and variant-parts of speech-affix relations as tags of a language, said data structure comprising a single combined finite state transducer (FST), said FST comprising a plurality of branches defining a plurality of FST paths from a single start state via transitions to different end states, each branch forming a path from the start state to the end state representing a string or a string and a tag, each of said transitions representing an ordered pair comprising one character or null symbol in an upper string constituting a valid word stem or a label representing a part-of-speech or affix relation and one character or null symbol in a lower string constituting a valid word variant of said word stem, said single FST comprising the merger of a first FST derived from a first list of irregular word stem-variant pairs constituting a morpheme lexicon and of a second FST derived from at least a second list of linguistic rules, said data structure being constructed such that traversing a branch of the FST via the upper string of a pair will enable retrieval by the program of the lower string of the pair, or traversing a branch of the FST via the lower string of a pair will enable retrieval by the program of the upper string of the pair or the upper string with the tag.

Claim 24

A data structure stored on a computer readable medium used in a computerized device executing a language processing application program, said data structure representing stem-variant relations and variant-parts of speech-affix relations as tags of a language, said data structure comprising a single combined finite state transducer (FST), said FST comprising a plurality of branches defining a plurality of FST paths from a single start state via transitions to different end states, each branch forming a path from the start state to the end state representing a string or a string and a tag, each of said transitions representing an ordered pair comprising one character or null symbol in an upper string constituting a valid word stem or a label representing a part-of-speech or affix relation and one character or null symbol in a lower string constituting a valid word variant of said word stem, said single FST comprising the merger of a first FST derived from a first list of irregular word stem-variant pairs constituting a morpheme lexicon and of a second FST derived from at least a second list of linguistic rules, said data structure being constructed such that traversing a branch of the FST via the upper string of a pair will enable retrieval by the program of the lower string of the pair, or traversing a branch of the FST via the lower string of a pair will enable retrieval by the program of the upper string of the pair or the upper string with the tag.

Claim 25

The data structure claim 19, wherein the second FST comprises a merger of a third FST derived from the second list of linguistic rules and a fourth FST derived from a third list of allowable stems of the language.

Claim 26

The data structure of claim 20, wherein the second FST was produced by using composition and intersecting algorithms to combine the third and fourth FSTs.

Claim 29

The method of claim 22 wherein, if a match is found, outputting the match or an identification of a document containing the match.

Claim 30

A computerized language processing device, comprising: (a) a database stored on a computer readable medium, said database comprising a data structure for representing stem-variant relations and variant-parts of speech-affix relations of a language, 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 a character of a valid word stem or a part-of-speech or affix tag or null, and the lower string of each pair is a character of a valid 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, said data structure being constructed such that 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 computer readable medium, 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 31

A computerized language processing device, comprising: (a) a database stored on a computer readable medium, said database comprising a data structure for representing stem-variant relations and variant-parts of speech-affix relations of a language, 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 a character of a valid word stem or a part-of-speech or affix tag or null, and the lower string of each pair is a character of a valid 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, said data structure being constructed such that 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 computer readable medium, 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.