如何正確區分樹（即嵌套的字符串列表）？

Question

我正在聯機編輯器中處理由嵌套字符串列表組成的數據類型。請注意，如果每次更改單個值時我要轉移整個結構，則流量會變得難以忍受。所以，爲了減少流量，我想應用diff工具。問題是：我如何找到並報告兩棵樹的差異？例如：

["ah","bh",["ha","he",["li","no","pz"],"ka",["kat","xe"]],"po","xi"] -> 
["ah","bh",["ha","he",["li","no","pz"],"ka",["rag","xe"]],"po","xi"] 

在那裏，唯一的變化是"kat" -> "rag"內心深處的樹。大多數diff工具都適用於平面列表，文件等，但不適用於樹。我找不到有關這個具體問題的任何文獻。報告這種變化的最簡單方法是什麼？以及找到它的有效算法是什麼？

Answer 1

XML是一種常用的樹狀數據結構，通常用於描述結構化文檔或其他需要監視其隨時間變化的分層對象。因此，近期在樹分析中的大部分工作都是在XML的背景下應該是不足爲奇的。

這裏有一個2006年的調查有很多的可能有用的鏈接：Change Detection in XML Trees

一個從上面的比較有趣的環節，這是伴隨着被稱爲TreePatch一個開源實現，但現在似乎已不存在：Kyriakos Komvoteas' thesis

另一篇調查文章，由Daniel Ehrenberg提供，有更多參考文獻。 （來自http://cstheory.stackexchange.com的question）

祝你好運。

Answer 2

找到兩棵樹之間的區別看起來有點像在樹中搜索。唯一的區別就是你知道你將不得不深入他們兩人的底部。 您可以同時搜索兩棵樹，並且當您找到差異時，將其中一個更改爲另一個樹（如果這是您的目標 - 以相同的樹木結束，而不是每次都發送一棵樹）。

，我已經在diff'ing 2樹木中的一些鏈接：

How can i diff two trees to determine parental changes?

Detect differences between tree structures

Diff algorithms

希望這些鏈接將是對你有用。 :)

Answer 3

1. 你可以使用任何通用的DIFF算法，這是不是一個問題找到準備使用庫。
2. 如果您可以使用ZLIB庫，我可以建議另一種解決方案。用一些技巧就可以使用這個庫來發送兩個任何二進制文件之間非常壓縮的差異，讓它們稱爲A和B（以及差異Bc）。

側1：

1. 初始化ZLIB流
2. 壓縮A->交流與Z_SNC_FLUSH（我們不需要的結果，這樣的交流可以釋放）
3. 壓縮B-> BC與Z_SNC_FLUSH
4. DEINIT ZLIB流

我們壓縮塊的第一特殊標誌，它迫使了ZLib處理和輸出所有數據。但它不會重置壓縮狀態！當我們壓縮塊B時，壓縮器已經知道A的子序列並且將非常有效地壓縮塊B（如果它們有很多共同的話）。 Bc是唯一要發送的數據。

方2：

1. 初始化ZLIB流
2. 壓縮A->交流與Z_SNC_FLUSH
3. DEINIT ZLIB流

我們需要爲我們的壓縮解壓縮完全相同塊。這就是爲什麼我們需要Ac。

1. 初始化ZLIB流再次
與Z_SNC_FLUSH
2. 解壓縮BC->乙與Z_SNC_FLUSH
3. DEINIT ZLIB流
4. 解壓縮的Ac->甲

現在我們可以解壓縮的Ac-A（我們必須這樣做，因爲我們是在另一邊做的，它有助於解壓縮器學習塊A）的所有子序列，最後Bc-> B。

這是ZLib的一個不尋常和棘手的用法，但在這種情況下Bc不僅僅是壓縮塊B，它實際上是壓縮塊A和B之間的差異。如果ZLIB字典的大小是可比較的與塊A的大小。對於巨大的數據塊，它不會那麼高效。