S-Restricted Monotone Alignments: Algorithm, Search Space, and Applications

Proceedings of COLING 2012: Technical Papers, pages 781–798, COLING 2012, Mumbai, December 2012. S-restricted monotone alignments: Algorithm, search space, and applications Steffen Eger Goethe University Frankfurt, Grueneburg-Platz 1, 60323 Frankfurt am Main, Germany steffen.eger@yahoo.com Abstract We present a simple and straightforward alignment algorithm for monotone many-to-many alignments in grapheme-to-phoneme conversion and related fields such as morphology, and discuss a few noteworthy extensions. Moreover, we specify combinatorial formulas for monotone many-to-many alignments and decoding in G2P which indicate that exhaustive enumeration is generally possible, so that some limitations of our approach can easily be overcome. Finally, we present a decoding scheme, within the monotone many-to-many alignment paradigm, that relates the decoding problem to restricted integer compositions and that is, putatively, superior to alternatives suggested in the literature. Title and Abstract in German S-beschränkte monotone Alignierungen: Algorithmus, Suchraum und Anwendungen Wir präsentieren einen einfachen Alignment-Algorithmus für monotone ‘many-to- many’ Alignierungen im Bereich Graphem-zu-Phonem-Konversion und verwandten Gebieten wie z.B. Morphologie, und besprechen sinnvolle Erweiterungen. Darüber hinaus geben wir kombinatorische Formeln im Bereich der monotonen ‘many-to-many’ Alignierungen und im Bereich des Decoding in G2P an, die suggerieren, dass vollständige Enumeration hier im Allgemeinen möglich ist, sodass ein paar Einschränkungen unseres Ansatzes leicht behoben werden können. Schließlich präsentieren wir ein Decoding-Schema, innerhalb des Paradigmas von ‘many-to-many’ Alignierungen, dass das Decoding-Problem mit beschränkten Zahlenkompositionen in Beziehung setzt und das in der Literatur vorgeschlagenen Alternativen vermeintlich überlegen ist. Keywords: many-to-many alignments, monotone alignments, string transduction, restricted integer compositions, grapheme-to-phoneme conversion. Keywords in German: many-to-many Alignierungen, monotone Alignierungen, String- Überführungen, beschränkte Zahlenkompositionen, Graphem-zu-Phonem-Konversion. 781 1 Introduction Grapheme-to-phoneme conversion (G2P) is the problem of transducing, or converting, a grapheme, or letter, string x over an alphabet Σx into a phoneme string y over an alphabet Σy. A crucial first step thereby is finding alignments between grapheme and phoneme strings in training data. The classic alignment paradigm has assumed alignments that were (i) one-to-one or one-to-zero; i.e. one grapheme character is mapped to at most one phoneme character; this assumption has probably been a relic of both the traditional assumptions in machine translation (cf. (Brown et al., 1990)) and in biological sequence alignment (cf. (Needleman and Wunsch, 1970)). In the field of G2P such alignment models are also called ϵ-scattering models (cf. (Black et al., 1998)). (ii) monotone, i.e., the order between characters in grapheme and phoneme strings is preserved. It is clear that, despite its benefits, the classical alignment paradigm has a couple of limitations; in particular, it may be unable to explain certain grapheme-phoneme sequence pairs, a.o. those where the length of the phoneme string is greater than the length of the grapheme string such as in exact igzækt where x has length 5 and y has length 6. In the same context, even if an input pair can be explained, the one-to-one or one-to-zero assumption may lead to alignments that, linguistically, seem nonsensical, such as p h o e n i x f – i: n i k s where the reader may verify that, no matter …

Content truncated to 500 words