用樹結構描述和計算資料展望

描述資料最常見的結構是平面表格，資料庫，excel,csv都是典型的表格。表格是扁平結構，了解起來簡單，能友善的增删改查。 

下面是一個典型的表格:

時間

小時

分鐘

12:03

12

03

15:32

15

32

從上面的表格，明顯能看出表格的缺陷：

所有的子項都是平級的，無法描述它們内在的結構

列名很重要，否則很難确定其語義，這和第一條相輔相成

在資料深度上進行規約和下鑽時，不可避免的會造成資料重複。

對列的描述，無法直接儲存在表格中，還需要另外建立資料結構存儲

如果我們将上面的表格描述成下面的樹，這些問題就變得容易解決了：

(父節點) 

(子節點)12

(子節點):

(子節點)03

是以，父節點不需要存儲資料，其值是子節點資料的組合，不會有重複。能夠明确的描述資料的層級關系和結構，支援在不同層級檢索資料，對上面的例子，第一層是12:03, 細分之後，第二層是12和03。

是以，将表格轉換為樹，筆者将其稱為樹表，可能會是兩種情況：

結構一緻的樹的森林，每一棵樹代表一行資料

隻有一棵樹，每個樹節點是數組，分别對應了表格中的一列

推薦使用第二種，這樣就能友善地将列的元屬性記錄在節點中，而不造成重複，也可以很容易的将樹表打平，變成普通表格。樹結構是遞歸的，是以支援遞歸操作，下面将讨論樹表可能的操作類型。

對樹子節點的描述，通常有兩種：

将子節點作為數組，儲存在父節點中

将子節點儲存為連結清單，隻将頭結點儲存在父節點中

第二種方法的優點，比缺點多得多。第二種除了對子節點的索引通路不易之外，其他的操作都要比第一種友善。不用預先聲明長度，能友善地拼接,删除。 

但最大的優點，是能夠友善的實作緩存機制。重複的資料，能讓多個節點指向同一個連結清單頭結點，實作複用。而第一種方案則會複雜得多。 

是以，我們采用第二種政策作為樹表的存儲結構。

在不同節點讀取資料，值為子節點值的組合

在不同節點寫入資料，節點負責将資料配置設定到不同子節點存儲

删除一個節點，對應的子節點都會被删除

展平一個節點，将該節點替換為其子節點的頭結點

将節點拼接到其他子節點上

描述嵌套結構，子節點的下一個節點指向父節點。

同級節點的推導，如果父節點提供計算能力，則子節點能夠被計算并傳回結果

轉換為xml,json等遞歸結構類型

從html中自動提取樹表 

這幾乎是樹表最正常的用途，随便看一個html的例子，資料都是以樹結構存儲的，沒有明确的列名，但其層級關系卻表現了資料的關聯性。

我們很難通過樹結構，自動标注“1997年建闆樓”的列名，但卻知道，它和“中樓層”屬于一個層級。這樣，自動清洗html就會友善地多。

資訊抽取 

資訊抽取的結果，一般是樹，還是之前時間的例子，12:03提取子資訊後，就變成了12點和03分，分别成為了12:03的兩個子節點。 

這也同樣避免了生成多個列，造成資料重複的問題。

自動推導 

對編譯原理有概念的同學，自然會對文法樹有印象。文法樹代表了目前語句的邏輯結構，分析文法樹，能夠發現無用備援節點，或進行規約計算。例如加法(+)的父節點，如果有兩個int子節點，那麼就可以求和。 

一樣的道理，如果在同一層級，分别有長度和寬度，那麼這兩個名額一般衡量的都是同一個“物體”，那麼自然就可以增加“面積”子節點。 

同時，節點可以代表“動作”，也可以儲存函數，那麼樹表本身就提供了自動推導的能力。 

節點的上浮/下沉，都可以通過規則自動實作，而之前對資料上鑽和下探，都可以了解為觀察樹不同的層級而已。 

這極大地簡化了程式設計/推導，甚至能實作一個簡單的人工智能。

易于實作lazy執行 

是否延遲執行，可根據實際要求來決定。如果父節點計算代價高昂，那麼可緩存子節點計算值，否則可随時傳回子節點的規約新值。 

想要讓平面表支援延遲執行，肯定不會太容易。

資料就是對象 

想象一下，以後通路一個資料表，都能通過object.property.subproperty來通路了，那種感覺多爽，還要什麼orm!

樹表最大的缺陷，是它對使用者不友好，了解扁平的表結構是很容易的，但如果看到一片森林，肯定不少程式員會暈菜，普通使用者更是不必說，是以這種審查資料的方式顯然隻應該在背景，面向程式員。 

我們可以用excel等工具友善地檢視表結構，但樹表怎麼看？這也同樣需要可視化設計器，好在這種事情是苦力活，并不難做。

想象一下以後如何處理和清洗資料，把樹的某個節點拖到垃圾箱，這一列就自動删除了，可以建立某個層級的節點，然後添加幾個節點的連線，它就自動成了它們的父節點；節點和節點之間可以插入新的計算節點，定義新的層級。也可以随時檢視不同層級的資料，進而實作更好的洞察力。這一切簡直太酷了。

這個問題，确實是我在實際開發爬蟲和資料清洗工具時遇到的，平面表格大量的中間計算結果，重複列，無法定義的列名，讓我深感平面模式的弊端，我甚至都已經迫不及待地開發這樣的資料處理工具，以替代之前的工具。不過，在一切都不明朗之前，這種計劃還是往後推一推吧。

有任何問題，歡迎随時讨論。