Challenge: compress all of English into the smallest symbol set

Question

Imagine mapping English to short codes, like “a”, “aa”, “abc”, “cde”, separated by spaces. How would you do it?

In my opinion, this is very mathematical: because combinations of any finite alphabet are orderable, they are countable in the set-theoretic sense (like integers). Whereas it is difficult to conceive of a good “ordering” on the elements of English, but it is a good paradigm to explore and learn something from.

You can proceed from concepts, or a compression algorithm on sentences, for example.

You could take a frequency list of strings from an English corpus and make a basic algorithm that compresses each string to the first letter - if the letter is already taken, next it seeks the first letter of each word, if possible, to form a partial or total acrostic - it can also choose to add a numerical suffix, like a1, a2, a39, etc. It can also take common letters from words, like ‘cabbage’ becomes cbg.

What algorithm would you design?

---

This is a simple, non-ideal example, in Algol. I don’t think it works perfectly. Work in progress.

It iterates over strings of letters from shortest to longest.

begin
    file f := stand out to "map-english-to-short-codes";
    char array alphabet[1:26];
    alphabet := ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z');
    int i := 1;
    while i <= upb alphabet do
        begin
            printf(stand out, "Is %c a word? (1 for yes, 0 for no)", alphabet[i]);
            int response;
            scanf(stand in, "%d", response);
            if response = 1 then
                begin
                    printf(stand out, "What is its shortcut?");
                    char array shortcut[1:10];
                    scanf(stand in, "%s", shortcut);
                    printf(f, "%c %s\n", alphabet[i], shortcut);
                end;
            i := i + 1;
        end;
end

I am picturing making a tree of strings, like

(a, an)
(an, and)
(and, andy)
(and, andrew)
(bat, batch)
(bat, batter)
(batter, battery)

What is interesting here, is that in one direction, the tree is not totally ordered, but starting from the longest strings, every string has only one “parent” string.

This could be a way to find an ordering on English words, and map them into all possible alphabet arrangements, a, aa, ab, abc, abcd, abdd, etc.

Answer 1

The first step is to gather a corpus and use it to estimate the entropy: how many bits of information each signal conveys (where signals can be letters, syllables, words…your choice). The first reference I have on hand gives an entropy of 9.51 bits per syllable (page 58).

So you could count all the possible syllables, assign each one a number, and encode them that way. But this isn't quite ideal, since the distribution is very skewed: the syllable /ɪz/ is far more common than /strɪkt/. Huffman coding gives an algorithm to encode signals into variable-length binary strings in a way that's guaranteed to be optimal—that is, averaging around ten bits per syllable.

But in many cases we can do better still! Sometimes the context affects the probability of the next signal. If you're looking at a sequence of letters, then U is not especially frequent, but the odds of seeing it right after a Q are almost 100%. If you look at the conditional entropy, taking the context into account, that will generally be significantly lower: the same source reports 7.09 bits per syllable for English using the previous syllable as context (page 61).

To take advantage of this, you can have a bunch of different Huffman trees, and choose which one to use based on the context. The more context you use, the more efficient the encoding becomes, but also the more trees you need to keep on hand for decoding.

As for whether it's more efficient to go by letters, phonemes, syllables, words…and how much context to use, that's something that has to be determined empirically. It comes down to a tradeoff between the level of compression and the ease of decoding.

Answer 2

This is basically what the Hutter prize is about. So far it achieved rather impressive results, getting about 8× compression. With the current avalanche of LLMs, we can expect further improvements, e.g. see the ts_zip project (though computational requirements to train and quantize really large models are currently quite prohibitive).