System to achieve automatic recognition of linguistic strings

• US 4,654,875 A
• Filed: 05/23/1983
• Issued: 03/31/1987
• Est. Priority Date: 05/23/1983
• Status: Expired due to Fees

• Current Assignee: The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Hull, Jonathan J., Srihari, Sargur N.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/496,827
• Time in Patent Office: 1,408 Days
• Field of Search: 382/40, 382/37, 382/38, 382/57, 382/1, 382/36, 381/52, 381/44, 371/67-69
• US Class Current: 382/229
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context

Abstract

A method (and system) to achieve automatic language recognition that includes the steps of introducing language in the form of strings to a mechanism that converts the language to electrical signals derived from the strings introduced, which electrical signals are the electrical analog of words in the strings; analyzing the electrical signals to achieve automatic recognition of the letters in a word of the text on the basis of an integration of (a) channel characteristics in the form of probabilities that the particular letter is a corruption of another letter, (b) the probabilities of the letter occurring serially with other recognized letters that precede the letter being analyzed, and (c) lexical information in the form of acceptable words represented as a graph structure and presenting as output a reproduction of the text introduced and analyzed.

Claims

1. A single-pass system to achieve automatic recognition of text, that comprises:

means to read the text and to generate electrical signals derived from the text read, which electrical signals are the electrical analog of words in the text;

analysis means connected to receive the electrical signals and operable to achieve automatic recognition of the individual letters in a word on the basis of the combination of

a. channel characteristics in the form of probabilities of the observed electrical signal given that true state of nature is each of the possible letters,

b. the probabilities of the letter occurring serially with other recognized letters that precede the letter being analyzed, and

c. lexical information in the form of acceptable words represented as a graph structure; and

means to present a reproduction of the text so read and analyzed.

2. A system according to claim 1 in which the means to read is an optical character reader.

3. A system according to claim 1 in which the analysis means is further operable to achieve a posteriori recognition of whole words of the text.

4. A system according to claim 1 in which the means to present is a printer.

5. A system according to claim 1 in which the means to present is operable to present the input information as an output of audible, understandable sound.

6. A system according to claim 1 in which the means to read is a scanner which converts the input text to said electrical signals that characterize the letters of words in the text.

22. A system according to claim 1 in which said analysis means employs the viterbi algorithm to establish the probability that particular signals are the electrical analog of a particular word and in which the lexical information is in the form of a trie structure that contains a dictionary of acceptable words and which is accessed each time the viterbi algorithm establishes said probability.

7. A system to achieve automatic language recognition, that comprises:

means to receive the language as input in the form of structures or feature sets and to provide electrical signals derived from the structures or feature sets received, which electrical signals are electrical representations of symbols in the language so received; and

analysis means connected to receive the electrical signals and operable to achieve automatic recognition of the individual symbols in the input information on the basis of the combination of

a. channel characteristics in the form of probabilities of observing the particular symbol given that the true state of nature is each of the different possible letters;

b. the probabilities of the particular symbol occurring serially with other recognized symbols that precede the symbol being analyzed; and

c. lexical information in the form of acceptable structures represented as a graph structure.

13. A system according to claim 7 in which said analysis means employs the viterbi algorithm to establish the probability that particular signals are the electrical analog of a particular word and in which the lexical information is in the form of a trie structure that contains a dictionary of acceptable words and which is accessed each time the viterbi algorithm establishes said probability.

14. A system according to claim 13 in which said viterbi algorithm selects the shortest path through a directed graph having nodes and edges, said nodes being established by selecting letter a posteriori probabilities that correspond to said signals and which are above a predetermined threshold, said edges being established by selecting transitional probabilities which correspond to said nodes.

15. A system according to claim 14 in which said viterbi algorithm constructs said graph in the form of a trellis having a plurality of paths, said trellis comprising nodes representing log letter a posteriori probabilities and edges representing log transitional probabilities and wherein the cost of a path through said trellis is the sum of said node probabilities and said edge probabilities along said path, wherein the lowest probability of error in said signals corresponds to the shortest path through said trellis, said shortest path thereby being selected by said viterbi algorithm.

16. A system according to claim 15 in which the nodes of said trellis are established by selecting only nodes which correspond to said particular signals for which the sum of said signal'"'"'s log confusion and log unigram probabilities are among a predetermined number of the highest such sums for that particular signal.

17. A system according to claim 15 in which the nodes of said trellis are established by selecting only those nodes which correspond to signals having a probability of error above a predetermined threshold value.

18. A system according to claim 14 wherein said nodes are established by selecting a predetermined number of the highest letter a posteriori probabilities that correspond to said signals.

19. A system according to claim 14 in which said trie structure considers words as ordered lists of characters, and wherein said trie structure represents elements of said words as nodes in a binary tree so thereby represent a dictionary of allowable words.

20. A system according to claim 18 wherein access to said trie structure at each node of said trellis or graph structure is enhanced by mounting a vector of pointers for accessing said trie structure at a desired location.

8. A method of achieving automatic language recognition, that comprises:

introducing language in the form of strings to a mechanism that converts the same to electrical signals derived from the strings introduced, which electrical signals are the electrical analog of words in the strings;

analyzing the electrical signals to achieve automatic recognition of the individual letters in a word of the text on the basis of an integration of

a. channel characteristics in the form of probabilities that the particular letter is a corruption of another letter;

b. the probabilities of the particular letter occurring serially with other recognized letters that precede the letter being analyzed, and

c. lexical information in the form of acceptable words represented as a graph structure; and

presenting as output a reproduction of the test so introduced and analyzed.

9. A method according to claim 8 in which the output is a printed output.

10. A method according to claim 8 in which the output is an oral output.

11. A method according to claim 8 in which the text is read by an optical character reader and then converted to the electrical signals.

12. A method according to claim 8 in which the strings are introduced as a speech input.

21. A method according to claim 8 in which analyzing the eletrical signals employs the viterbi algorithm to establish the probability that particular signals are the electrical analog of a particular word and in which the lexical information is in the form of a trie structure that contains a dictionary of acceptable words and which is accessed each time the viterbi algorithm establishes said probability.

23. A method according to claim 8 wherein the analyzing is achieved by the Steps, a, b, and c as serial steps.