📄 A Compression Technique for Arabic Dictionaries: The Affix Analysis

Summary

This paper addresses how to keep a dictionary for non-diacritical (unvowelled) Arabic small enough for automatic processing. The work comes from a project on detecting and correcting spelling errors. Rather than listing every word form, the author stores only roots, the non-redundant part of the language. Prefixes, infixes and suffixes are recovered by morphological analysis.

A decomposition module strips candidate prefixes and suffixes using lookup tables. A single analyser then identifies the infix in the remaining string. The analysis accounts for transformations that alter surface forms, mainly in roots containing yaa, waw or hamza. A validation module filters candidate decompositions by checking affix compatibility at three levels and by consulting the root dictionary.

The dictionary was built from a functional-Arabic corpus of the Maghreb countries and holds about 1,600 roots. The method was tested on roughly 100,000 words. It matters because it exploits Arabic's derivational root-and-pattern structure. A compact, memory-resident lexicon then covers many forms, and the segmentation it produces helps spelling correction.

Key points

• The paper compares three ways to shrink a dictionary:
  • sharing common prefixes in chained lists, as in the PIAF system;
  • topic-specific dictionaries layered over a base dictionary;
  • affix analysis, which is the approach used in DECIO-SPELL and the one the author adopts.
• Surface changes are split into two kinds:
  • morpho-phonological substitutions, which keep word length;
  • purely phonological deletions, which shorten the word.
• The prefix–suffix congruity matrix has 609 cells (21 prefixes × 29 suffixes). Each cell is 0 if the pair is incompatible, or an index N_k (1–226) pointing to a list of allowed Morphological Codes. The code produced for the infix is intersected with that list.
• The root dictionary has about 1,500 three-letter roots and 100 four-letter roots, drawn from the corpus of the Permanent Commission of Functional Arabic (PCFA 76). Each root is accessed directly by a key computed from its first three letters and its length.
• The system was implemented in FORTRAN and tested on about 100,000 words. For checking whether a word exists, the first valid decomposition is enough.

Interesting ideas

• I1. Validation is factored into a small prefix×suffix matrix whose cells point to shared lists of permitted pattern codes, so legality checks become cheap set intersections instead of a large enumerated table.
• I2. Decomposition runs in two stages: outer affixes are peeled off via tables, then one generic analyser handles the internal change, so a single mechanism covers all patterns.
• I3. Spelling transformations are classed as length-preserving substitutions versus length-changing deletions, which tells the reverse analyser what kinds of edits to undo.
• I4. The root lexicon itself records which non-systematic patterns each root legitimately takes, treating some impossible forms as lexical or semantic gaps rather than morphological ones.
• I5. A word is stored as a root plus pattern codes instead of a full string, which both compresses the lexicon and yields a natural segmentation useful for correction.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

• I1 (tokens): English affix stacking (un-…-able-ness) could be validated the same way, with a compact compatibility table pointing to allowed morphological codes in the en lemmatizer.
• I2 (tokens): irregular stem changes (sing/sang, mouse/mice) could be handled by one analyser applied after suffix stripping, keeping the morphology code uniform and each step explainable.
• I3 (tokens): tagging English orthographic rules (y→i, e-deletion, consonant doubling) by this distinction would make lemma recovery rules easier to organise and trace.
• I4 (world): verb-class knowledge could mark, per lemma, which derivations or alternations are attested, so the system can reject plausible-looking but unused forms.
• I5 (back): the text → graph → text compressor could encode words as lemma plus morphological features and regenerate surface forms, saving space while staying fully reversible.