2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
9 * http://www.apache.org/licenses/LICENSE-2.0
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
18 package org.apache.lucene.analysis.compound.hyphenation;
21 import java.io.Serializable;
22 import java.net.MalformedURLException;
23 import java.util.ArrayList;
24 import java.util.HashMap;
26 import org.xml.sax.InputSource;
29 * This tree structure stores the hyphenation patterns in an efficient way for
30 * fast lookup. It provides the provides the method to hyphenate a word.
32 * This class has been taken from the Apache FOP project (http://xmlgraphics.apache.org/fop/). They have been slightly modified.
34 public class HyphenationTree extends TernaryTree implements PatternConsumer,
37 private static final long serialVersionUID = -7842107987915665573L;
40 * value space: stores the interletter values
42 protected ByteVector vspace;
45 * This map stores hyphenation exceptions
47 protected HashMap<String,ArrayList<Object>> stoplist;
50 * This map stores the character classes
52 protected TernaryTree classmap;
55 * Temporary map to store interletter values on pattern loading.
57 private transient TernaryTree ivalues;
59 public HyphenationTree() {
60 stoplist = new HashMap<String,ArrayList<Object>>(23); // usually a small table
61 classmap = new TernaryTree();
62 vspace = new ByteVector();
63 vspace.alloc(1); // this reserves index 0, which we don't use
67 * Packs the values by storing them in 4 bits, two values into a byte Values
68 * range is from 0 to 9. We use zero as terminator, so we'll add 1 to the
71 * @param values a string of digits from '0' to '9' representing the
73 * @return the index into the vspace array where the packed values are stored.
75 protected int packValues(String values) {
76 int i, n = values.length();
77 int m = (n & 1) == 1 ? (n >> 1) + 2 : (n >> 1) + 1;
78 int offset = vspace.alloc(m);
79 byte[] va = vspace.getArray();
80 for (i = 0; i < n; i++) {
82 byte v = (byte) ((values.charAt(i) - '0' + 1) & 0x0f);
84 va[j + offset] = (byte) (va[j + offset] | v);
86 va[j + offset] = (byte) (v << 4); // big endian
89 va[m - 1 + offset] = 0; // terminator
93 protected String unpackValues(int k) {
94 StringBuilder buf = new StringBuilder();
95 byte v = vspace.get(k++);
97 char c = (char) ((v >>> 4) - 1 + '0');
99 c = (char) (v & 0x0f);
103 c = (char) (c - 1 + '0');
107 return buf.toString();
111 * Read hyphenation patterns from an XML file.
113 * @param f the filename
114 * @throws HyphenationException In case the parsing fails
116 public void loadPatterns(File f) throws HyphenationException {
118 InputSource src = new InputSource(f.toURL().toExternalForm());
120 } catch (MalformedURLException e) {
121 throw new HyphenationException("Error converting the File '" + f
122 + "' to a URL: " + e.getMessage());
127 * Read hyphenation patterns from an XML file.
129 * @param source the InputSource for the file
130 * @throws HyphenationException In case the parsing fails
132 public void loadPatterns(InputSource source) throws HyphenationException {
133 PatternParser pp = new PatternParser(this);
134 ivalues = new TernaryTree();
138 // patterns/values should be now in the tree
139 // let's optimize a bit
142 classmap.trimToSize();
144 // get rid of the auxiliary map
148 public String findPattern(String pat) {
149 int k = super.find(pat);
151 return unpackValues(k);
157 * String compare, returns 0 if equal or t is a substring of s
159 protected int hstrcmp(char[] s, int si, char[] t, int ti) {
160 for (; s[si] == t[ti]; si++, ti++) {
168 return s[si] - t[ti];
171 protected byte[] getValues(int k) {
172 StringBuilder buf = new StringBuilder();
173 byte v = vspace.get(k++);
175 char c = (char) ((v >>> 4) - 1);
177 c = (char) (v & 0x0f);
185 byte[] res = new byte[buf.length()];
186 for (int i = 0; i < res.length; i++) {
187 res[i] = (byte) buf.charAt(i);
194 * Search for all possible partial matches of word starting at index an update
195 * interletter values. In other words, it does something like:
198 * for(i=0; i<patterns.length; i++) {
199 * if ( word.substring(index).startsWidth(patterns[i]) )
200 * update_interletter_values(patterns[i]);
204 * But it is done in an efficient way since the patterns are stored in a
205 * ternary tree. In fact, this is the whole purpose of having the tree: doing
206 * this search without having to test every single pattern. The number of
207 * patterns for languages such as English range from 4000 to 10000. Thus,
208 * doing thousands of string comparisons for each word to hyphenate would be
209 * really slow without the tree. The tradeoff is memory, but using a ternary
210 * tree instead of a trie, almost halves the the memory used by Lout or TeX.
211 * It's also faster than using a hash table
214 * @param word null terminated word to match
215 * @param index start index from word
216 * @param il interletter values array to update
218 protected void searchPatterns(char[] word, int index, byte[] il) {
225 while (p > 0 && p < sc.length) {
226 if (sc[p] == 0xFFFF) {
227 if (hstrcmp(word, i, kv.getArray(), lo[p]) == 0) {
228 values = getValues(eq[p]); // data pointer is in eq[]
230 for (int k = 0; k < values.length; k++) {
231 if (j < il.length && values[k] > il[j]) {
248 // look for a pattern ending at this position by searching for
249 // the null char ( splitchar == 0 )
250 while (q > 0 && q < sc.length) {
251 if (sc[q] == 0xFFFF) { // stop at compressed branch
255 values = getValues(eq[q]);
257 for (int k = 0; k < values.length; k++) {
258 if (j < il.length && values[k] > il[j]) {
268 * actually the code should be: q = sc[q] < 0 ? hi[q] : lo[q]; but
269 * java chars are unsigned
274 p = d < 0 ? lo[p] : hi[p];
280 * Hyphenate word and return a Hyphenation object.
282 * @param word the word to be hyphenated
283 * @param remainCharCount Minimum number of characters allowed before the
285 * @param pushCharCount Minimum number of characters allowed after the
287 * @return a {@link Hyphenation Hyphenation} object representing the
288 * hyphenated word or null if word is not hyphenated.
290 public Hyphenation hyphenate(String word, int remainCharCount,
292 char[] w = word.toCharArray();
293 return hyphenate(w, 0, w.length, remainCharCount, pushCharCount);
297 * w = "****nnllllllnnn*****", where n is a non-letter, l is a letter, all n
298 * may be absent, the first n is at offset, the first l is at offset +
299 * iIgnoreAtBeginning; word = ".llllll.'\0'***", where all l in w are copied
300 * into word. In the first part of the routine len = w.length, in the second
301 * part of the routine len = word.length. Three indices are used: index(w),
302 * the index in w, index(word), the index in word, letterindex(word), the
303 * index in the letter part of word. The following relations exist: index(w) =
304 * offset + i - 1 index(word) = i - iIgnoreAtBeginning letterindex(word) =
305 * index(word) - 1 (see first loop). It follows that: index(w) - index(word) =
306 * offset - 1 + iIgnoreAtBeginning index(w) = letterindex(word) + offset +
311 * Hyphenate word and return an array of hyphenation points.
313 * @param w char array that contains the word
314 * @param offset Offset to first character in word
315 * @param len Length of word
316 * @param remainCharCount Minimum number of characters allowed before the
318 * @param pushCharCount Minimum number of characters allowed after the
320 * @return a {@link Hyphenation Hyphenation} object representing the
321 * hyphenated word or null if word is not hyphenated.
323 public Hyphenation hyphenate(char[] w, int offset, int len,
324 int remainCharCount, int pushCharCount) {
326 char[] word = new char[len + 3];
329 char[] c = new char[2];
330 int iIgnoreAtBeginning = 0;
332 boolean bEndOfLetters = false;
333 for (i = 1; i <= len; i++) {
334 c[0] = w[offset + i - 1];
335 int nc = classmap.find(c, 0);
336 if (nc < 0) { // found a non-letter character ...
337 if (i == (1 + iIgnoreAtBeginning)) {
338 // ... before any letter character
339 iIgnoreAtBeginning++;
341 // ... after a letter character
342 bEndOfLetters = true;
346 if (!bEndOfLetters) {
347 word[i - iIgnoreAtBeginning] = (char) nc;
354 if (len < (remainCharCount + pushCharCount)) {
355 // word is too short to be hyphenated
358 int[] result = new int[len + 1];
361 // check exception list first
362 String sw = new String(word, 1, len);
363 if (stoplist.containsKey(sw)) {
364 // assume only simple hyphens (Hyphen.pre="-", Hyphen.post = Hyphen.no =
366 ArrayList<Object> hw = stoplist.get(sw);
368 for (i = 0; i < hw.size(); i++) {
369 Object o = hw.get(i);
370 // j = index(sw) = letterindex(word)?
371 // result[k] = corresponding index(w)
372 if (o instanceof String) {
373 j += ((String) o).length();
374 if (j >= remainCharCount && j < (len - pushCharCount)) {
375 result[k++] = j + iIgnoreAtBeginning;
380 // use algorithm to get hyphenation points
381 word[0] = '.'; // word start marker
382 word[len + 1] = '.'; // word end marker
383 word[len + 2] = 0; // null terminated
384 byte[] il = new byte[len + 3]; // initialized to zero
385 for (i = 0; i < len + 1; i++) {
386 searchPatterns(word, i, il);
389 // hyphenation points are located where interletter value is odd
390 // i is letterindex(word),
391 // i + 1 is index(word),
392 // result[k] = corresponding index(w)
393 for (i = 0; i < len; i++) {
394 if (((il[i + 1] & 1) == 1) && i >= remainCharCount
395 && i <= (len - pushCharCount)) {
396 result[k++] = i + iIgnoreAtBeginning;
403 int[] res = new int[k+2];
404 System.arraycopy(result, 0, res, 1, k);
405 // We add the synthetical hyphenation points
406 // at the beginning and end of the word
409 return new Hyphenation(res);
416 * Add a character class to the tree. It is used by
417 * {@link PatternParser PatternParser} as callback to add character classes.
418 * Character classes define the valid word characters for hyphenation. If a
419 * word contains a character not defined in any of the classes, it is not
420 * hyphenated. It also defines a way to normalize the characters in order to
421 * compare them with the stored patterns. Usually pattern files use only lower
422 * case characters, in this case a class for letter 'a', for example, should
423 * be defined as "aA", the first character being the normalization char.
425 public void addClass(String chargroup) {
426 if (chargroup.length() > 0) {
427 char equivChar = chargroup.charAt(0);
428 char[] key = new char[2];
430 for (int i = 0; i < chargroup.length(); i++) {
431 key[0] = chargroup.charAt(i);
432 classmap.insert(key, 0, equivChar);
438 * Add an exception to the tree. It is used by
439 * {@link PatternParser PatternParser} class as callback to store the
440 * hyphenation exceptions.
442 * @param word normalized word
443 * @param hyphenatedword a vector of alternating strings and
444 * {@link Hyphen hyphen} objects.
446 public void addException(String word, ArrayList<Object> hyphenatedword) {
447 stoplist.put(word, hyphenatedword);
451 * Add a pattern to the tree. Mainly, to be used by
452 * {@link PatternParser PatternParser} class as callback to add a pattern to
455 * @param pattern the hyphenation pattern
456 * @param ivalue interletter weight values indicating the desirability and
457 * priority of hyphenating at a given point within the pattern. It
458 * should contain only digit characters. (i.e. '0' to '9').
460 public void addPattern(String pattern, String ivalue) {
461 int k = ivalues.find(ivalue);
463 k = packValues(ivalue);
464 ivalues.insert(ivalue, (char) k);
466 insert(pattern, (char) k);
470 public void printStats() {
471 System.out.println("Value space size = "
472 + Integer.toString(vspace.length()));