24

同様のデータ ファイルの (膨大な) セットがあります。セットは常に成長しています。1 つのファイルのサイズは約 10K です。各ファイルは個別に圧縮する必要があります。java.util.zip.Deflater圧縮は、クラスで使用される zlib ライブラリで行われます。を使用して Deflate アルゴリズムに辞書を渡すとsetDictionary、圧縮率を向上させることができます。

「最適な」辞書、つまり全体的に最適な圧縮率を持つ辞書を見つける方法 (アルゴリズム) はありますか?

zlib マニュアルを参照

4

1 に答える 1

16

ジョン・ライザーは comp.compression について説明しました:

ディクショナリの場合:短い部分文字列のヒストグラムを作成し、ペイオフ (発生数×圧縮時に保存されるビット数) で並べ替え、最高のペイオフ部分文字列をディクショナリに入れます。たとえば、k が圧縮可能な最短部分文字列の長さ (通常は 3==k または 2==k) である場合、長さ k、1+k、2+k、および3+k。 もちろん、これらの部分文字列をディクショナリに配置し、部分文字列、オーバーラップ、上位アドレス endに近い短い文字列などを利用するためのいくつかの技術があります。

Linux カーネルは、同様の手法を使用して、サブルーチン呼び出しスタックのバックトレースを出力するために使用されるシンボルの名前を圧縮します。ファイル scripts/kallsyms.c を参照してください。たとえば、https://code.woboq.org/linux/linux/scripts/kallsyms.c.html

zlibのマニュアルでは、最も一般的な出現箇所を辞書の最後に配置することを推奨しています。

ディクショナリは、圧縮されるデータ内で後で検出される可能性が高い文字列 (バイト シーケンス) で構成する必要があります。最も一般的に使用される文字列は、ディクショナリの最後に配置することが望ましいです。ディクショナリの使用は、圧縮するデータが短く、正確に予測できる場合に最も役立ちます。これにより、デフォルトの空のディクショナリよりもデータを圧縮できます。

これは、LZ77 がスライディング ウィンドウ アルゴリズムを備えているためです。そのため、後の部分文字列は、最初のいくつかよりもデータ ストリーム上で到達可能になります。

文字列を適切にサポートする高水準言語で辞書を生成してみます。大雑把な JavaScript の例:

var str = "The dictionary should consist of strings (byte sequences) that"
    + " are likely to be encountered later in the data to be compressed,"
    + " with the most commonly used strings preferably put towards the "
    + "end of the dictionary. Using a dictionary is most useful when the"
    + " data to be compressed is short and can be predicted with good"
    + " accuracy; the data can then be compressed better than with the "
    + "default empty dictionary.";
// Extract words, remove punctuation (extra: replace(/\s/g, " "))
var words = str.replace(/[,\;.:\(\)]/g, "").split(" ").sort();
var  wcnt = [], w = "", cnt = 0; // pairs, current word, current word count
for (var i = 0, cnt = 0, w = ""; i < words.length; i++) {
    if (words[i] === w) {
        cnt++; // another match
    } else {
        if (w !== "")
            wcnt.push([cnt, w]); // Push a pair (count, word)
        cnt = 1; // Start counting for this word
        w = words[i]; // Start counting again
    }
}
if (w !== "")
    wcnt.push([cnt, w]); // Push last word
wcnt.sort(); // Greater matches at the end
for (var i in wcnt)
    wcnt[i] = wcnt[i][1]; // Just take the words
var dict = wcnt.join("").slice(-70); // Join the words, take last 70 chars

次に、dict は次の 70 文字の文字列です。

rdsusedusefulwhencanismostofstringscompresseddatatowithdictionarybethe

ここでコピーアンドペースト実行を試すことができます（追加：「print（dict）」）

それは単語全体であり、部分文字列ではありません。また、辞書のスペースを節約するために共通の部分文字列を重ねる方法もあります。

于 2010-02-28T01:37:58.993 に答える