उच्च लगातार उपयोग के लिए सबसे तेज़ लेवेनशेटिन एल्गोरिदम क्या है

Question

क्लाइंट साइड सर्च टूल के लिए मुझे लाखों अन्य शब्दों वाले शब्द के लेवेनशेटिन दूरी की आवश्यकता है। एक उपयोगकर्ता को पुस्तक के साथ लगभग बीस शब्दों के एक छोटे से पाठ की तुलना करने में सक्षम होना चाहिए। उपयोगकर्ता पुस्तक में पाठ के सबसे विशिष्ट शब्दों के स्थानों को ढूंढकर ऐसा कर सकता है। 'स्थानों को ढूंढना मतलब सटीक मिलान की तलाश में नहीं है बल्कि लगभग लेवेनशेटिन के साथ मिलते हैं। मैंने पहले ही उपलब्ध कार्यान्वयन के साथ शुरुआत की लेकिन मुझे और गति की आवश्यकता थी। मैं इस के साथ समाप्त हो गया:

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

मैं भी अपने आप को थोड़ा पाश linearizing द्वारा बार-बार कुछ हद तक।

सुनिश्चित नहीं हूं कि यह बहुत तेजी से हो जाता है, लेकिन आप सरणियों में से एक को छोड़ सकते हैं - आप को पढ़ने के लिए/उन्हें एक बारी ढंग से लिखने की जरूरत नहीं है:

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

मैं आगे नहीं लगता कि आपके लाखों शब्दों को एक समर्पित डेटा संरचना (उदाहरण के लिए एक उपसर्ग त्रिभुज) में डाले बिना ऑप्टिमाइज़ेशन किए जा सकते हैं।