\documentclass[preprint]{ltugboat} \usepackage{shortvrb} \usepackage{booktabs} \providecommand{\meta}[1]{\ensuremath{\langle\textit{#1}\rangle}} \makeatletter \providecommand{\eTeX}{$\m@th\varepsilon$-\TeX} \makeatother \hyphenation{pa-ra-me-ter} \emergencystretch=4mm \title{An extension of \TeX's hyphenation algorithm} \author{Matthias Clasen} %\address{} \netaddress{maclas@gmx.de} \setcounter{page}{1} \begin{document} \maketitle \MakeShortVerb{\|} \section{Introduction} \TeX{}'s hyphenation algorithm works quite well and has been adapted for a large number of languages. But there are a few shortcomings, which have been noticed long ago \cite{Mittelbach:90,MR:92}: \begin{itemize} \item While \TeX{} has provisions to deal with general discretionaries like \textit{ck$\rightarrow$k-k}, there is no way to generate these automatically in the same way as ordinary discretionaries. They have to be entered manually using macros like |"ck| from |german.sty|. \item \TeX{} has \cs{doublehyphendemerits} to discourage consecutive hyphenated lines, but there is no provision to enforce a specification like ``no more that three consecutive hyphenated lines''. \item All breakpoints inserted by the hyphenation algorithm are treated the same, although their quality might be quite different. Especially for languages like German it would be nice to prefer breakpoints at word boundaries over intra-word breakpoints. \end{itemize} I don't tackle the first problem, but I do propose a solution for the other problems in the sequel. \section{Extensions to \TeX{}} \subsection{Consecutive hyphens} \label{sec:linebreaking} \TeX's linebreaking algorithm does already keep track of the hyphenation status of the feasible line breaks. All one has to do to solve the second problem is to change this boolean parameter into an integer and accumulate the information for consecutive line breaks. This is not very difficult, since the data structures for line breaks (the |active_node| node type) has enough room for this information. Well, actually this is not quite true, since it fails to preserve the dynamic programming principle of optimality and thus might miss optimal solutions. To do it properly we have to maintain information about optimal solutions not only for each fitness class, but for each combination of fitness class and number of consecutive hyphens. This is what I have implemented. With this bookkeeping in place, it would in principle be possible to apply different demerits for arbitrary numbers of consecutive hyphens. I have implemented this only for three, four, and five lines since higher numbers are unlikely to be relevant in practice. The new demerits are made available as integer parameters \begin{quotation} \cs{threehyphendemerits},\\ \cs{fourhyphendemerits}, \end{quotation} and \begin{quotation} \cs{fivehyphendemerits}. \end{quotation} \subsection{Hyphen classes} \label{sec:hyphenclasses} \TeX's hyphenation algorithm works by assigning numbers to inter-letter positions in a word and reducing these numbers modulo~2 to obtain a binary alternative (breakpoint or not). A natural extension of this algorithm would be to reduce modulo~$n$ to obtain an $n$-ary alternative, e.\,g.\ the class of the hyphen (where a higher class means a more acceptable breakpoint). This of course implies that the patterns have to be generated with this in mind, i.\,e.\ the number of hyphen classes becomes a parameter of the pattern generation algorithm like \cs{lefthyphenmin} and \cs{righthyphenmin}. This has been implemented in a change to \textsf{patgen} which enables it to deal with up~to~10 hyphen classes and eject inter-letter values of up~to~63. My preliminary tests seem to indicate that it is indeed possible to generate useful patterns for more than one hyphen class, but more extensive experiments are needed. The extended \TeX{} knows the number of hyphen classes through the integer parameter \begin{quotation} \cs{hyphenclasses}. \end{quotation} It is saved and restored like \cs{lefthyphenmin} and \cs{righthyphenmin} when the language is changed in the middle of a paragraph. To make use of the hyphen classes, it is necessary to make \TeX{} charge different penalties for them. To this end, the extended \TeX{} has the integer parameters \begin{quotation} \cs{hyphenpenalties}\meta{hyphen class},\\ \null\qquad\qquad\qquad\qquad$(1\leq\meta{hyphen class}\leq 9)$. \end{quotation} The parameters \cs{hyphen\-penalty} and \cs{exhyphen\-penalty} are now synonyms for \cs{hyphen\-penalties1} and \cs{hyphen\-penalties}\meta{n}, where \meta{n} is the value of the new integer parameter \begin{quotation} \cs{exhyphenclass}. \end{quotation} It determines the class to which the automatically inserted discretionaries after~|-| and discretionaries with empty pre-break text generated by \cs{-} or \cs{discretionary} belong (\cs{exhyphen\-class} may also be~0 to disable breaking after~|-|). Discretionaries of any class can be inserted with the help of the new primitive \begin{quotation} \cs{gendiscretionary}\meta{hyphen class}. \end{quotation} If these extensions are enabled, the \TeX{} primitives \cs{patterns} and \cs{hyphenation} accept slightly more general input: \cs{patterns} accepts two-digit values up~to~63 between letters and \cs{hyphenation} accepts one-digit hyphen classes after hyphens. \subsection{Enabling the extensions} Following the model of \eTeX, the extensions described above are protected by two integer parameters, \begin{quotation} \cs{hyphencountstate} \end{quotation} and \begin{quotation} \cs{hyphenclassesstate}, \end{quotation} which must be set to a positive value to enable them. With both state variables set to zero the extended \TeX{} still passes the trip test (with small differences in memory usage caused by the different size of discretionary nodes). In this mode, the primitives \cs{gendiscretionary} and \cs{hyphenpenalties} are forbidden and the values of the integer parameters \cs{exhyphenclass}, \cs{hyphen\-classes}, \cs{hyphen\-penalties3}, \dots, \cs{hyphen\-penalties9}, \cs{three\-hy\-phen\-demerits}, \dots, \cs{five\-hyphen\-demerits} are ignored. \section{Generating patterns} I have done some experiments to see if it is possible to generate patterns for more than one hyphen class. My test data was a list of approximately 25\,000 German words, many of them compound. I used \TeX's hyphenation to insert hyphens and flagged the inter-word hyphens manually as hyphen class~2. For the last experiment, I broke all compound words in their constituents. \medskip \hspace{-4cm}\hfill \begin{tabular}{cccccc} \toprule break points&\multicolumn{2}{c}{patterns}&good&bad&missed\\ &kB&\#&\%&\%&\%\\ \midrule all&65582&9271&99.02&0.10&0.98\\ all in one class&32892&4970&99.98&0.01&0.02\\ only inter-word&37407&5386&99.63&0.01&0.37\\ only intra-word&14653&2226&99.70&0.04&0.30\\ \bottomrule \end{tabular} \medskip Note that in the first experiment, hyphens of class~1 which are inserted where a hyphen of class~2 was wanted do count as bad. The percentage of \emph{really} bad (i.\,e.\ too permissive) hyphens is much smaller. It's not too surprising that the patterns for two hyphen classes are bigger than the patterns for one hyphen class, since they contain more information. The results of the third and fourth experiment might encourage a different approach to the problem of weighting breaks: Replace the current hyphenation algorithm by two passes of the same algorithm, where the first pass would use special patterns to find word boundaries and the second would find breakpoints in the broken words. This would fit nicely with \TeX's three line-breaking passes. The first pass would be done as always before any hyphenation. The second try would be done after the insertion of inter-word breaks. Only the last pass would make use of intra-word breaks. But I haven't tried this yet. \section{Implementation} The changes to \TeX{} the program and \textsf{patgen} sketched above are realized as a series of change files. \begin{itemize} \item |classes.ch| extends \TeX's hyphenation routines to deal with hyphens of up to~9 different classes. It implements the new control sequences described in section~\ref{sec:hyphenclasses}. \item |count.ch| extends \TeX's line breaking routines to deal with sequences of breakpoints containing more than two consecutive hyphens. It implements the new control sequences described in section~\ref{sec:linebreaking}. \item |patgen-classes.ch| extends \textsf{patgen}s pattern generation algorithm to deal with up~to~10 different hyphen classes. The new algorithm has one new integer parameter, the number of hyphen classes (between 2 and~10). This parameter can be specified in columns 8 and~9 of the first line of the translate file. \textsf{patgen} will now produce values up~to~63. \end{itemize} \section{Installation} The change files are written for \TeX~3.1459 and \textsf{patgen}~2.3. But it should need only cosmetic changes to make them work with other versions of \TeX3 or \textsf{patgen}2. First, you have to apply the change file |pre.ch|. The |count.ch| and |classes.ch| change files should be independent of each other. I have only tried these files with |web2c|, and for that you need to surround the |web2c| change file with |pre-web2c.ch| and |post-web2c.ch|. All this boils down to the command line \begin{verbatim} mv tex.ch tex.ch.orig tie -c tex.ch tex.web pre.ch classes.ch \ count.ch pre-web2c.ch tex.ch.orig \ post-web2c.ch \end{verbatim} \makesignature \bibliographystyle{plain} \bibliography{etex} \end{document}