Decoder for searching a digraph and generating a lattice, decoding method, and computer program product

Patent metadata

Field	Value
Publication number	US-9786272-B2
Application number	US-201414574892-A
Country	US
Kind code	B2
Filing date	Dec 18, 2014
Priority date	Dec 24, 2013
Publication date	Oct 10, 2017
Grant date	Oct 10, 2017

Abstract

According to an embodiment, a decoder includes a token operating unit, a node adder, and a connection detector. The token operating unit is configured to, every time a signal or a feature is input, propagate each of a plurality of tokens, which is an object assigned with a state of the of a path being searched, according to a digraph until a state or a transition assigned with a non-empty input symbol is reached. The node adder is configured to, in each instance of token propagating, add, in a lattice, a node corresponding to a state assigned to each of the plurality of tokens. The connection detector is configured to refer to the digraph and detect a node that is connected to a node added in an i-th instance in the lattice and that is added in an i+1-th instance in the lattice.

First claim

What is claimed is:

1. A decoder for searching a digraph and generating a lattice, partially or entirely, corresponding to a signal that is input or corresponding to a feature of the signal, the digraph having an input symbol and an output symbol assigned to a state or a transition, the input symbol being a score identifier that represents at least either an algorithm or data for calculating a signal score from the signal or the feature, the decoder comprising:
a processor that executes instructions that facilitate performance of operations, comprising:
every time the signal or the feature is input, propagating each of a plurality of tokens, which is an object assigned with a state of the head of a path being searched, based on using the digraph to determine that a state or a transition assigned with a non-empty input symbol is reached;
in each instance of token propagating, adding, in the lattice, a node corresponding to a state assigned to each of the plurality of tokens,
as a function of using the digraph, detecting a first node that is connected to a second node added in an i-th instance (where i is an integer equal to or greater than one) in the lattice and that is added in an i+1-th instance in the lattice; and
outputting an output symbol with which the output symbol in the state corresponding to the first node and the output symbol in the state corresponding to the second node are concatenated, when the output symbol being assigned the state, the transition on the digraph detecting the second node connected to the first node, or outputting an output symbol assigned to an arc or the transition and the output symbol in the preceding and succeeding transitions are concatenated, when the output symbol being assigned the transition, the arc generated from the transition and the first node and the second node;
every time the signal or the feature is input for a predetermined number of times, eliminating unnecessary nodes from the lattice.

2. The decoder according to claim 1 , the operations further comprising adding, in the lattice, an arc from the node added at the i-th instance in the lattice to the node added at the i+1-th node in the lattice.

3. The decoder according to claim 2 , the operations further comprising adding the arc in the lattice after completion of adding nodes.

4. The decoder according to claim 1 , the operations further comprising every time the tokens are propagated, calculating, with respect to each of the plurality of tokens, a signal score corresponding to the input symbol assigned to a state or a transition of the head of a path and an accumulation score obtained by accumulating the signal scores in the path.

5. The decoder according to claim 4 , wherein, with respect to each of the node that is added, the operations further comprising associating the signal scores and the accumulation score of the token holding information to generate the node and associating a state of the head of a path represented by the token holding the information.

6. The decoder according to claim 5 , wherein, when the node added in the i-th instance is treated as a first node and the node connected to the first node and added in the i+1-th instance is treated as a second node, the operations further comprising detecting a path in which the accumulation score associated to the second node is identical to the value obtained by adding the accumulation score associated to the first node and the signal score associated to the second node.

7. The decoder according to claim 4 , wherein
the digraph has a weight assigned to a state or a transition, and
with respect to each of the plurality of tokens, the operations further comprising calculating the signal score and calculating an accumulation score obtained by accumulating the weights and the signal scores in a path represented by the token.

8. The decoder according to claim 7 , wherein, with respect to each of the nodes that is added, the operations further comprising associating the signal scores and the accumulation score of the token holding information to generate the node and associating a state of the head of a path represented by the token holding the information.

9. The decoder according to claim 8 , wherein, when the node added in the i-th instance is treated as a first node and the node connected to the first node and added in the i+1-th instance is treated as a second node, the operations further comprising detecting a path in which the accumulation score associated to the second node is identical to the value obtained by adding the accumulation score associated to the first node, the signal score associated to the second node, and weights in a path connecting the first node and the second node.

10. The decoder according to claim 1 , the operations further comprising:
performing a plurality of token operation processes in parallel to each other;
performing a plurality of duplication elimination processes in parallel to each other;
dividing the plurality of tokens into a plurality of first small sets corresponding to the plurality of token operation processes and distributing, to each of the plurality of token operation processes, tokens included in corresponding first small sets;
collecting a plurality of tokens propagated by the plurality of token operating processes;
dividing the plurality of tokens into a plurality of second small sets corresponding to the duplication elimination processes, and distributing, to each of the plurality of duplication elimination processes, tokens included in corresponding second small sets; and
collecting a plurality of tokens that remain after elimination is performed by the plurality of duplication elimination processes.

11. The decoder according to claim 10 , wherein the operations further comprise putting tokens reaching same state into the second small sets.

12. The decoder according to claim 1 , the operations further comprising:
in parallel calculating, every time the tokens are propagated, a signal score corresponding to the input symbol assigned to a state or a transition of the head of a path represented by the token and an accumulation score obtained by accumulating the signal scores in the path represented by the path;
dividing the plurality of tokens into a plurality of small sets and distributing tokens included in corresponding small set; and
collecting a plurality of tokens for which the signal score and the accumulation score have been calculated.

13. The decoder according to claim 12 , the operations further comprising from among a plurality of tokens reaching same state, keeping a token having best of the accumulation scores.

14. The decoder according to claim 1 , the operations further comprising:
in parallel to each other, eliminating tokens having an accumulation score worse than a certain score;
dividing the plurality of tokens into a plurality of small sets, and distributing tokens included in corresponding small set; and
collecting a plurality of tokens that remain after performance of an elimination.

15. A decoder for searching a digraph and generating a lattice, partially or entirely, corresponding to a signal that is input or corresponding to a feature of the signal, the digraph having an input symbol and an output symbol assigned to a state or a transition, the input symbol being a score identifier that represents at least either an algorithm or data for calculating a signal score from the signal or the feature, the decoder comprising:
a processor that executes instructions that facilitate performance of operations, comprising:
every time the signal or the feature is input, propagati

Assignees

• Toshiba Kk

Inventors

• Nagao Manabu

Classifications

• G06F18/295

  Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models · CPC title

• G10L15/142

  Hidden Markov Models [HMMs] · CPC title

• G10L2015/085

  Methods for reducing search complexity, pruning · CPC title

• G10L2015/081

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

• G10L15/08 Primary

  Speech classification or search · CPC title