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

Question

我有一个包含 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 年之前完成，所以正则表达式似乎是可行的方法)。

游戏的重点是迫使你的对手完成拼写一个单词。玩家轮流将字母添加到字符串中，一旦字符串与字典中的单词匹配，游戏就结束了。出于这个原因，像夸大、开销和矫枉过正这样的词是自重的。一旦开销结束，游戏就...嗯...结束。

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

我确信还有其他方法可以做到这一点(api 等)，但我们不能将它们用于此作业。

非常感谢任何帮助!

Answer 1

存储单词列表的有效结构是 prefix tree .例如，给定一个像

这样的字典

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

trie 可能看起来像这样

(其中 0 表示单词的结尾)。

构建 trie 的代码相当简单:

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;
}

现在，要枚举所有以给定前缀开头的单词，只需递归遍历 trie 并收集匹配的单词:

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));

要删除以另一个词开头的词，您可以像上面那样构建 trie，然后遍历它，一旦找到终止标记 (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));