350  PART 43: INITIALIZING THE HYPHENATION TABLES  TEX82 §942

942. Initializing the hyphenation tables. The trie for TEX’s hyphenation algorithm is built from a sequence of patterns following a specification. Such a specification is allowed only in , since the extra memory for auxiliary tables and for the initialization program itself would only clutter up the production version of TEX with a lot of deadwood.

The first step is to build a trie that is linked, instead of packed into sequential storage, so that insertions are readily made. After all patterns have been processed, compresses the linked trie by identifying common subtries. Finally the trie is packed into the efficient sequential form that the hyphenation algorithm actually uses. ⟨ Declare subprocedures for line break 826 ⟩ +≡

init ⟨ Declare procedures for preprocessing hyphenation patterns 944 ⟩

tini

943. Before we discuss trie building in detail, let’s consider the simpler problem of creating the hyf distance, hyf num, and hyf next arrays.

Suppose, for example, that TEX reads the pattern ‘ ’. This is a pattern of length 5, with n_{0} … n_{5} = 0 0 2 0 0 1 in the notation above. We want the corresponding trie op code v to have hyf distance[v] = 3, hyf num[v] = 2, and hyf next [v] = v′, where the auxiliary trie op code v′ has hyf distance[v′] = 0, hyf num[v′] = 1, and hyf next [v′] = min quarterword .

TEX computes an appropriate value v with the new trie op subroutine below, by setting

v′ ← new trie op(0, 1, min quarterword ), v ← new trie op(3, 2, v′).

This subroutine looks up its three parameters in a special hash table, assigning a new value only if these three have not appeared before for the current language.

The hash table is called trie op hash, and the number of entries it contains is trie op ptr . ⟨ Global variables 13 ⟩ +≡

init trie op hash: array [−trie op size . . trie op size] of 0 . . trie op size;

{ trie op codes for quadruples }

trie used : array [ASCII code] of quarterword ; { largest opcode used so far for this language } trie op lang : array [1 . . trie op size] of ASCII code; { language part of a hashed quadruple } trie op val : array [1 . . trie op size] of quarterword ; { opcode corresponding to a hashed quadruple } trie op ptr : 0 . . trie op size; { number of stored ops so far }

§944  TEX82  PART 43: INITIALIZING THE HYPHENATION TABLES 351

tini 944. It’s tempting to remove the overflow stops in the following procedure; new trie op could return min quarterword (thereby simply ignoring part of a hyphenation pattern) instead of aborting the job. However, that would lead to different hyphenation results on different installations of TEX using the same patterns. The overflow stops are necessary for portability of patterns. ⟨ Declare procedures for preprocessing hyphenation patterns 944 ⟩ ≡ function new trie op(d, n : small number ; v : quarterword ): quarterword ;

label exit ; var h: −trie op size . . trie op size; { trial hash location }

u: quarterword ; { trial op code } l: 0 . . trie op size; { pointer to stored data }

begin h ← abs (n + 313 ∗ d + 361 ∗ v + 1009 ∗ cur lang ) mod (trie op size + trie op size) − trie op size; loop begin l ← trie op hash[h];

if l = 0 then { empty position found for a new op } begin if trie op ptr = trie op size then overflow ( ␣ ␣ , trie op size); u ← trie used [cur lang ]; if u = max quarterword then

overflow ( ␣ ␣ ␣ ␣ , max quarterword − min quarterword ); incr (trie op ptr ); incr (u); trie used [cur lang ] ← u; hyf distance[trie op ptr ] ← d; hyf num[trie op ptr ] ← n; hyf next [trie op ptr ] ← v; trie op lang [trie op ptr ] ← cur lang ; trie op hash[h] ← trie op ptr ; trie op val [trie op ptr ] ← u; new trie op ← u; return; end;

if (hyf distance[l] = d) ∧ (hyf num[l] = n) ∧ (hyf next [l] = v) ∧ (trie op lang [l] = cur lang ) then begin new trie op ← trie op val [l]; return; end;

if h > −trie op size then decr (h) else h ← trie op size; end;

exit : end;

See also sections 948, 949, 953, 957, 959, 960, and 966. This code is used in section 942.

945. After new trie op has compressed the necessary opcode information, plenty of information is available to unscramble the data into the final form needed by our hyphenation algorithm. ⟨ Sort the hyphenation op tables into proper order 945 ⟩ ≡

op start [0] ← −min quarterword ; for j ← 1 to 255 do op start [j] ← op start [j − 1] + qo(trie used [j − 1]); for j ← 1 to trie op ptr do trie op hash[j] ← op start [trie op lang [j]] + trie op val [j]; { destination } for j ← 1 to trie op ptr do

while trie op hash[j] > j do begin k ← trie op hash[j]; t ← hyf distance[k]; hyf distance[k] ← hyf distance[j]; hyf distance[j] ← t; t ← hyf num[k]; hyf num[k] ← hyf num[j]; hyf num[j] ← t; t ← hyf next [k]; hyf next [k] ← hyf next [j]; hyf next [j] ← t; trie op hash[j] ← trie op hash[k]; trie op hash[k] ← k; end

This code is used in section 952.

946. Before we forget how to initialize the data structures that have been mentioned so far, let’s write down the code that gets them started. ⟨ Initialize table entries (done by only) 164 ⟩ +≡

for k ← −trie op size to trie op size do trie op hash[k] ← 0;

for k ← 0 to 255 do trie used [k] ← min quarterword ;

trie op ptr ← 0;

947. The linked trie that is used to preprocess hyphenation patterns appears in several global arrays. Each node represents an instruction of the form “if you see character c, then perform operation o, move to the next character, and go to node l; otherwise go to node r.” The four quantities c, o, l, and r are stored in four arrays trie c, trie o, trie l , and trie r . The root of the trie is trie l [0], and the number of nodes is trie ptr . Null trie pointers are represented by zero. To initialize the trie, we simply set trie l [0] and trie ptr to zero. We also set trie c[0] to some arbitrary value, since the algorithm may access it.

The algorithms maintain the condition

trie c[trie r [z]] > trie c[z] whenever z ≠ 0 and trie r [z] ≠ 0;

in other words, sibling nodes are ordered by their c fields.

define trie root ≡ trie l [0] { root of the linked trie } ⟨ Global variables 13 ⟩ +≡

init trie c: packed array [trie pointer ] of packed ASCII code; { characters to match } trie o: packed array [trie pointer ] of quarterword ; { operations to perform } trie l : packed array [trie pointer ] of trie pointer ; { left subtrie links } trie r : packed array [trie pointer ] of trie pointer ; { right subtrie links } trie ptr : trie pointer ; { the number of nodes in the trie } trie hash: packed array [trie pointer ] of trie pointer ; { used to identify equivalent subtries } tini

948. Let us suppose that a linked trie has already been constructed. Experience shows that we can often reduce its size by recognizing common subtries; therefore another hash table is introduced for this purpose, somewhat similar to trie op hash. The new hash table will be initialized to zero.

The function trie node(p) returns p if p is distinct from other nodes that it has seen, otherwise it returns the number of the first equivalent node that it has seen.

Notice that we might make subtries equivalent even if they correspond to patterns for different languages, in which the trie ops might mean quite different things. That’s perfectly all right. ⟨ Declare procedures for preprocessing hyphenation patterns 944 ⟩ +≡ function trie node(p : trie pointer ): trie pointer ; { converts to a canonical form }

label exit ;

var h: trie pointer ; { trial hash location }

q: trie pointer ; { trial trie node } begin h ← abs (trie c[p] + 1009 ∗ trie o[p] + 2718 ∗ trie l [p] + 3142 ∗ trie r [p]) mod trie size; loop begin q ← trie hash[h];

if q = 0 then begin trie hash[h] ← p; trie node ← p; return; end;

if (trie c[q] = trie c[p]) ∧ (trie o[q] = trie o[p]) ∧ (trie l [q] = trie l [p]) ∧ (trie r [q] = trie r [p]) then begin trie node ← q; return; end;

if h > 0 then decr (h) else h ← trie size;

end; exit : end; 949. A neat recursive procedure is now able to compress a trie by traversing it and applying trie node to its nodes in “bottom up” fashion. We will compress the entire trie by clearing trie hash to zero and then saying ‘trie root ← compress trie(trie root )’. ⟨ Declare procedures for preprocessing hyphenation patterns 944 ⟩ +≡ function compress trie(p : trie pointer ): trie pointer ;

begin if p = 0 then compress trie ← 0

else begin trie l [p] ← compress trie(trie l [p]); trie r [p] ← compress trie(trie r [p]); compress trie ← trie node(p); end;

end;

950. The compressed trie will be packed into the trie array using a “top-down first-fit” procedure. This is a little tricky, so the reader should pay close attention: The trie hash array is cleared to zero again and renamed trie ref for this phase of the operation; later on, trie ref [p] will be nonzero only if the linked trie node p is the smallest character in a family and if the characters c of that family have been allocated to locations trie ref [p] + c in the trie array. Locations of trie that are in use will have trie link = 0, while the unused holes in trie will be doubly linked with trie link pointing to the next larger vacant location and trie back pointing to the next smaller one. This double linking will have been carried out only as far as trie max , where trie max is the largest index of trie that will be needed. To save time at the low end of the trie, we maintain array entries trie min[c] pointing to the smallest hole that is greater than c. Another array trie taken tells whether or not a given location is equal to trie ref [p] for some p; this array is used to ensure that distinct nodes in the compressed trie will have distinct trie ref entries.

define trie ref ≡ trie hash { where linked trie families go into trie }

define trie back (#) ≡ trie[#].lh { backward links in trie holes } ⟨ Global variables 13 ⟩ +≡

init trie taken: packed array [1 . . trie size] of boolean; { does a family start here? } trie min: array [ASCII code] of trie pointer ; { the first possible slot for each character } trie max : trie pointer ; { largest location used in trie } trie not ready : boolean; { is the trie still in linked form? } tini

951. Each time appears, it contributes further patterns to the future trie, which will be built only when hyphenation is attempted or when a format file is dumped. The boolean variable trie not ready will change to false when the trie is compressed; this will disable further patterns. ⟨ Initialize table entries (done by only) 164 ⟩ +≡

trie not ready ← true; trie root ← 0; trie c[0] ← si (0); trie ptr ← 0;

952. Here is how the trie-compression data structures are initialized. If storage is tight, it would be possible to overlap trie op hash, trie op lang , and trie op val with trie, trie hash, and trie taken, because we finish with the former just before we need the latter. ⟨ Get ready to compress the trie 952 ⟩ ≡

⟨ Sort the hyphenation op tables into proper order 945 ⟩;

for p ← 0 to trie size do trie hash[p] ← 0;

trie root ← compress trie(trie root ); { identify equivalent subtries }

for p ← 0 to trie ptr do trie ref [p] ← 0;

for p ← 0 to 255 do trie min[p] ← p + 1;

trie link (0) ← 1; trie max ← 0

This code is used in section 966.

953. The first fit procedure finds the smallest hole z in trie such that a trie family starting at a given node p will fit into vacant positions starting at z. If c = trie c[p], this means that location z − c must not already be taken by some other family, and that z − c + c′ must be vacant for all characters c′ in the family. The procedure sets trie ref [p] to z − c when the first fit has been found. ⟨ Declare procedures for preprocessing hyphenation patterns 944 ⟩ +≡ procedure first fit (p : trie pointer ); { packs a family into trie }

label not found , found ; var h: trie pointer ; { candidate for trie ref [p] }

z: trie pointer ; { runs through holes } q: trie pointer ; { runs through the family starting at p } c: ASCII code; { smallest character in the family } l, r: trie pointer ; { left and right neighbors } ll : 1 . . 256; { upper limit of trie min updating }

begin c ← so(trie c[p]); z ← trie min[c]; { get the first conceivably good hole } loop begin h ← z − c;

⟨ Ensure that trie max ≥ h + 256 954 ⟩; if trie taken[h] then goto not found ; ⟨ If all characters of the family fit relative to h, then goto found , otherwise goto not found 955 ⟩;

not found : z ← trie link (z); { move to the next hole }

end; found : ⟨ Pack the family into trie relative to h 956 ⟩;

end;

954. By making sure that trie max is at least h + 256, we can be sure that trie max > z, since h = z − c. It follows that location trie max will never be occupied in trie, and we will have trie max ≥ trie link (z). ⟨ Ensure that trie max ≥ h + 256 954 ⟩ ≡

if trie max < h + 256 then begin if trie size ≤ h + 256 then overflow ( ␣ , trie size); repeat incr (trie max ); trie taken[trie max ] ← false; trie link (trie max ) ← trie max + 1;

trie back (trie max ) ← trie max − 1; until trie max = h + 256; end

This code is used in section 953.

955. ⟨ If all characters of the family fit relative to h, then goto found , otherwise goto not found 955 ⟩ ≡ q ← trie r [p]; while q > 0 do

begin if trie link (h + so(trie c[q])) = 0 then goto not found ; q ← trie r [q]; end;

goto found

This code is used in section 953.

956. ⟨ Pack the family into trie relative to h 956 ⟩ ≡ trie taken[h] ← true; trie ref [p] ← h; q ← p; repeat z ← h + so(trie c[q]); l ← trie back (z); r ← trie link (z); trie back (r) ← l; trie link (l) ← r;

trie link (z) ← 0; if l < 256 then

begin if z < 256 then ll ← z else ll ← 256;

repeat trie min[l] ← r; incr (l);

until l = ll ;

end; q ← trie r [q];

until q = 0

This code is used in section 953.

957. To pack the entire linked trie, we use the following recursive procedure. ⟨ Declare procedures for preprocessing hyphenation patterns 944 ⟩ +≡ procedure trie pack (p : trie pointer ); { pack subtries of a family }

var q: trie pointer ; { a local variable that need not be saved on recursive calls } begin repeat q ← trie l [p];

if (q > 0) ∧ (trie ref [q] = 0) then begin first fit (q); trie pack (q); end;

p ← trie r [p]; until p = 0; end;

958. When the whole trie has been allocated into the sequential table, we must go through it once again so that trie contains the correct information. Null pointers in the linked trie will be represented by the value 0, which properly implements an “empty” family. ⟨ Move the data into trie 958 ⟩ ≡

h.rh ← 0; h.b0 ← min quarterword ; h.b1 ← min quarterword ;

{ trie link ← 0, trie op ← min quarterword , trie char ← qi (0) } if trie root = 0 then { no patterns were given }

begin for r ← 0 to 256 do trie[r] ← h; trie max ← 256; end

else begin trie fix (trie root ); { this fixes the non-holes in trie } r ← 0; { now we will zero out all the holes } repeat s ← trie link (r); trie[r] ← h; r ← s; until r > trie max ; end;

trie char (0) ← qi ( ); { make trie char (c) ≠ c for all c }

This code is used in section 966.

959. The fixing-up procedure is, of course, recursive. Since the linked trie usually has overlapping subtries, the same data may be moved several times; but that causes no harm, and at most as much work is done as it took to build the uncompressed trie. ⟨ Declare procedures for preprocessing hyphenation patterns 944 ⟩ +≡ procedure trie fix (p : trie pointer ); { moves p and its siblings into trie }

var q: trie pointer ; { a local variable that need not be saved on recursive calls } c: ASCII code; { another one that need not be saved } z: trie pointer ; { trie reference; this local variable must be saved }

begin z ← trie ref [p]; repeat q ← trie l [p]; c ← so(trie c[p]); trie link (z + c) ← trie ref [q]; trie char (z + c) ← qi (c);

trie op(z + c) ← trie o[p]; if q > 0 then trie fix (q); p ← trie r [p];

until p = 0; end;

960. Now let’s go back to the easier problem, of building the linked trie. When has scanned the ‘ ’ control sequence, it calls on new patterns to do the right thing. ⟨ Declare procedures for preprocessing hyphenation patterns 944 ⟩ +≡ procedure new patterns ; { initializes the hyphenation pattern data }

label done, done1 ; var k, l: 0 . . 64; { indices into hc and hyf ; not always in small number range }

digit sensed : boolean; { should the next digit be treated as a letter? } v: quarterword ; { trie op code } p, q: trie pointer ; { nodes of trie traversed during insertion } first child : boolean; { is p = trie l [q]? } c: ASCII code; { character being inserted }

begin if trie not ready then

begin set cur lang ; scan left brace; { a left brace must follow } ⟨ Enter all of the patterns into a linked trie, until coming to a right brace 961 ⟩; end

else begin print err (  ␣    ␣   ␣ ); print esc(  );
help1 (  ␣        ␣    ␣  ␣     ␣      ␣          ␣  ); error ;

link (garbage) ← scan toks (false, false); flush list (def ref ); end;

end; 961. Novices are not supposed to be using , so the error messages are terse. (Note that all error messages appear in TEX’s string pool, even if they are used only by .) ⟨ Enter all of the patterns into a linked trie, until coming to a right brace 961 ⟩ ≡

k ← 0; hyf [0] ← 0; digit sensed ← false; loop begin get x token;

case cur cmd of

letter , other char : ⟨ Append a new letter or a hyphen level 962 ⟩; spacer , right brace: begin if k > 0 then ⟨ Insert a new pattern into the linked trie 963 ⟩;

if cur cmd = right brace then goto done;

k ← 0; hyf [0] ← 0; digit sensed ← false;

end; othercases begin print err ( ␣ ); print esc( ); help1 ( ␣ ␣ ); error ;

end endcases; end;

done:

This code is used in section 960.

962. ⟨ Append a new letter or a hyphen level 962 ⟩ ≡

if digit sensed ∨ (cur chr < ) ∨ (cur chr > ) then begin if cur chr = then cur chr ← 0 { edge-of-word delimiter } else begin cur chr ← lc code(cur chr );

if cur chr = 0 then begin print err ( ); help1 ( ␣ ␣ ); error ; end;

end; if k < 63 then

begin incr (k); hc[k] ← cur chr ; hyf [k] ← 0; digit sensed ← false; end;

end else if k < 63 then

begin hyf [k] ← cur chr − ; digit sensed ← true;

end

This code is used in section 961.

963. When the following code comes into play, the pattern p_{1} … p_{k} appears in hc[1 . . k], and the corresponding sequence of numbers n_{0} … n_{k} appears in hyf [0 . . k]. ⟨ Insert a new pattern into the linked trie 963 ⟩ ≡

begin ⟨ Compute the trie op code, v, and set l ← 0 965 ⟩; q ← 0; hc[0] ← cur lang ; while l ≤ k do

begin c ← hc[l]; incr (l); p ← trie l [q]; first child ← true;

while (p > 0) ∧ (c > so(trie c[p])) do begin q ← p; p ← trie r [q]; first child ← false; end;

if (p = 0) ∨ (c < so(trie c[p])) then

⟨ Insert a new trie node between q and p, and make p point to it 964 ⟩; q ← p; { now node q represents p_{1} … p_{l} } end;

if trie o[q] ≠ min quarterword then begin print err ( ␣ ); help1 ( ␣ ␣ ); error ; end;

trie o[q] ← v; end

This code is used in section 961.

964. ⟨ Insert a new trie node between q and p, and make p point to it 964 ⟩ ≡ begin if trie ptr = trie size then overflow ( ␣ , trie size); incr (trie ptr ); trie r [trie ptr ] ← p; p ← trie ptr ; trie l [p] ← 0; if first child then trie l [q] ← p else trie r [q] ← p; trie c[p] ← si (c); trie o[p] ← min quarterword ; end

This code is used in section 963.

965. ⟨ Compute the trie op code, v, and set l ← 0 965 ⟩ ≡ if hc[1] = 0 then hyf [0] ← 0; if hc[k] = 0 then hyf [k] ← 0; l ← k; v ← min quarterword ; loop begin if hyf [l] ≠ 0 then v ← new trie op(k − l, hyf [l], v);

if l > 0 then decr (l) else goto done1 ;

end; done1 :

This code is used in section 963.

966. Finally we put everything together: Here is how the trie gets to its final, efficient form. The following packing routine is rigged so that the root of the linked tree gets mapped into location 1 of trie, as required by the hyphenation algorithm. This happens because the first call of first fit will “take” location 1. ⟨ Declare procedures for preprocessing hyphenation patterns 944 ⟩ +≡ procedure init trie;

var p: trie pointer ; { pointer for initialization } j, k, t: integer ; { all-purpose registers for initialization } r, s: trie pointer ; { used to clean up the packed trie } h: two halves ; { template used to zero out trie’s holes }

begin ⟨ Get ready to compress the trie 952 ⟩; if trie root ≠ 0 then

begin first fit (trie root ); trie pack (trie root );

end; ⟨ Move the data into trie 958 ⟩; trie not ready ← false; end;