기호가 나오는 확률을 바탕으로, 평균 부호 길이가 최소가 되는 접두 부호를 만드는 방법. 확률이 가장 작은 두 기호(또는 노드)를 묶어 하나로 만드는 조작을 반복하여 트리를 만들고, 각 분기에 0과 1을 할당하여 부호어로 한다. 자주 나오는 기호일수록 짧은 부호어가 된다. 1기호씩 부호화하는 접두 부호 중에서는 최적이며, 평균 부호 길이는 엔트로피 이상, 엔트로피 + 1비트 미만이 된다. ZIP이나 gzip의 Deflate, JPEG 등에서 다른 방식과 조합하여 쓰인다. 1952년에 허프만이 발표했다.
일본어 명칭: ハフマン符号
허프만 부호(Huffman Code)은(는) 정보 이론과 부호의 기초 등 1개 분야의 연습 문제 5개에 나와요.
분야: 정보 이론과 부호의 기초
예를 들어 확률 1/2, 1/4, 1/8, 1/8인 기호에서는 먼저 1/8끼리 묶어 1/4, 다음으로 그것과 1/4을 묶어 1/2, 마지막으로 나머지 1/2과 묶습니다. 루트에서 각 기호까지의 분기에 0과 1을 붙이면 부호어는 0, 10, 110, 111이 되고, 평균 부호 길이는 1.75비트로 엔트로피와 같아집니다. 확률이 모두 2의 거듭제곱분의 1일 때는 이처럼 평균 부호 길이가 엔트로피와 일치합니다.
0과 1을 붙이는 방법이나, 같은 확률 중 어느 쪽을 먼저 묶느냐에 따라 부호어는 바뀝니다. 예를 들어 확률 0.4, 0.2, 0.2, 0.1, 0.1에서는 부호 길이가 1, 2, 3, 4, 4도, 1, 3, 3, 3, 3도, 2, 2, 2, 3, 3도 될 수 있지만, 평균 부호 길이는 모두 2.2비트입니다. 그래서 시험 등에서는 부호어 자체보다 평균 부호 길이를 묻는 경우가 많습니다.
부호 길이는 정수 비트로 제한되므로, 확률이 1에 가까운 기호가 있는 정보원에서는 엔트로피와의 차이가 커집니다. 이진 기호를 하나씩 부호화하면 아무리 치우쳐 있어도 1기호에 1비트가 필요합니다. 기호를 묶어서 부호화하거나, 산술 부호처럼 정수 비트에 얽매이지 않는 방식을 사용하면 엔트로피에 가깝게 할 수 있습니다.
정답: A. 2.25비트
먼저 0.1과 0.15를 묶어 0.25, 다음으로 0.2와 0.25를 묶어 0.45, 남은 0.25와 0.3을 묶어 0.55, 마지막으로 0.45와 0.55를 묶습니다. 부호 길이는 A, B, C가 2비트, D와 E가 3비트가 되며, 평균 부호 길이는 (0.3 + 0.25 + 0.2) × 2 + (0.15 + 0.1) × 3 = 1.5 + 0.75 = 2.25비트입니다. 확률의 치우침이 작은 정보원에서는 1, 2, 3, 4, 4와 같은 계단식 부호 길이보다 길이가 고른 부호가 더 짧아집니다.
어느 기호에 어느 부호어를 할당했는지(부호표 또는 각 기호의 부호 길이)가 필요합니다. 그래서 압축한 데이터에는 부호표를 첨부하거나 미리 정한 표를 사용합니다. Deflate에서는 부호 길이만 보내고, 수신 측이 같은 규칙으로 부호어를 다시 만듭니다(캐노니컬 허프만 부호).
아니요. 기호가 나오는 확률에 치우침이 없으면 거의 줄어들지 않습니다. 예를 들어 256종류의 바이트가 모두 같은 확률로 나오는 데이터에서는 모든 부호어가 8비트가 되어, 부호표만큼 오히려 커집니다.
허프만 부호에서는 확률이 가장 작은 두 개를 묶는 조작을 반복합니다.
기호 A, B, C, D를 확률 0.4, 0.3, 0.2, 0.1로 서로 독립적으로 내는 정보원을 허프만 …허프만 부호에서는 0.1과 0.3을 묶어 0.4, 다음으로 0.4와 0.6을 묶으므로, 부호 길이는 A가 1, B와 C가 2비트입니다.
기호 A, B, C를 확률 0.6, 0.3, 0.1로 서로 독립적으로 내는 정보원이 있으며, 그 엔트로피는…ZIP이나 gzip의 Deflate 방식은 LZ77로 치환한 결과를 다시 허프만 부호로 부호화합니다.
ZIP이나 gzip 등에서 사용되는 LZ77 방식의 개념으로 올바른 것은?평균 부호 길이(Average Code Length) 정보 엔트로피(Information Entropy) 무손실 압축(Lossless Compression) 런 렝스 부호화(Run-Length Encoding) 상호 정보량(Mutual Information) 손실 압축(Lossy Compression) 순방향 오류 정정(FEC) 이진 대칭 채널(Binary Symmetric Channel) 접두 부호(Prefix Code) 정보량(Self-Information)