344  PART 42: HYPHENATION  TEX82 §919

919. Hyphenation. When a word hc[1 . . hn] has been set up to contain a candidate for hyphenation, TEX first looks to see if it is in the user’s exception dictionary. If not, hyphens are inserted based on patterns that appear within the given word, using an algorithm due to Frank M. Liang.

Let’s consider Liang’s method first, since it is much more interesting than the exception-lookup routine. The algorithm begins by setting hyf [j] to zero for all j, and invalid characters are inserted into hc[0] and hc[hn +1] to serve as delimiters. Then a reasonably fast method is used to see which of a given set of patterns occurs in the word hc[0 . . (hn + 1)]. Each pattern p_{1} … p_{k} of length k has an associated sequence of k + 1 numbers n_{0} … n_{k}; and if the pattern occurs in hc[(j+1) . . (j+k)], TEX will set hyf [j+i] ← max(hyf [j+i], n_{i}) for 0 ≤ i ≤ k. After this has been done for each pattern that occurs, a discretionary hyphen will be inserted between hc[j] and hc[j + 1] when hyf [j] is odd, as we have already seen.

The set of patterns p_{1} … p_{k} and associated numbers n_{0} … n_{k} depends, of course, on the language whose words are being hyphenated, and on the degree of hyphenation that is desired. A method for finding appropriate p’s and n’s, from a given dictionary of words and acceptable hyphenations, is discussed in Liang’s Ph.D. thesis (Stanford University, 1983); TEX simply starts with the patterns and works from there.

920. The patterns are stored in a compact table that is also efficient for retrieval, using a variant of “trie memory” [cf. The Art of Computer Programming 3 (1973), 481–505]. We can find each pattern p_{1} … p_{k} by letting z_{0} be one greater than the relevant language index and then, for 1 ≤ i ≤ k, setting z_{i} ← trie link (z_{i−1}) + p_{i}; the pattern will be identified by the number z_{k}. Since all the pattern information is packed together into a single trie link array, it is necessary to prevent confusion between the data from inequivalent patterns, so another table is provided such that trie char (z_{i}) = p_{i} for all i. There is also a table trie op(z_{k}) to identify the numbers n_{0} … n_{k} associated with p_{1} … p_{k}.

Comparatively few different number sequences n_{0} … n_{k} actually occur, since most of the n’s are generally zero. Therefore the number sequences are encoded in such a way that trie op(z_{k}) is only one byte long. If trie op(z_{k}) ≠ min quarterword , when p_{1} … p_{k} has matched the letters in hc[(l −k +1) . . l] of language t, we perform all of the required operations for this pattern by carrying out the following little program: Set v ← trie op(z_{k}). Then set v ← v+op start [t], hyf [l−hyf distance[v]] ← max(hyf [l−hyf distance[v]], hyf num[v]), and v ← hyf next [v]; repeat, if necessary, until v = min quarterword . ⟨ Types in the outer block 18 ⟩ +≡

trie pointer = 0 . . trie size; { an index into trie }

921. define trie link (#) ≡ trie[#].rh { “downward” link in a trie } define trie char (#) ≡ trie[#].b1 { character matched at this trie location } define trie op(#) ≡ trie[#].b0 { program for hyphenation at this trie location }

⟨ Global variables 13 ⟩ +≡ trie: array [trie pointer ] of two halves ; { trie link , trie char , trie op } hyf distance: array [1 . . trie op size] of small number ; { position k − j of n_{j} } hyf num: array [1 . . trie op size] of small number ; { value of n_{j} } hyf next : array [1 . . trie op size] of quarterword ; { continuation code } op start : array [ASCII code] of 0 . . trie op size; { offset for current language }

§923  TEX82  PART 42: HYPHENATION 345

922. ⟨ Local variables for hyphenation 901 ⟩ +≡ z: trie pointer ; { an index into trie } v: integer ; { an index into hyf distance, etc. } 923. Assuming that these auxiliary tables have been set up properly, the hyphenation algorithm is quite short. In the following code we set hc[hn + 2] to the impossible value 256, in order to guarantee that hc[hn + 3] will never be fetched. ⟨ Find hyphen locations for the word in hc, or return 923 ⟩ ≡

for j ← 0 to hn do hyf [j] ← 0;

⟨ Look for the word hc[1 . . hn] in the exception table, and goto found (with hyf containing the hyphens)

if an entry is found 930 ⟩; if trie char (cur lang + 1) ≠ qi (cur lang ) then return; { no patterns for cur lang } hc[0] ← 0; hc[hn + 1] ← 0; hc[hn + 2] ← 256; { insert delimiters } for j ← 0 to hn − r hyf + 1 do

begin z ← trie link (cur lang + 1) + hc[j]; l ← j; while hc[l] = qo(trie char (z)) do

begin if trie op(z) ≠ min quarterword then ⟨ Store maximum values in the hyf table 924 ⟩; incr (l); z ← trie link (z) + hc[l]; end; end;

found : for j ← 0 to l hyf − 1 do hyf [j] ← 0;

for j ← 0 to r hyf − 1 do hyf [hn − j] ← 0

This code is used in section 895.

924. ⟨ Store maximum values in the hyf table 924 ⟩ ≡ begin v ← trie op(z); repeat v ← v + op start [cur lang ]; i ← l − hyf distance[v];

if hyf num[v] > hyf [i] then hyf [i] ← hyf num[v]; v ← hyf next [v];

until v = min quarterword ;

end

This code is used in section 923.

925. The exception table that is built by TEX’s primitive is organized as an ordered hash table [cf. Amble and Knuth, The Computer Journal 17 (1974), 135–142] using linear probing. If α and β are words, we will say that α < β if |α| < |β| or if |α| = |β| and α is lexicographically smaller than β. (The notation |α| stands for the length of α.) The idea of ordered hashing is to arrange the table so that a given word α can be sought by computing a hash address h = h(α) and then looking in table positions h, h − 1, …, until encountering the first word ≤ α. If this word is different from α, we can conclude that α is not in the table.

The words in the table point to lists in mem that specify hyphen positions in their info fields. The list for c_{1} … c_{n} contains the number k if the word c_{1} … c_{n} has a discretionary hyphen between c_{k} and c_{k+1}. ⟨ Types in the outer block 18 ⟩ +≡

hyph pointer = 0 . . hyph size; { an index into the ordered hash table }

926. ⟨ Global variables 13 ⟩ +≡ hyph word : array [hyph pointer ] of str number ; { exception words } hyph list : array [hyph pointer ] of pointer ; { list of hyphen positions } hyph count : hyph pointer ; { the number of words in the exception dictionary }

927. ⟨ Local variables for initialization 19 ⟩ +≡ z: hyph pointer ; { runs through the exception dictionary } 928. ⟨ Set initial values of key variables 21 ⟩ +≡

for z ← 0 to hyph size do begin hyph word [z] ← 0; hyph list [z] ← null ; end;

hyph count ← 0;

929. The algorithm for exception lookup is quite simple, as soon as we have a few more local variables to work with. ⟨ Local variables for hyphenation 901 ⟩ +≡ h: hyph pointer ; { an index into hyph word and hyph list } k: str number ; { an index into str start } u: pool pointer ; { an index into str pool }

930. First we compute the hash code h, then we search until we either find the word or we don’t. Words from different languages are kept separate by appending the language code to the string. ⟨ Look for the word hc[1 . . hn] in the exception table, and goto found (with hyf containing the hyphens) if

an entry is found 930 ⟩ ≡ h ← hc[1]; incr (hn); hc[hn] ← cur lang ; for j ← 2 to hn do h ← (h + h + hc[j]) mod hyph size; loop begin ⟨ If the string hyph word [h] is less than hc[1 . . hn], goto not found ; but if the two strings

are equal, set hyf to the hyphen positions and goto found 931 ⟩; if h > 0 then decr (h) else h ← hyph size; end;

not found : decr (hn)

This code is used in section 923.

931. ⟨ If the string hyph word [h] is less than hc[1 . . hn], goto not found ; but if the two strings are equal,

set hyf to the hyphen positions and goto found 931 ⟩ ≡ k ← hyph word [h]; if k = 0 then goto not found ; if length(k) < hn then goto not found ; if length(k) = hn then

begin j ← 1; u ← str start [k];

repeat if so(str pool [u]) < hc[j] then goto not found ; if so(str pool [u]) > hc[j] then goto done; incr (j); incr (u);

until j > hn;

⟨ Insert hyphens as specified in hyph list [h] 932 ⟩; decr (hn); goto found ; end;

done:

This code is used in section 930.

932. ⟨ Insert hyphens as specified in hyph list [h] 932 ⟩ ≡ s ← hyph list [h]; while s ≠ null do

begin hyf [info(s)] ← 1; s ← link (s);

end

This code is used in section 931.

933. ⟨ Search hyph list for pointers to p 933 ⟩ ≡

for q ← 0 to hyph size do

begin if hyph list [q] = p then begin print nl ( ); print int (q); print char ( ); end;

end

This code is used in section 172.

934. We have now completed the hyphenation routine, so the line break procedure is finished at last. Since the hyphenation exception table is fresh in our minds, it’s a good time to deal with the routine that adds new entries to it.

When TEX has scanned ‘ ’, it calls on a procedure named new hyph exceptions to do the right thing.

define set cur lang ≡ if language ≤ 0 then cur lang ← 0 else if language > 255 then cur lang ← 0

else cur lang ← language

procedure new hyph exceptions ; { enters new exceptions } label reswitch, exit , found , not found ; var n: 0 . . 64; { length of current word; not always a small number }

j: 0 . . 64; { an index into hc } h: hyph pointer ; { an index into hyph word and hyph list } k: str number ; { an index into str start } p: pointer ; { head of a list of hyphen positions } q: pointer ; { used when creating a new node for list p } s, t: str number ; { strings being compared or stored } u, v: pool pointer ; { indices into str pool }

begin scan left brace; { a left brace must follow } set cur lang ; ⟨ Enter as many hyphenation exceptions as are listed, until coming to a right brace; then return 935 ⟩;

exit : end;

935. ⟨ Enter as many hyphenation exceptions as are listed, until coming to a right brace; then

return 935 ⟩ ≡

n ← 0; p ← null ; loop begin get x token; reswitch: case cur cmd of

letter , other char , char given: ⟨ Append a new letter or hyphen 937 ⟩; char num: begin scan char num; cur chr ← cur val ; cur cmd ← char given; goto reswitch;

end; spacer , right brace: begin if n > 1 then ⟨ Enter a hyphenation exception 939 ⟩;

if cur cmd = right brace then return;

n ← 0; p ← null ;

end; othercases ⟨ Give improper error 936 ⟩ endcases; end

This code is used in section 934.

936. ⟨ Give improper error 936 ⟩ ≡

begin print err (  ␣ ); print esc(  ); print ( ␣    ␣  ␣  );
help2 (  ␣          ␣    ␣       ␣    ␣  )
(  ␣        ␣   ␣         ␣ ´ ␣       ␣   ␣  ); error ;

end

This code is used in section 935.

937. ⟨ Append a new letter or hyphen 937 ⟩ ≡ if cur chr = then ⟨ Append the value n to list p 938 ⟩ else begin if lc code(cur chr ) = 0 then

begin print err (  ␣ ␣  );
help2 (  ␣  ␣           ␣     ␣    ␣    ␣  )
(  ␣ ´ ␣      ␣   ␣         ␣ ␣    ␣  ); error ;

end else if n < 63 then

begin incr (n); hc[n] ← lc code(cur chr ); end;

end

This code is used in section 935.

938. ⟨ Append the value n to list p 938 ⟩ ≡

begin if n < 63 then begin q ← get avail ; link (q) ← p; info(q) ← n; p ← q; end;

end

This code is used in section 937.

939. ⟨ Enter a hyphenation exception 939 ⟩ ≡ begin incr (n); hc[n] ← cur lang ; str room(n); h ← 0; for j ← 1 to n do

begin h ← (h + h + hc[j]) mod hyph size; append char (hc[j]);

end; s ← make string ; ⟨ Insert the pair (s, p) into the exception table 940 ⟩; end

This code is used in section 935.

940. ⟨ Insert the pair (s, p) into the exception table 940 ⟩ ≡ if hyph count = hyph size then overflow ( ␣ , hyph size); incr (hyph count ); while hyph word [h] ≠ 0 do

begin ⟨ If the string hyph word [h] is less than or equal to s, interchange (hyph word [h], hyph list [h])

with (s, p) 941 ⟩; if h > 0 then decr (h) else h ← hyph size; end;

hyph word [h] ← s; hyph list [h] ← p

This code is used in section 939.

941. ⟨ If the string hyph word [h] is less than or equal to s, interchange (hyph word [h], hyph list [h]) with

(s, p) 941 ⟩ ≡ k ← hyph word [h]; if length(k) < length(s) then goto found ; if length(k) > length(s) then goto not found ; u ← str start [k]; v ← str start [s]; repeat if str pool [u] < str pool [v] then goto found ;

if str pool [u] > str pool [v] then goto not found ; incr (u); incr (v);

until u = str start [k + 1]; found : q ← hyph list [h]; hyph list [h] ← p; p ← q;

t ← hyph word [h]; hyph word [h] ← s; s ← t; not found :

This code is used in section 940.