词集中词的最大交集算法

背后的故事

我正在使用创建语音控制应用程序x-webkit-speech这是令人惊讶的好（功能，而不是我的应用程序），但有时用户（我）会有点咕哝。如果单词的某些合理部分与某些合理命令的某些合理部分相匹配，那么接受该命令会很好。所以我寻找名为“圣杯”的东西词集中词的最大交集算法。一些新鲜明亮的头脑能把我从绝望的洞穴中带出来吗？

Example

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

应该匹配tattoo因为它与 的相交最长rotation (tat_o). 统计上是第二好的（tatiintersect），因为需要忽略单词的较长部分（但这是奖励条件，没有它也是可以接受的）。

Notes

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

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

FIDDLE http://jsfiddle.net/bTPZx/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，这就是它将返回的值。