FSA: An Efficient and Flexible C++ Toolkit for Finite State Automata Using On-Demand Computation

FSA: An Efficient and Flexible C++ Toolkit for Finite State Automata Using On-Demand Computation Stephan Kanthak and Hermann Ney Lehrstuhl f¨ur Informatik VI, Computer Science Department RWTH Aachen – University of Technology 52056 Aachen, Germany {kanthak,ney}@informatik.rwth-aachen.de Abstract In this paper we present the RWTH FSA toolkit – an efficient implementation of algorithms for creating and manipulating weighted finite-state automata. The toolkit has been designed using the principle of on-demand computation and offers a large range of widely used algorithms. To prove the superior efficiency of the toolkit, we compare the implemen- tation to that of other publically available toolkits. We also show that on-demand computations help to reduce memory requirements significantly without any loss in speed. To increase its flexibility, the RWTH FSA toolkit supports high-level interfaces to the programming language Python as well as a command-line tool for interactive manipulation of FSAs. Furthermore, we show how to utilize the toolkit to rapidly build a fast and accurate statisti- cal machine translation system. Future extensibility of the toolkit is ensured as it will be publically avail- able as open source software. 1 Introduction Finite-state automata (FSA) methods proved to el- egantly solve many difficult problems in the field of natural language processing. Among the most recent ones are full and lazy compilation of the search network for speech recognition (Mohri et al., 2000a), integrated speech translation (Vidal, 1997; Bangalore and Riccardi, 2000), speech sum- marization (Hori et al., 2003), language modelling (Allauzen et al., 2003) and parameter estimation through EM (Eisner, 2001) to mention only a few. From this list of different applications it is clear that there is a high demand for generic tools to create and manipulate FSAs. In the past, a number of toolkits have been pub- lished, all with different design principles. Here, we give a short overview of toolkits that offer an almost complete set of algorithms: • The FSM LibraryTM from AT&T (Mohri et al., 2000b) is judged the most efficient im- plementation, offers various semirings, on- demand computation and many algorithms, but is available only in binary form with a propri- etary, non commercial license. • FSA6.1 from (van Noord, 2000) is imple- mented in Prolog. It is licensed under the terms of the (GPL, 1991). • The WFST toolkit from (Adant, 2000) is built on top of the Automaton Standard Template Library (LeMaout, 1998) and uses C++ tem- plate mechanisms for efficiency and flexibil- ity, but lacks on-demand computation. Also licensed under the terms of the (GPL, 1991). This paper describes a highly efficient new im- plementation of a finite-state automata toolkit that uses on-demand computation. Currently, it is being used at the Lehrstuhl f¨ur Informatik VI, RWTH Aachen in different speech recognition and translation research applications. The toolkit will be available under an open source license (GPL, 1991) and can be obtained from our website http://www-i6.informatik.rwth-aachen.de. The remaining part of the paper is organized as follows: Section 2 will give a short introduc- tion to the theory of finite-state automata to …

Content truncated to 500 words