单词集合中最大交集的算法

Question

背后的故事

我正在创建一个使用x-webkit-speech的语音控制应用程序，这个功能出奇的好（不是我的应用），但有时用户（我）会说话含糊不清。如果某个单词的合理部分与某个合理命令的合理部分相匹配，那么接受该命令将会很好。因此，我寻找被称为“单词集中最大交集算法”的圣杯。是否有一些新鲜而聪明的头脑能够帮我走出绝望的洞穴呢？

示例

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

应该匹配tattoo，因为它与rotation（tat_o）有最长的交集。 Statistically是第二好的选择（tati交集），因为需要忽略单词的较长部分（但这是奖励条件，即使没有它也可以接受）。

注意：

- 我使用捷克语，发音非常接近书写形式。 - 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

- Jan Turoň

---

这是否与编辑距离相同，只是删除的权重为0？ - Mike Samuel

@JanTuron，"编辑距离"是指那个广泛使用的算法。 - Mike Samuel

刚在维基百科上找了一下，我猜编辑距离可能会有帮助，但我还是感到头疼。 - Jan Turoň

你要找的是Levenshtein距离算法。在Wikipedia上有它的介绍，还有几个C语言版本的示例。 - Jason Nichols

你关心算法的速度还是准确性？另外请参考：http://en.wikipedia.org/wiki/Fuzzy_string_searching - Andrew W

Answer 1

这是一个看起来能够运行的算法。我不知道它与其他已经成熟的算法相比表现如何（我怀疑它的表现更差），但也许它能给你一些想法： 点这里查看演示。

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

- basilikum

Answer 2

这是一个使用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]);
    }
    //https://dev59.com/FlXTa4cB1Zd3GeqP3Jp-
    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 + "." )

你可以在这里玩弄这个示例 链接。

- Jason Nichols

Answer 3

感谢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

- Jan Turoň