まず、各文字とその頻度をリストアップします。これらは、ハフマン木の初期ノードとなります。
次に、最も頻度が低い2つのノードを選び、それらを組み合わせて新しいノードを作成します。この新しいノードの頻度は元の2つのノードの頻度の合計となります。
このプロセスを繰り返し、全てのノードが一つの木になるまで続けます。
最終的に得られるハフマン木から、各データ項目に対するハフマンコードを生成できます。木のルートから各データ項目までのパスをたどり、左枝を'0'、右枝を'1'として符号化します。

入力DAEBCBACBBBCに対して上記のアルゴリズムを適用すると、以下のハフマン木を構築できます。

参考　ハフマン符号

各文字の出現頻度と割り当てられた符号は以下の通りです。

個数の多い文字ほど短い符号が割り当てられていることがわかります。

固定長で符号化した場合1文字あたり最低3bit必要になります。以下のように符号化してみましょう。

  A   B   C   D   E
 000 001 010 011 100

メッセージ全体は以下のようになり、全体は36bitです。

  D   A   E   B   C   B   A   C   B   B   B   C
011 000 100 001 010 001 000 010 001 001 001 010

上記の表を使ってハフマン符号で符号化すると以下のようになります。

   D   A    E B  C B  A   C B B B  C
1110 110 1111 0 10 0 110 10 0 0 0 10

全体は25bitであり、固定長の符号化と比べてサイズが小さいことが確認できます。

LZ77アルゴリズムについて

次にLZ77アルゴリズムについて解説していきます。
LZ77はランレングス法という圧縮方式をベースにして開発されたアルゴリズムです。

ランレングス法は以下の図のように同じ値が何回連続して出現するかを記録する手法です。

参考　今更だけど、データ圧縮についてまとめてみたい

LZ77はランレングス法を発展させたアルゴリズムです。単一の文字の繰り返しだけでなく、文字列の繰りかえしを圧縮することが可能です。

LZ77アルゴリズムでは、スライディングウィンドウという概念が重要です。これは、走査している文字列の現在位置の前後にある特定の長さの文字列集合を指します。

スライディングウィンドウは参照部、符号化部の二つの部分に分けられます。
参照部はすでに圧縮が完了した部分です。符号化部はこれから圧縮しようとしている部分です。

各ステップでは、参照部内で符号化部の文字列と最長に一致するパターンを探し出し、 そのパターンの参照部の最後尾からのオフセット、一致する長さ、そしてパターンに一致しなくなる最初の文字（不一致記号）を結果に追加します。

「オフセット」と「長さ」が共に0である場合、それは参照部中に一致する文字列パターンが存在しなかったことを示します。

また、参照部のパターンとの一致は繰り返しを許容します。 例えば、参照部がabで、走査している符号化部がababacであった場合、abという文字列パターンがababaと5文字分繰り返されていると解釈します。

文章だけでは理解しにくいかもしれませんので、具体的な例を用いて説明します。上図のaacaacabcabaacという文字列を長さ6のスライディングウィンドウを用いたLZ77アルゴリズムで圧縮する手順を見てみましょう。この手順は以下の通りです。

最初の文字はaです。参照部は空なので一致するパターンはありません。
そのため、結果に(0,0,a)を追加します。
参照部はaで、符号化部はacaaです。
符号化部先頭のaだけが一致します。この一致する長さは1で、参照部最後尾からのaパターンのオフセットは1です。
不一致記号はcなので、結果に(1,1,c)を追加します。
参照部はaacで、符号化部はaacaです。
aacaという部分がaacというパターンの4文字分繰り返しとなっています。
符号化部の長さが4であるため、aacaが最長の一致する文字列となります。aacパターンの最後尾からのオフセットは3なので、結果に(3,4,b)を追加します。
参照部はcaacabで、符号化部はcabaです。
cabというパターンが最も長く一致します。
この一致する長さは3で、このパターンの参照部最後尾からのオフセットも3です。
そのため、結果に(3,3,a)を追加します。
参照部abcabaで、符号化部はaacです。
aというパターンが2文字分繰り返されています。
このパターンの参照部最後尾からのオフセットは1なので、結果に(1,2,c)を追加します。
最終的な出力は(0,0,a),(1,1,c),(3,4,b),(3,3,a),(1,2,c)となります。

以上がLZアルゴリズムによる圧縮手順となります。

解凍ではタプル内の情報を用いて参照部内の一致するパターンを探し出し、そのパターンと次に一致しない文字を用いて元の文字列を再構築しています。

先ほど圧縮した結果である(0,0,a),(1,1,c),(3,4,b),(3,3,a),(1,2,c)を解凍する手順を1ステップずつ図解していきます。

最初のタプルは(0,0,a)です。参照部は空です。マッチする文字列パターンはありません。
解凍結果にaをセットし、参照部をaに更新します。
次のタプルは(1,1,c)です。参照部最後尾から１文字前のパターンaが1文字分繰り返され、次の文字がcであることを示しています。したがって、解凍された文字列はaacとなります。参照部はaacに更新されます。
次のタプルは(3,4,b)です。参照部内最後尾から3文字前で始まる文字列パターンaacが4文字分繰り返され、次の文字がbであることを示しています。したがって、解凍された文字列はaacaacabとなります。参照部はcaacabに更新されます。
次のタプルは(3,3,a)で、参照部最後尾から3文字前で始まる文字列パターンcabが3文字分繰り返され、次の文字がaであることを示しています。したがって、解凍された文字列はaacaacabcabaとなります。参照部はabcabaに更新されます。
最後のタプルは(1,2,c)です。参照部最後尾から１文字前のパターンaが2文字分繰り返され、次の文字がcであることを示しています。したがって、最終的に解凍された文字列はaacaacabcabaacとなります。