*Notice: Parts of this article may be outdated. There are many changes to its API and performance improvements recently in the java fst framework. Please refer to recent articles in Java FST Framework category for the latest info.
*

**Foreword**

This article is the first part of a series of articles on porting openFST[1] in java. OpenFST is an open-source C++ library for weighted finite-state transducers (WFSTs) [1] and having a similar java implementation is a crucial first step for the integration of phonetisaurus g2p into sphinx 4 [2]

This article will briefly review some mathematical background of weighted finite-state transducers describe the current implementation of openFST and then start describing the java implementation which will be completed in articles that will follow.

**1. Weighted finite-state transducers**

Weighted finite-state transducers have been used in speech recognition and synthesis, machine translation, optical character recognition, pattern matching,string processing, machine learning, information extraction and retrieval among others. Having a comprehensive software library of weighted transducer representations and core algorithms is key for using weighted transducers in these applications and for the development of new algorithms and applications. [1]

A weighted finite-state transducer (WFST) is a finite automaton for which each transition has an input label, an output label, and a weight. Figure 1 depicts a weighted finite state transducer: [1]

The initial state is labeled 0. The final state is 2 with final weight of 3.5. Any state with non-infinite final weight is a final state. There is a transition from state 0 to 1 with input label a, output label x, and weight 0.5. This machine transduces, for instance, the string ac to xz with weight 6.5 (the sum of the arc and final weights). [1]

The weights may represent any set so long as they form a semiring. A semiring is specified by a set of values , two binary operations and , and two designated values and . The operation is associative, commutative, and has as identity. The operation is associative, has identity $ and , distributes with respect to , and has as annihilator: for all . If is also commutative, we say that the semiring is commutative. [1]

Table 1 below lists some common semirings. All but the last are defined over subsets of the real numbers (extended with positive and negative infinity). In addition to the familiar Boolean semiring, and the probability semiring used to combine probabilities, two semirings often used in applications are the log semiring which is isomorphic to the probability semiring via the negative-log mapping, and the tropical semiring which is similar to the log semiring except the operation is min. The left (right) string semiring, which is defined over strings, has longest common prefix (suffix) and concatenation as its operations, and has the (extended element) infinite string and the empty string for its identity elements. It only distributes on the left (right). [1]

**2. The openFST C++ library: Representation and Construction**

The motivation for OpenFst was to create a library as comprehensive and efficient as the AT&T FSM [3] Library, but that was an open-source project. We also sought to make this library as flexible and customizable as possible given the wide range of applications WFSTs have enjoyed in recent years. It is a C++ template library, allowing it to be both very customizable and efficient. [1]

In the OpenFst Library, a transducer can be constructed from either the C++ level using class constructors and mutators or from a shell-level program using a textual file representation. [1]

In order to create a transducer using openFST we need first to construct an empty `VectorFst`

: [1]

1 2 | // A vector FST is a general mutable FST VectorFst<StdArc> fst; |

The `VectorFst`

, like all transducer representations and algorithms in this library, is templated on the transition type. This permits customization of the labels, state IDs and weights in a transducer. `StdArc`

defines the library-standard transition representation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | template <class W> class ArcTpl { public: typedef W Weight; typedef int Label; typedef int StateId; ArcTpl(Label i, Label o, const Weight& w, StateId s) : ilabel(i), olabel(o), weight(w), nextstate(s) {} ArcTpl() {} static const string &Type(void) { static const string type = (Weight::Type() == "tropical") ? "standard" : Weight::Type(); return type; } Label ilabel; Label olabel; Weight weight; StateId nextstate; }; |

A `Weight`

class holds the set element and provides the semiring operations. Currently openFST provides many different C++ Template-based implementations like `TropicalWeightTpl`

, `LogWeightTpl`

and `MinMaxWeightTpl`

which extend a base `FloatWeightTpl`

(see float-weight.h for implementation details) and others. Having these Template-based implementations opeFST we need just have a typedef to define a particular `Weight`

such as TropicalWeight:

1 2 | // Single precision tropical weight typedef TropicalWeightTpl<float> TropicalWeight; |

**3. The proposed FST java library**

Based on the above description and on technical implementation differences between C++ and Java, and more specific mostly on a) difference between C++ Templates and Java generics [4] and b) the lack of operation overloads in Java, the initial implementation includes the `edu.cmu.sphinx.fst.weight.Weight<T>`

class, acting basically as a wrapper for the weight’s value, which can be on any type. The `Weight<T>`

class can be extended in order to create more advanced implementations, if needed.

There is also a generics based interface `edu.cmu`

which declares the Plus, Times and Divide semiring operations for a `.sphinx`

.fst.weight.Semiring<W extends Weight<?>>`Weight<?>`

class. In addition, it declares the zero and one elements of the semiring and the `boolean isMember(Weight<?> w)`

method which should be implemented in a way that returns true if w is a member of the semiring set of values () or false if it is not. The `edu.cmu`

class implements this interface in order to create a solid class of a Tropical Semiring based on single-precision `.sphinx`

.fst.weight.TropicalSemiring`Float`

type for storing the weight’s values.

Finaly the `edu.cmu`

package contains a main class for testing the above functionality by instatiating a TropicalSemiring and performing some operations on various Weight values.`.sphinx`

.fst.demos.basic

**4. Conclusion – Future work**

This article tried to describe some basic theoritical background on weighted finite-state transducers, provide a brief description on the openFST architect and foundation classes and finally presented an initial design for the FST java library implementation. Following the general open-source philosophy “perform small commits often” the library is available in CMUShinx’ repository created for the integration of phonetisaurus g2p into sphinx 4. [5]

The next steps is to provide the Arc and Fst classes which over time will be extended to provide the required functionality for the various FST operations needed for my GSoC 2012 project. Hopefully, over time, more functionality will be provided by the community.

**References**

[1] C. Allauzen, M. Riley, J. Schalkwyk, W. Skut, M. Mohri, “OpenFst: a general and efficient weighted finite-state transducer library”, Proceedings of the 12th International Conference on Implementation and Application of Automata (CIAA 2007), pp. 11–23, Prague, Czech Republic, July 2007.

[2] J. Salatas, “Phonetisaurus: A WFST-driven Phoneticizer – Framework Review”, ICT Research Blog, May 2012.

[3] M. Mohri, F. Pereira, M. Riley, “The Design Principles of a Weighted Finite-State Transducer Library”, Theoretical Computer Science, pp. 15-32, 2000.

[4] H. M. Qusay, “Using and Programming Generics in J2SE 5.0”, Oracle Technology Network, 2004, last accessed: 08/05/2012.