suffix-thumb

find the optimal transormations between sets of words

npm install suffix-thumb

discover the minimal rules for mapping two sets of words to one another, according to changes in their suffix.

It was built for learning rules about verb conjugations, but in a way, it is just a generic compression algorithm.

The assumption is that a word's suffix is the most-often changed part of a word.

Learn → Convert

import { learn, convert } from 'suffix-thumb'

let pairs = [
  ['walk', 'walked'],
  ['talk', 'talked'],
  ['go', 'went'],
]
let model = learn(pairs)
/* {
  fwd: {},
  both: { '': 'ed', go: 'went' },
  rev: {},
  ex: {},
}*/

let out = convert('walk', model)
// 'walked'

the model has four parts:

• fwd - suffix rules that only work left→right
• both - suffix rules that also work right→left
• rev - suffix rules that only work right→left
• ex - whole-word exceptions

when converting a word, exceptions are checked first, then the longest matching suffix wins. A rule may match the whole word, and the empty-suffix rule '' is a fallback that simply appends.

you can pass-in options:

let opts={
  min: 0, // a rule must serve at least this many pairs (otherwise, use an exception)
  reverse: true, // also learn the backward transformation
  verbose: false, // warn about skipped pairs
}
let model = learn(pairs, opts)

Reverse

the model also works transforming the words the other way:

import { learn, reverse, convert } from 'suffix-thumb'

let pairs = [
  ['walk', 'walked'],
  ['talk', 'talked'],
  ['go', 'went'],
]
let model = learn(pairs)
let rev = reverse(model)
let out = convert('walked', rev)
// 'walk'

By default, the model learns both directions. When multiple left-side words share a right-side word, reversing chooses the first accepted pair. If you only require the forward direction, you can do:

learn(pairs, {reverse: false})

you can expect the model to be 5% smaller or so - not much.

Compress

by default, the model is small, but remains human-readable (and human-editable). We can pack it further, into one string:

import { learn, compress, uncompress, convert } from 'suffix-thumb'

let pairs = [
  ['walk', 'walked'],
  ['talk', 'talked'],
  ['go', 'went'],
]
let model = learn(pairs)
// shrink it
let str = compress(model)
// '~0ed:|2went:go~~'
// pop it back
model = uncompress(str)
let out = convert('walk', model)
// 'walked'

The models must be uncompressed before they are used, or reversed.

The packed string is still legible, with some squinting:

• the four sections (fwd, both, rev, ex) are separated by ~
• each section is a list of value:keys groups, separated by |
• a value is drop this many characters, then add this - so 1as turns chico into chicas
• the keys are a suffix-trie: ador{lt,nz,ep} is ltador, nzador and epador. An empty entry, like ero{,nton}, means ero is a key too.

'4èlerons:eler{en,c,t{man,r},g,od,i,k}|4èterons:eter{h,qu{c,écli,a{r,p}}}'

This means the characters ~ | : , { } and digits are reserved - pairs containing them are skipped.

Duplicates

a left-side word can only map to one thing, so learn() keeps the first accepted pair for each left-side word and ignores later duplicates.

Repeated right-side words are fine - 'poner' and 'ponerse' can both become 'puesto'. When reversing, the first pair wins: 'puesto' → 'poner'.

import { validate } from 'suffix-thumb'
let pairs = [
  ['left', 'right'],
  ['left', 'right-two'],
  ['ok', 'right'],
]
const uniqueBoth = validate(pairs) // remove dupes on both sides, and unencodable pairs
const uniqueLeft = validate(pairs, { reverse: false }) // keep right-side dupes, as learn() does

The exported test(pairs, model) helper checks every accepted forward pair and the first pair for each reverse target. If no valid pairs remain, it reports N/A (no pairs) in both directions.

How it works

The left-side words are arranged into a suffix-trie. Every pair implies a family of possible rules - 'walk'→'walked' could be ''→'ed', 'k'→'ked', 'lk'→'lked', and so on - and each of those rules lives at one node in the trie.

Walking the trie bottom-up, each node either inherits the rule of its nearest ancestor, or places its own rule, which then governs every word beneath it - until a deeper node overrides it, or a word that no rule fits becomes an exception. Because the lookup is longest-suffix-wins, these choices are independent enough that the byte-cheapest combination can be found exactly, in about a second for 15,000 pairs.

The backward direction is then learned the same way, with a discount for any rule that is simply the mirror of a forward rule - those are stored once, in both.

• The library optimizes for file-size of the model
• it reproduces every accepted forward training pair; invalid pairs and later left-side duplicates are skipped
• with reverse learning enabled (the default), each right-side word maps back to the first accepted left-side word that produced it
• it may be less-clever about words it hasn't seen.

Words are case-sensitive, and case is preserved through learning, conversion, and compression. Pairs containing digits or the reserved characters ~ | : , { } on either side are skipped by learn() and validate().

Conjugation datasets in French, Spanish and Italian tend to get ~98% filesize compression.

See also

• efrt - trie-based prefix compression for JSON

MIT