[Xmlgraphics-fop Wiki] Update of "AutomaticHyphenation" by JoergPietschmann

[Apache Wiki <wi...@apache.org>]

Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Xmlgraphics-fop Wiki" for change notification.

The following page has been changed by JoergPietschmann:
http://wiki.apache.org/xmlgraphics-fop/AutomaticHyphenation

New page:
= Automatic Hyphenation =

FOP uses Frank Liang's famous pattern based algorithm for automated hyphenation of words. This page will describe
* The core algorithm for hyphenation, in an abstract way.
* Data structures used in an efficient implementation
* Refinements and embedding of the algorithm
* How to generate the patterns used in the algorithm
* Related problems
* Various notes and other work in the area of automated hyphenation and related problems.

== The Core Algorithm ==

The algorithm work roughly as follows:
{{{
setup the hyphenation position vector (fill with zeros)
for each substring of the word
  lookup the substring in the pattern store
  if you got a result
    // merge the result into the hyphenation position vector
    for each element of the result
      if the element is greater than the corresponding element in the hyphenation position vector
        replace the element in the hyphenation position vector by the element form the lookup result
      end if
    end for
  end if
end for
}}}
After this, odd integers in the hyphenation position vector mark valid hyphenation points, while even integers (including zero) denote potitions unavailable for hyphenation.

=== Data Details ===

The hyphenation position vector is an array of integers with one element more than the number of characters in the word which is hyphenated. Each element in the hyphenation position vector represents a potential hyphenation position. The first element in the hyphenation position vector represents the position ''before'' the first character in the word, the secont element represents the position between the first and the second character of the word and so on, and the last element represents the position after the last character of the word. The first and last element in the hyphenation position vector are already there for the sake of an efficient implementation.

The pattern store maps strings (the ''patterns'') to vectors of integers, which have one element more then the number of characters in the associated pattern. The integer values in these vectors are called ''weights''. Similarly to the pattern hyphenation vector, the first element represents the weight for the position before the first character of the pattern etc.

A sample pattern store (taken from the english LaTeX hyphenation patterns):
{{{
  +---+---+    +---+---+---+
  | a | m | -> | 2 | 2 | 0 |
  +---+---+    +---+---+---+

  +---+---+---+---+    +---+---+---+---+---+
  | a | r | a | m | -> | 0 | 0 | 0 | 3 | 0 |
  +---+---+---+---+    +---+---+---+---+---+
}}}

=== Merging The Pattern Weights ===

Let's say we want to hyphenate the word "parameter". First setup the hyphenation position vector for the word:
{{{
      p   a   r   a   m   e   t   e   r
  +---+---+---+---+---+---+---+---+---+---+
  | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
  +---+---+---+---+---+---+---+---+---+---+
}}}

Now we scan the substrings of the word starting with the first character: p, pa, par, para, param, parame, ... no hits, continue with the substrings starting at the second character: a, ar, ara, aram ... hit! Merge it into the hyphenation position vector:
{{{
      p   a   r   a   m   e   t   e   r
  +---+---+---+---+---+---+---+---+---+---+
  | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
  +---+---+---+---+---+---+---+---+---+---+
          a   r   a   m
      +---+---+---+---+---+
      | 0 | 0 | 0 | 3 | 0 |
      +---+---+---+---+---+
                    |
                    v
  +---+---+---+---+---+---+---+---+---+---+
  | 0 | 0 | 0 | 0 | 3 | 0 | 0 | 0 | 0 | 0 |
  +---+---+---+---+---+---+---+---+---+---+
}}}
Scanning further, we find a second hit:
{{{
      p   a   r   a   m   e   t   e   r
  +---+---+---+---+---+---+---+---+---+---+
  | 0 | 0 | 0 | 0 | 3 | 0 | 0 | 0 | 0 | 0 |
  +---+---+---+---+---+---+---+---+---+---+
                  a   m
              +---+---+---+
              | 2 | 2 | 0 |
              +---+---+---+
                |   x
                v   x
  +---+---+---+---+---+---+---+---+---+---+
  | 0 | 0 | 0 | 2 | 3 | 0 | 0 | 0 | 0 | 0 |
  +---+---+---+---+---+---+---+---+---+---+
}}}
The result is a possible hyphenation as para-meter, indicated by the weight 3 at the 5th position, while all the zeroes and the weight 2 at position 4 inhibit hyphenation.

The example also demonstrates why the hyphenation position vector extends left and right beyond the boundaries of the word: patters may have weights associated with the position before or after the end of the pattern, and extending the hyphenation position vector saves explicit clipping if a pattern matches at the beginning or the end of the word. The positions are clipped after the weights for all matching patterns have been merged, which is much more efficient.

=== Anchoring Patterns ===

Like for [http://en.wikipedia.org/wiki/Regular_expression regular expressions], it may be useful to anchor hyphenation patters to the beginning or the end of a word. The common, established way is to use sentinel characters, conventionally a dot. The core algorithm isn't changed at all, there are just the sentinel characters added to the word.

Here a somewhat fictious example, which uses a high weight to force a hyphenation of a "pa-ra" prefix:
{{{
      .   p   a   r   a   m   e   t   e   r   .
  +---+---+---+---+---+---+---+---+---+---+---+---+
  | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
  +---+---+---+---+---+---+---+---+---+---+---+---+
      .   p   a   r   a
  +---+---+---+---+---+---+
  | 0 | 0 | 0 | 7 | 0 | 0 |
  +---+---+---+---+---+---+
                |
                v
  +---+---+---+---+---+---+---+---+---+---+---+---+
  | 0 | 0 | 0 | 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
  +---+---+---+---+---+---+---+---+---+---+---+---+
}}}
Of course, this requires that the sentinel character never occurs in a word.

=== External representation Of Patterns ===

Liang and Knuth also invented a convenient, compact representation to write down patters. It basically inserts the non-zero weights as single digits between the characters of the patterns, and uses the dot for anchoring a pattern to the begin or the end of the word. The zero weights are implicit.
The patterns used so far can be written as
{{{
ara3m
2a2m
.pa7ra
}}}
A (fictious) pattern anchored at the end of the word would be
{{{
ete8r.
}}}
The representation has never been standardized, and obvious extensions (multi-digit weights, non-ASCII characters) are likely to create some confusion. Here an attempt at formalization in form of an [http://en.wikipedia.org/wiki/Extended_Backus-Naur_form EBNF] grammar:
{{{
pattern ::= [start-of-word-anchor character] { [digit]? character }+ [digit] [character end-of-word-anchor]
digit ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
start-of-word-anchor ::= "."
end-of-word-anchor ::= "."
character ::= "any Unicode character except a dot"
}}}
Note that this grammar allows a pattern like "a44b" which should probably be interpreted as a pattern string "a4b" with a weight 4 for the position between the a and the 4. 

(FIXME: More to come)

Keywords: overlapping patterns (?)

== Efficient Pattern Storage Implementation ==

Keywords: suffix tree, trie, ternary tree, PATRICIA tree, etc.; link DADS and freshmeat projects

== Refinements And Embedding Of the Algorithm ==

Keywords: parse words out of the text, character normalization (link Unicode TR, icu4j etc.), alphabet mapping/transformation

== Hot To Generate Patterns ==

Keywords: patgen description, patgen parameters, word weights, hyphenation position weights

== Related Problems ==

Keywords: ligatures, character shaping (e.g. arabic), thai word extraction

== Further work ==

=== Known Problems Automated Hyphenation ===

Keywords: word compositions, agglutinating languages, unmarked foreign words, ambiguities, context

=== Other Work and Projects ===

Keywords: Petr Sojka, SiSiSi, track down more people and projects

---------------------------------------------------------------------
To unsubscribe, e-mail: fop-commits-unsubscribe@xmlgraphics.apache.org
For additional commands, e-mail: fop-commits-help@xmlgraphics.apache.org