Thuật toán levenshtein nhanh nhất để sử dụng thường xuyên là gì

Question

Đối với một công cụ tìm kiếm phía khách hàng, tôi cần tìm khoảng cách Levenshtein của một từ với hàng triệu từ khác. Người dùng có thể so sánh văn bản ngắn khoảng hai mươi từ với một cuốn sách. Người dùng có thể thực hiện việc này bằng cách tìm vị trí của các từ có đặc trưng nhất của văn bản trong sách. 'Tìm vị trí không có nghĩa là tìm kiếm một kết hợp chính xác nhưng gần giống như với levenshtein. Tôi bắt đầu với việc triển khai sẵn có nhưng tôi cần tốc độ cao hơn. Tôi đã kết thúc với điều này:

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

Như bạn thấy tôi đã sử dụng các kỹ thuật như cách đặt các đối tượng ra khỏi chức năng để tái sử dụng chúng. Tôi cũng lặp lại một chút bằng cách tuyến tính hóa vòng lặp phần nào. Nó có thể nhanh hơn không? Tôi tò mò về lời khuyên của bạn.

Cập nhật: Sau lời khuyên từ Bergi và một số suy nghĩ nhiều hơn tôi đến giải pháp này:

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

Đây lại là nhanh hơn nhiều. Tôi không thể vắt kiệt thêm. Tôi tiếp tục tìm kiếm các ý tưởng khác và sẽ thử thêm một số ý tưởng khác.

Answer 1

Vì bạn đang so sánh với cùng một từ hơn và hơn, bạn có thể nhận được một sự cải thiện hiệu suất nhỏ bằng cách sử dụng ứng dụng một phần và bộ nhớ đệm có:

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

Tôi cũng lặp đi lặp lại bản thân mình một chút bởi linearizing vòng lặp phần nào.

Không chắc chắn cho dù nó được nhanh hơn rất nhiều, nhưng bạn có thể bỏ qua một trong những mảng - bạn không cần phải đọc/viết chúng một cách xen kẽ:

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

Tôi không nghĩ xa hơn tối ưu hóa có thể được thực hiện mà không cần đưa hàng triệu từ của bạn vào một cấu trúc dữ liệu chuyên dụng (ví dụ như một tiền tố trie).