Syntactic word recognizer

• US 4,156,868 A
• Filed: 05/05/1977
• Issued: 05/29/1979
• Est. Priority Date: 05/05/1977
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Inventors: Levinson, Stephen E.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US05/793,954
• Time in Patent Office: 754 Days
• Field of Search: 179/1 SD, 179/1 SB, 340/146.3 WD, 340/146.3 AQ, 340/146.1 AB, 340/146.3 Q, 340/146.3 R, 340/146.3 SG
• US Class Current: 704/251
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks

Abstract

A syntactic analyzer recognizes a series of spoken words as one of a set of predetermined sequences of prescribed words defined by a state sequence array of state transition signals representing state linked prescribed words. Each sequence corresponds to a selected plurality of linked state transition signals ending in a final state. For each word position of the series, a set of signals representative of the acoustic correspondence between the position word and the array prescribed words is generated. A cumulative correspondence signal is produced from the array state transition signals and the correspondence signals. Upon termination of the last word position, the sequence having the closest cumulative correspondence to the spoken word series is identified.

Claims

1. A method for recognizing a series of words as one of a set of predetermined sequences of prescribed words comprising the steps of (1) storing a set of state transition signals each representative of an initial state, a terminal state and a prescribed word linking said initial and terminal states to define the set of predetermined sequences of prescribed words, each sequence corresponding to a selected plurality of state connected prescribed words ending in a final state;

(2) identifying the word positions of said series;

(3) storing a set of signals representative of the final states of said predetermined sequences as addressed by said identified word positions;

(4) generating a set of signals representative of a correspondence between the series word in each identified word position and said prescribed words;

(5) assigning a time interval to each identified word position of said series;

(6) in each identified word position interval, producing a cumulative correspondence signal for the identified word position of each sequence including selecting the word position correspondence signal associated with each sequence state transition signal prescribed word responsive to the sequence state transition signal in said identified word position, and combining said identified word position selected correspondence signal for each sequence with the sequence selected correspondence signals of the preceding word positions;

(7) upon termination of the last word position interval selecting the sequences in their final states in said last word position responsive to the stored last word position final state signals, and (8) identifying the selected sequence having the closest cumulative correspondence to said series responsive to the last word position cumulative correspondence signals of said selected sequences.

2. A method for recognizing a series of words as one of a set of predetermined sequences of prescribed words according to claim 1 further comprising storing the initial state and prescribed word of each word position sequence state transition signal addressed by the state transition signal terminal state;

and wherein said sequence identifying step comprises identifying the final state of the selected sequence having the minimum last word position cumulative correspondence signal; and

forming a signal representative of the identified sequence from said stored prescribed words responsive to the identified sequence final state and the stored initial states.

3. A method for recognizing a series of words as one of a set of predetermined sequences of prescribed words according to claim 2 wherein said series of words is a series of spoken words, and said correspondence signal generation comprises generating a set of signals for each word position representative of the acoustic similarity between the spoken word of said word position and the prescribed words.

4. A method for recognizing a series of spoken words as one of a set of predetermined sequences of prescribed words comprising the steps of (1) storing a set of state transition signals each representative of an initial state, a terminal state, and the prescribed word linking said initial and terminal states to define the set of predetermined sequences, each sequence corresponding to a selected plurality of state connected prescribed words ending in a final state;

(2) identifying the word positions of said spoken word series;

(3) storing a set of signals representative of the final states of said predetermined sequences as addressed by said identified word positions;

(4) generating a set of signals for each spoken word position representative of the acoustic correspondence between the spoken word of said identified word position and the prescribed words;

(5) assigning a time interval to each spoken word position;

(6) forming a cumulative correspondence signal for each sequence in each word position including selecting the word position correspondence signal associated with the sequence state transition signal prescribed word responsive to each sequence state transition signal, and adding the sequence word position selected correspondence signal to the immediately preceding word position cumulative correspondence signals for said sequence;

(7) upon termination of the last word position interval, selecting the sequences in their final states in said last word position responsive to said stored last word position final state signals; and

(8) identifying the selected sequence having the closest cumulative correspondence to said spoken word series responsive to the last word position cumulative correspondence signals of the selected sequences.

5. A method for recognizing a series of spoken words as one of a set of predetermined sequences of prescribed words according to claim 4 further comprising storing the initial state and prescribed word of each sequence state transition signal addressed by the sequence state transition signal terminal state in said word position;

and wherein said selected sequences identification further comprises identifying the final state of the selected sequence having the minimum last word position cumulative correspondence signal; and

forming a signal comprising the prescribed words of said identified sequence from said stored prescribed words responsive to said identified final state and said stored initial states.

15. Apparatus for recognizing a series of words according to claim 4 wherein said series of words is a series of unknown spoken words, and wherein said correspondence signal generating means comprises means for generating a set of signals representative of the acoustic similarity between each word position spoken word and said prescribed words.

6. A syntactic analyzer for recognizing a series of words as one of a set of syntactically allowable sequences of prescribed words comprising means for storing a set of first signals each including an initial state code, a terminal state code and a prescribed word code linking said initial and terminal state codes, which signals define a set of predetermined syntactically allowable sequences, each sequence corresponding to a selected plurality of state connected prescribed words ending in a final state;

means for generating a signal identifying the word positions of said series;

means for storing a set of signals representative of the final states of said sequences addressed by said identified word positions;

means for generating a set of second signals representative of the similarity between each identified position word and said prescribed words;

means responsive to said word position identifying signal for assigning a time interval to each word position of said series;

means operative in each word position interval for producing a third signal representative of the word position cumulative similarity of each syntactically allowable sequence to said word series including means responsive to each sequence first signal for selecting the word position second signal associated with said sequence first signal prescribed word code, and means for combining the sequence selected word position second signal and the sequence selected second signals of the preceding word positions;

means operative upon termination of the last word position of said series responsive to the last word position stored final state signals for selecting the sequences in their final states in said series last word position; and

means responsive to said last word position third signals for identifying the selected syntactically allowable sequence having the closest cumulative similarity to said word series.

7. A syntactic analyzer for recognizing a series of words as one of a set of syntactically allowable sequences of prescribed words according to claim 6 wherein said combining means comprises means for adding the sequence word position selected second signal and the preceding word position third signal for said sequence to produce the word position third signal for said sequence.

8. A syntactic analyzer for recognizing a series of words as one of a set of syntactically allowable sequences of prescribed words according to claim 7 further comprising means operative in each word position interval responsive to each word position sequence first signal for storing the initial state code and the prescribed word code of said sequence first signal, and wherein said sequence identifying means comprises means responsive to the third signals of the selected sequences for identifying the final state of the selected sequence having the minimum last word position third signal, and means responsive to said identified final state and the stored initial state codes for forming a signal representative of the identified sequence from said stored prescribed words.

9. A syntactic analyzer for recognizing a series of words as one of a set of syntactically allowable sequences of prescribed words according to claim 8 wherein said series of words is a series of spoken words and said second signal generating means comprises means operative for each spoken word position of said series for generating a set of second signals representative of the acoustic similarity between said position spoken word and said prescribed words.

17. Apparatus for recognizing a series of spoken words according to claim 6 wherein said cumulative correspondence signal forming means comprises means operative prior to the first word position interval for forming an initial cumulative correspondence signal for each sequence, means operative in each word position interval responsive to each sequence state transition signal for selecting the correspondence signal associated with the sequence state transition signal prescribed word, and means for adding the sequence cumulative correspondence signal of the immediately preceding word position interval and said word position sequence selected correspondence signal to form the word position cumulative correspondence signal of the sequence.

18. Apparatus for recognizing a series of spoken words according to claim 17 wherein said sequence identifying means further comprises means responsive to the stored prescribed words of said identified sequence in its final state for forming a signal representative of said identified sequence.

10. A speech analyzer for recognizing a series of spoken words as one of a set of predetermined sequences of prescribed words comprising means for storing a set of first signals each including an initial state code, a terminal state code and a prescribed word code linking said initial and terminal state codes to define the set of predetermined sequences of prescribed words;

each predetermined sequence corresponding to a selected plurality of state linked first signals beginning in a common starting state and ending in a final state;

means for generating a signal identifying the word positions of said series;

means for storing a set of signals representative of the final states of said predetermined sequences as addressed by said identified word positions;

means for generating a set of second signals representative of the correspondence between each identified position word and said prescribed words;

means responsive to said word position identifying signal for assigning a time interval to each identified word position;

means operative in each word position time interval jointly responsive to the set of first signals and said word position second signals for forming a third signal representative of the cumulative correspondence of each sequence in said word position;

means operative upon termination of the last word position time interval responsive to the stored last word position final state signals for selecting the predetermined sequences in their final states in said last word position; and

means responsive to the third signals of the selected sequences for identifying the selected sequence having the closest cumulative correspondence to said spoken word series.

11. A speech analyzer for recognizing a series of spoken words as one of a set of predetermined sequences of prescribed words according to claim 10 wherein said cumulative correspondence signal forming means comprises first register means addressed by said first signal initial states for storing the third signals of said sequences at the beginning of each word position time interval;

second register means addressed by the first signal terminal states for storing the third signals of said sequences at the end of each word position interval, said starting state position of said first register means being initially set to a first code, all other state positions of said first and second register means being initially set to a selected largest number code, means operative in each word position interval responsive to each first signal for selecting the word position second signal associated with said first signal prescribed word;

means for adding said selected word position second signal to the signal in the position of said first register means addressed by said first signal initial state;

means for comparing the signal from said adding means to the signal in said second register means addressed by said first signal terminal state;

means responsive to said signal from said adding means being less than the signal from said second register means for inserting said adding means signal into the position of said second register means addressed by the first signal terminal state as the word position third signal of the sequence ending in said first signal terminal state, means addressed by said first signal terminal state for storing the first signal initial state and prescribed word, and means for transferring the word position third signals in said second register means at the end of said word position time interval to said first register means and for setting each second register means position to said selected largest number code upon termination of said transfer.

12. A speech analyzer for recognizing a series of spoken words as one of a set of predetermined sequences of prescribed words according to claim 11 wherein said predetermined sequence identifying means further comprises means operative upon the termination of said last word position time interval responsive to the last word position third signals for identifying the final state of the selected sequence having the minimum third signal, and means responsive to the identified final state and the stored initial states for forming a signal representative of the predetermined sequence corresponding to said identified final state from said stored prescribed words.

13. Apparatus for recognizing a series of words comprising, means for generating a set of state transition signals each representative of an initial state, a terminal state and a prescribed word connected between said initial and terminal states to define a set of predetermined sequences of prescribed words, each sequence corresponding to a selected plurality of state connected prescribed words ending in a final state;

means for generating a signal to identify the word positions of said series;

means responsive to said word position identifying signal for generating a set of signals representative of the final states of said predetermined sequences as addressed by said identified word positions;

means for generating a set of signals representative of the correspondence between the word of each identified position of the series and the prescribed words;

means operative for each identified word position for forming a cumulative correspondence signal for each sequence in each word position including means responsive to said word position identifying signal for assigning a time interval to each identified word position, means operative in each word position interval responsive to each sequence state transition signal for selecting the correspondence signal associated with the sequence state transition signal prescribed word, and means for combining said sequence word position selected correspondence signal with the sequence selected correspondence signals of the preceding word positions;

means operative upon termination of the last identified word position interval responsive to said generated last word position final states for selecting the sequences in their final states in said last word position; and

means responsive to the cumulative correspondence signals of the selected sequences for identifying the selected sequence having the closest cumulative correspondence to said series of words.

14. Apparatus for recognizing a series of words according to claim 13 further comprising means operative in each word position time interval for storing the prescribed word of each sequence state transition signal and wherein said selected sequence identifying means further comprises means for producing the selected sequence in its final state having the closest cumulative correspondence to said word series from said stored prescribed words.

16. Apparatus for recognizing a series of spoken words comprising means for storing a set of state transition signals each representative of an initial state, a terminal state, and the prescribed word connected from said initial state to said terminal state to define a set of predetermined sequences of prescribed words, each sequence corresponding to a selected plurality of state connected prescribed words ending in a final state;

means for generating a signal identifying the word positions of said series;

means for storing a set of signals respresentative of the final states of said predetermined sequences as addressed by said identified word position;

means for generating a set of signals representative of the accoustic correspondence between each identified position spoken word and the prescribed words of the stored state transition signals;

means responsive to said word identifying signal for assigning a time interval to each identified spoken word position;

means operative in each identified word position interval for forming a cumulative correspondence signal for each predetermined sequence including means responsive to the state transition signal of each sequence for selecting the correspondence signal associated with the prescribed word of the sequence state transition signal, and means for combining said sequence word position selected correspondence signal with the prior word position correspondence signals for the sequence;

means operative in each word position time interval for storing each sequence state transition signal prescribed word; and

means operative upon termination of the last word position interval responsive to said last word position stored final state signals for selecting the sequences in their final states in said last word position; and

means responsive to the cumulative correspondence signals of the selected sequences for identifying the selected sequence having the minimum cumulative correspondence signal as the series of spoken words.

19. A word recognizer for identifying a series of spoken words comprising first means for storing a set of state transition signals each representative of an initial state, a terminal state and the prescribed word linking said initial and terminal states to define a set of predetermined sequences of prescribed words, each predetermined sequence being represented by a selected plurality of linked state transition signals ending in a final state, all predetermined sequences beginning in a common starting state, means for generating a signal identifying the word positions of said series of spoken words;

means for storing a set of signals representative of the final states of the predetermined sequences as addressed by said identified word positions;

means responsive to each identified spoken word position of said series for generating a set of signals representative of the correspondence between the spoken word in said position and said prescribed words;

second means for storing each corresponding signal addressed by word position and prescribed word;

means responsive to said identifying signal for assigning a time interval to each identified word position of said series;

means operative in each identified word position interval jointly responsive to said state transition signals and said stored correspondence signals for forming a cumulative correspondence signal for each sequence in each word position including means responsive to each sequence state transition signal for adding the stored correspondence signal addressed by the sequence state transition signal prescribed word from said first storing means and the identified word position to the sequence cumulative correspondence signal of the immediately preceding word position to produce a cumulative correspondence signal for the word position of the sequence;

third means operative in each identified word position interval responsive to each sequence state transition signal for storing the sequence state transition signal initial state and prescribed word addressed by the state transition signal terminal state and word position; and

means operative upon termination of the last word position interval for producing the predetermined sequence in its final state in said last word position having the closest cumulative correspondence to said spoken word series comprising means responsive to said stored final state signals of said last word position for selecting the sequences in their final states in said last word position;

means responsive to said selected sequences for identifying the final state of the selected sequence having the minimum last word position cumulative correspondence signal; and

means jointly responsive to said identified final state and said third storing means initial states for retrieving the prescribed words of said closest corresponding selected sequence from said third storing means, and for forming a signal representative of said closest corresponding selected sequence.