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