Logic Compression of Dictionaries for Multilingual Spelling Checkers

LOGIC COMPRESSION OF DICTIONARIES FOR MULTILINGUAL SPELLING CHECKERS Boubaker MEDI)EII I IAMROUNI GETA, IMAG-campus (UJF & CNRS) BP 53, I;-38041 Grenoble Cedcx 09, FRANCE Boubaker. Meddeb-namrouni@ i mag. t7 r & WinSoft SA. 34, Bd. de l'Esplanade 1:-38000 Grenoble, FRANCF ABSTRACT To provide practical spelling checkers on micro-com- puters, good compression algorithms ,'~'c essenlial. CutTeut techniques used to compress lexicons for indo-Fmropean languages provide efficient spelling checker. Applying the .~une methods to languages which have a different morpho- logical system (Arabic, Turkish,...) gives insufficient re- suits. To get better results, we apply other "logical" com- pression mechanisms based on tile structure of the lan- guage itself. Experiments with muir)lingual dictionaries show a significant reduction rate attributable to our logic compression alone and even better resnlls when using our method in conjunction with existing methods. KEY WORDS: Spelling checkers, Multilinguism, Compression, Dictionary, Finite-state machines. INTRODUCTION Since the first work in 1957 by Glantz [611, a great deal of timer)zing and reseltrch has taken place on the sub- ject of spelling verificatiou and correction. Many commer- cial products (word processors, desktop presentation,...) in- elude efficient spelling checkers on mic,'o-computers. The classical methods, used arc generally based on a morpho- logical analyzer. This is sufficient to provide a robust monolingual spelling checker, but using morphological amdyzers can become unrealistic when wc want to develop an univers~d solution. In fact, tile analyzers built for each language use various linguistic models and engines, and it is impossible to convert a morphoh)gical analyzer from one formalism to another. Furthermore, using flmse classi- cal mcthods would lead to combining into the host appli- cation as many of grammars and parsers as languages, which would increase the code size and Ihe mainten:mcc problem of rules and data. The method presented in this paper is based on building a dictionary of all surface forms for each language, which is sufficient for spelling checkers applications. "llle dictionary built with the existing genera- )ors can bc e~ily updated manually bt,t may l)e huge, es- pecially for some agglutinative language (Arabic, Turkish,...). A compression process on the muir)lingual dictionaries is neeess,'u'y to obtain a reduced size. The exist- ins compression methods generally used are physical and provide good results for indo-European languages. Applying the sane techniques to other languages (Arabic, Tnrkish,...) shows their limits. For this reason we intro- duce a new kind of compression techniques that we called "logic compression". This new technique requires a p,'imi- tire morphological knowledge during tile compression process and requires less storage space than prevkms meth- ods. It ,also has the advantage of being an universal lnelhod applicable to all languages, Seclion 1 contains an overview of existing methods for building spell checkers and the limits of such system whcll we take into account new constraints such as lnnlti- lingual)sin. Section 2 outlines tile first two steps of our work: we adapt an existing method to Arabic, then make a first extension hy introducing a new kind of compression called "logic compression". Section 3 introduces ill …

Content truncated to 500 words