← Back to branch summary

~slub.team/goobi-indexserver/3.x

« back to all changes in this revision

Viewing changes to lucene/contrib/spellchecker/src/java/org/apache/lucene/search/spell/NGramDistance.java

  • Committer: Sebastian Meyer
  • Date: 2012-08-03 09:12:40 UTC
  • Revision ID: sebastian.meyer@slub-dresden.de-20120803091240-x6861b0vabq1xror
https://launchpad.net/bugs/985487
Remove Lucene and Solr source code and add patches instead
Fix Bug #985487: Auto-suggestion for the search interface

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
 
}