lucene-java-3.4.0/lucene/contrib/analyzers/stempel/src/java/org/egothor/stemmer/Trie.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  * A Trie is used to store a dictionary of words and their stems.
  65  * <p>
  66  * Actually, what is stored are words with their respective patch commands. A
  67  * trie can be termed forward (keys read from left to right) or backward (keys
  68  * read from right to left). This property will vary depending on the language
  69  * for which a Trie is constructed.
  70  */
  71 public class Trie {
  72   List<Row> rows = new ArrayList<Row>();
  73   List<CharSequence> cmds = new ArrayList<CharSequence>();
  74   int root;
  75
  76   boolean forward = false;
  77
  78   /**
  79    * Constructor for the Trie object.
  80    *
  81    * @param is the input stream
  82    * @exception IOException if an I/O error occurs
  83    */
  84   public Trie(DataInput is) throws IOException {
  85     forward = is.readBoolean();
  86     root = is.readInt();
  87     for (int i = is.readInt(); i > 0; i--) {
  88       cmds.add(is.readUTF());
  89     }
  90     for (int i = is.readInt(); i > 0; i--) {
  91       rows.add(new Row(is));
  92     }
  93   }
  94
  95   /**
  96    * Constructor for the Trie object.
  97    *
  98    * @param forward set to <tt>true</tt>
  99    */
 100   public Trie(boolean forward) {
 101     rows.add(new Row());
 102     root = 0;
 103     this.forward = forward;
 104   }
 105
 106   /**
 107    * Constructor for the Trie object.
 108    *
 109    * @param forward <tt>true</tt> if read left to right, <tt>false</tt> if read
 110    *          right to left
 111    * @param root index of the row that is the root node
 112    * @param cmds the patch commands to store
 113    * @param rows a Vector of Vectors. Each inner Vector is a node of this Trie
 114    */
 115   public Trie(boolean forward, int root, List<CharSequence> cmds, List<Row> rows) {
 116     this.rows = rows;
 117     this.cmds = cmds;
 118     this.root = root;
 119     this.forward = forward;
 120   }
 121
 122   /**
 123    * Gets the all attribute of the Trie object
 124    *
 125    * @param key Description of the Parameter
 126    * @return The all value
 127    */
 128   public CharSequence[] getAll(CharSequence key) {
 129     int res[] = new int[key.length()];
 130     int resc = 0;
 131     Row now = getRow(root);
 132     int w;
 133     StrEnum e = new StrEnum(key, forward);
 134     boolean br = false;
 135
 136     for (int i = 0; i < key.length() - 1; i++) {
 137       Character ch = new Character(e.next());
 138       w = now.getCmd(ch);
 139       if (w >= 0) {
 140         int n = w;
 141         for (int j = 0; j < resc; j++) {
 142           if (n == res[j]) {
 143             n = -1;
 144             break;
 145           }
 146         }
 147         if (n >= 0) {
 148           res[resc++] = n;
 149         }
 150       }
 151       w = now.getRef(ch);
 152       if (w >= 0) {
 153         now = getRow(w);
 154       } else {
 155         br = true;
 156         break;
 157       }
 158     }
 159     if (br == false) {
 160       w = now.getCmd(new Character(e.next()));
 161       if (w >= 0) {
 162         int n = w;
 163         for (int j = 0; j < resc; j++) {
 164           if (n == res[j]) {
 165             n = -1;
 166             break;
 167           }
 168         }
 169         if (n >= 0) {
 170           res[resc++] = n;
 171         }
 172       }
 173     }
 174
 175     if (resc < 1) {
 176       return null;
 177     }
 178     CharSequence R[] = new CharSequence[resc];
 179     for (int j = 0; j < resc; j++) {
 180       R[j] = cmds.get(res[j]);
 181     }
 182     return R;
 183   }
 184
 185   /**
 186    * Return the number of cells in this Trie object.
 187    *
 188    * @return the number of cells
 189    */
 190   public int getCells() {
 191     int size = 0;
 192     for (Row row : rows)
 193       size += row.getCells();
 194     return size;
 195   }
 196
 197   /**
 198    * Gets the cellsPnt attribute of the Trie object
 199    *
 200    * @return The cellsPnt value
 201    */
 202   public int getCellsPnt() {
 203     int size = 0;
 204     for (Row row : rows)
 205       size += row.getCellsPnt();
 206     return size;
 207   }
 208
 209   /**
 210    * Gets the cellsVal attribute of the Trie object
 211    *
 212    * @return The cellsVal value
 213    */
 214   public int getCellsVal() {
 215     int size = 0;
 216     for (Row row : rows)
 217       size += row.getCellsVal();
 218     return size;
 219   }
 220
 221   /**
 222    * Return the element that is stored in a cell associated with the given key.
 223    *
 224    * @param key the key
 225    * @return the associated element
 226    */
 227   public CharSequence getFully(CharSequence key) {
 228     Row now = getRow(root);
 229     int w;
 230     Cell c;
 231     int cmd = -1;
 232     StrEnum e = new StrEnum(key, forward);
 233     Character ch = null;
 234     Character aux = null;
 235
 236     for (int i = 0; i < key.length();) {
 237       ch = new Character(e.next());
 238       i++;
 239
 240       c = now.at(ch);
 241       if (c == null) {
 242         return null;
 243       }
 244
 245       cmd = c.cmd;
 246
 247       for (int skip = c.skip; skip > 0; skip--) {
 248         if (i < key.length()) {
 249           aux = new Character(e.next());
 250         } else {
 251           return null;
 252         }
 253         i++;
 254       }
 255
 256       w = now.getRef(ch);
 257       if (w >= 0) {
 258         now = getRow(w);
 259       } else if (i < key.length()) {
 260         return null;
 261       }
 262     }
 263     return (cmd == -1) ? null : cmds.get(cmd);
 264   }
 265
 266   /**
 267    * Return the element that is stored as last on a path associated with the
 268    * given key.
 269    *
 270    * @param key the key associated with the desired element
 271    * @return the last on path element
 272    */
 273   public CharSequence getLastOnPath(CharSequence key) {
 274     Row now = getRow(root);
 275     int w;
 276     CharSequence last = null;
 277     StrEnum e = new StrEnum(key, forward);
 278
 279     for (int i = 0; i < key.length() - 1; i++) {
 280       Character ch = new Character(e.next());
 281       w = now.getCmd(ch);
 282       if (w >= 0) {
 283         last = cmds.get(w);
 284       }
 285       w = now.getRef(ch);
 286       if (w >= 0) {
 287         now = getRow(w);
 288       } else {
 289         return last;
 290       }
 291     }
 292     w = now.getCmd(new Character(e.next()));
 293     return (w >= 0) ? cmds.get(w) : last;
 294   }
 295
 296   /**
 297    * Return the Row at the given index.
 298    *
 299    * @param index the index containing the desired Row
 300    * @return the Row
 301    */
 302   private Row getRow(int index) {
 303     if (index < 0 || index >= rows.size()) {
 304       return null;
 305     }
 306     return rows.get(index);
 307   }
 308
 309   /**
 310    * Write this Trie to the given output stream.
 311    *
 312    * @param os the output stream
 313    * @exception IOException if an I/O error occurs
 314    */
 315   public void store(DataOutput os) throws IOException {
 316     os.writeBoolean(forward);
 317     os.writeInt(root);
 318     os.writeInt(cmds.size());
 319     for (CharSequence cmd : cmds)
 320       os.writeUTF(cmd.toString());
 321
 322     os.writeInt(rows.size());
 323     for (Row row : rows)
 324       row.store(os);
 325   }
 326
 327   /**
 328    * Add the given key associated with the given patch command. If either
 329    * parameter is null this method will return without executing.
 330    *
 331    * @param key the key
 332    * @param cmd the patch command
 333    */
 334   public void add(CharSequence key, CharSequence cmd) {
 335     if (key == null || cmd == null) {
 336       return;
 337     }
 338     if (cmd.length() == 0) {
 339       return;
 340     }
 341     int id_cmd = cmds.indexOf(cmd);
 342     if (id_cmd == -1) {
 343       id_cmd = cmds.size();
 344       cmds.add(cmd);
 345     }
 346
 347     int node = root;
 348     Row r = getRow(node);
 349
 350     StrEnum e = new StrEnum(key, forward);
 351
 352     for (int i = 0; i < e.length() - 1; i++) {
 353       Character ch = new Character(e.next());
 354       node = r.getRef(ch);
 355       if (node >= 0) {
 356         r = getRow(node);
 357       } else {
 358         node = rows.size();
 359         Row n;
 360         rows.add(n = new Row());
 361         r.setRef(ch, node);
 362         r = n;
 363       }
 364     }
 365     r.setCmd(new Character(e.next()), id_cmd);
 366   }
 367
 368   /**
 369    * Remove empty rows from the given Trie and return the newly reduced Trie.
 370    *
 371    * @param by the Trie to reduce
 372    * @return the newly reduced Trie
 373    */
 374   public Trie reduce(Reduce by) {
 375     return by.optimize(this);
 376   }
 377
 378   public void printInfo(CharSequence prefix) {
 379     System.out.println(prefix + "nds " + rows.size() + " cmds " + cmds.size()
 380         + " cells " + getCells() + " valcells " + getCellsVal() + " pntcells "
 381         + getCellsPnt());
 382   }
 383
 384   /**
 385    * This class is part of the Egothor Project
 386    */
 387   class StrEnum {
 388     CharSequence s;
 389     int from;
 390     int by;
 391
 392     /**
 393      * Constructor for the StrEnum object
 394      *
 395      * @param s Description of the Parameter
 396      * @param up Description of the Parameter
 397      */
 398     StrEnum(CharSequence s, boolean up) {
 399       this.s = s;
 400       if (up) {
 401         from = 0;
 402         by = 1;
 403       } else {
 404         from = s.length() - 1;
 405         by = -1;
 406       }
 407     }
 408
 409     int length() {
 410       return s.length();
 411     }
 412
 413     char next() {
 414       char ch = s.charAt(from);
 415       from += by;
 416       return ch;
 417     }
 418   }
 419 }