11

2つのJSONドキュメント間の差分を表すための確立されたまたは既存の形式または規則はありますか？

2つのリモートノード（またはサーバー/クライアント）の両方に、潜在的に複雑なJSONとして表されるデータがあり、その構造は実行前には不明であるとします。一方は他方に更新を送信したいが、状態全体を1つの大きなJSONとして送信することはありません。代わりに、デルタだけです。2つのJSONドキュメント間のデルタ（または差分）を表す良い方法は何でしょうか？それらは非常に似ている可能性がありますが（1つの小さな変更）、そうではない可能性があります。

4

2 に答える 2

9

JSON ドキュメントは基本的にツリーであり、リーフには名前と値のペアが含まれます。

あなたがしたいことは、最小限のツリー デルタ (あるツリーを別のツリーに変換する最小の編集セット) を送信することです。

ツリー デルタの計算は、許可するデルタの種類に部分的に依存するため、ちょっとした芸術です (葉の挿入/削除? サブツリーの交換? サブツリーの移動? サブツリーの複製? 名前の変更? 値の置換?)。また、セマンティックの同等性も考慮する必要があります。2 つのサブツリーの位置を交換すると、結果は意味的に異なりますか? (デルタ検出器はこのようなツリー スワップを検出する場合があります。セマンティック アイデンティティ チェックでは、対象外として除外される場合があります)。サブツリーを複製した場合、答えは意味的に異なりますか? （JSONの場合、効果的な答えは「いいえ」だと思います）。

このような最小デルタを決定するには、動的計画法アルゴリズムのようなものが必要です。弦のレーベンシュタイン距離からインスピレーションを得ることができます。

これは、ソース コードに関してプログラマが関心を持つ一般的な問題です。JSON ドキュメントをソース コードと考えてください。詳細については、 https://stackoverflow.com/q/5779160/120163の回答を参照してください。

于 2013-03-24T02:28:32.223 に答える
6

Ira が指摘したように、Levenshtein の方針に沿ったいくつかのオプションがありますが、オブジェクトをシリアル化し、それを辞書編集的に比較することを検討することになりますが、Ira が述べたように、探している JSON 固有の言語差分は考慮されません ( 2 つのツリーは同一の JSON である可能性がありますが、レーベンシュタイン距離が大きく異なります)。あなたが望むのは、間違いなく木の編集距離です。

したがって、ツリー編集距離の技術に関する詳細を追加すると、この分野で使用される既知のアルゴリズムは通常、たとえば Zhang & Shasha または Klein であり、Zhang & Shasha の Python 実装を見つけることができます。これらのアルゴリズムは、あるツリーを別のツリーに変換するための最小数の編集を取得し、差分を提供します。ただし、それらは最高でも O(n^2) とやや遅いため、多数の JSON オブジェクトまたはファイルを比較すると、ゴルフ ゲームを完成させ、皿洗い、洗濯、ペットの入浴などを行うことができます。家事雑務。

そして、これこそが Ira が語る芸術の真の姿なのです。なぜなら、この種のアルゴリズムは難しく、計算コストがかかるからです。だからあなたができることは、創造的になることです。1 つの方法は、比較するオブジェクトの数を絞り込むことです。たとえば、お互いよりも明らかに中間体に似ている 2 つの JSON オブジェクト間の編集距離を計算するのはなぜでしょうか? 辞書式比較によって同一のオブジェクトの編集距離を計算しないでください。2 つのオブジェクトが多少または劇的に異なる場合は、差分を忘れて、完全な置換が必要であるとだけ言ってください。

不必要な CPU サイクルを節約するツリー編集距離の「芸術」を適用するために必要なのは、「やや似ている」または「劇的に異なる」とは何を意味するかに関するメトリックを提供する方法です。

そのために、PQ-Gram ツリー編集距離近似アルゴリズム ( http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf )の実装を作成しました。既存の PyGram Python コード ( https://github.com/Sycondaman/PyGram ) に基づくNode.js またはブラウザー ( https://github.com/hoonto/jqgram.git )。

PQ-Gram は、O(n log n) 時間と O(n) 空間 (n はノード数) で動作する真の編集距離アルゴリズムよりもはるかに高速です。

そのため、jqgram を使用して、JSON オブジェクトの編集距離メトリックに関して何を見ているのかをすばやく把握することをお勧めします。どのJSONオブジェクトを比較するか、単に置き換えるかを決定し、実際の距離を取得して差分を取得したい場合は、KleinまたはZhang＆Shashaを使用して実際の差分を取得します。

以下は、github の jqgram 実装の README から直接引用した jqgram JSON オブジェクト ツリー編集距離近似の例です。

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-15T17:18:21.227 に答える