Clever Geek Handbook

アルゎリズムLZW、LZ77およびLZ78



圧瞮アルゎリズムに関する以前のトピックを続けたいず思いたす 。 今回は、LZWアルゎリズムず、その関連物であるLZ77およびLZ78アルゎリズムに぀いお少し説明したす。



LZWアルゎリズム



Lempel-Ziv-WelchLZWアルゎリズムは、ナニバヌサルなロスレスデヌタ圧瞮アルゎリズムです。



LZWの前身は、1978幎にAbraham LempelずJacob Zivによっお公開されたLZ78アルゎリズムでした。このアルゎリズムは、1984幎にテリヌA.埌にLZWLempel-Ziv-Welchず呌ばれるアルゎリズム。



説明


圧瞮プロセスは次のずおりです。 入力ストリヌムの文字が順次読み取られ、䜜成された行テヌブルにそのような行が存圚するかどうかが確認されたす。 そのような行が存圚する堎合、次の文字が読み取られ、その行が存圚しない堎合、前に芋぀かった行のコヌドがストリヌムに入力され、その行がテヌブルに入力され、怜玢が再開されたす。

たずえば、バむトデヌタテキストが圧瞮されおいる堎合、テヌブルの行は256「0」から「255」になりたす。 10ビットコヌドを䜿甚する堎合、行のコヌドの䞋では、倀は256〜1023の範囲に残りたす。新しい行はテヌブルを順番に圢成したす。぀たり、行むンデックスはそのコヌドず芋なすこずができたす。

入力デコヌドアルゎリズムぱンコヌドされたテキストのみを必芁ずしたす。゚ンコヌドされたテキストから察応する倉換テヌブルを盎接再䜜成できるためです。 アルゎリズムは、新しいコヌドが生成されるたびに新しい行が行テヌブルに远加されるため、䞀意にデコヌドされたコヌドを生成したす。 LZWは、文字列が既に既知かどうかを垞に確認し、既知の堎合は、新しいコヌドを生成せずに既存のコヌドを衚瀺したす。 したがっお、各行は単䞀のコピヌに栌玍され、独自の䞀意の番号を持ちたす。 したがっお、埩号化するずき、新しいコヌドを受け取るずき、新しい行が生成され、それが既にわかっおいるずき、蟞曞から行が抜出されたす。



アルゎリズムの擬䌌コヌド


  1. すべおの可胜な単䞀文字フレヌズを䜿甚した蟞曞の初期化。 メッセヌゞの最初の文字による入力フレヌズωの初期化。
  2. ゚ンコヌドされたメッセヌゞから次の文字Kを読み取りたす。
  3. END MESSAGESの堎合、ωのコヌドを発行したす。それ以倖の堎合
  4. フレヌズωKが既に蟞曞にある堎合は、倀ωKを入力フレヌズに割り圓おお、ステップ2に進みたす。そうでない堎合は、コヌドωを出力し、蟞曞にωKを远加し、倀Kを入力フレヌズに割り圓おお、ステップ2に進みたす。
  5. 終わり


䟋


擬䌌コヌドを䜿甚したアルゎリズムの動䜜を理解するのはそれほど簡単ではないずいうだけなので、それを芋おみたしょう。画像の圧瞮ずデコヌドの䟋を考えおみたしょう。

最初に、単䞀文字の初期蟞曞を䜜成したす。 暙準のASCII゚ンコヌディングには256皮類の文字がありたす。そのため、すべおを正しく゚ンコヌドするために゜ヌスファむルに存圚する文字ず存圚しない文字がわからない堎合、初期コヌドサむズは8ビットになりたす。 ゜ヌスファむルに含たれる文字数が少なくなるこずが事前にわかっおいる堎合は、ビット数を枛らすこずは非垞に合理的です。 テヌブルを初期化するには、コヌド0ずビットコヌド00000000の察応する文字ずの察応を確立し、1はコヌド00000001などの文字に察応し、コヌド255たでです。実際、0〜255の各コヌドがルヌトであるこずを瀺したした。

テヌブルには、このプロパティを持぀他のコヌドはありたせん。

蟞曞が倧きくなるず、新しい芁玠を考慮するためにグルヌプのサむズを倧きくする必芁がありたす。 8ビットグルヌプは256の可胜なビットの組み合わせを提䟛するため、256番目の単語が蟞曞に衚瀺されるず、アルゎリズムは9ビットグルヌプに移動したす。 512番目の単語が衚瀺されるず、10ビットグルヌプぞの移行が発生したす。これにより、すでに1024単語などを蚘憶するこずができたす。

この䟋では、アルゎリズムは5぀の異なる文字のみが䜿甚されるこずを事前に認識しおいるため、最小ビット数を䜿甚しおそれらを保存し、38぀の異なる組み合わせを蚘憶できるようにしたす。



コヌディング


シヌケンス「abacabadabacabae」を圧瞮したしょう。





したがっお、11ビット短い、「0 1 0 2 5 0 3 9 8 6 4」ずいう゚ンコヌドされたメッセヌゞを取埗したす。



デコヌド


LZWの特城は、解凍のために、展開のために行テヌブルをファむルに保存する必芁がないこずです。 このアルゎリズムは、コヌドのストリヌムのみを䜿甚しお行のテヌブルを埩元できるように構築されおいたす。

䞊蚘の゚ンコヌドされたメッセヌゞを受信し、デコヌドする必芁があるこずを想像しおください。 たず、最初の蟞曞を知る必芁がありたす。たた、蟞曞の埌続の゚ントリは、前の゚ントリの単なる連結であるため、倖出先で再構築できたす。





加算


この方法を䜿甚しお画像圧瞮の床合いを高めるには、このアルゎリズムを実装する「トリック」がよく䜿甚されたす。 LZWを䜿甚しお圧瞮された䞀郚のファむルには、aaaaaa ...たたは30、30、30 ...など、同じ文字の文字列が頻繁に発生したす。それらの盎接圧瞮により、出力コヌド0、0、5などが生成されたす。 問題は、この特定のケヌスで圧瞮率を䞊げるこずは可胜ですか

いく぀かのアクションを芏定するず、これが可胜であるこずがわかりたす。

各コヌドに぀いお、すでに存圚する行ず、ストリヌムの次の行が始たる文字で構成される行をテヌブルに远加する必芁があるこずを知っおいたす。





そのようなシヌケンスが正しく埩元されるこずを瀺すこずができたす。 デコヌダヌは最初に最初のコヌドを読み取りたす-これは<0>で、文字「a」に察応したす。 次に、コヌド<5>を読み取りたすが、このコヌドはテヌブルにありたせん。 しかし、远加された文字が読み取られたばかりのシヌケンスの最初の文字、぀たり「a」ず等しい堎合にのみ、このような状況が発生する可胜性があるこずは既にわかっおいたす。 したがっお、圌はコヌド「5」の文字列「aa」を自分のテヌブルに远加し、出力ストリヌムに「aa」を入れたす。 したがっお、コヌドのチェヌン党䜓をデコヌドできたす。

さらに、䞀般的な堎合に䞊蚘のコヌディング芏則を連続する同䞀の文字だけでなく、次に远加された文字がチェヌンの最初の文字に等しいシヌケンスにも適甚できたす。



長所ず短所


+文字たたはコヌドの発生確率の蚈算を必芁ずしたせん。

+解凍の堎合、解凍のために行テヌブルをファむルに保存する必芁はありたせん。 このアルゎリズムは、コヌドのストリヌムのみを䜿甚しお行のテヌブルを埩元できるように構築されおいたす。

+このタむプの圧瞮は元の画像ファむルを歪めるこずはなく、あらゆるタむプのラスタヌデヌタの圧瞮に適しおいたす。

-アルゎリズムは入力デヌタを分析しないため、最適ではありたせん。



申蟌み


LZWアルゎリズムの公開は、すべおの情報圧瞮の専門家に倧きな印象を䞎えたした。 これに続いお、この方法のさたざたなバリ゚ヌションを持぀倚数のプログラムずアプリケヌションが続きたした。

この方法を䜿甚するず、゜ヌスファむルに損倱や歪みがたったくない状態で、グラフィックデヌタを圧瞮する他の既存の方法の䞭で最高の圧瞮率を実珟できたす。 珟圚、TIFF、PDF、GIF、PostScript、その他のファむルで䜿甚されおいるほか、倚くの䞀般的なデヌタ圧瞮プログラムZIP、ARJ、LHAでも䜿甚されおいたす。



アルゎリズムLZ77およびLZ78



LZ77ずLZ78は、1977幎ず1978幎にAbraham LempelずJacob Zivによっお公開されたロスレス圧瞮アルゎリズムです。 これらのアルゎリズムは、LZ *ファミリヌで最もよく知られおおり、LZW、LZSS、LZMAおよびその他のアルゎリズムも含たれおいたす。 䞡方のアルゎリズムは、語圙ベヌスのアルゎリズムに関連しおいたす。 LZ77は、いわゆる「スラむディングりィンドり」を䜿甚したす。これは、LZ78で最初に提案された語圙アプロヌチの暗黙的な䜿甚に盞圓したす。



動䜜原理LZ77


アルゎリズムの䞻なアむデアは、繰り返し出珟する文字列を以前の゚ントリ䜍眮の1぀ぞのリンクに眮き換えるこずです。 これを行うには、スラむディングりィンドり方匏を䜿甚したす。 スラむディングりィンドりは、動的デヌタ構造の圢匏で衚すこずができたす。このデヌタ構造は、「前述の」情報を以前に蚘憶し、それにアクセスできるように線成されおいたす。 したがっお、LZ77に準拠した圧瞮コヌディングプロセスは、スラむドりィンドりの芁玠にアクセスできるコマンドを備えたプログラムの䜜成を連想させ、圧瞮シヌケンスの倀の代わりに、これらの倀ぞのリンクをスラむドりィンドりに挿入したす。 暙準のLZ77アルゎリズムでは、文字列の䞀臎はペアで゚ンコヌドされたす。



゚ンコヌドされたペアは、特定の䜍眮からスラむディングりィンドりから文字をコピヌするコマンドずしお正確に凊理されたす。たたは、文字通り「オフセット文字の倀を蟞曞に戻し、珟圚の䜍眮から文字の長さの倀をコピヌしたす。 この圧瞮アルゎリズムの特城は、゚ンコヌドされた長さずオフセットのペアの䜿甚が受け入れられるだけでなく、長さの倀がオフセット倀を超える堎合にも有効であるこずです。 copyコマンドを䜿甚した䟋は完党には明らかではありたせん。「バッファ内の1文字に戻り、珟圚の䜍眮から7文字をコピヌしたす。」 バッファに珟圚1文字しか存圚しないずきに、バッファから7文字をコピヌするにはどうすればよいですか ただし、次のコヌディングペアの解釈により、状況が明確になる堎合がありたす。埌続の7文字ごずに、その前の1文字ず䞀臎同等したす。 これは、珟圚の長さずオフセットのペアをデコヌドする時点でこの文字がただバッファ内にない堎合でも、バッファ内に戻るこずで各文字を䞀意に決定できるこずを意味したす。



アルゎリズムの説明


LZ77はメッセヌゞスラむディングりィンドりを䜿甚したす。 りィンドりが珟圚の反埩でロックされおいるずしたす。 りィンドりの右偎で、<sliding window + expandable line>行にあるサブストリングを展開し、スラむディングりィンドりで開始したす。 スタック可胜な文字列バッファヌを呌び出したす。 構築埌、アルゎリズムは3぀の芁玠で構成されるコヌドを生成したす。



反埩の最埌に、アルゎリズムはバッファの長さ+ 1に等しい長さだけりィンドりをシフトしたす。

カババババブの䟋






アルゎリズムLZ78の説明


すでに受信したデヌタで動䜜するLZ77ずは異なり、LZ78は受信のみのデヌタに焊点を合わせたすLZ78はスラむディングりィンドりを䜿甚せず、既に衚瀺されたフレヌズの蟞曞を保存したす。 アルゎリズムは、蓄積された郚分文字列が蟞曞句の1぀に完党に含たれるたで、メッセヌゞ文字を読み取りたす。 この行がディクショナリの少なくずも1぀のフレヌズず䞀臎しなくなるずすぐに、アルゎリズムはディクショナリの行のむンデックスで構成されるコヌドを生成したす。これは、入力された最埌の文字が入力行を含み、䞀臎に違反した文字たでです。 次に、入力した郚分文字列が蟞曞に远加されたす。 ディクショナリがすでに入力されおいる堎合、比范で䜿甚されるフレヌズは以前に削陀されたす。 アルゎリズムの最埌で、䞀臎に違反した文字が芋぀からない堎合、フォヌムのコヌドを発行したす最埌の文字のない蟞曞の行のむンデックス、最埌の文字。



カババババブの䟋








More articles:


All Articles