title: 多叉树treelib&区间树intervaltree
subtitle: 多叉树相关以及区间树三方库介绍
date: 2021-03-04
author: NSX
catalog: true
tags:
- 多叉树treelib
- 区间树intervaltree

  • treelib 库是一个 Python 的第三方库。这个库实现了一些多叉树相关的常用方法。
  • intervaltree库是一个可变的、自平衡的区间树。查询可以按点、按范围重叠或按范围包含。

    treelib 库

用于构建多叉树

  1. #创建一棵多叉树
  2. #show(): 将多叉树按树形结构展示输出
  3. from treelib import Tree, Node
  4. tree = Tree()
  5. tree.show()
  6. print(tree.identifier)
  8. #添加节点到多叉树中
  9. tree.create_node(tag='Node-5', identifier='node-5', data=5)
  10. tree.create_node(tag='Node-10', identifier='node-10', parent='node-5', data=10)
  11. tree.create_node('Node-15', 'node-15', 'node-10', 15)
  12. tree.show()
  14. node = Node(tag='Node-A', identifier='node-A', data='A')
  15. tree.add_node(node, parent='node-5')
  16. tree.show()
  18. """
  19. Node-5
  20. └── Node-10
  21.     └── Node-15
  23. Node-5
  24. ├── Node-10
  25. │   └── Node-15
  26. ├── Node-A
  27. """
  29. #节点的属性和方法
  30. print(node)
  31. print('node id: ', node.identifier)
  32. print('node tag:', node.tag)
  33. print('node data:', node.data)
  34. print('node is leaf: ', node.is_leaf())
  35. print('node is root: ', node.is_root())
  37. #多叉树中的节点个数
  38. print('tree len: ', len(tree))
  39. print('tree size:', tree.size())
  41. #多叉树的深度和叶子节点
  42. print('tree depth:', tree.depth())
  43. print('node-20 depth:', tree.depth(node='node-20'))
  44. print('node-20 level:', tree.level('node-20'))
  45. print('tree leaves:', tree.leaves())    #返回多叉树的所有叶节点
  46. print(tree.paths_to_leaves())  #返回根节点到每个叶节点的路径上的所有节点id
  48. #返回多叉树中的节点
  49. print('tree nodes:', tree.nodes)
  50. print(tree.all_nodes())
  51. for node in tree.all_nodes_itr():
  52.     print(node)
  54. #多叉树转换成字典和保存到文件中
  55. print(tree.to_dict())
  56. print(tree.to_json())
  57. tree.to_graphviz()
  58. tree.save2file('demo_tree.tree')

应用：通过多叉树解决嵌套实体的问题

  1. class Nodex(object):
  2.     def __init__(self, tmp):
  3.         self.tmp = tmp
  5. def cross_judge(item_a, item_b):
  6.   """判断实体之间是否存在交集
  7.   """
  8.     a1, b1 = item_a["char_offset"], item_a["char_offset"] + item_a["char_length"]
  9.     a2, b2 = item_b["char_offset"], item_b["char_offset"] + item_b["char_length"]
  10.     if max(a1, a2) < min(b1, b2):
  11.         return True
  12.     else:
  13.         return False
  15. def get_slot_dic_from_tree(result_tmp):
  16.     """通过多叉树输出嵌套实体（非包含关系）的排列组合结果
  17.     result_tmp: 实体相关信息 ↑
  18.     """
  19.     tree1 = Tree()
  20.     tree1.create_node("Root", "root", data=Nodex(-1))  #  根节点
  21.     root2leave = []
  22.     if result_tmp:
  23.         result_tmp.sort(key=lambda x: x["char_offset"])
  24.         # 第一个new_node直接加入tree
  25.         tree1.create_node("Child0", "child0", parent="root", data=Nodex(result_tmp[0]))
  26.         for i in range(1, len(result_tmp)):
  27.             parent_idt_list = []
  28.             # 每个new_node与所有的叶子结点进行比较
  29.             for j, leaf in enumerate(tree1.leaves()):
  30.                 idt = leaf.identifier  # 叶子结点标识符
  31.                 parent_idt = tree1.parent(idt).identifier  # 父结点标识符
  32.                 node_a = Node(
  33.                     tag="Child" + str(i) + "_" + str(j),
  34.                     identifier="Child" + str(i) + "_" + str(j),
  35.                     data=Nodex(result_tmp[i]),
  36.                 )
  37.                 # 1、如果存在嵌套（冲突），则父节点增加新分支
  38.                 if cross_judge(result_tmp[i], leaf.data.tmp):
  39.                     # 针对相同的new_node，父节点仅可增加一个新分支
  40.                     if parent_idt not in parent_idt_list:
  41.                         tree1.add_node(node_a, parent=parent_idt)
  42.                         parent_idt_list.append(parent_idt)
  43.                 # 2、否则，当前节点加深
  44.                 else:
  45.                     tree1.add_node(node_a, parent=idt)
  46.         # 最后返回【根节点→叶子结点】的所有路径，即所有不存在嵌套实体的排列组合结果
  47.         for path in tree1.paths_to_leaves():
  48.             item = [tree1.get_node(idt).data.tmp for idt in path[1:]]
  49.             root2leave.append(item)
  50.     return root2leave

图示解决过程：
NER核心处理逻辑.drawio.png

intervaltree库

判断多个区间是否有重叠：利用intervaltree构建区间树，也即构建一个二叉排序树，树的叶节点是每个区间。同时，树的查询效率和树的深度是有关系的，所以构建一个相对平衡的二叉排序树也能进一步提高效率，比如红黑树。算法导论上介绍了这种数据结构，节点是区间的红黑树——区间树。

  1. >>> from intervaltree import Interval, IntervalTree
  3. >>> tree = IntervalTree()
  4. >>> iv = Interval(4, 7)
  5. >>> tree.add(iv)
  7. >>> target_iv = Interval(5, 8)
  8. >>> tree.overlaps(target_iv)
  9. True
  10. >>> target_iv_2 = Interval(7, 10)
  11. >>> tree.overlaps(target_iv_2)
  12. False

应用：如“今天8点到10点, 8个人”提取时间和人数时，idx=text.find(x)只能查找第一个时间“8”出现位置的索引，导致人数“8”的位置被覆盖了。解决：在发现实体区间有重叠时，循环执行 idx=text.find(x, idx+1)，直到-1跳出；

  1. # 寻找最适合的索引
  2. interval_tree = IntervalTree()  # 用于判断实体区间的重叠情况！
  3. char_offset = text.find(x.upper())  # first
  4. while char_offset!=-1:
  5.     target_iv = Interval(char_offset, char_offset+len(x))
  6.     is_overlaps = bool(interval_tree.overlaps(target_iv))
  7.     if is_overlaps:    # 有重叠，则继续找，直到-1跳出
  8.         char_offset = text.find(x.upper(), char_offset+1)
  9.     else:    # 无重叠，直接跳出
  10.         interval_tree.add(target_iv)
  11.         break
  12. if char_offset==-1:
  13.     char_offset = text.find(x.upper())  # first

参考

Python treelib库创建多叉树的用法介绍

Python多叉树的构造及取出节点数据(treelib)的方法

treelib官方文档

判断多个区间是否有重叠

区间重叠计算及IntervalTree初识