+++ /dev/null
-/*
- Egothor Software License version 1.00
- Copyright (C) 1997-2004 Leo Galambos.
- Copyright (C) 2002-2004 "Egothor developers"
- on behalf of the Egothor Project.
- All rights reserved.
-
- This software is copyrighted by the "Egothor developers". If this
- license applies to a single file or document, the "Egothor developers"
- are the people or entities mentioned as copyright holders in that file
- or document. If this license applies to the Egothor project as a
- whole, the copyright holders are the people or entities mentioned in
- the file CREDITS. This file can be found in the same location as this
- license in the distribution.
-
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions are
- met:
- 1. Redistributions of source code must retain the above copyright
- notice, the list of contributors, this list of conditions, and the
- following disclaimer.
- 2. Redistributions in binary form must reproduce the above copyright
- notice, the list of contributors, this list of conditions, and the
- disclaimer that follows these conditions in the documentation
- and/or other materials provided with the distribution.
- 3. The name "Egothor" must not be used to endorse or promote products
- derived from this software without prior written permission. For
- written permission, please contact Leo.G@seznam.cz
- 4. Products derived from this software may not be called "Egothor",
- nor may "Egothor" appear in their name, without prior written
- permission from Leo.G@seznam.cz.
-
- In addition, we request that you include in the end-user documentation
- provided with the redistribution and/or in the software itself an
- acknowledgement equivalent to the following:
- "This product includes software developed by the Egothor Project.
- http://egothor.sf.net/"
-
- THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
- WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
- MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
- IN NO EVENT SHALL THE EGOTHOR PROJECT OR ITS CONTRIBUTORS BE LIABLE
- FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
- BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
- WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
- OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
- IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-
- This software consists of voluntary contributions made by many
- individuals on behalf of the Egothor Project and was originally
- created by Leo Galambos (Leo.G@seznam.cz).
- */
-package org.egothor.stemmer;
-
-import java.io.DataInput;
-import java.io.DataOutput;
-import java.io.IOException;
-import java.util.ArrayList;
-import java.util.List;
-
-/**
- * A Trie is used to store a dictionary of words and their stems.
- * <p>
- * Actually, what is stored are words with their respective patch commands. A
- * trie can be termed forward (keys read from left to right) or backward (keys
- * read from right to left). This property will vary depending on the language
- * for which a Trie is constructed.
- */
-public class Trie {
- List<Row> rows = new ArrayList<Row>();
- List<CharSequence> cmds = new ArrayList<CharSequence>();
- int root;
-
- boolean forward = false;
-
- /**
- * Constructor for the Trie object.
- *
- * @param is the input stream
- * @exception IOException if an I/O error occurs
- */
- public Trie(DataInput is) throws IOException {
- forward = is.readBoolean();
- root = is.readInt();
- for (int i = is.readInt(); i > 0; i--) {
- cmds.add(is.readUTF());
- }
- for (int i = is.readInt(); i > 0; i--) {
- rows.add(new Row(is));
- }
- }
-
- /**
- * Constructor for the Trie object.
- *
- * @param forward set to <tt>true</tt>
- */
- public Trie(boolean forward) {
- rows.add(new Row());
- root = 0;
- this.forward = forward;
- }
-
- /**
- * Constructor for the Trie object.
- *
- * @param forward <tt>true</tt> if read left to right, <tt>false</tt> if read
- * right to left
- * @param root index of the row that is the root node
- * @param cmds the patch commands to store
- * @param rows a Vector of Vectors. Each inner Vector is a node of this Trie
- */
- public Trie(boolean forward, int root, List<CharSequence> cmds, List<Row> rows) {
- this.rows = rows;
- this.cmds = cmds;
- this.root = root;
- this.forward = forward;
- }
-
- /**
- * Gets the all attribute of the Trie object
- *
- * @param key Description of the Parameter
- * @return The all value
- */
- public CharSequence[] getAll(CharSequence key) {
- int res[] = new int[key.length()];
- int resc = 0;
- Row now = getRow(root);
- int w;
- StrEnum e = new StrEnum(key, forward);
- boolean br = false;
-
- for (int i = 0; i < key.length() - 1; i++) {
- Character ch = new Character(e.next());
- w = now.getCmd(ch);
- if (w >= 0) {
- int n = w;
- for (int j = 0; j < resc; j++) {
- if (n == res[j]) {
- n = -1;
- break;
- }
- }
- if (n >= 0) {
- res[resc++] = n;
- }
- }
- w = now.getRef(ch);
- if (w >= 0) {
- now = getRow(w);
- } else {
- br = true;
- break;
- }
- }
- if (br == false) {
- w = now.getCmd(new Character(e.next()));
- if (w >= 0) {
- int n = w;
- for (int j = 0; j < resc; j++) {
- if (n == res[j]) {
- n = -1;
- break;
- }
- }
- if (n >= 0) {
- res[resc++] = n;
- }
- }
- }
-
- if (resc < 1) {
- return null;
- }
- CharSequence R[] = new CharSequence[resc];
- for (int j = 0; j < resc; j++) {
- R[j] = cmds.get(res[j]);
- }
- return R;
- }
-
- /**
- * Return the number of cells in this Trie object.
- *
- * @return the number of cells
- */
- public int getCells() {
- int size = 0;
- for (Row row : rows)
- size += row.getCells();
- return size;
- }
-
- /**
- * Gets the cellsPnt attribute of the Trie object
- *
- * @return The cellsPnt value
- */
- public int getCellsPnt() {
- int size = 0;
- for (Row row : rows)
- size += row.getCellsPnt();
- return size;
- }
-
- /**
- * Gets the cellsVal attribute of the Trie object
- *
- * @return The cellsVal value
- */
- public int getCellsVal() {
- int size = 0;
- for (Row row : rows)
- size += row.getCellsVal();
- return size;
- }
-
- /**
- * Return the element that is stored in a cell associated with the given key.
- *
- * @param key the key
- * @return the associated element
- */
- public CharSequence getFully(CharSequence key) {
- Row now = getRow(root);
- int w;
- Cell c;
- int cmd = -1;
- StrEnum e = new StrEnum(key, forward);
- Character ch = null;
- Character aux = null;
-
- for (int i = 0; i < key.length();) {
- ch = new Character(e.next());
- i++;
-
- c = now.at(ch);
- if (c == null) {
- return null;
- }
-
- cmd = c.cmd;
-
- for (int skip = c.skip; skip > 0; skip--) {
- if (i < key.length()) {
- aux = new Character(e.next());
- } else {
- return null;
- }
- i++;
- }
-
- w = now.getRef(ch);
- if (w >= 0) {
- now = getRow(w);
- } else if (i < key.length()) {
- return null;
- }
- }
- return (cmd == -1) ? null : cmds.get(cmd);
- }
-
- /**
- * Return the element that is stored as last on a path associated with the
- * given key.
- *
- * @param key the key associated with the desired element
- * @return the last on path element
- */
- public CharSequence getLastOnPath(CharSequence key) {
- Row now = getRow(root);
- int w;
- CharSequence last = null;
- StrEnum e = new StrEnum(key, forward);
-
- for (int i = 0; i < key.length() - 1; i++) {
- Character ch = new Character(e.next());
- w = now.getCmd(ch);
- if (w >= 0) {
- last = cmds.get(w);
- }
- w = now.getRef(ch);
- if (w >= 0) {
- now = getRow(w);
- } else {
- return last;
- }
- }
- w = now.getCmd(new Character(e.next()));
- return (w >= 0) ? cmds.get(w) : last;
- }
-
- /**
- * Return the Row at the given index.
- *
- * @param index the index containing the desired Row
- * @return the Row
- */
- private Row getRow(int index) {
- if (index < 0 || index >= rows.size()) {
- return null;
- }
- return rows.get(index);
- }
-
- /**
- * Write this Trie to the given output stream.
- *
- * @param os the output stream
- * @exception IOException if an I/O error occurs
- */
- public void store(DataOutput os) throws IOException {
- os.writeBoolean(forward);
- os.writeInt(root);
- os.writeInt(cmds.size());
- for (CharSequence cmd : cmds)
- os.writeUTF(cmd.toString());
-
- os.writeInt(rows.size());
- for (Row row : rows)
- row.store(os);
- }
-
- /**
- * Add the given key associated with the given patch command. If either
- * parameter is null this method will return without executing.
- *
- * @param key the key
- * @param cmd the patch command
- */
- public void add(CharSequence key, CharSequence cmd) {
- if (key == null || cmd == null) {
- return;
- }
- if (cmd.length() == 0) {
- return;
- }
- int id_cmd = cmds.indexOf(cmd);
- if (id_cmd == -1) {
- id_cmd = cmds.size();
- cmds.add(cmd);
- }
-
- int node = root;
- Row r = getRow(node);
-
- StrEnum e = new StrEnum(key, forward);
-
- for (int i = 0; i < e.length() - 1; i++) {
- Character ch = new Character(e.next());
- node = r.getRef(ch);
- if (node >= 0) {
- r = getRow(node);
- } else {
- node = rows.size();
- Row n;
- rows.add(n = new Row());
- r.setRef(ch, node);
- r = n;
- }
- }
- r.setCmd(new Character(e.next()), id_cmd);
- }
-
- /**
- * Remove empty rows from the given Trie and return the newly reduced Trie.
- *
- * @param by the Trie to reduce
- * @return the newly reduced Trie
- */
- public Trie reduce(Reduce by) {
- return by.optimize(this);
- }
-
- public void printInfo(CharSequence prefix) {
- System.out.println(prefix + "nds " + rows.size() + " cmds " + cmds.size()
- + " cells " + getCells() + " valcells " + getCellsVal() + " pntcells "
- + getCellsPnt());
- }
-
- /**
- * This class is part of the Egothor Project
- */
- class StrEnum {
- CharSequence s;
- int from;
- int by;
-
- /**
- * Constructor for the StrEnum object
- *
- * @param s Description of the Parameter
- * @param up Description of the Parameter
- */
- StrEnum(CharSequence s, boolean up) {
- this.s = s;
- if (up) {
- from = 0;
- by = 1;
- } else {
- from = s.length() - 1;
- by = -1;
- }
- }
-
- int length() {
- return s.length();
- }
-
- char next() {
- char ch = s.charAt(from);
- from += by;
- return ch;
- }
- }
-}
fnp / pylucene.git / blobdiff