허프만 코딩(Huffman coding) 알고리즘을 이용하여 다음 19… | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 16년 1회차
허프만 코딩(Huffman coding) 알고리즘을 이용하여 다음 19개 문자로 구성된 문자열을 압축하였다. 압축된 문자열에 사용된 비트 수는?
| a | b | a | b | a | d | c | d | a | b | a | c | d | a | b | c | d | d | e |
1
39
2
42
3
44
4
46
해설
압축된 문자열은 42비트를 사용한다.
문자별 빈도는 a 6, d 5, b 4, c 3, e 1이다. 허프만 트리는 빈도가 가장 작은 두 노드를 반복해 합친다.
e(1) + c(3) → 4
4 + b(4) → 8
d(5) + a(6) → 11
8 + 11 → 19
코드 길이는 a·b·d 2비트, c·e 3비트이므로 6×2 + 5×2 + 4×2 + 3×3 + 1×3 = 42
- 39는 42보다 짧은데, 허프만 코드는 접두어 코드 중 총 비트 수가 최소이므로 이보다 짧은 접두어 코드는 만들 수 없다.
- 44는 42보다 길어 최적 코드인 허프만 코드의 결과가 될 수 없다.
- 46도 42보다 길어 허프만 코드의 결과가 될 수 없다.
오류나 개정된 내용이 보이면 알려주세요