+++ /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;
-
-/**
- * The Diff object generates a patch string.
- * <p>
- * A patch string is actually a command to a stemmer telling it how to reduce a
- * word to its root. For example, to reduce the word teacher to its root teach
- * the patch string Db would be generated. This command tells the stemmer to
- * delete the last 2 characters from the word teacher to reach the stem (the
- * patch commands are applied starting from the last character in order to save
- */
-public class Diff {
- int sizex = 0;
- int sizey = 0;
- int net[][];
- int way[][];
-
- int INSERT;
- int DELETE;
- int REPLACE;
- int NOOP;
-
- /**
- * Constructor for the Diff object.
- */
- public Diff() {
- this(1, 1, 1, 0);
- }
-
- /**
- * Constructor for the Diff object
- *
- * @param ins Description of the Parameter
- * @param del Description of the Parameter
- * @param rep Description of the Parameter
- * @param noop Description of the Parameter
- */
- public Diff(int ins, int del, int rep, int noop) {
- INSERT = ins;
- DELETE = del;
- REPLACE = rep;
- NOOP = noop;
- }
-
- /**
- * Apply the given patch string <tt>diff</tt> to the given string <tt>
- * dest</tt>.
- *
- * @param dest Destination string
- * @param diff Patch string
- */
- public static void apply(StringBuilder dest, CharSequence diff) {
- try {
-
- if (diff == null) {
- return;
- }
-
- int pos = dest.length() - 1;
- if (pos < 0) {
- return;
- }
- // orig == ""
- for (int i = 0; i < diff.length() / 2; i++) {
- char cmd = diff.charAt(2 * i);
- char param = diff.charAt(2 * i + 1);
- int par_num = (param - 'a' + 1);
- switch (cmd) {
- case '-':
- pos = pos - par_num + 1;
- break;
- case 'R':
- dest.setCharAt(pos, param);
- break;
- case 'D':
- int o = pos;
- pos -= par_num - 1;
- /*
- * delete par_num chars from index pos
- */
- // String s = orig.toString();
- // s = s.substring( 0, pos ) + s.substring( o + 1 );
- // orig = new StringBuffer( s );
- dest.delete(pos, o + 1);
- break;
- case 'I':
- dest.insert(pos += 1, param);
- break;
- }
- pos--;
- }
- } catch (StringIndexOutOfBoundsException x) {
- // x.printStackTrace();
- } catch (ArrayIndexOutOfBoundsException x) {
- // x.printStackTrace();
- }
- }
-
- /**
- * Construct a patch string that transforms a to b.
- *
- * @param a String 1st string
- * @param b String 2nd string
- * @return String
- */
- public synchronized String exec(String a, String b) {
- if (a == null || b == null) {
- return null;
- }
-
- int x;
- int y;
- int maxx;
- int maxy;
- int go[] = new int[4];
- final int X = 1;
- final int Y = 2;
- final int R = 3;
- final int D = 0;
-
- /*
- * setup memory if needed => processing speed up
- */
- maxx = a.length() + 1;
- maxy = b.length() + 1;
- if ((maxx >= sizex) || (maxy >= sizey)) {
- sizex = maxx + 8;
- sizey = maxy + 8;
- net = new int[sizex][sizey];
- way = new int[sizex][sizey];
- }
-
- /*
- * clear the network
- */
- for (x = 0; x < maxx; x++) {
- for (y = 0; y < maxy; y++) {
- net[x][y] = 0;
- }
- }
-
- /*
- * set known persistent values
- */
- for (x = 1; x < maxx; x++) {
- net[x][0] = x;
- way[x][0] = X;
- }
- for (y = 1; y < maxy; y++) {
- net[0][y] = y;
- way[0][y] = Y;
- }
-
- for (x = 1; x < maxx; x++) {
- for (y = 1; y < maxy; y++) {
- go[X] = net[x - 1][y] + DELETE;
- // way on x costs 1 unit
- go[Y] = net[x][y - 1] + INSERT;
- // way on y costs 1 unit
- go[R] = net[x - 1][y - 1] + REPLACE;
- go[D] = net[x - 1][y - 1]
- + ((a.charAt(x - 1) == b.charAt(y - 1)) ? NOOP : 100);
- // diagonal costs 0, when no change
- short min = D;
- if (go[min] >= go[X]) {
- min = X;
- }
- if (go[min] > go[Y]) {
- min = Y;
- }
- if (go[min] > go[R]) {
- min = R;
- }
- way[x][y] = min;
- net[x][y] = (short) go[min];
- }
- }
-
- // read the patch string
- StringBuffer result = new StringBuffer();
- final char base = 'a' - 1;
- char deletes = base;
- char equals = base;
- for (x = maxx - 1, y = maxy - 1; x + y != 0;) {
- switch (way[x][y]) {
- case X:
- if (equals != base) {
- result.append("-" + (equals));
- equals = base;
- }
- deletes++;
- x--;
- break;
- // delete
- case Y:
- if (deletes != base) {
- result.append("D" + (deletes));
- deletes = base;
- }
- if (equals != base) {
- result.append("-" + (equals));
- equals = base;
- }
- result.append('I');
- result.append(b.charAt(--y));
- break;
- // insert
- case R:
- if (deletes != base) {
- result.append("D" + (deletes));
- deletes = base;
- }
- if (equals != base) {
- result.append("-" + (equals));
- equals = base;
- }
- result.append('R');
- result.append(b.charAt(--y));
- x--;
- break;
- // replace
- case D:
- if (deletes != base) {
- result.append("D" + (deletes));
- deletes = base;
- }
- equals++;
- x--;
- y--;
- break;
- // no change
- }
- }
- if (deletes != base) {
- result.append("D" + (deletes));
- deletes = base;
- }
-
- return result.toString();
- }
-}
fnp / pylucene.git / blobdiff