DP Matching system for recognizing a string of words connected according to a regular grammar

• US 4,555,796 A
• Filed: 12/09/1982
• Issued: 11/26/1985
• Est. Priority Date: 12/10/1981
• Status: Expired due to Term

• Current Assignee: Nippon Electric Company Limited (NEC Corporation)
• Original Assignee: Nippon Electric Company Limited (NEC Corporation)
• Inventors: Sakoe, Hiroaki
• Primary Examiner(s): Kemeny, E. S. Matt
• Application Number:
  US06/448,088
• Time in Patent Office: 1,083 Days
• Field of Search: 381/41-43, 364/300
• US Class Current: 704/241
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G10L 15/12 using dynamic programming techniques, e.g. dynamic time warping [DTW]

Abstract

A connected word recognition system operable according to a DP algorithm and in compliance with a regular grammar, is put into operation in synchronism with successive specification of feature vectors of an input pattern. In an m-th period in which an m-th feature vector is specified, similarity measures are calculated (58, 59) between reference patterns representative of reference words and those fragmentary patterns of the input pattern, which start at several previous periods and end at the m-th period, for start and end states of the reference words. In the m-th period, an extremum of the similarity measures is found (66, 69, 86), together with a particular word and a particular pair of start and end states thereof, and stored (61-63). Moreover, a particular start period is selected (67, 86) and stored (64). A previous extremum found and stored (61) during the (m-1)-th period for the particular start state found in the (m-1)-th period, is used in the m-th period as a boundary condition in calculating each similarity measure. After all input pattern feature vectors are processed, a result of recognition is obtained (89) by referring to the stored extrema, particular words, particular start states, and particular start periods.

Claims

1. A system responsive to an input sequence of input pattern feature vectors representative of an input string of words selected from a word set of first through N-th words and substantially continuously uttered in compliance with a regular grammar for recognizing said input string as an optimum one of word concatenations, each concatenation being a string of words selected from said word set and cancatenated in compliance with said grammar, said grammar specifying a set of transition rules for said first through said N-th words and a set of final states of said concatenations, the transition rule for an n-th word optionally selected from said word set defining a combination of said n-th word and a state pair consisting of a start and an end state of said n-th word, said system comprising:

a reference pattern memory for memorizing reference pattern feature vectors representative of said first through said N-th words, the reference pattern feature vectors representative of said n-th word being consecutively numbered as first through J-th feature vectors according to utterance of said n-th word;

control means for generating a basic timing signal successively specifying first through I-th periods assigned to the respective input pattern feature vectors, a word specifying signal specifying, while an m-th period is specified as each of said first through said I-th periods, said first through said N-th words, and a state specifying signal specifying, while said m-th period is specified, the state pairs of said first through said N-th words;

similarity calculating means responsive to said input sequence and coupled to said reference pattern memory and said control means for calculating, while said n-th word is specified in said m-th period, a plurality of similarity measures between the input pattern feature vector assigned to said m-th period and said first through said J-th feature vectors;

extremum finding means coupled to said control means and said similarity calculating means for calculating, while said n-th word and each state pair of said n-th word are specified in said m-th period, a recurrence value g_pⁿ (m, q) for said n-th word and said each state pair under a boundary condition iteratively in correspondence to said first through said J-th feature vectors by using the similarity measures calculated for said n-th word before said m-th period, where m represents said m-th period, n represents said n-th word, and p and q represents the start and the end states of said each state pair, for finding, while said m-th period is specified, an extremum T(m, q) of the recurrence values calculated for the words having state pairs including said end state q, and for deciding that particular word and that particular start state of said particular word for which said extremum is found, said boundary condition being given by T(m-1, p);

start period selecting means coupled to said control means and said extremum finding means for selecting, while said m-th period is specified, a particular period from said first through the (m-1)-th periods with reference to said particular start state and said particular word; and

deciding means coupled to said control means, said extremum finding means, and said start period selecting means for deciding the optimum concatenation by referring, after lapse of said I-th period, to the extrema found in said first through said I-th periods, respectively, and to those particular words, those particular start states, and those particular start periods which are decided in said first through said I-th periods.