| /* |
| 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; |
| |
| /** |
| * The MultiTrie is a Trie of Tries. |
| * <p> |
| * It stores words and their associated patch commands. The MultiTrie handles |
| * patch commands broken into their constituent parts, as a MultiTrie does, but |
| * the commands are delimited by the skip command. |
| */ |
| public class MultiTrie2 extends MultiTrie { |
| /** |
| * Constructor for the MultiTrie object. |
| * |
| * @param is the input stream |
| * @exception IOException if an I/O error occurs |
| */ |
| public MultiTrie2(DataInput is) throws IOException { |
| super(is); |
| } |
| |
| /** |
| * Constructor for the MultiTrie2 object |
| * |
| * @param forward set to <tt>true</tt> if the elements should be read left to |
| * right |
| */ |
| public MultiTrie2(boolean forward) { |
| super(forward); |
| } |
| |
| /** |
| * Return the element that is stored in a cell associated with the given key. |
| * |
| * @param key the key to the cell holding the desired element |
| * @return the element |
| */ |
| @Override |
| public CharSequence getFully(CharSequence key) { |
| StringBuilder result = new StringBuilder(tries.size() * 2); |
| try { |
| CharSequence lastkey = key; |
| CharSequence p[] = new CharSequence[tries.size()]; |
| char lastch = ' '; |
| for (int i = 0; i < tries.size(); i++) { |
| CharSequence r = tries.get(i).getFully(lastkey); |
| if (r == null || (r.length() == 1 && r.charAt(0) == EOM)) { |
| return result; |
| } |
| if (cannotFollow(lastch, r.charAt(0))) { |
| return result; |
| } else { |
| lastch = r.charAt(r.length() - 2); |
| } |
| // key=key.substring(lengthPP(r)); |
| p[i] = r; |
| if (p[i].charAt(0) == '-') { |
| if (i > 0) { |
| key = skip(key, lengthPP(p[i - 1])); |
| } |
| key = skip(key, lengthPP(p[i])); |
| } |
| // key = skip(key, lengthPP(r)); |
| result.append(r); |
| if (key.length() != 0) { |
| lastkey = key; |
| } |
| } |
| } catch (IndexOutOfBoundsException x) {} |
| return result; |
| } |
| |
| /** |
| * Return the element that is stored as last on a path belonging to the given |
| * key. |
| * |
| * @param key the key associated with the desired element |
| * @return the element that is stored as last on a path |
| */ |
| @Override |
| public CharSequence getLastOnPath(CharSequence key) { |
| StringBuilder result = new StringBuilder(tries.size() * 2); |
| try { |
| CharSequence lastkey = key; |
| CharSequence p[] = new CharSequence[tries.size()]; |
| char lastch = ' '; |
| for (int i = 0; i < tries.size(); i++) { |
| CharSequence r = tries.get(i).getLastOnPath(lastkey); |
| if (r == null || (r.length() == 1 && r.charAt(0) == EOM)) { |
| return result; |
| } |
| // System.err.println("LP:"+key+" last:"+lastch+" new:"+r); |
| if (cannotFollow(lastch, r.charAt(0))) { |
| return result; |
| } else { |
| lastch = r.charAt(r.length() - 2); |
| } |
| // key=key.substring(lengthPP(r)); |
| p[i] = r; |
| if (p[i].charAt(0) == '-') { |
| if (i > 0) { |
| key = skip(key, lengthPP(p[i - 1])); |
| } |
| key = skip(key, lengthPP(p[i])); |
| } |
| // key = skip(key, lengthPP(r)); |
| result.append(r); |
| if (key.length() != 0) { |
| lastkey = key; |
| } |
| } |
| } catch (IndexOutOfBoundsException x) {} |
| return result; |
| } |
| |
| /** |
| * Write this data structure to the given output stream. |
| * |
| * @param os the output stream |
| * @exception IOException if an I/O error occurs |
| */ |
| @Override |
| public void store(DataOutput os) throws IOException { |
| super.store(os); |
| } |
| |
| /** |
| * Add an element to this structure consisting of the given key and patch |
| * command. |
| * <p> |
| * This method will return without executing if the <tt>cmd</tt> |
| * parameter's length is 0. |
| * |
| * @param key the key |
| * @param cmd the patch command |
| */ |
| @Override |
| public void add(CharSequence key, CharSequence cmd) { |
| if (cmd.length() == 0) { |
| return; |
| } |
| // System.err.println( cmd ); |
| CharSequence p[] = decompose(cmd); |
| int levels = p.length; |
| // System.err.println("levels "+key+" cmd "+cmd+"|"+levels); |
| while (levels >= tries.size()) { |
| tries.add(new Trie(forward)); |
| } |
| CharSequence lastkey = key; |
| for (int i = 0; i < levels; i++) { |
| if (key.length() > 0) { |
| tries.get(i).add(key, p[i]); |
| lastkey = key; |
| } else { |
| tries.get(i).add(lastkey, p[i]); |
| } |
| // System.err.println("-"+key+" "+p[i]+"|"+key.length()); |
| /* |
| * key=key.substring(lengthPP(p[i])); |
| */ |
| if (p[i].length() > 0 && p[i].charAt(0) == '-') { |
| if (i > 0) { |
| key = skip(key, lengthPP(p[i - 1])); |
| } |
| key = skip(key, lengthPP(p[i])); |
| } |
| // System.err.println("--->"+key); |
| } |
| if (key.length() > 0) { |
| tries.get(levels).add(key, EOM_NODE); |
| } else { |
| tries.get(levels).add(lastkey, EOM_NODE); |
| } |
| } |
| |
| /** |
| * Break the given patch command into its constituent pieces. The pieces are |
| * delimited by NOOP commands. |
| * |
| * @param cmd the patch command |
| * @return an array containing the pieces of the command |
| */ |
| public CharSequence[] decompose(CharSequence cmd) { |
| int parts = 0; |
| |
| for (int i = 0; 0 <= i && i < cmd.length();) { |
| int next = dashEven(cmd, i); |
| if (i == next) { |
| parts++; |
| i = next + 2; |
| } else { |
| parts++; |
| i = next; |
| } |
| } |
| |
| CharSequence part[] = new CharSequence[parts]; |
| int x = 0; |
| |
| for (int i = 0; 0 <= i && i < cmd.length();) { |
| int next = dashEven(cmd, i); |
| if (i == next) { |
| part[x++] = cmd.subSequence(i, i + 2); |
| i = next + 2; |
| } else { |
| part[x++] = (next < 0) ? cmd.subSequence(i, cmd.length()) : cmd.subSequence(i, next); |
| i = next; |
| } |
| } |
| return part; |
| } |
| |
| /** |
| * Remove empty rows from the given Trie and return the newly reduced Trie. |
| * |
| * @param by the Trie to reduce |
| * @return the newly reduced Trie |
| */ |
| @Override |
| public Trie reduce(Reduce by) { |
| List<Trie> h = new ArrayList<>(); |
| for (Trie trie : tries) |
| h.add(trie.reduce(by)); |
| |
| MultiTrie2 m = new MultiTrie2(forward); |
| m.tries = h; |
| return m; |
| } |
| |
| private boolean cannotFollow(char after, char goes) { |
| switch (after) { |
| case '-': |
| case 'D': |
| return after == goes; |
| } |
| return false; |
| } |
| |
| private CharSequence skip(CharSequence in, int count) { |
| if (forward) { |
| return in.subSequence(count, in.length()); |
| } else { |
| return in.subSequence(0, in.length() - count); |
| } |
| } |
| |
| private int dashEven(CharSequence in, int from) { |
| while (from < in.length()) { |
| if (in.charAt(from) == '-') { |
| return from; |
| } else { |
| from += 2; |
| } |
| } |
| return -1; |
| } |
| |
| @SuppressWarnings("fallthrough") |
| private int lengthPP(CharSequence cmd) { |
| int len = 0; |
| for (int i = 0; i < cmd.length(); i++) { |
| switch (cmd.charAt(i++)) { |
| case '-': |
| case 'D': |
| len += cmd.charAt(i) - 'a' + 1; |
| break; |
| case 'R': |
| len++; /* intentional fallthrough */ |
| case 'I': |
| break; |
| } |
| } |
| return len; |
| } |
| } |
