The Technical Honeypot · typography

Where a Word May Break

A word that will not fit gets cut in half, and something has to decide where. That something is a model with about five thousand parameters, fitted to a dictionary in 1983, still shipping unchanged inside every TeX on earth. Here it is, opened up: type a word and watch its patterns fight over the gaps between your letters. Then the finding, which is that the American and British versions of the same model disagree about 35.63% of the words they share, and the disagreement has a direction. Britain breaks on the seam. America breaks on the sound.

Set a line of type narrower than a word and you have a problem no amount of good taste solves quickly. Extraordinary does not fit. You may cut it, but not anywhere: extraordina-ry is wrong, ex-traordinary is thin, and extraor-dinary is fine. A person who knows English can feel the difference. Getting a machine to feel it took until 1983, and the answer that worked is stranger and smaller than you would guess.

It has no dictionary in it. It does not know what a syllable is, or a prefix, or a vowel. It is a list of about five thousand short strings of letters with numbers wedged between them, like hy3ph and 4p and .mis1, and a rule for making them argue. The strings were not written by anyone. They were fitted: a program called patgen was shown a dictionary that had already been divided into syllables, and it searched for a small set of patterns that would reproduce those divisions on words it had not been shown. Frank Liang's Stanford dissertation, Word Hy-phen-a-tion by Com-pu-ter, is where this happened, and the title is the joke and the specification at once.

That makes the thing in front of you a model fitted to data, published in 1983, and still running. Not a descendant of it. The file TeX Live installs for American English today contains all 4,447 of Liang's original patterns, byte for byte, and adds 491. That is checked below, in your browser, against both files.

1. Watch the patterns fight

The rule is four sentences long. Wrap the word in dots. Find every pattern that occurs inside it as a substring. Each match proposes a number for each gap it covers, and each gap keeps the largest number anything proposed for it. An odd number means a break is allowed there; an even number, and the default of zero, means it is not.

That is the whole algorithm. The subtlety is entirely in which patterns exist, and the trick that makes it work is that later, louder patterns can take back what earlier ones proposed. Watch the bottom row: the winning number in each gap, gold where it is odd.

Try hyphenation first, because Liang's own title claims the answer: hy-phen-ation. It is what TeX really does. Then try present, and notice that the American file refuses to break it at all. That refusal is not a failure of the patterns. It is the one place in this whole system where a human overruled the machine, and section 4 is about why.

2. Two nations, one word, two places to break it

TeX ships a second English pattern file. hyph-en-gb.tex was made by Dominik Wujastyk and Graham Toal in 1992, has 8,527 patterns to the American file's 4,938, and typesets British books. Both files answer the same question about the same language. They do not answer it the same way.

Now the whole lexicon. The comparison runs on the 58,739 words that the American and British word lists spell identically, because comparing colour against color would measure spelling and not hyphenation. Every one of those words is in this page. Press the button and your browser will hyphenate all of them, twice, using the same code the lab used.

The rate is 35.63% of words. Weighted by how often words are actually used, which pulls the number toward short common ones, it is 24.42% of the words in a page of running text. That is not a rounding difference between two typesetting conventions. Roughly one hyphenated word in three would be cut in a different place depending on which side of the Atlantic set the book.

My guess before running it was that the British set, with nearly twice the patterns, would be the more permissive one. That was wrong. The American set allows 1.257 breaks per word against the British 1.229, and refuses to break 13,720 words outright where the British file refuses 14,532. More patterns bought more restraint, not more licence, because a great many patterns exist only to forbid.

The direction of the disagreement

The interesting question is not how often they differ but whether the difference has a shape. It does, and it is the difference the two dictionary traditions describe: American division follows the spoken syllable, British division follows the derivation. The word that names the whole quarrel is democracy. Say it and the stress falls on the second syllable, de-MOC-ra-cy, and the American file cuts democ-racy. Look at where it came from, demos and kratia, and the British file cuts demo-cracy. You can see the same split in the commonest words on the list without any statistics at all.

The most frequent words in the shared lexicon that the two files break differently, ranked by how often the word occurs in a large corpus of web text. Recomputed live from the pattern files; the ranking is the lab's.

information is the whole argument in one word. The American file cuts in-for-ma-tion, which is how you say it. The British file cuts in-form-a-tion, which keeps form whole. Same for tech-nol-ogy against tech-no-logy, and se-cu-rity against se-cur-ity.

To test that rather than admire it, I fixed a list of 80 Greek and Latin initial combining forms before looking at any results, took every shared word beginning with one, and asked each file a single question: may a break fall on the seam? There are 1,193 such words. The British file says yes for 80.4% of them, the American for 60.9%. Among the 414 words where exactly one file allows the seam, it is the British one 323 times (exact two-sided binomial p = 1.5 × 10^-31).

Run from the other end of the word, using final forms like -graphy and -cracy so that no guess about the start of the word is involved, the gap is wider: British 92.0%, American 42.4%, discordant 215 to 9. And the mirror image holds too. Where a word has a run of two or more consonants in the middle, the American file is the one that cuts through it, on 4,607 clusters the British file leaves whole against 2,702 the other way. That is exactly what dividing by sound does: it closes the first syllable on a consonant and hands the rest along, at-mos-phere where derivation would say at-mo-sphere.

One honest deduction from the noise: the seam of a listed form is taken to be the end of that form, and sometimes that is not the real morpheme boundary. aerobic is aer plus obic, not aero plus bic, and in the cases inspected that kind of mistake counted against the prediction rather than for it. The measured gap is more likely an underestimate than an inflation.

3. The confessions

At the end of each pattern file is a short list of words written out by hand, with the breaks marked, because the patterns get them wrong. Fourteen words in the American file. Eight in the British. For a model with thousands of parameters and a whole language to cover, that is a startlingly short list of admitted failures, and every entry is a place where a person looked at the output and said no.

Two things fall out of that table. The first is small and slightly comic: four of the fourteen American exceptions are dead letters. declination, obligatory, philanthropic and retribution are hand-corrected to exactly what the patterns already produce. Switch to Liang's 1983 file and none of the fourteen is redundant, because in 1983 all fourteen were live. The 1990 revision fixed four of them in the patterns and nobody went back and pruned the list. It has been carried, inert, in every TeX distribution since.

The second is not small at all.

4. The four words it was told to stop guessing about

Four entries in the American exception list are not corrections. present, presents, project and projects are listed with no break anywhere, while the patterns on their own would happily give pre-sent and pro-ject. Somebody deliberately made the machine say nothing.

The reason is that these words are two words. A PRES-ent is a gift; to pre-SENT is to hand it over. A PROJ-ect is a plan; to pro-JECT is to throw. The pronouncing dictionary carries both, with the stress on different syllables, and where American practice divides on the spoken syllable the two senses do not divide in the same place. The spelling does not say which one you meant. A model whose entire input is the letters cannot get such a word right. It can only choose which sense to be wrong about. Refusing to break is the only output that is not a guess.

So how many such words are there? Taking every word in the shared lexicon that CMUdict records with two pronunciations putting the primary stress on different syllables gives 476. The American file names four of them.

There is no protective instinct in the file at all. The American set refuses to break 14.7% of the stress-ambiguous words, and refuses 22.9% of a length-matched control drawn from the rest of the lexicon, so if anything the ambiguous ones get broken slightly more often than ordinary words of the same size. The four are not the tip of a policy. They are four words somebody happened to notice.

What this does not show, and I would rather say so than let the number carry more than it can: a word having two stress patterns does not prove that a printed dictionary divides its two senses differently. Establishing that needs a dictionary's division column, which I do not have. What is established is the size of the class the four named exceptions belong to, and that 406 other members of it are broken without comment.

5. What 491 patterns bought

Because the modern American file contains Liang's file whole, the difference between 1983 and now is exactly 491 patterns, and it can be subtracted. Delete them and 1983 comes back.

Those 491 patterns change the hyphenation of 1,074 words out of 62,156, which is 1.73% of the lexicon. Most of the change is permission: 743 words gained a break, 156 lost one, 175 had a break move. Some of the additions are obviously repairs. m2an. and m2en. together stop the machine cutting fisher-m-an, and they occur in 155 words each.

And some of it made things worse in a way you can see. Liang's 1983 file hyphenates academically as aca-dem-i-cally. The file your TeX installs today gives aca-d-e-m-i-cally, which offers to leave a single letter d hanging at the end of a line. That is not my engine misreading the file. It is what TeX prints when you ask it.

6. Fit it yourself

The last thing worth doing with a fitted model is fitting it again, because the shape of the training is the part nobody ever sees. Liang's key move is an alternation. Level 1 finds strings that usually sit at a break and marks them odd; it will over-fire, because proposing is cheap. Level 2 looks at exactly the places level 1 got wrong and marks those even, which switches them off, because even beats odd when it is larger. Level 3 goes back through what level 2 over-suppressed. Each level corrects the last, and the numbers climb.

Press train. It fits on a few thousand words and is scored on words it never saw. Watch precision and recall take turns.

The zigzag is the design showing itself. In the lab run over the full lexicon, level 1 reaches 86.7% precision and 85.3% recall; level 2 pushes precision to 92.8% and costs half a point of recall; level 4 takes precision to 95.6% and again gives back recall; level 5 lifts recall to 94.7%. Nobody has to describe the alternation. It is in the numbers.

Your own run above will not match those, and should not. It fits on a few thousand words rather than 48,504, and the thresholds are absolute counts, so far fewer patterns clear them and every score lands lower. What survives the shrinking is the shape: retracting levels buy precision and pay for it in recall, proposing levels do the reverse, and the last proposing level trades a chunk of precision for a large jump in recall. If you see level 5 lose a couple of points of precision, that is the alternation working, not the fit failing.

What the fitting does not do is beat Liang. My learner needs 16,284 patterns to get 88.6% of held-out words exactly right, and 38,690 patterns to reach 92.6%, against a published file of 4,938 that is right by definition. patgen's staged search and hand-tuned weights are doing real work that the alternating idea alone does not supply. Only 13.1% of the letter sequences my fit chose appear anywhere in the published file, so the two runs are not even exploring the same neighbourhood.

One caution about what is being fitted here, since it is the thing that could quietly turn this section into a lie. The training targets are the breaks the published American patterns permit, not the breaks a dictionary prints. I have no independent hyphenated dictionary of sixty thousand words, and inventing one would be worse than not having one. So this measures how compressible the published model's behaviour is, and how well pattern fitting generalises to unseen words. It cannot say whether the answers are right, and it is not asked to.

7. The dead weight

A pattern earns its place only if it fires. Over the full 62,156-word lexicon, 280 of the American file's 4,938 patterns never occur in a single word, and 602 of them, 12.2%, never change the answer anywhere: whatever they propose, something else was already proposing the same parity in that gap. The British file, larger, is emptier still: 1,439 patterns never match a word and 27.7% never change an outcome.

That is not a criticism of either file. A pattern that never fires on this lexicon may fire on a word neither list contains, and both files were fitted against dictionaries larger and older than a Debian word list. It is a measurement of how much of a fitted model is load-bearing for the vocabulary you actually meet, and the answer is: most of it, but not all, and less of it the bigger the model gets.

What the check panel checks

Everything above that is a number is recomputed below, in your browser, from the three pattern files and the word list shipped with this page. The one thing your browser cannot redo is the comparison against TeX itself, because TeX is not here; that arm ran offline over every word and its result is reported as an offline result.