prefix_tree#

prefix_tree(paths)\[source]#

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

路径通常表示为字符串或整数列表。

“前缀树”表示字符串的前缀结构。每个节点代表某个字符串的一个前缀。根节点代表空前缀，其子节点代表单字符前缀；单字符前缀的子节点代表以父节点对应单字符开头的双字符前缀，依此类推。

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

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

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

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

参数：
paths：路径的可迭代对象

一个路径的可迭代对象，这些路径本身也是序列。这些序列中匹配的前缀会被标识为前缀树的节点。树的一个叶节点与每条路径关联。（相同的路径与树的同一个叶节点关联。）

返回：
tree：有向图

一个有向图，表示由 paths 生成的前缀树组成的有根树（arborescence）。节点方向是“向下”的，从父节点指向子节点。添加了一个特殊的“合成”根节点，作为每条路径中第一个节点的父节点。添加了一个特殊的“合成”叶节点，即“空”节点 -1，作为表示路径中最后一个元素的所有节点的子节点。（严格来说，添加此空节点使其不再是有根树，而是一个有向无环图；移除空节点则使其成为有根树。）

注意

前缀树也称为 trie。

示例

从包含共同前缀的字符串列表创建前缀树

>>> 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))  # only one predecessor
...     recovered.append(prefix)
>>> sorted(recovered)
['ab', 'abs', 'ad']
在本页