Spelled word input directory information retrieval system with input word error corrective searching

• US 4,164,025 A
• Filed: 12/13/1977
• Issued: 08/07/1979
• Est. Priority Date: 12/13/1977
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Inventors: Rosenberg, Aaron E., Dubnowski, John J.
• Primary Examiner(s): Chapnick, Melvin B.
• Application Number:
  US05/860,101
• Time in Patent Office: 602 Days
• Field of Search: 364/900 MS File, 364/200 MS File, 340/146.3 WD, 340/146.3 ED, 179/1 S D
• US Class Current: 715/210
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context
• CPC Class Codes: G10L 15/00 Speech recognition G10L17/00 takes precedence

Abstract

An arrangement for retrieving information from a directory responsive to a sequence of spoken character signals in which a set of probable characters for each character signal is stored in a position ordered array. A candidate word is formed from the most probable characters of the array and the directory is repeatedly searched for words therein which match a candidate word. After each unsuccessful search, the candidate word is modified by selectively substituting array characters for mismatched position characters on the basis of the closest mismatched word found in the preceding search. If there are no more array characters for substitution after an unsuccessful search, a new candidate word is formed by placing an ignore character in the first mismatched position of the best candidate word of all preceding searches. The position of the ignore mismatch character is shifted left each time no further array characters are available for substitution. Responsive to detection of a matching word, a spoken message is generated from the information associated therewith.

Claims

1. A circuit for recognizing a sequence of spelled character signals comprising a directory store for storing a plurality of reference words each having a set of prescribed characters;

means for receiving a sequence of spelled character signals;

means connected to said receiving means responsive to each received spelled character signal for generating a set of probable characters;

means connected to said probable character set generating means for storing a set of probable characters for each spelled character signal in a predetermined position of a position ordered array;

means responsive to the storing of the final character signal probable character set of the sequence for generating a candidate word comprising a probable character from each spelled character position of the array;

means for storing the generated candidate word;

means responsive to the storing of said generated candidate word for generating a first signal;

directory store search means responsive to said first signal for determining directory store reference words which correspond to the sequence of spelled character signals comprising means responsive to the stored candidate word for selecting a sequence of directory store reference words;

means jointly responsive to said selected sequence of directory store reference words and said stored candidate word for comparing the characters of each word of said selected sequence of directory store reference words with the corresponding characters of said stored candidate word in left to right order to detect directory store reference words that match said stored candidate word;

means responsive to the nonmatching directory store reference words of said selected sequence for detecting the rightmost first occurring mismatched position of all nonmatching directory store reference words of the selected sequence;

means jointly responsive to the absence of matching directory store reference words in the selected sequence and said detected mismatched position of said selected sequence for generating a modified candidate word and for storing said modified candidate word in said candidate word storing means;

means responsive to the storing of said modified candidate word for generating a first signal to initiate a succeeding directory store search; and

means responsive to the detection of at least one directory store reference word that matches a stored candidate word in a directory store reference word sequence search for identifying the sequence of spelled character signals as said matching directory words.

2. A circuit for recognizing a sequence of spelled character signals according to claim 1 wherein said modified candidate word generating means comprises means responsive to said rightmost first occurring detected mismatched position for replacing the character in the rightmost first occurring detected mismatched position of the candidate word with another probable character from the corresponding position of the array.

3. A circuit for recognizing a sequence of spelled character signals according to claim 2 wherein said modified candidate word generating means further comprises means responsive to the absence of another probable character in the array position corresponding to the detected mismatched position for generating a second signal;

means responsive to said second signal for shifting the detected mismatched position left to the next array position in which there is another probable character for substitution; and

means for substituting said other probable character in the shifted detected mismatched position of the array for the character in the shifted detected mismatched position of the candidate word.

4. A circuit for recognizing a sequence of spelled character signals according to claim 3 wherein said directory store search means further comprises means for detecting the rightmost first occurring mismatched position of the current and all preceding directory store selected reference word sequence searches;

means for storing the best candidate word corresponding to said detected rightmost first occurring mismatched position of the current and all preceding directory store selected reference word sequence searches; and

wherein said modified candidate word generating means further comprises means responsive to the absence of another probable character in the leftmost position of the array for generating a third signal; and

means responsive to said third signal for forming a modified candidate word from said best candidate word by replacing the character of said best candidate word in said rightmost first occurring mismatched position of all preceding directory store selected reference word sequence searches with an ignore mismatch character.

5. A circuit for recognizing a sequence of spelled character signals according to claim 4 wherein said modified candidate word generating means further comprises means jointly responsive to the absence of another probable character for substitution in the leftmost position of the array and the presence of an ignore mismatch character in the stored candidate word for generating a fourth signal;

and means responsive to said fourth signal for forming a modified candidate word by shifting said ignore mismatch character to the adjacent left position of the stored candidate word.

6. A circuit for recognizing a sequence of spelled character signals according to claim 5 wherein said modified candidate word generating means further comprises means jointly responsive to the ignore mismatch character being in the leftmost position of the stored candidate word and the absence of a probable character for substitution in the next to leftmost position of the array for terminating said directory store selected reference word sequence searches.

7. A circuit for recognizing a sequence of character signals comprising a directory store for storing a plurality of reference words, each reference word including a set of prescribed character codes;

means for receiving a sequence of character signals;

means responsive to each received character signal for generating a set of probable character codes;

an array of character set registers, each register being responsive to said probable character code set generating means for storing a set of probable character codes in most to least probable order;

said probable character code sets being stored in left to right order in said character set register array;

said character code set corresponding to the first character signal of the sequence being in the leftmost position register;

means responsive to the storing of the character set corresponding to the final character signal of the sequence for generating a candidate word comprising the most probable character of each position register of the array;

means for storing said candidate word;

means responsive to the storing of said candidate word for generating a first signal;

directory store search means responsive to said first signal for determining directory store reference words which correspond to said sequence of character signals comprising means responsive to the stored candidate word for selecting a sequence of directory store reference words;

means for comparing the character codes of each directory store reference word of the selected sequence with the corresponding character codes of the stored candidate word in left to right order to detect matching directory store reference words;

means responsive to the nonmatching directory store reference words of said selected sequence for detecting the rightmost first occurring mismatched position of all nonmatching directory store reference words;

means jointly responsive to the absence of matching directory store reference words in the selected sequence and the detected mismatched position of the selected sequence for generating a modified candidate word and for storing said modified candidate word in said candidate word storing means, means responsive to the storing of said modified candidate word for generating a first signal to initiate a succeeding directory store search; and

means responsive to the detection of at least one matching directory store reference word in a directory store search for identifying the sequence of character signals as said detected matching directory store reference words.

8. A circuit for recognizing a sequence of character signals according to claim 7 wherein each character signal is a spoken character signal.

9. A circuit for recognizing a sequence of character signals according to claim 7 wherein said modified candidate word generating means comprises means responsive to said detected rightmost first occurring mismatched position for forming a modified candidate word by substituting the next most probable character code from the detected rightmost first occurring mismatched position register of the array in the detected mismatched position of the candidate word.

10. A circuit for recognizing a sequence of character signals according to claim 9 wherein said modified candidate word forming means comprises means responsive to the absence of a next most probable character code in said detected mismatched position register of the array for generating a second signal, means responsive to said second signal for replacing the most probable character code from the detected mismatched position register of the array in the corresponding position of the candidate word, means responsive to said second signal for shifting said detected mismatched position left to the next position register of the array having a next most probable character code, and means responsive to said second signal for substituting said next position register next most probable character code in the corresponding position of the candidate word.

11. A circuit for recognizing a sequence of character signals according to claim 10 wherein said directory store search means further comprises means for detecting the rightmost first occurring mismatched position of the current and all preceding directory store selected reference word sequence searches;

means for storing the candidate word of the directory store reference word sequence search in which said rightmost first occurring mismatched position of the current and all preceding directory search operations is detected as the best candidate word; and

said modified candidate word forming means further comprises means responsive to the absence of a next most probable character code in the leftmost position register of the array for generating a third signal; and

means responsive to said third signal for forming a modified candidate word from said best candidate word by substituting an ignore mismatch character in said rightmost first occurring mismatched position of all preceding directory store selected reference word sequence searches in the corresponding position of said best candidate word.

12. A circuit for recognizing a sequence of character signals according to claim 11 wherein said modified candidate word forming means further comprises means jointly responsive to the absence of a next most probable character code in the leftmost position register of the array and an ignore mismatch character code in the stored candidate word of the preceding directory store selected reference word sequence search for generating a fourth signal;

and means responsive to said fourth signal for forming a modified candidate word by replacing the ignore mismatch character code in the candidate word of the preceding directory search with the most probable character code of that position register of the array and placing the ignore mismatch character code in the adjacent left position of the stored candidate word of the preceding directory store selected reference word sequence search.

13. A circuit for recognizing a sequence of character signals according to claim 12 wherein said modified candidate word forming means further comprises means jointly responsive to the ignore mismatch character code being in said leftmost position of the stored candidate word of the preceding directory store selected reference word sequence search and the absence of a next most probable character code in the next to leftmost position register of the array for inhibiting succeeding directory store selected reference word sequence searches.

14. A circuit for retrieving information from a directory in response to a sequence of spoken characters comprising a directory store for storing reference words, each reference word comprising a set of prescribed characters and each reference word addressing associated information in said directory store;

means for receiving a sequence of spoken character signals;

means responsive to each received spoken character signal for generating a set of probable characters;

means connected to said probable character set generating means for storing each set of probable characters in most to least probable order for said spoken character signal in a predetermined position of a left to right position ordered array;

means responsive to the storing of the final probable character set of the sequence for generating a candidate word comprising the most probable character of each position of the probable character set array;

means for storing said candidate word;

means responsive to the storing of said candidate word for generating a first signal;

directory store search means responsive to said first signal for searching said directory store to determine directory store reference words corresponding to the sequence of spoken characters comprising means responsive to the stored candidate word for selecting a sequence of directory store reference words;

means for comparing each directory store reference word of the selected sequence with the stored candidate word in a left to right character sequence to detect directory store reference words that match said stored candidate word;

means responsive to the nonmatching directory store reference words of the selected sequence for detecting the rightmost first occurring mismatched position of all nonmatching directory store reference words of the selected sequence;

means jointly responsive to the absence of a detected matching directory store reference word in said selected sequence and the detected rightmost first occurring mismatched position of said selected sequence for generating a modified candidate word and for storing said modified candidate word in said candidate word storing means;

means responsive to the storing of said modified candidate word for generating a first signal to initiate a next directory store reference word search;

means responsive to the detection of at least one matching directory store reference word in a selected sequence for retrieving the associated information of each detected matching directory store reference word; and

means for forming a spoken message corresponding to said associated information.

15. A circuit for retrieving information from a directory in response to a sequence of spoken characters in accordance with claim 14 wherein said modified candidate word generating means comprises means responsive to said detected mismatched position for substituting the next most probable character in the detected mismatched position of the array in the detected mismatched position of the candidate word.

16. A circuit for retrieving information from a directory in response to a sequence of spoken characters in accordance with claim 15 wherein said modified candidate word generating means further comprises means responsive to the absence of a next most probable character in the detected mismatched position of the array for generating a second signal;

means responsive to said second signal for replacing the character in said detected mismatched position of the candidate word with the most probable character of said detected mismatched position of the array;

means for shifting the detected mismatched position left to the next left position of the array in which there is a next most probable character for substitution; and

means for substituting said next most probable character in said next left position of the array for the character in said next left position of the candidate word.

17. A circuit for retrieving information from a directory in response to a sequence of spoken characters in accordance with claim 16 wherein said directory store search means further comprises means for detecting the rightmost first occurring mismatched position of the current and all preceding directory store selected reference word sequence;

means for storing the best candidate word corresponding to said detected rightmost first occurring mismatched position of the current and all preceding directory store selected reference word sequence searches; and

wherein said modified candidate word generating means further comprises means responsive to the absence of a next most probable character in the leftmost position of the array for substitution for generating a third signal;

means responsive to said third signal for forming a modified candidate word from said best candidate word by replacing the character in said detected rightmost first occurring mismatched position of all preceding directory searches of the best candidate word with an ignore mismatch character.

18. A circuit for retrieving information from a directory in response to a sequence of spoken characters in accordance with claim 17 wherein said modified candidate word generating means further comprises means responsive to the absence of a next most probable character in the leftmost position of the array and the presence of an ignore mismatch character in the stored candidate word of the immediately preceding directory store search for generating a fourth signal;

and means responsive to said fourth signal for forming a modified candidate word by replacing the ignore mismatch character in the stored candidate word of the immediately preceding directory store search with the most probable character of that position in the array and placing the ignore mismatch character in the adjacent left position of the stored candidate word of the preceding directory store search.

19. A circuit for retrieving information from a directory in response to a sequence of spoken characters in accordance with claim 18 wherein said modified candidate word generating means further comprises means jointly responsive to the ignore mismatch character being in the leftmost position of the stored candidate word and the absence of a next most probable character in the next to leftmost position of the array for forming a spoken message corresponding to the absence of matching directory words.

20. In a circuit for retrieving information from a directory in response to a sequence of spoken character signals including a directory store for storing a plurality of reference words addressing associated information and said associated information;

means for receiving a sequence of spoken character signals;

a character position ordered array; and

a trial word store;

a method for recognizing said sequence of spoken character signals comprising the steps of generating a set of probable characters for each spoken character signal responsive to the sequence of received spoken character signals;

storing a set of probable character signals in most to least probable order for each received spoken character signal in a predetermined position of said position ordered array;

responsive to the storing of the final probable character set for said sequence, generating a trial word comprising the most probable character from each array position;

storing said generated trial word in said trial word store;

responsive to the storing of said generated trial word, generating a first signal;

responsive to said first signal, searching said directory store to determine reference words which correspond to the sequence of received spoken character signals including selecting a sequence of directory store reference words responsive to said stored trial word;

comparing the characters of each directory store selected sequence reference word with the corresponding probable characters of said stored trial word in left to right order to detect directory store selected sequence reference words which match said stored trial word;

detecting the rightmost first occurring mismatched position in all the non-matching reference words of the directory store selected sequence;

generating a modified trial word from the array jointly responsive to the absence of a matching reference word in said directory store selected sequence and said detected rightmost first occurring mismatched position;

storing said modified trial word in said trial word store;

generating a first signal to initiate a next directory store searching step responsive to the storing of said modified trial word;

retrieving the associated information of each detected matching directory store reference word responsive to the detection of at least one matching reference word in a directory store selected sequence searching step; and

forming a spoken message corresponding to said matching directory store reference words and said associated information.

21. A method for retrieving information from a directory storing a plurality of words addressing associated information and said associated information responsive to a sequence of spoken character signals according to claim 20 wherein the generation of the modified trial word comprises substituting the next most probable character from the detected mismatched position of the array in the detected mismatched position of the stored trial word.

22. A method for recognizing a sequence of spoken character signals according to claim 21 wherein the generation of the modified trial word further comprises forming a second signal responsive to the absence of a next most probable character in said detected mismatched position of the array;

replacing the character in said detected mismatched position of the stored trial word with the most probable character of the detected mismatched position of the array responsive to said second signal;

shifting the detecting mismatched position left to the next left position in which there is a next most probable character in the array for substitution responsive to said second signal; and

substituting said next most probable character in said next left position of the array in the next left position of the stored trial word responsive to said second signal.

23. A method for recognizing a sequence of spoken character signals according to claim 22 wherein said directory store searching step further comprises detecting the rightmost first occurring mismatched position of the current and all preceding directory searches and storing the best trial word corresponding to said detected rightmost first occurring mismatched position of the current and all preceding directory searches;

and wherein the generation of the modified trial word further comprises forming a third signal responsive to the absence of a next most probable character in the leftmost position of the array;

forming a modified trial word from said best trial word by replacing the character in said detected rightmost first occurring mismatched position of all preceding directory store selected sequence reference word searches in the best trial word with an ignore mismatch character responsive to said third signal.

24. A method for recognizing a sequence of spoken character signals according to claim 23 wherein the generation of the modified trial word further comprises forming a fourth signal responsive to the absence of a next most probable character for substitution in the leftmost position of the array and the presence of an ignore mismatch character in the stored trial word;

and forming a modified trial word by replacing the ignore mismatch character in the stored trial word with the most probable character of that position in the array and placing the ignore mismatch character in the adjacent left position of the stored trial word responsive to said fourth signal.

25. A method for recognizing a sequence of spoken character signals according to claim 24 wherein the generation of the modified trial word further comprises forming a spoken message corresponding to the absence of matching directory store selected sequence reference words responsive to the ignore mismatch character being in the leftmost position of the stored trial word and the absence of a next most probable character in the next to leftmost position of the array.

26. A directory assistance system comprising a directory store for storing a plurality of subscriber names addressing associated subscriber information;

means for recognizing a sequence of spoken character signals spelling a subscriber name comprising means for receiving a sequence of spoken character signals, means responsive to said received spoken character signals for generating a set of probable characters for each spoken character signal;

means connected to said probable character set generating means for storing each set of probable characters in most to least probable order in a predetermined position of a position ordered array;

means responsive to the storing of the final probable character set of the sequence for generating a candidate name comprising the most probable character of each position of the array;

means for storing said candidate name;

means responsive to the storing of said candidate name for generating a first signal;

directory store search means responsive to said first signal for determining subscriber names corresponding to the sequence of spoken character signals comprising means responsive to said stored candidate name for selecting a sequence of directory store subscriber names;

means for comparing the characters of each directory store selected sequence subscriber name with the corresponding characters of the stored candidate name in left to right order to detect directory store selected sequence subscriber names that match said stored candidate name;

means responsive to the nonmatching names of the selected sequence of directory store subscriber names for detecting the rightmost first occurring mismatched position of all nonmatching subscriber names of the selected sequence of directory store subscriber names;

means jointly responsive to the absence of matching subscriber names in the selected sequence of directory store subscriber names and the detected mismatched position for generating a modified candidate name and for storing said modified candidate name in said candidate name storing means;

means responsive to the storing of said modified candidate name for generating a first signal to initiate a next directory store search;

means responsive to the detection of at least one matching subscriber name in a selected sequence of directory store subscriber names for retrieving the associated information for each matching subscriber name; and

means for forming a spoken message corresponding to each matching subscriber name and the associated subscriber information.

27. A directory assistance system according to claim 26 wherein said modified candidate name generating means comprises means responsive to said detected mismatched position for substituting the next most probable character in the detected mismatched position of the array for the character in the detected mismatched position of the stored candidate name.

28. A directory assistance system according to claim 27 wherein said modified candidate name generating means further comprises means responsive to the absence of a next most probable character in the detected mismatched position of the array for substitution for generating a second signal;

means responsive to said second signal for replacing the character in said detected mismatched position of the stored candidate name with the most probable character of the detected mismatched position of the array;

means for shifting the detected mismatched position left to the next left position of the array in which there is a next most probable character for substitution; and

means for substituting said next most probable character in said next left position of the array for the character in said next left position of the stored candidate name.

29. A directory assistance system according to claim 28 wherein said directory store search means further comprise means for detecting the rightmost first occurring mismatched position of the current and all preceding directory store searches;

means for storing the best candidate name corresponding to the detected rightmost first occurring mismatched position of the current and all preceding directory store searches; and

wherein said modified candidate name generating means further comprises means responsive to the absence of a next most probable character in the leftmost position of the array for generating a third signal; and

means responsive to said third signal for forming a modified candidate name from the best candidate name by replacing the character in the detected rightmost first occurring mismatched position of all preceding directory searches in said best candidate name with an ignore mismatch character.

30. A directory assistance system according to claim 29 wherein said modified candidate name generating means further comprises means responsive to the absence of a next most probable character in the leftmost position of the array for substitution and the presence of an ignore mismatch character in the stored candidate name for generating a fourth signal;

and means responsive to said fourth signal for modifying the stored candidate name by replacing the ignore mismatch character with the most probable character of that position of the array and placing the ignore mismatch character in the adjacent left position of the stored candidate name.

31. A directory assistance system according to claim 30 wherein said modified candidate name generating means further comprises means jointly responsive to the ignore mismatch character being in the leftmost position of the stored candidate name and the absence of a next most probable character in the next to leftmost position of the array for forming a spoken message corresponding to the absence of matching directory names in said directory.