Search device, search method, and computer program product

A search method for searching paths of a digraph which has input symbols and weights assigned thereto, the method comprising:

• storing, in a hypothesis storage, one or more hypotheses each representing information which holds an input symbol string and one or more state of the head of each of the paths from which the input symbol string is obtained, the input symbol string being obtained by searching the paths from an initial state of the digraph;
• retrieving, from among one or more hypotheses stored in the hypothesis storage, as a target hypothesis, a single hypothesis for which a weight obtained by addition of a weight of an already-searched path corresponding to each hypothesis and a weight of the best path from the state of the head of concerned path to a final state is the best weight and which holds an input symbol string corresponding to the already-searched path;
• and
• when the retrieved target hypothesis is not a final hypothesis for which the search has been completed up to a final state, generating one or more new hypotheses each holding an input symbol string that is present in a path in which the search has been performed from one or more states held by the target hypothesis until finding a single input symbol, and writing the generated hypotheses in the hypothesis storage, wherein
• the retrieving includes repeatedly retrieving the target hypothesis from the hypothesis storage until a predetermined number of the final hypothesis is retrieved, and
• the generating includes adding, when an outgoing transition from each of one or more states held by the target hypothesis includes an empty transition, to the target hypothesis a state reached by following the empty transition from concerned state and then continuing with the search to generate the one or more new hypotheses.

A computer program product comprising a computer-readable medium containing a program for searching paths of a digraph which has input symbols and weights assigned thereto, the program causing a computer to execute:

• storing, in a hypothesis storage, one or more hypotheses each representing information which holds an input symbol string and one or more state of the head of each of the paths from which the input symbol string is obtained, the input symbol string being obtained by searching the paths from an initial state of the digraph;
• retrieving, from among one or more hypotheses stored in the hypothesis storage, as a target hypothesis, a single hypothesis for which a weight obtained by addition of a weight of an already-searched path corresponding to each hypothesis and a weight of the best path from the state of the head of concerned path to a final state is the best weight and which holds an input symbol string corresponding to the already-searched path;
• and
• when the retrieved target hypothesis is not a final hypothesis for which the search has been completed up to a final state, generating one or more new hypotheses each holding an input symbol string that is present in a path in which the search has been performed from one or more states held by the target hypothesis until finding a single input symbol, and writing the generated hypotheses in the hypothesis storage, wherein
• the retrieving includes repeatedly retrieving the target hypothesis from the hypothesis storage until a predetermined number of the final hypothesis is retrieved, and
• the generating includes adding, when an outgoing transition from each of one or more states held by the target hypothesis includes an empty transition, to the target hypothesis a state reached by following the empty transition from concerned state and then continuing with the search to generate the one or more new hypotheses.