ISCA Archive Interspeech 2009
ISCA Archive Interspeech 2009

A generalized composition algorithm for weighted finite-state transducers

Cyril Allauzen, Michael Riley, Johan Schalkwyk

This paper describes a weighted finite-state transducer composition algorithm that generalizes the concept of the composition filter and presents filters that remove useless epsilon paths and push forward labels and weights along epsilon paths. This filtering permits the composition of large speech recognition contextdependent lexicons and language models much more efficiently in time and space than previously possible. We present experiments on Broadcast News and a spoken query task that demonstrate an ¡«5% to 10% overhead for dynamic, runtime composition compared to a static, offline composition of the recognition transducer. To our knowledge, this is the first such system with so little overhead.


doi: 10.21437/Interspeech.2009-348

Cite as: Allauzen, C., Riley, M., Schalkwyk, J. (2009) A generalized composition algorithm for weighted finite-state transducers. Proc. Interspeech 2009, 1203-1206, doi: 10.21437/Interspeech.2009-348

@inproceedings{allauzen09_interspeech,
  author={Cyril Allauzen and Michael Riley and Johan Schalkwyk},
  title={{A generalized composition algorithm for weighted finite-state transducers}},
  year=2009,
  booktitle={Proc. Interspeech 2009},
  pages={1203--1206},
  doi={10.21437/Interspeech.2009-348}
}