T-code compression for Arabic computational morphology

T-Code Compression for Arabic Computational Morphology Jim Yaghi and Mark R. Titchener Department of Computer Science University of Auckland. jyag001@ec.auckland.ac.nz, mark@tcode.auckland.ac.nz Sane Yagi Department of Linguistics University of Sharjah. saneyagi@yahoo.com Abstract It is impossible to perform root-based searching, concordancing, and gram- mar checking in Arabic without a method to match words with roots and vice versa. A comprehensive word list is essential for incremental searching, predictive SMS messaging, and spell checking, but due to the derivational and inflectional nature of Arabic, a comprehensive word list is taxing on storage space and access speed. This paper describes a method for com- pactly storing and efficiently accessing an extensive dictionary of Arabic words by their morphological properties and roots. Compression of the dictionary is based on T-Code encoding, which follows the Huffman encoding model. The special characteristics inherent in the recursive augmentation method with which codes are created allow compact storage on disk and in mem- ory. They also facilitate the efficient use of bandwidth, for Arabic text transmission, over intranets and the Internet. 1 Introduction 1.1 Challenges of Arabic Arabic poses a formidable challenge for compu- tational linguists due to its derivational nature. Word generation requires moulding three- and oc- casionally four-consonant roots into a range of morphosemantic template patterns, where the root radicals intersperse between a templates’ letters to produce a new word with a new meaning that still shares the basic meaning of the root. Often these templates augment the root by lengthening its me- dial radical, inserting a long vowel between the radicals, and/or adding consonantal prefixes. The generated words are what is termed ‘stems’ in the English language, but they are not actual words; they are mere semantic abstractions. To become actual words, the stems are moulded into mor- phosyntactic patterns that will indicate whether a word is a verb or noun, present or past, active or passive voice, etc. The process of root extraction from actual words, on the other hand, is not a simple reversal of the process of word generation because the root radicals would have been disguised by the application of morphological patterns. Although Arabic morphology is systematic, it has remained a challenge to produce, for example, useful spell checkers, grammar checkers, search engines, and indexers that are not based on exact matching. The missing ingredient at the base of this problem is an accurate root-based morpho- logical analyser. Spell-checkers, normally, do not contain a large enough word list to accommodate the inflectional variation words undergo when affixed because these may run in millions. Few grammar checkers exist for Arabic, because it is difficult to parse a sentence if its words are not correctly interpreted by a morphological parser. Various types of Arabic search engines are significantly impaired because of the inability to find character-to-character correspondence between search terms and variant match items such as differing tense, voice, person, number, or gender. 1.2 T-Code Technique Finite State Transducers (FSTs) have been estab- lished as a standard way to encode morphologi- cal alterations (Karttunen …

Content truncated to 500 words