알고리즘

Question

나는 (나의 응용 프로그램 기능) 놀라 울 정도로 좋은 x-webkit-speech를 사용하여 음성 제어 응용 프로그램을 만드는 오전 뒤에 이야기,하지만 때로는 사용자 (나) 조금 덜컹 거리다. 단어의 합리적인 일부가 적당한 명령의 합리적인 부분과 일치하면 명령을 받아들이는 것이 좋을 것입니다. 그래서 나는 이라는 성배를 찾으십시오. 단어 집합에서 단어의 가장 큰 교차점의 알고리즘은입니다. 신선한 밝은 정신으로 나를 절망의 동굴에서 빠져 나올 수 있을까요? 이 회전 (tat_o)와 가장 긴 교차을 가지고 있기 때문에

예

"rotation" in ["notable","tattoo","onclick","statistically"] 

문신 일치해야합니다. 통계적으로이 두 번째로 우수합니다 (tat 교차). 단어의 더 긴 부분을 무시해야하기 때문에 (보너스 조건이므로 아무런 문제없이 사용 가능합니다).

노트

• 나는 발음이
• 자바 스크립트 단련 시킨다면 언어의 서면 매우 가까운 체코 어를 사용하지만, 어떤 의사가 교차의
• 최소 길이 허용 알고리즘의 파라미터 여야합니다.

무엇을 시도 했습니까?

음, 꽤 embarassing하고 ....

for(var i=10; i>=4; --i) // reasonable substring 
for(var word in words) // for all words in the set 
for(var j=0; j<word.length-i; ++j) // search for any i substring 
// aaargh... three levels of abstraction is too much for me 

Answer 1

이 작동하는 것 같다 알고리즘이입니다. 나는 그것이 (내가 더 악화 수행 의심) 다른 이미 확립 된 알고리즘에 비해 수행하는 방법을 잘 몰라하지만 어쩌면 그것은 당신에게 당신이 그것을 할 수있는 방법을 생각 제공 :

FIDDLE

var minInt = 3; 
var arr = ["notable","tattoo","onclick","statistically"]; 
var word = "rotation"; 

var res = []; 
if (word.length >= minInt) { 
    for (var i = 0; i < arr.length; i++) { 
     var comp = arr[i]; 
     var m = 0; 
     if (comp.length >= minInt) { 
      for (var l = 0; l < comp.length - minInt + word.length - minInt + 1; l++) { 
       var subcomp = l > word.length - minInt ? comp.substring(l - word.length + minInt) : comp; 
       var subword = l < word.length - minInt ? word.substring(word.length - minInt - l) : word; 
       var minL = Math.min(subcomp.length, subword.length); 
       var matches = 0; 
       for (var k = 0; k < minL; k++) { 
        if (subcomp[k] === subword[k]) { 
         matches++; 
        } 
       } 
       if (matches > m) { 
        m = matches; 
       } 
      } 
     } 
     res[i] = m >= minInt ? m : null; 
    } 
} 

console.log(res); 

은 어떻게됩니까을 그것은 두 문자열을 다른 것에 대해 "움직여"비교하여 각 위치에서 일치하는 문자를 계산한다는 것입니다. 다음은 rotation vs. notable의 비교 "하위"단어를 참조하십시오

ion/notable --> one match on index 1 
tion/notable --> no match 
ation/notable --> no match 
tation/notable --> one match on index 2 
otation/notable --> no match 
rotation/notable --> three matches on index 1,2,3 
rotation/otable --> no match 
rotation/table --> no match 
rotation/able --> no match 
rotation/ble --> no match 

를 보시다시피, 경기의 최대 수는 3이고 그게 반환 것입니다.

Answer 2

다음은 Levenshtein Distance Calculator를 자바 스크립트로 구현 한 것입니다.

일치하는 명령과 거리가 포함 된 개체를 반환합니다.

var commandArr = ["cat", "dog", "fish", "copy", "delete"] 
var testCommand = "bopy"; 

function closestMatch(str, arr) 
{ 
    //console.log("match called"); 
    var matchDist = []; 
    var min, pos; 
    for(var i=0; i<arr.length; i++) 
    { 
     matchDist[i]=calcLevDist(str, arr[i]); 
     console.log("Testing "+ str + " against " + arr[i]); 
    } 
    //http://stackoverflow.com/questions/5442109/how-to-get-the-min-elements-inside-an-array-in-javascript 
    min = Math.min.apply(null,matchDist); 
    pos = matchDist.indexOf(min); 

    var output = { match : arr[pos], 
        distance : matchDist[pos] 
       }; 

    return output; 
} 

function calcLevDist (str1, str2) 
{ 
    //console.log("calc running"); 

    var cost = 0 , len1, len2; 
    var x = 1; 
    while(x > 0) 
    { 
     len1 = str1.length; 
     console.log("Length of String 1 = " + len1); 
     len2 = str2.length; 
     console.log("Length of String 2 = " + len2); 

     if(len1 == 0) 
     { 
      cost+= len2; 
      return cost; 
     } 
     if(len2 == 0) 
     {  
      cost+= len1; 
      return cost; 
     } 
     x = Math.min(len1,len2); 

     if(str1.charAt(len1 -1) != str2.charAt(len2 -1)) 
     { 
      cost++; 
     } 
     else 
      console.log(str1.charAt(len1-1) + " matches " + str2.charAt(len2-1)); 

     str1 = str1.substring(0, len1 -1); 
     str2 = str2.substring(0, len2 -1); 


     console.log("Current Cost = " + cost); 
    } 


} 

var matchObj = closestMatch(testCommand, commandArr); 
var match = matchObj["match"]; 
var dist = matchObj["distance"]; 

$("#result").html("Closest match to " + testCommand + " = " + match + " with a Lev Distance of " + dist + ".") 

당신은 바이올린 here와 주변 엉망 수 있습니다.

Answer 3

감사합니다. basilikum과 JasonNichols, 그리고 Mike와 Andrew도 의견을 보내 주셔서 감사합니다. 알고리즘을 완료하는 데 정말로 도움이되었습니다. 나는 누군가가 같은 문제로이 질문에 부딪 힐 경우 내 자신의 짐승 O(n^3) 해결책을 생각해 낸다.

개선을 위해 누구나 the fiddle으로 초대되었습니다.

알고리즘

/** 
* Fuzzy match for word in array of strings with given accurancy 
* @param string needle word to search 
* @param int accurancy minimum matching characters 
* @param array haystack array of strings to examine 
* @return string matching word or undefined if none is found 
*/ 
function fuzzyMatch(needle,accurancy,haystack) { 
    function strcmpshift(a,b,shift) { 
    var match=0, len=Math.min(a.length,b.length); 
    for(var i in a) if(a[i]==b[+i+shift]) ++match; 
    return match; 
    } 
    function strcmp(a,b) { 
    for(var i=0,max=0,now; i<b.length; ++i) { 
     now = strcmpshift(a,b,i); 
     if(now>max) max = now; 
    } 
    return max; 
    } 

    var word,best=accurancy-1,step,item; 
    for(var i in haystack) { 
    item = haystack[i]; 
    step = Math.max(strcmp(item,needle),strcmp(needle,item)); 
    if(step<=best) continue; 
    best=step, word=item; 
    }; 
    return word; 
} 

예

var word = "rotation"; 
var commands = ["notable","tattoo","onclick","statistically"]; 
// find the closest command with at least 3 matching characters 
var command = fuzzyMatch(word,3,commands); 
alert(command); // tattoo