[Python3] 多模式字符串搜索 `Aho-Corasick`

ahocorasick.Automaton 是 Python 中 pyahocorasick 库提供的一个类，用于实现 Aho-Corasick 自动机。Aho-Corasick 算法是一种用于精确或近似多模式字符串搜索的高效算法。

通过 pip install pyahocorasick 安装 pyahocorasick 库。
并且，该模块是用 C 编写的，安装时需要有 C 编译器来编译本机 Cpython 扩展。

使用 ahocorasick.Automaton 类的一般步骤如下：

1. 导入 ahocorasick 库：import ahocorasick。

2. 创建 Automaton 对象：a = ahocorasick.Automaton() 。

3. （可选）将字符串键及其关联值添加到自动机，可作为 trie 树使用。例如：

   for idx, key in enumerate('heherhersshe'.split()):
       a.add_word(key, (idx, key))
   

4. 调用 make_automaton() 方法完成并创建 Aho-Corasick 自动机：a.make_automaton() 。

创建好自动机后，可以使用以下主要方法进行搜索操作：

• iter(string, (start, (end)))：使用提供的输入字符串执行 Aho-Corasick 搜索过程。它返回一个迭代器，为在字符串中找到的键返回元组 (end_index, value)，其中 end_index 是匹配结束的索引位置，value 是与匹配的键相关联的值。

• iter_long(string, (start, (end)))：返回一个搜索最长、非重叠匹配的迭代器（automaton_search_iter_long 类的对象）。

以下是一个使用 ahocorasick.Automaton 进行多模式字符串搜索的示例代码：

import ahocorasick as ah

a = ah.automaton()

with open('userdict.txt', 'r', encoding='utf-8') as f2:  # 加载文件
    keywords = (a.strip() for a in f2.readlines())  # 加载关键词

    # 利用 add_word 方法将关键词加入自动机！
    for x in range(len(keywords)):
        a.add_word(keywords[x], (x, keywords[x]))  # 第二个参数为自定义的返回值

# 创建 aho-corasick 自动机
a.make_automaton()

with open('jianjie.txt', 'r', encoding='utf-8') as f:  # 打开要检索文档
    jianjie = f.read()  # 读取正文（如果太多，可以分断加载，分段检索）

# 开始查找，该方法匹配最长的字符串
for item in a.iter_long(jianjie):
    print(item)
print('-' * 20)

# 开始查找，该方法匹配所有字符串
for item in a.iter(jianjie):
    print(item)

在上述示例中，首先创建了一个自动机对象 a，然后从文件中读取关键词，并使用 add_word 方法将关键词添加到自动机中。接着调用 make_automaton 方法创建 Aho-Corasick 自动机。最后，通过打开另一个文件读取要搜索的正文，并使用 iter_long 和 iter 方法进行匹配查找，并打印出匹配的结果。

Aho-Corasick 自动机的优点包括能够在一次运行中找到给定集合所有字符串，适用于多模式字符串匹配的场景，例如网络内容过滤、版权检测、病毒扫描等，在自然语言处理中查找特定词汇或模式，以及生物信息学中在 DNA 或蛋白质序列分析中寻找特定的序列模式等方面都有应用。

原文地址：https://blog.csdn.net/qq_44810930/article/details/140631550

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！