java - 在 trie 树中实现模式匹配

Question

我目前正在使用此堆栈溢出帖子中的 trie 实现:

Getting a list of words from a Trie

返回与给定前缀匹配的单词列表。然后，我使用正则表达式过滤掉不符合整个指定模式的单词。

EX:如果我正在搜索的模式是:CH??S？这是与我的初始前缀匹配的字典的子集: {CHABAD、CHACHA、CHARIOT、CHATTED、CHEATER、CHOMSKY、CHANNEL CHAFED、CHAFER、链条、椅子、奶酪、奶酪 CHRONO、CHUTES、凿子}

我会搜索带有“CH”前缀的特里树，然后过滤出与我所需的 CH??S 模式匹配的单词。 (俗气，奶酪，凿子)并将其归还。

我想知道是否有更快的方法来避免在最后一步中使用正则表达式。我以为我可以使用后缀树( Ukkonen's suffix tree algorithm in plain English )或 boyer-moore 算法，但这两种算法都不起作用，因为它们搜索后缀而不是模式。

Answer 1

这是一个很好的递归算法，您可以使用它，无需使用最终的正则表达式传递。它的工作原理是将模式 P 与树 T 进行匹配:

FindMatches(pattern P, tree T) {
    if (tree is empty) {
        return that there are no matches;
    }

    if (pattern is empty) {
        report a match if T is a word;
    } else if (pattern[0] is a letter) {
        FindMatches(P[1:], T.childFor(pattern[0]));
    } else if (pattern[0] is ?) {
        for (each child C of T) {
             gather matches from FindMatches(P[1:], C);
        }
        report all matches found this way;
    } else {
        something is wrong with your pattern;
    }
}

您仅匹配 CH 的方法遵循此方法。但是，当您到达匹配 ? 字符的位置时，您的方法只是执行 DFS 来查找当前点以下的所有单词，而这种方法只是在一个级别上分支并收集火柴。换句话说，这种方法是“如果有明确的字符需要跟踪，则一次跟踪一个字符”和“探索整个子树寻找匹配项”和“策略性地集中分支”之间的混合体。