Jaki jest najszybszy algorytm algorytmu dla szerokiego zastosowania

Question

W przypadku narzędzia wyszukiwania po stronie klienta muszę znaleźć odległość Levenshteina słowa z milionami innych słów. Użytkownik powinien mieć możliwość porównania krótkiego tekstu około dwudziestu słów z książką. Użytkownik może to zrobić, znajdując lokalizacje najbardziej charakterystycznych słów tekstu w książce. "Szukanie lokalizacji" nie oznacza szukania dokładnego dopasowania, ale prawie identyczne jak z levenshtein. Zacząłem od już dostępnych wdrożeń, ale potrzebowałem większej prędkości. Skończyło się tak:

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; 
} 

Jak widać użyłem techniki jak umieszczenie obiektów z funkcji w celu ponownego ich używać. Powtórzyłem też trochę przez linearyzację pętli. Czy to może być szybciej? Jestem ciekaw twojej rady.

Aktualizacja: Po wskazówki od Bergi i trochę więcej myślenia doszedłem do tego rozwiązania:

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; 
    } 

To znowu znacznie szybciej. Nie mogę wycisnąć z tego więcej. Wciąż szukam innych pomysłów i spróbuję czegoś więcej.

Answer 1

Ponieważ jesteś porównując wobec tego samego słowa w kółko, można uzyskać niewielką poprawę wydajności przy użyciu częściowego stosowania i buforowanie tam:

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; 
    }; 
} 

ja również powtórzył sobie trochę przez linearizing pętlę nieco.

Nie jestem pewien, czy robi się dużo szybciej, ale można pominąć jednej z tablic - nie trzeba czytać/zapisywać je w sposób naprzemienny:

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; 
    }; 
} 

nie sądzę dalej optymalizacji można dokonać bez umieszczania miliona słów w dedykowanej strukturze danych (np. prefiks trie).