3-Way Composition of Weighted Finite-State Transducers

DOI10.1007/978-3-540-70844-5_27MaRDI QIDQ3602821zbMATH OpenOpenAlexFDO

Authors Cyril Allauzen, Mehryar Mohri

Publication date 12 February 2009

Published in Implementation and Applications of Automata (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0802.1465

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: Composition of weighted transducers is a fundamental algorithm used in many applications, including for computing complex edit-distances between automata, or string kernels in machine learning, or to combine different components of a speech recognition, speech synthesis, or information extraction system. We present a generalization of the composition of weighted transducers, 3-way composition, which is dramatically faster in practice than the standard composition algorithm when combining more than two transducers. The worst-case complexity of our algorithm for composing three transducers $T_1$, $T_2$, and $T_3$ resulting in $T$, ignore{depending on the strategy used, is $O(|T{|}_{Q}d(T_1)d(T_3)+|T{|}_E)$ or $(|T{|}_{Q}d(T_2)+|T{|}_E)$,} is $O(|T{|}_{Q}min(d(T_1)d(T_3),d(T_2))+|T{|}_E)$, where $|cdot{|}_Q$ denotes the number of states, $|cdot{|}_E$ the number of transitions, and $d(cdot)$ the maximum out-degree. As in regular composition, the use of perfect hashing requires a pre-processing step with linear-time expected complexity in the size of the input transducers. In many cases, this approach significantly improves on the complexity of standard composition. Our algorithm also leads to a dramatically faster composition in practice. Furthermore, standard composition can be obtained as a special case of our algorithm. We report the results of several experiments demonstrating this improvement. These theoretical and empirical improvements significantly enhance performance in the applications already mentioned.

Recommendations

• N-WAY COMPOSITION OF WEIGHTED FINITE-STATE TRANSDUCERS
• A filter-based algorithm for efficient composition of finite-state transducers
• Filters for Efficient Composition of Weighted Finite-State Transducers
• scientific article; zbMATH DE number 2150300
• Weighted automata algorithms

Cites work

• EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS
• scientific article; zbMATH DE number 3932372 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Rational kernels: theory and algorithms

Cited in

(3)

• Filters for Efficient Composition of Weighted Finite-State Transducers
• A filter-based algorithm for efficient composition of finite-state transducers
• N-WAY COMPOSITION OF WEIGHTED FINITE-STATE TRANSDUCERS

This page was built for publication: 3-Way Composition of Weighted Finite-State Transducers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3602821)