Python Aho-Corasick实现

noahong 是基于 Aho-Corasick 算法的字符串匹配Python实现，基于NoAho C++实现的分支。

noahong 支持在 Python 3.6+ 上运行于 macOS、Linux、Windows。

API

首先，需要实例化一个 NoAho 对象并向其中添加一些键（可选地，每个键可以有不同的负载）。

from noahong import NoAho

trie = NoAho()

# fill with .add()
trie.add("foo", "id_foo")
trie.add("foobar", "id_foobar")

# or fill with __setitem__
trie["bar"] = "id_bar"

一旦添加了不同的键和它们的负载，就需要编译 NoAho 对象。

trie.compile()

一旦编译完成，就不能再向 NoAho 对象中添加键。

noahong 然后公开了四个函数，用于在文本中查找匹配的子字符串。

find_short

trie.find_short(text) 查找 text 中第一个与 trie 中添加的键匹配的子字符串。

它返回一个元组 (start, stop, payload)，其中

• payload 是使用 trie.add() 插入的对象。
• start 和 stop 是匹配在 text 中的索引： text[start:stop] == key

例如，使用上面的 trie

trie.find_short("something foo")
# returns (10, 13, 'id_foo')
# "something foo"[10:13] == "foo"

即使较长的匹配可能从同一位置开始，也返回第一个匹配

trie.find_short("something foobar")
# returns (10, 13, 'id_foo')

find_long

trie.find_long(text) 查找 text 中第一个最长匹配的子字符串，该子字符串与 trie 中添加的键匹配。

例如，使用上面的 trie

trie.find_long("something foobar")
# returns (10, 16, 'id_foobar')

findall_*

find_short 和 find_long 都有 findall_short 和 findall_long 对应的版本，允许您遍历在文本中找到的所有非重叠匹配。

for x in trie.findall_long("something foo bar foobar"): 
    print(x)       

# prints                          
# (10, 13, 'id_foo')
# (14, 17, 'id_bar')
# (18, 24, 'id_foobar')

因为匹配是非重叠的

list(trie.findall_short("foobar")) == [(0, 3, "id_foo"), (3, 6, "id_bar")]

而

list(trie.findall_long("foobar")) == [(0, 6, "id_foobar")]

负载

NoAho 尝试接受任何 Python 对象作为负载。

trie = NoAho()
trie.add("foo", 0)
trie.add("bar", CustomClass())
trie.add("baz", lambda x: x)

相同的负载可以与不同的键关联。

注意，不可拾取的 lambda x: x 负载可以正常工作，因为没有涉及序列化。

长度和包含

NoAho trie 对象还通过 len 暴露键的数量。

len(trie)

并且，当它们被编译时，可以用来测试键的包含。

"foo" in trie

可以通过以下方式恢复底层 Trie 的节点数

trie.nodes_count()

映射 NoAho

为了节省内存，noahong 公开了可以写入磁盘并在以后直接加载到内存中进行匹配的 Mapped 匹配对象，从而具有更小的内存占用。

Mapped 对象公开不同的查找方法，仅支持整数负载。

通过向 NoAho 对象添加键和负载来构建它。

from noahong import NoAho, Mapped

trie = NoAho()
trie.add("baz", "id_baz")

trie.compile()
trie.write("./test.matcher")

mapped_trie = Mapped("./test.matcher")

mapped_trie 对象公开一个 findall_anchored 函数，该函数遍历 锚定 匹配，这些匹配可以找到具有特殊“锚”字符 \u001F 设置的边界内的匹配。

这有助于将匹配限制在仅存在于，例如，空格之间。

trie = NoAho()
trie.add("foo", 0)
trie.add("bar", 1)

trie.compile()
trie.write("./test.matcher")

mapped_trie = Mapped("./test.matcher")
mapped_trie.findall_anchored("\u001Fbar\u001F\u001Ffoo\u001F\u001Ffoobar\u001F")

# returns [(1, 4, 1), (6, 9, 0), (11, 14, 0)]

注意 "bar" 在最终的 "foobar" 中没有被找到，因为它不在“锚”字符之间。

可以在键中放置锚字符

trie = NoAho()
trie.add("foo\u001F\u001Fbar", 0)
trie.add("foo", 1)
trie.add("bar", 2)

trie.compile()
trie.write("./test.matcher")

mapped_trie = Mapped("./test.matcher")
mapped_trie.findall_anchored("\u001Ffoo\u001F\u001Fbar\u001F")
# returns [(1, 9, 0)]

在这种情况下，返回锚字符之间的最长键。

安装

Devpi

noahong 在 devpi 上可用。

pip install noahong

Python 3

noahong 可以手动安装。

python3 setup.py install

旧版 README

您可以通过阅读在此处找到的旧版 README 获取有关包和 C++ 实现的更多信息：这里。