5

背后的故事

我正在创建一个语音控制的应用程序，使用x-webkit-speech它非常好（功能，而不是我的应用程序），但有时用户（我）会咕哝一点。如果单词的某个合理部分与某个合理命令的某个合理部分匹配，那么接受该命令会很好。因此，我在 Set of Words 中寻找名为 Algorithm of the Greatest Intersect of Word 的圣杯。一些新鲜的聪明头脑能把我赶出绝望的洞穴吗？

例子

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

应该匹配纹身，因为它与旋转的相交时间最长（tat_o）。统计上是第二好的（tati intersect ），因为需要忽略单词的较长部分（但这是奖励条件，没有它也是可以接受的）。

笔记

  • 我使用捷克语，发音非常接近书面形式
  • javascript 是首选语言，但任何伪代码都是可以接受的
  • 相交的最小长度应该是算法的参数

我尝试了什么？

嗯，还蛮尴尬的。。。。

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
4

3 回答 3

2

这是一个似乎有效的算法。与其他已经建立的算法相比，我不知道它的性能有多好（我怀疑它的性能更差），但也许它让你知道如何做到这一点：

小提琴

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，这就是它将返回的内容。

于 2013-05-30T19:22:34.297 回答
1

这是 Javascript 中的 Levenshtein 距离计算器的实现。

它返回一个包含匹配命令和距离的对象。

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 + "." )

你可以在这里摆弄小提琴。

于 2013-05-30T20:15:30.577 回答
0

谢谢 basilikum 和 JasonNichols 以及 Mike 和 Andrew 的评论，这真的帮助我完成了算法。我想出了我自己的蛮力O(n^3)解决方案，以防有人遇到同样的问题。

任何人都被邀请玩小提琴来改进它。

算法

/**
 * 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
于 2013-05-31T07:58:46.147 回答