prefix_tree

prefix_tree(paths)

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

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

“前缀树”表示字符串的前缀结构。每个节点代表某个字符串的前缀。根表示具有单个字母前缀的子项的空前缀，每个双字母前缀又具有子项，每个双字母前缀以对应于父节点的单个字母开始，依此类推。

更一般地，前缀不需要是字符串。前缀指的是序列的开始。根元素的每个元素前缀都有子项，每个以父项的一个元素序列开头的两个元素前缀都有子项，依此类推。

请注意，此实现使用具有属性的整数节点。每个节点都有一个属性“source”，它的值是该节点对应的路径的原始元素。例如，假设 paths 由一条路径组成：“能”。然后是节点 [1, 2, 3] 代表这条路径的值有“源”值“c”、“a”和“n”。

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

根节点始终为 0 并具有“源”属性 None 。根是唯一具有零度的节点。Nil节点始终为 -1 并具有“源”属性 "NIL" 。零节点是唯一的出度为零的节点。

参数

paths: iterable of paths

路径本身为序列的可迭代路径。利用前缀树的节点来识别这些序列之间的匹配前缀。树的一片叶子与每条路径相关联。(相同的路径与树的同一叶相关联。)

返回

树：有向图

表示由生成的前缀树组成的树状结构的有向图 paths 。节点被“向下”定向，从父节点到子节点。添加一个特殊的“合成”根节点作为每条路径中第一个节点的父节点。一种特殊的“合成”叶节点，即“nil”节点 -1 被添加为表示路径中最后一个元素的所有节点的子节点。(从技术上讲，添加此nil节点使其不是树状结构，而是有向无环图；删除nil节点使其成为树状结构。)

笔记

前缀树也称为 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)]

叶节点可以作为nil节点的前置节点获得：：

>>> 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']