Qual è l'algoritmo di levenshtein più veloce per l'uso frequente e frequente

Question

Per uno strumento di ricerca lato client ho bisogno di trovare la distanza Levenshtein di una parola con milioni di altre parole. Un utente dovrebbe essere in grado di confrontare un breve testo di circa venti parole con un libro. L'utente può farlo trovando le posizioni delle parole più caratterizzanti del testo nel libro. "Trovare luoghi" non significa cercare una corrispondenza esatta, ma quasi coincidere con levenshtein. Ho iniziato con le implementazioni già disponibili ma avevo bisogno di più velocità. Ho finito con questo:

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

Come vedi ho usato le tecniche di come mettere gli oggetti fuori della funzione, al fine di ri usarli. Mi sono anche ripetuto un po 'linearizzando il loop in qualche modo. Potrebbe essere più veloce? Sono curioso del tuo consiglio.

Aggiornamento: Dopo suggerimenti da Bergi e ancora un po 'il pensiero mi è venuto a questa soluzione:

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

Anche questo è molto più veloce. Non riesco a spremere di più. Continuo a cercare altre idee e proverò ancora.

Answer 1

Dal momento che si sta confrontando contro la stessa parola più e più volte, è possibile ottenere un po 'di miglioramento delle prestazioni utilizzando l'applicazione parziale e la cache non:

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

Mi sono anche ripetuto un po' dalla linearizzazione del ciclo un po '.

Non è sicuro se si arriva molto più veloce, ma è possibile omettere una delle matrici - non c'è bisogno di leggere/scrivere loro in modo alternato:

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

Non credo più le ottimizzazioni possono essere fatte senza mettere milioni di parole in una struttura dati dedicata (ad es. un prefisso trie).