Succinct Sounds-like Starting Vowels

An herb, but a herbicide.

An honest opinion, but a honeypot.

But you already knew that English was a mess, so now we have the question: can we represent that mess compactly? If you ever wanted to know whether an English word should be preceeded by an 'a' or an 'an', it turns out that all you need to know is (roughly) 747 bits:

11111110011011001011111111010001101110110001011011111010110101010101011010101001
01111111100000010000001101010000101000000100010101101001001001010001010101001010
10000000000010000111010000111010100110001010010110001000111001101000010101001011
01101100011001010011101011001101000100010110001101101000001000100000000000001000
00000001000100001110101000011101100100110000010011100010000100000001000111010001
00100100010110100010001010101101110100001001010011101010010000000010000011010010
01110010001001010001100010001010101001001010010100010000100010010001001010000011
00011011000010001101110000010011100100000010011000000110111001100100000000011010
00011010011101101100000000000000000010000000000001000000000000000000000000000000
000001000000000000111101100

Why? Well, you'd have to start by reading Amit Patel's Blog Post About Vowels, in which he derives a relatively small list of exceptions to the "if it starts with a vowel, it gets an an" rule. The program implementing it is 1252 bytes including whitespace and starts like this:

VOWELS="aeiou"

def starts_with_vowel(word):
    if word.startswith("eu"): return False
    if word.startswith("ew"): return False
    if word.startswith("heir"): return True
    if word.startswith("herb") and not word.startswith("herbiv") and word != "herbarium" and word != "herbicide": return True
    ...

Over 1kb? Oh that won't do. As a starter, I had an LLM golf it down to about 362 bytes of dog vomit:

def starts_with_vowel(w):s=w.startswith;return w in("unissued","ur","us","usher")or s(("heir","homage","hones","hono","hour","onerous","utm","utt","ytt"))or not(s(("eu","ew","once","one","ula","unani","ub","uk","us","ut","uva","herbiv"))or w in("herbarium","herbicide")or s("uni")and w[3:4]in"cfloqstv"or s("ur")and w[2:3]in"aeiou")and(s("herb")or w[0]in"aeiou")

And if we wanted to, we could use zstd -19 to compress that down to 224 bytes. But we can do better than that. Notably, almost all of the rules he derives are about prefixes of the words, which we can represent very easily with a trie:

Tries have some advantages of built-in compression of shared strings. But we're left with the question of how to represent the trie.

We could go for a more compact ASCII representation, looking something like this, using parentheses to represent children and +/- for vowel and consonant, with ! for negation:

-(a+,e+(u-,w-),h(e(ir+,rb+(arium!,i(cide!,v-))),o(mage+,n(es+,o+),ur+)),i+,o+(n(ce-,e-(rous+))),u+(b-,k-,la-,n(ani-,i!(c-,f-,l-,o-,q-,s-(sued!),t-,v-)),r(a-,e-,i-,o-,u-),s-!(her!),t-(m+,t+),va-),ytt+)

Not bad! That gets us down to 200 bytes. And surely we could compress that using standard compression techniques:

Not bad! And yet...

There's a cool area of CS theory that looks at succinct data structures—those that take only the information-theoretic minimum amount of space to represent. One of the first things people thought about encoding succinctly were trees of various sorts. As an example, you could encode this simple two-level binary tree with one root and two children by writing a 1 if a child was present and a 0 if not:

    O
   / \
  O   O

as 110000 -- here, the root has one child on the left (the first 1), and one on the right (the second 1), and then the left child has no further children (00) nor does the right. And if you wanted to have a tree that looked like

   c
  / \
 a   t

You could encode it using two arrays, the first recording 110000 as above, and the second recording the values, packed densely, 'cat'. That works for binary trees but it's a little unwieldy when you have widely different fan-outs.

Instead, a common encoding for general trees and tries is to use a slightly different encoding called LOUDS ("level ordered unary degree sequence"), where you write down the degree of the nodes directly. Our tree above would have degrees 2, 0, and 0, so you'd write them down like that, but using a unary sequence, where the count of 1's before a 0 is the count of the degree of the nodes. That would look like 11000. (many conventional louds encodings prepend 10 to the sequence to make some math more intuitive, but it's not really necessary). Because each node is identified in a level-ordered traversal, we can still associate edge labels with their position in an auxiliary array (the nth entry in the array corresponds to the nth node in the tree as we traverse it top-to-bottom, left-to-right). For our experiment here, let's define four associated bit vectors:

• labels: One five-bit a-z character per entry
• decision (vowel/consonant): One bit indicating if suffixes of that node are vowel (sounds)
• terminal marker: One bit indicating if an exact match is handled specially
• terminal handler: One bit indicating vowel/no vowel for exact matches, only if a terminal marker was used

This gets us to 165 bits used to write down our topology, 410 bits for edge labels (ow), 83 bits for decisions and terminal markers, and 6 more bits for those special terminal handlers. A total of 94 bytes when stored in a file.

We could go farther, because the alphabet used for the edge labels is not uniformly distributed among a-z (for example, "e" appears 10 times, x and z never appear), but this seems like enough for now. So if you ever want to know if an english word sounds like it starts with a vowel, you've got 94 bytes ready to help you out.

Endnotes

(1) To be a little bit precise, I'm not claiming here this is actually the minimum size needed to represent this problem. It could be there are better ways of representing the state machine that decides vowel-or-not than a trie, in which case we could encode that structure succinctly instead. But it smells pretty close to optimal given what the rules looked like.