prefix_tree#

prefix_tree(paths)[source]#

从路径列表创建一个有向前缀树。

通常，路径被描述为字符串或整数列表。

“前缀树”表示字符串的前缀结构。每个节点表示某个字符串的前缀。根节点表示空前缀，其子节点表示单字母前缀，这些单字母前缀的子节点表示以该单字母为起始的双字母前缀，依此类推。

更一般地，前缀不必是字符串。前缀指的是序列的开始部分。根节点有每个单元素前缀的子节点，它们有每个以父节点的单元素序列为起始的双元素前缀的子节点，依此类推。

注意，此实现使用具有属性的整数节点。每个节点都有一个“source”属性，其值是与此节点对应的路径的原始元素。例如，假设 paths 包含一个路径：”can”。那么表示该路径的节点 [1, 2, 3] 的“source”值分别为 “c”, “a” 和 “n”。

一个节点的所有后代在与其关联的序列/路径中具有共同的前缀。通过返回的树，可以通过遍历树到根节点并沿途累积“source”值来构建每个节点的前缀。

根节点始终为 0 ，并且具有“source”属性 None 。根节点是唯一入度为零的节点。空节点始终为 -1 ，并且具有“source”属性 "NIL" 。空节点是唯一出度为零的节点。

Parameters:
paths: 路径的可迭代对象

一个路径的可迭代对象，这些路径本身就是序列。 这些序列中的匹配前缀通过前缀树的节点来识别。树的每个叶子节点与一个路径相关联。（相同的路径与树的同一个叶子节点相关联。）

Returns:
tree: DiGraph

一个表示由 paths 生成的树形结构的有向图。节点从父节点指向子节点。添加了一个特殊的“合成”根节点，作为每个路径中第一个节点的父节点。添加了一个特殊的“合成”叶子节点，即“空”节点 -1 ，作为表示路径中最后一个元素的所有节点的子节点。（添加此空节点在技术上使其不是一个树形结构，而是一个有向无环图；移除空节点使其成为一个树形结构。）

Notes

前缀树也称为 trie。

Examples

从具有共同前缀的字符串列表创建前缀树:

>>> paths = ["ab", "abs", "ad"]
>>> T = nx.prefix_tree(paths)
>>> list(T.edges)
[(0, 1), (1, 2), (1, 4), (2, -1), (2, 3), (3, -1), (4, -1)]

可以通过空节点的先驱节点获取叶子节点:

>>> root, NIL = 0, -1
>>> list(T.predecessors(NIL))
[2, 3, 4]

要从生成前缀树的原始路径中恢复，从节点 -1 遍历到节点 0

>>> recovered = []
>>> for v in T.predecessors(NIL):
...     prefix = ""
...     while v != root:
...         prefix = str(T.nodes[v]["source"]) + prefix
...         v = next(T.predecessors(v))  # 只有一个先驱节点
...     recovered.append(prefix)
>>> sorted(recovered)
['ab', 'abs', 'ad']
On this page