Polytree 的随笔
共 2807字，需浏览 6分钟
· 2021-09-17
前几天，有个朋友向我推荐了一个github 的开源项目https://github.com/OhBonsai/RedisTree, 可以用redis 直接读写polytree 的数据结构，挺有意思的。那么， 什么是polytree 呢？
数据结构与树
当我们说数据结构的时候，在我们的脑海里呈现的可能是一棵如下的树：
也就是说， 数据结构大体可以分为两类：线性数据结构和非线性数据结构。线性数据结构中常见的有数组，链表，栈和队列；非线性数据结构主要是树和图。
虽然不是自举，但我们实际上用『树』来描述了数据结构。树数据结构定义为对象或实体（称为节点）的集合，这些对象或实体链接在一起以表示或模拟层次结构。树数据结构是一种非线性数据结构，因为它不按顺序存储。它是一种层次结构，因为树中的元素被安排在多个级别。『树』中的常用术语大致如下：
基于树中子节点的多少以及子节点自身的属性，形成了各种各样的树，且树的应用场景非常广泛，例如计算机系统的文件系统，计算简单或复杂的数学表达式，这时的树是一种特殊的树，称为表达式树，二叉树支持O（logN）平均时间内的搜索操作等等。
polytree 及其特点
polytree一词由Rebane和Pearl于1987年创造。Polytree是一个有向无环图的特例，任意两个顶点之间最多有一条无向路径的图。换句话说，一个有向无环图，其中可从任何节点到达的子图形成一棵树。关于有向无环图可以参考《有向无环图（DAG）的温故知新》。
图是一个神奇的东西，图论是应用数学中应用极其广泛的一类，在计算机科学中也是如此，日常生活中其实也很广泛；任意一种网络，都是一种图；思维导图也是一种图；鄙视链同样是一种图；网格其实也是图，等等。不管是什么结构，只要结构中的对象存在一种二元联系，就总可以找到一个图来描述它，用一些有向边或无向边把一些点连起来，无所谓其中边的长度；如果是多元关系，可以用超图表示。
具体考虑一个 polytree，线性预处理可以插入中间节点并折叠只有一个子节点的节点，从而得到一个polytree，可以使用该polytree来回答对原始polytree的查询，因此，可以在不损失一般性的情况下假设𝑃 正好有2个度。按照任何拓扑顺序自底向上进行线性时间预处理，对于每个节点𝑃 我们将为节点构造一个索引结构，我们称之为“中缀树（infix tree）”，它还可能包括指向其他先前定义的此类结构的指针。
在线性时间内构造polytree，对于任何节点，都可以通过恒定延迟枚举其中缀树。
中缀树中有三种节点：
叶子节点，用至少一个且最多四个元素的显式集合标记（是原始polytree的叶子）；
小型内部节点，用一个显式元素和指向一个或两个中缀树节点的指针标记；
大型内部节点，用两个显式元素和指向一个或两个中缀树节点的指针标记。
进一步要求中缀树中没有重复的元素，即，对于中缀树的每个节点𝑥，P 的每一片叶子在标签中最多显示一次𝑥。节点𝑥 在中缀树中，是对P的叶子节点进行编码的集合𝑆(𝑥)。中缀树的思想是，通过保留一些显式元素，我们既可以在枚举时使用它们，以便快捷地访问节点，也可以在合并时使用它们，以便有足够多的元素来标准中缀树中新创建的节点。
索引的数据结构将polytree的每个节点𝑛 映射到可到达的叶子节点 𝑁(𝑛) ，𝑆(𝑁(𝑛)) 是𝑃中的节点可达的叶子节点集合。那么，可以得到Polytree 的两个如下特性：
在线性时间内可以做到这一点；
可以在恒定的延迟中完成枚举。
polytree的应用
polytree树的典型应用之一是用作概率推理的图模型。如果贝叶斯网络具有polytree的结构，则可以使用信念传播有效地对其进行推理。
实际上，polytree还有很多更为具体的应用，例如复调音乐是一种共时、离散的时间序列，通常被表示为一维的events序列，或者二维的piano roll，缺点是music knowledge不够多，不能体现复调音乐的内在结构。而基于polytree的树结构，包含三个级别：时间序列——音符——音符属性，
再以一个Encoder-Decoder网络来学习复调音乐的latent representation，整体模型架构如下：
在钢琴表征学习任务实验结果显示，polytree在重建准确性和模型泛化方面优于baseline。
几乎同名的prollytree
创造新名词是IT界的最爱， 国内外差不多都是如此。Norms 为了创建一个类似git 的去中心化数据库，提出了Prolly Tree，虽然几乎同音，但实际上咫尺天涯。
Prolly Tree 全称是Probabilistic Merkle B-Trees，集成了B树和merkle 树，结构示例如下：
因此，prolly tree 具有B树高效随机读写和有序扫描的特性，同时拥有merkle 树的可验证性以及包括/排除的可证明性，具体的属性如下表所示：
Norms 项目以prollytree 作为核心的数据结构，试图实现一个去中心化的数据库，是一个积极的尝试。
小结
当觉得它没有什么意思的时候，或许是因为我们对它缺乏了解；当觉得它有点意思的时候，或许我们才刚刚走在了应用的路上。老码农对polytree的感知如是，给予不同的约束，我们可以得到不同的树，进而应用到不同的业务场景。
【参考资料与关联阅读】
Incremental Dynamic Construction of Layered Polytree Networks，https://arxiv.org/abs/1302.6833
https://ldzhangyx.github.io/2019/10/30/polytree/
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/05/prml-slides-8.pdf
https://cstheory.stackexchange.com/questions/37262/efficient-enumeration-of-the-reachable-leaves-of-nodes-in-a-polytree
https://github.com/attic-labs/noms