持久化數據結構學習筆記——序列

02-20

前言

本學期正在修讀一門數據結構課程，內容是持久化數據結構（Persistent Data Structures）。我感到這門課的內容十分有趣，希望可以寫一些筆記記錄一下學習過程。筆記的內容將會圍繞課程展開，但是其中主要是我自己的一些思考得出的「私貨」。

我們日常接觸到的數據結構多是可變的（mutable），這意味著對於一個數據結構的更新將會破壞其過去的版本。與之相對應的，持久化數據結構在更新時會創建一個「新」的數據結構，從而與此同時保證對舊有版本的訪問與修改。持久化數據結構可以帶來許多好處，比如異常安全（Exception Safety）和並發性（Concurrency）。但是，這並不意味著我們必須為此付出很大的代價。實際上，許多持久化數據結構在實現上會更加自然直觀，也可以保持很高的效率。

持久化數據結構與不可變性（Immutability）有一些相關性。我們往往會利用不可變性來實現高效率的持久化數據結構。不可變性保證了同一數據結構的不同版本可以共享相同的部分，從而節省達到節省空間的目的。

讓我們從最簡單的例子開始。

序列

序列（Sequence）是一種抽象數據類型（Abstract Data Type）。它由四個函數定義：

emtpy 返回一個空序列
first 作用在一個序列上，返回其第一個元素
rest 作用在一個序列上，返回除去其首元素以後的新序列
cons 作用在一個元素和一個序列上，返回一個新的序列，使得 first (cons h t) = h 與 rest (cons h t) = t 成立

在OCaml中，上述定義表達如下

module type sequence = sig type a sequence val empty : a sequence val first : a sequence -> a option val rest : a sequence -> a sequence option val cons : a -> a sequence -> a sequence end

在函數式語言中常見的列表（List）就是一個符合本定義的數據結構。值得注意的是列表就是一個持久化數據結構的簡單例子。列表是非常高效的，上述函數的時間複雜度均為 $O(1)$ ，同時其不可變性保證了高效的內存利用與持久性。

但是，如果我們並不需要頻繁使用以上操作，而希望我們的序列有相對高效的隨機訪問呢？我們在之前的序列定義中添加一個新的介面 index : int -> a sequence -> a option ，作用在一個整數和一個序列上，返回其對應位置的元素。符合我們要求的新的實現可以有相對較慢的 rest 和 cons ，但是需要有比 $O(n)$ 更快的 index 。一個自然的想法是使用樹狀的結構代替線性結構提高訪問效率。

第一個嘗試

我們選擇使用二叉樹來存儲（編碼？encode?）一個序列結構，這要求我們在序列的位置和二叉樹的中存儲元素的位置之間建立一個雙射。一個比較顯而易見的做法是選取一棵深度為 $k$ 的滿二叉樹，用他的所有葉子結點來存儲數據。葉子結點從左向右分別標註為 $0$ 至 $2^{k-1}-1$ 。這樣我們建立了這棵樹的葉子結點和序列中的位置的一一對應。並不令人意外的是，這種對應關係實際上就是 $0$ 至 $2^n-1$ 的自然數的 $n$ 位二進位（高位補全 $0$ ）表示。這一關係給出了一個查找我們的二叉樹中的元素的方法：將序列中的位置轉換成二進位表示，補齊高位的零，然後從二叉樹的根節點開始，按照二進位表示的從高位到低位，逢0向左逢1向右，直至達到葉子結點。

以上思路給出了一個看似可能的實現。但是，這一次嘗試中我們只使用了二叉樹的葉子結點，造成了空間的浪費。這一點並沒有真的影響到我們的實現的空間複雜度。但是，它暴露出了一件更重要的事情：我們的思路引入了不必要的信息，而這是不自然的。

解決方法

讓我們試著分析一下這件事的原因是什麼。我們為了讓自然數和它的二進位表示是一一對應，必須限定二進位表示的位數，同時對位數不足的二進位表示補全高位的0。這種關係是我們人為限定的，而我們引入的冗餘信息就是對二進位表示的位數的限定，與之相對應的，就是我們只使用了二叉樹的葉子結點，而空置了其餘節點。那麼，解決這個問題的思路似乎明朗了。我們需要找尋一種自然數的表示，它必須是base-2的（只使用兩種符號，與二叉樹的結構對應），使得他是一種同構計數（Bijective Numeration）。換句話說，我們需要的表示是一個由兩種字元 ${a,b}$ 構成的任意長度的字元串。我們需要做的就是賦予這些字元串組成的集合 ${a,b}^*$ 一個到自然數集的雙射。

我們選取 $1$ 和 $2$ 來組成這個字元串。我們用空字元串 $varepsilon$ 來表示 $0$ ，用 $a_n…a_1a_0$ 表示 $sum_{i=0}^n a_i2^i$ ，其中 $a_iin{1,2}$ . 例如： $4$ 被表示為 $12$ ， $7$ 被表示為 $111$ 。容易證明這種表示是一個雙射。這是一種常用的計數方法，被稱為bijective base-2 numeration。

由此，我們可以得到一個更緊湊的在二叉樹中存儲序列的方法。將表示序列位置的自然數展開成它的bijective base-2表示（展開方法類似二進位數），然後從樹的根節點、二進位表示的最高位開始逢1向左逢2向右直至走完，停止的位置就是在二叉樹中應該存放的位置。直觀上看，二叉樹中的節點被我們從上到下從左到右依次標註。

如果我們選用這樣的結構，first 和 index 的實現是顯然的。隨著元素增多，這棵樹的形態始終是接近滿的，這保證了index 一定是 $O(log n)$ 的。但是，似乎並沒有一個直觀的方法提示我們應該如何高效的實現 cons 和 rest。究其原因，每當我們插入新元素或者去除舊元素時，樹的結構會被破壞，每一個其中的元素的位置都會受到影響。同時，甚至是 index 的實現都是不甚自然的，因為我們需要首先展開一個自然數，完整存儲這個結果，再從高到低使用。那麼，如果我們使用逆序的bijective base-2 numeration呢？

新的結構 Braun tree

考慮一個序列 $varepsilon,1,2,11,12,21,22,…$ 如果把它們當作逆序以後的表示，即 $a_0a_1…a_n$ 表示 $sum_{i=0}^n a_i2^i$ ，那麼這個序列將對應 $0,1,2,3,5,4,6,…$ 用這樣的表示來編碼二叉樹中的位置，我們會得到結構如下的樹：

這樣的樹被稱為Braun tree。這個改變看似只是方便了我們實現index，但它卻具有更大的意義。Braun tree 具有如下的性質：

Braun tree的左支和右支都是Braun tree
Braun tree的左支的元素個數只可能和右支相等或多1

第二條性質保證了Braun tree總是平衡的的，我們可以高效的訪問它的節點。第一條性質保證了我們可以方便地遞歸實現對於Braun tree的一些操作。同時，我們發現對於任意的 $i$ ，序數是 $2i+1$ 的元素和 $2i+2$ 的元素總是在同一父節點的左右子樹中處在同一個位置。這個性質和我們選取的自然數的逆序同構表示是直接相關的。這一性質為我們提供了高效實現 cons 和 rest 的思路。

當我們想要在Braun tree的根節點增加新元素時，我們新增元素替換了舊的根節點元素。由於上述性質，新的二叉樹的右子樹將是當前的左子樹，新的左子樹將是舊的二叉樹的右子樹增加了舊根節點元素以後的結果。我們可以遞歸地將根節點替換，將舊元素插入右子樹，然後交換左右子樹。

OCaml 實現

我們按照上述討論在OCaml中定義Braun tree，並聲明它是序列的一種實現：

type a brt = Empty | Node of a * a brt * a brttype a sequence = a brt

empty 與 first 的實現非常顯然，在此不做贅述。cons 應當對它作用的的Braun tree進行判斷，如果為空則返回只有一個節點的樹，否則按照我們的討論返回一個新的樹，其根節點是新的元素。cons 實現如下：

let rec cons x = function Empty -> Node (x, Empty, Empty) | Node (x, lt, rt) -> Node (x, cons x rt, lt)

要實現 rest ，更容易入手的方法是實現cons 的逆運算uncons。cons 作用在一個元素和一棵樹上，返回一棵新樹。uncons 則應當作用在一棵樹上，「拆解」出它的根節點，並返回根節點元素和一棵由剩餘元素組成的樹。考慮到cons的值域中沒有Empty，uncons 的返回值應當是一個 option 類型。因此，uncons 的類型應當為 a sequence -> (a * a sequence) option。

由於uncons 是 cons的逆運算，它的實現可以直接得到。對於空的樹，我們應當返回None。而對於非空的樹，我們返回的「拆解」下的元素則為當前的根節點。同時我們應當對這棵樹的左子樹（由舊的樹的右子樹cons舊的根節點得到）遞歸地進行uncons，如果返回結果是一個元素和一棵樹構成的二元組，那麼我們返回的樹的根節點為遞歸返回的元素，左右子樹分別是當前的右子樹和遞歸返回的樹。如果遞歸返回的結果是None，返回的樹應當為空。在OCaml中實現如下：

let rec uncons = function Empty -> None | Node (x, lt, rt) -> match uncons lt with None -> Some (x, Empty) | Some (x, lt) -> Some (x, Node (x, rt, lt))let rest t = match uncons t with None -> None | Some (_, t) -> Some t

index 我們已經進行了詳細的討論，它的實現在此按下不表。

分析總結

上述的實現保證了持久性，同時有相對較高的效率。cons rest index 的時間複雜度均為 $O(log n)$ ，同時由於我們的實現是不可變的，新舊版本的樹可以共享數據和節點。值得注意的是想要用 $n$ 個元素創建一棵Braun tree可以在 $O(n)$ 的時間完成，具體的實現參見文末Okasaki的文章。

Braun tree的序列實現並不是非常的高效，但至少是可用的。同時Braun tree本身是一種在持久化數據結構中時常出現的數據結構，它被用來實現很多複雜的數據結構。除此以外，實際應用中也有和傳統的序列（如C++ vector）一樣高效的持久化實現，比如Clojure的persistent vector。

參考資料

Three Algorithms on Braun Trees by Chris Okasaki