OpenFst: Racket Bindings🔗ℹ

This package provides Racket bindings for OpenFst, "a library for constructing, combining, optimizing, and searching weighted finite-state transducers (FSTs)" [openfst]. Extensions to OpenFst based on the Python package pynini are also included [pynini].

1 Getting Started🔗ℹ

A weighted finite-state transducers (FSTs) is a type of automata that consists of:

• A set of states, represented by natural numbers. Each state is also assigned a final weight representing the weight of terminating computation in this state (Infinity is used to represent non-final states).

• A set of arcs (or transitions) between states, consisting of a current and a next state, an input and output label, and a weight. labels are integers representing the unicode encoding of characters with 0 representing ε, or no-character.

• A special state designated as the start state, from which computation begins. Empty or non-sane FSTs may lack a start state.

This library provides a high- and low-level interface for interacting with FSTs. The high-level abstract functional interface contains functions over FSTs such as fst-union and fst-compose. The low-level direct interface allows for inspection and stateful mutation of the structure of an FST.

1.1 Example: Thousand Separators🔗ℹ

To do this, we first define an FST that accepts any single digit called digit. Next, we take the closure over this FST with a lower and upper bound of 3. The resulting FST, digits3, will accept only strings of exactly 3 digits and rewrite them unchanged.

(define digit (fst-union "0" "1" "2" "3" "4" "5" "6" "7" "8" "9"))

(define digits3 (fst-closure digit #:lower 3 #:upper 3))

Next we add a comma inserting FST before digits3 and take the Kleene * of this to get digits3*. The resulting FST will accept a string of digits with length divisible by 3 and insert a comma before every 3rd digit. Finally we concatenate this FST with an FST taking 1, 2, or 3 digits representing the leading digit of the number, to produce add-commas-fst.

(define digits3*

(fst-closure (fst-concat (fst-cross "" ",") digits3)))

(define add-commas-fst

(fst-concat (fst-closure digit #:lower 1 #:upper 3)

digits3*))

To actually apply this FST to a string we use fst-compose to implicitly convert the string to an FST itself and then compose that FST with the one we build for thousand separation. Finally, we convert the resulting FST back into a string. For the purposes of this example we do this explicitly, but fst-rewrite wraps this functionality up nicely.

(define (add-commas number-string)

(fst->string

(fst-compose number-string add-commas-fst)))

1.2 Example: Leading Zeros🔗ℹ

To see how weights can be applied to FSTs, consider the problem of removing leading zeros from a number. While this task can be accomplished with an unweighted-FST, introducing weights simplifies the solution.

"007" → "7"

The leading-zero removing transducer is defined as the concatenation of an FST that removes zero or more "0"s and an FST that accepts one or more digits. While the second FST could process the leading "0"s without removing them, this path will have more weight associated with it.

(define leading-0s

(fst-concat (fst-closure (fst-cross "0" ""))

(fst-closure (fst-add-weight digit 1.0) #:lower 1)))

Note that this FST can be composed with the thousand separator from the previous problem into a single new FST. When applying this FST, fst-shortest-path must be used since now multiple computations exist for some strings.

(define cleanup-fst (fst-compose leading-0s add-commas-fst))

(define (cleanup-number number-string)

(fst->string

(fst-shortest-path

(fst-compose number-string cleanup-fst))))

2 Abstract Automata Manipulation🔗ℹ

• (fst-closure fst) is equivalent to the Kleene *.

• (fst-closure fst #:lower 1) is equivalent to the Kleene +.

• (fst-closure fst #:upper 1) is equivalent to the ?.

2.1 File I/O🔗ℹ

Because of the limiations of the interfaces between Racket, C, and C++ these functions work by creating a named temporary file and passing the name of this file to the underlying C++ implementation. This should not be apparent to users of the library, but this approach has not been fully tested on all systems.

2.2 Derived Utilities🔗ℹ

This is accomplished by adding an ε transition to the start of fst with the given weight.

This function has the effect of replacing the input-label of every arc in the input FST with ε.

This function has the effect of replacing the output-label of every arc in the input FST with ε.

3 Direct Automata Access🔗ℹ

3.1 Transition Arcs🔗ℹ

Arcs represent transitions between states in an finite-state transducer. Each arc consists of a in-label, an out-label, a weight, and a next state. Arcs are added to the automata at the states from which they originate.

As an implementation note, arc objects are in fact pointers to underlying C++ objects in foreign memory. From the perspective of the user, however they conform to the struct interface.

4 Limitations🔗ℹ

This library currently only supports x86_64 architecture. Getting it working on different hardware should be as simple as running the build script corresponding to the OS in the lib/ directory of the GitHub Repo, but I haven’t tested this...

While it should not be visible to the consumers of this library, the Windows implementation of this library is using an unofficial port of OpenFST [winfst] because the official OpenFST distribution does not support Windows.

Bibliography🔗ℹ