Help us understand the problem. What is going on with this article?

可変長符号とは

可変長符号

情報源の記号に対して割り当てる符号を可変長とする符号
情報源が誤りなしで圧縮および解凍(可逆圧縮)され、依然として記号として読み取られることを可能にする
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は、それぞれ次のように文字コードが割り当てられます。
スクリーンショット 2019-08-02 17.14.56.png
A : 11
B : 00
C : 010
D : 10
R : 011
ABRACADABRAは以下のようにエンコードされます。
11 00 011 11 010 11 10 11 00 011 11

このように、二分木を用いると、文字コードが他の文字コードの接頭辞ではないことを保証するので、文字列は木から一意にデコード可能になります。
デコードの方法としては、ルートから始めて、メッセージのビットに従ってツリーの下に進み、リーフに遭遇するたびに、そのリーフに文字を出力し、再びルートから再開します。

可変長符号化の説明は以上になります。

次に、与えられた文字列に対して最短の二分木を考える必要が出てきます。

ここで、D.ハフマンが考えた与えられた文字列に対して最小の長さのビット列を導く二分木を計算するための方法「ハフマン符号化」を用います。
Python3でハフマン符号化

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした