US6424983B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Spelling and grammar checking system
Assignee: Global Information Res and Tech LLC
•
Filing: 1998-05-26
•
Granted: 2002-07-23
•
Expires: 2018-05-26
Abstract
Abstract A system of correcting misspelled words in input text detects a misspelled word in the input text, determines a list of alternative words for the misspelled word, and ranks the list of alternative words based on a context of the input text. The system then selects one of the alternative words from the list, and replaces the misspelled word in the text with the selected one of the alternative words. In certain embodiments of the invention finite state machines are utilized in the spelling and grammar correction process. Thus according to certain embodiments the invention stores one or more lexicon finite state machines (FSM), each of which represents a set of correctly spelled reference words. Storing the lexicon as one or more finite state machines facilitates those embodiments of the invention employing a client-server architecture. The input text to be corrected may also be encoded as a finite state machine, which includes alternative word(s) for word(s) in need of correction along with associated weights. The weights are determined by a process that involves assessing the number and type of changes that would be required in order to transform an incorrect word, e.g., a misspelled word, into a correct word. The invention adjusts the weights by taking into account the grammatical context in which the word appears in the input text. In certain embodiments of the invention the modification is performed by applying a second finite state machine to the finite state machine that was generated for the input text, where the second finite state machine encodes a grammatically correct sequence of words, thereby generating an additional finite state machine.
Inventors
- 👤 Yves Schabes
- 👤 Emmanuel Roche
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 18:55
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/232; G06F40/253; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935
Claims Analysis
Total Claims: 48
Claim 1
Independent Claim
171 words
A method of correcting a misspelled word in input text, the method comprising steps of: storing one or more lexicon finite state machines (FSM), each of the lexicon FSMs representing plural reference words, wherein a representation of a reference word comprises one or more states and one or more arcs, each arc comprising a character in the reference word; detecting a misspelled word in the input text, wherein the detecting comprises comparing each word in the input text to a dictionary database and characterizing a word as misspelled when the word does not match any words in the dictionary database; generating an additional FSM comprising a plurality of states, each state including information identifying a state of a lexicon FSM and a position in the input word and a cost, wherein the cost is used to select states of the additional FSM that are to be expanded; and determining a list of alternative words for the misspelled word, wherein the determining comprises selecting one or more words from the additional FSM.
Claim 2
Independent Claim
171 words
A method of correcting a misspelled word in input text, the method comprising steps of: storing one or more lexicon finite state machines (FSM), each of the lexicon FSMs representing plural reference words, wherein a representation of a reference word comprises one or more states and one or more arcs, each arc comprising a character in the reference word; detecting a misspelled word in the input text, wherein the detecting comprises comparing each word in the input text to a dictionary database and characterizing a word as misspelled when the word does not match any words in the dictionary database; generating an additional FSM comprising a plurality of states, each state including information identifying a state of a lexicon FSM and a position in the input word and a cost, wherein the cost is used to select states of the additional FSM that are to be expanded; and determining a list of alternative words for the misspelled word, wherein the determining comprises selecting one or more words from the additional FSM.
Claim 3
Dependent Claim
30 words
The method of claim 1 , wherein the list of alternative words comprises words that correspond to a path from an initial to a final state of the additional FSM.
Claim 4
Dependent Claim
67 words
The method of claim 2 , wherein a word or portion thereof corresponding to a current state in the additional FSM is obtained by making a series of character modifications to an input word or portion thereof, wherein each of the character modifications is associated with a predetermined value, and wherein the cost reflects a combination of the predetermined values associated with the series of character modifications.
Claim 5
Dependent Claim
44 words
The method of claim 3 , wherein the character modifications comprise one or more character modifications selected from the list consisting of: a character replacement, a character insertion, a character deletion, a character transposition, and replacement of a character by a phonetically equivalent character.
Claim 6
Dependent Claim
32 words
The method of claim 1 , wherein the cost is an indication of the likelihood that a current state is on a path leading to a correct spelling of the misspelled word.
Claim 7
Dependent Claim
17 words
The method of claim 1 , further comprising the step of: ranking the list of alternative words.
Claim 8
Dependent Claim
29 words
The method of claim 6 , further comprising the step of: selecting one of the alternative words as a correct spelling for the misspelled word based on the ranking.
Claim 9
Dependent Claim
52 words
The method of claim 1 , 2 , 5 , or 3 , wherein each of the alternative words corresponds to a final state of the additional FSM, further including the step of: ranking the list of alternative words based on the costs of the final states corresponding to the alternative words.
Claim 10
Dependent Claim
23 words
The method of claim 1 , wherein the states further include information indicating whether a character transposition has occurred in the input word.
Claim 11
Dependent Claim
288 words
The method of claim 1 , wherein the generating step comprises applying one or more states of the additional FSM to one or more modules selected from the list consisting of: (i) a character identity module, (ii) a phonetic identity module, (iii) a character insertion module, (iv) a character deletion module, (v) a character replacement module, (vi) a character transposition module, and (vii) a character transposition completion module, wherein (i) the character identity module determines whether characters of a reference word in the lexicon FSM match characters of the misspelled word, (ii) the phonetic identity module determines whether characters of the reference word are pronounced the same as characters of the misspelled word, (iii) the character insertion module determines whether a character inserted in the misspelled word causes at least part of the incorrect word to match at least part of the reference word, (iv) the character deletion module determines whether a character deleted in the misspelled word causes at least part of the misspelled word to match at least part of the reference word, (v) the character replacement module replaces characters in the incorrect word with characters in the reference word in order to determine whether at least part of the misspelled word matches at least part of the reference word, (vi) the character transposition module changes the order of two or more characters in the misspelled word and compares a changed character in the misspelled word to a corresponding character in the reference word, and (vii) the character transposition completion module compares characters in the misspelled word which were not compared by the character transposition module in order to determine if at least part of the misspelled word matches at least part of the reference word.
Claim 12
Independent Claim
271 words
A method of correcting a misspelled word in input text, the method comprising steps of: storing one or more lexicon finite state machines (FSM), each of the lexicon FSMs representing plural reference words together with a phonetic representation of each reference word, wherein a representation of a reference word together with its phonetic representation comprises one or more states and one or more arcs, each arc comprising a pair of characters, one of which is a character in the reference word and the other of which is a phonetic representation thereof; detecting a misspelled word in the input text, wherein the detecting comprises comparing each word in the input text to a dictionary database and characterizing a word as misspelled when the word does not match any words in the dictionary database; generating an input FSM for the misspelled word, the input FSM representing the misspelled word together with a phonetic representation of the misspelled word, wherein the representation of the misspelled word together with its phonetic representation comprises one or more arcs, each arc comprising a pair of characters, one of which is a character in the reference word and the other of which is a phonetic representation thereof; generating an additional FSM comprising a plurality of states, each state including information identifying a state of a lexicon FSM and a state of the input FSM and a cost, wherein the cost is used to select states of the additional FSM that are to be expanded; and determining a list of alternative words for the misspelled word, wherein the determining comprises selecting one or more words from the additional FSM.
Claim 13
Independent Claim
271 words
A method of correcting a misspelled word in input text, the method comprising steps of: storing one or more lexicon finite state machines (FSM), each of the lexicon FSMs representing plural reference words together with a phonetic representation of each reference word, wherein a representation of a reference word together with its phonetic representation comprises one or more states and one or more arcs, each arc comprising a pair of characters, one of which is a character in the reference word and the other of which is a phonetic representation thereof; detecting a misspelled word in the input text, wherein the detecting comprises comparing each word in the input text to a dictionary database and characterizing a word as misspelled when the word does not match any words in the dictionary database; generating an input FSM for the misspelled word, the input FSM representing the misspelled word together with a phonetic representation of the misspelled word, wherein the representation of the misspelled word together with its phonetic representation comprises one or more arcs, each arc comprising a pair of characters, one of which is a character in the reference word and the other of which is a phonetic representation thereof; generating an additional FSM comprising a plurality of states, each state including information identifying a state of a lexicon FSM and a state of the input FSM and a cost, wherein the cost is used to select states of the additional FSM that are to be expanded; and determining a list of alternative words for the misspelled word, wherein the determining comprises selecting one or more words from the additional FSM.
Claim 14
Dependent Claim
30 words
The method of claim 11 , wherein the list of alternative words comprises words that correspond to a path from an initial to a final state of the additional FSM.
Claim 15
Dependent Claim
32 words
The method of claim 11 , wherein the cost is an indication of the likelihood that a current state is on a path leading to a correct spelling of the misspelled word.
Claim 16
Dependent Claim
67 words
The method of claim 11 , wherein a word or portion thereof corresponding to a current state in the additional FSM is obtained by making a series of character modifications to an input word or portion thereof, wherein each of the character modifications is associated with a predetermined value, and wherein the cost reflects a sum of the predetermined values associated with the series of character modifications.
Claim 17
Dependent Claim
44 words
The method of claim 14 , wherein the character modifications comprise one or more character modifications selected from the list consisting of: a character replacement, a character insertion, a character deletion, a character transposition, and replacement of a character by a phonetically equivalent character.
Claim 18
Dependent Claim
17 words
The method of claim 11 , further comprising the step of: ranking the list of alternative words.
Claim 19
Dependent Claim
29 words
The method of claim 11 , further comprising the step of: selecting one of the alternative words as a correct spelling for the misspelled word based on the ranking.
Claim 20
Dependent Claim
52 words
The method of claim 11 , 13 , 14 , or 15 , wherein each of the alternative words corresponds to a final state of the additional FSM, further including the step of: ranking the list of alternative words based on the costs of the final states corresponding to the alternative words.
Claim 21
Dependent Claim
23 words
The method of claim 11 , wherein the states further include information indicating whether a character transposition has occurred in the input word.
Claim 22
Dependent Claim
288 words
The method of claim 11 , wherein the generating step comprises applying one or more states of the additional FSM to one or more modules selected from the list consisting of: (i) a character identity module, (ii) a phonetic identity module, (iii) a character insertion module, (iv) a character deletion module, (v) a character replacement module, (vi) a character transposition module, and (vii) a character transposition completion module, wherein (i) the character identity module determines whether characters of a reference word in the lexicon FSM match characters of the misspelled word, (ii) the phonetic identity module determines whether characters of the reference word are pronounced the same as characters of the misspelled word, (iii) the character insertion module determines whether a character inserted in the misspelled word causes at least part of the incorrect word to match at least part of the reference word, (iv) the character deletion module determines whether a character deleted in the misspelled word causes at least part of the misspelled word to match at least part of the reference word, (v) the character replacement module replaces characters in the incorrect word with characters in the reference word in order to determine whether at least part of the misspelled word matches at least part of the reference word, (vi) the character transposition module changes the order of two or more characters in the misspelled word and compares a changed character in the misspelled word to a corresponding character in the reference word, and (vii) the character transposition completion module compares characters in the misspelled word which were not compared by the character transposition module in order to determine if at least part of the misspelled word matches at least part of the reference word.
Claim 23
Independent Claim
205 words
A method of correcting a misspelled word in input text, the method comprising steps of: storing one or more lexicon finite state machines (FSM), each of the lexicon FSMs representing plural reference words, wherein a representation of a reference word comprises one or more states and one or more arcs, each arc comprising a character in the reference word; detecting a misspelled word in the input text, wherein the detecting comprises comparing each word in the input text to a dictionary database and characterizing a word as misspelled when the word does not match any words in the dictionary database; generating an additional FSM comprising a plurality of states, each state including information identifying a state of a lexicon FSM and a position in the input word and a cost indicating the likelihood that a current state is on a path leading to a correct spelling of the misspelled word, wherein the cost is used to select states of the additional FSM that are to be expanded; determining a list of alternative words for the misspelled word, wherein the determining comprises selecting one or more words from the additional FSM; and ranking the list of alternative words based on a context of the input text.
Claim 24
Independent Claim
205 words
A method of correcting a misspelled word in input text, the method comprising steps of: storing one or more lexicon finite state machines (FSM), each of the lexicon FSMs representing plural reference words, wherein a representation of a reference word comprises one or more states and one or more arcs, each arc comprising a character in the reference word; detecting a misspelled word in the input text, wherein the detecting comprises comparing each word in the input text to a dictionary database and characterizing a word as misspelled when the word does not match any words in the dictionary database; generating an additional FSM comprising a plurality of states, each state including information identifying a state of a lexicon FSM and a position in the input word and a cost indicating the likelihood that a current state is on a path leading to a correct spelling of the misspelled word, wherein the cost is used to select states of the additional FSM that are to be expanded; determining a list of alternative words for the misspelled word, wherein the determining comprises selecting one or more words from the additional FSM; and ranking the list of alternative words based on a context of the input text.
Claim 25
Dependent Claim
32 words
The method of claim 21 , wherein the cost associated with an alternative word is equivalent to the cost identified in a final state for the alternative word in the additional FSM.
Claim 26
Independent Claim
209 words
A method of retrieving text from a source, the method comprising the steps of: inputting a search word; correcting a spelling of the search word through the steps of storing one or more lexicon finite state machines (FSM), each of the lexicon FSMs representing plural reference words, wherein a representation of a reference word comprises one or more states and one or more arcs, each arc comprising a character in the reference word, comparing the search word to a dictionary database and characterizing the search word as a misspelled search word when the search word does not match any words in the dictionary database, generating an additional FSM comprising a plurality of states, each state including information identifying a state of a lexicon FSM and a position in the search word and a cost indicating the likelihood that a current state is on a path leading to a correct spelling of the misspelled search word, wherein the cost is used to select states of the additional FSM that are to be expanded, and determining a list of alternative words for the misspelled search word, wherein the determining comprises selecting one or more words from the additional FSM; and retrieving text from the source that includes the corrected search word.
Claim 27
Independent Claim
209 words
A method of retrieving text from a source, the method comprising the steps of: inputting a search word; correcting a spelling of the search word through the steps of storing one or more lexicon finite state machines (FSM), each of the lexicon FSMs representing plural reference words, wherein a representation of a reference word comprises one or more states and one or more arcs, each arc comprising a character in the reference word, comparing the search word to a dictionary database and characterizing the search word as a misspelled search word when the search word does not match any words in the dictionary database, generating an additional FSM comprising a plurality of states, each state including information identifying a state of a lexicon FSM and a position in the search word and a cost indicating the likelihood that a current state is on a path leading to a correct spelling of the misspelled search word, wherein the cost is used to select states of the additional FSM that are to be expanded, and determining a list of alternative words for the misspelled search word, wherein the determining comprises selecting one or more words from the additional FSM; and retrieving text from the source that includes the corrected search word.
Claim 28
Dependent Claim
13 words
The method of claim 23 , wherein the source comprises a pre-stored database.
Claim 29
Dependent Claim
32 words
The method of claim 23 , wherein the source comprises a remote network location; and wherein the method further comprises the step of displaying the retrieved text on a local display screen.
Claim 30
Dependent Claim
27 words
The method of claim 23 , wherein the correcting step comprises displaying one or more corrected search words and manually selecting one of plural corrected search words.
Claim 31
Dependent Claim
19 words
The method of claim 23 , wherein the correcting step comprises automatically selecting one of plural corrected search words.
Claim 32
Independent Claim
237 words
A method of retrieving text from a source, the method comprising the steps of: inputting a search phrase comprised of a plurality of words, at least one of the plurality of words being a misspelled word; replacing the misspelled word in the search phrase with a corrected word in order to produce a corrected search phrase through the steps of storing one or more lexicon finite state machines (FSM), each of the lexicon FSMs representing plural reference words, wherein a representation of a reference word comprises one or more states and one or more arcs, each arc comprising a character in the reference word, comparing each word in the search phrase to a dictionary database and characterizing a word as a misspelled word when the word does not match any words in the dictionary database, generating an additional FSM comprising a plurality of states, each state including information identifying a state of a lexicon FSM and a position in the input search word and a cost indicating that a current state is on a path leading to a correct spelling of the misspelled word, wherein the cost is used to select states of the additional FSM that are to be expanded, and determining a list of alternative words for the misspelled word, wherein the determining comprises selecting one or more words from the additional FSM; and retrieving text from the source based on the corrected search phrase.
Claim 33
Independent Claim
237 words
A method of retrieving text from a source, the method comprising the steps of: inputting a search phrase comprised of a plurality of words, at least one of the plurality of words being a misspelled word; replacing the misspelled word in the search phrase with a corrected word in order to produce a corrected search phrase through the steps of storing one or more lexicon finite state machines (FSM), each of the lexicon FSMs representing plural reference words, wherein a representation of a reference word comprises one or more states and one or more arcs, each arc comprising a character in the reference word, comparing each word in the search phrase to a dictionary database and characterizing a word as a misspelled word when the word does not match any words in the dictionary database, generating an additional FSM comprising a plurality of states, each state including information identifying a state of a lexicon FSM and a position in the input search word and a cost indicating that a current state is on a path leading to a correct spelling of the misspelled word, wherein the cost is used to select states of the additional FSM that are to be expanded, and determining a list of alternative words for the misspelled word, wherein the determining comprises selecting one or more words from the additional FSM; and retrieving text from the source based on the corrected search phrase.
Claim 34
Dependent Claim
13 words
The method of claim 28 , wherein the source comprises a pre-stored database.
Claim 35
Dependent Claim
32 words
The method of claim 28 , wherein the source comprises a remote network location; and wherein the method further comprises the step of displaying the retrieved text on a local display screen.
Claim 36
Dependent Claim
28 words
The method of claim 28 , wherein the replacing step further comprises displaying one or more corrected search words and manually selecting one of plural corrected search words.
Claim 37
Dependent Claim
20 words
The method of claim 28 , wherein the replacing step further comprises automatically selecting one of plural corrected search words.
Claim 38
Independent Claim
187 words
A method of correcting misspelled words in input text sequences received from a plurality of different clients, the method comprising the steps of: storing, in a memory on a server, a single shared lexicon comprised of a plurality of reference words, wherein the single shared lexicon comprises one or more lexicon finite state machines (“FSM”), each of the lexicon FSMs representing plural reference words together with a phonetic representation of each reference word, wherein a representation of a reference word comprises one or more states and one or more arcs, each arc comprising a pair of characters, one of which is a character in the reference word and the other of which is a phonetic representation thereof; receiving the input text sequences from the plurality of different clients; spell-checking the input text sequences using the reference words in the single shared lexicon, wherein the spell-checking step comprises a correcting step for correcting misspelled words in each of the input text sequences substantially in parallel using the single shared lexicon comprised of one or more lexicon FSMs; and outputting spell-checked text sequences to the plurality of different clients.
Claim 39
Independent Claim
187 words
A method of correcting misspelled words in input text sequences received from a plurality of different clients, the method comprising the steps of: storing, in a memory on a server, a single shared lexicon comprised of a plurality of reference words, wherein the single shared lexicon comprises one or more lexicon finite state machines (“FSM”), each of the lexicon FSMs representing plural reference words together with a phonetic representation of each reference word, wherein a representation of a reference word comprises one or more states and one or more arcs, each arc comprising a pair of characters, one of which is a character in the reference word and the other of which is a phonetic representation thereof; receiving the input text sequences from the plurality of different clients; spell-checking the input text sequences using the reference words in the single shared lexicon, wherein the spell-checking step comprises a correcting step for correcting misspelled words in each of the input text sequences substantially in parallel using the single shared lexicon comprised of one or more lexicon FSMs; and outputting spell-checked text sequences to the plurality of different clients.
Claim 40
Dependent Claim
97 words
A method according to claim 33 , wherein, for each text sequence, the correcting step comprises: generating an additional FSM comprising a plurality of states, each state including information identifying a state of a lexicon FSM and a position in the input word and a cost, wherein the cost is used to select states of the additional FSM that are to be expanded; selecting one or more reference words from the lexicon FSMs based on the additional FSM; and replacing the misspelled word in the text sequence with a selected one of the one or reference words.
Claim 41
Dependent Claim
46 words
The method of claim 34 , further comprising the step of: generating an input FSM for a misspelled word in the text sequence, wherein the input FSM comprises one or more states and one or more arcs, each arc comprising a character in the reference word.
Claim 42
Dependent Claim
64 words
The method of claim 34 , further comprising the step of: generating an input FSM for a misspelled word in the text sequence, wherein the input FSM comprises one or more states and one or more arcs, each arc comprising a pair of characters, one of which is a character in the reference word and the other of which is a phonetic representation thereof.
Claim 43
Independent Claim
160 words
A method of spell-checking input text, the method comprising the steps of: detecting a misspelled word in the input text; storing one or more lexicon finite state machines (“FSM”) in a memory, each of the lexicon FSMs including plural reference words; generating an input FSM for the misspelled word; selecting one or more reference words from the lexicon FSMs based on the input FSM, the one or more reference words substantially corresponding to a spelling of the misspelled word, wherein the selecting step further comprises the steps of generating an additional FSM comprising a plurality of states, each state identifying a state of a lexicon FSM and a position in the input word and a cost, wherein the cost is used to select states of the additional FSM that are to be expanded, and selecting the one or more reference words from the lexicon FSMs using the additional FSM; and otuputting selected ones of the one or more reference words.
Claim 44
Independent Claim
160 words
A method of spell-checking input text, the method comprising the steps of: detecting a misspelled word in the input text; storing one or more lexicon finite state machines (“FSM”) in a memory, each of the lexicon FSMs including plural reference words; generating an input FSM for the misspelled word; selecting one or more reference words from the lexicon FSMs based on the input FSM, the one or more reference words substantially corresponding to a spelling of the misspelled word, wherein the selecting step further comprises the steps of generating an additional FSM comprising a plurality of states, each state identifying a state of a lexicon FSM and a position in the input word and a cost, wherein the cost is used to select states of the additional FSM that are to be expanded, and selecting the one or more reference words from the lexicon FSMs using the additional FSM; and otuputting selected ones of the one or more reference words.
Claim 45
Dependent Claim
293 words
A method according to claim 37 , wherein the selecting step selects the one or more reference words by applying each state of the additional FSM to one or more of (i) a character identity module, (ii) a phonetic identity module, (iii) a character insertion module, (iv) a character deletion module, (v) a character replacement module, (vi) a character transposition module, and (vii) a character transposition completion module; and wherein (i) the character identity module determines whether characters of a reference word in the lexicon FSM match characters of the misspelled word in the input FSM, (ii) the phonetic identity module determines whether characters of the reference word are pronounced the same as characters of the misspelled word, (iii) the character insertion module determines whether a character inserted in the misspelled word causes at least part of the misspelled word to match at least part of the reference word, (iv) the character deletion module determines whether a character deleted from the misspelled word causes at least part of the misspelled word to match at least part of the reference word, (v) the character replacement module replaces characters in the misspelled word with characters in the reference word in order to determine whether at least part of the misspelled word matches at least part of the reference word, (vi) the character transposition module changes the order of two or more characters in the misspelled word and compares a changed character in the misspelled word to a corresponding character in the reference word, and (vi) the character transposition completion module compares characters in the misspelled word which were not compared by the character transposition module in order to determine if at least part of the misspelled word matches at least part of the reference word.
Claim 46
Dependent Claim
58 words
The method of claim 37 , wherein each of the lexicon FSMs also includes a phonetic representation of each reference word; wherein the input FSM also includes a phonetic representation of the misspelled word; and wherein the selecting step selects reference words from the lexicon FSMs which also substantially correspond to the phonetic representation of the misspelled word.
Claim 47
Independent Claim
308 words
A method of correcting a misspelled word in input text, the method comprising the steps of: storing one or more lexicon finite state machines (FSM), each of the lexicon FSMs representing plural reference words together with a phonetic representation of each reference word, wherein a representation of a reference word together with its phonetic representation comprises one or more states and one or more arcs, each arc comprising a pair of characters, one of which is a character in the reference word and the other of which is a phonetic representation thereof; detecting a misspelled word in the input text, wherein the detecting comprises comparing each word in the input text to a dictionary database and characterizing a word as misspelled when the word does not match any words in the dictionary database; generating an input FSM for the misspelled word, the input FSM representing the misspelled word together with a phonetic representation of the misspelled word, wherein the representation of the misspelled word together with its phonetic representation comprises one or more arcs, each arc comprising a pair of characters, one of which is a character in the reference word and the other of which is a phonetic representation thereof; generating an additional FSM comprising a plurality of states, each state including information identifying a state of a lexicon FSM and a state of the input FSM and a cost indicating of the likelihood that a current state is on a path leading to a correct spelling of the misspelled word, wherein the cost is used to select states of the additional FSM that are to be expanded; determining a list of alternative words for the misspelled word, wherein the determining comprises selecting one or more words from the additional FSM; and ranking the list of the alternative words based on a context of the input text.
Claim 48
Independent Claim
308 words
A method of correcting a misspelled word in input text, the method comprising the steps of: storing one or more lexicon finite state machines (FSM), each of the lexicon FSMs representing plural reference words together with a phonetic representation of each reference word, wherein a representation of a reference word together with its phonetic representation comprises one or more states and one or more arcs, each arc comprising a pair of characters, one of which is a character in the reference word and the other of which is a phonetic representation thereof; detecting a misspelled word in the input text, wherein the detecting comprises comparing each word in the input text to a dictionary database and characterizing a word as misspelled when the word does not match any words in the dictionary database; generating an input FSM for the misspelled word, the input FSM representing the misspelled word together with a phonetic representation of the misspelled word, wherein the representation of the misspelled word together with its phonetic representation comprises one or more arcs, each arc comprising a pair of characters, one of which is a character in the reference word and the other of which is a phonetic representation thereof; generating an additional FSM comprising a plurality of states, each state including information identifying a state of a lexicon FSM and a state of the input FSM and a cost indicating of the likelihood that a current state is on a path leading to a correct spelling of the misspelled word, wherein the cost is used to select states of the additional FSM that are to be expanded; determining a list of alternative words for the misspelled word, wherein the determining comprises selecting one or more words from the additional FSM; and ranking the list of the alternative words based on a context of the input text.
References Cited (Backward Citations)
US4674065A
Cited
US4580241A
Cited
US4730269A
Cited
US4672571A
Cited
US4701851A
Cited
US4818131A
Cited
EP0283685A2
Cited
US4864502A
Cited
US4868750A
Cited
US4847766A
Cited
US4994966A
Cited
JPH0242574A
Cited
JPH0283664A
Cited
JPH02103662A
Cited
US5258909A
Cited
US5604897A
Cited
US5369577A
Cited
US5625554A
Cited
US5677835A
Cited
US5606690A
Cited
US5537317A
Cited
US5485372A
Cited
US5610812A
Cited
US5659771A
Cited
US5737734A
Cited
EP0788062A2
Cited
WO1997049043A1
Cited
US6016471A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-07-22 | 2006-01-21 | 2006-07-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-07-22 | 2010-01-21 | 2010-07-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-07-22 | 2014-01-21 | 2014-07-23 | $7700.00 | Window Closed / Lapsed |