Stanford Lecture: The Internal Details of TeX82 - Session 8 (July 29, 1982)

Key Concepts

• Hyphenation Algorithm: A method for determining where to break words at the end of a line to improve text layout.
• Pattern-Based Hyphenation: A technique where hyphenation rules are defined by patterns of characters and associated numerical values.
• Numerical Values in Patterns: Zeros indicate no hyphenation, odd numbers indicate hyphenation points, and even numbers indicate suppressed hyphenation. Higher numbers represent stronger preferences.
• Trie (Digital Search Tree): An efficient data structure for storing and searching strings, used here to store hyphenation patterns.
• Hyphenation Exception List: A list of specific words that are handled differently from the general hyphenation rules.
• Ligatures: Characters formed by combining two or more letters, which can complicate hyphenation.
• Kerning: Adjusting the space between characters for aesthetic purposes.
• Discretionary Hyphen: A hyphen inserted by the user or algorithm that may or may not be used depending on line breaking.
• Web (Literate Programming): A programming paradigm where code is interspersed with explanatory text.
• CPU Minutes: A measure of computational time.

New Hyphenation Algorithm in TeX

This presentation introduces a new, advanced hyphenation algorithm for TeX, developed by "tex82" and detailed in an upcoming thesis. The algorithm aims to improve hyphenation accuracy and efficiency, particularly for foreign languages.

Core Mechanism: Pattern-Based Hyphenation

The fundamental principle of the new algorithm is based on patterns. These patterns are sequences of characters with associated numerical values.

• Pattern Structure: A pattern might look like a, b2, d.
• Numerical Interpretation:
  • Zero (0): Indicates no hyphenation is allowed at that position.
  • Odd Numbers (1, 3, 5, etc.): Indicate a potential hyphenation point. Higher odd numbers signify stronger preference for hyphenation.
  • Even Numbers (2, 4, etc.): Indicate a suppression of hyphenation. Higher even numbers represent stronger suppression.
• Algorithm Logic:
  1. For a given word, all applicable patterns are identified.
  2. The numerical values from these patterns are combined (using maximum value).
  3. If the final result for a position is odd, it's a valid hyphenation point.
  4. If the final result is even, it's not a hyphenation point.
  5. Higher numbers (e.g., 3 overriding 1, or 2 overriding 0) take precedence.

Pattern Examples and Data

• Pattern List Size: The English hyphenation patterns used in the demonstration comprise 3,879 patterns.
• Pattern Notation: A dot (.) signifies the beginning of a word.
  • Example: .ace4 means that between 'c' and 'e' in a word starting with "ac", hyphenation should be strongly suppressed (indicated by '4').
  • Example: lpa-b with a '5' would indicate a strong preference for hyphenation.
• Pattern Generation: The patterns were generated by a program written in Web (a literate programming system) and took 57 CPU minutes to run on a Sunday. This program is intended to be adaptable for other languages and dictionaries.

Testing and Results

The algorithm was tested against various word lists and dictionaries:

• accept.hyphen: A list of words that were exceptions to the previous TeX hyphenation algorithm. The new algorithm successfully found hyphens in many of these.
• texcom: Words from the appendix of the TeX manual, considered important for computer scientists. The new algorithm picked up "almost every hyphen" in these words (e.g., "algorithm," "computer," "declaration").
• Webster's Pocket Dictionary: A dictionary of 101 pages that formed the basis for many hyphenation patterns.
  • Statistics: The algorithm achieved 88.3% of hyphens in this dictionary and made only 27 errors.
  • Errors: An error is defined as inserting a hyphen where it shouldn't be.
    • "associate": Identified as an error because the dictionary listed it with different syllable counts (noun vs. verb), leading to different hyphenation possibilities. This is considered a minor error.
• Commercial Newspaper Dictionary: A larger dictionary from a commercial firm for newspaper setting. The new patterns were checked against this to ensure accuracy on words not in the pocket dictionary.
• trip.tex: A test program designed to exercise TeX's features, including hyphenation. It was used to test hyphenation of unusual words like "bbbbbb".

tex-hyphen Program and Data Structures

A program called tex-hyphen was demonstrated, which allows users to input words and see how the hyphenation algorithm performs.

• Data Structure: The algorithm uses a trie (or digital search tree) to store patterns efficiently.
  • Trie Size: For English, the trie contains 5,207 words (nodes) and uses approximately 21 KB of memory (4 bytes per word).
  • Opcodes: Another table contains 174 opcodes (limited to 255).
• Hyphenation Notation in tex-hyphen:
  • Hyphen (-): Indicates a hyphen found by the algorithm.
  • Equals Sign (=): Indicates a position where an even number greater than 0 was found, meaning hyphenation was suppressed.
• Performance: The trie structure allows for very fast hyphenation lookups. The process involves a few instructions per iteration, and the loop typically terminates quickly.

Handling of Special Cases and Foreign Languages

• Multi-language Support: The algorithm is designed to support multiple languages, though currently, it handles only one language per paragraph. Extending it to switch between hyphenation tables is a potential future development.
• Left-to-Right vs. Right-to-Left: The algorithm assumes a single direction of text.
• Exceptions: A hyphenation exception table is maintained using ordered hashing. This table is checked first. If a word is not found in the exception table, the pattern matching process is used.
• Word Definition for Hyphenation:
  • Hyphenation is shut off inside math formulas.
  • The algorithm skips over punctuation (quotes, parentheses) and spaces to find the start of a word.
  • It considers a character a "letter" if it has a non-zero LC code (lowercase code).
  • Uppercase letters are converted to lowercase for lookup, and the original casing is preserved when inserting hyphens.
  • The process stops if it encounters a "dangerous" element like a discretionary hyphen, a box, or a math formula.
• Ligatures and Kerning:
  • Kerning: Ignored during hyphenation; the word is collected as if kerning wasn't present, and then kerning is reapplied.
  • Ligatures: If a letter is part of a ligature (e.g., a letter and a parenthesis), hyphenation starts after the ligature. If a letter is at the end of a ligature followed by a non-letter, that letter is excluded from hyphenation.
  • Candidate for Hyphenation: A sequence of nodes (character, ligature, or kern nodes) with at least five letters is considered a candidate.
• Foreign Languages: The algorithm shows promise for languages other than English, as many languages are considered less "weird" in their structure for hyphenation. The pattern generation program can be used with foreign dictionaries.
  • Example: A German word "Wissenschaften" and "computerwissenschaften" were tested successfully.
  • French: The handling of prefixes like "L'" in French was discussed, suggesting that common prefixes could be incorporated into patterns or dictionaries.
• Accents: The new ligature mechanism is seen as a solution for accents in foreign languages, as it allows hyphenation to work correctly, unlike previous methods that turned it off.
  • Example: Cyrillic fonts use ligatures for characters like "j1" and "j2" representing soft and hard stops. Patterns can be defined for these using a special escape mechanism (e.g., 0j10j21 where '0' indicates a digit is treated as a letter).

trip.tex and the "bbbbbb" Example

The trip.tex program was used to test extreme cases.

• "bbbbbb" Hyphenation:
  • The test program was configured to hyphenate uppercase letters and had a large line penalty.
  • The word "bbbbbb" was hyphenated as bb-b-bbb.
  • This specific hyphenation was achieved because "bbbbbb" was explicitly added as a hyphenation exception in the test program.
  • The algorithm's ability to handle ligatures was demonstrated:
    • BB became a ligature A.
    • B followed by B became A kern A.
    • The process of reconstructing the word with discretionary hyphens in the presence of ligatures was described as complex but important.
• "trip font": A custom TeX font metric file used in trip.tex that defines ligatures and kerning.
  • Ligature Examples:
    • BB -> A
    • B- -> C
    • B followed by C -> B kern C
  • Kerning Examples:
    • A followed by B -> A kern B
    • A followed by - -> A kern - (hyphen)

Future Directions and Related Concepts

• Spelling Verification: The pect trie structure used for hyphenation is also an extremely compact and efficient way to represent a spelling checker.
• Apostrophes: Apostrophes can be handled by including them in hyphenation patterns or by treating them as word terminators. This is particularly relevant for languages like French.
• System Dependencies: Tomorrow's sessions will focus on system-dependent aspects of TeX, with recommendations to review specific modules related to system dependencies for potential modification.

Notable Quotes

• "I'm in hyperspace." - Referring to the advanced nature of the new hyphenation algorithm.
• "Computers are wonderful." - Expressed with amusement during a demonstration of text manipulation.
• "So the success of this looks quite promising for just replacing this by another set of pattern." - Indicating the potential for adapting the algorithm to different languages.
• "And the answer is that you just put a 0 here and a 0 there and a 1 there. And if it sees a 0, then it assumes a digit after it is like a letter." - Explaining the escape mechanism for defining patterns with digits in ligatures.

Conclusion

The presented hyphenation algorithm represents a significant advancement in TeX's text typesetting capabilities. By employing a sophisticated pattern-matching system based on numerical values and utilizing an efficient trie data structure, it achieves high accuracy (88.3% in a large dictionary) with a compact representation. The algorithm's design also demonstrates a strong potential for adaptation to various languages, including handling complex linguistic features like ligatures and accents, which were previously problematic. The development process, including the generation of patterns and the use of test programs like trip.tex, highlights a rigorous approach to improving TeX's core functionalities.