US5377281A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Knowledge-based character recognition
Assignee: AT&T Inc
•
Filing: 1992-03-18
•
Granted: 1994-12-27
•
Expires: 2012-03-18
Abstract
Abstract Character string recognition and identification is accomplished with a combined, multi-phase top-down and bottom-up process. Characters in an applied signal are recognized with a process that employs a knowledge source which contains information both, about the basic elements in the signal and about strings of the basic elements in the signal. The knowledge source, which may be derived from a training corpus, includes word probabilities, word di-gram probabilities, statisitics that relate the likelihood of words with particular character prefixes, and rewrite suggestions and their costs. Higher level word n-grams, such as word tri-gram probabilities, can also be used. A mechanism is provided for accepting words that are not found in the knowledge base, as well as for rewrite suggestions that are not in the knowledge base.
Inventors
- 👤 Bruce W. Ballard
- 👤 Mark A. Jones
- 👤 Guy A. Story
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 16:03
CPC Classifications
G; G06; G06V; G06V30/00; G06V30/10; G06V30/26; G06V30/262
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
130 words
A method responsive to a collection of input characters comprising the steps of: separating the collection of input characters into input character strings; for each one of the input character strings, forming at least one set of candidate output strings, with most of the sets containing more than one candidate output string: and based on probability measure related to the occurrence of input character combinations and probability measure related to the occurrence of an output string having a given string of characters, selecting one candidate output string from each of the sets as a determined output string of the set wherein said step of forming a set of candidate output strings carries out an iterative search procedure with the aid of a rewrite probabilities table and a word probabilities table.
Claim 2
Independent Claim
130 words
A method responsive to a collection of input characters comprising the steps of: separating the collection of input characters into input character strings; for each one of the input character strings, forming at least one set of candidate output strings, with most of the sets containing more than one candidate output string: and based on probability measure related to the occurrence of input character combinations and probability measure related to the occurrence of an output string having a given string of characters, selecting one candidate output string from each of the sets as a determined output string of the set wherein said step of forming a set of candidate output strings carries out an iterative search procedure with the aid of a rewrite probabilities table and a word probabilities table.
Claim 3
Dependent Claim
17 words
The method of claim 1 wherein said input character strings are delimited by a preselected space character.
Claim 4
Dependent Claim
106 words
The method of claim 1 wherein the step of forming a set of candidate output strings creates each candidate output string by rewriting groups of m characters of the input string into groups of n characters of the candidate output string, where m and n are unconstrained to be equal to each other, are unconstrained to be the same for successive groups of characters making up the input string and the candidate output string, and the number of characters in each candidate output string in the set is unconstrained to be equal to the number of characters in any other candidate output string in the set.
Claim 5
Dependent Claim
48 words
The method of claim 3 wherein the step of forming a set of candidate output strings still further comprises the step of removing a candidate output string from said set of candidate output strings when the number of candidate output strings in the set exceeds a preselected value.
Claim 6
Dependent Claim
47 words
The method of claim 3 wherein the step of forming a set of candidate output strings further comprises the step of removing a candidate output string from said set of candidate output strings when the number of candidate output strings in the set exceeds a preselected value.
Claim 7
Dependent Claim
63 words
The method of claim 1 wherein the step of forming a set of candidate output strings creates each candidate output string by m-to-n character rewrites, where m is the number of input string characters, n is the number of candidate output string characters and both m and n are unconstrained to independently take on any value within the range 0 to 3 characters.
Claim 8
Dependent Claim
198 words
The method of claim 1 wherein the step of forming a set of candidate output strings comprises the steps of: converting the input character string to a candidate output string by rewriting groups of input characters which, when concatenated, form the input character string, into groups of output characters which, when concatenated, form the candidate output string, where corresponding groups of input characters and output characters are unconstrained to have an equal number of characters; forming a candidate cost measure for the candidate output string created by the step of converting by combining costs associated with the rewriting of groups of input characters, as carried out in the step of converting, and adding thereto a cost measure representative of the likelihood of occurrence of the candidate output string; tentatively adding the candidate output string to the set of candidate output strings when the candidate cost measure is within a threshold of the lowest candidate cost measure of candidate output strings already in the set of candidate output strings, and returning to the step of converting as long as a possibility exists that candidate output strings can be found with a candidate cost measure that is within said threshold.
Claim 9
Dependent Claim
39 words
The method of claim 7 wherein the steps of converting the input string and forming a candidate cost measure are carried out interactively, with the cost measure being updated with each rewrite carried out in the step of converting.
Claim 10
Dependent Claim
32 words
The method of claim 8 where with each rewrite carried out in the step of converting and updating of the candidate's cost measure, the candidate's most optimistic final cost measure is estimated.
Claim 11
Dependent Claim
25 words
The method of claim 9 where the estimate is derived from a table of candidate costs based on known initial characters rewritten for the candidate.
Claim 12
Dependent Claim
39 words
The method of claim 9 where the estimate is derived by combining the candidate's updated cost measure with a lowest cost measure of a candidate string having the characters rewritten for the candidate, derived from a word probabilities table.
Claim 13
Dependent Claim
46 words
The method of claim 9 where the estimate is derived by combining the candidate's updated cost measure with a lowest cost measure of a candidate string having the characters rewritten for the candidate and the width of the input string, derived from a word probabilities table.
Claim 14
Dependent Claim
48 words
The method of claim 8 where the step of converting is aborted prior to its termination when the candidate cost measure is anticipated to exceed the lowest candidate cost measure of a candidate output string already in the set of candidate output swings by more than the threshold.
Claim 15
Dependent Claim
56 words
The method of claim 13 where a determination is made that the candidate cost measure is anticipated to exceed the lowest cost of a candidate output string already in the set of candidate output strings by more than the threshold on the basis of a table that is keyed to a prefix of the input string.
Claim 16
Dependent Claim
64 words
The method of claim 13 where a determination is made that the candidate cost measure is anticipated to exceed the lowest cost of a candidate output string already in the set of candidate output swings by more than the threshold on the basis of a table that is keyed to a prefix of the input swing and to the width of the input string.
Claim 17
Dependent Claim
28 words
The method of claim 15 where the width of the input string is related to the nature of the characters in the input string and to their number.
Claim 18
Dependent Claim
59 words
The method of claim 15 wherein the step of forming a set of candidate output strings further comprises the step of removing a candidate output string from said set of candidate output strings when the candidate cost measure of that candidate output string exceeds the lowest cost measure or some candidate output string in the set by said threshold.
Claim 19
Dependent Claim
31 words
The method of claim 1 wherein the word probabilities table is augmented with a process for determining the probability of a word that is not present in the word probabilities table.
Claim 20
Dependent Claim
76 words
The method of claim 18 wherein the process for determining the probability of a word that is not present in the word probabilities table comprises evaluating the expression ##EQU4## where n is the number of letters in the word, C rare is some selected estimate of a real word existing which the training session hasn't seen, and p i is the probability of the i th letter digram of the unknown word generally occurring in text.
Claim 21
Dependent Claim
14 words
The method of claim 1 wherein said iterative search procedure is a branch-and-bound procedure.
Claim 22
Dependent Claim
114 words
The method of claim 1 wherein said step of selecting considers probability measures of occurrence of triplets of character strings wherein the first string in the triplet of character strings is a previously determined output string of a set, the second string in the triplet of character strings is a candidate output string in the set of candidate strings that is adjacent to the first string, and the third string in the triplet of character strings is a candidate output string in the set of candidate strings that is adjacent to the set of the second string, where the selection is made of a determined output swing in the set of the second string.
Claim 23
Dependent Claim
23 words
The method of claim 1 further comprising a step of augmenting a set of candidate output strings with a suggested candidate output string.
Claim 24
Dependent Claim
35 words
The method of claim 1 wherein the step of forming a set of candidate output swing comprises a step of augmenting a previously formed set of candidate output strings with a suggested candidate output string.
Claim 25
Dependent Claim
22 words
The method of claim 23 wherein said step of augmenting derives the suggested candidate output string from a word di-gram probabilities table.
Claim 26
Dependent Claim
22 words
The method of claim 23 wherein said step of augmenting derives the suggested candidate output string from a word tri-gram probabilities table.
Claim 27
Dependent Claim
43 words
The method of claim 23 wherein said step of augmenting derives the suggested candidate output string from a word n-gram probabilities table, where n designates the number of words in the set of words for which the n-gram probabilities table provides probability values.
Claim 28
Dependent Claim
56 words
The method of claim 1 wherein an input character string is effectively split into a number of input character strings by the step of forming a corresponding number of sets of candidate output strings, with a delimiter which separates character strings that are recognized as valid character strings on either side of the input character strings.
Claim 29
Dependent Claim
79 words
The method of claim 1 further comprising a steps of: combining at least two of the input character strings created in the step of separating, to form a modified input character string; forming an X set of candidate output strings for the modified input character string; and based on probability measures related to the occurrence of character string input character sequences, selecting one candidate output string from the X set as a determined output string of the X set.
Claim 30
Independent Claim
177 words
A method responsive to a collection of input characters comprising the steps of: separating the collection of input characters into input character strings; for each one of the input character strings, forming at least one set of candidate output strings, with most of the sets containing more than one candidate output string; and based on probability measure related to the occurrence of input character combinations and probability measure related to the occurrence of an output string having a given string of characters, selecting one candidate output string from each of the sets as a determined output string of the set wherein said step of selecting considers probability measures of occurrence of pairs of character strings wherein the first character string in the pair of character strings is a previously determined output string, and the second character string in the pair of character strings is a candidate output string in the set of candidate output strings that correspond to an input character string which is adjacent to an input character string that corresponds to the first character string.
Claim 31
Independent Claim
177 words
A method responsive to a collection of input characters comprising the steps of: separating the collection of input characters into input character strings; for each one of the input character strings, forming at least one set of candidate output strings, with most of the sets containing more than one candidate output string; and based on probability measure related to the occurrence of input character combinations and probability measure related to the occurrence of an output string having a given string of characters, selecting one candidate output string from each of the sets as a determined output string of the set wherein said step of selecting considers probability measures of occurrence of pairs of character strings wherein the first character string in the pair of character strings is a previously determined output string, and the second character string in the pair of character strings is a candidate output string in the set of candidate output strings that correspond to an input character string which is adjacent to an input character string that corresponds to the first character string.
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) | 1997-12-26 | 1998-06-27 | 1998-12-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-12-26 | 2002-06-27 | 2002-12-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-12-26 | 2006-06-27 | 2006-12-27 | $7700.00 | Window Closed / Lapsed |