- Machine types and their filters
Finite-state machines can be seen as graphs bearing transitions. These transitions can be symbols, couples of symbols, weighted couples or any other objects. Our filters however have been compiled once for all, so that the choice of a filter involves the choice of a transition type.
Four types of filters can be built from WFST sources :
- FSA, finite-state automata (deterministic and non-deterministic with epsilon)
- WFSA, weighted finite-state automata
- FST, finite-state transducers
- WFST, weighted finite-state transducers
Once all the filters for these machines have been built, you can toggle between each type by doing (in src) either :- make install_fsa for FSA
- make install_fst for FST
- make install_wfa for WF(S)A
- make install_wfst for WFST.
Why haven't we made single but generic filters as in FSM ?
First, it is a preliminary version whose goal is to test the template library.
Second, we keep compatible with FSM text file format. To make generic filters, one need necessary to extend FSM text file format with headers giving the type of the machines.
- Symbol file and SYMB environment variable
Once you have chosen on which type of machines you want to work, you need to make sure that a symbol file is accessible in the environment variable $SYMB. A symbol file is shipped with WFST package symbol/symbols.syms. It maps symbols to integer. If you want to add a symbol, add it at the end of the file and increment the index. Note that the first four symbols are reserved and must be included in any symbol file. (epsilon, default, eps1, eps2)
It is required to set the SYMB environment variable to the path where symbols.syms is located.
For example, you can edit your .bash_profile and add the following line:
export SYMB="/YOUR_INSTALL_PATH/symbol/symbols.syms" (bash)
set SYMB="/YOUR_INSTALL_PATH/symbol/symbols.syms" (csh)
Test the variable, cat $SYMB should show a non-empty file.
- File format
A line can be either
- a transition ex : 1 2 a transition from state 1 to state 2 with transition label b see example below.
- a final state ex: 2
In case of couples or weighted couples, additional information is added at the end of the line. ex: 1 2 a b 0.5 stands for transition (a:b/0.5) from 1 to 2. See other examples below :
Machine Graph Text file Command FSA 
fsa.txt ASTL_compile -i $SYMB fsa.txt >fsa.fsa WFSA 
wfsa.txt ASTL_compile -i $SYMB wfsa.txt >wfsa.wfa FST 
fst.txt ASTL_compile -i $SYMB fst.txt >fst.fst WFST 
wfst.txt ASTL_compile -i $SYMB wfst.txt >wfst.wfst
Please refer to my graduation project report for more information on the algorithms used and graphical examples. Other formats (ps, pdf) are available here
- Input/Output operations
Operation Machines Input Result Command Compilation all text file compiled machine ASTL_compile -i $SYMB in.txt >out.fsm Drawing all compiled machine ATT dot file ASTL_draw -i $SYMB in.fsm >out.dot Printing all compiled machine text file ASTL_print -i $SYMB in.fsm >out.txt
- Unary operations
Operation Machines Input Result Command Closure all fsm fsm ASTL_closure a.fsm >closure.fsm Epsilon-removal (~W)FSA, (~W)FST fsm fsm ASTL_rmepsilon a.fsm >rmeps.fsm Reversal all fsm fsm ASTL_reverse a.fsm >reverse.fsm Connection all fsm fsm ASTL_connect a.fsm >connect.fsm Inversion FST, WFST fsm fsm ASTL_invert a.fsm >invert.fsm Completion all fsm fsm ASTL_complete a.fsm >complete.fsm Determinization FSA, UFST, UWFSA, UWFST fsm Dfsm ASTL_determinize a.fsm >det.fsm Minimization FSA, UFST, UWFSA, UWFST fsm MD(U)fsm ASTL_minimize a.fsm >min.fsm Best path WFSA, WFST fsm fsm ASTL_bestpath a.fsm >bestpath.fsm Projection FST, WFSA, WFST fsm FSA ASTL_project a.fsm >a.fsa
Note : UFST, UWFSA, UWFST are underlying machines that is, automata where each transition is taken as a symbol from a machine transition.
D stands for deterministic and M minimal.
The weighted epsilon-removal will work in most cases but can possibly produce false results in final weights.
- Binary operations
Operation Machines Input Result Command Union all fsms fsm ASTL_union a.fsm b.fsm c.fsm >d.fsm Concatenation all fsms fsm ASTL_concat a.fsm b.fsm c.fsm >d.fsm Intersection FSA, UFST, WFSA, UWFST fsms fsm ASTL_intersect a.fsm b.fsm c.fsm >d.fsm Difference FSA, UFST, WFSA, UWFST D(U)fsms fsm ASTL_difference a.fsm b.fsm c.fsm >d.fsm Composition FST, WFST fsms fsm ASTL_compose a.fsm b.fsm c.fsm >d.fsm Local grammar (layer=3) DAFSAs DAFSAs DAFSA ASTL_applygram a.fsm b.fsm c.fsm >d.fsm
Note : DAFSA stands for deterministic acyclic FSA
input fsms for difference must be deterministic.
It is possible to build finite-state machines from their expressions. ASTLreg uses the machine filters to perform that translation. The program is very flexible though not very efficient as it calls filters at run time and stores temporary results on the disk. However, it is handy for test purposes and non-critical tasks.
ASTLreg processes standard input as A line ended by a carriage return.
Expressions are built from symbols specified symbol file and the following operators (by decreasing order of precedence):
| Operator | Operation |
|---|---|
| [@file] | Reference to a compiled fsm on disk |
| [] | Brackets (force atomic symbol) |
| () | Parentheses |
| * | Kleene closure |
| + | Kleene Plus |
| . | Concatenation (default between two symbols) |
| - | Difference |
| | | Union |
Note : brackets are used to distinguish [yes] symbol (one transition) from y-e-s (letters taken one by one : 3 transitions).
In couples or weighted couples, symbols are assumed : ie: (yes/1) is the weighted symbol [yes].
Some reserved symbols must be placed at the top of the symbol file :
| Symbol | Use | Rank in symbol file | Name in symbol file |
|---|---|---|---|
| Epsilon | Empty string/word transition | 0 | eps |
| Epsilon 1 | Empty string/word transition for composition | 1 | eps1 |
| Epsilon 2 | Empty string/word transition for composition | 2 | eps2 |
| Default | Transition on all symbols except those existing from a state | 3 | /? |
| Stop | No transition allowed | compulsory | /X |
Here are some simple examples :
| Machine | Graph | Expression | Command |
|---|---|---|---|
| FSA | | a*b+ | echo "a*b+" | ASTLreg >fsa.fsa |
| WFSA | | ((a/1)|(b/0))* | echo "((a/1)|(b/0))*" | ASTLreg >wfsa.wfa |
| FST | | (a:b)*(b:c)(b:d)* | echo "(a:b)*(b:c)(b:d)*" | ASTLreg >fst.fst |
| WFST | | (a:A/0.5)*(b:B/0.3)((c:C/0)|(d:D/0.6)) | echo "(a:A/0.5)*(b:B/0.3)((c:C/0)|(d:D/0.6))" >wfst.wfst |
Note : for WFSA and WFST, it is not possible to enter final weights.
The library is shipped with four main test directories :
| Name | Description | Machine type required | Comment |
|---|---|---|---|
| ASTL_DTW | Genetic sequence alignment | WFST | Just an example |
| ASTL_HMM | Viterbi decoding with HMM | WFST | see the main report for details |
| ASTL_grammar | Application of local grammars | FSA, FST, WFST | see the main report for details |
| ASTL_grammar/blois | Application of Blois-Buydens rules | FSA | see the main report and Thierry Dutoit's thesis (LIPSS) for details |
| ASTL_kk | Application of Kaplan and Kay rules | FST, WFST | heavy and non efficient but good test ! |
In order to carry out comparisons, FSM equivalent tests are also provided. In fact, the results of these comparisons are a little biased for fast operations. One should try to implement Mohri and Sproat rule compilation within the library to see how it behaves.
Please refer to ASTL Programming documentation as WFST is only a single ASTL extension made of template algorithms.
If you want to use WFST extension in your own programs, please see ASTL_io.cpp, ASTL_unary_op.cpp and ASTL_binary_op.cpp in src/common. Notice that all headers have been placed in ASTL_lib.h. makefile and makefile.common in src might be of some help.
- ASTL library : Automata Standard Template Library by Vincent LeMaout, Marne-la-Vallée University
- ATT's FSM library : binaries available for Linux and other Unices. (fast)
- ATT's Lextools: tools (binto build expressions and grammars for speech synthesis and NLP. (fast)
- Fire Lite and Spare Parts by Bruce Watson : free C++ library for automata and pattern matching . (fast)
- FSA and U_TR : Jan Daciuk's free C++ library including dictionary for spelling correction and morphology. (good)
- Grail 3.0 : heavy template finite-state machine library for theoretical purposes (slow).
- FSA 6.1 : Prolog and Tk based environment devoted to algorithm researches rather than performance. (very slow but very useful)
- INTEX : a LADL-proprietary software to build corpus, local grammar and dictionaries with FST
- GTL : the Graph Template Library : a related C++ library
- Filters should be extended to support all machines at a time. A change in text file format is therefore needed.
- ASTLreg should use internal function calls to build machines from expressions.
- Epsilon-removal bugs should be fixed. Recent articles (Mohri 2000, Van Noord 1998) provide adequate algorithms
- On-the-fly algorithms have not been implemented in this extension. Most of the operations presented can be performed locally and on several finite-state machines in parallel, rather than sequentially. This could improve speech recognition tasks, genome sequencing through HMM Viterbi decoding
-
Cursors developed at Marne-la-Vallée University (LeMaout and Revuz) are a promising way
to simplify algorithm coding. However, cursors are only available for acyclic and deterministic automata.
. ...
If you have noticed a bug in the library or incorrectness in an algorithm or for any other comments, feel free to contact me at adant@usa.net. Arnaud Adant 2000.