development-logo
소프트웨어가 처리해야 하는 데이터 양이 늘어날수록, 단순히 기능 구현만으로는 성능과 효율을 보장하기 어렵습니다. 특히 파일 저장이나 네트워크 전송 같은 영역에서는 적절한 압축 기법이 전체 시스템 효율에 큰 영향을 미치는데요.
“그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)” 스터디의 이번 미션에서는, 문서 압축에 널리 쓰이는 허프만 코딩(Huffman Coding)을 직접 구현해 보며, 왜 빈도 기반 트리 구조가 압축 효율을 높이는지 체감하고자 합니다.
허프만 코딩은 문자별 빈도 정보를 기반으로 가변 길이 이진 코드를 생성하여 평균 코드 길이를 최소화하는 무손실 압축 알고리즘입니다. 스터디 미션으로 “주어진 문자열에 대해 HuffmanCoding.compress(str) 호출 시 강의 예시와 같은 결과가 출력되도록 구현”하라는 지시가 있었습니다.
그러나 허프만 코딩은 동일 빈도 노드 병합 순서에 따라 여러 올바른 코드표가 나올 수 있으므로, “예시와 완벽한 일치”를 목표로 한다면 동률 빈도 처리(tie-breaker) 규칙을 명시해야 합니다.
스터디 목적에서는
주어진 문자열에 대해 HuffmanCoding.compress(str)를 호출했을 때, [ [문자, 코드], … ] 형태의 배열을 출력하도록 허프만 코딩을 구현합니다.
여러분은 문서 압축 프로그램을 개발해야 합니다.
‘허프만 코딩’이라는 압축 알고리즘을 사용하여,
아래와 같은 결과가 나오도록 구현해보세요
(필요하다면 사용된 자료구조를 수정해도 좋습니다.)
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' ]
]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);[
[ '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' ]
]허프만 코딩 구현 과정을 직접 해보며, 빈도 기반 코드 생성 원리를 체득할 수 있었습니다. 문자를 빈도에 따라 다르게 처리하는 알고리즘의 실질적 동작 방식을 확인하면서, 자료구조와 알고리즘 지식이 실제 코드에 어떻게 녹아드는지 깨달았습니다. 이번 경험을 바탕으로 앞으로도 새로운 아이디어를 시도하며 학습을 이어가고 싶습니다. 감사합니다!
들어가며 소프트웨어를 구현할 때 성능 최적화나 안정성을 높이려면, 단순히 고수준 코드만 신경 쓰는 것을 넘어…
들어가며 소프트웨어가 복잡해질수록, 단순히 알고리즘의 시간복잡도만으로는 모든 문제를 해결할 수 없습니다. 특히 운영체제 수준에서는 다중…
들어가며 복잡한 소프트웨어가 원활히 동작하려면 단순히 코드만 잘 짜는 것으로는 부족합니다. 트랜잭션 처리나 대규모 데이터…
들어가며 소프트웨어를 개발할 때 메모리 관리 방식은 프로그램의 안정성과 성능을 좌우하는 핵심 요소입니다. 특히 자바스크립트,…
들어가며 소프트웨어 개발자는 코드가 어떻게 실행되는지 정확히 이해해야 할 필요가 있습니다. 우리가 작성한 프로그램은 결국…
서론 현대 웹 애플리케이션 아키텍처에서 웹 서버(Web Server) 와 웹 애플리케이션 서버(WAS, Web Application Server)…