×

Pattern matching method, apparatus and computer readable memory medium for speech recognition using dynamic programming

  • US 5,960,395 A
  • Filed: 02/06/1997
  • Issued: 09/28/1999
  • Est. Priority Date: 02/09/1996
  • Status: Expired due to Term
First Claim
Patent Images

1. An apparatus for performing a dynamic programming pattern matching process, the apparatus comprising:

  • input means for inputting a sequence of input patterns representative of an input signal;

    memory means for storing a plurality of sequences of references patterns, each sequence being representative of a reference signal;

    means for processing a current input pattern with respect to at least some of the reference signals in turn, comprising;

    (1) means for defining as active patterns the reference patterns of a current reference signal which are at the end of a dynamic programming path for the current into pattern being processed, each path representing a possible matching between an ordered sequence of reference patterns and an ordered sequence of input patterns ending at said current input pattern, and for listing the active patterns for the current input pattern in a current active list;

    (2) means for storing in a store associated with each active pattern, a cumulative value representative of a score for the dynamic programming path which ends at that active pattern for said current input pattern; and

    (3) means for processing each active pattern of said current reference signal in reverse sequential order, to update said cumulative values and to propagate said dynamic programming paths based on constraints which are placed on the dynamic programming path propagation, said active pattern processing means comprising;

    (A) means for updating the cumulative value stored in the store associated with a current active pattern being processed, using said current input pattern; and

    (B) means for propagating the dynamic programming path associated with the current active pattern, and for listing, if it is not already listed, each reference pattern of the current reference signal, which may be at the end of that dynamic programming path for the succeeding input pattern, in a new active list; and

    wherein said propagating means is controlled using a pointer associated with the current reference signal, which identifies the reference pattern which is the earliest in the sequence of patterns of the current reference signal listed in the new active list, after the processing of the preceding active pattern, such that the propagating means can propagate each dynamic programming path without the need to search the new active list to identify which reference patterns, of the current reference signal, have been listed on the new active list as a result of said active pattern processing means processing preceding active patterns of the current reference signal.

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