48

指定された文字列が圧縮された (短い) 文字列を返す JavaScript 関数を探しています。

長い文字列 (HTML) をローカル データベースに保存する Chrome Web アプリケーションを開発しています。テスト目的で、データベースを格納するファイルを圧縮しようとしましたが、5 分の 1 に縮小されたので、格納するものを圧縮するとデータベースを小さく保つのに役立つと考えました。

ここで、JavaScript での LZSS の実装を見つけました: http://code.google.com/p/u-lzss/ (「U-LZSS」)。

短いサンプル文字列 (デコード === エンコード) を使用して「手で」テストしたところ、動作するように見えました。また、Chrome でもかなり高速です。しかし、大きな文字列 (100 ko) を指定すると、文字列の後半が文字化け/混同されているように見えます。

U-LZSS が短い文字列を想定していて、より大きな文字列を処理できない可能性はありますか? そして、その上限を動かすためにいくつかのパラメータを調整することは可能でしょうか?

4

8 に答える 8

41

既存の実装のどれも私のニーズを満たしていなかったため、まさにこの目的のために特別に調整された小さなLZW実装をリリースしました。

それが私が今後使用しているものであり、おそらくいつかライブラリを改善しようとします。

于 2013-05-09T10:29:24.837 に答える
7

私には、宛先として UTF-8 を使用して文字列を圧縮するのは合理的ではないように思えます... トラブルを探しているだけのようです。伝送サイズが重要な場合は、圧縮をいくらか落として、プレーンな 7 ビット ASCII を宛先として使用する方がよいと思います。

ストレージ制限が UTF-16 文字に基づいている場合、エスケープまたは UTF-16 準拠を気にする場合は、大きな安全なサブセットを探すことができます。または、他のすべてが関係する場合は、各文字を 0..65535 として使用することもできます (例:データベース) には問題はありません。ほとんどのソフトウェア層はその (ab) 使用に問題はないはずですが、UTF-16 の範囲では 0xD800-0xDFFF が特別な用途 (サロゲート ペア) のために予約されているため、一部の組み合わせは正式には「エンコード エラー」であり、理論的には停止または停止できることに注意してください。歪。

私が面白半分に書いた4 KB の JavaScript デモでは、4 バイナリ バイトを、JavaScript 文字列 (85^5は 8^4 よりわずかに大きいですが、JavaScript 整数の精度に収まります)。これにより、エスケープする必要なく、たとえばJSONの圧縮データが安全になります。

次のコードでは、85 個の「安全な」文字のリストを作成します。

let cset = "";
for (let i=35; i<35+85+1; i++) {
    if (i !== 92) cset += String.fromCharCode(i);
}

次に、4 バイト ( b0、b1、b2およびb3それぞれ 0...255 から) を 5 文字にエンコードするコードは次のとおりです。

// First convert to 0...4294967295
let x = ((b0*256 + b1)*256 + b2)*256 + b3;

// Then convert to base 85
let result = "";
for (let i=0; i<5; i++) {
    let x2 = Math.floor(x / 85);
    result += cset[x - x2*85];
    x = x2;
}

デコードするには、逆の手順を実行します。つまり、base-85 の数値から x を計算し、base-256 の 4 桁 (つまり、バイト) を抽出します。

注: トーラス コードでは、 92 をスキップする代わりに、わずかに異なる文字セットを使用し、\126 に置き換えました~。興味のある方は、完全な解凍コードをご覧ください。

// There are two Huffman-encoded code streams
//    T - single chars (0..127) and sequence lengths (128...255)
//    A - high bits of relative addresses of sequence (0..255)
//
// Expansion algorithm is:
//    1) Read a code X from T
//    2) If it's a char (X < 128) then add to output
//    3) otherwise (X>=128) read sequence address ADDR from stream A (high bits)
//       and from input (low bits) and copy X-128 bytes from ADDR bytes "ago"
//

let Z = 5831; // expanded size
let i = 0, // source ptr
    a = 0, // current bits accumulator
    n = 0; // number of available bits in a

// Read a single bit
let b = function(){
    if (!n) {
        // There are no more bits available in the accumulator, read a new chunk:
        // 5 ASCII escape-safe chars will be transformed in 4 8-bit binary bytes
        // (like BASE64, just a bit more dense)
        a = 0;
        let w = 5;
        while (w--) {
            let y = s.charCodeAt(i+w);          // get next char
            a = a*85 + (y > 125 ? 92 : y) - 35; // extract base-85 "digit" (note, uses ~ instead of \ that requires quoting)
        }
        n = 32; // we got 32 bits in a
        i += 5; // we consumed 5 characters from source
    }
    return (a >> --n) & 1;  // extract a single bit
};

// Read a code of z bits by concatenating bits coming from b()
let v = function(z){
    return (--z ? v(z) : 0)*2+b();
};

// Read an Huffman (sub-)tree: a bit will tell if we need to
// read a two sub-trees or a leaf
let h = function(){
    return b() ? [h(), h()] : v(8);
};

// Read A and T Huffman trees
let A = h(), T = h();

// Extract a code given a node:
//   if the node is an array (intermediate node) then we need to read a bit
//   from the input binary stream to decide which way to go down the tree,
//   if it's a number then we just return the value.
//   `n.map` is truthy for arrays and falsy for numbers.
let d = function(n){
    return n.map ? d(n[b()]) : n;
};

let S="";  // Output

// While we're not done
while(S.length<Z){
    // Extract a code from T
    x = d(T);
    if (x < 128) {
        // This is a single character, copy to output
        S += String.fromCharCode(x);
    } else {
        // This is a sequence of x-128 bytes, get address and copy it
        // Note: high 8 bits are from the Huffman tree A and 8 low bits
        // are instead directly form the bit stream as they're basically
        // noise and there's nothing to gain by trying to compress them.
        S += S.substr(S.length-(d(A)<<8)-v(8), x-128)
    };
}

（この再フォーマット/コメント付きバージョンはテストしていないことに注意してください。タイプミスがある可能性があります）

于 2010-12-31T13:36:18.143 に答える
6

Piskvor の提案で、この質問への回答にあるコードをテストしました: Gzip のJavaScript 実装 (トップ投票の回答: LZW 実装) で、次のことがわかりました:

  1. できます
  2. データベースのサイズを 2 分の 1 に縮小します。

...これは 5 未満ですが、何もないよりはましです。だから私はそれを使いました。

(Piskvor の回答を受け入れることができればよかったのですが、それは単なるコメントでした)。

于 2011-01-03T12:16:52.610 に答える
1

lz-stringも調べる必要があると思います。これは高速で圧縮が非常によく、ページにリストされているいくつかの利点があります。

他のライブラリはどうですか？

  • 数値の配列を返すいくつかの LZW 実装 (トークンは 64 ビットを使用するため、格納するのは非常に非効率的です) で、255 を超える文字はサポートされません。
  • 文字列を返すいくつかの他の LZW 実装 (格納するのはそれほど効率的ではありませんが、それでも、すべてのトークンは 16 ビットを使用します) で、255 を超える文字はサポートされません。
  • 非同期で非常に遅い LZMA 実装ですが、遅いのは LZMA であり、実装ではありません。
  • GZip 実装は実際にはブラウザ向けではなく、70kb の node.js 向けでした (deflate.js と crc32.js が依存しています)。

著者が lz-string を作成した理由:

  • モバイルでの作業で、何か速いものが必要でした。
  • Web サイトの外部から収集した文字列を操作するには、255 を超える UTF 文字を含む、あらゆる種類の文字列を入力として受け取ることができるものが必要でした。
  • ライブラリが 70kb を使用しないことは決定的なプラスでした。可能な限りコンパクトな文字列を生成して localStorage に格納するもの。そのため、オンラインで見つけることができたライブラリはどれも、私のニーズに合っていませんでした。

他の言語でこの lib の実装があります。私は現在 Python の実装を調べていますが、現時点では解凍に問題があるようですが、JS のみに固執する場合は、私には本当に良さそうです。

于 2016-01-29T18:27:05.967 に答える
1

以下が必ずしも当てはまるとは限らないと思うので、何かを実装する前にテキストファイルを試してみてください。

そのため、格納するものを圧縮すると、データベースを小さく保つのに役立つと考えました。

これは、可逆圧縮アルゴリズムが繰り返しパターン (空白など) に非常に適しているためです。

于 2010-12-31T13:22:11.367 に答える