lucene-java-3.4.0/lucene/contrib/analyzers/common/src/java/org/apache/lucene/analysis/compound/hyphenation/HyphenationTree.java

   1 /*
   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
   8  *
   9  *      http://www.apache.org/licenses/LICENSE-2.0
  10  *
  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.
  16  */
  17
  18 package org.apache.lucene.analysis.compound.hyphenation;
  19
  20 import java.io.File;
  21 import java.io.Serializable;
  22 import java.net.MalformedURLException;
  23 import java.util.ArrayList;
  24 import java.util.HashMap;
  25
  26 import org.xml.sax.InputSource;
  27
  28 /**
  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.
  31  *
  32  * This class has been taken from the Apache FOP project (http://xmlgraphics.apache.org/fop/). They have been slightly modified.
  33  */
  34 public class HyphenationTree extends TernaryTree implements PatternConsumer,
  35     Serializable {
  36
  37   private static final long serialVersionUID = -7842107987915665573L;
  38
  39   /**
  40    * value space: stores the interletter values
  41    */
  42   protected ByteVector vspace;
  43
  44   /**
  45    * This map stores hyphenation exceptions
  46    */
  47   protected HashMap<String,ArrayList<Object>> stoplist;
  48
  49   /**
  50    * This map stores the character classes
  51    */
  52   protected TernaryTree classmap;
  53
  54   /**
  55    * Temporary map to store interletter values on pattern loading.
  56    */
  57   private transient TernaryTree ivalues;
  58
  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
  64   }
  65
  66   /**
  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
  69    * value.
  70    *
  71    * @param values a string of digits from '0' to '9' representing the
  72    *        interletter values.
  73    * @return the index into the vspace array where the packed values are stored.
  74    */
  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++) {
  81       int j = i >> 1;
  82       byte v = (byte) ((values.charAt(i) - '0' + 1) & 0x0f);
  83       if ((i & 1) == 1) {
  84         va[j + offset] = (byte) (va[j + offset] | v);
  85       } else {
  86         va[j + offset] = (byte) (v << 4); // big endian
  87       }
  88     }
  89     va[m - 1 + offset] = 0; // terminator
  90     return offset;
  91   }
  92
  93   protected String unpackValues(int k) {
  94     StringBuilder buf = new StringBuilder();
  95     byte v = vspace.get(k++);
  96     while (v != 0) {
  97       char c = (char) ((v >>> 4) - 1 + '0');
  98       buf.append(c);
  99       c = (char) (v & 0x0f);
 100       if (c == 0) {
 101         break;
 102       }
 103       c = (char) (c - 1 + '0');
 104       buf.append(c);
 105       v = vspace.get(k++);
 106     }
 107     return buf.toString();
 108   }
 109
 110   /**
 111    * Read hyphenation patterns from an XML file.
 112    *
 113    * @param f the filename
 114    * @throws HyphenationException In case the parsing fails
 115    */
 116   public void loadPatterns(File f) throws HyphenationException {
 117     try {
 118       InputSource src = new InputSource(f.toURL().toExternalForm());
 119       loadPatterns(src);
 120     } catch (MalformedURLException e) {
 121       throw new HyphenationException("Error converting the File '" + f
 122           + "' to a URL: " + e.getMessage());
 123     }
 124   }
 125
 126   /**
 127    * Read hyphenation patterns from an XML file.
 128    *
 129    * @param source the InputSource for the file
 130    * @throws HyphenationException In case the parsing fails
 131    */
 132   public void loadPatterns(InputSource source) throws HyphenationException {
 133     PatternParser pp = new PatternParser(this);
 134     ivalues = new TernaryTree();
 135
 136     pp.parse(source);
 137
 138     // patterns/values should be now in the tree
 139     // let's optimize a bit
 140     trimToSize();
 141     vspace.trimToSize();
 142     classmap.trimToSize();
 143
 144     // get rid of the auxiliary map
 145     ivalues = null;
 146   }
 147
 148   public String findPattern(String pat) {
 149     int k = super.find(pat);
 150     if (k >= 0) {
 151       return unpackValues(k);
 152     }
 153     return "";
 154   }
 155
 156   /**
 157    * String compare, returns 0 if equal or t is a substring of s
 158    */
 159   protected int hstrcmp(char[] s, int si, char[] t, int ti) {
 160     for (; s[si] == t[ti]; si++, ti++) {
 161       if (s[si] == 0) {
 162         return 0;
 163       }
 164     }
 165     if (t[ti] == 0) {
 166       return 0;
 167     }
 168     return s[si] - t[ti];
 169   }
 170
 171   protected byte[] getValues(int k) {
 172     StringBuilder buf = new StringBuilder();
 173     byte v = vspace.get(k++);
 174     while (v != 0) {
 175       char c = (char) ((v >>> 4) - 1);
 176       buf.append(c);
 177       c = (char) (v & 0x0f);
 178       if (c == 0) {
 179         break;
 180       }
 181       c = (char) (c - 1);
 182       buf.append(c);
 183       v = vspace.get(k++);
 184     }
 185     byte[] res = new byte[buf.length()];
 186     for (int i = 0; i < res.length; i++) {
 187       res[i] = (byte) buf.charAt(i);
 188     }
 189     return res;
 190   }
 191
 192   /**
 193    * <p>
 194    * Search for all possible partial matches of word starting at index an update
 195    * interletter values. In other words, it does something like:
 196    * </p>
 197    * <code>
 198    * for(i=0; i<patterns.length; i++) {
 199    * if ( word.substring(index).startsWidth(patterns[i]) )
 200    * update_interletter_values(patterns[i]);
 201    * }
 202    * </code>
 203    * <p>
 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
 212    * </p>
 213    *
 214    * @param word null terminated word to match
 215    * @param index start index from word
 216    * @param il interletter values array to update
 217    */
 218   protected void searchPatterns(char[] word, int index, byte[] il) {
 219     byte[] values;
 220     int i = index;
 221     char p, q;
 222     char sp = word[i];
 223     p = root;
 224
 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[]
 229           int j = index;
 230           for (int k = 0; k < values.length; k++) {
 231             if (j < il.length && values[k] > il[j]) {
 232               il[j] = values[k];
 233             }
 234             j++;
 235           }
 236         }
 237         return;
 238       }
 239       int d = sp - sc[p];
 240       if (d == 0) {
 241         if (sp == 0) {
 242           break;
 243         }
 244         sp = word[++i];
 245         p = eq[p];
 246         q = p;
 247
 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
 252             break;
 253           }
 254           if (sc[q] == 0) {
 255             values = getValues(eq[q]);
 256             int j = index;
 257             for (int k = 0; k < values.length; k++) {
 258               if (j < il.length && values[k] > il[j]) {
 259                 il[j] = values[k];
 260               }
 261               j++;
 262             }
 263             break;
 264           } else {
 265             q = lo[q];
 266
 267             /**
 268              * actually the code should be: q = sc[q] < 0 ? hi[q] : lo[q]; but
 269              * java chars are unsigned
 270              */
 271           }
 272         }
 273       } else {
 274         p = d < 0 ? lo[p] : hi[p];
 275       }
 276     }
 277   }
 278
 279   /**
 280    * Hyphenate word and return a Hyphenation object.
 281    *
 282    * @param word the word to be hyphenated
 283    * @param remainCharCount Minimum number of characters allowed before the
 284    *        hyphenation point.
 285    * @param pushCharCount Minimum number of characters allowed after the
 286    *        hyphenation point.
 287    * @return a {@link Hyphenation Hyphenation} object representing the
 288    *         hyphenated word or null if word is not hyphenated.
 289    */
 290   public Hyphenation hyphenate(String word, int remainCharCount,
 291       int pushCharCount) {
 292     char[] w = word.toCharArray();
 293     return hyphenate(w, 0, w.length, remainCharCount, pushCharCount);
 294   }
 295
 296   /**
 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 +
 307    * iIgnoreAtBeginning
 308    */
 309
 310   /**
 311    * Hyphenate word and return an array of hyphenation points.
 312    *
 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
 317    *        hyphenation point.
 318    * @param pushCharCount Minimum number of characters allowed after the
 319    *        hyphenation point.
 320    * @return a {@link Hyphenation Hyphenation} object representing the
 321    *         hyphenated word or null if word is not hyphenated.
 322    */
 323   public Hyphenation hyphenate(char[] w, int offset, int len,
 324       int remainCharCount, int pushCharCount) {
 325     int i;
 326     char[] word = new char[len + 3];
 327
 328     // normalize word
 329     char[] c = new char[2];
 330     int iIgnoreAtBeginning = 0;
 331     int iLength = len;
 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++;
 340         } else {
 341           // ... after a letter character
 342           bEndOfLetters = true;
 343         }
 344         iLength--;
 345       } else {
 346         if (!bEndOfLetters) {
 347           word[i - iIgnoreAtBeginning] = (char) nc;
 348         } else {
 349           return null;
 350         }
 351       }
 352     }
 353     len = iLength;
 354     if (len < (remainCharCount + pushCharCount)) {
 355       // word is too short to be hyphenated
 356       return null;
 357     }
 358     int[] result = new int[len + 1];
 359     int k = 0;
 360
 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 =
 365       // null)
 366       ArrayList<Object> hw = stoplist.get(sw);
 367       int j = 0;
 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;
 376           }
 377         }
 378       }
 379     } else {
 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);
 387       }
 388
 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;
 397         }
 398       }
 399     }
 400
 401     if (k > 0) {
 402       // trim result array
 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
 407       res[0]=0;
 408       res[k+1]=len;
 409       return new Hyphenation(res);
 410     } else {
 411       return null;
 412     }
 413   }
 414
 415   /**
 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.
 424    */
 425   public void addClass(String chargroup) {
 426     if (chargroup.length() > 0) {
 427       char equivChar = chargroup.charAt(0);
 428       char[] key = new char[2];
 429       key[1] = 0;
 430       for (int i = 0; i < chargroup.length(); i++) {
 431         key[0] = chargroup.charAt(i);
 432         classmap.insert(key, 0, equivChar);
 433       }
 434     }
 435   }
 436
 437   /**
 438    * Add an exception to the tree. It is used by
 439    * {@link PatternParser PatternParser} class as callback to store the
 440    * hyphenation exceptions.
 441    *
 442    * @param word normalized word
 443    * @param hyphenatedword a vector of alternating strings and
 444    *        {@link Hyphen hyphen} objects.
 445    */
 446   public void addException(String word, ArrayList<Object> hyphenatedword) {
 447     stoplist.put(word, hyphenatedword);
 448   }
 449
 450   /**
 451    * Add a pattern to the tree. Mainly, to be used by
 452    * {@link PatternParser PatternParser} class as callback to add a pattern to
 453    * the tree.
 454    *
 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').
 459    */
 460   public void addPattern(String pattern, String ivalue) {
 461     int k = ivalues.find(ivalue);
 462     if (k <= 0) {
 463       k = packValues(ivalue);
 464       ivalues.insert(ivalue, (char) k);
 465     }
 466     insert(pattern, (char) k);
 467   }
 468
 469   @Override
 470   public void printStats() {
 471     System.out.println("Value space size = "
 472         + Integer.toString(vspace.length()));
 473     super.printStats();
 474
 475   }
 476 }