Cross Linguistic Name Matching in English and Arabic

Proceedings of the Human Language Technology Conference of the North American Chapter of the ACL, pages 471–478, New York, June 2006. c⃝2006 Association for Computational Linguistics Cross Linguistic Name Matching in English and Arabic: A “One to Many Mapping” Extension of the Levenshtein Edit Distance Algorithm Dr. Andrew T. Freeman, Dr. Sherri L. Condon and Christopher M. Ackerman The Mitre Corporation 7525 Colshire Dr McLean, Va 22102-7505 {afreeman, scondon, cackerman}@mitre.org Abstract This paper presents a solution to the prob- lem of matching personal names in Eng- lish to the same names represented in Arabic script. Standard string comparison measures perform poorly on this task due to varying transliteration conventions in both languages and the fact that Arabic script does not usually represent short vowels. Significant improvement is achieved by augmenting the classic Levenshtein edit-distance algorithm with character equivalency classes. 1 Introduction to the problem Personal names are problematic for all language technology that processes linguistic content, espe- cially in applications such as information retrieval, document clustering, entity extraction, and transla- tion. Name matching is not a trivial problem even within a language because names have more than one part, including titles, nicknames, and qualifiers such as Jr. or II. Across documents, instances of the name might not include the same name parts, and within documents, the second or third mention of a name will often have only one salient part. In multilingual applications, the problem is compli- cated by the fact that when a name is represented in a script different from its native script, there may be several alternative representations for each phoneme, leading to large number of potential variants for multi-part names. A good example of the problem is the name of the current leader of Libya. In Arabic, there is only one way to write the consonants and long vowels of any person’s name, and the current leader of Libya’s name in un-vocalized Arabic text can only be written as ﻲﻓاﺬﻘﻟا ﺮﻤﻌﻣ. In English, his name has many common representations. Ta- ble 1 documents the top five hits returned from a web search at www.google.com, using various English spellings of the name. Version Muammar Gaddafi Occurrences 43,500 Muammar Qaddafi 35,900 Moammar Gadhafi 34,100 Muammar Qadhafi 15,000 Muammar al Qadhafi 11,500 Table 1. Qadhafy’s names in English Part of this variation is due to the lack of an English phoneme corresponding to the Standard Arabic phoneme /q/. The problem is further com- pounded by the fact that in many dialects spoken in the Arabic-speaking world, including Libya, this phoneme is pronounced as [g]. The engineering problem is how one reliably matches all versions of a particular name in lan- guage A to all possible versions of the same name in language B. Most solutions employ standard string similarity measures, which require the names to be represented in a common character set. The solution presented here exploits translit- eration conventions in normalization procedures and equivalence mappings for the standard Leven- shtein distance measure. 2 Fuzzy string matching The term …

Content truncated to 500 words