什麼是高頻率使用最快的levenshtein算法

Question

對於客戶端搜索工具，我需要找到包含數百萬其他詞彙的單詞的Levenshtein距離。用戶應該能夠將約20個詞的短文與書進行比較。用戶可以通過查找書中文本中最具特色的單詞的位置來完成此操作。 「尋找地點」並不意味着尋找精確的匹配，而是與levenshtein幾乎匹配。我從已經可用的實現開始，但我需要更多的速度。我結束了這個：

var rowA = new Uint16Array(1e6); 
var rowB = new Uint16Array(1e6); 
function levenshtein(s1, s2) { 
    var s1_len = s1.length, s2_len = s2.length, i1, i2 = 0, a, b, c, c2, i = 0; 
    if (s1_len === 0) 
     return s2_len; 
    if (s2_len === 0) 
     return s1_len; 
    while (i < s1_len) 
     rowA[i] = ++i; 
    while (i2 < s2_len) { 
     c2 = s2[i2]; 
     a = i2; 
     ++i2; 
     b = i2; 
     for (i1 = 0; i1 < s1_len; ++i1) { 
      c = a + (s1[i1] !== c2); 
      a = rowA[i1]; 
      b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c); 
      rowB[i1] = b; 
     } 
     if (i2 === s2_len) 
      return b; 
     c2 = s2[i2]; 
     a = i2; 
     ++i2; 
     b = i2; 
     for (i1 = 0; i1 < s1_len; ++i1) { 
      c = a + (s1[i1] !== c2); 
      a = rowB[i1]; 
      b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c); 
      rowA[i1] = b; 
     } 
    } 
    return b; 
} 

正如你所看到的我使用的技術，如放置對象的功能，以便重新使用它們。我也稍微重複了一點線性化循環。它會更快嗎？我很好奇你的建議。

更新： 後從BERGI技巧和一些更多的思考我來到這個解決方案：

var row = new Uint16Array(1e6); 
    function levenshtein(s1, s2) { 
     var s1_len = s1.length, s2_len = s2.length, i2 = 1, a, b = 0, c, c2, i1 = 0; 
     if (s1_len === 0) 
      return s2_len; 
     if (s2_len === 0) 
      return s1_len; 
     c2 = s2[0]; 
     if (s1[0] === c2) { 
      while (i1 < s1_len) { 
       row[i1] = i1++; 
      } 
      b = s1_len - 1; 
     } else { 
      row[0] = 1; 
      ++b; 
      if (s1_len > 1) 
       for (i1 = 1; i1 < s1_len; ++i1) { 
        if (s1[i1] === c2) { 
         row[i1] = b; 
         for (++i1; i1 < s1_len; ++i1) { 
          row[i1] = ++b; 
         } 
        } else { 
         row[i1] = ++b; 
        } 
       } 
     } 
     if (s2_len > 1) 
      while (i2 < s2_len) { 
       c2 = s2[i2]; 
       c = i2 + (s1[0] !== c2); 
       a = row[0]; 
       ++i2; 
       b = i2 < a ? (i2 < c ? i2 + 1 : c) : (a < c ? a + 1 : c); 
       row[0] = b; 
       if (s1_len > 1) { 
        for (i1 = 1; i1 < s1_len; ++i1) { 
         c = a + (s1[i1] !== c2); 
         a = row[i1]; 
         b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c); 
         row[i1] = b; 
        } 
       } 
      } 
     return b; 
    } 

這又是要快得多。我無法從中擠出更多。我一直在尋找其他想法，並會嘗試更多。

Answer 1

因爲你是對同一個詞一遍又一遍的比較，您可以通過使用部分應用程序和緩存那裏得到一點點的性能提升：

function levenshtein(s1) { 
    var row0 = [], row1 = [], s1_len = s1.length; 
    if (s1_len === 0) 
     return function(s2) { 
      return s2.length; 
     }; 
    return function(s2) { 
     var s2_len = s2.length, s1_idx, s2_idx = 0, a, b, c, c2, i = 0; 
     if (s2_len === 0) 
      return s1_len; 
     … 
     return b; 
    }; 
} 

我也重複自己被線性化環位有些。

不能確定它是否得到快了很多，但你可以省略陣列中的一個 - 你不需要讀/他們以交替的方式寫：

function levenshtein(s1) { 
    var s1_len = s1.length, row = new Array(s1_len); 
    if (s1_len === 0) 
     return function(s2) { 
      return s2.length; 
     }; 
    return function(s2) { 
     var s2_len = s2.length, s1_idx, s2_idx = 0, a, b, c, c2, i = 0; 
     if (s2_len === 0) 
      return s1_len; 
     while (i < s1_len) 
      row[i] = ++i; 
     while (s2_idx < s2_len) { 
      c2 = s2[s2_idx]; 
      a = s2_idx; 
      ++s2_idx; 
      b = s2_idx; 
      for (s1_idx = 0; s1_idx < s1_len; ++s1_idx) { 
       c = a + (s1[s1_idx] === c2 ? 0 : 1); 
       a = row[s1_idx]; 
       b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c); 
       row[s1_idx] = b; 
      } 
     } 
     return b; 
    }; 
} 

我不認爲進一步無需將數百萬個單詞放入專用數據結構（例如前綴特里結構）即可進行優化。