定期的にテキストベースのデータセットをプッシュする予定ですウェブページからサーバーへおそらく JSON として。
プッシュごとに、データはまったく変更されていないか、一部またはすべてが変更されている可能性があります。ネットワーク経由で送信する必要があるデータの量を減らすには、各プッシュで変更された部分の差分のみを送信します。
次のような既成のソリューション、ツール、ライブラリをご存知ですか?
- 変更が行われるとJSONの差分を動的に構築する（oldJsonとnewJsonを保存してプッシュごとに完全な差分を実行することを避けるため）JavaScriptで記述（つまりクライアント側用）
- 既存のJSONチャンクをJSON diffでパッチするサーバー側では、Java または .NET^ 以外のプラットフォームで記述されます (Linux で実行する必要があります。Java は私が使用している環境ではオプションではなく、Mono も同様です)。
さらに、これがこの特定の問題に対処する最善の方法なのでしょうか?テキストデータのチャンクをプッシュするより良い方法はありますか?
編集：いくつかの説明:
- 考えられるデータ構造は、基本的にかなりフラットな (つまり、高度に接続されているため、リンクは実際のネストされたデータではなく ID ベースの参照になる) ノードのコレクションになります。ノードにはツリーのコレクションが含まれ、これらのツリーのリーフには、数値、文字列、ID などの実際の「プリミティブ」データが含まれます。ほとんどのデータ変更はリーフで発生します。
- リーフ データのほとんどは非常に小さいもの (プリミティブまたは 1 段落未満のテキスト) ですが、一部は非常に長くなります (「リッチ」テキストのページ)。
- 現時点では、これを厳密に 1 対 1 と見なすことができます。つまり、特定のデータ構造に接続されている (読み取り/書き込み) クライアントは 1 つだけです。
- 複雑さの点では、サーバーをできるだけ最小限に抑えることが望ましいでしょう。つまり、サーバーをできるだけ持たないようにすることです。HTML5 はまだほとんどサポートされていませんが、データを格納するためにサーバーは必要です...
^それは、ランダムな共有ホスティングで期待されるものです。私が言っているのは、あなたの良き友人である PHP、Python、PERL、Ruby などのフル機能のことです。または、ランダムな共有ホスティングに簡単にインストールできるもの。
ベストアンサー1
私もこれについて苦労してきました。もし誰かが私よりも良い答えを出してくれたら、とても興味がありますが、とりあえずは...
まず、http://www.xn--schler-dya.net/blog/2008/01/15/diffing_json_objects/
個人的にはこのライブラリを動作させることができませんでしたが、状況は異なる可能性があります。
もう 1 つの選択肢は、DIFF アルゴリズムを使用して問題を解決しようとしないことです。これは非常に非効率的であり、問題によっては、たとえ同じことを繰り返して行うことになったとしても、データ全体を送信した方がパフォーマンス メトリックが向上する場合があります。これは主に、非常に小さなデータ チャンクに当てはまります。送信する必要があるデータが大きくなるにつれて、当然、転換点が生まれますが、何らかの測定を行わない限り、転換点がどこにあるかは明らかではありません。ここでのポイントは、データが大きくなるほど、diff の計算にかかる時間も長くなることです。転換点は、各方法の成長率によって形成される 2 本の線の交点によってのみ決定されます。どちらの線も、diff の実装方法に応じて、直線的またはそれより悪いものになります。最悪のシナリオでは、中央に島ができ、diff の方がパフォーマンスが向上しますが、さらに大きなデータ セットでは再び交差し、ネットワーク経由で送信する方が再びパフォーマンスが向上します。
diff を試す前の次のステップは、データ アクセスを、行われた変更を追跡する「get」、「set」、および「delete」メソッドでラップすることです。ネットワーク経由で送信されるデータは、基本的にこれらのメソッドの使用状況の連続ログであり、送信が成功するたびにクライアント側からフラッシュされます。サーバー側では、データ アクセス メソッドに類似したサーバー側を使用して、このログをサーバー側データに適用します。これは、diff よりも多少軽量なソリューションであり、それほど多くの処理能力を必要としません。
最後に、diff を実行する場合、最も効率的な方法は、データセットを個別の「チャンク」に分割し、それぞれに一意の ID を割り当てることです。その後、diff を実行すると、diff の粗さはまさに「チャンク」レベルになります。つまり、比較するのは ID と ID だけです。チャンクを変更する場合は、新しい ID を割り当てます。diff アルゴリズムを粗くするほど、実行にかかる時間が短くなります。
あるいは、変更時に新しい ID を割り当てるのではなく、単に diff を実行して特定のオブジェクトが「変更」されたかどうかを確認し、変更を検出するとすぐに停止し、そのチャンク全体を再送信するようにマークして、サーバー側のチャンクを同じ ID で更新することもできます。チャンクに対して、等価性を迅速に確立するために使用できる、ある種の高速ハッシュ アルゴリズムがあれば、これをさらに効率的にすることができます。
チャンクの順序が重要でない場合、またはチャンクの物理的な順序でモデル化するのではなく、チャンク自体のプロパティとして順序を保存できる場合は、チャンクを ID でキー付けすることもできます。その後、違いを見つけるには、オブジェクト A のキーをリストし、オブジェクト B で検索し、その逆を行うだけです。これは、「実際の」 diff アルゴリズムよりもはるかに簡単に実装でき、O(a+b) のパフォーマンスがあり、実際の diff アルゴリズムの最悪のシナリオよりも優れていると思います。これは、自分で実装しようとしたり、不適切な実装を取得したりした場合に発生する可能性があります。