Python 字典树的模糊匹配与模式匹配算法

2023-04-11 00:00:00 算法 匹配 字典

字典树，也称为前缀树（Trie树），是一种典型的树结构，用于存储字符串集合，可以高效地实现字符串的查找、插入和删除。在字典树中，每个节点代表一个字符串的前缀，从根节点到叶子节点构成一个完整的字符串。字典树的性质可以支持多种字符串匹配算法。

模糊匹配是一种字符串匹配算法，用于识别与目标字符串类似但不完全匹配的字符串。字典树可以用于实现模糊匹配，具体实现方法如下：

  1. 构建一个字典树，将需要匹配的模式字符串插入到树中。

  2. 对于一个待匹配的字符串，遍历整个字典树，在每个节点上进行字符匹配，如果当前字符与节点匹配，则继续匹配下一个字符，否则根据模糊匹配的规则，可以选择跳过该节点或者替换当前字符后继续匹配。

  3. 如果遍历到了字典树的叶子节点，说明找到了一个匹配的模式字符串，记录下来即可。

代码演示：

class TrieNode:
    def __init__(self):
        self.next = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.next:
                node.next[c] = TrieNode()
            node = node.next[c]
        node.is_end = True

    def search(self, word, node=None):
        if node is None:
            node = self.root
        for i in range(len(word)):
            c = word[i]
            if c in node.next:
                node = node.next[c]
            else:
                return False

        return node.is_end

    def fuzzy_search(self, word, node=None, delta=1, prefix=""):
        if node is None:
            node = self.root

        if len(word) == 0:
            if node.is_end:
                print(prefix)

            for c in node.next:
                self.fuzzy_search("", node.next[c], delta, prefix+c)

            return

        if delta >= 0:
            if word[0] in node.next:
                self.fuzzy_search(word[1:], node.next[word[0]], delta, prefix+word[0])

            for c in node.next:
                if c != word[0]:
                    self.fuzzy_search(word[1:], node.next[c], delta-1, prefix+c)

        if delta == 0 and len(word) > 1:
            for c in node.next:
                self.fuzzy_search(word[1:], node.next[c], delta-1, prefix+c)

    def pattern_search(self, word, node=None, idx=0, prefix=""):
        if node is None:
            node = self.root

        if idx == len(word):
            if node.is_end:
                print(prefix)

            return

        if word[idx] == "*":
            for c in node.next:
                self.pattern_search(word, node.next[c], idx, prefix+c)
        elif word[idx] == "?":
            for c in node.next:
                self.pattern_search(word, node.next[c], idx+1, prefix+c)
        else:
            if word[idx] in node.next:
                self.pattern_search(word, node.next[word[idx]], idx+1, prefix+word[idx])

trie = Trie()
trie.insert("pidancode.com")
trie.insert("皮蛋编程")
trie.insert("python")
trie.fuzzy_search("pidancode", delta=1) # 匹配pidancode或pidanccde
trie.pattern_search("pi*co*e") # 匹配pidancode

以上代码演示了如何在字典树中实现模糊匹配和模式匹配。

相关文章