Hyphen - hyphenation library to use converted TeX hyphenation patterns

(C) 1998 Raph Levien
(C) 2001 ALTLinux, Moscow
(C) 2006, 2007, 2008 László Németh

This was part of libHnj library by Raph Levien.

Peter Novodvorsky from ALTLinux cut hyphenation part from libHnj
to use it in OpenOffice.org.

Compound word and non-standard hyphenation support by László Németh.

License is the original LibHnj license:
LibHnj is dual licensed under LGPL and MPL (see also README.libhnj).

Because LGPL allows GPL relicensing, COPYING contains now
LGPL/GPL/MPL tri-license for explicit Mozilla source compatibility.

Original Libhnj source with OOo's patches are managed by Rene Engelhard
and Chris Halls at Debian:

http://packages.debian.org/stable/libdevel/libhnj-dev
and http://packages.debian.org/unstable/source/libhnj


OTHER FILES

This distribution is the source of the en_US hyphenation patterns
"hyph_en_US.dic", too. See README_hyph_en_US.txt.

Source files of hyph_en_US.dic in the distribution:

hyphen.tex (en_US hyphenation patterns from plain TeX)

  Source: http://tug.ctan.org/text-archive/macros/plain/base/hyphen.tex

tbhyphext.tex: hyphenation exception log from TugBoat archive

  Source of the hyphenation exception list:
  http://www.ctan.org/tex-archive/info/digests/tugboat/tb0hyf.tex

  Generated with the hyphenex script
  (http://www.ctan.org/tex-archive/info/digests/tugboat/hyphenex.sh)

  sh hyphenex.sh <tb0hyf.tex >tbhyphext.tex


INSTALLATION

./configure
make
make install

UNIT TESTS (WITH VALGRIND DEBUGGER)

make check
VALGRIND=memcheck make check

USAGE

./example hyph_en_US.dic mywords.txt

or (under Linux)

echo example | ./example hyph_en_US.dic /dev/stdin

NOTE: In the case of Unicode encoded input, convert your words
to lowercase before hyphenation (under UTF-8 console environment):

cat mywords.txt | awk '{print tolower($0)}' >mywordslow.txt

DEVELOPMENT

See README.hyphen for hyphenation algorithm, README.nonstandard
and doc/tb87nemeth.pdf for non-standard hyphenation,
README.compound for compound word hyphenation, and tests/*.

Description of the dictionary format:

First line contains the character encoding (ISO8859-x, UTF-8).

Possible options in the following lines:

LEFTHYPHENMIN num          minimal hyphenation distance from the left word end
RIGHTHYPHENMIN num         minimal hyphation distance from the right word end
COMPOUNDLEFTHYPHENMIN num  min. hyph. dist. from the left compound word boundary
COMPOUNDRIGHTHYPHENMIN num min. hyph. dist. from the right comp. word boundary

hyphenation patterns       see README.* files

NEXTWORD                   separate the two compound sets (see README.compound)

Default values:
Without explicite declarations, hyphenmin fields of dict struct
are zeroes, but in this case the lefthyphenmin and righthyphenmin
will be the default 2 under the hyphenation (for backward compatibility).

Comments

Use percent sign at the beginning of the lines to add comments to your
hpyhenation patterns (after the character encoding in the first line):

% comment

*****************************************************************************
* Warning! Correct working of Libhnj *needs* prepared hyphenation patterns. *

For example, generating hyph_en_US.dic from "hyphen.us" TeX patterns:

perl substrings.pl hyphen.us hyph_en_US.dic ISO8859-1

or with default LEFTHYPHENMIN and RIGHTHYPHENMIN values:

perl substrings.pl hyphen.us hyph_en_US.dic ISO8859-1 2 3
perl substrings.pl hyphen.gb hyph_en_GB.dic ISO8859-1 3 3
****************************************************************************

OTHERS

Java hyphenation: Peter B. West (Folio project) implements a hyphenator with
non standard hyphenation facilities based on extended Libhnj. The HyFo module
is released in binary form as jar files and in source form as zip files.
See http://sourceforge.net/project/showfiles.php?group_id=119136

László Németh
<nemeth (at) openoffice (dot) org>

Compound word hyphenation

Hyphen library supports better compound word hyphenation and special
rules of compound word hyphenation of German languages and other
languages with arbitrary number of compound words. The new options,
COMPOUNDLEFTHYPHENMIN and COMPOUNDRIGHTHYPHENMIN help to set the right
style for the hyphenation of compound words.

Algorithm

The algorithm is an extension of the original pattern based hyphenation
algorithm. It uses two hyphenation pattern sets, defined in the same
pattern file and separated by the NEXTLEVEL keyword. First pattern
set is for hyphenation only at compound word boundaries, the second one
is for hyphenation within words or word parts.

Recursive compound level hyphenation

The algorithm is recursive: every word parts of a successful
first (compound) level hyphenation will be rehyphenated
by the same (first) pattern set.

Finally, when first level hyphenation is not possible, Hyphen uses
the second level hyphenation for the word or the word parts.

Word endings and word parts

Patterns for word endings (patterns with ellipses) match the
word parts, too.

Options

COMPOUNDLEFTHYPHENMIN: min. hyph. dist. from the left compound word boundary
COMPOUNDRIGHTHYPHENMIN: min. hyph. dist. from the right comp. word boundary
NEXTLEVEL: sign second level hyphenation patterns

Default hyphenmin values

Default values of COMPOUNDLEFTHYPHENMIN and COMPOUNDRIGHTHYPHENMIN are 0,
and 0 under the hyphenation, too. ("0" values of
LEFTHYPHENMIN and RIGHTHYPHENMIN mean the default "2" under the hyphenation.)

Examples

See tests/compound* test files.

Preparation of hyphenation patterns

It hasn't been special pattern generator tool for compound hyphenation
patterns, yet. It is possible to use PATGEN to generate both of
pattern sets, concatenate it manually and set the requested HYPHENMIN values.
(But don't forget the preprocessing steps by substrings.pl before
concatenation.) One of the disadvantage of this method, that PATGEN
doesn't know recursive compound hyphenation of Hyphen.

László Németh
<nemeth (at) openoffice.org>

Brief explanation of the hyphenation algorithm herein.[1]

Raph Levien <raph@acm.org>
4 Aug 1998

   The hyphenation algorithm is basically the same as Knuth's TeX
algorithm. However, the implementation is quite a bit faster.

   The hyphenation files from TeX can almost be used directly. There
is a preprocessing step, however. If you don't do the preprocessing
step, you'll get bad hyphenations (i.e. a silent failure).

   Start with a file such as hyphen.us. This is the TeX ushyph1.tex
file, with the exception dictionary encoded using the same rules as
the main portion of the file. Any line beginning with % is a comment.
Each other line should contain exactly one rule.

   Then, do the preprocessing - "perl substrings.pl hyphen.us". The
resulting file is hyphen.mashed. It's in Perl, and it's fairly slow
(it uses brute force algorithms; about 17 seconds on a P100), but it
could probably be redone in C with clever algorithms. This would be
valuable, for example, if it was handle user-supplied exception
dictionaries by integrating them into the rule table.[2]

   Once the rules are preprocessed, loading them is quite quick -
about 200ms on a P100. It then hyphenates at about 40,000 words per
second on a P100. I haven't benchmarked it against other
implementations (both TeX and groff contain essentially the same
algorithm), but expect that it runs quite a bit faster than any of
them.

Knuth's algorithm

   This section contains a brief explanation of Knuth's algorithm, in
case you missed it from the TeX books. We'll use the semi-word
"example" as our running example.

   Since the beginning and end of a word are special, the algorithm is
actually run over the prepared word (prep_word in the source)
".example.". Knuths algorithm basically just does pattern matches from
the rule set, then applies the matches. The patterns in this case that
match are "xa", "xam", "mp", and "pl". These are actually stored as
"x1a", "xam3", "4m1p", and "1p2l2". Whenever numbers appear between
the letters, they are added in. If two (or more) patterns have numbers
in the same place, the highest number wins. Here's the example:

 . e x a m p l e .
     x1a
     x a m3
        4m1p
          1p2l2
 -----------------
 . e x1a4m3p2l2e .

   Finally, hyphens are placed wherever odd numbers appear. They are,
however, suppressed after the first letter and before the last letter
of the word (TeX actually suppresses them before the next-to-last, as
well). So, it's "ex-am-ple", which is correct.

   Knuth uses a trie to implement this. I.e. he stores each rule in a
trie structure. For each position in the word, he searches the trie,
searching for a match. Most patterns are short, so efficiency should
be quite good.

Theory of the algorithm

   The algorithm works as a slightly modified finite state machine.
There are two kinds of transitions: those that consume one letter of
input (which work just like your regular finite state machine), and
"fallback" transitions, which don't consume any input. If no
transition matching the next letter is found, the fallback is used.
One way of looking at this is a form of compression of the transition
tables - i.e. it behaves the same as a completely vanilla state
machine in which the actual transition table of a node is made up of
the union of transition tables of the node itself, plus its fallbacks.

   Each state is represented by a string. Thus, if the current state
is "am" and the next letter is "p", then the next state is "amp".
Fallback transitions go to states which chop off one or (sometimes)
more letters from the beginning. For example, if none of the
transitions from "amp" match the next letter, then it will fall back
to "mp". Similarly, if none of the transitions from "mp" match the
next letter, it will fall back to "m".

   Each state is also associated with a (possibly null) "match"
string. This represents the union of all patterns which are
right-justified substrings of the match string. I.e. the pattern "mp"
is a right-justified substring of the state "amp", so it's numbers get
added in. The actual calculation of this union is done by the
Perl preprocessing script, but could probably be done in C just about
as easily.

   Because each state transition either consumes one input character
or shortens the state string by one character, the total number of
state transitions is linear in the length of the word.

[1] Documentations:

Franklin M. Liang: Word Hy-phen-a-tion by Com-put-er.
Stanford University, 1983. http://www.tug.org/docs/liang.

László Németh: Automatic non-standard hyphenation in OpenOffice.org,
TUGboat (27), 2006. No. 2., http://hunspell.sourceforge.net/tb87nemeth.pdf

[2] There is the C version of pattern converter "substrings.c"
in the distribution written by Nanning Buitenhuis. Unfortunatelly,
this version hasn't handled the non standard extension of the
algorithm, yet.

Non-standard hyphenation
------------------------

Some languages use non-standard hyphenation; `discretionary'
character changes at hyphenation points. For example,
Catalan: paral·lel -> paral-lel,
Dutch: omaatje -> oma-tje,
German (before the new orthography): Schiffahrt -> Schiff-fahrt,
Hungarian: asszonnyal -> asz-szony-nyal (multiple occurance!)
Swedish: tillata -> till-lata.

Using this extended library, you can define
non-standard hyphenation patterns. For example:

l·1l/l=l
a1atje./a=t,1,3
.schif1fahrt/ff=f,5,2
.as3szon/sz=sz,2,3
n1nyal./ny=ny,1,3
.til1lata./ll=l,3,2

or with narrow boundaries:

l·1l/l=,1,2
a1atje./a=,1,1
.schif1fahrt/ff=,5,1
.as3szon/sz=,2,1
n1nyal./ny=,1,1
.til1lata./ll=,3,1

Note: Libhnj uses modified patterns by preparing substrings.pl.
Unfortunatelly, now the conversion step can generate bad non-standard
patterns (non-standard -> standard pattern conversion), so using
narrow boundaries may be better for recent Libhnj. For example,
substrings.pl generates a few bad patterns for Hungarian hyphenation
patterns resulting bad non-standard hyphenation in a few cases. Using narrow
boundaries solves this problem. Java HyFo module can check this problem.

Syntax of the non-standard hyphenation patterns
------------------------------------------------

pat1tern/change[,start,cut]

If this pattern matches the word, and this pattern win (see README.hyphen)
in the change region of the pattern, then pattern[start, start + cut - 1]
substring will be replaced with the "change".

For example, a German ff -> ff-f hyphenation:

f1f/ff=f

or with expansion

f1f/ff=f,1,2

will change every "ff" with "ff=f" at hyphenation.

A more real example:

% simple ff -> f-f hyphenation
f1f
% Schiffahrt -> Schiff-fahrt hyphenation
%
schif3fahrt/ff=f,5,2

Specification

- Pattern: matching patterns of the original Liang's algorithm
  - patterns must contain only one hyphenation point at change region
    signed with an one-digit odd number (1, 3, 5, 7 or 9).
    These point may be at subregion boundaries: schif3fahrt/ff=,5,1
  - only the greater value guarantees the win (don't mix non-standard and
    non-standard patterns with the same value, for example
    instead of f3f and schif3fahrt/ff=f,5,2 use f3f and schif5fahrt/ff=f,5,2)

- Change: new characters.
  Arbitrary character sequence. Equal sign (=) signs hyphenation points
  for OpenOffice.org (like in the example). (In a possible German LaTeX
  preprocessor, ff could be replaced with "ff, for a Hungarian one, ssz
  with `ssz, according to the German and Hungarian Babel settings.)

- Start: starting position of the change region.
  - begins with 1 (not 0): schif3fahrt/ff=f,5,2
  - start dot doesn't matter: .schif3fahrt/ff=f,5,2
  - numbers don't matter: .s2c2h2i2f3f2ahrt/ff=f,5,2
  - In UTF-8 encoding, use Unicode character positions: össze/sz=sz,2,3
    ("össze" looks "össze" in an ISO 8859-1 8-bit editor).

- Cut: length of the removed character sequence in the original word.
  - In UTF-8 encoding, use Unicode character length: paral·1lel/l=l,5,3
    ("paral·lel" looks "paral·1lel" in an ISO 8859-1 8-bit editor).

Dictionary developing
---------------------

There hasn't been extended PatGen pattern generator for non-standard
hyphenation patterns, yet.

Fortunatelly, non-standard hyphenation points are forbidden in the PatGen
generated hyphenation patterns, so with a little patch can be develop
non-standard hyphenation patterns also in this case.

Warning: If you use UTF-8 Unicode encoding in your patterns, call
substrings.pl with UTF-8 parameter to calculate right
character positions for non-standard hyphenation:

./substrings.pl input output UTF-8

Programming
-----------

Use hyphenate2() or hyphenate3() to handle non-standard hyphenation.
See hyphen.h for the documentation of the hyphenate*() functions.
See example.c for processing the output of the hyphenate*() functions.

Warning: change characters are lower cased in the source, so you may need
case conversion of the change characters based on input word case detection.
For example, see OpenOffice.org source
(lingucomponent/source/hyphenator/altlinuxhyph/hyphen/hyphenimp.cxx).

László Németh
<nemeth (at) openoffice.org>