Treesimi
计算树之间的相似度,例如依赖树
将邻接表转换为嵌套集表
例如,CoNLL-U的['id', 'head']字段形成依赖关系树的邻接列表。 遍历邻接表比读取嵌套集慢。 因此,如果我们以后需要多次读取这三个表,则将邻接表一次转换为嵌套集表是有意义的。
import treesimi as ts
adjac = [( 1 , 0 ), ( 2 , 1 ), ( 3 , 1 ), ( 4 , 2 )]
nested = ts . adjac_to_nested ( adjac )
# columns: node id, left, right, depth
# [[1, 1, 8, 0], [2, 2, 5, 1], [4, 3, 4, 2], [3, 6, 7, 1]]
演示:查询嵌套集表
要提取子树,我们只需要遍历列表($ O(n)$)
_ , lft0 , rgt0
2021-12-22 17:01:00
24KB
Python
1