3

私はデータの冗長性について考えていましたが、これを続ける前にすべてを書面で破棄したいと思っていました(さらに、このアイデアがすでに実行されているかどうかを再確認しました)。

さて、ここに行きます。

インターネットは、テキスト、画像、ビデオなどの冗長データでいっぱいです。その結果、HTTPを介したgzipおよびbzip2のオンザフライ圧縮および解凍に多くの努力が注がれています。GoogleやFacebookのような大規模なサイトには、ページの読み込みを高速化するために時間を費やすチーム全体があります。

私の「質問」は、圧縮がファイルごとにのみ行われるという事実に関連しています(gzip file.txtyields file.txt.gz)。間違いなく、インターネット上に散らばっている一見無関係なデータの間には多くの共通点があります。これらの一般的なチャンクを保存し、クライアント側またはサーバー側でそれらを組み合わせて、コンテンツを動的に生成できるとしたらどうでしょうか。

これを実行できるようにするには、インターネット上で最も一般的なデータの「チャンク」を見つける必要があります。これらのチャンクは任意のサイズにすることができ(おそらくここで最適な選択があります)、組み合わせて、考えられる任意のデータを表現できる必要があります。

説明のために、次の5つの共通データのチャンクがあるとしましょう- a, b, c, d, and e。これらのチャンクのみを含む2つのファイルがあります。と呼ばれるプログラムがchunkありcombineます。chunkデータを取得し、bzip2、gzip、またはその他の圧縮アルゴリズムを使用して圧縮し、そのデータを構成するチャンクを出力します(圧縮後)。combineチャンクを展開し、連結された結果を解凍します。使用方法は次のとおりです。

$ cat gettysburg.txt
"Four score and seven years ago...cont'd"
$ cat test.txt
"This is a test"
$ chunk gettysburg.txt test.txt
$ cat gettysburg.txt.ck
abdbdeabcbdbe
$ cat test.txt.ck
abdeacccde
$ combine gettysburg.txt.ck test.txt.ck
$ cat gettysburg.txt
"Four score and seven years ago...cont'd"
$ cat test.txt
"This is a test"

たとえば、HTTPを介してファイルを送信する場合、サーバーchunkはデータを送信してクライアントに送信できます。クライアントはcombine、チャンク化されたデータを送信してレンダリングすることができます。

誰かがこれを以前に試みたことがありますか?そうでない場合は、その理由を知りたいのですが、そうであれば、この機能をどのように実現できるかを投稿してください。良い最初のステップは、これらのチャンクが何であるかを理解する方法を詳しく説明することです。チャンクを取得する方法を理解したら、これら2つのプログラムchunkとがどのように機能するかを理解しますcombine

これは現実世界に影響を与える非常に興味深い問題だと思うので、おそらくこれに賞金をかけます(受信状況によって異なります)。

4

4 に答える 4

3

あなたは誰かが以前に似たようなことをしたことがあるかどうか、そしてチャンクのサイズはどうあるべきかを尋ねました、そして私はあなたに私の頭に浮かんだ2つの論文を指摘したいと思いました:

  • (のチーム)Googleは、ドキュメント間で共有されるデータを活用することにより、Webリクエストを高速化しようとしています。サーバーは、事前に計算された辞書をクライアントに通信します。この辞書には、ドキュメント間で共通であり、後の要求で参照されるデータが含まれています。これは、一度に1つのドメインでのみ機能し、現在はGoogle Chromeでのみ機能します:HTTPを介した共有辞書の圧縮

  • (のチーム)Microsoftは、リモート差分圧縮を使用した制限帯域幅ネットワークでのファイルレプリケーションの最適化の作業で、ファイルシステム同期の場合、約2KiBのチャンクサイズが適切に機能することを確認しました。それらは間接参照のレベルを使用するので、ファイルを再作成するために必要なチャンクのリスト自体がチャンクに分割されます-紙は読むのが魅力的であり、物事がどのように行われるかについての新しいアイデアを与えるかもしれません。

それがあなたを助けるかどうかはわかりませんが、ここではそれが役立つ場合に備えています。:-)

于 2009-12-27T22:16:31.340 に答える
1

最も一般的なチャンクについて実際に分析する必要はありません。実際、このような分散型の意思決定は非常に難しい場合があります。このようなものはどうですか:

HTTPデータ転送の場合を考えてみましょう。各ファイルを10MiBブロック(または任意のサイズ、それぞれの方法でパフォーマンスに影響があると確信しています)にチャンクし、SHA-256(または衝突に対して安全であるとかなり確信しているハッシュ)を計算します。

たとえば、ブロックB1..BnとチェックサムC1..Cnを含むファイルF1があります。これで、HTTPサーバーは、リストC1..Cnを使用してファイルF1の要求に応答できます。

これを実際に役立つようにするには、クライアントは既知のブロックのレジストリを保持する必要があります。チェックサムがすでに存在する場合は、ブロックをローカルにフェッチするだけです。終わり。不明な場合は、ローカルキャッシュから取得するか、チェックサムリストを取得したリモートHTTPサーバーからブロックを取得します。

ブロックを共有しているサーバーから別のファイルをダウンロードした場合(まったく異なるファイルであっても)、既にダウンロードされており、選択したハッシュアルゴリズムと同じくらい安全です。

現在、これはオフセットがある場合には対処していません(たとえば、1つのファイルが

AAAAAAAA

と他の

BAAAAAAAA

これはおそらく圧縮アルゴリズムで処理できます。しかし、ブロック自体を圧縮した場合、とにかく節約のほとんどを得ることができるでしょう...

考え?

于 2009-12-27T21:34:09.987 に答える
1

テキストデータを処理する簡単な方法があります。現在、テキストは音を表す文字のストリームとして保存されています。しかし、言語の単位は言葉ではなく音です。したがって、すべての単語の辞書があり、そのような単語への「ポインタ」をファイルに保存すると、ポインタを使用して単語リストを検索することにより、テキストを動的に再構成できます。

これにより、物事のサイズがすぐに3倍または4分の1に縮小されます。この方法では、単語はあなたが考えているチャンクと同じです。次のステップは、「this is」、「i am」、「full moon」、「seriously dude」、「ohbaby」などの一般的な単語グループです。

単語リストはスペルチェックにも役立ち、オペレーティングシステムで実装する必要があります。スペルチェッカーがオペレーティングシステムの一部ではない理由はありますか?

于 2009-12-27T22:57:04.947 に答える
0

あなたの答えとは正確には関係ありませんが、あなたはすでにこれを見ています。Microsoft(およびその他)は、jqueryライブラリをホストするためのエッジネットワークをすでに提供しています。これらの同じURIを参照して、ユーザーが別のサイトからファイルにアクセスし、ブラウザーがファイルをキャッシュするという利点を得ることができます。

しかし、過去20分間に他の誰かが参照したコンテンツ(任意の数)をどのくらい参照していますか?多くの従業員がアプリケーションを共有している大企業では、いくらかのメリットが見られるかもしれませんが、そうでなければ、必要なチャンクを決定するのに苦労し、それを共有することのメリットを上回ります。

于 2009-12-27T22:55:29.177 に答える