pyahocorasick 1.4.4

感言

非常感谢这个包。不知道在哪里留下感谢信，但是这个包在我们的应用程序中绝对很棒，我们有一个包含 100k+ CRISPR 指南的库，我们必须在数百万个 DNA 测序读取流中进行计数。这个包比我们之前使用的 C 程序更快，并帮助我们在管道中只使用 Python 代码。

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

下载和源代码

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

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

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

• 康达锻造https://github.com/conda-forge/pyahocorasick-feedstock/

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

快速开始

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

pip install pyahocorasick

然后创建一个自动机：

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

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

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

然后检查 trie 中是否存在某些字符串：

>>> 'he' in A
True
>>> 'HER' in A
False

并使用get()类似 dict 的方法：

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

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

>>> A.make_automaton()

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

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

>>> for end_index, (insert_order, original_value) in A.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'))

您还可以提前创建一个最终大型的自动机，然后将其腌制以稍后重新加载。在这里，我们只是腌制一个字符串。您通常会改为腌制文件：

>>> import cPickle
>>> pickled = cPickle.dumps(A)
>>> B = cPickle.loads(pickled)
>>> B.get('he')
(0, 'he')

也可以看看：

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

文档

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

概述

使用Aho-Corasick 自动机 ，您可以有效地搜索输入字符串（大海捞针）中所有出现的多个字符串（针），从而对输入字符串进行一次遍历。使用 pyahocorasick，您最终可以构建大型自动机并腌制它们以反复重用它们作为快速多模式字符串匹配的索引结构。

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

一个缺点是它需要在搜索字符串之前提前构建和“最终确定”。在几个应用程序中，您在变量“haystacks”中搜索多个预定义的“needles”，这实际上是一个优势。

Aho-Corasick 自动机通常用于入侵检测系统（例如 snort）、防病毒和许多其他需要与预定义的字符串键集进行快速匹配的应用程序中的快速多模式匹配。

在内部，Aho-Corasick 自动机通常基于带有额外数据的 Trie 用于故障链接和 Aho-Corasick 搜索过程的实现。

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

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

pyahocorasick 有两种口味：

• 一个基于 CPython C 的扩展，与 Python 2 和 3 兼容。

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

从 PyPi 构建和安装

要安装通用操作系统，请使用 pip。未来某个时候，Pypi 上应该可以使用预构建的轮子：

pip install pyahocorasick

要从源代码构建，您需要安装和配置 C 编译器，该编译器在 Linux 上应该是标准的，并且在 MacOSX 上很容易上手。

在 Windows 和 Python 2.7 上，您需要Microsoft Visual C++ Compiler for Python 2.7（又名 Visual Studio 2008）。有报道称，pyahocorasick尚未使用 MinGW 构建。它可以使用 cygwin 构建，但尚未经过测试。如果您在这些平台上使用此功能，请在工单中报告！

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

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

pip install .

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

支持

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

贡献

您可以通过GitHub pull requests提交贡献。

作者

最初的作者和维护者是 Wojciech Muła。当前的共同所有人Philippe Ombredanne重写了文档，设置了 CI 服务器并做了很多工作以使最终用户可以更好地访问该模块。

按字母顺序排列的作者名单：

• 安德鲁·格里戈列夫

• 波格丹

• 大卫·沃克斯

• 爱德华·贝茨

• 弗兰基·罗伯逊

• 弗雷德里克·彼得森

• 很高兴见到

• 稻田直树

• 范扬

• 面食主义者

• 菲利普·奥布雷丹

• 雷纳特·纳西罗夫

• 西尔万·齐默

• 徐小鹏

如果没有许多人的帮助，这个图书馆是不可能实现的，他们以各种方式做出了贡献。他们创建拉取请求，将错误报告为GitHub 问题 或通过直接消息，提出修复建议，或将宝贵的时间用于测试。

谢谢你。

执照

这个库是在非常自由 的 BSD-3-Clause许可下获得许可的。代码的某些部分专用于公共领域，例如纯 Python 自动机和测试代码。

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

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

虽然pyahocorasick试图成为 Python 中最好和最快的 Aho Corasick 库，但您可以考虑以下其他库：

• py_aho_corasick由 Jan

• 用纯 Python 编写。

• 表现不佳。

• ahocorapy by abusix

• 用纯 Python 编写。

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

• 使用 pypy，ahocorapy 的搜索性能只比 pyahocorasick 的稍差。

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

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

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

• 杰夫·唐纳的诺亚

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

• 不能在 Windows 上编译（2016 年 7 月）。

• 不支持 pickle 协议。

• Stefan Behnel的acora

• 用 Cython 编写。

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

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

• Danny Yoo 的ahocorasick

• 写在 C 中。

• 似乎无人维护（2005 年最后一次更新）。

• GPL 许可。