levenshtein расстояние для индексированного словаря

Question

У меня в настоящее время возникают проблемы с нечеткой строкой, которую я реализовал. Я хочу иметь возможность быстро определить менее чем за одну секунду, какие фразы из списка из 10 000 фраз имеют расстояние редактирования 2 или менее до любой из 200 000 фраз в словаре, используя Javascript. Фразы в среднем около 15 символов. Меня не волнует, сколько матчей есть, или даже, что такое матч, просто ли матч или нет. Я могу сделать любую индексацию перед рукой по словам в словаре, который хотел бы, но ни один из других слов.

Мой главный подход - использовать дерево BK. Для классификации всех 10 000 слов обычно требуется около 130-140 секунд, поэтому примерно на два порядка ниже, чем я надеюсь. Является ли реалистичным возможность классифицировать фразы, которые быстро появляются в Javascript? Если да, то какие методы я должен использовать, есть ли более быстрый метод, чем деревья BK, которые используются для таких проблем?

Answer 1

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

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