pyahocorasick 2.1.0

用户评价

非常感谢这个包。不确定在哪里留下感谢信，但这个包在我们的应用中绝对出色，我们在应用中有一个包含100k+ CRISPR向导的库，我们不得不在数百万个DNA测序读数流中计数。这个包比我们之前用于此目的的C程序做得更快，并帮助我们仅使用Python代码构建我们的流水线。

Miika（阿斯利康功能基因组学中心） https://github.com/WojciechMula/pyahocorasick/issues/145

下载和源代码

您可以从以下位置获取 pyahocorasick：

• GitHub https://github.com/WojciechMula/pyahocorasick/

• Pypi https://pypi.python.org/pypi/pyahocorasick/

• Conda-Forge https://github.com/conda-forge/pyahocorasick-feedstock/

文档发布在 https://pyahocorasick.readthedocs.io/

快速入门

此模块是用C编写的。您需要安装C编译器以编译本机CPython扩展。要安装

pip install pyahocorasick

然后创建一个自动机

>>> import ahocorasick
>>> automaton = ahocorasick.Automaton()

您可以使用自动机类作为Trie。向此Trie添加一些字符串键及其关联的值。这里我们将（插入索引，原始字符串）元组作为值关联到我们添加到Trie的每个键字符串

>>> for idx, key in enumerate('he her hers she'.split()):
...   automaton.add_word(key, (idx, key))

然后检查某个字符串是否存在于Trie中

>>> 'he' in automaton
True
>>> 'HER' in automaton
False

然后玩一下 get() 字典样式的方法

>>> automaton.get('he')
(0, 'he')
>>> automaton.get('she')
(3, 'she')
>>> automaton.get('cat', 'not exists')
'not exists'
>>> automaton.get('dog')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError

现在将Trie转换为Aho-Corasick自动机，以启用Aho-Corasick搜索

>>> automaton.make_automaton()

然后在输入字符串（我们的草堆）中搜索键（针）的所有实例。

这里我们打印结果，并检查它们是否正确。Automaton.iter()方法返回结果，作为在输入字符串中找到Trie键的结束索引和与此键关联的值的两个元组。这里我们存储了包含原始字符串及其Trie插入顺序的元组作为值

>>> for end_index, (insert_order, original_value) in automaton.iter(haystack):
...     start_index = end_index - len(original_value) + 1
...     print((start_index, end_index, (insert_order, original_value)))
...     assert haystack[start_index:start_index + len(original_value)] == original_value
...
(1, 2, (0, 'he'))
(1, 3, (1, 'her'))
(1, 4, (2, 'hers'))
(4, 6, (3, 'she'))
(5, 6, (0, 'he'))

您还可以提前创建一个可能很大的自动机并将其pickle，以在以后重新加载。这里我们只是将其pickle到一个字符串。您通常会将其pickle到一个文件中

>>> import pickle
>>> pickled = pickle.dumps(automaton)
>>> B = pickle.loads(pickled)
>>> B.get('he')
(0, 'he')

另请参阅

• 常见问题解答和谁在使用pyahocorasick？ https://github.com/WojciechMula/pyahocorasick/wiki/FAQ#who-is-using-pyahocorasick

文档

包括API概述和参考的完整文档发布在 readthedocs。

概述

使用 Aho-Corasick自动机，您可以在单个遍历输入字符串的过程中高效地搜索多个字符串（针）在输入字符串（草堆）中的所有实例。使用pyahocorasick，您最终可以构建大型自动机并将其pickle，以作为索引结构重复使用，以实现快速多模式字符串匹配。

aho-corasick自动机的优点之一是，典型情况下的最坏情况和最好情况的运行时间大致相同，主要取决于输入字符串的大小，其次取决于返回的匹配数。虽然这可能在所有情况下都不是最快的字符串搜索算法，但它可以同时搜索多个字符串，并且其运行时保证使其相当独特。因为pyahocorasick基于Trie，它只使用内存一次存储冗余键前缀。

缺点是需要在搜索字符串之前先构建和“最终确定”它。在搜索多个预定义“针”的变量“草堆”的几个应用中，这实际上是一个优点。

aho-corasick自动机通常用于入侵检测系统（如snort）、杀毒软件和其他许多需要与预定义字符串键集快速匹配的应用中的快速多模式匹配。

在内部，aho-corasick自动机通常基于Trie，具有额外的失败链接数据和一个Aho-Corasick搜索过程实现。

在幕后，Python库pyahocorasick实现了这两种数据结构：一个Trie和一个Aho-Corasick字符串匹配自动机。两者都通过Automaton类公开。

除了类似Trie的Aho-Corasick方法和数据结构之外，pyahocorasick还实现了类似字典的方法：pyahocorasick的Automaton是一个Trie，是一个类似于字典的结构，以字符串键为索引，每个键都与一个值对象相关联。您可以使用它以与字符串键长度成比例的时间检索关联的值。

pyahocorasick有两种版本

• 一个基于C的Python扩展，仅与Python 3兼容。使用旧版本1.4.x支持Python 2.7.x和32位。

• 一个更简单的纯Python模块，兼容Python 2和3。它仅可在源代码库（不在Pypi上）的etc/py目录下使用，并且API略有不同。

从PyPi构建和安装

要为常见的操作系统安装，请使用pip。预构建的轮子在Pypi上可能最终会可用。

pip install pyahocorasick

要从源代码构建，您需要安装并配置C编译器，这在Linux上是标准的，在MacOSX上也很容易获得。

要从源代码构建，请克隆git存储库或下载并提取源代码归档。

安装pip（及其setuptools伴侣），然后运行（当然是在virtualenv中！）

pip install .

如果编译成功，该模块就准备就绪，可以使用了。

支持

支持通过GitHub问题跟踪器报告错误或提出问题。

贡献

您可以通过GitHub拉取请求提交贡献。

• 有一个Makefile，具有默认目标，用于构建和运行测试。

• 测试可以通过pip installe -e .[testing] && pytest -vvs运行。

• 另请参阅 .github 目录中的 CI 测试和工作流程

作者

初始作者和维护者是 Wojciech Muła。 Philippe Ombredanne 是 Wojciech 的合作伙伴，帮助维护，并重新编写文档，设置 CI 服务器，并做了一些工作，使此模块更易于最终用户使用。

作者和贡献者按字母顺序列表

• Andrew Grigorev

• Ayan Mahapatra

• Bogdan

• David Woakes

• Edward Betts

• Frankie Robertson

• Frederik Petersen

• gladtosee

• INADA Naoki

• Jan Fan

• Pastafarianist

• Philippe Ombredanne

• Renat Nasyrov

• Sylvain Zimmer

• Xiaopeng Xu

以及许多人！

没有许多人的帮助，这个库是无法实现的。他们在各种方式上做出了贡献。他们创建了 拉取请求，以 GitHub 问题 或直接消息报告错误，提出了修复方案，或花费宝贵的时间进行测试。

谢谢。

许可

此库根据非常自由的 BSD-3-Clause 许可证授权。代码的一些部分是奉献给公共领域的，例如纯 Python 自动机和测试代码。

许可证的全文可在 LICENSE 文件中找到。

您可以考虑的其他 Python Aho-Corasick 实现

虽然 pyahocorasick 努力成为 Python 最优秀和最快的 Aho Corasick 库，但您可以考虑以下其他库

• py_aho_corasick by Jan

• 纯 Python 编写。

• 性能较差。

• ahocorapy by abusix

• 纯 Python 编写。

• 比 py-aho-corasick 有更好的性能。

• 使用 pypy，ahocorapy 的搜索性能仅略低于 pyahocorasick。

• 执行额外的后缀快捷方式（更多的设置开销，较少的搜索开销用于后缀查找）。

• 包括用于结果的自动机的可视化工具（使用 pygraphviz）。

• MIT 许可证，100% 测试覆盖率，在所有主要 Python 版本（+ pypy）上测试

• noaho by Jeff Donner

• 用 C 编写。不返回重叠匹配。

• 在 Windows 上无法编译（截至 2016 年 7 月）。

• 不支持 pickle 协议。

• acora by Stefan Behnel

• 用 Cython 编写。

• 大型自动机可能需要很长时间才能构建（截至 2016 年 7 月）

• 不支持将值与字符串键相关联的字典式协议。

• ahocorasick by Danny Yoo

• 用 C 编写。

• 似乎未维护（最后更新于 2005 年）。

• GPL 许可证。