1의 거리를 확인하기 위해 levenshtein 거리를 최적화하는 방법은 무엇입니까?

Question

저는 두 단어 사이에 0 또는 1의 거리가 있는지 확인하고 그럴 경우 참을 리턴 할 필요가있는 게임을하고 있습니다. 나는 범용 levenshtein 거리 알고리즘 발견 작동

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

을하지만,이 지점은 핫스팟으로 잠재적으로 수천 번 두 번째 수백을 실행할 것입니다 그리고 내가하지 않기 때문에이를 최적화 할 범용 알고리즘, 0의 거리 또는 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; 
} 

을하지만 프로파일 후 나는 내 코드는 것을 발견 두 번 느리게, 나는 놀랐다. 왜냐하면 나는 g eneral 목적 알고리즘은 O (n * m)이고 나는 내 것이 O (n)라고 생각한다.

나는이 바이올린의 성능 차이를 테스트했습니다 :

https://jsfiddle.net/aubtze2L/3/는 거기에 내가 사용할 수있는 더 나은 알고리즘이나 내가 더 빨리 내 코드를 최적화 할 수있는 방법을?

Answer 1

에 대한 루프 :

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 - 레프
• 708.12ms - 나는 바이올린을 통해 코드를 실행하고 게시 한 그냥 뭐

Answer 2

당신이 거리 0과 1을 찾고 있다면, 범용 DP 알고리즘은 이해가되지 않는다. (그리고 당신이 보여준 알고리즘이 복잡한 것처럼 보이는 방식으로, 더 좋은 설명 here을 보라).

거리가 0인지 확인하려면 2 개의 문자열이 동일한 지 확인해야합니다. 이제 거리가 1이면 삽입, 삭제 또는 대체가 발생했음을 의미합니다. 따라서 원래 문자열에서 가능한 모든 삭제를 생성하고 두 번째 문자열과 같은지 확인하십시오. 이렇게하면 다음과 같은 것을 얻을 수 있습니다 :

삽입 및 대체를 위해서는 모든 문자의 알파벳을 알아야합니다. 큰 문자열 var alphabet = "abcde...."으로 정의 할 수 있습니다. 이제는 비슷한 일을하지만 대체 또는 삽입을 도입하면 알파벳의 모든 요소를 ​​반복합니다. 여기에 전체 코드를 작성할 계획이 아닙니다.

몇 가지 추가 사항이 있습니다. 여기에 많은 마이크로 최적화를 만들 수 있습니다. 예를 들어, 두 문자열의 길이가 1보다 다른 경우에는 거리가 1이 될 수 없습니다. 또 하나는 문자열의 기본 문자 빈도와 관련이 있습니다.

Answer 3

는 다음과 같은 경우 고려 : 용어의 길이의 차이는 다음 1보다 큰 경우

1. 을 길이의 차이 인 경우 1보다 큰
2. 될 것입니다 그들 사이의 Levenshtein 거리 정확히 1이면 가장 짧은 문자열은 가장 긴 문자열과 같아야하며 하나의 삭제 (또는 삽입)가 있어야합니다.문자열이 같은 길이 인 경우
가
3. 다음 이 경우는 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/