HBOのドラマ『シリコンバレー』を見てから、私はずっと圧縮アルゴリズムに興味を持つようになりました。 リチャード・ヘンドリックスと彼の中間圧縮アルゴリズムはもちろん偽物ですが、Googleで調べてみると、現実にもそのような圧縮アルゴリズムの天才が存在することがわかりました。
ヤン・コレットは2011年にLZ4圧縮アルゴリズムを発明しました。 もちろん、LZ4アルゴリズムはミドルアウトほど優れているわけではありませんが、無敵の圧縮速度と、一定の圧縮率が保証されている場合の高速な減圧速度で知られています。
ここでは圧縮速度の評価について詳しくは触れませんが、興味があればこの比較記事をお読みください。ハイパーリンクのログインが見えます。
また、LZ4のGitHubアドレスも添付されています:ハイパーリンクのログインが見えます。
本記事では、LZ4圧縮アルゴリズムの原理を説明することに焦点を当てます。 偉大な神が以前にLZ4アルゴリズムの説明を書いています:ハイパーリンクのログインが見えます。しかし、以前勉強していたとき、この記事は初心者にはあまり親切ではないと感じたので、私のような初心者向けの別の記事を書き始めました。
一文でまとめると、LZ4は16kサイズのハッシュテーブルを持つ辞書を保存し、検索を簡素化するLZ77です。
LZ4はロスレス圧縮アルゴリズムで、1コアあたり>500 MB/sの圧縮速度を持ち、マルチコアCPUで拡張可能です。 非常に高速なデコーダを搭載し、1コアあたり数GB/sの速度に達し、マルチコアシステムではしばしばRAMの速度制限に達します。
速度は動的に調整可能で、「加速度」係数を選択でき、圧縮比を犠牲にして高速化します。 一方で、CPU時間を犠牲にして圧縮を増やす高圧縮微分LZ4_HCも提供されます。 すべてのバージョンは減圧速度が同じです。
では、LZ77とは何でしょうか?
LZ77の圧縮と原理
LZ77は圧縮のために辞書を適用するアルゴリズムです。 簡単に言えば、プログラムに現在表示されたデータが前のデータと重複しているかどうかを観察(辞書を参照)し、重複した場合は距離(オフセット)と重複フィールドの長さを保存して重複フィールドを置き換え、データを圧縮するということです。
参考ハイパーリンクのログインが見えます。
文字の列 A A B C B B A B C の場合、2番目の A を読み取るとプログラムは (1,1)(前の A から 1 桁、長さ 1 を保存)、同様に 2 番目の B を読み取ると (2,1)(距離 2、長さ 1) を保存します。
しかし、文字列が長く、プログラムが常にデータを辞書に記録している場合、重複するフィールドの探索は非常に時間がかかります。最悪の場合、新しい文字を読み取るたびに辞書全体を読み漁ってしまうからです。 LZ77はこの問題を解決するためにスライディングウィンドウ方式を用いています。
TCPのスライディングウィンドウの出発点と同様に、スライディングウィンドウはキャッシュ領域を縮小し、同時に過剰なキャッシュデータを処理しないようにできます。 LZ77では、辞書は常に増え続けるのではなく、辞書で指定された最大サイズを超えると最初に加えられた文字を破棄し、辞書のサイズが常に指定された最大サイズに保たれるようにしています。
辞書の長さが3であると仮定します
| 辞書 |
| A | A B C B B A B C
出力(0,0,A)
| A A | B C B B A B C
出力(1,1)
| A A B | C B B A B C
出力(0,0,B)
A | A B C | B B A B C
出力(0,0,C)
A A | B C B | B A B C
出力(2,1)
スライディングウィンドウのもう一つの部分は検索対象のキャッシュです(ルックアヘッドバッファには公式な翻訳はありません)。 検索対象のキャッシュは、辞書に最も近い長さの非圧縮部分です。 LZ77アルゴリズムは、この文字部分で最も長い文字列で辞書と同じものをマッチングします。 前述の例は1の先取りバッファとして考えることができます。
辞書長が5で、検索するキャッシュサイズが3であるとします
| 辞書 | 先取りバッファ |
A | A B C B B | A B C |
出力(5,3)
最長の文字列はABCです
完全な圧縮プロセス:
辞書長が5で、検索するキャッシュサイズが3であるとします
| 辞書 | 先取りバッファ |
| A A B | C B B A B C
出力(0,0,A)
| A | A B C | B B A B C
出力(1,1)
| A A | B C B | B A B C
出力(0,0,B)
| A A B | C B B | A B C
出力(0,0,C)
| A A B C | B B A | B C
出力(2,1)
| A A B C B | B A B | C
出力(1,1)
A | A B C B B | A B C |
出力(5,3)
A A B C | B B A B C | 。。|
コンプレッサーの出力ファイルに辞書を保存する必要はありません。なぜなら、復式プログラムが出力単位を照合して辞書を復元するからです。
減圧プロセス
LZ77アルゴリズムの大きな利点の一つは、解圧が非常に速いことです。
最初の一致単位が(0,0,A)であれば、Aが出力されます。
2番目のマッチングユニットは(1,1)で、出力文字列の前のビットをコピーし、コピー長が1ならAを出力します。
。。。
最後の一致単位が(5,3)であればコピー出力文字列の5ビットを遡り、コピー長が3なら出力A、B、Cです。
LZ77アルゴリズムの圧縮で最も時間がかかる部分は、辞書で検索するキャッシュ内の最も長い一致文字を見つけることです。 検索すべき辞書とキャッシュが短すぎると、一致する可能性は低くなります。 そのため、LZ4はLZ77のマッチングアルゴリズムを変更しました。
まず、LZ4アルゴリズムの辞書はハッシュテーブルです。 辞書内のキーは4バイトの文字列で、各キーは1つのスロットのみに対応し、そのスロットの値はその文字列の位置を表します。
キャッシュを探す代わりに、LZ4は入力ファイルから4バイトずつ読み込み、ハッシュテーブル内の文字列に対応するスロットを探します。以下、これを現在の文字列と呼びます。
最後の12文字に達したら、直接出力ファイルに入れてください。
スロットに値が割り当てられていない場合は、4バイトが初めて現れ、これら4バイトと位置をハッシュテーブルに加え、検索を続けます。
スロットに割り当てがあれば、マッチングの値を見つけたことを意味します。
スロット内の値とスライダーウィンドウのサイズが現在の文字の位置<合う場合、マッチ位置はブロックのサイズを超え、プログラムはハッシュスロット内の値を現在の文字列の位置に更新します。
LZ4はハッシュ競合があったかどうかを確認します。 スロット内の4バイトが現在の文字列と一致しなければ、ハッシュ競合が起きているはずです。 作者自身のxxhashも効率性で知られていますが、対立は避けられません。 競合が発生した場合、プログラムはハッシュスロット内の値を文字列の現在の位置に更新します
最終的に、マッチングが有効であることを確認し、プログラムはマッチング文字列の後続の文字が同じかどうかを引き続き確認します。 最後に、前の有効なマッチの末尾からこの有効なマッチの冒頭にすべての文字をコピーし、その有効なマッチのマッチングシーケンスを追加します。
ColletはLZ4の出力を一致ユニットのシーケンスと呼び出し、それらがLZ4圧縮ファイルを構成します。 詳細は以下の通りです。
トークンは1バイトで、最初の4語が文字通りの長さ、最後の4語がマッチ長です。 前述の通り、前の有効なマッチの終わりからその有効マッチの開始までのすべての文字は圧縮ファイルにコピーされます。これらの非圧縮ファイルはリテラルで、その長さは文字通りの長さです。
文字通り逸脱が続きます。 LZ77と同様に、偏差とマッチ長は現在の文字列がマッチングからどれだけ長く、マッチ長は現在の文字列と辞書内の同じ文字列へのマッチ長の長さを指します。 解凍とは、コピーする文字列とコピーする長さを見つけるためにそれを通すことです。 偏差の大きさは固定されています。
図では、リテラル長+およびマッチ長+は、トークン内のリテラルまたはマッチ長4語で足りない場合、対応する位置でさらに増加し続けます。 4語は0から15までを表し、もしそれ以上あれば1バイトを加えます。つまり、バイトが255未満になるまでサイズに255を加えます。 マッチング長では、0は4バイトを表します。
最後の12バイトは文字通りコピーされたから終わります。
コードを見てみよう(Pythonはより抽象的だ)
まとめ これらすべてを踏まえた上で、LZ4がなぜこれほど速いのかはまだまとめていません。 まずはLZ77とLZ4の辞書検索を比較しましょう。 ネイティブのLZ77は、検索するキャッシュと辞書内で最大の一致を探すことで辞書を検索します。 これは、2つの文字列で最大の同一文字列を見つける問題です。 動的計画法を使わなければ、最悪でも一つの文字列のすべての部分文字列を考慮し、別の文字列でそれらをマッチングしなければなりません。 ×動的計画法を使う場合、動的計画法の最長一致を保持するテーブルを使い、O(m*n)の場合のみマッチを完了させます。 しかも、それは検索キャッシュと辞書のペアだけの話です。 最悪の場合、マッチがなければLZ77は(検索するキャッシュの長さ)を数えなければなりません。 LZ4は実際にはより高度な動的プログラミングを用いています。4バイトとその位置をハッシュテーブルに保存し、その後、ハッシュテーブルの値が有効かどうかを確認するために新しい4バイトのデータと照合します。 有効なマッチングが見つかった後、2つのマッチングのフォローアップデータを見ると、その最長マッチも見つけることができます。 LZ4ハッシュテーブルの各キーは1スロットのみに対応するため、ハッシュテーブルの探索・追加・修正作業はO(1)だけで済みます。マッチング後にさらに多くのマッチが見つかれば、グループ比較も増えますが、合計時間としてこれらの比較はハッシュテーブルの検索時間を置き換えるため、LZ4アルゴリズムの総時間はO(n)です。Colletのアルゴリズムの美しさには感心せざるを得ません! アルゴリズムをさらに高速化するために、Colletはデフォルトのハッシュテーブルサイズを16kに設定しており、これは32kを超えないことが推奨されており、ほぼすべてのCPUのL1キャッシュ(Intel)に組み込めるようにしています。 CPUのL1キャッシュの速度とメモリ比率が大きく異なることは誰もが知っているので、LZ4が高速で動いているのは驚くことではありません。さらに、LZ4のハッシュテーブルで使われているハッシュ方程式が依然として最速のxxハッシュであることは言うまでもありません。 もちろん、このような設計には欠点もあります。 ハッシュテーブルが小さいほど、キー数は少なくなります。 つまり、より多くのハッシュ衝突が発生することになり、それは避けられません。 そしてハッシュ衝突が多ければ、マッチ数も減ります。 また、ハッシュテーブルが小さくなるほどスライドウィンドウも小さくなり、距離が遠すぎて多くのマッチが破棄されます。 マッチが少ないほど圧縮比が小さくなるため、LZ4の圧縮比はあまり目立たないのです。 展望 LZ4は幅広い応用シナリオを持っています。 シリコンバレーのVRでミドルアウトが使われていたように、LZ4は非常に高速な圧縮速度によりIO数を減らし、非常に低遅延を抑えることで帯域幅利用率を上げることができます。 また、レベル1でキャッシュ容量が大きいCPUがある場合、LZ4は速度を損なわずに圧縮比を上げられるのでしょうか?
翻訳元：ハイパーリンクのログインが見えます。 |
掲載地 2022/01/03 13:54:23
|
|
|
|
