LZW圧縮で圧縮バッファを入力バッファより大きくする必要があるのはなぜですか？

Question

私は現在、私のプロジェクトにFFmpegのソースコードからLZWの圧縮と解凍の方法を実装しようとしています。私が遭遇したのは、圧縮されたデータが格納される出力バッファのサイズが、圧縮したい入力バッファのサイズよりも大きくなければならないということです。圧縮そのものとは対照的ではありませんか？

lzwenc.cソースファイルの一部であるff_lzw_encode()機能にコードの次の部分があります。

if (insize * 3 > (s->bufsize - s->output_bytes) * 2) 
{ 
    printf("Size of output buffer is too small!\n"); 
    return -1; 
} 

私の具体的な例として、私は生のビデオフレームをローカルに送信する前に圧縮しようとしています。しかし、(insize * 3)/2（圧縮データが格納される）のサイズのバッファにメモリを割り当てると、insizeのサイズのrawバッファを送信するよりも、send()の関数を使用して送信するのに時間がかかりませんか？

Answer 1

「圧縮された」フォームが入力と同じかそれより小さいサイズであることを保証することはできません。どのような方法でも圧縮できない純粋にランダムなデータの最悪のケースについて考えてみてください。最良の場合、元のサイズに100％圧縮されます。それに加えて、いくつかの圧縮メタデータまたはエスケープシーケンスを追加する必要があり、その結果、例えば、 100％+ 5バイト。

実際、非圧縮データを「100％」に圧縮するのは、通常は自動的に行われません。アルゴリズムが単に入力を正常に圧縮しようとすると、その結果は入力よりもかなり大きいになることさえあります。スマート圧縮ツールはこの状況を検出し、そのチャンクを代わりに非圧縮で送信し、少なくともチャンクが圧縮されていないことを示すメタデータを追加します。

割り当てたバッファは、最悪の場合の「圧縮された」バイト数を格納するのに十分な大きさでなければなりません。したがって、「ヘッドルーム」が必要です。

はないことは

はい、それは希望、生のバッファを送信 よりも（）関数を使用して送信送信するために多くの時間がかかるだろう。そのため、（割り当てられた）バッファ全体を送信するのではなく、そのバッファから、圧縮関数が使用したことを示すバイト数だけ送信します。