<h1 id="deflate%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AE%E6%A6%82%E8%A6%81">
<a class="header-anchor-link" href="#deflate%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AE%E6%A6%82%E8%A6%81" aria-hidden="true"></a> DEFLATEアルゴリズムの概要</h1>
<p>DEFLATEはzipやgzip, PNGファイルなどにおいて使用される圧縮アルゴリズムです。</p>
<p>DEFLATEではまずLZ77で圧縮を行い、その後にハフマン符号化で圧縮するという流れで圧縮が行われます。</p>
<p>この記事では第一回としてハフマン符号やLZ77とは何かについて解説していきます。</p>
<h1 id="%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E7%AC%A6%E5%8F%B7%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6">
<a class="header-anchor-link" href="#%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E7%AC%A6%E5%8F%B7%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6" aria-hidden="true"></a> ハフマン符号について</h1>
<p>ハフマン符号化は、データ圧縮に使用される効率的な符号化手法の一つです。<br>
<strong>この手法は頻度が高いデータは短いコードを、頻度が低いデータは長いコードを割り当てます。</strong><br>
この符号はハフマン木というデータ構造に基づいて決定されます。</p>
<h3 id="%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E6%9C%A8">
<a class="header-anchor-link" href="#%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E6%9C%A8" aria-hidden="true"></a> ハフマン木</h3>
<p>ハフマン木は、ハフマン符号化に使用されるデータ構造です。これは、出現頻度に基づいてデータを効率的に符号化するための二分木です。</p>
<h3 id="%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E6%9C%A8%E3%82%92%E6%A7%8B%E6%88%90%E3%81%99%E3%82%8B%E3%81%9F%E3%82%81%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0">
<a class="header-anchor-link" href="#%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E6%9C%A8%E3%82%92%E6%A7%8B%E6%88%90%E3%81%99%E3%82%8B%E3%81%9F%E3%82%81%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0" aria-hidden="true"></a> ハフマン木を構成するためのアルゴリズム</h3>
<p>ハフマン木を作成するための手順は以下の通りです：</p>
<ol>
<li>
<p>まず、各文字とその頻度をリストアップします。これらは、ハフマン木の初期ノードとなります。</p>
</li>
<li>
<p>次に、最も頻度が低い2つのノードを選び、それらを組み合わせて新しいノードを作成します。この新しいノードの頻度は元の2つのノードの頻度の合計となります。</p>
</li>
<li>
<p>このプロセスを繰り返し、全てのノードが一つの木になるまで続けます。</p>
</li>
<li>
<p>最終的に得られるハフマン木から、各データ項目に対するハフマンコードを生成できます。木のルートから各データ項目までのパスをたどり、左枝を'0'、右枝を'1'として符号化します。</p>
</li>
</ol>
<h3 id="%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E6%9C%A8%E3%81%AE%E4%BE%8B">
<a class="header-anchor-link" href="#%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E6%9C%A8%E3%81%AE%E4%BE%8B" aria-hidden="true"></a> ハフマン木の例</h3>
<p>入力<code>DAEBCBACBBBC</code>に対して上記のアルゴリズムを適用すると、以下のハフマン木を構築できます。</p>
<p><img src="https://storage.googleapis.com/zenn-user-upload/089750e2079f-20231011.png" loading="lazy" class="md-img"></p>
<blockquote>
<p>参考　<a href="https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E7%AC%A6%E5%8F%B7" target="_blank" rel="nofollow noopener noreferrer">ハフマン符号</a></p>
</blockquote>
<p>各文字の出現頻度と割り当てられた符号は以下の通りです。</p>
<table>
<thead>
<tr>
<th>文字</th>
<th>個数</th>
<th>符号</th>
</tr>
</thead>
<tbody>
<tr>
<td>B</td>
<td>5</td>
<td>0</td>
</tr>
<tr>
<td>C</td>
<td>3</td>
<td>10</td>
</tr>
<tr>
<td>A</td>
<td>2</td>
<td>110</td>
</tr>
<tr>
<td>D</td>
<td>1</td>
<td>1110</td>
</tr>
<tr>
<td>E</td>
<td>1</td>
<td>1111</td>
</tr>
</tbody>
</table>
<p>個数の多い文字ほど短い符号が割り当てられていることがわかります。</p>
<h5>データサイズの比較</h5>
<p>固定長で符号化した場合1文字あたり最低3bit必要になります。以下のように符号化してみましょう。</p>
<div class="code-block-container"><pre><code>  A   B   C   D   E
 000 001 010 011 100
</code></pre></div><p>メッセージ全体は以下のようになり、全体は36bitです。</p>
<div class="code-block-container"><pre><code>  D   A   E   B   C   B   A   C   B   B   B   C
011 000 100 001 010 001 000 010 001 001 001 010
</code></pre></div><p>上記の表を使ってハフマン符号で符号化すると以下のようになります。</p>
<div class="code-block-container"><pre><code>   D   A    E B  C B  A   C B B B  C
1110 110 1111 0 10 0 110 10 0 0 0 10
</code></pre></div><p>全体は25bitであり、固定長の符号化と比べてサイズが小さいことが確認できます。</p>
<h1 id="lz77%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6">
<a class="header-anchor-link" href="#lz77%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6" aria-hidden="true"></a> LZ77アルゴリズムについて</h1>
<p>次にLZ77アルゴリズムについて解説していきます。<br>
LZ77はランレングス法という圧縮方式をベースにして開発されたアルゴリズムです。</p>
<p>ランレングス法は以下の図のように同じ値が何回連続して出現するかを記録する手法です。</p>
<p><img src="https://storage.googleapis.com/zenn-user-upload/b960c7e3266a-20231011.png" loading="lazy" class="md-img"></p>
<blockquote>
<p>参考　<a href="https://www.plan-b.co.jp/blog/tech/10282/" target="_blank" rel="nofollow noopener noreferrer">今更だけど、データ圧縮についてまとめてみたい</a></p>
</blockquote>
<h3 id="lz77%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AE%E5%9C%A7%E7%B8%AE%E3%82%B9%E3%83%86%E3%83%83%E3%83%97">
<a class="header-anchor-link" href="#lz77%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AE%E5%9C%A7%E7%B8%AE%E3%82%B9%E3%83%86%E3%83%83%E3%83%97" aria-hidden="true"></a> LZ77アルゴリズムの圧縮ステップ</h3>
<p>LZ77はランレングス法を発展させたアルゴリズムです。単一の文字の繰り返しだけでなく、文字列の繰りかえしを圧縮することが可能です。</p>
<h4 id="%E3%82%B9%E3%83%A9%E3%82%A4%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0%E3%82%A6%E3%82%A3%E3%83%B3%E3%83%89%E3%82%A6">
<a class="header-anchor-link" href="#%E3%82%B9%E3%83%A9%E3%82%A4%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0%E3%82%A6%E3%82%A3%E3%83%B3%E3%83%89%E3%82%A6" aria-hidden="true"></a> スライディングウィンドウ</h4>
<p>LZ77アルゴリズムでは、<strong>スライディングウィンドウ</strong>という概念が重要です。これは、走査している文字列の現在位置の前後にある特定の長さの文字列集合を指します。</p>
<p>スライディングウィンドウは参照部、符号化部の二つの部分に分けられます。<br>
参照部はすでに圧縮が完了した部分です。符号化部はこれから圧縮しようとしている部分です。</p>
<p><img src="https://storage.googleapis.com/zenn-user-upload/21b5331fa9ed-20231014.png" loading="lazy" class="md-img"></p>
<p><strong>各ステップでは、参照部内で符号化部の文字列と最長に一致するパターンを探し出し、</strong> そのパターンの参照部の最後尾からのオフセット、一致する長さ、そしてパターンに一致しなくなる最初の文字（不一致記号）を結果に追加します。</p>
<p><strong>「オフセット」と「長さ」が共に0である場合、それは参照部中に一致する文字列パターンが存在しなかったことを示します。</strong></p>
<p><strong>また、参照部のパターンとの一致は繰り返しを許容します。</strong> 例えば、参照部が<code>ab</code>で、走査している符号化部が<code>ababac</code>であった場合、<code>ab</code>という文字列パターンが<code>ababa</code>と5文字分繰り返されていると解釈します。</p>
<h4 id="%E5%85%B7%E4%BD%93%E4%BE%8B">
<a class="header-anchor-link" href="#%E5%85%B7%E4%BD%93%E4%BE%8B" aria-hidden="true"></a> 具体例</h4>
<p>文章だけでは理解しにくいかもしれませんので、具体的な例を用いて説明します。上図の<code>aacaacabcabaac</code>という文字列を長さ6のスライディングウィンドウを用いたLZ77アルゴリズムで圧縮する手順を見てみましょう。この手順は以下の通りです。</p>
<aside class="msg message"><span class="msg-symbol">!</span><div class="msg-content">
<p>図では水色が不一致文字、紫が参照部、青がパターンに一致した文字列を表します。<br>
囲んである部分が符号化部です。</p>
</div></aside>
<ol>
<li>最初の文字は<code>a</code>です。参照部は空なので一致するパターンはありません。<br>
そのため、結果に(0,0,a)を追加します。<br>
<img src="https://storage.googleapis.com/zenn-user-upload/9bb0a67aaf70-20231014.png" loading="lazy" class="md-img">
</li>
<li>参照部は<code>a</code>で、符号化部は<code>acaa</code>です。<br>
符号化部先頭の<code>a</code>だけが一致します。この一致する長さは1で、参照部最後尾からの<code>a</code>パターンのオフセットは1です。<br>
不一致記号は<code>c</code>なので、結果に(1,1,c)を追加します。<br>
<img src="https://storage.googleapis.com/zenn-user-upload/bb9a76a0c6bf-20231014.png" loading="lazy" class="md-img">
</li>
<li>参照部は<code>aac</code>で、符号化部は<code>aaca</code>です。<br>
<code>aaca</code>という部分が<code>aac</code>というパターンの4文字分繰り返しとなっています。<br>
符号化部の長さが4であるため、<code>aaca</code>が最長の一致する文字列となります。<code>aac</code>パターンの最後尾からのオフセットは3なので、結果に(3,4,b)を追加します。<br>
<img src="https://storage.googleapis.com/zenn-user-upload/41b15d71aa57-20231014.png" loading="lazy" class="md-img">
</li>
<li>参照部は<code>caacab</code>で、符号化部は<code>caba</code>です。<br>
<code>cab</code>というパターンが最も長く一致します。<br>
この一致する長さは3で、このパターンの参照部最後尾からのオフセットも3です。<br>
そのため、結果に(3,3,a)を追加します。<br>
<img src="https://storage.googleapis.com/zenn-user-upload/db4641fb3a22-20231014.png" loading="lazy" class="md-img">
</li>
<li>参照部<code>abcaba</code>で、符号化部は<code>aac</code>です。<br>
<code>a</code>というパターンが2文字分繰り返されています。<br>
このパターンの参照部最後尾からのオフセットは1なので、結果に(1,2,c)を追加します。<br>
<img src="https://storage.googleapis.com/zenn-user-upload/0631d50886d4-20231014.png" loading="lazy" class="md-img">
</li>
<li>最終的な出力は(0,0,a),(1,1,c),(3,4,b),(3,3,a),(1,2,c)となります。</li>
</ol>
<p>以上がLZアルゴリズムによる圧縮手順となります。</p>
<h3 id="lz77%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AE%E8%A7%A3%E5%87%8D%E3%82%B9%E3%83%86%E3%83%83%E3%83%97">
<a class="header-anchor-link" href="#lz77%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AE%E8%A7%A3%E5%87%8D%E3%82%B9%E3%83%86%E3%83%83%E3%83%97" aria-hidden="true"></a> LZ77アルゴリズムの解凍ステップ</h3>
<p>解凍ではタプル内の情報を用いて参照部内の一致するパターンを探し出し、そのパターンと次に一致しない文字を用いて元の文字列を再構築しています。</p>
<p>先ほど圧縮した結果である(0,0,a),(1,1,c),(3,4,b),(3,3,a),(1,2,c)を解凍する手順を1ステップずつ図解していきます。</p>
<ol>
<li>最初のタプルは(0,0,a)です。参照部は空です。マッチする文字列パターンはありません。<br>
解凍結果に<code>a</code>をセットし、参照部を<code>a</code>に更新します。<br>
<img src="https://storage.googleapis.com/zenn-user-upload/4366a3347260-20231013.png" loading="lazy" class="md-img">
</li>
<li>次のタプルは(1,1,c)です。参照部最後尾から１文字前のパターン<code>a</code>が1文字分繰り返され、次の文字が<code>c</code>であることを示しています。したがって、解凍された文字列は<code>aac</code>となります。参照部は<code>aac</code>に更新されます。<br>
<img src="https://storage.googleapis.com/zenn-user-upload/9ee60ad8efe1-20231013.png" loading="lazy" class="md-img">
</li>
<li>次のタプルは(3,4,b)です。参照部内最後尾から3文字前で始まる文字列パターン<code>aac</code>が4文字分繰り返され、次の文字が<code>b</code>であることを示しています。したがって、解凍された文字列は<code>aacaacab</code>となります。参照部は<code>caacab</code>に更新されます。<br>
<img src="https://storage.googleapis.com/zenn-user-upload/471c7a1341fe-20231013.png" loading="lazy" class="md-img">
</li>
<li>次のタプルは(3,3,a)で、参照部最後尾から3文字前で始まる文字列パターン<code>cab</code>が3文字分繰り返され、次の文字が<code>a</code>であることを示しています。したがって、解凍された文字列は<code>aacaacabcaba</code>となります。参照部は<code>abcaba</code>に更新されます。<br>
<img src="https://storage.googleapis.com/zenn-user-upload/c03636bd2f3c-20231013.png" loading="lazy" class="md-img">
</li>
<li>最後のタプルは(1,2,c)です。参照部最後尾から１文字前のパターン<code>a</code>が2文字分繰り返され、次の文字が<code>c</code>であることを示しています。したがって、最終的に解凍された文字列は<code>aacaacabcabaac</code>となります。<br>
<img src="https://storage.googleapis.com/zenn-user-upload/48ac9fc7258c-20231013.png" loading="lazy" class="md-img">
</li>
</ol>
<p>以上がLZ77アルゴリズムによる解凍手順となります。</p>
<h1 id="lzss%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6">
<a class="header-anchor-link" href="#lzss%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6" aria-hidden="true"></a> LZSSについて</h1>
<p>実際のDEFLATEではLZ77を改良したLZSSが使用されています。</p>
<p>LZ77の出力ではパターンの一致があろうとなかろうと<strong>オフセット、一致する長さ、そしてパターンに一致しなくなる最初の文字（不一致記号）</strong> の組が出力されました。</p>
<p>LZSSの出力は以下のように一致するパターンがある場合とない場合で出力が異なります。</p>
<p>・一致するパターンがない場合<br>
(<strong>0</strong>、不一致記号)<br>
・一致するパターンが存在する場合<br>
(<strong>1</strong>、一致するパターンのオフセット、一致する長さ)</p>
<p>符号の先頭の太文字はスライディングウィンドウ内のパターンに一致したかどうかを表す1bitのフラグです。</p>
<p>このようにすることで一致するバターンがないときにオフセット、一致長を符号化する必要がないのでさらに圧縮サイズが効率化されます。</p>
<h1 id="%E3%81%BE%E3%81%A8%E3%82%81">
<a class="header-anchor-link" href="#%E3%81%BE%E3%81%A8%E3%82%81" aria-hidden="true"></a> まとめ</h1>
<p>DEFLATEアルゴリズムの構成要素であるハフマン符号とLZ77(LZSS)アルゴリズムについて解説しました。</p>
<p>次回の記事ではこれらの要素がDEFLATEの中でどのように組み合わさっているのかについて解説します。</p>
<p>この記事が参考になった方はいいねを押してもらえると執筆の励みになります。よろしくお願いします。</p>
<h1 id="%E5%8F%82%E8%80%83">
<a class="header-anchor-link" href="#%E5%8F%82%E8%80%83" aria-hidden="true"></a> 参考</h1>
<p><span class="embed-block zenn-embedded zenn-embedded-card"><iframe id="zenn-embedded__757441082043d" src="https://embed.zenn.studio/card#zenn-embedded__757441082043d" data-content="https%3A%2F%2Fwww.slideshare.net%2F7shi%2Fdeflate" frameborder="0" scrolling="no" loading="lazy"></iframe></span><a href="https://www.slideshare.net/7shi/deflate" style="display:none" target="_blank" rel="nofollow noopener noreferrer">https://www.slideshare.net/7shi/deflate</a><br style="display:none">
<span class="embed-block zenn-embedded zenn-embedded-card"><iframe id="zenn-embedded__c6a95717f1aa4" src="https://embed.zenn.studio/card#zenn-embedded__c6a95717f1aa4" data-content="https%3A%2F%2Fwww.plan-b.co.jp%2Fblog%2Ftech%2F10282%2F" frameborder="0" scrolling="no" loading="lazy"></iframe></span><a href="https://www.plan-b.co.jp/blog/tech/10282/" style="display:none" target="_blank" rel="nofollow noopener noreferrer">https://www.plan-b.co.jp/blog/tech/10282/</a><br style="display:none">
<span class="embed-block zenn-embedded zenn-embedded-card"><iframe id="zenn-embedded__5fe261d87e5c3" src="https://embed.zenn.studio/card#zenn-embedded__5fe261d87e5c3" data-content="http%3A%2F%2Fwww.nct9.ne.jp%2Fm_hiroi%2Flight%2Fpyalgo32.html" frameborder="0" scrolling="no" loading="lazy"></iframe></span><a href="http://www.nct9.ne.jp/m_hiroi/light/pyalgo32.html" style="display:none" target="_blank" rel="nofollow noopener noreferrer">http://www.nct9.ne.jp/m_hiroi/light/pyalgo32.html</a><br style="display:none">
<span class="embed-block zenn-embedded zenn-embedded-card"><iframe id="zenn-embedded__9f14520cbe50e" src="https://embed.zenn.studio/card#zenn-embedded__9f14520cbe50e" data-content="https%3A%2F%2Fcognicull.com%2Fja%2Fudjx8co5" frameborder="0" scrolling="no" loading="lazy"></iframe></span><a href="https://cognicull.com/ja/udjx8co5" style="display:none" target="_blank" rel="nofollow noopener noreferrer">https://cognicull.com/ja/udjx8co5</a></p>


図解DEFLATEアルゴリズム 1/2 ー ハフマン符号とLZ77アルゴリズム

ハフマン木を構成するためのアルゴリズム

LZ77アルゴリズムの圧縮ステップ

LZ77アルゴリズムの解凍ステップ

gzip

図解DEFLATEアルゴリズム 1/2 ーハフマン符号とLZ77アルゴリズム

Discussion