Package org.apache.fop.hyphenation
Class HyphenationTree
java.lang.Object
org.apache.fop.hyphenation.TernaryTree
org.apache.fop.hyphenation.HyphenationTree
- All Implemented Interfaces:
Serializable
,Cloneable
,PatternConsumer
This tree structure stores the hyphenation patterns in an efficient
way for fast lookup. It provides the provides the method to
hyphenate a word.
This work was originally authored by Carlos Villegas cav@uniscope.co.jp
- See Also:
-
Nested Class Summary
Nested classes/interfaces inherited from class org.apache.fop.hyphenation.TernaryTree
TernaryTree.Iterator
-
Field Summary
Modifier and TypeFieldDescriptionprotected TernaryTree
This map stores the character classesprotected HashMap
This map stores hyphenation exceptionsprotected ByteVector
value space: stores the interletter valuesFields inherited from class org.apache.fop.hyphenation.TernaryTree
BLOCK_SIZE, eq, freenode, hi, kv, length, lo, root, sc
-
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionvoid
Add a character class to the tree.void
addException
(String word, ArrayList hyphenatedword) Add an exception to the tree.void
addPattern
(String pattern, String ivalue) Add a pattern to the tree.findPattern
(String pat) Find pattern.protected byte[]
getValues
(int k) Get values.protected int
hstrcmp
(char[] s, int si, char[] t, int ti) String compare, returns 0 if equal or t is a substring of s.hyphenate
(char[] w, int offset, int len, int remainCharCount, int pushCharCount) Hyphenate word and return an array of hyphenation points.Hyphenate word and return a Hyphenation object.void
loadPatterns
(String filename) Read hyphenation patterns from an XML file.void
loadPatterns
(InputSource source) Read hyphenation patterns from an XML file.static void
Main entry point for this hyphenation utility application.protected int
packValues
(String values) Packs the values by storing them in 4 bits, two values into a byte Values range is from 0 to 9.void
Print statistics.protected void
searchPatterns
(char[] word, int index, byte[] il) Search for all possible partial matches of word starting at index an update interletter values.protected String
unpackValues
(int k) Unpack values.
-
Field Details
-
vspace
value space: stores the interletter values -
stoplist
This map stores hyphenation exceptions -
classmap
This map stores the character classes
-
-
Constructor Details
-
HyphenationTree
public HyphenationTree()Default constructor.
-
-
Method Details
-
packValues
Packs the values by storing them in 4 bits, two values into a byte Values range is from 0 to 9. We use zero as terminator, so we'll add 1 to the value.- Parameters:
values
- a string of digits from '0' to '9' representing the interletter values.- Returns:
- the index into the vspace array where the packed values are stored.
-
unpackValues
Unpack values.- Parameters:
k
- an integer- Returns:
- a string
-
loadPatterns
Read hyphenation patterns from an XML file.- Parameters:
filename
- the filename- Throws:
HyphenationException
- In case the parsing fails
-
loadPatterns
Read hyphenation patterns from an XML file.- Parameters:
source
- the InputSource for the file- Throws:
HyphenationException
- In case the parsing fails
-
findPattern
Find pattern.- Parameters:
pat
- a pattern- Returns:
- a string
-
hstrcmp
protected int hstrcmp(char[] s, int si, char[] t, int ti) String compare, returns 0 if equal or t is a substring of s.- Parameters:
s
- first character arraysi
- starting index into first arrayt
- second character arrayti
- starting index into second array- Returns:
- an integer
-
getValues
protected byte[] getValues(int k) Get values.- Parameters:
k
- an integer- Returns:
- a byte array
-
searchPatterns
protected void searchPatterns(char[] word, int index, byte[] il) Search for all possible partial matches of word starting at index an update interletter values. In other words, it does something like:
for(i=0; i<patterns.length; i++) { if ( word.substring(index).startsWidth(patterns[i]) ) update_interletter_values(patterns[i]); }
But it is done in an efficient way since the patterns are stored in a ternary tree. In fact, this is the whole purpose of having the tree: doing this search without having to test every single pattern. The number of patterns for languages such as English range from 4000 to 10000. Thus, doing thousands of string comparisons for each word to hyphenate would be really slow without the tree. The tradeoff is memory, but using a ternary tree instead of a trie, almost halves the the memory used by Lout or TeX. It's also faster than using a hash table
- Parameters:
word
- null terminated word to matchindex
- start index from wordil
- interletter values array to update
-
hyphenate
Hyphenate word and return a Hyphenation object.- Parameters:
word
- the word to be hyphenatedremainCharCount
- Minimum number of characters allowed before the hyphenation point.pushCharCount
- Minimum number of characters allowed after the hyphenation point.- Returns:
- a
Hyphenation
object representing the hyphenated word or null if word is not hyphenated.
-
hyphenate
Hyphenate word and return an array of hyphenation points.- Parameters:
w
- char array that contains the wordoffset
- Offset to first character in wordlen
- Length of wordremainCharCount
- Minimum number of characters allowed before the hyphenation point.pushCharCount
- Minimum number of characters allowed after the hyphenation point.- Returns:
- a
Hyphenation
object representing the hyphenated word or null if word is not hyphenated.
-
addClass
Add a character class to the tree. It is used byPatternParser
as callback to add character classes. Character classes define the valid word characters for hyphenation. If a word contains a character not defined in any of the classes, it is not hyphenated. It also defines a way to normalize the characters in order to compare them with the stored patterns. Usually pattern files use only lower case characters, in this case a class for letter 'a', for example, should be defined as "aA", the first character being the normalization char.- Specified by:
addClass
in interfacePatternConsumer
- Parameters:
chargroup
- a character class (group)
-
addException
Add an exception to the tree. It is used byPatternParser
class as callback to store the hyphenation exceptions.- Specified by:
addException
in interfacePatternConsumer
- Parameters:
word
- normalized wordhyphenatedword
- a vector of alternating strings andhyphen
objects.
-
addPattern
Add a pattern to the tree. Mainly, to be used byPatternParser
class as callback to add a pattern to the tree.- Specified by:
addPattern
in interfacePatternConsumer
- Parameters:
pattern
- the hyphenation patternivalue
- interletter weight values indicating the desirability and priority of hyphenating at a given point within the pattern. It should contain only digit characters. (i.e. '0' to '9').
-
printStats
public void printStats()Print statistics.- Overrides:
printStats
in classTernaryTree
-
main
Main entry point for this hyphenation utility application.- Parameters:
argv
- array of command linee arguments- Throws:
Exception
- in case an exception is raised but not caught
-