c++ - Trie 搜索正则表达式 : C++

Question

好吧，我必须使用像“*all”这样的输入来搜索 Trie 树，其中 * 可以是任何字符。我知道使用 regex_match 来匹配对字符串的搜索，就像其他树一样，您在其中搜索整个单词。但是由于 Trie 的搜索算法是按字符进行的，因此我无法将常规搜索算法转换为我的需要。

这是没有 * 的 trie 搜索的原始代码

 bool Trie::searchWord(string s){
Node* cur = root;

while(cur != NULL){
    for(int i = 0; i < s.length(); i++){
        Node* tmp = cur->findChild(s[i]);
        if(tmp == NULL){
            return false;
        }//end if
        cur = tmp;
    }//end for
    if(cur->wordMarker()){
        return true;
    }else{
        return false;
    }//end if-else
}//end while
return false;
}//end searchWord(s)

Node* Node::findChild(char c){
for(int i = 0; i<mChildren.size(); i++){
    Node* tmp = mChildren.at(i);
    if(tmp->content() == c){
        return tmp;
    }//end if
}//end for
return NULL;
}//end findChild(c)

这是我尝试修改它的尝试。它仍然适用于常规单词，但不适用于 *

bool Trie::searchWordRegex(string s){
Node* cur = root;

while(cur != NULL){
    regex reg ;
    for(int i = 0; i < s.length(); i++){
        if(s[i] == '*'){
            reg = regex("(\\w)");
        }//end if
        Node* tmp = cur->findChildRegex(s[i], reg);
        if(tmp == NULL){
            return false;
        }//end if
        cur = tmp;
    }//end for
    if(cur->wordMarker()){
        return true;
    }else{
        return false;
    }//end if-else
}//end while
return false;
}//end searchWord(s)

Node* Node::findChildRegex(char c, regex r){
for(int i = 0; i<mChildren.size(); i++){
    Node* tmp = mChildren.at(i);
    string s(1,tmp->content());
    if(tmp->content() == c || regex_match(s, r)){
        return tmp;
    }//end if
}//end for
return NULL;
}//end findChild(c)

有没有办法让这些功能正常工作？或者是否有像其他树的 regex_match 一样简单的方法？

谢谢。

Answer 1

意图有点困惑，因为您将“*”称为字符通配符，但您指的是正则表达式匹配(实际的正则表达式字符通配符是“.”)。我将尝试回答这个问题，假设意图是支持对 trie 进行完整的正则表达式搜索，或者在 trie 中进行通配符搜索。

Trie 中的正则表达式匹配

trie 通常用于支持快速 O(m) 操作。它通常不是处理正则表达式的有效结构。

regular expression matching 有几个算法(DFA/NFA 和回溯)，并在 trie 搜索中支持它们，您必须有效地实现一个修改以支持子尝试的迭代，并在 trie 中回溯以获取正则表达式可以收集的状态/匹配项匹配。这将具有最低的渐近复杂性，可能是最有效的。

然而...

t 几乎具有相同的渐近复杂度来迭代 trie 中的所有字符串，并使用 std::regex 和 std::regex_match 测试它们与正则表达式匹配>。此外，它使您不必实现相对复杂的正则表达式引擎。

Trie 中的通配符匹配

但是，修改您的代码以支持通配符搜索非常简单。您无需使用显式字符搜索每个级别，而是根据通配符(“*”或“.”)检查搜索字符 s[i]，如果它匹配，您可以进入任何一个子尝试，并递增 i。不过，需要注意的是，您需要能够转义您选择作为通配符的任何字符，以便它在存储在 trie 中的字符串中仍然是有效字符。