Damerau - Levenshtein Distance, добавив порог

Question

У меня есть следующая реализация, но я хочу добавить порог, поэтому, если результат будет больше, просто прекратите вычислять и возвращать.

Как я могу это сделать?

EDIT: Вот мой текущий код, threshold еще не используется ... цель состоит в том, что она используется

public static int DamerauLevenshteinDistance(string string1, string string2, int threshold) 
    { 
     // Return trivial case - where they are equal 
     if (string1.Equals(string2)) 
      return 0; 

     // Return trivial case - where one is empty 
     if (String.IsNullOrEmpty(string1) || String.IsNullOrEmpty(string2)) 
      return (string1 ?? "").Length + (string2 ?? "").Length; 


     // Ensure string2 (inner cycle) is longer 
     if (string1.Length > string2.Length) 
     { 
      var tmp = string1; 
      string1 = string2; 
      string2 = tmp; 
     } 

     // Return trivial case - where string1 is contained within string2 
     if (string2.Contains(string1)) 
      return string2.Length - string1.Length; 

     var length1 = string1.Length; 
     var length2 = string2.Length; 

     var d = new int[length1 + 1, length2 + 1]; 

     for (var i = 0; i <= d.GetUpperBound(0); i++) 
      d[i, 0] = i; 

     for (var i = 0; i <= d.GetUpperBound(1); i++) 
      d[0, i] = i; 

     for (var i = 1; i <= d.GetUpperBound(0); i++) 
     { 
      for (var j = 1; j <= d.GetUpperBound(1); j++) 
      { 
       var cost = string1[i - 1] == string2[j - 1] ? 0 : 1; 

       var del = d[i - 1, j] + 1; 
       var ins = d[i, j - 1] + 1; 
       var sub = d[i - 1, j - 1] + cost; 

       d[i, j] = Math.Min(del, Math.Min(ins, sub)); 

       if (i > 1 && j > 1 && string1[i - 1] == string2[j - 2] && string1[i - 2] == string2[j - 1]) 
        d[i, j] = Math.Min(d[i, j], d[i - 2, j - 2] + cost); 
      } 
     } 

     return d[d.GetUpperBound(0), d.GetUpperBound(1)]; 
    } 
} 

Answer 1

Наконец получил его ... хотя это не так выгодно, как я надеялся

public static int DamerauLevenshteinDistance(string string1, string string2, int threshold) 
    { 
     // Return trivial case - where they are equal 
     if (string1.Equals(string2)) 
      return 0; 

     // Return trivial case - where one is empty 
     if (String.IsNullOrEmpty(string1) || String.IsNullOrEmpty(string2)) 
      return (string1 ?? "").Length + (string2 ?? "").Length; 


     // Ensure string2 (inner cycle) is longer 
     if (string1.Length > string2.Length) 
     { 
      var tmp = string1; 
      string1 = string2; 
      string2 = tmp; 
     } 

     // Return trivial case - where string1 is contained within string2 
     if (string2.Contains(string1)) 
      return string2.Length - string1.Length; 

     var length1 = string1.Length; 
     var length2 = string2.Length; 

     var d = new int[length1 + 1, length2 + 1]; 

     for (var i = 0; i <= d.GetUpperBound(0); i++) 
      d[i, 0] = i; 

     for (var i = 0; i <= d.GetUpperBound(1); i++) 
      d[0, i] = i; 

     for (var i = 1; i <= d.GetUpperBound(0); i++) 
     { 
      var im1 = i - 1; 
      var im2 = i - 2; 
      var minDistance = threshold; 

      for (var j = 1; j <= d.GetUpperBound(1); j++) 
      { 
       var jm1 = j - 1; 
       var jm2 = j - 2; 
       var cost = string1[im1] == string2[jm1] ? 0 : 1; 

       var del = d[im1, j] + 1; 
       var ins = d[i, jm1] + 1; 
       var sub = d[im1, jm1] + cost; 

       //Math.Min is slower than native code 
       //d[i, j] = Math.Min(del, Math.Min(ins, sub)); 
       d[i, j] = del <= ins && del <= sub ? del : ins <= sub ? ins : sub; 

       if (i > 1 && j > 1 && string1[im1] == string2[jm2] && string1[im2] == string2[jm1]) 
        d[i, j] = Math.Min(d[i, j], d[im2, jm2] + cost); 

       if (d[i, j] < minDistance) 
        minDistance = d[i, j]; 
      } 

      if (minDistance > threshold) 
       return int.MaxValue; 
     } 

     return d[d.GetUpperBound(0), d.GetUpperBound(1)] > threshold 
      ? int.MaxValue 
      : d[d.GetUpperBound(0), d.GetUpperBound(1)]; 
    } 

Answer 2

Вот самый элегантный способ, которым я могу думать. После установки каждого индекса d проверьте, превышает ли он ваш порог. Оценка постоянная время, так что это капля в море по сравнению с теоретическими N^2 сложностей общего алгоритма:

public static int DamerauLevenshteinDistance(string string1, string string2, int threshold) 
{ 
    ... 

    for (var i = 1; i <= d.GetUpperBound(0); i++) 
    { 
     for (var j = 1; j <= d.GetUpperBound(1); j++) 
     { 
      ... 

      var temp = d[i,j] = Math.Min(del, Math.Min(ins, sub)); 

      if (i > 1 && j > 1 && string1[i - 1] == string2[j - 2] && string1[i - 2] == string2[j - 1]) 
       temp = d[i,j] = Math.Min(temp, d[i - 2, j - 2] + cost); 

      //Does this value exceed your threshold? if so, get out now 
      if(temp > threshold) 
       return temp; 
     } 
    } 

    return d[d.GetUpperBound(0), d.GetUpperBound(1)]; 
} 

Answer 3

вы также спрашивали об этом, как вопрос SQL CLR UDF, так что я буду отвечать в данном конкретном контексте: вы лучше optmiziation не будет исходить от оптимизации расстояния Левенштейна, но от уменьшения числа пар вы сравните. Да, более быстрый алгоритм Левенштейна улучшит ситуацию, но не так сильно, как уменьшение числа сравнений с N квадратом (с N в миллионах строк) до N *. Мое предложение состоит в том, чтобы сравнивать только те элементы, у которых разница длин в допустимой дельте. На большом столе, добавьте сохраненный вычисляемый столбец на LEN(Data), а затем создать индекс на нем включают данные:

ALTER TABLE Table ADD LenData AS LEN(Data) PERSISTED; 
CREATE INDEX ndxTableLenData on Table(LenData) INCLUDE (Data); 

Теперь вы можете ограничить истинное пространство проблемы пути объединения в пределах максимальной разницы в длине (например. скажем, 5), если ваши данные LEN(Data) значительно меняются:

SELECT a.Data, b.Data, dbo.Levenshtein(a.Data, b.Data) 
FROM Table A 
JOIN Table B ON B.DataLen BETWEEN A.DataLen - 5 AND A.DataLen+5 

Answer 4

Это Что касается ур ответа это: Damerau - Levenshtein Distance, adding a threshold (извините, не может комментировать, как у меня нет 50 респа еще)

Я думаю, вы сделали ошибку здесь. Вы инициализирован:

var minDistance = threshold; 

И ур правило обновления:

if (d[i, j] < minDistance) 
    minDistance = d[i, j]; 

Кроме того, ур ранние критерии выхода является:

if (minDistance > threshold) 
    return int.MaxValue; 

Теперь заметим, что если условие выше никогда не верны ! Вы должны скорее инициализировать minDistance до int.MaxValue