|
|
HBOのシリコンバレーシリーズを見て以来、圧縮アルゴリズムに興味を持っている。リチャード・ヘンドリックスと彼のミドルアウト圧縮アルゴリズムはもちろんフェイクだが、一生懸命ググった結果、現実にそのような圧縮アルゴリズムの天才がいることを知った。
ヤン・コレットが2011年に発明したLZ4圧縮アルゴリズムで、もちろんミドルアウトほど凄くはないが、無敵の圧縮スピードと、一定の圧縮率を維持しながら解凍を高速化することで知られている。
その圧縮速度についてのレビューはここでは繰り返さない。興味があれば、こちらの比較記事を読んでほしい： https://blog.csdn.net/leilonghao/article/details/73200859
LZ4のgithubアドレスも添付する： https://github.com/lz4/lz4/
この記事は、LZ4圧縮アルゴリズムの原理を説明することに焦点を当てています。LZ4のアルゴリズムについては、 https://blog.csdn.net/zhangskd/article/details/17282895 という素晴らしい記事があるのですが、それを学んでいるときに、この記事は初心者にはあまり親切ではないと感じたので、私のような初心者のために別の記事を始めました。
LZ4を一文で要約すると、LZ4はLZ77に辞書の保存と検索の簡略化のための16kハッシュテーブルを加えたものである。
LZ4は可逆圧縮アルゴリズムで、マルチコアCPUでスケーラブルに、コアあたり500MB/sを超える圧縮速度を提供する。LZ4は非常に高速なデコーダを持ち、コアあたり数GB/sの速度があり、マルチコアシステムではRAM速度の限界に達することもある。
速度は、圧縮率と高速性を交換する「アクセラレーション」ファクターを選択することで、動的に調整することができる。一方、CPU時間を犠牲にして圧縮率を高めるために、高圧縮の派生版であるLZ4_HCが提供されている。どのバージョンも解凍速度は同じである。
では、LZ77はどうでしょうか？
LZ77の圧縮と原理
LZ77は、圧縮に辞書を適用するアルゴリズムである。平たく言えば、プログラムが現在見ているデータが重複しているかどうかを観察（辞書を見る）し、重複していれば、重複している2つのフィールドのオフセットと、重複しているフィールドを置き換える長さを保存し、このようにしてデータを圧縮するということである。
https://msdn.microsoft.com/en-us/library/ee916854.aspx を参照。
文字列A A B C B B A B Cの場合、2番目のAを読むと、プログラムは(1, 1）（前の繰り返しから1ビット離れている、長さ1）を保存し、同様に、2番目のBを読むと、プログラムは（2, 1）（距離2、長さ1）を保存する。
しかし、文字列が長くなり、プログラムがデータを常に辞書に記録するようになると、最悪の場合、プログラムは新しい文字を読み取るたびに辞書全体を調べることになるため、繰り返されるフィールドを検索するのは非常に時間がかかるようになる。 LZ77は、この問題を解決するためにスライディングウィンドウ方式を採用しています。
TCPのスライディング・ウィンドウの使用と同様に、スライディング・ウィンドウはキャッシュのサイズを縮小し、同時に多くのキャッシュ・データを処理する必要がないようにします。LZ77では、辞書は増加し続けることはないが、辞書の最大サイズを超えると、辞書に追加された最 初の文字は破棄されるため、辞書のサイズは常に指定された最大サイズに維持される。
辞書が3であるとする。
| 辞書
| a｜a｜b｜c｜b｜a｜b｜c｜であるとする。
出力(0,0,A)
| 辞書｜a｜b｜c｜b｜a｜b｜c
出力(1,1)
| a a b | c b b a b c
出力(0,0,B) | A A | A B C | C B A B C
A｜A｜B｜C｜B｜A｜B｜C
出力(0,0,C)
a a | b c b | b a b c
出力(2,1)
スライディング・ウィンドウのもう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 bA B
出力(0,0,A)
| 辞書｜先読みバッファ｜a｜b｜c｜b｜b｜aB B C
出力(1,1)
| a a | b c b | b aB C
出力(0,0,B)
| 出力(0,0,B)B C
出力(0,0,C)
| A A B C｜B B A｜B  B
出力(2,1)
| A B C B｜B A B｜ C
出力(1,1) | A | A B C B | B A B |   ;C
A｜B｜C｜B｜A｜BC
出力(5,3)
a a b c | b b a b c| 出力(5,3) A A B C | .
伸長手続きは、出力の一致する単位によって辞書を復元するので、圧縮手続きの出力ファイルに辞書を保存する必要はない。
伸長プロセス
LZ77アルゴリズムの利点の1つは、解凍が非常に速いことである。
最初のマッチが(0,0,A)であれば、Aが出力される。
2番目のマッチが(1,1)であれば、出力文字列の最初のビットがコピーされ、コピーの長さが1であれば、Aが出力される。
最後のマッチング・ユニットは(5,1)で、出力文字列の前のビットをコピーし、長さ1をコピーし、そしてAを出力する。
最後のマッチング・ユニットが(5,3)の場合、出力文字列の後ろの5ビットをコピーし、コピーの長さは3、そしてA,B,Cを出力する。
圧縮のためのLZ77アルゴリズムでは、最も時間のかかる部分は、検索されるキャッシュ内の辞書で最も長く一致する文字を見つけることである。辞書と検索対象キャッシュが短すぎる場合、一致する文字を見つける可能性は低くなります。そこでLZ4では、マッチング・アルゴリズムにLZ77への変更を加えている。
まず、LZ4アルゴリズムの辞書はハッシュテーブルである。 辞書のキーは4バイトの文字列で、各キーは1つのスロットにのみ対応し、スロット内の値は文字列の位置になります。
LZ4は検索されるキャッシュを持たず、入力ファイルから一度に4バイトを読み込み、この文字列に対応するハッシュテーブルのスロットを検索し、これを現在の文字列と呼ぶことにする。
最後の12文字に達したなら、それを直接出力ファイルに入れる。
スロットに値が割り当てられていない場合は、この4バイトが初めて現れたことを意味し、この4バイトと位置をハッシュテーブルに追加し、検索を続ける。
スロットに値があれば、マッチが見つかったことになる。
スロット内の値にスライディング・ウィンドウのサイズを足した値＜文字の現在位置の場合、マッチ位置がブロックのサイズを超えると、プログラムはハッシュ・スロット内の値を文字列の現在位置に更新する。
LZ4はハッシュの衝突が起きていないかどうかをチェックする。もし4バイトのスロット値の位置が現在の文字列と同じでなければ、ハッシュの衝突が起きているはずである。筆者自身のxxhashもその効率の良さで知られているが、どうしても衝突が発生してしまう。競合に遭遇すると、プログラムはハッシュ・スロットの値も現在の文字列の位置に更新する。
最後に、マッチが有効であることを確認し、プログラムはマッチ文字列の後続の文字も同じかどうかを確認し続ける。最後に、最後の有効なマッチの終わりから、現在の有効なマッチの 始まりまでのすべての文字をzipファイルにコピーし、現在の有効なマッチの シーケンスを追加する。
ColletはLZ4マッチシーケンスによって出力されたマッチング単位をLZ4と呼び、それらがLZ4 zipファイルを構成する。具体的には次の図のようになる：
トークンは1バイト長で、そのうち最初の4ワードがリテラル長、次の4ワードがマッチ長である。前のセクションで述べたように、最後の有効なマッチの終わりからこの有効なマッチの始まりまでのすべての文字は圧縮ファイルにコピーされ、これらの圧縮されていないファイルはリテラルであり、その長さはリテラル長である。
リテラルの後に偏差が続く。LZ77における偏差と一致長さのように、偏差は、現在の文字列の一致項目からの長さを指し、一致長さは、現在の文字列と辞書内の同じ文字列との間の一致の長さを指す。解凍時にコピーする文字列とコピーする長さを求めるために必要である。ずれの大きさは固定である。
図において、リテラル長＋とマッチ長＋は、トークン内の4文字のリテラル長またはマッチ長で足りない場合に追加される。4文字は0～15を表し、さらに1バイトを追加する。すなわち、255バイトで足りなくなるまで、サイズに255を追加する。 マッチ長では、0は4バイトを表す。
最後の12バイトは、リテラルがそのままコピーされるので、リテラルの後で終わります。
コードを見てみよう（パイソンの方が抽象的だ）。
まとめ これだけやっても、なぜLZ4がこれほど速いのかのまとめはまだない。 まずはLZ77とLZ4の辞書検索を比較してみよう。ネイティブのLZ77は、保留中の検索キャッシュと辞書の中から最大の一致を見つけることで辞書を検索します。 これは、2つの文字列の中で最大の同一文字列を見つける問題である。 もし動的計画法を使わなければ、最悪の場合、一方の文字列のすべての部分文字列を考慮し、もう一方の文字列でマッチしなければならない。 これにはO(m^2×n)がかかる。もし動的計画法を使うなら、動的最長一致を保持するテーブルを使うことになり、O(m*n)で一致を完了させることができる。 また、これは検索バッファと辞書のペアの場合のみである。最悪の場合、一致するものがない場合、LZ77は（ファイル全体の長さ - サーチバッファの長さ）という非常に多くのマッチング問題をこなさなければならない。 LZ4は実際には、より大きなレベルの動的プログラミングを使用しています。4バイトとその位置をハッシュテーブルに保存し、新しい4バイトのデータとマッチするたびに、ハッシュテーブルを見て有効な値かどうかを確認します。そして、後続のデータも一致するときに一致する値の2つのセットを見た後に有効な一致を見つけると、その最長の一致を見つけることができます。各キーのLZ4ハッシュテーブルは1スロットにしか対応しないので、ハッシュテーブルを見つけて変更する作業はO(1)しか必要としない。マッチの後にさらにマッチが見つかれば、より多くの比較のセットが必要になるが、これらの比較の合計時間は、ハッシュテーブルを探すのに費やされる時間により取って代わるので、LZ4アルゴリズムの合計時間はO(n)だけである。コレットのアルゴリズムの美しさには感嘆せざるを得ない！アルゴリズムをさらに高速化するために、Colletはデフォルトのハッシュテーブルのサイズを16kに設定し、32kを超えないことを推奨している。LZ4のハッシュ・テーブルがハッシュ方程式または最速のxxhashを使用していることは言うまでもない。 もちろん、このような設計には欠点もある。ハッシュ・テーブルが小さくなればなるほど、キーの数は少なくなる。これはハッシュの衝突が多くなることを意味する。そして、ハッシュの衝突が増えるということは、マッチの数が減ることを意味する。 また、ハッシュ・テーブルが小さくなればなるほど、スライディング・ウィンドウも小さくなる。より少ないマッチはより小さい圧縮率を表し、これがLZ4の圧縮率がより低い理由である。 Outlook LZ4には幅広い応用場面がある。 シリコンバレーでMIDDLE OUTがVRに使用されたように、LZ4は非常に高速な圧縮のため、レイテンシが非常に小さくなる代償として、より少ないIOをもたらすことで帯域幅の使用を増やすことができる。 また、ちょっとした推測だが、もしCPUのレベル1キャッシュが大きければ、LZ4は速度を損なうことなく圧縮率を高めることができるのではないだろうか？
元記事：https://www.cnblogs.com/z-blog/p/8860799.html |
前の記事：TrueNASCore ビューのスナップショット（スナップショット）の場所次の記事：OkHttpを使ってHTTPネットワークリクエストを送信するJava |
发表于2022-1-3 13:54:23
お
