EP0425291A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Word recognition process and apparatus
Assignee: Xerox Corp
•
Filing: 1990-10-25
•
Granted: —
•
Expires: 2010-10-25
Abstract
Abstract A data structure includes data indicating a set of strings of character or phoneme candidate identifiers. Each identifier indicates a machine discriminatable candidate type, and the data are accessible to determine whether a string of candidate identifiers is in the set. To produce the data structure, the set of strings is obtained using a list of words. All possible strings up to a given length are obtained, and those that have a high probability of being one of the words are retained. Also, the words are expanded into strings by using probable candidate identifiers for each character or phoneme. If necessary, the number of candidate types is increased or decreased to obtain a satisfactory set of strings. The data structure can include information relating to each string in the set; for example, it can be a finite state transducer with data units, each including a candidate identifier and a character or phoneme identifier, so that the characters or phonemes of a word can be obtained from it. A processor receives a string of candidate identifiers from a candidate discriminator and searches the data structure for the identifiers that occur in the string. If a search succeeds, data relating to the matched string are obtained, such as a word it is likely to be or an identifier of the string. If the string is likely to be more than one word, one of the words is selected and its characters or ph,one,mes are provided as output. A system can include parallel recognition units, each with a respective data structure. The sets of strings can correspond to words with features such as' part of speech font speaker, a language, or a specialized vocabulary. A results processor can receive the results from the recognition units and use them to obtain the characters or phonemes of a word that is likely to be the string being recognized.
Inventors
- 👤 James T. Beran
- 👤 Ronald M. Kaplan
- 👤 Lynn D. Wilcox
- 👤 Per-Kristian Halvorsen
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-26 07:49
CPC Classifications
G; G10; G10L; G10L15/00; G10L15/08; G10L15/083; G06; G06V; G06V30/00; G06V30/10; G06V30/26; G06V30/262; G06V30/268
Claims Analysis
Total Claims: 54
Claim 1
Independent Claim
83 words
A method of recognising a specified data string in a set of such strings comprising the step of: including data in a data structure indicating a set of strings of character candidate identifiers, each character candidate identifier indicating one of a set of machine discriminatable character candidate types, the step comprising including the data such that the data is accessible to determine whether a string of character candidate identifiers being recognized is one of the strings in the set indicated by the data.
Claim 2
Independent Claim
83 words
A method of recognising a specified data string in a set of such strings comprising the step of: including data in a data structure indicating a set of strings of character candidate identifiers, each character candidate identifier indicating one of a set of machine discriminatable character candidate types, the step comprising including the data such that the data is accessible to determine whether a string of character candidate identifiers being recognized is one of the strings in the set indicated by the data.
Claim 3
Dependent Claim
24 words
The method of claim 1, further comprising obtaining the data indicating the set of strings of character candidate identifiers using a list of words.
Claim 4
Dependent Claim
83 words
The method of claim 2, in which a first word in the list of words includes a character, the set of character candidate identifiers including first and second character candidate identifiers indicating first and second character candidates that are likely to be the character, the step of obtaining the data indicating-the set of strings comprising obtaining first and second strings of character candidate identifiers, the first string including the first character candidate identifier and the second string including the second character candidate identifier.
Claim 5
Dependent Claim
54 words
The method of claim 2 in which the step of obtaining the data indicating the set of strings comprises obtaining all possible strings of character candidate identifiers of a given length and determining whether each of the possible strings has a high probability of being one of the words in the list of words.
Claim 6
Dependent Claim
143 words
The method of claim 1, further comprising obtaining preliminary data indicating, for each string in the set of strings, a word that the string is likely to be; the step of including the data in the data structure comprising including in the data structure a finite state transducer data structure based on the preliminary data; the finite state transducer data structure comprising data defining a set of states and a set of transitions, each transition originating in one of the states and terminating in one of the states; the data defining the states and transitions indicating the set of strings of character candidate identifiers and, for each string in the set, a respective string of character identifiers; the finite state transducer data structure being accessible to determine whether the string of character candidate identifiers being recognized is one of the set of strings.
Claim 7
Dependent Claim
25 words
The method of claim 1, further comprising modifying a preliminary set of character candidate types to obtain the set of machine discriminable character candidate types.
Claim 8
Dependent Claim
22 words
The method of claim 6 in which the modifying step comprises increasing the number of character candidate types in the preliminary set.
Claim 9
Dependent Claim
22 words
The method of claim 6 in which the modifying step comprises decreasing the number of character candidate types in the preliminary set.
Claim 10
Dependent Claim
60 words
A data structure comprising data indicating a set of strings of character candidate identifiers, each character candidate identifier indicating one of a set of machine discriminable character candidate types, the data in the data structure being accessible to determine whether a string of character candidate identifiers being recognized is one of the strings in the set indicated by the data.
Claim 11
Dependent Claim
60 words
A data structure comprising data indicating a set of strings of character candidate identifiers, each character candidate identifier indicating one of a set of machine discriminable character candidate types, the data in the data structure being accessible to determine whether a string of character candidate identifiers being recognized is one of the strings in the set indicated by the data.
Claim 12
Dependent Claim
19 words
The data structure of claim 9 in which each of the strings in the set is an acceptable string.
Claim 13
Dependent Claim
119 words
The data structure of claim 9, further comprising a finite state transducer data structure indicating, for each string in the set of strings, a word that the string is likely to be; the finite state transducer data structure comprising data defining a set of states and a set of transitions, each transition originating in one of the-states and terminating in one of the states; the data defining the states and transitions indicating the set of strings of character candidate identifiers and, for each string in the set, a respective string of character identifiers; the finite state transducer data structure being accessible to determine whether the string of character candidate identifiers being recognized is one of the set of strings.
Claim 14
Dependent Claim
31 words
The data structure of claim 11 in which the data defining one of the transitions comprises a data unit that includes a respective character candidate identifier and a respective character identifier.
Claim 15
Dependent Claim
65 words
A method of using the data structure of claim 12 comprising: searching for the string being recognized, the searching step comprising: accessing the data unit; determining whether the respective character candidate identifier of the data unit matches one of the character candidate identifiers in the string being recognized; and if the respective character candidate identifier matches, storing the respective character identifier of the data unit.
Claim 16
Dependent Claim
46 words
A method of using the finite state transducer data structure of claim 11 comprising: accessing the data defining the states and transitions; and determining whether the string being recognized is one of the strings in the set indicated by the data defining the states and transitions.
Claim 17
Dependent Claim
64 words
The method of claim 14 in which the data structure further includes, in addition to the data defining the states and transitions, respective data relating to one of the strings in the indicated set, the method further comprising, if the string being recognized is the one of the strings in the indicated set, accessing the respective data relating to the one of the strings.
Claim 18
Dependent Claim
52 words
A system comprising the finite state transducer data structure of claim 11, the system further comprising a processor for accessing the data defining the states and transitions and for determining whether the string being recognized is one of the strings in the set indicated by the data defining the states and transitions.
Claim 19
Dependent Claim
40 words
A system comprising the data structure of claim 9, the system further comprising a processor for accessing the data structure and for determining whether the string being recognized is one of the strings in the set indicated by the data.
Claim 20
Dependent Claim
29 words
The system of claim 17, further comprising a candidate discriminator for providing the string being recognized to the processor, the candidate discriminator providing the string based on a text.
Claim 21
Dependent Claim
79 words
The system of claim 18 in which each character candidate identifier is one of a set of cluster IDs, each of the cluster IDs indicating a respective cluster in character probability space, the candidate discriminator further being for segmenting the text into character candidates and for determining a nearest one of the respective clusters in character probability space for each character candidate, the candidate discriminator providing the cluster ID indicating the nearest cluster for each of the character candidates.
Claim 22
Independent Claim
73 words
A system comprising: a candidate discriminator for providing a string of character candidate identifiers to be recognized, each character candidate identifier indicating one of a set of machine discriminable character candidate types, the candidate discriminator providing the string to be recognized based on a text; and a string recognizer for receiving the string to be recognized and for providing characters of a word that the string to be recognized is likely to be.
Claim 23
Independent Claim
73 words
A system comprising: a candidate discriminator for providing a string of character candidate identifiers to be recognized, each character candidate identifier indicating one of a set of machine discriminable character candidate types, the candidate discriminator providing the string to be recognized based on a text; and a string recognizer for receiving the string to be recognized and for providing characters of a word that the string to be recognized is likely to be.
Claim 24
Dependent Claim
55 words
The system of claim 20 in which the string recognizer comprises a data structure that includes data indicating a set of strings of the character candidate identifiers, the data in the data structure being accessible to determine whether the string to be recognized is one of the strings in the set indicated by the data.
Claim 25
Dependent Claim
60 words
The system of claim 20 in which the string recognizer comprises a plurality of data structures, each data structure including respective data indicating a respective set of strings of the character candidate identifiers, the data in each of the data structures being accessible to determine whether the string to be recognized is one of the strings in the respective set.
Claim 26
Dependent Claim
32 words
The system of claim 21 in which each string in the respective set of strings of one of the data structures is likely to be a word having a respective word feature.
Claim 27
Dependent Claim
18 words
The system of claim 23 in which the respective word feature is a feature of part of speech.
Claim 28
Dependent Claim
16 words
The system of claim 23 in which the respective word feature is a feature of typeface.
Claim 29
Dependent Claim
55 words
The system of claim 20 in which the string recognizer comprises a plurality of recognition units, each receiving the string to be recognized from the candidate discriminator, each recognition unit being for determining whether the string to be recognized is one of the strings in a respective set of strings of the character candidate identifiers.
Claim 30
Dependent Claim
55 words
The system of claim 26 in which each recognition unit comprises a data structure including data indicating the respective set of strings of character candidate identifiers, the data in each data structure being accessible to determine whether the string to be recognized is one of the strings in the respective set indicated by the data.
Claim 31
Dependent Claim
23 words
The system of claim 27 in which the data in each data structure includes data relating to each string in the respective set.
Claim 32
Dependent Claim
75 words
The system of claim 26 in which each recognition unit is further for providing a preliminary string identifier indicating the string to be recognized if the string to be recognized is one of the strings in its respective set, the system further comprising a processor for receiving each preliminary string identifier provided by the recognition units and for using the preliminary string identifiers to obtain a resolved string identifier indicating the string to be recognized.
Claim 33
Dependent Claim
32 words
The system of claim 29 in which the processor is further for using the resolved string identifierto obtain a set of words that the string to be recognized is likely to be.
Claim 34
Dependent Claim
33 words
The method of claim 30 in which the processor is further for selecting one of the set of words and for providing character identifiers indicating character types of characters of the selected word.
Claim 35
Dependent Claim
49 words
The method of claim 26 in which each recognition unit is further for providing character identifiers indicating character types of characters of a word which the string to be recognized is likely to be if the string to be recognized is one of the strings in its respective set.
Claim 36
Dependent Claim
21 words
The system of claim 26 in which each of the strings in each of the respective sets is an acceptable string.
Claim 37
Dependent Claim
103 words
A finite state transducer data structure comprising data defining a set of states and a set of transitions, each transition originating in one of the states and terminating in one of the states; the data defining the states and transitions indicating a set of strings of phoneme candidate identifiers and, for each string in the set, a respective string of phoneme identifiers; each of the phoneme candidate identifiers indicating one of a set of machine discriminable phoneme candidate types; the data structure being accessible to determine whether a string of phoneme candidate identifiers being recognized is one of the indicated set of strings.
Claim 38
Dependent Claim
103 words
A finite state transducer data structure comprising data defining a set of states and a set of transitions, each transition originating in one of the states and terminating in one of the states; the data defining the states and transitions indicating a set of strings of phoneme candidate identifiers and, for each string in the set, a respective string of phoneme identifiers; each of the phoneme candidate identifiers indicating one of a set of machine discriminable phoneme candidate types; the data structure being accessible to determine whether a string of phoneme candidate identifiers being recognized is one of the indicated set of strings.
Claim 39
Dependent Claim
22 words
The data structure of claim 34 in which each of the strings in the indicated set of strings is an acceptable string.
Claim 40
Dependent Claim
31 words
The data structure of claim 34 in which the data defining one of the transitions comprises a data unit that includes a respective phoneme candidate identifier and a respective phoneme identifier.
Claim 41
Dependent Claim
65 words
A method of using the data structure of claim 36 comprising: searching for the string being recognized, the searching step comprising: accessing the data unit; determining whether the respective phoneme candidate identifier of the data unit matches one of the phoneme candidate identifiers in the string being recognized; and if the respective phoneme candidate identifier matches, storing the respective phoneme identifier of the data unit.
Claim 42
Dependent Claim
46 words
A method of using the finite state transducer data structure of claim 34 comprising: accessing the data defining the states and transitions; and determining whether the string being recognized is one of the strings in the set indicated by the data defining the states and transitions.
Claim 43
Dependent Claim
64 words
The method of claim 38 in which the data structure further includes, in addition to the data defining the states and transitions, respective data relating to one of the strings in the indicated set, the method further comprising, if the string being recognized is the one of the strings in the indicated set, accessing the respective data relating to the one of the strings.
Claim 44
Dependent Claim
52 words
A system comprising the finite state transducer data structure of claim 34, the system further comprising: a processor for accessing the data defining the states and transitions and for determining whether the string being recognized is one of the strings in the set indicated by the data defining the states and transitions.
Claim 45
Independent Claim
121 words
A system comprising: a candidate discriminator for providing a string of phoneme candidate identifiers to be recognized, each phoneme candidate identifier indicating one of a set of machine discriminable phoneme candidate types, the candidate discriminator obtaining the string to be recognized from a spoken word; and a string recognizer for receiving the string to be recognized and for providing phonemes of a word that the string to be recognized is likely to be; the string recognizer comprising a plurality of recognition units, each receiving the string to be recognized from the candidate discriminator, each recognition unit being for determining whether the string to be recognized is one of the strings in a respective set of strings of the phoneme candidate identifiers.
Claim 46
Independent Claim
121 words
A system comprising: a candidate discriminator for providing a string of phoneme candidate identifiers to be recognized, each phoneme candidate identifier indicating one of a set of machine discriminable phoneme candidate types, the candidate discriminator obtaining the string to be recognized from a spoken word; and a string recognizer for receiving the string to be recognized and for providing phonemes of a word that the string to be recognized is likely to be; the string recognizer comprising a plurality of recognition units, each receiving the string to be recognized from the candidate discriminator, each recognition unit being for determining whether the string to be recognized is one of the strings in a respective set of strings of the phoneme candidate identifiers.
Claim 47
Dependent Claim
50 words
The system of claim 41 in which one of the recognition units comprises a data structure including data indicating the respective set of strings of the phoneme candidate identifiers, the data being accessible to determine whether the string to be recognized is one of the strings in the respective set.
Claim 48
Dependent Claim
32 words
The system of claim 41 in which each string in the respective set of strings of one of the recognition units is likely to be a word having a respective word feature.
Claim 49
Dependent Claim
18 words
The system of claim 43 in which the respective word feature is a feature of part of speech.
Claim 50
Dependent Claim
75 words
The system of claim 41 in which each recognition unit is further for providing a preliminary string identifier indicating the string to be recognized if the string to be recognized is one of the strings in its respective set, the system further comprising a processor for receiving each preliminary string identifier provided by the recognition units and for using the preliminary string identifiers to obtain a resolved string identifier indicating the string to be recognized.
Claim 51
Dependent Claim
33 words
The system of claim 45 in which the processor is further for using the resolved string identifier to obtain a set of words that the string to be recognized is likely to be.
Claim 52
Dependent Claim
33 words
The system of claim 46 in which the processor is further for selecting one of the set of words and for providing phoneme identifiers indicating phoneme types of phonemes of the selected word.
Claim 53
Dependent Claim
49 words
The system of claim 41 in which each recognition unit is further for providing phoneme identifiers indicating phoneme types of phonemes of a word which the string to be recognized is likely to be if the string to be recognized is one of the strings in its respective set.
Claim 54
Dependent Claim
21 words
The system of claim 41 in which the candidate discriminator obtains the string to be recognized from an isolated spoken word.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.