lucene-java-3.5.0/lucene/contrib/spellchecker/src/java/org/apache/lucene/search/spell/NGramDistance.java

   1 package org.apache.lucene.search.spell;
   2
   3 /**
   4 * Licensed to the Apache Software Foundation (ASF) under one or more
   5 * contributor license agreements.  See the NOTICE file distributed with
   6 * this work for additional information regarding copyright ownership.
   7 * The ASF licenses this file to You under the Apache License, Version 2.0
   8 * (the "License"); you may not use this file except in compliance with
   9 * the License.  You may obtain a copy of the License at
  10 *
  11 *     http://www.apache.org/licenses/LICENSE-2.0
  12 *
  13 * Unless required by applicable law or agreed to in writing, software
  14 * distributed under the License is distributed on an "AS IS" BASIS,
  15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16 * See the License for the specific language governing permissions and
  17 * limitations under the License.
  18 */
  19
  20 /**
  21  * N-Gram version of edit distance based on paper by Grzegorz Kondrak,
  22  * "N-gram similarity and distance". Proceedings of the Twelfth International
  23  * Conference on String Processing and Information Retrieval (SPIRE 2005), pp. 115-126,
  24  * Buenos Aires, Argentina, November 2005.
  25  * http://www.cs.ualberta.ca/~kondrak/papers/spire05.pdf
  26  *
  27  * This implementation uses the position-based optimization to compute partial
  28  * matches of n-gram sub-strings and adds a null-character prefix of size n-1
  29  * so that the first character is contained in the same number of n-grams as
  30  * a middle character.  Null-character prefix matches are discounted so that
  31  * strings with no matching characters will return a distance of 0.
  32  *
  33  */
  34 public class NGramDistance implements StringDistance {
  35
  36   private int n;
  37
  38   /**
  39    * Creates an N-Gram distance measure using n-grams of the specified size.
  40    * @param size The size of the n-gram to be used to compute the string distance.
  41    */
  42   public NGramDistance(int size) {
  43     this.n = size;
  44   }
  45
  46   /**
  47    * Creates an N-Gram distance measure using n-grams of size 2.
  48    */
  49   public NGramDistance() {
  50     this(2);
  51   }
  52
  53   public float getDistance(String source, String target) {
  54     final int sl = source.length();
  55     final int tl = target.length();
  56
  57     if (sl == 0 || tl == 0) {
  58       if (sl == tl) {
  59         return 1;
  60       }
  61       else {
  62         return 0;
  63       }
  64     }
  65
  66     int cost = 0;
  67     if (sl < n || tl < n) {
  68       for (int i=0,ni=Math.min(sl,tl);i<ni;i++) {
  69         if (source.charAt(i) == target.charAt(i)) {
  70           cost++;
  71         }
  72       }
  73       return (float) cost/Math.max(sl, tl);
  74     }
  75
  76     char[] sa = new char[sl+n-1];
  77     float p[]; //'previous' cost array, horizontally
  78     float d[]; // cost array, horizontally
  79     float _d[]; //placeholder to assist in swapping p and d
  80
  81     //construct sa with prefix
  82     for (int i=0;i<sa.length;i++) {
  83       if (i < n-1) {
  84         sa[i]=0; //add prefix
  85       }
  86       else {
  87         sa[i] = source.charAt(i-n+1);
  88       }
  89     }
  90     p = new float[sl+1];
  91     d = new float[sl+1];
  92
  93     // indexes into strings s and t
  94     int i; // iterates through source
  95     int j; // iterates through target
  96
  97     char[] t_j = new char[n]; // jth n-gram of t
  98
  99     for (i = 0; i<=sl; i++) {
 100         p[i] = i;
 101     }
 102
 103     for (j = 1; j<=tl; j++) {
 104         //construct t_j n-gram
 105         if (j < n) {
 106           for (int ti=0;ti<n-j;ti++) {
 107             t_j[ti]=0; //add prefix
 108           }
 109           for (int ti=n-j;ti<n;ti++) {
 110             t_j[ti]=target.charAt(ti-(n-j));
 111           }
 112         }
 113         else {
 114           t_j = target.substring(j-n, j).toCharArray();
 115         }
 116         d[0] = j;
 117         for (i=1; i<=sl; i++) {
 118             cost = 0;
 119             int tn=n;
 120             //compare sa to t_j
 121             for (int ni=0;ni<n;ni++) {
 122               if (sa[i-1+ni] != t_j[ni]) {
 123                 cost++;
 124               }
 125               else if (sa[i-1+ni] == 0) { //discount matches on prefix
 126                 tn--;
 127               }
 128             }
 129             float ec = (float) cost/tn;
 130             // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
 131             d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1),  p[i-1]+ec);
 132         }
 133         // copy current distance counts to 'previous row' distance counts
 134         _d = p;
 135         p = d;
 136         d = _d;
 137     }
 138
 139     // our last action in the above loop was to switch d and p, so p now
 140     // actually has the most recent cost counts
 141     return 1.0f - (p[sl] / Math.max(tl, sl));
 142   }
 143
 144 }