Modyfikowanie algorytmu Levenshtein Distance, aby nie obliczyć wszystkich odległości

Question

Pracuję nad implementacją wyszukiwania rozmytego i jako część implementacji używamy StringUtils.getLevenshteinDistance Apache. W tej chwili szukamy konkretnego maksymalnego średniego czasu odpowiedzi dla naszego wyszukiwania rozmytego. Po różnych ulepszeniach i pewnym profilowaniu miejscem, w którym spędza się najwięcej czasu, jest obliczenie odległości Levenshteina. Zajmuje około 80-90% całkowitego czasu wyszukiwania trzech liter lub więcej.

Wiem, że są pewne ograniczenia co do tego, co można tutaj zrobić, ale czytałem na poprzednich pytaniach SO i na linku do Wikipedii dla LD, że jeśli ktoś chce ograniczyć próg do ustalonej maksymalnej odległości, to może pomóc w ograniczeniu czasu spędzonego na algorytmie, ale nie jestem pewien, jak to zrobić dokładnie.

Jeśli jesteśmy zainteresowani tylko w odległości do jeżeli jest ona mniejsza niż progowej k, to wystarczy obliczyć przekątnej paskiem o szerokości 2k + 1 w matrycy. W ten sposób algorytm może być uruchamiany w czasie O (kl), , gdzie l jest długością najkrótszego ciągu . [3]

Poniżej zostanie wyświetlony oryginalny kod LH z StringUtils. Po tym jest moja modyfikacja. Próbuję w zasadzie obliczyć odległości o zadanej długości od przekątnej i, j (tak, w moim przykładzie, dwie przekątne powyżej i poniżej przekątnej i, j). Jednak nie może to być poprawne, tak jak to zrobiłem. Na przykład na najwyższej przekątnej zawsze wybierze wartość komórki bezpośrednio powyżej, która będzie wynosić 0. Jeśli ktoś mógłby mi pokazać, jak sprawić, by działało to tak, jak opisałem, lub ogólną radę, jak to zmienić , byłoby to bardzo docenione.

public static int getLevenshteinDistance(String s, String t) { 
     if (s == null || t == null) { 
      throw new IllegalArgumentException("Strings must not be null"); 
     } 

     int n = s.length(); // length of s 
     int m = t.length(); // length of t 

     if (n == 0) { 
      return m; 
     } else if (m == 0) { 
      return n; 
     } 

     if (n > m) { 
      // swap the input strings to consume less memory 
      String tmp = s; 
      s = t; 
      t = tmp; 
      n = m; 
      m = t.length(); 
     } 

     int p[] = new int[n+1]; //'previous' cost array, horizontally 
     int d[] = new int[n+1]; // cost array, horizontally 
     int _d[]; //placeholder to assist in swapping p and d 

     // indexes into strings s and t 
     int i; // iterates through s 
     int j; // iterates through t 

     char t_j; // jth character of t 

     int cost; // cost 

     for (i = 0; i<=n; i++) { 
      p[i] = i; 
     } 

     for (j = 1; j<=m; j++) { 
      t_j = t.charAt(j-1); 
      d[0] = j; 

      for (i=1; i<=n; i++) { 
       cost = s.charAt(i-1)==t_j ? 0 : 1; 
       // minimum of cell to the left+1, to the top+1, diagonally left and up +cost 
       d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1), p[i-1]+cost); 
      } 

      // copy current distance counts to 'previous row' distance counts 
      _d = p; 
      p = d; 
      d = _d; 
     } 

     // our last action in the above loop was to switch d and p, so p now 
     // actually has the most recent cost counts 
     return p[n]; 
    } 

Moje modyfikacje (tylko do pętli):

for (j = 1; j<=m; j++) { 
     t_j = t.charAt(j-1); 
     d[0] = j; 

     int k = Math.max(j-2, 1); 
     for (i = k; i <= Math.min(j+2, n); i++) { 
      cost = s.charAt(i-1)==t_j ? 0 : 1; 
      // minimum of cell to the left+1, to the top+1, diagonally left and up +cost 
      d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1), p[i-1]+cost); 
     } 

     // copy current distance counts to 'previous row' distance counts 
     _d = p; 
     p = d; 
     d = _d; 
    } 

Answer 1

Problem z zaimplementowaniem okna dotyczy wartości po lewej stronie pierwszego wpisu i powyżej ostatniego wpisu w każdym wierszu.

Jednym ze sposobów jest rozpoczęcie wartości, które początkowo wypełniasz 1 zamiast 0, a następnie zignoruj ​​wszystkie napotkane 0. Musisz odjąć 1 od ostatecznej odpowiedzi.

Innym sposobem jest wypełnienie wpisów po lewej i po lewej stronie wartościami najwyższymi, więc kontrola minimalna nigdy ich nie wybierze. W ten sposób wybrałem kiedy musiałem wdrożyć go na drugi dzień:

public static int levenshtein(String s, String t, int threshold) { 
    int slen = s.length(); 
    int tlen = t.length(); 

    // swap so the smaller string is t; this reduces the memory usage 
    // of our buffers 
    if(tlen > slen) { 
     String stmp = s; 
     s = t; 
     t = stmp; 
     int itmp = slen; 
     slen = tlen; 
     tlen = itmp; 
    } 

    // p is the previous and d is the current distance array; dtmp is used in swaps 
    int[] p = new int[tlen + 1]; 
    int[] d = new int[tlen + 1]; 
    int[] dtmp; 

    // the values necessary for our threshold are written; the ones after 
    // must be filled with large integers since the tailing member of the threshold 
    // window in the bottom array will run min across them 
    int n = 0; 
    for(; n < Math.min(p.length, threshold + 1); ++n) 
     p[n] = n; 
    Arrays.fill(p, n, p.length, Integer.MAX_VALUE); 
    Arrays.fill(d, Integer.MAX_VALUE); 

    // this is the core of the Levenshtein edit distance algorithm 
    // instead of actually building the matrix, two arrays are swapped back and forth 
    // the threshold limits the amount of entries that need to be computed if we're 
    // looking for a match within a set distance 
    for(int row = 1; row < s.length()+1; ++row) { 
     char schar = s.charAt(row-1); 
     d[0] = row; 

     // set up our threshold window 
     int min = Math.max(1, row - threshold); 
     int max = Math.min(d.length, row + threshold + 1); 

     // since we're reusing arrays, we need to be sure to wipe the value left of the 
     // starting index; we don't have to worry about the value above the ending index 
     // as the arrays were initially filled with large integers and we progress to the right 
     if(min > 1) 
      d[min-1] = Integer.MAX_VALUE; 

     for(int col = min; col < max; ++col) { 
      if(schar == t.charAt(col-1)) 
       d[col] = p[col-1]; 
      else 
       // min of: diagonal, left, up 
       d[col] = Math.min(p[col-1], Math.min(d[col-1], p[col])) + 1; 
     } 
     // swap our arrays 
     dtmp = p; 
     p = d; 
     d = dtmp; 
    } 

     if(p[tlen] == Integer.MAX_VALUE) 
      return -1; 
    return p[tlen]; 
} 

Answer 2

Pisałem o Levenshteina automatów, które są jednym ze sposobów, aby zrobić ten rodzaj czeku w O (n) czas wcześniej, here. Próbki kodu źródłowego są w języku Python, ale wyjaśnienia powinny być pomocne, a referowane dokumenty dostarczają więcej szczegółów.

Answer 3

Here ktoś odpowiada na bardzo podobne pytanie:

wymienić:
Robiłem to wiele razy. Sposób, w jaki to robię, polega na rekursywnym pierwszym przejściu drzewa gry z możliwych zmian. Jest budżet k zmian, których używam do przycinania drzewa. Z tą rutyną w ręku najpierw uruchamiam ją z k = 0, potem k = 1, potem k = 2, aż dostaję uderzenie, albo nie chcę iść wyżej.

char* a = /* string 1 */; 
char* b = /* string 2 */; 
int na = strlen(a); 
int nb = strlen(b); 
bool walk(int ia, int ib, int k){ 
    /* if the budget is exhausted, prune the search */ 
    if (k < 0) return false; 
    /* if at end of both strings we have a match */ 
    if (ia == na && ib == nb) return true; 
    /* if the first characters match, continue walking with no reduction in budget */ 
    if (ia < na && ib < nb && a[ia] == b[ib] && walk(ia+1, ib+1, k)) return true; 
    /* if the first characters don't match, assume there is a 1-character replacement */ 
    if (ia < na && ib < nb && a[ia] != b[ib] && walk(ia+1, ib+1, k-1)) return true; 
    /* try assuming there is an extra character in a */ 
    if (ia < na && walk(ia+1, ib, k-1)) return true; 
    /* try assuming there is an extra character in b */ 
    if (ib < nb && walk(ia, ib+1, k-1)) return true; 
    /* if none of those worked, I give up */ 
    return false; 
} 

tylko główną część, więcej kodu w oryginalnym

Answer 4

użyłem oryginalnego kodu i umieszcza ten tuż przed końcem j pętli for:

if (p[n] > s.length() + 5) 
     break; 

Znak + 5 jest dowolne, ale dla naszych celów, jeśli odległości to długość zapytania plus pięć (lub jakakolwiek liczba, na którą się zdecydujemy), to nie ma znaczenia, co zostanie zwrócone, ponieważ uważamy, że mecz jest po prostu zbyt odmienny. Trochę to ogranicza.Mimo to, na pewno nie jest to idea, o której mówiło oświadczenie Wiki, jeśli ktokolwiek lepiej to rozumie.

Answer 5

Zgodnie z "Gusfield, Dan (1997) Algorytmy dotyczące łańcuchów, drzew i sekwencji: informatyka i biologia obliczeniowa" (strona 264) należy ignorować zera.

Answer 6

Apache Commons Lang 3.4 ma ten realizacji:

/** 
* <p>Find the Levenshtein distance between two Strings if it's less than or equal to a given 
* threshold.</p> 
* 
* <p>This is the number of changes needed to change one String into 
* another, where each change is a single character modification (deletion, 
* insertion or substitution).</p> 
* 
* <p>This implementation follows from Algorithms on Strings, Trees and Sequences by Dan Gusfield 
* and Chas Emerick's implementation of the Levenshtein distance algorithm from 
* <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a></p> 
* 
* <pre> 
* StringUtils.getLevenshteinDistance(null, *, *)    = IllegalArgumentException 
* StringUtils.getLevenshteinDistance(*, null, *)    = IllegalArgumentException 
* StringUtils.getLevenshteinDistance(*, *, -1)    = IllegalArgumentException 
* StringUtils.getLevenshteinDistance("","", 0)    = 0 
* StringUtils.getLevenshteinDistance("aaapppp", "", 8)  = 7 
* StringUtils.getLevenshteinDistance("aaapppp", "", 7)  = 7 
* StringUtils.getLevenshteinDistance("aaapppp", "", 6))  = -1 
* StringUtils.getLevenshteinDistance("elephant", "hippo", 7) = 7 
* StringUtils.getLevenshteinDistance("elephant", "hippo", 6) = -1 
* StringUtils.getLevenshteinDistance("hippo", "elephant", 7) = 7 
* StringUtils.getLevenshteinDistance("hippo", "elephant", 6) = -1 
* </pre> 
* 
* @param s the first String, must not be null 
* @param t the second String, must not be null 
* @param threshold the target threshold, must not be negative 
* @return result distance, or {@code -1} if the distance would be greater than the threshold 
* @throws IllegalArgumentException if either String input {@code null} or negative threshold 
*/ 
public static int getLevenshteinDistance(CharSequence s, CharSequence t, final int threshold) { 
    if (s == null || t == null) { 
     throw new IllegalArgumentException("Strings must not be null"); 
    } 
    if (threshold < 0) { 
     throw new IllegalArgumentException("Threshold must not be negative"); 
    } 

    /* 
    This implementation only computes the distance if it's less than or equal to the 
    threshold value, returning -1 if it's greater. The advantage is performance: unbounded 
    distance is O(nm), but a bound of k allows us to reduce it to O(km) time by only 
    computing a diagonal stripe of width 2k + 1 of the cost table. 
    It is also possible to use this to compute the unbounded Levenshtein distance by starting 
    the threshold at 1 and doubling each time until the distance is found; this is O(dm), where 
    d is the distance. 

    One subtlety comes from needing to ignore entries on the border of our stripe 
    eg. 
    p[] = |#|#|#|* 
    d[] = *|#|#|#| 
    We must ignore the entry to the left of the leftmost member 
    We must ignore the entry above the rightmost member 

    Another subtlety comes from our stripe running off the matrix if the strings aren't 
    of the same size. Since string s is always swapped to be the shorter of the two, 
    the stripe will always run off to the upper right instead of the lower left of the matrix. 

    As a concrete example, suppose s is of length 5, t is of length 7, and our threshold is 1. 
    In this case we're going to walk a stripe of length 3. The matrix would look like so: 

     1 2 3 4 5 
    1 |#|#| | | | 
    2 |#|#|#| | | 
    3 | |#|#|#| | 
    4 | | |#|#|#| 
    5 | | | |#|#| 
    6 | | | | |#| 
    7 | | | | | | 

    Note how the stripe leads off the table as there is no possible way to turn a string of length 5 
    into one of length 7 in edit distance of 1. 

    Additionally, this implementation decreases memory usage by using two 
    single-dimensional arrays and swapping them back and forth instead of allocating 
    an entire n by m matrix. This requires a few minor changes, such as immediately returning 
    when it's detected that the stripe has run off the matrix and initially filling the arrays with 
    large values so that entries we don't compute are ignored. 

    See Algorithms on Strings, Trees and Sequences by Dan Gusfield for some discussion. 
    */ 

    int n = s.length(); // length of s 
    int m = t.length(); // length of t 

    // if one string is empty, the edit distance is necessarily the length of the other 
    if (n == 0) { 
     return m <= threshold ? m : -1; 
    } else if (m == 0) { 
     return n <= threshold ? n : -1; 
    } 

    if (n > m) { 
     // swap the two strings to consume less memory 
     final CharSequence tmp = s; 
     s = t; 
     t = tmp; 
     n = m; 
     m = t.length(); 
    } 

    int p[] = new int[n + 1]; // 'previous' cost array, horizontally 
    int d[] = new int[n + 1]; // cost array, horizontally 
    int _d[]; // placeholder to assist in swapping p and d 

    // fill in starting table values 
    final int boundary = Math.min(n, threshold) + 1; 
    for (int i = 0; i < boundary; i++) { 
     p[i] = i; 
    } 
    // these fills ensure that the value above the rightmost entry of our 
    // stripe will be ignored in following loop iterations 
    Arrays.fill(p, boundary, p.length, Integer.MAX_VALUE); 
    Arrays.fill(d, Integer.MAX_VALUE); 

    // iterates through t 
    for (int j = 1; j <= m; j++) { 
     final char t_j = t.charAt(j - 1); // jth character of t 
     d[0] = j; 

     // compute stripe indices, constrain to array size 
     final int min = Math.max(1, j - threshold); 
     final int max = (j > Integer.MAX_VALUE - threshold) ? n : Math.min(n, j + threshold); 

     // the stripe may lead off of the table if s and t are of different sizes 
     if (min > max) { 
      return -1; 
     } 

     // ignore entry left of leftmost 
     if (min > 1) { 
      d[min - 1] = Integer.MAX_VALUE; 
     } 

     // iterates through [min, max] in s 
     for (int i = min; i <= max; i++) { 
      if (s.charAt(i - 1) == t_j) { 
       // diagonally left and up 
       d[i] = p[i - 1]; 
      } else { 
       // 1 + minimum of cell to the left, to the top, diagonally left and up 
       d[i] = 1 + Math.min(Math.min(d[i - 1], p[i]), p[i - 1]); 
      } 
     } 

     // copy current distance counts to 'previous row' distance counts 
     _d = p; 
     p = d; 
     d = _d; 
    } 

    // if p[n] is greater than the threshold, there's no guarantee on it being the correct 
    // distance 
    if (p[n] <= threshold) { 
     return p[n]; 
    } 
    return -1; 
}