×

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
First Claim
Patent Images

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 gpn (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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×