Decoder, decoding method, and computer program product

Patent metadata

Field	Value
Publication number	US-2015179177-A1
Application number	US-201414574895-A
Country	US
Kind code	A1
Filing date	Dec 18, 2014
Priority date	Dec 24, 2013
Publication date	Jun 25, 2015
Grant date	—

Abstract

According to an embodiment, a decoder searches a finite state transducer and outputs an output symbol string corresponding to a signal that is input or corresponding to a feature sequence of signal that is input. The decoder includes a token operating unit and a duplication eliminator. The token operating unit is configured to, every time the signal or the feature is input, propagate each of a plurality of tokens, which is assigned with a state of the head of a path being searched, according to the finite state transducer. The duplication eliminator is configured to eliminate duplication of two or more tokens which have same state assigned thereto and for which respective previously-passed transitions are assigned with same input symbol.

First claim

What is claimed is:

1 . A decoder for searching a finite state transducer and outputting an output symbol string corresponding to a signal that is input or corresponding to a feature of the signal that is input, the decoder comprising:
a token operating unit configured to, every time the signal or the feature is input, propagate each of a plurality of tokens, which is assigned with a state of the head of a path being searched, according to the finite state transducer; and a duplication eliminator configured to eliminate duplication of two or more tokens which have same state assigned thereto and for which respective previously-passed transitions are assigned with same input symbol.

2 . The decoder according to claim 1 , wherein each of the plurality of tokens holds an input symbol of corresponding previously-passed transition.

3 . The decoder according to claim 1 , wherein each of the plurality of tokens holds information indicating a state assigned thereto.

4 . The decoder according to claim 3 , wherein
each state in the finite state transducer is assigned with a mutually different number, and each of the plurality of tokens holds the number of the state assigned thereto.

5 . The decoder according to claim 1 , wherein
each of the plurality of tokens is stored in an array, and the duplication eliminator is configured to
rearrange the plurality of tokens, which is recorded in the array, in such a way that the tokens which have same state assigned thereto and for which respective previously-passed transitions are assigned with same input symbol are placed next to each other,
compare adjacent tokens from among the plurality of tokens recorded in the array, and
detect two or more tokens which have same state assigned thereto and for which respective previously-passed transitions are assigned with same input symbol.

6 . The decoder according to claim 5 , wherein
the input symbols are integers, and the decoder further comprises a sorter configured to sort the plurality of tokens by performing a bucket sort with respect to assigned states and the input symbols.

7 . The decoder according to claim 1 , further comprising:
a score calculator configured to, with respect to each of the plurality of tokens, calculate a signal score based on the input symbol of corresponding previously-passed transition; and a sorter configured to sort the plurality of tokens with the input symbols of the previously-passed transition as a key, wherein for each input of a signal sequence or a feature sequence of the signals, the score calculator calculates the signal score once for each of the input symbols.

8 . The decoder according to claim 1 , wherein
the duplication eliminator is configured to
calculate, with respect to each of the plurality of tokens, a hash value for the assigned state and the input symbol of corresponding previously-passed transition,
compare the hash values that are calculated, and
detect two or more tokens which have same state assigned thereto and for which respective previously-passed transitions are assigned with same input symbol.

9 . The decoder according to claim 1 , wherein
the duplication eliminator is configured to
generate a set of tokens including tokens for which respective previously-passed transitions are assigned with same input symbol,
determine, for each set of tokens, whether the assigned state is identical, and
detect two or more tokens which have same state assigned thereto and for which respective previously-passed transitions are assigned with same input symbol.

10 . The decoder according to claim 9 , further comprising a score calculator configured to, for each of the sets, calculate a signal score based on the input symbol of corresponding previously-passed transition.

11 . The decoder according to claim 1 , wherein
every time the signal or the feature is input, the token operating unit propagates the tokens until a transition having a non-empty input symbol is passed, and the duplication eliminator eliminates duplication of the tokens after the tokens are propagated until a transition having a non-empty input symbol is passed.

12 . The decoder according to claim 1 , wherein the finite state transducer is a weighted finite state transducer.

13 . The decoder according to claim 1 , wherein
the input symbol is a score identifier that indicates at least either an algorithm or data for calculating a signal score from the signal or the feature, and the decoder further comprises a score calculator configured to, with respect to each of the plurality of tokens, calculate a signal score based on the input symbol of respective previously-passed transition.

14 . A decoding method implemented in a computer for searching a finite state transducer and outputting an output symbol string corresponding to a signal that is input or corresponding to a feature sequence of signal that is input, the decoding method comprising:
propagating, every time the signal or the feature is input, each of a plurality of tokens, which is assigned with a state of the head of a path being searched, according to the finite state transducer; and eliminating duplication of two or more tokens which have same state assigned thereto and for which respective previously-passed transitions are assigned with same input symbol.

15 . A computer program product comprising a computer-readable medium containing a program for searching a finite state transducer and outputting an output symbol string corresponding to a signal that is input or corresponding to a feature sequence of signal that is input, the program causing a computer to execute:
propagating, every time the signal or the feature is input, each of a plurality of tokens, which is assigned with a state of the head of a path being searched, according to the finite state transducer; and eliminating duplication of two or more tokens which have same state assigned thereto and for which respective previously-passed transitions are assigned with same input symbol.

Assignees

• Toshiba Kk

Inventors

• Nagao Manabu

Classifications

• G10L15/142

  Hidden Markov Models [HMMs] · CPC title

• G10L15/083 Primary

  Recognition networks (G10L15/142, G10L15/16 take precedence) · CPC title

• G10L2015/081

  Search algorithms, e.g. Baum-Welch or Viterbi · CPC title

• G10L19/00 Primary

  Speech or audio signals analysis-synthesis techniques for redundancy reduction, e.g. in vocoders; Coding or decoding of speech or audio signals, using source filter models or psychoacoustic analysis (in musical instruments G10H) · CPC title