Substring-Based Transliteration

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 944–951, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Substring-Based Transliteration Tarek Sherif and Grzegorz Kondrak Department of Computing Science University of Alberta Edmonton, Alberta, Canada T6G 2E8 {tarek,kondrak}@cs.ualberta.ca Abstract Transliteration is the task of converting a word from one alphabetic script to another. We present a novel, substring-based ap- proach to transliteration, inspired by phrase- based models of machine translation. We in- vestigate two implementations of substring- based transliteration: a dynamic program- ming algorithm, and a finite-state transducer. We show that our substring-based transducer not only outperforms a state-of-the-art letter- based approach by a significant margin, but is also orders of magnitude faster. 1 Introduction A significant proportion of out-of-vocabulary words in machine translation models or cross language in- formation retrieval systems are named entities. If the languages are written in different scripts, these names must be transliterated. Transliteration is the task of converting a word from one writing script to another, usually based on the phonetics of the orig- inal word. If the target language contains all the phonemes used in the source language, the translit- eration is straightforward. For example, the Arabic transliteration of Amanda is @ Y � K A� � @, which is essen- tially pronounced in the same way. However, if some of the sounds are missing in the target lan- guage, they are generally mapped to the most pho- netically similar letter. For example, the sound [p] in the name Paul, does not exist in Arabic, and the phonotactic constraints of Arabic disallow the sound [A] in this context, so the word is transliterated as � �K ., pronounced [bul]. The information loss inherent in the process of transliteration makes back-transliteration, which is the restoration of a previously transliterated word, a particularly difficult task. Any phonetically rea- sonable forward transliteration is essentially correct, although occasionally there is a standard translitera- tion (e.g. Omar Sharif). In the original script, how- ever, there is usually only a single correct form. For example, both Naguib Mahfouz and Najib Mahfuz are reasonable transliterations of � � � � � m � I . J � m . � � ', but Tsharlz Dykens is certainly not acceptable if one is referring to the author of Oliver Twist. In a statistical approach to machine translitera- tion, given a foreign word F, we are interested in finding the English word ˆE that maximizes P(E|F). Using Bayes’ rule, and keeping in mind that F is constant, we can formulate the task as follows: ˆE = arg max E P(F|E)P(E) P(F) = arg max E P(F|E)P(E) This is known as the noisy channel approach to machine transliteration, which splits the task into two parts. The language model provides an esti- mate of the probability P(E) of an English word, while the transliteration model provides an estimate of the probability P(F|E) of a foreign word being a transliteration of an English word. The probabilities assigned by the …

Content truncated to 500 words