lucene-java-3.5.0/lucene/contrib/analyzers/stempel/src/java/org/egothor/stemmer/MultiTrie2.java

   1 /*
   2                     Egothor Software License version 1.00
   3                     Copyright (C) 1997-2004 Leo Galambos.
   4                  Copyright (C) 2002-2004 "Egothor developers"
   5                       on behalf of the Egothor Project.
   6                              All rights reserved.
   7
   8    This  software  is  copyrighted  by  the "Egothor developers". If this
   9    license applies to a single file or document, the "Egothor developers"
  10    are the people or entities mentioned as copyright holders in that file
  11    or  document.  If  this  license  applies  to the Egothor project as a
  12    whole,  the  copyright holders are the people or entities mentioned in
  13    the  file CREDITS. This file can be found in the same location as this
  14    license in the distribution.
  15
  16    Redistribution  and  use  in  source and binary forms, with or without
  17    modification, are permitted provided that the following conditions are
  18    met:
  19     1. Redistributions  of  source  code  must retain the above copyright
  20        notice, the list of contributors, this list of conditions, and the
  21        following disclaimer.
  22     2. Redistributions  in binary form must reproduce the above copyright
  23        notice, the list of contributors, this list of conditions, and the
  24        disclaimer  that  follows  these  conditions  in the documentation
  25        and/or other materials provided with the distribution.
  26     3. The name "Egothor" must not be used to endorse or promote products
  27        derived  from  this software without prior written permission. For
  28        written permission, please contact Leo.G@seznam.cz
  29     4. Products  derived  from this software may not be called "Egothor",
  30        nor  may  "Egothor"  appear  in  their name, without prior written
  31        permission from Leo.G@seznam.cz.
  32
  33    In addition, we request that you include in the end-user documentation
  34    provided  with  the  redistribution  and/or  in the software itself an
  35    acknowledgement equivalent to the following:
  36    "This product includes software developed by the Egothor Project.
  37     http://egothor.sf.net/"
  38
  39    THIS  SOFTWARE  IS  PROVIDED  ``AS  IS''  AND ANY EXPRESSED OR IMPLIED
  40    WARRANTIES,  INCLUDING,  BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  41    MERCHANTABILITY  AND  FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  42    IN  NO  EVENT  SHALL THE EGOTHOR PROJECT OR ITS CONTRIBUTORS BE LIABLE
  43    FOR   ANY   DIRECT,   INDIRECT,  INCIDENTAL,  SPECIAL,  EXEMPLARY,  OR
  44    CONSEQUENTIAL  DAMAGES  (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  45    SUBSTITUTE  GOODS  OR  SERVICES;  LOSS  OF  USE,  DATA, OR PROFITS; OR
  46    BUSINESS  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  47    WHETHER  IN  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
  48    OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
  49    IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  50
  51    This  software  consists  of  voluntary  contributions  made  by  many
  52    individuals  on  behalf  of  the  Egothor  Project  and was originally
  53    created by Leo Galambos (Leo.G@seznam.cz).
  54  */
  55 package org.egothor.stemmer;
  56
  57 import java.io.DataInput;
  58 import java.io.DataOutput;
  59 import java.io.IOException;
  60 import java.util.ArrayList;
  61 import java.util.List;
  62
  63 /**
  64  * The MultiTrie is a Trie of Tries.
  65  * <p>
  66  * It stores words and their associated patch commands. The MultiTrie handles
  67  * patch commmands broken into their constituent parts, as a MultiTrie does, but
  68  * the commands are delimited by the skip command.
  69  */
  70 public class MultiTrie2 extends MultiTrie {
  71   /**
  72    * Constructor for the MultiTrie object.
  73    *
  74    * @param is the input stream
  75    * @exception IOException if an I/O error occurs
  76    */
  77   public MultiTrie2(DataInput is) throws IOException {
  78     super(is);
  79   }
  80
  81   /**
  82    * Constructor for the MultiTrie2 object
  83    *
  84    * @param forward set to <tt>true</tt> if the elements should be read left to
  85    *          right
  86    */
  87   public MultiTrie2(boolean forward) {
  88     super(forward);
  89   }
  90
  91   /**
  92    * Return the element that is stored in a cell associated with the given key.
  93    *
  94    * @param key the key to the cell holding the desired element
  95    * @return the element
  96    */
  97   @Override
  98   public CharSequence getFully(CharSequence key) {
  99     StringBuilder result = new StringBuilder(tries.size() * 2);
 100     try {
 101       CharSequence lastkey = key;
 102       CharSequence p[] = new CharSequence[tries.size()];
 103       char lastch = ' ';
 104       for (int i = 0; i < tries.size(); i++) {
 105         CharSequence r = tries.get(i).getFully(lastkey);
 106         if (r == null || (r.length() == 1 && r.charAt(0) == EOM)) {
 107           return result;
 108         }
 109         if (cannotFollow(lastch, r.charAt(0))) {
 110           return result;
 111         } else {
 112           lastch = r.charAt(r.length() - 2);
 113         }
 114         // key=key.substring(lengthPP(r));
 115         p[i] = r;
 116         if (p[i].charAt(0) == '-') {
 117           if (i > 0) {
 118             key = skip(key, lengthPP(p[i - 1]));
 119           }
 120           key = skip(key, lengthPP(p[i]));
 121         }
 122         // key = skip(key, lengthPP(r));
 123         result.append(r);
 124         if (key.length() != 0) {
 125           lastkey = key;
 126         }
 127       }
 128     } catch (IndexOutOfBoundsException x) {}
 129     return result;
 130   }
 131
 132   /**
 133    * Return the element that is stored as last on a path belonging to the given
 134    * key.
 135    *
 136    * @param key the key associated with the desired element
 137    * @return the element that is stored as last on a path
 138    */
 139   @Override
 140   public CharSequence getLastOnPath(CharSequence key) {
 141     StringBuilder result = new StringBuilder(tries.size() * 2);
 142     try {
 143       CharSequence lastkey = key;
 144       CharSequence p[] = new CharSequence[tries.size()];
 145       char lastch = ' ';
 146       for (int i = 0; i < tries.size(); i++) {
 147         CharSequence r = tries.get(i).getLastOnPath(lastkey);
 148         if (r == null || (r.length() == 1 && r.charAt(0) == EOM)) {
 149           return result;
 150         }
 151         // System.err.println("LP:"+key+" last:"+lastch+" new:"+r);
 152         if (cannotFollow(lastch, r.charAt(0))) {
 153           return result;
 154         } else {
 155           lastch = r.charAt(r.length() - 2);
 156         }
 157         // key=key.substring(lengthPP(r));
 158         p[i] = r;
 159         if (p[i].charAt(0) == '-') {
 160           if (i > 0) {
 161             key = skip(key, lengthPP(p[i - 1]));
 162           }
 163           key = skip(key, lengthPP(p[i]));
 164         }
 165         // key = skip(key, lengthPP(r));
 166         result.append(r);
 167         if (key.length() != 0) {
 168           lastkey = key;
 169         }
 170       }
 171     } catch (IndexOutOfBoundsException x) {}
 172     return result;
 173   }
 174
 175   /**
 176    * Write this data structure to the given output stream.
 177    *
 178    * @param os the output stream
 179    * @exception IOException if an I/O error occurs
 180    */
 181   @Override
 182   public void store(DataOutput os) throws IOException {
 183     super.store(os);
 184   }
 185
 186   /**
 187    * Add an element to this structure consisting of the given key and patch
 188    * command.
 189    * <p>
 190    * This method will return without executing if the <tt>cmd</tt>
 191    * parameter's length is 0.
 192    *
 193    * @param key the key
 194    * @param cmd the patch command
 195    */
 196   @Override
 197   public void add(CharSequence key, CharSequence cmd) {
 198     if (cmd.length() == 0) {
 199       return;
 200     }
 201     // System.err.println( cmd );
 202     CharSequence p[] = decompose(cmd);
 203     int levels = p.length;
 204     // System.err.println("levels "+key+" cmd "+cmd+"|"+levels);
 205     while (levels >= tries.size()) {
 206       tries.add(new Trie(forward));
 207     }
 208     CharSequence lastkey = key;
 209     for (int i = 0; i < levels; i++) {
 210       if (key.length() > 0) {
 211         tries.get(i).add(key, p[i]);
 212         lastkey = key;
 213       } else {
 214         tries.get(i).add(lastkey, p[i]);
 215       }
 216       // System.err.println("-"+key+" "+p[i]+"|"+key.length());
 217       /*
 218        * key=key.substring(lengthPP(p[i]));
 219        */
 220       if (p[i].length() > 0 && p[i].charAt(0) == '-') {
 221         if (i > 0) {
 222           key = skip(key, lengthPP(p[i - 1]));
 223         }
 224         key = skip(key, lengthPP(p[i]));
 225       }
 226       // System.err.println("--->"+key);
 227     }
 228     if (key.length() > 0) {
 229       tries.get(levels).add(key, EOM_NODE);
 230     } else {
 231       tries.get(levels).add(lastkey, EOM_NODE);
 232     }
 233   }
 234
 235   /**
 236    * Break the given patch command into its constituent pieces. The pieces are
 237    * delimited by NOOP commands.
 238    *
 239    * @param cmd the patch command
 240    * @return an array containing the pieces of the command
 241    */
 242   public CharSequence[] decompose(CharSequence cmd) {
 243     int parts = 0;
 244
 245     for (int i = 0; 0 <= i && i < cmd.length();) {
 246       int next = dashEven(cmd, i);
 247       if (i == next) {
 248         parts++;
 249         i = next + 2;
 250       } else {
 251         parts++;
 252         i = next;
 253       }
 254     }
 255
 256     CharSequence part[] = new CharSequence[parts];
 257     int x = 0;
 258
 259     for (int i = 0; 0 <= i && i < cmd.length();) {
 260       int next = dashEven(cmd, i);
 261       if (i == next) {
 262         part[x++] = cmd.subSequence(i, i + 2);
 263         i = next + 2;
 264       } else {
 265         part[x++] = (next < 0) ? cmd.subSequence(i, cmd.length()) : cmd.subSequence(i, next);
 266         i = next;
 267       }
 268     }
 269     return part;
 270   }
 271
 272   /**
 273    * Remove empty rows from the given Trie and return the newly reduced Trie.
 274    *
 275    * @param by the Trie to reduce
 276    * @return the newly reduced Trie
 277    */
 278   @Override
 279   public Trie reduce(Reduce by) {
 280     List<Trie> h = new ArrayList<Trie>();
 281     for (Trie trie : tries)
 282       h.add(trie.reduce(by));
 283
 284     MultiTrie2 m = new MultiTrie2(forward);
 285     m.tries = h;
 286     return m;
 287   }
 288
 289   private boolean cannotFollow(char after, char goes) {
 290     switch (after) {
 291       case '-':
 292       case 'D':
 293         return after == goes;
 294     }
 295     return false;
 296   }
 297
 298   private CharSequence skip(CharSequence in, int count) {
 299     if (forward) {
 300       return in.subSequence(count, in.length());
 301     } else {
 302       return in.subSequence(0, in.length() - count);
 303     }
 304   }
 305
 306   private int dashEven(CharSequence in, int from) {
 307     while (from < in.length()) {
 308       if (in.charAt(from) == '-') {
 309         return from;
 310       } else {
 311         from += 2;
 312       }
 313     }
 314     return -1;
 315   }
 316
 317   @SuppressWarnings("fallthrough")
 318   private int lengthPP(CharSequence cmd) {
 319     int len = 0;
 320     for (int i = 0; i < cmd.length(); i++) {
 321       switch (cmd.charAt(i++)) {
 322         case '-':
 323         case 'D':
 324           len += cmd.charAt(i) - 'a' + 1;
 325           break;
 326         case 'R':
 327           len++; /* intentional fallthrough */
 328         case 'I':
 329           break;
 330       }
 331     }
 332     return len;
 333   }
 334 }