Aho-Corasick算法

Aho-Corasick 算法是一种用于多模式字符串匹配的有效算法。它由 Alfred V. Aho 和 Margaret J. Corasick 于 1975 年提出。该算法的主要应用是在一个文本中同时搜索多个模式字符串。

算法原理

Aho-Corasick 算法的核心思想是将所有模式字符串构建成一棵有向图（称为“字典树”或“Trie”），并在此基础上构建一个失败函数（failure function），以便在匹配失败时能够快速转移到下一个可能的匹配状态。

Trie 构建

插入模式字符串：将所有模式字符串插入到 Trie 中，每个节点代表一个字符。
标记结束节点：在每个模式字符串的末尾节点进行标记，以便识别完整的模式。

失败函数构建

初始化失败指针：根节点的失败指针指向自身。
广度优先搜索：使用广度优先搜索（BFS）遍历 Trie，设置每个节点的失败指针。
失败指针设置：对于每个节点，失败指针指向当前节点的父节点的失败指针所指向的节点的子节点（如果存在），否则指向根节点。

匹配过程

初始化：从根节点开始。
字符匹配：对于文本中的每个字符，沿着 Trie 进行匹配。
失败转移：如果匹配失败，使用失败指针进行转移，直到找到匹配或回到根节点。
模式识别：当到达一个标记为结束的节点时，表示找到了一个模式。

时间复杂度

Aho-Corasick 算法的时间复杂度为 O(n + m + z)，其中 n 是文本长度，m 是所有模式字符串的总长度，z 是所有匹配出现的总数。这使得它在处理大规模文本和多模式匹配时非常高效。

应用场景

文本过滤：用于敏感词过滤、垃圾邮件检测等。
生物信息学：用于 DNA 序列分析。
网络安全：用于入侵检测系统。

Aho-Corasick 算法因其高效的多模式匹配能力而被广泛应用于各种领域。

示例代码

以下是一个简单的 Aho-Corasick 算法的 Python 实现示例：

class TrieNode:
    def __init__(self):
        self.children = {}
        self.fail = None
        self.output = []

class AhoCorasick:
    def __init__(self, patterns):
        self.root = TrieNode()
        self.build_trie(patterns)
        self.build_failure_links()

    def build_trie(self, patterns):
        for pattern in patterns:
            node = self.root
            for char in pattern:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.output.append(pattern)

    def build_failure_links(self):
        from collections import deque
        queue = deque()
        for node in self.root.children.values():
            node.fail = self.root
            queue.append(node)

        while queue:
            current_node = queue.popleft()
            for char, child_node in current_node.children.items():
                fail_node = current_node.fail
                while fail_node is not None and char not in fail_node.children:
                    fail_node = fail_node.fail
                child_node.fail = fail_node.children[char] if fail_node else self.root
                child_node.output += child_node.fail.output if child_node.fail else []
                queue.append(child_node)

    def search(self, text):
        node = self.root
        results = []
        for i, char in enumerate(text):
            while node is not None and char not in node.children:
                node = node.fail
            if node is None:
                node = self.root
                continue
            node = node.children[char]
            if node.output:
                for pattern in node.output:
                    results.append((i - len(pattern) + 1, pattern))
        return results

# 示例使用
patterns = ["he", "she", "his", "hers"]
text = "ushers"
ac = AhoCorasick(patterns)
matches = ac.search(text)
print(matches)  # 输出: [(1, 'she'), (2, 'he'), (3, 'hers')]