4

多くの反復トークン (~25%) を含むテキスト ファイル形式の生データがあります。（A）データをコンパクトな形式で保存し（B）、実行時に元のファイルを再構成できるようにするアルゴリズムがあるかどうかを知りたいです。

何か案は？

詳細:

  • 生データは、正規表現を使用したインスタント検索のために、純粋な html+javascript アプリで消費されます。
  • データは、(大文字と小文字を区別する) 英字といくつかの句読点を含むトークンで構成されます。
  • トークンはスペースと改行で区切られます。

これまでで最も有望なアルゴリズム: 以下で説明する簡潔なデータ構造ですが、再構築は難しそうです。

http://stevehanov.ca/blog/index.php?id=120

http://ejohn.org/blog/dictionary-lookups-in-javascript/

http://ejohn.org/blog/revised-javascript-dictionary-search/

PS: サーバー側の gzip が現在採用されていますが、これはトランスポート層の最適化にすぎず、たとえばオフライン ストレージを最大限に活用するのには役立ちません。25%という膨大な繰り返し性を考えれば、もっとコンパクトに収納できるはずですよね。

4

2 に答える 2

1

実際の使用法がかなり不明確であることを考えると、これが役立つかどうかはわかりませんが、最小の合計サイズ（html + javascript + data）の場合、テキストデータをグレースケールの.pngファイルに保存するというアイデアを思いついた人もいます。各ピクセルへのバイト。小さなローダースクリプトは、.pngをキャンバスに描画し、ピクセルごとに読み取り、この方法で元のデータを再構築できます。これにより、Javascriptで実装しなくても圧縮をデフレートできます。詳細については、ここなどを参照してください。

サイズに制約のあるプログラミング競技会など、かなり難解な要件がない限り、このような手法は使用しないでください。あなたの同僚はあなたに感謝します:-)

于 2012-05-14T16:23:52.437 に答える
1

一般的に言えば、JavaScript で圧縮を実装しようとするのは悪い考えです。圧縮は、まさに JS が最も苦手とするタイプの作業です。つまり、CPU を集中的に使用する計算です。

JS はシングルスレッド1であるため、データの解凍に費やされる時間全体にわたって、ブラウザー UI をブロックすることに注意してください。対照的に、HTTP gzip で圧縮されたコンテンツは、ブラウザーによって非同期的に解凍されます。

(正規表現に対してすべてのレコードをテストするために) データセット全体を再構築する必要があることを考えると、Succinct Trie がうまくいくとは思えません。正直なところ、ネイティブの gzip 圧縮よりもはるかに優れた圧縮が得られるとは思えません。

1 - Web ワーカーにもかかわらず。

于 2012-05-14T16:55:41.513 に答える