허프만 부호(Huffman coding)
가장 드문 두 기호를 묶어 트리(tree)를 쌓아 올려, 자주 나오는 기호에 짧은 부호를 주는 접두 부호(어떤 부호어(codeword)도 다른 부호어의 앞부분이 되지 않는 부호). 기호의 확률(probability)을 알 때, 기호마다 부호어 하나를 정해 두고 이어 붙여도 되살릴 수 있는 부호 가운데 평균(mean) 길이가 가장 짧다.
글자를 0과 1로 적을 때 모든 글자에 같은 길이를 줄 필요는 없습니다. 새뮤얼 모스의 모스 부호(Morse code)가 영어에서 가장 흔한 E에 점 하나를 준 것처럼, 자주 나오는 글자에 짧은 부호를, 드문 글자에 긴 부호를 주면 전체가 짧아집니다. 다만 부호를 이어 붙인 비트열을 거꾸로 끊어 읽을 수 있어야 합니다. 가장 깔끔한 방법은 어떤 부호도 다른 부호의 앞부분이 되지 않게 하는 것(접두 부호, prefix code)입니다. 접두 부호는 잎(leaf)마다 글자를 단 이진 트리와 같습니다. 뿌리에서 왼쪽 가지는 0, 오른쪽 가지는 1로 읽으며 내려가다 잎에 닿으면 한 글자가 끝납니다. 글자 i가 나올 확률이
이 평균을 가장 작게 하는 트리를 만드는 법은 MIT 대학원생이던 데이비드 허프만이 1951년 수업의 기말 보고서로 찾아 1952년 논문으로 발표했습니다. 글자마다 나온 횟수를 무게로 한 작은 트리 하나씩에서 시작해, 가장 가벼운 두 트리를 한 뿌리 아래로 묶는 일을 한 그루가 남을 때까지 되풀이합니다. 글:
다 묶은 뒤의 부호는
왜 가장 좋을까요? 최적의 트리에서 가장 드문 두 글자는 가장 깊은 곳에 형제로 놓여 있다고 해도 됩니다. 더 드문 글자가 더 흔한 글자보다 얕은 곳에 있다면, 둘을 맞바꿔도 평균은 줄거나 그대로이기 때문입니다. 또 최적의 트리에는 자식이 하나뿐인 마디가 없으니(있다면 그 마디를 없애 부호를 줄일 수 있습니다), 가장 깊은 잎에는 늘 형제 잎이 있습니다. 그 두 글자를 무게가 합쳐진 한 글자로 보면 글자가 하나 적은 같은 문제가 남고, 수학적 귀납법(mathematical induction)으로 매번 가장 가벼운 둘을 묶는 것이 최적임이 따라 나옵니다. 매 순간 가장 좋아 보이는 선택을 하는 욕심쟁이 알고리즘(greedy algorithm)이 정확한 답을 주는 드문 예입니다. 가장 가벼운 둘을 꺼내는 데 우선순위 큐(priority queue)를 쓰면 글자가 k가지일 때
평균 길이는 엔트로피(entropy) H 밑으로 내려갈 수 없고(섀넌의 원천 부호화 정리(source coding theorem)), 허프만 부호는 언제나 H 이상 H+1 미만입니다. 부호 길이가 정수라서 생기는 이 1비트 미만의 손해는 '치우친 글'에서 잘 보입니다. a가 거의 전부라 엔트로피는 글자당 0.34비트쯤인데 부호는 글자당 1비트보다 짧아질 수 없습니다. 여러 글자를 묶어 한 기호로 부호화하거나, 글 전체를 수 하나로 적는 산술 부호화(arithmetic coding)를 쓰면 이 손해가 줄어듭니다. 또 허프만 부호는 글자의 빈도를 미리 알아야 합니다. 앞에 나온 문자열을 가리키는 렘펠–지브 압축(Lempel–Ziv compression)은 빈도를 몰라도 되고, zip과 PNG가 쓰는 DEFLATE는 렘펠–지브로 반복을 줄인 뒤 그 결과를 다시 허프만 부호로 적습니다. JPEG도 이산 코사인 변환(discrete cosine transform)으로 얻어 양자화(quantization)한 계수를 마지막에 허프만 부호로 줄입니다.
이어지는 곳. 고정 길이 부호는 k가지 글자에
이 개념이 나오는 긴 글
이 개념 위에 세워진 것
이 개념을 언급하는 페이지
- 해밍 거리
… 상대가 다릅니다. 오류 정정 부호가 일부러 여분을 더한다면, 거꾸로 여분을 덜어 내 길이를 줄이는 쪽은허프만 부호같은 압축입니다. 길이가 다른 문자열까지 비교하려면 글자를 넣고 빼는 것도 허용하는 편집 거리로 …
- 지프의 법칙
… 만큼 글자나 낱말 하나가 주는 정보 엔트로피는 균등할 때보다 작고, 흔한 낱말에 짧은 부호를 주는허프만 부호같은 방법으로 글을 압축할 수 있습니다. 낱말을 벡터로 바꾸는 단어 임베딩을 학습할 때는 the, a …
- 정보 엔트로피
… \log_2 6 \approx 2.585 )입니다. 흔한 글자에 짧은 부호를, 드문 글자에 긴 부호를 주는허프만 부호(1952년 데이비드 허프만)로 적으면 한 글자에 평균 비트가 듭니다. 섀넌의 원천 부호화 정리에 …
- 욕심쟁이 알고리즘
… 만들지 않는 한 가장 짧은 변부터 고르는 크러스컬의 최소 신장 트리, 가장 드문 두 기호부터 묶는허프만 부호, 가장 가까운 점부터 확정하는 다익스트라 알고리즘(에츠허르 데이크스트라)의 최단 경로입니다. …
- 힙과 우선순위 큐
… 로버트 프림이 발표한 최소 신장 트리 알고리즘도 지금 트리에 가장 가까운 점을 힙에서 꺼냅니다.허프만 부호는 가장 드문 두 기호를 힙에서 꺼내 묶은 뒤 다시 넣기를 되풀이하는 욕심쟁이 알고리즘입니다. 최대 …
- 트리
… 가지는 1로 적으면 부호가 정해집니다. 기호의 빈도에 맞춰 평균 길이가 가장 짧도록 이런 트리를 만든 것이허프만 부호입니다. 비교 정렬이 할 수 있는 모든 비교를 가지로 펼친 결정 트리는 비교 정렬의 하한을 증명하는 …
- 원천 부호화 정리
… 손해가 1/n 밑으로 줄어듭니다. 앞면 확률이 인 동전의 엔트로피는 비트입니다. 던진 결과를 번씩 묶어허프만 부호로 적으면 한 번 던질 때마다 가 듭니다. 묶음 크기 n을 1부터 늘려 가며 노란 점이 어디로 가는지 …
- 렘펠–지브 압축
… 때마다 이미 풀어 놓은 부분에서 그대로 베껴 오면 됩니다. 글자마다의 확률표가 전혀 필요 없다는 점이허프만 부호와 다릅니다. 글: . 세 글자 이상 겹칠 때만 참조로 바꿉니다. 흰 글자는 그대로 적은 글자, 청록 …
- 오류 정정 부호
… 공을 겹치지 않게 많이 넣을수록 부호어가 많아져 전송률이 올라가기 때문입니다. 압축(원천 부호화 정리,허프만 부호)은 쓸모없는 여분을 없애고, 오류 정정 부호는 쓸모 있는 여분을 규칙적으로 되돌려 놓습니다. 실제 통신은 …
- 이산 코사인 변환
… 둔하기 때문입니다. 그러면 0이 된 계수가 많아지고, 이것을 지그재그로 읽어 0의 길이와 나머지 값을허프만 부호로 적습니다. 너무 세게 줄이면 덩어리 경계가 보이는 격자 무늬가 생깁니다. MP3와 AAC는 소리를 …
- 결합 엔트로피와 조건부 엔트로피
… 이 조건부 구조를 그대로 씁니다. 질문 하나로 후보를 절반으로 줄이는 이진 탐색은 스무고개 그대로이고,허프만 부호의 나무는 갈림길 하나하나가 예/아니오 질문 하나인 스무고개 전략표로, 평균 질문 수를 가장 적게 하는 …
- 쿨백–라이블러 발산
… 거의 정확히 -\log_2 q_i 비트가 들어서, 모형이 틀린 값이 그대로 D(p‖q)비트로 나타납니다.허프만 부호로 짠 표를 빈도가 다른 글에 쓸 때 손해를 보는 것도 같은 이치입니다. 언어 모델을 사람의 선호 쪽으로 …
- 산술 부호화
허프만 부호는 기호 하나마다 정수 개의 비트를 줍니다. 확률이 0.95인 기호의 이상적인 길이는 -\log_2 …
- 율–왜곡 이론
… 약 4.35 dB 모자랍니다. 대표값의 번호를 고정 길이로 적는 대신 흔한 칸의 번호에 짧은 부호를 주면(허프만 부호, 산술 부호화) 비트 수가 번호의 엔트로피 H(\hat X) 로 줄어듭니다. 이때는 오히려 촘촘한 …
- 결정 트리와 랜덤 포레스트
… n! 이상입니다. 스무고개로 물건 하나를 알아맞힐 때 평균 질문 수는 엔트로피보다 작을 수 없고,허프만 부호의 나무가 그 한계에서 1비트 안쪽까지 다가가는 가장 좋은 질문 순서를 줍니다. 다만 거기서는 질문을 …
- 토큰화와 BPE
… 2016년 리코 제니히 등이 기계 번역의 어휘를 만드는 데 가져왔습니다. 흔한 것을 짧게 적는다는 점에서허프만 부호와, 되풀이되는 문자열을 사전에 올린다는 점에서 렘펠–지브 압축과 같은 생각입니다. 다만 BPE는 매 …