Adding a User Defined Fst to OpenFst

In the post I will show how to add user defined Fst type to OpenFst. doesn't go into detail on the process to add a new Fst type. The Fst type is memory mappable immutable transducers and this should allow for the same Fst instance to be shared across processes that load the same Fst.
All the code for the mmap-fst is avaliable in this gist. The implementation of the mmap-fst is contained in the file mmap-fst.h, the wrapper class around the mmap functions is taken from the mozc project. The wrapper supports both *nix and Windows oses, although only the former support the shared objects described in the article. I changed the length type in the Mmap class to allow larger than 2GB files. The MmapFst itself is basically a cut n' paste job on the ConstFst, the main difference is the MmapFst uses the mmap wrapper instead of  array to access the state and arc information.

Given the Fst code we want to make the OpenFst library and existing OpenFst command line tools aware of of the MmapFst type. To achieve this we need the c++ code and the Makefile to construct a shared object. The registration code that is shown below and is very simple

The makefile below will compile the code to a shared object.

The final step is to make sure the shared object is on the LD_LIBRARY_PATH. We can then convert fsts to the mmap type and use it in all the command line tools. For example we can convert an Fst to MmapFst  type by:

fstconvert --fst_typo=mmap < some.fst > mmap.fst

and view fst information by:

fstinfo mmap.fst

fst type                                          mmap
arc type                                         standard
input symbol table                        none

Shortest Paths in Weighted Graphs using a Stack

When computing shortest paths in graph (for example as partof a beam search) it is tempting to apply a pruned recursive algorithm. This is equivalent to performing a generic shortest path algorithm with

last-in first out LIFO queue (a stack). In an un-weighted graph this approachis fine, however in weighted graphs even with positive only weight this algorithm can have exponential worst case complexity.

The generic single source shorestpath algorihtm is shown below[1]. It assumes the input is a graph $G(V,E)$ where $V$ and $E$ denotes the vertices and edges respectively, $e$ is an edge with member $v$ for the destiantion vertex and $w$ for the edge costs,  $d$ is an array of vertex (or state) costs.In the first three lines of the algorithm the array of vertex costs is initialised. The initial state of the graph is added to the queue and the then the main loop of the algorithm is run. We are interested in a stack/lifo queue, therefore the dequeue operation of line seven will remove the last vertex that was added to the queue. The algorithm then process each of the arcs leaving the state and if the destination state is lower we update the cost eleement and either add the destination to the queue or decrease the key if the state is already in the queue. For the stack in this analysis the decrease-key operation does nothing as there are no priorities in this case and we update the statce costs in line ten. (The decrease-key is needed for priority queues).

$d[0] \leftarrow 0$
$\text{for } i = 1 \dots |V| - 1 $
$\hspace{1em} d[i] \leftarrow \infty$
$Q \leftarrow s$
$\text{while } Q \neq \emptyset$
$\hspace{1em} u \leftarrow \text{Dequeue}(Q)$
$\hspace{1em} \text{for } e \in \text{adj}(Q, u)$
$\hspace{1em} \text{if } d[e.v] > d[u] + e.w$
$\hspace{2em} d[e.v] \leftarrow d[u] + e.w$
$\hspace{2em}\text{if } e.v \in Q$
$\hspace{3em}\text{Decrease-key}(Q, e.v, d[e.v])$
$\hspace{3em}\text{Enqueue}(Q, v.e)$

If we use a first-in first-out (FIFO) queue the algorithm becomes equivalent to the
Bellman-ford aglorithm. In the case of priority queue discipline the algorithm corresponds to
Dijkstra algorithm. In the remainder of this article I will explore the SSSP algorithm with a
LIFO queue and will show certain weighted graphs give rise undesirable SSSP running times.

Consider the below graph, the vertex (state) marked 0 is the initial or start state and the double circle is the final or accept vertex (state), although the algorithm is computing the shortest  path from vertex zero to every other vertex we are only interested in the shortest path to state three. On inspection it easy to see the shortest path is to follow all edges with cost 0 that is the path $0\rightarrow1\rightarrow2\rightarrow3$

The below table shows the steps in the algorithm. The first column is the iteration algorithm,
the second column the element popped at that time step, the queue column is the items in the queue at the end of the current iteration and the substituent columns are the vertex costs. Here we see that for our graph that eight pops are required for the this graph as each path that has more edges but a lower
overall costs requires us to re-visit all the subsequent states again.

Time Pop Queue $d[0]$ $d[1]$ $d[2]$ $d[3]$
0 - 0 $0$ $\infty$ $\infty$ $\infty$
1 0 1,2,3 $0$ $0$ $2$ $3$
2 3 1,2 $0$ $0$ $2$ $3$
3 2 1,3 $0$ $0$ $2$ $2$
4 3 1 $0$ $0$ $2$ $2$
5 1 2,3 $0$ $0$ $0$ $1$
6 3 2 $0$ $0$ $0$ $1$
7 2 3 $0$ $0$ $0$ $0$
8 3 $\emptyset$ $0$ $0$ $0$ $0$

Repeating the analysis for a FIFO queue we see that it only necessary to visit each state once.

Time Pop Queue $d[0]$ $d[1]$ $d[2]$ $d[3]$
0 - 0 $0$ $\infty$ $\infty$ $\infty$
1 0 1,2,3 $0$ $0$ $2$ $3$
1 1 2,3 $0$ $0$ $0$ $1$
1 2 3 $0$ $0$ $0$ $0$
1 3 $\emptyset$ $0$ $0$ $0$ $0$
Likewise the algorithm runs in the same time for a priority queue, however, a graph with negative weights can be constructed to yield exponential running time. For example re-weighting the graph as shown below will give the same characteristics as the LIFO queue with positive weights considered earlier

In summary when computing  shortest paths the  LIFO queue is fine if the graph has no weights each state only needs to be visited once. For weighted graphs either a FIFO or priority queue is a better choice, the later having better running time. Although in practise I have observed the FIFO approach consistently performing better. For graphs with negative weighted edges a priority queue can also exhibit exponential worst case running time.

[1] Jeff Erickson, "Algorithms Lecture 19: Shortest Paths", 2011,