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

Question

背后的故事

我正在创建一个语音控制的应用程序,使用x-webkit-speech它非常好(功能,而不是我的应用程序),但有时用户(我)嘟a一点.如果该单词的某些合理部分与某个合理命令的某些合理部分相匹配,那么接受该命令会很好.因此,我搜索了一组名为"最大的单词交叉算法"的圣杯.一些新鲜明亮的头脑会让我走出绝望的洞穴吗？

例

"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

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