그리디 알고리즘 - A009_HuffmanCode

허프만 압축 문제 

메모리 공간을 효율적으로 사용할 수있고, 파일 전송 시간을 단축시키기 위해 주어진 파일의 크기를 줄이는 방법을 파일 압축(file compression)이라고 한다.

그렇다면  허프만(Huffman) 압축이란? 파일에 빈번히 나타는 문자에는 짧은 이진 코드를 할당, 드물게 나타나는 문자에는 긴 이진 코드를 할당한다. 

허프만 압축을 사용한 문자 코드들은 접두부 특성(Prefix Property)이 존재한다.  

-> 접두부 특성 : 각 문자에 할당된 이진 코드는 다른 문자에 할당된 이진 코드의 접두부가 되지 않는다. 코드 사이를 구분할 특별한 코드가 필요 없다. 

              ex) 문자 'a' -> 코드 '101' 이라면 다른 모든 문자의 코드는 '101'로 시작 안 함, 또한 '1','10'으로도 시작 안 함 

허프만 압축은 입력 파일에 대한 문자의 출현 빈도수에 기반을 둔 이진트리 생성 후 각 문자에 이진 코드(허프만 코드) 할당

---

알고리즘 

HuffmanCoding
입력: 입력 파일의 n개의 문자에 대한 각각의 빈도수
출력: 허프만 트리
각 문자에 대해 노드를 만들고, 그 문자의 빈도수를 노드에 저장한다.
n개의 노드들의 빈도수에 대해 우선순위 큐 Q를 만든다.
while (Q에 있는 노드 수 >=2) {
  빈도수가 가장 작은 2개의 노드(A와 B)를 Q에서 제거한다.
  새 노드 N을 만들고, A와 B를 N의 자식 노드로 만든다.
  노드 N을 Q에 삽입한다.
}
return Q	// 허프만 트리의 루트를 리턴하는 것이다.

EX)

입력 파일은 4개의 문자로 되어 있고, 각 문자의 빈도수는 다음과 같다.

A: 450 T: 90 G:120 C:270

• Line 5 : 4개의 문자들의 빈도수에 대해 우선순위 Q를 만든다.
• Line 6 : while-루프 조건이 ‘참’이므로, Line 7~10을 수행한다. 즉, Q에서 ‘T’와 ‘G’를 제거한 후, 새 부모 노드를 Q에 삽입한다.
• Line 6 : while-루프 조건 ‘참’, Line 7~10을 수행. 즉, Q에서 ‘T’와 ‘G’의 ‘부모 노드’와 ‘C’를 제거한 후, 새 부모 노드를 Q에 삽입한다.
• Line 6 : while-루프 조건 ‘참’, Line 7~10을 수행. 즉, Q에서 ‘c’의 ‘부모 노드’와 ‘A’를 제거한 후, 새 부모 노드를 Q에 삽입한다.
• Line 6 : while-루프 조건 ‘거짓’, Line 11에서 Q에 있는 노드를 리턴. 즉, 허프만 트리의 루트가 리턴된다.

 

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace HuffmanCode
{
    class HuffmanTree
    {
        private List<Node> nodes = new List<Node>();
        public Node Root { get; set; }
        public Dictionary<char, int> Frequencies = new Dictionary<char, int>();

        public void Build(string source)
        {
            for (int i = 0; i < source.Length; i++)
            {
                if (!Frequencies.ContainsKey(source[i]))
                {
                    Frequencies.Add(source[i], 0);
                }

                Frequencies[source[i]]++;
            }

            foreach (KeyValuePair<char, int> symbol in Frequencies)
            {
                nodes.Add(new Node() { Symbol = symbol.Key, Frequency = symbol.Value });
            }

            while (nodes.Count > 1)
            {
                List<Node> orderedNodes = nodes.OrderBy(node => node.Frequency).ToList<Node>();

                if (orderedNodes.Count >= 2)
                {
                    // Take first two items
                    List<Node> taken = orderedNodes.Take(2).ToList<Node>();

                    // Create a parent node by combining the frequencies
                    Node parent = new Node()
                    {
                        Symbol = '*',
                        Frequency = taken[0].Frequency + taken[1].Frequency,
                        Left = taken[0],
                        Right = taken[1]
                    };

                    nodes.Remove(taken[0]);
                    nodes.Remove(taken[1]);
                    nodes.Add(parent);
                }

                this.Root = nodes.FirstOrDefault();
            }
        }

        public BitArray Encode(string source)
        {
            List<bool> encodedSource = new List<bool>();

            for (int i = 0; i < source.Length; i++)
            {
                List<bool> encodedSymbol = this.Root.Traverse(source[i], new List<bool>());
                encodedSource.AddRange(encodedSymbol);
            }

            BitArray bits = new BitArray(encodedSource.ToArray());

            return bits;
        }

        public string Decode(BitArray bits)
        {
            Node current = this.Root;
            string decoded = "";

            foreach (bool bit in bits)
            {
                if (bit)
                {
                    if (current.Right != null)
                    {
                        current = current.Right;
                    }
                }
                else
                {
                    if (current.Left != null)
                    {
                        current = current.Left;
                    }
                }

                if (IsLeaf(current))
                {
                    decoded += current.Symbol;
                    current = this.Root;
                }
            }

            return decoded;
        }

        public bool IsLeaf(Node node)
        {
            return (node.Left == null && node.Right == null);
        }
    }
}

 

 

 if (orderedNodes.Count >= 2)
                {
                    // Take first two items
                    List<Node> taken = orderedNodes.Take(2).ToList<Node>();

                    // Create a parent node by combining the frequencies
                    Node parent = new Node()
                    {
                        Symbol = '*',
                        Frequency = taken[0].Frequency + taken[1].Frequency,
                        Left = taken[0],
                        Right = taken[1]
                    };

                    nodes.Remove(taken[0]);
                    nodes.Remove(taken[1]);
                    nodes.Add(parent);
                }

---

시간 복잡도 

n개의 노드생성 : O(n)

우선순위 큐 Q 생성 : O(n)

->힙 자료 구조 사용 

노드 2개를 Q에서 제거, 새 노드를 Q에 삽입 : O(logn)

while-루프는 (n-1)번 반복 : (n-1)*O(logn) = O(nlogn)

트리의 루트를 리턴 : O(1)

HuffmanCoding 알고리즘의 시간 복잡도  : O(n)+O(n)+O(nlogn)+ O(1) = O(nlogn)

---

사용도

팩스나 대용량 데이터 저장, 멀티미디어, mp3 등에 활요할 수 있다.

정보 이론 분양에서 엔트로피를 계산하는데 활용하기도 한다. 이는 자료의 불특정성을 분석하고 예측하는데 이용된다.