如何區分層次數據？

Question

有沒有差異層次結構的工具？

IE，請考慮以下層次：

A has child B. 
B has child C. 

這一點比起：

A has child B. 
A has child C. 

我想一個工具，它顯示了C是否已從B的孩子搬到了的孩子A.是否有這樣的工具存在？如果沒有特定的工具，我不反對寫自己的，那麼適用於這個問題的一些好的算法是什麼？

Answer 1

我的好先生的答案是：Depth-first search，也被稱爲深度優先遍歷。你可能會發現一些使用Visitor pattern。

在處理比較XML樹時，如果沒有爲此執行某種實現，則無法擺動死亡貓。舉個例子，以diffxml爲例。

Answer 2

基於達特茅斯研究的一部分，用於差異層次結構（非專門用於XML，HTML等）的優秀通用資源是github項目。他們有一個相當廣泛的列表related work，從XML差異到配置文件差異到HTML差異。

一般來說，實際上在樹結構上執行差異/補丁是一個相當好解決的問題，但以對人類有意義的方式顯示這些差異仍然是狂野的西部。當你的數據結構已經具有像HTML一樣的語義含義時，這是雙重的。

Answer 3

您可能會考慮我們的SmartDifferencer工具。

這些工具以差異化的方式比較計算機源代碼文件。與面向行的diff不同，這些工具根據代碼結構（變量名稱，表達式，語句，塊，函數，類等）將合理的編輯（「移動，插入，刪除，替換，複製，重命名」 ），產生對程序員有意義的答案。

這些計算機源代碼恰好具有您建議的「層次結構」結構;各種構造嵌套。特別是對於您的主題，通常代碼塊可以嵌套在代碼塊中。 SmartDifferencer工具使用目標語言準確的解析器將源文本「解構」爲這些層次實體。我們有一個XML的智能差異，您可以在其中明顯地編寫嵌套標籤。

答案沒有被報告爲「M的第N個孩子已經移動」，儘管它實際上是通過對解析器產生的分析樹進行計算來計算的。相反，它被報告爲「在x行的類型的代碼片段，以行col b已經移動...」