可変長符号
情報源の記号に対して割り当てる符号を可変長とする符号
情報源が誤りなしで圧縮および解凍（可逆圧縮）され、依然として記号として読み取られることを可能にする
Wikipediaより
可変長符号の一つであるハフマン符号について -> Python3でハフマン符号化
例1
アルファベット26文字（A、B、... Z）に、次のように5ビットのバイナリコードが割り当てられているとします。
1.A：00001
2.B：00010
3.C：00011
⋮
26.Z：11010
ABRACADABRAが与えられた場合、5ビットの2進表現を使用して、以下のようにエンコードされます。
ABRACADABRA:
00001 00010 10010 00001 00011 00001 00100 00001 00010 10010 00001
逆にこれをデコードするには、一度に5ビットを読み取り、上記の割り当てに従って変換します。
この例では、Dは1回出現し、Aは5回出現しますが、両方ともバイナリコードで5ビットが割り当てられています。
また、5・11 = 55ビット使用します。
例2
次に、以下のように2ビットのバイナリコードが割り当てられているとします。
A : 0
B : 1
R : 01
C : 10
D : 11
この時、ABRACADABRAは以下のようにエンコードされます。
0 1 01 0 10 0 11 0 1 01 0
これは例1の55ビットと比べると、15ビットしか使用していません。
しかし、このコードは文字を区切るための空白に依存します。 空白がなければ、010101001101010はRRRARBRRAなどのように様々なパターンでデコードされてしまいます。
では、区切り文字(空白など)を使わずに文字列をコンパクトにエンコードするにはどうしたらよいか？
ある文字のコードが他の文字のコードの接頭辞ではない場合は、区切り文字は不要です。
0、00、001、0011は00110の接頭辞です。
例2の場合
A : 0
B : 1
R : 01
C : 10
D : 11
AのコードはRの接頭辞、BのコードはCとDの接頭辞です。
そこで、他の文字コードの接頭辞にならないように文字コードを割り当てる方法を考えます。
ここでは、M個の葉を持つ二分木を用いて考えます。
二分木は、M個の異なる文字を持つ任意のメッセージをエンコードするために使うことができます（一つの葉は一つの文字を保持します）。
左:0、右:1として各文字のコードは、ルート(root 「根」にあたるノード)からその文字を保持するリーフ(葉)までのパス(経路)によって決めます。
これを用いると、文字列ABRACADABRAは、それぞれ次のように文字コードが割り当てられます。
A : 11
B : 00
C : 010
D : 10
R : 011
ABRACADABRAは以下のようにエンコードされます。
11 00 011 11 010 11 10 11 00 011 11
このように、二分木を用いると、文字コードが他の文字コードの接頭辞ではないことを保証するので、文字列は木から一意にデコード可能になります。
デコードの方法としては、ルートから始めて、メッセージのビットに従ってツリーの下に進み、リーフに遭遇するたびに、そのリーフに文字を出力し、再びルートから再開します。
可変長符号化の説明は以上になります。
次に、与えられた文字列に対して最短の二分木を考える必要が出てきます。
ここで、D.ハフマンが考えた与えられた文字列に対して最小の長さのビット列を導く二分木を計算するための方法「ハフマン符号化」を用います。
Python3でハフマン符号化