[javascript] 허프만 압축 코드 huffman

서문 

이 포스팅은 지난번에 작성 하였다가 잠시 임시저장 하였던 포스팅 인데, 브라우저 쿠키와 캐시를 지우면서 동시에 날라가버렸다... 분명 임시저장을 몇번이나 클릭하고 저장한 것을 확인하였는데, 날라간 것을 보니 아무래도 브라우저의 로컬 스토리지같은 곳에 저장 하는 모양이다. 

 

허프만 코드란 ? 

허프만 코드는 스트링을 압축하는 알고리즘이다. 주로 팩스같은 것을 이용할 때 허프만 코드로 통신 시 전달되는 데이터를 줄이는 용도로 사용된다. 

 

압축 알고리즘은 물리적으로 스트링을 압축하는 방법과 비트를 줄이며 스트링을 압축하는 방법이 존재하는데, 허프만 코드는 후자의 방법을 선택한다. 또한 허프만 코드는 가변 길이 문자의 특성을 이용한다

 

물리적 압축과 비트 압축. 

압축 방법을 떠 올리면 우리가 널리 알고 있는 물리적으로 스트링을 압축하는 방법이 생각 날 것이다. 예를 들어 다음과 같은 문자열이 존재한다고 가정해보자 . ex : aaaabbbbcccdcdcdcdcdwe 

 

위의 스트링은 22개의 문자로 이루어져있는데 해당 문자를 물리적으로 압축해보자 . 

 

aaaa는 4a, bbbb는 4b,ccc는 3c ,dc는 4dc, d,w,e 로 압축하여 4a4b3c4dcdwe로 쉽게 압축 할 수 있을 것이다. 그러나 4dc의 경우 4d인지, 4dc인지 햇갈릴 가능성이 있기때문에 , 4a4v3c4dc/dwe형태로 나눠주어야 할 필요가 있을 것이다. 이와 같은 방법 처럼 문자열의 크기를 줄이는 것을 물리적 압축 방법이라고 한다. 

 

반면 비트스트링으로 압축하는 방법은 조금 다르다. abbc의 경우 결국에는 모든 character가 8bit로 이루어진 아스키 코드 값이기 때문에 결국 32bit를 소비하게 된다. 이때 허프만 코드는 이진트리의 특성을 사용하여 많이 사용하는 문자의 경우 8bit이내로 bit를 압축한다. 

 

가변 길이 문자 

우리는 특정한 비트 코드를 보며 어디서 부터 어디까지 끊어야 한 단어 인지 알 것이다. 그래서 보통 8bit로 되어 있거나 7bit의 non-ascii문자를 보더라도 특정 길이만큼 비트를 나누면 해당 코드를 해석 할 수가 있다 그러나 가변길이문자는 문자마다 bit의 길이가 다르다. 그렇기에  어디서 부터 어디까지가 문자인지 알 수가 어렵다. 허프만 코드는 이진트리라는 특성을 이용하여 이 문제를 해결하였고, 이는 허프만 코드 알고리즘으로 해당 문자열을 줄이는 과정을 볼 때 이해하기 더 쉬울 것이다. 

허프만 코드 압축하기

허프만 코드알고리즘을 배우며 중요한 key point는 이진트리를 이용하는 것과 자주 사용하는 문자들은 자주 사용하지 않은 문자보다 짧은 형태로 bit가 제공된다는 점이다. 

 

허프만 코드의 압축 과정은 다음과 같다. 

 

1. 압축하고자 하는 string의 character들을 빈도수와 해당 문자를 가진 노드를 만든다. 

ex : qqqqqfsssdddee 

 

노드 -> {char:'q' , frequency : 5},  {char:'f' , frequency : 1},  {char:'s' , frequency : 3},  {char:'d' , frequency : 3},  {char:'e' , frequency : 2}, 

 

2. 해당 노드들을 우선 순위큐에 집어 넣고 우선 순위는 가장 낮은 빈도수를 우선으로 한다. 

 

sorted queue -> {char:'f' , frequency : 1},{char:'e' , frequency : 2},  {char:'s' , frequency : 3},  {char:'d' , frequency : 3}, {char:'q' , frequency : 5},

(정렬은 보기 편함을 위해서 넣었습니다. 우선순위큐의 특성 상 정렬하지 않아도 빈도수에 따라서 먼저 나오게 됩니다. )

 

3.  해당 노드들에서 가장 낮은 빈도수를 가진 노드를 두개를 꺼내 새로운 노드의 자식 노드로 연결하며 새로운 노드는 두 자식의 빈도수를 합친 값을 가지게 된다. 이후 해당 노드를 다시 엔큐에 집어 넣게 된다. 

 

deque_1 = {char:'f' , frequency : 1}

deque_2 = {char:'e' , frequency : 2},

 

newNode = new Node();

newNode.left = deque_2;

newNode.right = deque_1;

newNode.freqeuncy = deque_1.frequency  + deque_1.frequency;

 

priorityQueue.enque = newNode;

 

4. 3의 방법을 해당 큐의 엘리먼트가 1개가 될때 까지 반복 한다. 

 

위의 방법 까지 진행 되었다면 다음과 같은 트리가 최종적으로 만들어지게 될 것이다. 

 

여기서 특이점이라고 하면 char가 들어있는 노드들은 모두 leaf 노드로 자식 노드가 없는 노드들이다. 위의 이진트리의 특성을 이용하여, 왼쪽으로 가면 0 오른쪽으로 가면 1이라는 코드를 부여하여 각 문자에 새로운 비트 값을 줄 수 있다. 이 특성으로 인하여 가변 길이 문자로 변환되는 허프만 코드는 문자의 비트길이가 변해도 다시 문자로 변환 할 수 있다. 

 

ex -> q = 00, d = 010, s = 0111, f = 01100, e = 01101 

 

이로 인하여 허프만 코드로 변환된 bit의 수는 다음과 같다.  q의 빈도수 * 2bit , d 의 빈도수 * 3bit, s 의 빈도수 * 4bit, f의 빈도수 * 5bit, e의 빈도수 * 5bit 를 다 더한 값은 10 + 9 + 12 + 5 + 10 으로 46으로 기존 14* 8 bit였던 112bit보다 50% 이상 줄이는 모습을 볼 수 있다. 

 

단점 

허프만 코드의 단점은 사용하는 문자의 수가 다양해지고, 문자간 빈도수가 크게 차이 나지 않으면 8bit의 고정 길이 문자보다 훨 씬 많은 비트수를 가지게 된다. 

 

전체 코드

const string = "aasdasdasdasdasaskfmlkopoiulkwletjd";

class PriorityQueueForHuffman {
    constructor(sortedList) {
        const queue = {
            count: 0,
            root: null,
        };

        this.getLength = () => {
            return queue.count;
        }

        this.enque = (obj) => {
            if (queue.root === null) {
                obj.link = null;
                queue.root = obj;
            } else {
                let link = queue.root;
                while (link.link !== null && obj.frequency > link.frequency) {
                    link = link.link;
                }
                obj.link = link.link;
                link.link = obj;
            }
            queue.count++;
            return true;
        }

        this.deque = () => {
            const biggestFrequencyNode = queue.root;
            if (biggestFrequencyNode === null) {
                return null;
            } else {
                queue.root = queue.root.link;
                queue.count--;
                return biggestFrequencyNode;
            }
        }

        const init = () => {
            for (let i = 0; i < sortedList.length; i++) {
                this.enque(sortedList[i]);
            }
        }
        init();



    }
}

function calculateFrequency(string) {

    //각 스트링에 맞게 2진 트리를 맞춰야함  
    //각 빈도수를 계산 해야 한다. 
    const nodeObj = {};
    const nodeList = [];
    for (let i = 0; i < string.length; i++) {
        if (nodeObj[string[i]] === undefined) {
            nodeObj[string[i]] = {
                char: string[i],
                frequency: 1,
                left: null,
                right: null
            }
            nodeList.push(nodeObj[string[i]])
        } else {
            nodeObj[string[i]].frequency++
        }
    }

    return nodeList;
}
function makeHuffmanTree(queue) {

    while (queue.getLength() >= 2) {
        const node_1 = queue.deque();
        const node_2 = queue.deque();

        const node = {
            frequency: node_1.frequency + node_2.frequency,
            left: node_1,
            right: node_2,
        }
        queue.enque(node);
    }

    return queue.deque();
}




function huffmasnCodding(string) {

    const sortedNodelist = calculateFrequency(string).sort((a, b) => {
        return a.frequency - b.frequency;
    })

    const queue = new PriorityQueueForHuffman(sortedNodelist);
    const tree = makeHuffmanTree(queue);

    let incodedstring = "";
    const map = {};
    for (let i = 0; i < string.length; i++) {
        if (map[string[i]]) {
            incodedstring += map[string[i]];
        } else {
            map[string[i]] = incoding(string[i], tree);
            incodedstring += map[string[i]];
        }
    }


    return {
        code : incodedstring,
        tree : tree
    }
}

function incoding(char, node) {
    return find(char, node, "", "0");
}

function find(char, node, code, number) {
    if (node === null) {
        return null
    } else if (node.char === char) {
        return code + number;
    } else {
        return find(char, node.left, code + number, "0") || find(char, node.right, code + number, "1");
    }
}


function decoding(codeOBJ){
    
    let decodedString = "";
    let dummyNode = null;
    for(let i = 0; i < codeOBJ.code.length; i++){
        if(codeOBJ.code[i] === "0"){
            if(dummyNode === null){
                dummyNode = codeOBJ.tree;
            }else if(dummyNode.left !== null){
                dummyNode = dummyNode.left;
            }
            
            if(i <= codeOBJ.code.length){
                if(codeOBJ.code[i+1] === "0" && dummyNode.left === null){
                    decodedString += dummyNode.char;
                    dummyNode = null;
                }else if(codeOBJ.code[i+1] === "1" && dummyNode.right === null){
                    decodedString += dummyNode.char;
                    dummyNode = null;
                }
            }
        }else{
            if(dummyNode.right !== null){
                dummyNode = dummyNode.right;
            }

            if(i <= codeOBJ.code.length){
                if(codeOBJ.code[i+1] === "0" && dummyNode.left === null){
                    decodedString += dummyNode.char;
                    dummyNode = null;
                }else if(codeOBJ.code[i+1] === "1" && dummyNode.right === null){
                    decodedString += dummyNode.char;
                    dummyNode = null;
                }
            }
        }
        if(i === codeOBJ.code.length-1){
            decodedString += dummyNode.char;
        }
    }
    console.log(`string : ${string}`)
    console.log(`string bit : ${string.length * 8}`);
    console.log(`Incoded string : ${codeOBJ.code}`)
    console.log(`Incoded code bit : ${codeOBJ.code.length}`);
    console.log(`decodedString : ${decodedString}`)
}

const incodedCode = huffmasnCodding(string);
decoding(incodedCode)

 

해당 코드는 디코딩과 인코딩이 존재하며 시간 복잡도는 다음과 같다.

 

인코딩 시 O(n) 디코딩 시 시간 복잡도는 O(n)