FINITE STATE TRANSDUCER DETERMINIZING DEVICE AND FINITE STATE TRANSDUCER DETERMINIZING METHOD

• US 20120046935A1
• Filed: 09/13/2011
• Published: 02/23/2012
• Est. Priority Date: 03/30/2009
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation), Toshiba Digital Solutions Corporation (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Nagao, Manabu
• Granted Patent: US 8,744,836 B2
• Time in Patent Office: Days
• US Class Current: 704/8
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G10L 15/144 Training of HMMs

Abstract

According to one embodiment, a finite state transducer determinizing device includes a symbol determination unit, a state merging unit, and a single-value processing unit. The symbol determination unit generates an identification symbol different from an input symbol assigned to each transition of a finite state transducer. The state merging unit extracts one or more states at a transition destination by the same input symbol from among the states of the finite state transducer and generates states having the extracted states as sub-states. The single-value processing unit applies the input symbol assigned to each transition of the finite state transducer or the identification symbol as an input symbol of a transition between the states generated by the state merging unit to perform determinizing.

Claims

1. A finite state transducer determinizing device comprising:

a symbol determination unit that generates an identification symbol different from an input symbol assigned to each transition of a finite state transducer;

a state merging unit that extracts one or more states at a transition destination by the same input symbol from among the states of the finite state transducer and generates states having the extracted states as sub-states; and

a single-value processing unit that applies the input symbol assigned to each transition of the finite state transducer or the identification symbol as an input symbol of a transition between the states generated by the state merging unit to perform determinizing.

2. The device according to claim 1, further comprising a transition generation control unit that defines the state of a transition destination by an input with the identification symbol applied as the state of a transition destination of each of the sub-states.

3. The device according to claim 2, wherein the transition generation control unit defines an input symbol at the time of a transition from the next state of each of the sub-states as an input symbol corresponding to the next state before determinizing.

4. The device according to claim 2 or claim 3, wherein an output symbol from each of the sub-states to the next state includes empty.

5. The device according to claim 1, wherein, when there is a plurality of transitions, which transit by the same input symbol, from among transitions from one or more sub-states in the states generated by the state merging unit, there is a plurality of output symbols by the plurality of transitions, and the states of transition destinations by the plurality of transitions are the same,

the state merging unit generates the states of transition destinations of the plurality of transitions, and

the symbol determination unit applies identification symbols corresponding to the plurality of transitions.

6. The device according to claim 1, wherein the symbol determination unit associates each state generated by the state merging unit and the output symbol of a transition to the corresponding state with an identification symbol of the transition to the corresponding state.

7. The device according to claim 6, wherein the symbol determination unit uniquely determines the identification symbol for each transition from one state.

8. The device according to claim 6, wherein the symbol determination unit uniquely determines the identification symbol for each state associated with the identification symbol and for each output symbol.

9. The device according to claim 1, further comprising a transition selection unit that, when the finite state transducer is a weighted finite state transducer, selects a transition as an optimum path from the transitions corresponding to the identification symbol on the basis of a weight.

10. A finite state transducer determinizing method comprising:

generating an identification symbol different from an input symbol assigned to each transition of a finite state transducer;

extracting one or more states at a transition destination by the same input symbol from among the states of the finite state transducer and generating states having the extracted states as sub-states; and

applying the input symbol assigned to each transition of the finite state transducer or the identification symbol as an input symbol of a transition between the states generated to perform determinizing.