針對JSON對象的增量編碼

是否有標準庫或工具用於計算JSON文檔並將差異應用於JSON文檔？基本上，我有一大堆想要在網絡中保持同步的大文件，而且我希望避免在每次我想同步它們時重新發送它們的整個狀態（因爲其中許多變量不會發生變化）。換句話說，我只想傳輸已更改的字段，而不是重新傳輸整個對象。我想，這將是方便有類似下面的一套方法：針對JSON對象的增量編碼

//Start with two distinct objects on the server 
// prev represents a copy of the state of the object on the client 
// next represents a copy of the state of the object on the server 
// 
//1. Compute a patch 
patch = computePatch(prev, next); 

//2. Send patch over the network 

//3. Apply the patch on the client 
applyPatch(prev, patch); 

//Final invariant: 
// prev represents an equivalent object to JSON.parse(JSON.stringify(next))

我肯定能實現一個自己，但也有相當需要考慮一些邊緣情況。這裏有一些我能想到如的簡單（雖然有點不盡人意）方法：

推出自己的JSON的修補。漸近地說，這可能是最好的方法，因爲它可以支持JSON文檔的所有相關功能，並支持一些專門的方法來執行差異整數，雙精度和字符串（使用相對編碼/編輯距離）。但是，JSON有很多特殊情況，我有點不想做這個測試，所以我更願意找到一些能夠解決這個問題的東西，這樣我就可以信任它，並且不必擔心由於我的JSON修補錯誤導致網絡Heisenbugs出現
只需使用動態編程計算JSON字符串之間的編輯距離即可。不幸的是，如果客戶端和服務器有不同的JSON實現（即它們的字段順序可能不同），那麼這不起作用，而且它也是一個非常昂貴的二次時間操作。
使用協議緩衝區。協議緩衝區有一個內置的diff方法，它完全符合我的要求，並且它們是一個很好的二進制序列化網絡友好格式。不幸的是，因爲它們也是嚴格鍵入的，所以它們缺乏使用JSON的許多優點，例如動態添加和刪除字段的能力。現在，這是我目前所傾向的方法，但它可能會使未來的維護非常可怕，因爲我需要不斷更新每個對象。
做一些真正討厭的，就像爲每個對象類型的自定義協議，並希望我得到它的權利在這兩個地方（是正確的！）。

當然什麼我真的希望的是有人在這裏計算器來通過和天保存到一個空間高效的JavaScript對象不同/補丁參考已經在生產環境，並跨越了很好的測試，多個瀏覽器。

* 更新 *

我開始寫我自己的補丁，它的一個早期版本可在github上的位置：

https://github.com/mikolalysenko/patcher.js

我猜因爲似乎沒有在這裏，我會接受一個JSON修補程序的有趣測試用例列表作爲備選答案。

來源

2011-09-06 Mikola

既然您提到了「需要考慮的不少邊緣案例」，如果您列舉了需要處理的邊緣案例以及它們應該如何處理，可能會有所幫助（對於您的答案和後代）解決。 – Phrogz

另外：您的問題的後半部分很好地表明您已經考慮過這個問題，並且作爲「解決方法」答案的一部分可能不錯，但與問題無關，對吧？ – Phrogz

總是添加一個「髒」標誌。 –

開始之前從頭開始編寫自己的JSON差異&修補實用，我會建議利用現有的差異&修補實用的純文本。你所要做的只是編寫一些邏輯，它接受一個任意的JSON字符串並以「規範的」JSON格式呈現 - 這樣任何兩個表示等價數據的JSON字符串都具有與文本字符串相同的「規範」形式 - 然後你可以使用普通的舊「補丁」來計算你所有的增量。

似乎canonical JSON的想法並不新鮮，但爲任意JSON字符串生成規範表示形式所需的代碼並不是微不足道的，而且看起來谷歌向我展示的所有東西都有改進空間「規範JSON」（包括對this question的答案，儘管使用Bencode作爲規範化格式聽起來很有前途）。

這是一個好消息，因爲這意味着你可以寫一些新的有用的東西！當你找到一個可行的解決方案時，讓我們貼出來（我也想能夠生成JSON三角洲）。

編輯：想在此之後多一些我認識到「標準化」的想法並不能真正幫助所有，因爲同樣的三角形/補丁不能通常被應用了兩個文本方式不同的JSON塊，即使他們具有相同的「規範形式」。這引出了一個問題 - 如果你只是通過電報發送JSON文檔的「deltas」，那麼爲什麼不簡單地將它們作爲字面明文差異發送（或者可能是MIME帶有text/x-diff類型的文檔）？爲了防止由於刪除修補程序而導致的損壞，您可能需要在某處添加序列/修訂號字段（包括數據文件和差異文件），或者您可以採取雄心勃勃的措施並使用（爲WebDAV開發）。也許你已經這樣做了？本週晚些時候我會試着看看你的代碼。

來源

2011-09-08 04:24:55 Peter

將做:)我想我應該更新協議緩衝區沒有泛（沒有差異的方法），所以我已經開始建設一個JSON差異/修補工具的道路，已經有一個早期版本正在運行。但是，它並沒有經過非常徹底的測試，所以需要做更多的工作來完成這些步驟。 – Mikola

回覆您的編輯，純文本差異將不起作用，因爲JSON.stringify可以重新排序字段。如果使用簡單的lcs編輯距離，製作明文差異代價也要昂貴得多，需要在所分析對象大小上的二次時間和空間。另一方面，走JSON文檔層次結構只需要線性時間。 – Mikola