\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}



