あなたはファイル圧縮がどのように働くかをあなた自身に尋ねましたか?貪欲なアルゴスの背後の数学

背景：

はい、コンピュータのファイルの圧縮の基礎柱は-スポイラーアラート-数学、画像と基本的にちょうどフレームのシーケンスであるビデオのために、彼らは損失性の圧縮技術をサポートするため、わずかに異なっている.
圧縮技術の2種類があり、損失性と無損失です.
名前自体としての損失のテクニックは、我々がまだ見て、ビデオや画像で何が起こるかを理解することができますので、圧縮後に元のデータのいくつかを失うことを受け入れる、これらの技術は、テキストに適用されることはできませんので、メッセージの意味は失われます、あなたのテキストの受信機は、例えば、メッセージの中で彼に伝えたかった冗談を理解しないでしょう.

無意味のテクニックは圧縮後に任意の貴重なデータを失うことはありません、彼らは最高のテキストのような圧縮前にその元の情報の一部を失うことをサポートしていないデータに適しています.
80年代初期のマイクロBBC(8ビット)のコンピュータがマックス800 KBの記憶だけを持っていたので、テキストのための無損失のテクニックは生命に来ました.それで、我々はビットの途方もない量を使わないでください?ASCIIテーブルの各文字が8ビット(1ビット= 0または1)で符号化されるので、10 000文字のテキストは私たちの記憶ディスクの10 %である80 000ビット= 80 KBを重くします.私たちのストレージディスクは、10の小さなテキストファイルの最大サイズを格納することができます.痛みを感じますか.
しかし、David Huffmanと呼ばれる数学者は、スポイラー・アラート-ハフマン符号化と呼ばれるファイルを圧縮する方法を発見しました.ハフマン符号化は、8ビットの各文字を代表する代わりにファイル圧縮のアルゴリズムである.3ビットまたは最大8ビットあるいは9ビットでさえ、それらのより高いビットはテキストの最も頻繁なシンボルのためである.基本的に「E」または「空き空間」のいずれかである最も頻繁な記号は、1ビットのみで表される.
また、ASCIIテーブルの各々のシンボルの通常の8ビット表現におけるもう一つの問題があります、' A '表現が0100001と' B 'が01000010であると仮定しましょう
それで、『AB』は010000101000010です、そして、これはコンピュータが2進数で誰が誰であるかについて、わかりません.
大変な苦労.イエス.

アルゴリズム

まず、想像上のテキストを右にしましょうか.そして、我々は、テキスト内の各文字の周波数を計算し、各文字とその周波数の辞書(マップ)を返すプログラムを持っているあなたは目的を学習するためにこのプログラムを書きたいかもしれません.そして、このプログラムはこれを返します.
入力inputs = (a1,a2, ...,ap) P文字weights= (w1,w2,...,wp) テキストのそれぞれの重み
入力= = (' A '、' b '、' c ', ' d ')とw = ( 10 , 15 , 30 , 16 )を仮定しましょう

inputs = {'d':16,'c':30,'a':10,'b':15}

ハフマンアルゴリズムは、それぞれのコードPを出力します.output = (c1,c2,...,cp).アルゴリズムはoutput = (c1,c2,...,cp). 入力を重みに基づいてソートし、次のようにソートされた二分木を生成します.

そして最後に、ツリーを通って旅行することによってコードテーブルを生成し、それぞれの文字を見つけるために、もし左に行くと0、右側の文字を見つけるまであなたのコードに1を追加します.code = ""
if (root.left):
code = code + "0"
else:
code = code + "1"
チャー
頻度
コード
サイズ
エー
10
110
3ビット
b
15
111
3ビット
c
30
0
1ビット
ディー
16
10
2ビット
私が以前に言ったように、最も頻繁なキャラクタが1ビットでコード化されるこの例では、' c 'は0です、それはそれを天才観念にします、そして、最も頻繁なキャラクタはビットのより大きい数(符号化:110)でコード化されます.ファイル自体が非常に小さいので、ここでの圧縮効果はとても効率的ではありません.ファイル自体が10 + 15 + 30 + 16 = 71文字を含んでいるので、圧縮がファイルがサイズを圧縮する前に、ファイルサイズがそうである圧縮の後で、ファイルは71 * 8 = 568ビット、arround
ファイルが失われたことを意味する10 * 3 + 15 * 3 + 30 * 1 + 16 * 2 = 137ビット
568 - 137の= 431ビットarroundは、それさえ価値がないデータを失うことなくその元のサイズの76 %をあなたが考えます?
ここでは、インターネット上で私の最初の記事を終了し、Twitterで私に従って、次の我々は、もう少し複雑で楽しいが、写真やビデオに同じことを行う次回!そういうわけで、私たちはコーディングに情熱を持っています、また、私はここでこのアルゴリズムの私のPython実装を共有します、そして
Github repo
ASLO、接続して、より多くの知識を共有しましょう.
または

def sort_dict(inputs):
    frequencies_list = list(inputs.keys())
    frequencies_list.sort()
    temp = []
    for  item in frequencies_list:
        temp.append(inputs[item])
    new_dict = dict(zip(frequencies_list,temp))
    return new_dict



def huffmanTree(inputs):
    temp = sort_dict(inputs)#temporary sorted dict
    condition_arg =  list(temp.keys())
    condition = len(condition_arg) > 1
    while condition:
        temp = sort_dict(temp)
        char = list(temp.values())
        freq = list(temp.keys())
        if len(char) > 1 and len(freq) > 1:
            freq0 = freq.pop(0)
            freq1 = freq.pop(0)
            value0 = char.pop(0)
            value1 = char.pop(0)
        else:
            break
        temp = {freq0+freq1:(value0,value1)}
        remain_temp = dict(zip(freq,char)) 
        temp.update(remain_temp)
    return temp


def huffman_encode(char,inputs):
    temp = huffmanTree(inputs)
    temp = list(temp.values())
    temp = temp[0]
    print(temp)
    search(temp,char,"")

def search(root,char,code):
    code = code
    if(len(root)>1):
        search(root[0],char,code+"0")
        search(root[1],char,code+"1")
    else:
        if (root == char):
            print(code)





inputs1 = {12:"c",16:"e",9:"b",13:"d",5:"a",16:"e",45:"f"}
input2 = {10:'a',15:'b',30:'c',16:'d',29:'e'}

huffman_encode('a',inputs1) #should print 010