들어가며
소프트웨어가 처리해야 하는 데이터 양이 늘어날수록, 단순히 기능 구현만으로는 성능과 효율을 보장하기 어렵습니다. 특히 파일 저장이나 네트워크 전송 같은 영역에서는 적절한 압축 기법이 전체 시스템 효율에 큰 영향을 미치는데요.
“그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)” 스터디의 이번 미션에서는, 문서 압축에 널리 쓰이는 허프만 코딩(Huffman Coding)을 직접 구현해 보며, 왜 빈도 기반 트리 구조가 압축 효율을 높이는지 체감하고자 합니다.
허프만 코딩은 문자별 빈도 정보를 기반으로 가변 길이 이진 코드를 생성하여 평균 코드 길이를 최소화하는 무손실 압축 알고리즘입니다. 스터디 미션으로 “주어진 문자열에 대해 HuffmanCoding.compress(str) 호출 시 강의 예시와 같은 결과가 출력되도록 구현”하라는 지시가 있었습니다.
그러나 허프만 코딩은 동일 빈도 노드 병합 순서에 따라 여러 올바른 코드표가 나올 수 있으므로, “예시와 완벽한 일치”를 목표로 한다면 동률 빈도 처리(tie-breaker) 규칙을 명시해야 합니다.
스터디 목적에서는
- 허프만 코딩의 동작 원리를 올바르게 구현하고
- 예시 결과와 비교해 보며 이해를 심화하는 것이 핵심이라 보고, 아래와 같이 구현하고 설명합니다.
미션
목표
주어진 문자열에 대해 HuffmanCoding.compress(str)를 호출했을 때, [ [문자, 코드], … ] 형태의 배열을 출력하도록 허프만 코딩을 구현합니다.
지시문
여러분은 문서 압축 프로그램을 개발해야 합니다.
‘허프만 코딩’이라는 압축 알고리즘을 사용하여,
아래와 같은 결과가 나오도록 구현해보세요
(필요하다면 사용된 자료구조를 수정해도 좋습니다.)
JavaScript
const huffmanCoding = new HuffmanCoding();
const str =
"Lorem ipsum dolor sit amet consectetur adipiscing elit. " +
"Consectetur adipiscing elit quisque faucibus ex sapien vitae. " +
"Ex sapien vitae pellentesque sem placerat in id. " +
"Placerat in id cursus mi pretium tellus duis. " +
"Pretium tellus duis convallis tempus leo eu aenean.";
const result = huffmanCoding.compress(str);
console.log(result);
// 결과
[
[ 'i', '000' ], [ 'v', '001000' ],
[ 'q', '001001' ], [ 'd', '00101' ],
[ 'l', '0011' ], [ 'o', '01000' ],
[ 'b', '0100100' ], [ 'P', '0100101' ],
[ 'L', '01001100' ], [ 'E', '01001101' ],
[ 'C', '01001110' ], [ 'f', '01001111' ],
[ 'a', '0101' ], [ 'e', '011' ],
[ 'm', '10000' ], [ 'r', '10001' ],
[ 't', '1001' ], [ 'u', '1010' ],
[ 'x', '1011000' ], [ 'g', '1011001' ],
[ '.', '101101' ], [ 'p', '10111' ],
[ ' ', '110' ], [ 's', '1110' ],
[ 'c', '11110' ], [ 'n', '11111' ]
]구현 개요
- 빈도 계산
- 입력 문자열을 한 글자씩 순회하며 Map에 문자별 등장 횟수를 누적.
- 노드 객체 정의
- class Node { constructor(char, freq, left, right) } 형태로 구현.
- 리프 노드: 문자와 빈도, left, right는 null.
- 내부 노드: char=null, freq는 두 자식 빈도 합, left와 right는 합칠 두 노드.
- 트리 구성
- 모든 리프 노드를 배열에 모은 뒤, while (nodes.length > 1) 루프에서
- nodes.sort((a, b) => a.freq – b.freq)로 빈도 오름차순 정렬.
- 앞쪽 두 개를 꺼내 병합 노드 생성: new Node(null, a.freq + b.freq, a, b)를 다시 배열에 삽입.
- 이 과정을 반복해 최종적으로 하나의 root 노드를 얻음.
- 모든 리프 노드를 배열에 모은 뒤, while (nodes.length > 1) 루프에서
- 코드 생성
- root에서 재귀 탐색
- build(node, prefix) 내부 함수로 구현.
- node.char가 null이 아니면 리프이므로 codes[node.char] = prefix || “0” 할당.
- 빈 prefix일 때 “0”을 할당해 단일 문자 처리.
- 내부 노드면 build(node.left, prefix + “0”), build(node.right, prefix + “1”).
- 결과적으로 { 문자: 코드 } 형태 객체 codes가 완성됨.
- root에서 재귀 탐색
- 출력 형태
- Object.entries(codes)를 반환해 [ [char, code], … ] 배열로 변환.
코드
JavaScript
class Node {
constructor(char = null, freq = 0, left = null, right = null) {
this.char = char;
this.freq = freq;
this.left = left;
this.right = right;
}
}
class HuffmanCoding {
compress(str) {
if (!str) return [];
// 빈도 계산
const freqMap = new Map();
for (const ch of str) {
freqMap.set(ch, (freqMap.get(ch) || 0) + 1);
}
// 초기 노드 리스트 생성
const nodes = [];
for (const [ch, f] of freqMap.entries()) {
nodes.push(new Node(ch, f));
}
// 허프만 트리 구성
while (nodes.length > 1) {
nodes.sort((a, b) => a.freq - b.freq);
const a = nodes.shift();
const b = nodes.shift();
nodes.push(new Node(null, a.freq + b.freq, a, b));
}
const root = nodes[0];
// 코드 생성
const codes = {};
const build = (node, prefix) => {
if (node.char !== null) {
codes[node.char] = prefix || "0";
} else {
build(node.left, prefix + "0");
build(node.right, prefix + "1");
}
};
build(root, "");
// [문자, 코드] 쌍 배열 반환
return Object.entries(codes);
}
}
const huffmanCoding = new HuffmanCoding();
const str =
"Lorem ipsum dolor sit amet consectetur adipiscing elit. " +
"Consectetur adipiscing elit quisque faucibus ex sapien vitae. " +
"Ex sapien vitae pellentesque sem placerat in id. " +
"Placerat in id cursus mi pretium tellus duis. " +
"Pretium tellus duis convallis tempus leo eu aenean.";
const result = huffmanCoding.compress(str);
console.log(result);실행 결과
- 위 코드를 huffman.mjs로 저장한 뒤, 터미널에서 node huffman.mjs를 실행했습니다.
- 출력된 결과는 다음과 같습니다.
JavaScript
[
[ 'i', '000' ], [ 'q', '001000' ],
[ 'v', '001001' ], [ 'o', '00101' ],
[ 'l', '0011' ], [ 'd', '01000' ],
[ 'E', '0100100' ], [ 'g', '0100101' ],
[ 'x', '0100110' ], [ 'P', '0100111' ],
[ 'a', '0101' ], [ 'e', '011' ],
[ 'm', '10000' ], [ 'r', '10001' ],
[ 'u', '1001' ], [ 't', '1010' ],
[ 'p', '10110' ], [ 'L', '10111000' ],
[ 'C', '10111001' ], [ 'f', '10111010' ],
[ 'b', '10111011' ], [ '.', '101111' ],
[ ' ', '110' ], [ 's', '1110' ],
[ 'c', '11110' ], [ 'n', '11111' ]
]- 출력된 [문자, 코드] 쌍을 보면, 문자열에서 자주 등장한 문자는 비교적 짧은 비트열이, 드물게 등장한 문자는 긴 비트열이 할당된 것을 확인할 수 있습니다.
- 모든 서로 다른 문자가 코드표에 포함되어 있고, 코드들이 중복 없이 잘 생성되었으므로 허프만 트리 탐색이 올바르게 동작했음을 알 수 있습니다.
느낀 점
- 허프만 코딩을 직접 구현해 보니, 흔히 듣던 ‘자주 나오는 글자는 짧게, 적게 나오는 글자는 길게’가 실제로 코드 병합 과정에서 나오는 걸 직접 확인할 수 있어 이해가 쉬웠습니다.
- 배열 정렬 방식으로 빠르게 구현해 보니 동작은 잘 되지만, 입력이 커지면 느려질 수 있겠구나 싶었습니다.
- 결과를 볼 때는 코드 길이가 빈도와 잘 맞는지, 모든 문자가 빠짐없이 들어갔는지, 코드끼리 겹치지 않는지 확인해 보니 안정적인 구현이 어떤 건지 알게 되었습니다.
마치며
허프만 코딩 구현 과정을 직접 해보며, 빈도 기반 코드 생성 원리를 체득할 수 있었습니다. 문자를 빈도에 따라 다르게 처리하는 알고리즘의 실질적 동작 방식을 확인하면서, 자료구조와 알고리즘 지식이 실제 코드에 어떻게 녹아드는지 깨달았습니다. 이번 경험을 바탕으로 앞으로도 새로운 아이디어를 시도하며 학습을 이어가고 싶습니다. 감사합니다!
