An Optimal Self-Segregating Morphology

Playing around with the Huffman coding
http://en.wikipedia.org/wiki/Huffman_coding it occurred to me that the
Huffman code has two properties of interest to conlangers.  It is
optimal in the sense that it assigns a label (a spelling, or "word")
to every value in a way that optimizes the use of available label
symbols (the alphabet), with the most used value getting the shortest
labels, and the resulting labels are, as a by-product of the process,
self-segregating.

This works by what is called "prefix-free coding". In other words,
after assigning all the labels it turns out that if a particular
label, "al" has been assigned to a value, say "the definite article",
then the character string "al" will never appear as the first two
characters of any other word. There can not be any words like "alu",
or "alpino", because that violates the prefix-free rule.

Now to say that the labels are prefix-free does not mean that labels
cannot be used as prefixes. In fact, if we call the values "morphemes"
instead of "words", we could say that "po" is a label for the morpheme
"past tense of a verb", and the label "nimu" stands for the morpheme
"to take" the the word "ponimu" is the past tense of "to take", and
the prefix "po" is a self segregating morpheme because no other
morpheme can begin with "po...".

The procedure assigns labels to values by building a tree of the
complete lexicon. The normal application of Huffman coding uses the
binary alphabet {0, 1} and the values are bytes of data. In this
application I use the alphabet {a, b, c, d, ..., x, y, z} and the
values are semantic concepts.

So here's my morphology:

My alphabet consists of 5 vowels {a, e, i, o, u} and 19 consonants (Q
and R are not used, X stands for "sh", and C stands for "ch"). Because
that distribution is unbalanced I'm going to drop the designations
"vowel" and "consonant" and go with the terms "syllable head" and
"syllable tail". That way I can steal a couple letters from the
"consonants" set and move them to the "syllable tail" set. We will use
the 17 syllables heads { b, c, d, f, g, h, j, k, m, p, s, t, v, w, x,
y, z } and the 15 syllable tails { a, e, i, o, u, an, en, in, on, un,
al, el, il, ol, ul }. This gives us 15 * 17 = 255 possible syllables
and 255^3 = 16,581,375 possible three-syllable words. In addition, a
word may begin with a bare syllable tail.

Typical three-syllable words might look like "oltasu", or "mindaki",
or "denpudo". But the next step is where it gets interesting. We would
like for the very most commonly used words and affixes to have the
shortest spellings. Some prefixes might consist only of a syllable
tail, (say "u-") and some suffixes, only a syllable head, (say "-k").
So how do we assign spellings to meanings to accomplish that goal? The
Huffman tree.

In order for the Huffman algorithm to work its magic we need to know
how often a given morpheme is used, compared to the other morphemes in
the lexicon. For this I turn to the million-word Brown Corpus. Yes,
it's a corpus of English words, but with some jiggering we can get
useful semantic frequency data from it.  For example, take the words
"common", "commonly", "uncommon", "uncommonly". These have the
words-per-million counts of 236, 31, 8, and 0 respectively. So I
consider COMMON to be my root concept. (in upper case to designate
that this is the narrow semantic category "ordinary, easily found" and
NOT the English word, which might also mean "shared" as in "common
values"). Then I can add all the frequency values and get 275 uses of
COMMON (in some form) in a million words. Then I can do the same thing
with the affixes "un-" and "-ly". Summing all the frequencies of all
the words that use "un-" (unnecessary, unbecoming, unconscious,...) I
end up with exactly 1000 occurrences, so the frequency of that
morpheme will be taken to be 1000. (Compare that with the frequency of
"the" at 81,280, or with words in it's own vicinity; "should" at 1023
and "too" at 975.)

Now the lexicon, instead of containing "common", "commonly",
"uncommon", "uncommonly", contains "COMMON", "-LY", and "UN-" as three
distinct morphemes. Again, they are all in upper case to remind us
they are narrow semantic categories and not English words. We might
find that some separate English morphemes merge into single sets, such
as "im-" and "in-" possibly merging with "un-", for example.

Once the lexicon of morphemes is prepared then it can be run through
the Huffman algorithm and what emerges is a complete conlang lexicon,
pronounceable, optimized for word length vs frequency, and with 100%
self-segregating morphemes.

I'm currently working on turning a 14,000-word English lexicon into a
language-independent semantic/morpheme lexicon. When that gets done it
will be really interesting to see what kind of lexicon emerges from
the Huffman algorithm.

--gary