如何更有效地將有序樹編碼爲位序列

Question

假設我們要保存n節點的有序樹形狀，每個節點最多有2個子節點。 如果它是一個二叉樹，我們必須使用2n位。因爲在我們的情況下，我們沒有左或右的孩子，他們是一樣的，所以我們必須有一些冗餘的序列。那麼，我們可以用更好的方式對它進行編碼嗎？看來每個節點仍然有3個案例，沒有孩子，一個孩子，兩個孩子，但是我們可以將它存儲在少於2位的位置嗎？或總共有一個更好的常數比2？

Answer 1

你也許可以爲你提到存儲2n個位，然後用huffman coding或其他lossless data compression技術來壓縮該數據。

我不認爲你可以達到更好的最壞情況的界限，但在平均情況下 - 它應該爲你節省一些空間。

Answer 2

有兩種方法來解決：

1. 編碼多級子樹。例如：在最大電平2可以有四種形狀：（）中，（a），（A-> B）和（a < -B-> C）。現在使用0,10,110,111來處理這些情況。對於簡單的2級完整樹編碼是：111 0 0. 3級完整樹是：111,10,10。對於4級完整樹，這變成：111 111 111 0 0 0 0。任務是任意的。您可以使用霍夫曼編碼方案（如上所述）來尋找最佳編碼。這種編碼方案對鏈條來說更糟糕。對於一個純鏈，你需要3n-2位來存儲。

2. 做2n位編碼，然後用任何壓縮算法壓縮。

===另一種方法===

在每一個節點的正常表現，你可以有以下三個選項之一：00，01，11，現在，採取三個節點在同一時間。你可以有27個組合。您可以將這些組合中的每一個以5位存儲。這樣，所需的平均存儲量變爲5/3而不是2位。此外，您可以嘗試組合任意數量的節點。請參閱下表爲壓縮率：

正如你所看到的，如果你把10個節點同時您可以通過係數1.25減少存儲空間

naive_length compr_length compr_factor 
2 2 1.0 
4 4 1.0 
6 5 1.2 
8 7 1.14285714286 
10 8 1.25 
12 10 1.2 
14 12 1.16666666667 
16 13 1.23076923077 
18 15 1.2 
20 16 1.25 
22 18 1.22222222222 
24 20 1.2 
26 21 1.2380952381 
28 23 1.21739130435 
30 24 1.25 
32 26 1.23076923077 
34 27 1.25925925926 

Answer 3

（即空間減少20％），如果我正確理解，如果一個節點有一個孩子，這不是左或右的孩子，即你不辨左右在一個孩子的情況下。然後我認爲它可以在（日誌3）n中以日誌爲基數2來完成。

您可以通過預先遍歷來描述樹，爲每個節點編寫子節點數（0,1或2）。這將創建一個長度爲n的基數3（實際上長度爲n - 1，最後一個節點將始終爲零）。恰好有3 ^（N - 1）這樣的數字，這可以以二進制編碼的（對數3）（N - 1）〜= 1.59（N - 1）。

可以使用O（log n）位在編碼位串的開頭寫入位數。

更新：這裏是一個implementation。