당신은 자신의 파일 압축이 어떻게 작동하는지 물어본 적이 있습니까?탐욕 알고리즘 뒤의 수학

약간의 배경:

네, 컴퓨터 파일 압축의 기초 기둥은 - 교란판 경보 - 수학입니다. 기본적으로 프레임 서열만 있는 이미지와 영상에 대해 이것은 약간 다릅니다. 왜냐하면 그들은 손실 압축 기술을 지원하기 때문입니다.
두 가지 압축 기술이 있는데, 유손압축과 무손압축이다.
손상된 기술은 그 이름 자체가 설명한 바와 같이 압축된 후에 원시 데이터를 잃어버리는 것을 받아들인다. 왜냐하면 우리는 영상이나 사진에서 발생하는 일을 볼 수 있고 이해할 수 있기 때문이다. 이런 기술은 텍스트에 응용할 수 없다. 왜냐하면 메시지의 의미가 잃어버리기 때문이다. 예를 들어 당신의 텍스트 수신자는 당신이 메시지에서 그에게 말하고 싶은 농담을 이해하지 못할 것이다.

무손실 기술은 압축된 후에 가치 있는 데이터를 잃어버리지 않습니다. 압축하기 전에 원본 정보를 잃어버리는 데이터(예를 들어 텍스트)를 지원하지 않는 데 가장 적합합니다.
80년대 초반의 마이크로 BBC(8위) 등 컴퓨터의 최대 저장 용량은 800kb에 불과했기 때문에 텍스트 무손상 기술이 생겨났다.그래서 우리는 대량의 비트를 사용하지 않을 수 있습니까?ascii 테이블의 모든 문자는 8비트로 인코딩되어 있기 때문에 (1비트 = 0 또는 1), 10000자모의 텍스트의 무게는 80000비트 = 80KB입니다. 이것은 저장 디스크의 10%입니다.우리의 저장 디스크는 최대 10개의 작은 텍스트 파일만 저장할 수 있다...아파요?
그러나 데이비드 허프만(David Huffman)이라는 수학자가 파일을 압축하는 방법을 발견했다. - 교란판 경보 - 하프만 인코딩, 하프만 인코딩은 파일 압축 알고리즘으로 모든 문자(연구논문의 기호, 1995)를 8위가 아니라 각 기호를 1위 2위로 표시한다.3비트, 심지어 최대 8비트, 심지어 9비트, 그러나 비교적 높은 비트는 텍스트에서 빈도가 가장 낮은 기호에 사용되기 때문에 실제로는 공간을 많이 차지하지 않는다.텍스트에서 가장 흔히 볼 수 있는 기호는 기본적으로'e'또는 공백이며, 단지 1비트로만 표시된다.
그 밖에 ascii표에서 각 기호의 정상적인 8자리 표시에 또 다른 문제가 있다. 가령'a'는 0100001,'b'는 01000010을 나타낸다.
그래서'ab'는 0100010100010입니다. 이것은 읽을 수 없는 것입니다. 컴퓨터는 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"
타다
주파수
비밀번호
크기
하나
십
110
3비트
b
십오
111
3비트
c
삼십
0
1 비트
d
십육
십
2비트
내가 전에 말했듯이 이 예에서 가장 빈번한 문자는 1비트로 인코딩하고'c'는 0이다. 이것은 천재적인 생각이다. 가장 빈번하지 않은 문자는 더 많은 비트로 인코딩한다('a':110).파일 자체가 매우 작고 10+15+30+16=71자만 포함되어 있기 때문에 압축하기 전에 파일의 무게는 71*8=568비트로 약 0.55천 비트이며 압축된 파일의 크기는 다음과 같습니다.
10*3+15*3+30*1+16*2=137비트, 파일 분실
568-137=431위는 원시 크기의 76% 근처에 있고 심지어 데이터를 잃어버리지 않았습니다. 가치가 있다고 생각하지 않습니까?
제가 인터넷에 올린 첫 번째 글은 여기까지입니다. 트위터에서 저에게 더 많은 정보를 알려주세요. 다음에 사진과 동영상을 똑같이 처리하겠습니다. 이것은 좀 복잡하지만 재미있습니다!이것이 바로 우리가 인코딩에 열중하는 이유입니다. 저도 이 알고리즘에 대한python 실현을 여기서 공유할 것입니다.
Github repo
그 밖에 다음과 같은 분야에 대한 더 많은 지식을 공유하기 위해 연락을 취합니다.
또는:

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