edu.cmu.sphinx.fst.operations

Class NShortestPaths

java.lang.Object

edu.cmu.sphinx.fst.operations.NShortestPaths

public class NShortestPaths
extends java.lang.Object

N-shortest paths operation. See: M. Mohri, M. Riley, "An Efficient Algorithm for the n-best-strings problem", Proceedings of the International Conference on Spoken Language Processing 2002 (ICSLP '02). See: M. Mohri, "Semiring Framework and Algorithms for Shortest-Distance Problems", Journal of Automata, Languages and Combinatorics, 7(3), pp. 321-350, 2002.

Method Summary

Modifier and Type	Method and Description
static Fst	get(Fst fst, int n, boolean determinize) Calculates the n-best shortest path from the initial to the final state.
static float[]	shortestDistance(Fst fst) Calculates the shortest distances from each state to the final

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

shortestDistance

public static float[] shortestDistance(Fst fst)

Calculates the shortest distances from each state to the final

Parameters:

fst - the fst to calculate the shortest distances

Returns:

the array containing the shortest distances

get

public static Fst get(Fst fst,
                      int n,
                      boolean determinize)

Calculates the n-best shortest path from the initial to the final state.

Parameters:

fst - the fst to calculate the nbest shortest paths

n - number of best paths to return

determinize - if true the input fst will bwe determinized prior the operation

Returns:

an fst containing the n-best shortest paths