javascript - 捕获一个字符串然后匹配所有以该字符串开头的其他单词

我有一个包含80,000多个单词的列表，每个单词由换行符分隔。我需要匹配每一个以较小单词为前缀的单词。例如，

bald    <-- captures bald
balder  <-- matches because it starts with bald
balding <-- matches because it starts with bald
care    <-- captures care
cared   <-- matches because it starts with care
cares   <-- matches because it starts with care
caring  <-- does NOT match because it does not start with care

我将会在 Sublime Text 中使用查找和替换，所以我希望能够使用“全部替换”为“”，从而将它们从我的列表中移除。

好的，故事背景如下：

我的单词列表基本上是英语词典的简缩版。通过使用正则表达式，我已经能够删除所有专有名词、缩写、带重音符号的单词，以及所有少于4个字母的单词。我将使用这个词典来制作一个JavaScript单词游戏。（是的，这确实是一个作业，但它不是为了学校学分，这个作业只是为了制作一个简单的JavaScript游戏。我的游戏逻辑是可行的，我也可以手动编辑单词列表，但我希望在2016年前完成，所以正则表达式似乎是最快的方式）。

这个游戏的目的是迫使你的对手完成拼写一个单词。玩家轮流在一个字母串中添加字母，一旦字母串与字典中的某个单词匹配，游戏就结束了。出于这个原因，像 overblown、overhead 和 overkill 这样的单词是负担。一旦 overhead 中的 over 被拼出来，游戏就……嗯……结束了。

我会将 wordList 作为数组加载到一个 JavaScript 文件中，因此我希望它尽可能小。

我确定还有其他方法可以做到这一点（API之类的），但我们在这个作业中不能使用它们。

任何帮助都将不胜感激！

答案＃1

存储单词列表的一种高效结构是前缀树。例如，给定一个像这样的字典

'car',
'card',
'carder',
'care',
'cared',
'cares',
'caring',
'can'

这个字典树可能看起来像这样

（其中 0 表示单词的结尾）。

构建字典树的代码相当简单：

function buildTree(words) {
    var tree = {};
    words.forEach(function (word) {
        var t = tree;
        [].forEach.call(word + "0", function (char) {
            t = t[char] || (t[char] = {});
        });
    });
    return tree;
}

现在，要列出所有以给定前缀开头的单词，只需递归地遍历字典树并收集匹配的单词：

function findWords(prefix, tree) {
    var found = [];

    function walk(pfx, t, word) {
        if (!pfx) {
            if (t[0])
                found.push(word)
            for (var c in t)
                walk("", t[c], word + c);
        } else if (pfx[0] in t)
            walk(pfx.substr(1), t[pfx[0]], word + pfx[0]);
    }

    walk(prefix, tree, "");
    return found;
}

完整代码：

function buildTree(words) {
    var tree = {};
    words.forEach(function (word) {
        var t = tree;
        [].forEach.call(word + "0", function (char) {
            t = t[char] || (t[char] = {});
        });
    });
    return tree;
}

function findWords(prefix, tree) {
    var found = [];

    function walk(pfx, t, word) {
        if (!pfx) {
            if (t[0])
                found.push(word)
            for (var c in t)
                walk("", t[c], word + c);
        } else if (pfx[0] in t)
            walk(pfx.substr(1), t[pfx[0]], word + pfx[0]);
    }

    walk(prefix, tree, "");
    return found;
}

words = [
    'car',
    'card',
    'carder',
    'care',
    'cared',
    'cares',
    'caring',
    'can'

]

prefixTree = buildTree(words);
document.write(findWords("care", prefixTree));

要删除以另一个单词开头的单词，你可以像上面那样构建字典树，然后遍历它，一旦找到终止标记（0）就停止搜索：

function buildTree(words) {
    var tree = {};
    words.forEach(function (word) {
        var t = tree;
        [].forEach.call(word + "0", function (char) {
            t = t[char] || (t[char] = {});
        });
    });
    return tree;
}


function findShortWords(tree) {
    var found = [];

    function walk(t, word) {
        if(t[0]) {
            found.push(word);
            return;
          }
        for (var c in t)
            walk(t[c], word + c);
    }

    walk(tree, "");
    return found;
}

words = [
    'card',
    'carder',
    'care',
    'cared',
    'cares',
    'caring',
    'can',
    'canoe',
    'bald',
    'balder',
    'balding',
    'foo'

]

prefixTree = buildTree(words);

document.write(findShortWords(prefixTree));

答案＃2

如果你能先对你的单词列表进行逆序排序，那么有一个正则表达式可能对你有帮助。到目前为止，我只在 iPod 上的 JavaScript-replace 中测试过它，但我相信 Sublime Text 也应该能够做到同样的事情。这里是我的示例文本（添加了一些更多的单词来增加趣味性...）：

var s="runs,running,runner,run,forging,forgetting,forgets,forget,forged,forge,caring,cares,cared,care,balding,balder,bald"

我将很快把它转换成由换行符分隔的单词列表，然后应用我的正则表达式：

s=s.replace(/,/g,'\n');
s.replace(/(\w+)\w+\n(?=(?:.*\n)*\1(?:\n|$))/g,'');

这将完全删除所有“多余”的行，并为你获取

run
forge
caring
care
bald

然而，如果你仍然希望在不需要的单词位置保留空行，你可以这样做

s.replace(/(\w+)\w+(?=\n(?:.*\n)*\1(?:\n|$))/g,'');

倒序单词顺序对于我的方法至关重要，因为我正在使用可变长度的前瞻来查找单词的基本形式，同时我可能在主模式 (\w+)\w+ 中捕获它的一个变形形式。有趣的是，我从未相信它会这样工作，但它确实如此！这一行的捕获与非捕获部分没有明确定义，但正则表达式引擎会尝试不同的长度，直到在前瞻模式 \n(?:.*\n)*\1(?:\n|$) 中找到捕获组。在我的 JavaScript 示例中，只需设置 RegExp 的 g 标志即可。在 Sublime Text 中，你很可能还需要设置与 m 相当的多行标志。

正如你可能已经注意到的，整个方法仍然存在一个根本性的缺陷：词干“forge”不仅抹去了它自身的其他动词形式，还带走了“forget”的所有形式。这是一个“逻辑”问题，源于在一个单纯的单词列表中，从未明确定义一个动词的基本形式。

更新

刚刚又读了一遍你的问题。对于你的游戏来说，所谓的“根本缺陷”实际上是你想要的东西。所以就忽略我上一段话吧。;-）