FSA tool

FSA is an efficient and flexible toolkit to create, manipulate and optimize finite-state automata. It supports weighted and unweighted automata as well as transducers and is designed to use on-demand computations in order to keep memory footprint as low as possible. It may be used to model various problems from the field of natural language processing.

Usage:

fsa [OPTION(S)] <FILE | OPERATION> ...

options:

--help : show help

--progress=yes : show progress during operations

--resources=yes : print resource database

The tool maintains a stack of automata. Passing a file will put the automaton on top of the stack. Operations will take the automata from the top of the stack, and push the result back on top of it.

Operations

Algorithms

parameters and defaults in brackets, use e.g. closure,kleene or nbest,n=100

best : extract [n(1)] best path(s)

closure : [kleene] closure of the topmost automaton

collect : collect each arc weight and [value]

concat : concat the [n(2)] topmost automata

complement : automaton that represents the complement language

compose : compose the two topmost automata [filter=(match),seq]

determinize : determinize topmost automaton [disambiguate]

difference : build the difference of the topmost and second topmost automaton

duplicate : duplicate topmost automaton

extend : extend each arc weight by [value]

expm : weight –> exp(-weight)

invert : swap input and output labels

levenshtein : calculates the levenshtein distance of the two topmost automata

map-input : map input labels using output alphabet of second topmost automaton

map-output : map output labels using input alphabet of second topmost automaton

multiply : multiply each arc weight by [value] (log and tropical semiring only)

minimize : minimize topmost automaton

normalize : normalizes state ids of topmost automaton (i.e. initial = 0, no gaps)

partial : partial automaton starting at state [id]

permute : permute automaton with a window of [n=(infinity)], [type=(ibm),inv,itg,local],

[prob=(0.0)] : OR [dist=(0.0)] with a maximum distortion of [max=(dist> 0 ? 20 : infinity)]

posterior : calculate arc posterior weights

posterior64 : calculate arc posterior weights (numerically more stable version for log semiring)

posteriorE : calculate arc posterior weights with expectation semiring

project : project [type=(input),output] labels to input labels

prune : prune arcs using path posterior weights [beam] threshold

push : push weights [to=(final),initial] state

random : select a random path

remove : remove [type=(epsilons),disambiguators] from topmost automaton

remove : remove arcs with disambiguation symbols or replace by epsilons

sort : sort all edges by [(arc),input,output,weight]

sync-prune : prune states using synchronuous state potentials and [beam] threshold

transpose : reverse the direction of all arcs

trim : removes all but the connected and disconnected states

unite : unite the [n(2)] topmost automata

fuse : fuse initial states of the [n(2)] topmost automata

Output

draw : write topmost automaton to [file=(-)] in dot format [best,detailed]

write : write topmost automaton or [input,output] alphabet (both input and output is possible, too) or only the states [states] to [file=(-)]

Control

cache : caches states of topmost transducer

copy : creates a static copy of the topmost transducer

delete : delete topmost transducer

default : set the default semiring for all following read operations (see list below)

semiring : change the semiring of the topmost automaton (see list below)

Diagnostics

count : [(input),output] arc count statistics for [label] or number of [paths]

info : print sizes of topmost automaton

memory : print detailed memory info of topmost automaton

time : print time consumed by preceeding operation

wait : wait for pressing <ENTER>

Semirings

count, log, probability, tropical, tropical-integer

tolerance=(1) for log

File formats

prepend att: / bin: / lin: / xml: / trxml: in order to select file format

packed: for compressed storage

combine to combine automata from different files

Examples

Plotting a binary fsa:

fsa bin:input.binfsa draw | dot -Tsvg > out.svg

Compute the top n-best paths in an fsa:

fsa input.fsa best,n=5 write,file=out.fsa

Merge alphabet FSA into other FSA

This is not directly supported, but we can make use of the unite operation:

fsa bin:segment-am.binfsa bin:input-alphabet.binfsa unite trim draw,file=fsa.dot