미션

여러분은 문서 압축 프로그램을 개발해야 합니다. '허프만 코딩'이라는 압축 알고리즘을 사용하여, 아래와 같은 결과가 나오도록 구현해보세요. (필요하다면 사용된 자료구조를 수정해도 좋습니다.)

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."
let 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 HuffmanNode {
    constructor(char = null, freq = 0) {
        this.char = char;
        this.freq = freq;
        this.left = null;
        this.right = null;
    }
}

class HuffmanCoding {
    constructor() {
        this.codes = {};
    }

    buildTree(frequency) {
        let heap = [];
        
        for (let char in frequency) {
            heap.push(new HuffmanNode(char, frequency[char]));
        }
        
        heap.sort((a, b) => a.freq - b.freq);
        
        while (heap.length > 1) {
            let node1 = heap.shift();
            let node2 = heap.shift();
            
            let merged = new HuffmanNode(null, node1.freq + node2.freq);
            merged.left = node1;
            merged.right = node2;
            
            heap.push(merged);
            heap.sort((a, b) => a.freq - b.freq);
        }
        
        return heap.length > 0 ? heap[0] : null;
    }

    buildCodes(root, currentCode = '') {
        if (root === null) {
            return;
        }

        if (root.char !== null) {
            this.codes[root.char] = currentCode;
            return;
        }

        this.buildCodes(root.left, currentCode + '0');
        this.buildCodes(root.right, currentCode + '1');
    }

    compress(text) {
        let frequency = {};
        for (let char of text) {
            frequency[char] = (frequency[char] || 0) + 1;
        }

        let root = this.buildTree(frequency);
        
        this.codes = {};
        this.buildCodes(root, '');

        let result = [];
        for (let char in this.codes) {
            result.push([char, this.codes[char]]);
        }
        
        return result.sort((a, b) => a[0].localeCompare(b[0]));
    }
}