是否存在兩個JSON之間差異的既定表示？

是否存在用於表示兩個JSON文檔之間差異的已建立或現有格式或約定？是否存在兩個JSON之間差異的既定表示？

可以說，兩個遠程節點（或服務器/客戶端）都有一些數據表示爲一個潛在的複雜JSON，其結構在運行時並不知道。一個想發送更新到另一個，但沒有發送整個狀態作爲一個大的JSON。相反，只是三角洲。什麼是代表任何兩個JSON文檔之間的差異（或差異）的好方法？他們可能會非常相似（一個小小的變化），但可能不會。

來源

2013-03-23 derekv

JSON文檔本質上是樹，葉子包含名稱/值對。

你想要做的是發送一個最小樹delta：將一棵樹轉換爲另一棵樹的最小編輯集。

計算樹deltas是一門藝術，部分原因是它取決於您允許的增量類型（插入/刪除葉子？交換子樹？移動子樹？重複子樹？重命名名稱？替換值？）。您還需要考慮語義等價性;如果你通勤兩個子樹的位置，結果在語義上是不同的？（您的delta檢測器可能會看到這樣的樹交換;語義標識檢查可能會將其消除爲不感興趣）。如果你複製一個子樹，答案在語義上是不同的？（我認爲JSON的有效答案是「否」）。

您需要類似動態規劃算法來確定這樣的最小增量;你可以從Levenshtein distance上獲取靈感。

這是程序員對源代碼感興趣的常見問題。將JSON文檔視爲源代碼，並在https://stackoverflow.com/q/5779160/120163處查看答案以獲得進一步討論。

來源

2013-03-24 02:28:32

不錯，我已經考慮過提出一個問題來問一個關於「樹差異」或「樹三角洲」的問題，但是我還沒有想過的是「你允許的種類的三角洲」。 – derekv 2013-03-24 02:54:29

偉大的信息。只是fyi：看起來你連接的問題已被刪除。 – Hassan 2016-06-09 14:08:33

@Hassan：不是這麼好的地方嗎？我不會在那裏複製所有的Q/A。 [如果你是10K +用戶，你仍然可以看到這些信息]。這是我公司提供的SmartDifferencer系列工具的鏈接：http://www.semanticdesigns.com/Products/SmartDifferencer。是的，JSON有一個。 – 2016-06-09 14:21:44

正如Ira指出的那樣，Levenshtein有一些選擇，但是你會考慮序列化你的對象，並按照字典順序對比它，正如Ira所提到的那樣，你將不會考慮到JSON特定的語言差異正在尋找（兩棵樹可能是相同的JSON，但Levenshtein距離非常不同）。你想要的絕對是樹編輯距離。

因此，爲了在樹編輯距離上增加一些細節，在這個空間中使用的已知算法通常是例如Shasha或Klein的例如，您可以找到Shasha的蟒蛇實現。這些算法將獲得最少數量的編輯，將一棵樹轉換爲另一棵樹，從而提供您的差異。然而，它們在絕對最好的時候會比較慢O（n^2），所以如果你要比較大量的JSON對象或文件，你會發現自己正在完善你的高爾夫遊戲，做菜，洗衣，沐浴寵物和其他家庭雜錄。

這真的是艾拉所說的藝術真正的地方，因爲這些算法很難，而且計算起來很昂貴。所以你可能做的是創造性。一種方法是縮小與進行比較的對象數量。例如，爲什麼要計算兩個JSON對象之間的編輯距離，這兩個JSON對象明顯更接近中間值而不是彼此？不要通過字典對比計算相同對象上的編輯距離，如果兩個對象有些顯着不同，可能忘記差異，只是說需要徹底更換。

爲了應用樹編輯距離的「藝術」，即節省自己不必要的CPU週期，您需要的是提供有關「有點相似」或「顯着不同」意思的度量方法。

爲此我寫了基於現有的PQ-革蘭樹編輯距離近似算法（http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf），您可以在github中的Node.js或在瀏覽器（https://github.com/hoonto/jqgram.git）使用的實現PyGram Python代碼（https://github.com/Sycondaman/PyGram）。

PQ-Gram比在O（n log n）時間和O（n）空間中運行的真正編輯距離算法快得多，其中n是節點數量。

所以我的建議是使用jqgram非常快速地感受一下您在JSON對象編輯距離度量方面的看法。確定哪些JSON對象應該進行比較，而不僅僅是替換，然後當您希望獲得差異的真正距離時，使用Klein或Shasha來獲取實際差異。

這裏的jqgram JSON對象樹編輯距離近似爲jqgram實施直接取出自述在github例如：

var jq = require("jqgram").jqgram; 
var root1 = { 
    "thelabel": "a", 
    "thekids": [ 
     { "thelabel": "b", 
     "thekids": [ 
      { "thelabel": "c" }, 
      { "thelabel": "d" } 
     ]}, 
     { "thelabel": "e" }, 
     { "thelabel": "f" } 
    ] 
} 

var root2 = { 
    "name": "a", 
    "kiddos": [ 
     { "name": "b", 
     "kiddos": [ 
      { "name": "c" }, 
      { "name": "d" }, 
      { "name": "y" } 
     ]}, 
     { "name": "e" }, 
     { "name": "x" } 
    ] 
} 

jq.distance({ 
    root: root1, 
    lfn: function(node){ return node.thelabel; }, 
    cfn: function(node){ return node.thekids; } 
},{ 
    root: root2, 
    lfn: function(node){ return node.name; }, 
    cfn: function(node){ return node.kiddos; } 
},{ p:2, q:3, depth:10 }, 
function(result) { 
    console.log(result.distance); 
});

所述LFn和CFN參數指定每個JSON樹應如何確定節點標籤名稱和每個樹根的子數組，以便您可以做有趣的事情，比如比較來自不同來源的JSON對象。你所需要做的就是提供這些函數以及每個根，jqgram將完成剩下的工作，調用你的lfn和cfn提供的函數來構建樹。

來源

2013-06-15 17:18:21 hoonto

是否存在兩個JSON之間差異的既定表示？

回答

相關問題