INTERSPEECH 2009
10th Annual Conference of the International Speech Communication Association

Brighton, United Kingdom
September 6-10, 2009

A Generalized Composition Algorithm for Weighted Finite-State Transducers

Cyril Allauzen, Michael Riley, Johan Schalkwyk

Google Inc., USA

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.

Full Paper

Bibliographic reference.  Allauzen, Cyril / Riley, Michael / Schalkwyk, Johan (2009): "A generalized composition algorithm for weighted finite-state transducers", In INTERSPEECH-2009, 1203-1206.