📄 T-code compression for Arabic computational morphology

Summary

Arabic builds words by fitting consonantal roots into templates and then adding inflectional affixes. Because of this, exact-match tools such as spell checkers, search engines and indexers work badly, and a full list of word forms becomes very large. The authors take a generate-then-look-up approach. A rule-driven generator, written as Perl regular expressions, produces every inflected verb form together with its root, template and affix identifiers, about 2 million words in total. The forms are stored in a dictionary indexed by their undiacritised spelling. The dictionary is compressed with T-Codes, a self-synchronising subclass of Huffman-style variable-length codes, and gets a compact per-entry layout that allows fast scanning. The result is an 8 MB dictionary that includes its search information. That is more than 90% smaller than an uncompressed disk B-Tree, and lookup speed stays comparable. A small web CGI uses the dictionary to extract roots and parse words. The authors also propose sending words between devices as coded ID triples. This matters because analysis becomes a cheap, exact lookup into an enumerated and explainable form space.

Key points

• The Word Data Creator Environment (WCE) is a GUI for editing the MainDictionary Table (root, root class, pattern, variant) and the Templates Table (tense/voice template, transformation rules, affix list).
• The Word Generation Engine (WGE) runs three stages in sequence:
  • Stem Transformer applies ordered regex rules one pass at a time.
  • Affixer builds 17 morphosyntactic forms per stem.
  • Slotter places the radicals into the F/M/L/R position markers.
• Coverage is verbs only, about 2 million generated forms. Each entry stores numeric root, template and affix IDs so the fully diacritised word can be regenerated.
• Each entry starts with a 12-bit field giving the skip distance to the next entry with a different prefix, plus a 4-bit field counting letters shared with the next word. The final dictionary is 8 MB.
• Worked example: yaktubwna = {12,884, 460, 30} takes 18 bits as T-Codes versus 48 bits as raw 16-bit integers. A T-Code finite-state decoder that reads whole bytes is planned to make decoding faster.

Interesting ideas

• I1. Instead of analysing words by reversing rules, enumerate every surface form from lexicon plus rules, tag each with its generating IDs, and make analysis a lookup that returns all matching parses.
• I2. Represent a word as a small tuple (root, template, affix) and regenerate the surface form on demand, with variable-length codes assigned by corpus frequency of each ID.
• I3. Index entries under a normalised key (here the word with diacritics removed), then filter candidates by whatever extra detail the query actually supplies.
• I4. Apply transformation rules strictly one per pass in a fixed order, feeding each output into the next rule, with a tool to preview the result after any edit.
• I5. Strip candidate affix combinations from longest to shortest, push every stripped variant into a queue, and look all of them up, keeping every successful parse.

For Mova

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

• I1 (tokens): The en crate could precompile a lemma × paradigm form table in which every form carries its lemma and rule ID, so each analysis is an exact, explainable lookup rather than a guess.
• I2 (back): The text → graph → text compressor could encode tokens as (lemma, inflection-feature) IDs with frequency-based codes and rely on the generator to restore the exact spelling.
• I3 (tokens): Lexicon lookups could key on case-folded, apostrophe- and hyphen-normalised forms, then rerank by the original spelling, so noisy input still hits the right entries.
• I4 (learn): Self-induced repair rules could run as an ordered pipeline that logs each intermediate state, which makes it easy to see which rule broke a tree.
• I5 (tokens): Clitic and contraction splitting ('s, n't, -ly derivations) could generate several segmentation candidates checked against the form table, passing ambiguity on to the parser instead of committing early.