ahocorasick_rs：快速一次性搜索多个子字符串

ahocorasick_rs 允许您使用 Aho-Corasick 算法的变体在给定的字符串（“稻草”）中搜索多个子字符串（“模式”）。

特别是，它被实现为一个 Rust aho-corasick 库的包装器，并提供了一个比 pyahocorasick 库更快的替代方案。

遇到任何问题或有什么疑问？ 在GitHub项目上提交问题。

• 快速入门
• 选择匹配算法
• 额外配置：速度和内存使用权衡
• 实现细节
• 基准测试

快速入门

ahocorasick_rs 库允许您在“稻草”中搜索多个字符串（“模式”），或者也可以搜索多个字节。例如，让我们安装这个库

$ pip install ahocorasick-rs

搜索字符串

我们可以构建一个 AhoCorasick 对象

>>> import ahocorasick_rs
>>> patterns = ["hello", "world", "fish"]
>>> haystack = "this is my first hello world. hello!"
>>> ac = ahocorasick_rs.AhoCorasick(patterns)

您可以从任何可迭代对象（包括生成器）中构建一个 AhoCorasick 对象，而不仅仅是列表

>>> ac = ahocorasick_rs.AhoCorasick((p.lower() for p in patterns))

AhoCorasick.find_matches_as_indexes() 返回一个元组列表，每个元组是

1. 找到的模式在模式列表中的索引。
2. 模式在目标字符串中的起始索引。
3. 模式在目标字符串中的结束索引。

>>> ac.find_matches_as_indexes(haystack)
[(0, 17, 22), (1, 23, 28), (0, 30, 35)]
>>> patterns[0], patterns[1], patterns[0]
('hello', 'world', 'hello')
>>> haystack[17:22], haystack[23:28], haystack[30:35]
('hello', 'world', 'hello')

find_matches_as_strings() 返回找到的模式列表

>>> ac.find_matches_as_strings(haystack)
['hello', 'world', 'hello']

搜索 bytes 和其他类似对象

您还可以搜索 bytes、bytearray、memoryview 以及支持 Python 缓冲区 API 的其他对象。

>>> patterns = [b"hello", b"world"]
>>> ac = ahocorasick_rs.BytesAhoCorasick(patterns)
>>> haystack = b"hello world"
>>> ac.find_matches_as_indexes(b"hello world")
[(0, 0, 5), (1, 6, 11)]
>>> patterns[0], patterns[1]
(b'hello', b'world')
>>> haystack[0:5], haystack[6:11]
(b'hello', b'world')

BytesAhoCorasick 不支持 find_matches_as_strings() API。

选择匹配算法

匹配类型

在多个模式重叠的情况下，您可以通过三种方式配置匹配，这两种对象都支持。对于更详细的解释，请参阅底层 Rust 库的匹配文档。

假设我们有这个起点

>>> from ahocorasick_rs import AhoCorasick, MatchKind

Standard（默认）

这返回第一个匹配的模式，从语义上讲。这是默认匹配模式。

>>> ac AhoCorasick(["disco", "disc", "discontent"])
>>> ac.find_matches_as_strings("discontent")
['disc']
>>> ac = AhoCorasick(["b", "abcd"])
>>> ac.find_matches_as_strings("abcdef")
['b']

在这种情况下，disc 将在 disco 或 discontent 之前匹配。

同样，b 将在 abcd 之前匹配，因为它在目标字符串中的结束位置比 abcd 更早。

>>> ac = AhoCorasick(["b", "abcd"])
>>> ac.find_matches_as_strings("abcdef")
['b']

LeftmostFirst

这返回在目标字符串中最先出现的匹配模式，即 给定模式列表 中第一个出现的模式。这意味着模式的顺序是有影响的

>>> ac = AhoCorasick(["disco", "disc"], matchkind=MatchKind.LeftmostFirst)
>>> ac.find_matches_as_strings("discontent")
['disco']
>>> ac = AhoCorasick(["disc", "disco"], matchkind=MatchKind.LeftmostFirst)
['disc']

在这里我们看到 abcd 首先匹配，因为它在列表中先出现

>>> ac = AhoCorasick(["b", "abcd"], matchkind=MatchKind.LeftmostFirst)
>>> ac.find_matches_as_strings("abcdef")
['abcd']

LeftmostLongest

这返回在目标字符串中最先出现的最长的匹配模式

>>> ac = AhoCorasick(["disco", "disc", "discontent"], matchkind=MatchKind.LeftmostLongest)
>>> ac.find_matches_as_strings("discontent")
['discontent']

重叠匹配

您可以得到所有重叠的匹配，而不是只得到其中一个，但前提是您坚持使用默认的匹配类型 MatchKind.Standard。同样，这也被 AhoCorasick 和 BytesAhoCorasick 支持。

>>> from ahocorasick_rs import AhoCorasick
>>> patterns = ["winter", "onte", "disco", "discontent"]
>>> ac = AhoCorasick(patterns)
>>> ac.find_matches_as_strings("discontent", overlapping=True)
['disco', 'onte', 'discontent']

额外配置：速度和内存使用的权衡

算法实现：构建速度、内存和性能之间的权衡（《AhoCorasick》和《BytesAhoCorasick》）

您可以选择要使用的底层自动机的类型，具有不同的性能权衡。简而言之：如果您想获得最大的匹配速度，并且模式不多，请尝试使用 Implementation.DFA 实现并查看是否有所帮助。

底层 Rust 库支持四种选择，如下所示

• None 使用启发式方法选择为给定模式选择“最佳”Aho-Corasick 实现，平衡构建时间、内存使用和匹配速度。这是默认设置。
• Implementation.NoncontiguousNFA：非连续 NFA 是构建速度最快的，具有适中的内存使用量，并且通常在执行搜索时速度最慢。
• Implementation.ContiguousNFA：连续 NFA 比非连续 NFA 慢一些构建，具有优异的内存使用量，并且通常比 DFA 搜索速度略慢。
• Implementation.DFA：DFA 构建速度非常慢，使用大量的内存，但通常搜索速度最快。

>>> from ahocorasick_rs import AhoCorasick, Implementation
>>> ac = AhoCorasick(["disco", "disc"], implementation=Implementation.DFA)

以内存换取速度（《AhoCorasick》仅限）

如果您使用 find_matches_as_strings()，字符串可以以两种方式构建：从目标字符串中构建，或将模式缓存到对象中。前者需要更多的工作，后者如果模式会被垃圾回收，则会使用更多的内存。您可以通过使用 AhoCorasick() 的 store_patterns 关键字参数来控制此行为。

• AhoCorasick(..., store_patterns=None)：默认设置。使用启发式方法（目前，模式字符串长度总和是否小于 4096 个字符）来决定是否存储模式。
• AhoCorasick(..., store_patterns=True)：保留对模式的引用，可能会加快 find_matches_as_strings() 的速度，但会使用更多的内存。如果这使用了大量的内存，这可能会由于对 CPU 内存缓存的压力而减慢速度，并且/或者性能提升可能会被算法的搜索时间所抵消。
• AhoCorasick(..., store_patterns=False)：不保留模式引用，节省一些内存，但可能会减慢find_matches_as_strings()的执行速度，尤其是在模式数量较少且搜索的文本内容较小的情况下。

实现细节

• 字符串匹配会释放全局解释器锁（GIL），以实现并发。出于内存安全的原因，字节匹配目前不会释放GIL，除非文本类型是bytes。
• 并非所有底层库的功能都公开；如果您需要额外的功能，请提交问题或提交PR。

基准测试

与任何基准测试一样，实际结果会根据您的特定情况而有所不同。如果性能对您的应用程序很重要，请自行测量替代方案！

尽管如此，我观察到ahocorasick_rs的运行速度比pyahocorasick快1.5倍到7倍，具体取决于使用的选项。如果您想查看一些比较结果，可以运行包含的基准测试。克隆仓库后，

pip install pytest-benchmark ahocorasick_rs pyahocorasick
pytest benchmarks/