Openfst 1.2 was just released. One of the big addition is the lookahead composition filters, more details can be found in [2] and [3]. Get the latest source from here . By default the lookahead filters are not built so run configure with all the options.

configure --enable-compact-fsts --enable-const-fsts --enable-far --enable-lookahead-fsts --enable-pdt

Here is quick example of using the lookahead filters to compose two speech recognition transducers, a lexicon L and and language model G. Using these filter it is no possible to determinize the lexicon before composition with G. The advantage is the costly determinization of LG is avoided.

These are the steps to perform an *offline* lookahead compostion. The below assumes a closed lexicon L with auxillary symbols and and n-gram language model G constructed according to [1]. In this case L has 563232 of states and 656819 arcs and G has 997740 states and 4764980 arcs.

First determinize and convert the lexicon to an olabel_lookahead type fst. The save_olabel_pairs options although not shown in the fstconvert help output is valid option for the command.

fstdeterminize l.fst | fstconvert –fst_type=olabel_lookahead –save_relabel_opairs=relabel.txt > lookahead.l.fst

Next relabel the input of the language model to match the lookahead lexicon. The arcsort command will sort the input of language model. The sorting is essential for efficient composition in the following stage.

fstrelabel -relabel_ipairs=relabeltxt g.fst| fstarcsort > relabel.g.fst

Finally compose the L and G machines togeather. The compose tool can automatically detect that the L transducer is a lookahead type and select the optimized filter.

fstcompose lookahead.l.fst sorted.g.fst > lg.fst

Here is the output of fstinfo for lg.fst

# of states 5863514

# of arcs 9630754

# of final states 1

# of input/output epsilons 1414832

# of input epsilons 1904971

# of output epsilons 5863511

# of accessible states 5863514

# of coaccessible states 5863514

# of connected states 5863514

# of strongly conn components 150128

For a comparison a more standard det(LG) cascade.

# of states 6294455

# of arcs 10053167

# of final states 1

# of input/output epsilons 1995247

# of input epsilons 1995247

# of output epsilons 6302523

# of accessible states 6294455

# of coaccessible states 6294455

# of connected states 6294455

# of strongly conn components 168471

The difference in size is party due to the epsilon closure in the non-determinized L transducers.

[1] Mehryar Mohri, Fernando C. N. Pereira, and Michael Riley.

Speech recognition with weighted finite-state transducers.

In Larry Rabiner and Fred Juang, editors, Handbook on Speech Processing and Speech Communication, Part E: Speech recognition. Springer-Verlag, Heidelberg, Germany, 2008.

[2] Cyril Allauzen, Michael Riley, Johan Schalkwyk, A Generalized Composition Algorithm for Weighted Finite-State Transducers, Interspeech 2009.

[3] Cyril Allauzen, Michael Riley and Johan Schalkwyk, Filters for Efficient Composition of Weighted Finite-State Transducer", *Proceedings of the Fifteenth International Conference on Implementation and Application of Automata*, (CIAA 2010), Winnipeg, MB.