<p>This is basically what the <a href="http://prize.hutter1.net/" rel="nofollow noreferrer">Hutter prize</a> is about. So far it achieved rather impressive results, getting about 8× compression. With the current avalanche of <a href="https://en.wikipedia.org/wiki/Large_language_model" rel="nofollow noreferrer">LLM</a>s, we can expect further improvements, e.g. see the <a href="https://bellard.org/ts_zip/" rel="nofollow noreferrer">ts_zip</a> project (though computational requirements to train and quantize really large models are currently quite prohibitive).</p>

CC BY-SA 4.0
2023-06-28T11:18:15.917Z
2024-03-04T08:41:28.100Z
2024-03-04T08:41:28.100Z
Radovan Garabík
<p>The first step is to gather a corpus and use it to estimate the <a href="https://en.wikipedia.org/wiki/Entropy_(information_theory)" rel="nofollow noreferrer">entropy</a>: 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 (<a href="http://www.ddl.cnrs.fr/fulltext/Yoonmi/Oh_2015_1.pdf" rel="nofollow noreferrer">page 58</a>).</p>
<p>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 <code>/ɪz/</code> is far more common than <code>/strɪkt/</code>. <a href="https://en.wikipedia.org/wiki/Huffman_coding" rel="nofollow noreferrer">Huffman coding</a> 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.</p>
<p>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 <code>U</code> is not especially frequent, but the odds of seeing it right after a <code>Q</code> are almost 100%. If you look at the <em>conditional entropy</em>, 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 (<a href="http://www.ddl.cnrs.fr/fulltext/Yoonmi/Oh_2015_1.pdf" rel="nofollow noreferrer">page 61</a>).</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-06-28T08:09:34.183Z
That’s brilliant
Julius Hamilton
CC BY-SA 4.0
2023-07-10T15:43:02.003Z
@KarlKnechtel You're right, I worded that badly. Updated the answer.
Draconis
CC BY-SA 4.0
2023-07-10T16:05:35.713Z
Looks much better, thanks. (Feel free to NLN.)
Karl Knechtel
CC BY-SA 4.0
2023-06-27T16:46:44.600Z
2023-07-10T15:41:30.330Z
2023-07-10T15:41:30.330Z
Draconis
<p>Imagine mapping English to short codes, like “a”, “aa”, “abc”, “cde”, separated by spaces. How would you do it?</p>
<p>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.</p>
<p>You can proceed from concepts, or a compression algorithm on sentences, for example.</p>
<p>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.</p>
<p>What algorithm would you design?</p>
<hr />
<p>This is a simple, non-ideal example, in Algol. I don’t think it works perfectly. Work in progress.</p>
<p>It iterates over strings of letters from shortest to longest.</p>
<pre><code>begin
    file f := stand out to &quot;map-english-to-short-codes&quot;;
    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 &lt;= upb alphabet do
        begin
            printf(stand out, &quot;Is %c a word? (1 for yes, 0 for no)&quot;, alphabet[i]);
            int response;
            scanf(stand in, &quot;%d&quot;, response);
            if response = 1 then
                begin
                    printf(stand out, &quot;What is its shortcut?&quot;);
                    char array shortcut[1:10];
                    scanf(stand in, &quot;%s&quot;, shortcut);
                    printf(f, &quot;%c %s\n&quot;, alphabet[i], shortcut);
                end;
            i := i + 1;
        end;
end
</code></pre>
<p>I am picturing making a tree of strings, like</p>
<pre><code>(a, an)
(an, and)
(and, andy)
(and, andrew)
(bat, batch)
(bat, batter)
(batter, battery)
</code></pre>
<p>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.</p>
<p>This could be a way to find an ordering on English words, and map them into all possible alphabet arrangements, <code>a, aa, ab, abc, abcd, abdd,</code> etc.</p>

CC BY-SA 4.0
2023-06-28T09:04:25.123Z
You have basically described a Huffman code.
Oliver Mason
<writing-systems><unicode>
Challenge: compress all of English into the smallest symbol set
# Challenge: compress all of English into the smallest symbol set

(Asked by: username_0 on 2023-06-27)

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.

**Tags:** writing-systems, unicode

> **Comments:**
> **username_1**: You have basically described a Huffman code.  

---

## 2 answers

### Answer by username_3 on 2023-06-27. Score: 6 | Accepted answer

The first step is to gather a corpus and use it to estimate the [entropy](https://en.wikipedia.org/wiki/Entropy_(information_theory)): 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](http://www.ddl.cnrs.fr/fulltext/Yoonmi/Oh_2015_1.pdf)).

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](https://en.wikipedia.org/wiki/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](http://www.ddl.cnrs.fr/fulltext/Yoonmi/Oh_2015_1.pdf)).

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.

> **Comments:**
> **username_0**: That’s brilliant  
> **username_3**: @KarlKnechtel You're right, I worded that badly. Updated the answer.  
> **username_4**: Looks much better, thanks. (Feel free to NLN.)  

---

### Answer by username_2 on 2023-06-28. Score: 5

This is basically what the [Hutter prize](http://prize.hutter1.net/) is about. So far it achieved rather impressive results, getting about 8× compression. With the current avalanche of [LLM](https://en.wikipedia.org/wiki/Large_language_model)s, we can expect further improvements, e.g. see the [ts\_zip](https://bellard.org/ts_zip/) project (though computational requirements to train and quantize really large models are currently quite prohibitive).


---

