CONVERSION DEVICE, PATTERN RECOGNITION SYSTEM, CONVERSION METHOD, AND COMPUTER PROGRAM PRODUCT

摘要

According to an embodiment, a conversion device converts a first automaton into a second automaton, which both are weighted finite state automatons. The first automaton has a boundary of a path assigned with an input symbol, an appearance position of the boundary, and identifiers for identifying paths. The second automaton has path(s) except unnecessary path(s). The device includes a specifying unit and a search unit. The specifying unit is configured to specify, as a start position, a state of the head of a retrieved path in which a combined weight, which is obtained by adding an accumulated weight from an initial state to the state of the head of the retrieved path in the first automaton and a weight of the best path from the state of the head of the retrieved path to a final state, is best. The search unit is configured to search for a path in which a weight from the start position to a final state in the first automaton is best until reaching next boundary.

主权项

1. A conversion device that converts a first automaton into a second automaton, the first automaton being a weighted finite state automaton in which a boundary of a path assigned with an input symbol, an appearance position of the boundary, and identifiers for identifying paths which can be merged together are assigned, the second automaton being a weighted finite state automaton having paths of the first automaton except at least one or more of unnecessary paths, the device comprising:
a specifying unit configured to specify, as a start position, a state of the head of a retrieved path in which a combined weight, which is obtained by adding an accumulated weight from an initial state to the state of the head of the retrieved path in the first automaton and a weight of the best path from the state of the head of the retrieved path to a final state, is best; a search unit configured to, for each of the identifiers, search for a path in which a weight from the start position to a final state in the first automaton is best until reaching next boundary; and a transition register configured to, when a search has reached next boundary from the start position, register, in the second automaton, a new transition corresponding to a start position and a state of the head of a path retrieved as a result of the search.