[[424148]]

前幾天，有個朋友向我推薦了一個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