1の距離をチェックするためにレベンショニング距離を最適化する方法は？

Question

私は、2つの単語の間に0または1の距離があるかどうかを確認し、そうであれば真を返すだけのゲームに取り組んでいます。

function levenshtein(s, t) { 
    if (s === t) { return 0; } 
    var n = s.length, m = t.length; 
    if (n === 0 || m === 0) { return n + m; } 
    var x = 0, y, a, b, c, d, g, h, k; 
    var p = new Array(n); 
    for (y = 0; y < n;) { p[y] = ++y; } 
    for (; 
    (x + 3) < m; x += 4) { 
    var e1 = t.charCodeAt(x); 
    var e2 = t.charCodeAt(x + 1); 
    var e3 = t.charCodeAt(x + 2); 
    var e4 = t.charCodeAt(x + 3); 
    c = x; b = x + 1; d = x + 2; g = x + 3; h = x + 4; 

    for (y = 0; y < n; y++) { 
     k = s.charCodeAt(y); 
     a = p[y]; 

     if (a < c || b < c) { c = (a > b ? b + 1 : a + 1); } 
     else { if (e1 !== k) { c++; } } 

     if (c < b || d < b) { b = (c > d ? d + 1 : c + 1); } 
     else { if (e2 !== k) { b++; } } 

     if (b < d || g < d) { d = (b > g ? g + 1 : b + 1); } 
     else { if (e3 !== k) { d++; } } 

     if (d < g || h < g) { g = (d > h ? h + 1 : d + 1); } 
     else { if (e4 !== k) { g++; } } 

     p[y] = h = g; g = d; d = b; b = c; c = a; 
    } 
    } 

    for (; x < m;) { 
    var e = t.charCodeAt(x); 
    c = x; 
    d = ++x; 
    for (y = 0; y < n; y++) { 
     a = p[y]; 
     if (a < c || d < c) { d = (a > d ? d + 1 : a + 1); } 
     else { 
     if (e !== s.charCodeAt(y)) { d = c + 1; } 
     else { d = c; } 
     } 
     p[y] = d; 
     c = a; 
    } 
    h = d; 
    } 

    return h; 
} 

動作しますが、このスポットはホットスポットになるだろうと私がいないため、2番目の潜在的に何百何千回ものを実行し、私はそれを最適化したいこと：私は、汎用のレーベンシュタイン距離アルゴリズムを発見しました汎用アルゴリズムを必要とし、0または1

の距離がある場合、私はそれを書いてみましたし、これを思いついチェックするだけで1：

function closeGuess(guess, word) { 
    if (Math.abs(word.length - guess.length) > 1) { return false; } 

    var errors = 0, guessIndex = 0, wordIndex = 0; 

    while (guessIndex < guess.length || wordIndex < word.length) { 
    if (errors > 1) { return false; } 
    if (guess[guessIndex] !== word[wordIndex]) { 
     if (guess.length < word.length) { wordIndex++; } 
     else { guessIndex++; } 
     errors++; 
    } else { 
     wordIndex++; 
     guessIndex++; 
    } 
    } 

    return true; 
} 

しかし、それをプロファイリングした後、私は私のコードがあることがわかりました2倍遅く、私は驚いたエネルナル目的アルゴリズムはO（n * m）であり、私はO（n）と考える。

私はこのフィドルにパフォーマンスの違いをテストしてきた：https://jsfiddle.net/aubtze2L/3/

は、私が使用できる任意のより良いアルゴリズムや私がより速くなるために私のコードを最適化することができます任意の方法はありますか？

Answer 1

forループ：

function lev01(a, b) { 
 
    let la = a.length; 
 
    let lb = b.length; 
 
    let d = 0; 
 
    switch (la - lb) { 
 
    case 0: // mutation 
 
     for (let i = 0; i < la; ++i) { 
 
     if (a.charAt(i) != b.charAt(i) && ++d > 1) { 
 
      return false; 
 
     } 
 
     } 
 
     return true; 
 
    case -1: // insertion 
 
     for (let i = 0; i < la + d; ++i) { 
 
     if (a.charAt(i - d) != b.charAt(i) && ++d > 1) { 
 
      return false; 
 
     } 
 
     } 
 
     return true; 
 
    case +1: // deletion 
 
     for (let i = 0; i < lb + d; ++i) { 
 
     if (a.charAt(i) != b.charAt(i - d) && ++d > 1) { 
 
      return false; 
 
     } 
 
     } 
 
     return true; 
 
    } 
 
    return false; 
 
} 
 

 
console.log(lev01("abc", "abc")); 
 
console.log(lev01("abc", "abd")); 
 
console.log(lev01("abc", "ab")); 
 
console.log(lev01("abc", "abcd")); 
 
console.log(lev01("abc", "cba"));

性能比較（クローム）：

• 80.33ms - lev01（この答え）
• 234.84ms - LEV
• 708.12ms - 私はフィドルを通して、あなたのコードを実行し、あなたが投稿しているだけで何

Answer 2

距離0と1を探していることがわかったら、汎用DPアルゴリズムは意味をなさない（そして、あなたが示したアルゴリズムが畳み込まれているように、より良い説明hereを見てください）。

距離が0であることを確認するには、2つの文字列が同じかどうかを確認するだけです。距離が1の場合は、挿入、削除、置換のいずれかが発生しているはずです。元の文字列から可能なすべての削除を生成し、2番目の文字列と等しいかどうかを確認します。したがって、次のようなものが得られます：

すべての文字のアルファベットを知る必要があります。大きな文字列として定義することができますvar alphabet = "abcde...."。今でも同様のことをしますが、置換や挿入を導入すると、アルファベットのすべての要素を繰り返し処理します。私はここにコード全体を書くつもりはない。

追加のものが2つあります。ここでは、多くのマイクロ最適化を行うことができます。例えば、2つの文字列の長さが1より大きい場合、それらは明らかに距離1を持つことができません。もう1つは、文字列の下にある文字の頻度に関連しています。

Answer 3

次のような場合を考慮してください

1. 用語の長さの差が1よりも大きい場合に長さの差がある場合、 それらの間のレーベンシュタイン距離は1
2. よりも大きくなりますちょうど1の場合、最短の文字列は最長の文字列と等しく、単一の削除（または挿入）が必要です。
3. 文字列が同じ長さであるなら、あなたは 2場合はfalse を返すハミング距離の修正版を検討し、異なる文字が発見されなければならない。ここで

が実装サンプルです：

var areSimilar; 

areSimilar = function(guess, word) { 
    var charIndex, foundDiff, guessLength, lengthDiff, substring, wordLength, shortest, longest, shortestLength, offset; 

    guessLength = guess.length; 
    wordLength = word.length; 

    lengthDiff = guessLength - wordLength; 
    if (lengthDiff < -1 || lengthDiff > 1) { 
    return false; 
    } 

    if (lengthDiff !== 0) { 
    if (guessLength < wordLength) { 
     shortest = guess; 
     longest = word; 
     shortestLength = guessLength; 
    } else { 
     shortest = word; 
     longest = guess; 
     shortestLength = wordLength; 
    } 

    offset = 0; 
    for (charIndex = 0; charIndex < shortestLength; charIndex += 1) { 
     if (shortest[charIndex] !== longest[offset + charIndex]) { 
     if (offset > 0) { 
      return false; // second error 
     } 
     offset = 1; 
     if (shortest[charIndex] !== longest[offset + charIndex]) { 
      return false; // second error 
     } 
     } 
    } 

    return true; // only one error 
    } 

    foundDiff = false; 
    for (charIndex = 0; charIndex < guessLength; charIndex += 1) { 
    if (guess[charIndex] !== word[charIndex]) { 
     if (foundDiff) { 
     return false; 
     } 
     foundDiff = true; 
    } 
    } 
    return true; 
}; 

私はこの方法を組み込むようにフィディルドを更新しました。ここに私のマシン上での結果は以下のとおりです。

close: 154.61 
lev: 176.72500000000002 
sim: 32.48000000000013 

フィドル：私は速く古き良きよりも、同時に、よりエレガントな方法が表示されていないhttps://jsfiddle.net/dylon/aubtze2L/11/