허프만 알고리즘(Huffman Algorithm)

디지털 시대는 JPEG 이미지, MP3 오디오 파일, ZIP 아카이브 등 데이터 압축을 통해 발전합니다. 데이터 압축의 기본 알고리즘 중 하나는 허프만 알고리즘(Huffman Algorithm)입니다. 이 블로그 게시물에서는 Huffman 알고리즘을 이해하고 C#을 사용하여 작동하는 방식을 보여줍니다.

 

허프만 알고리즘이란 무엇입니까?

 

허프만 알고리즘은 창시자인 David Huffman의 이름을 따서 명명된 무손실 데이터 압축 방법입니다. 자주 사용되는 기호는 짧은 코드로, 자주 사용되지 않는 기호는 긴 코드로 인코딩하는 방식으로 작동합니다. 영어에서 가장 자주 사용되는 문자인 "e"가 긴 일련의 비트로 인코딩되고 "z"와 같이 거의 사용되지 않는 문자에는 짧은 코드가 제공된다고 상상해 보십시오. 그것은 비효율적입니다. 허프만의 방법은 그러한 비효율성을 해결하려고 합니다.

 

핵심 개념 이해

알고리즘은 이진 트리의 일종인 "허프만 트리"라는 데이터 구조를 사용합니다. 작동 방식은 다음과 같습니다.

 

1. 각 기호나 문자에 대한 노드를 생성하고 발생 빈도를 할당합니다.
2. 이러한 노드를 빈도에 따라 우선 순위 대기열에 배치합니다.
3. 대기열에 노드가 두 개 이상 있는 경우:
   주파수가 가장 낮은 두 개의 노드를 제거합니다.
   이 두 노드를 하위 노드로 사용하여 새 노드를 만듭니다. 이 새 노드의 빈도는 하위 노드 빈도의 합입니다.
   이 새 노드를 대기열에 다시 삽입합니다.
4. 대기열의 마지막 노드는 허프만 트리의 루트입니다.
5. 기호에 대한 허프만 코드는 트리 루트에서 해당 기호까지의 경로입니다. 여기서 왼쪽 자식으로의 이동은 '0'을 나타내고 오른쪽 자식으로의 이동은 '1'을 나타냅니다.

 

노드 클래스 정의

캐릭터, 빈도, 왼쪽 및 오른쪽 자식에 대한 속성을 갖는 기본 Node 클래스를 정의하는 것부터 시작하겠습니다.

public class Node
{
    public char Symbol { get; set; }
    public int Frequency { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }

    public Node(char symbol, int frequency)
    {
        Symbol = symbol;
        Frequency = frequency;
    }

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

 

허프만 트리 구축

단순화를 위해 List<Node>를 우선순위 대기열로 사용하겠습니다. 빈도가 가장 낮은 두 개의 노드를 반복적으로 찾아서 그로부터 새 노드를 만듭니다.

public static Node BuildHuffmanTree(List<Node> nodes)
{
    while (nodes.Count > 1)
    {
        nodes.Sort((x, y) => x.Frequency.CompareTo(y.Frequency));

        var left = nodes[0];
        var right = nodes[1];

        Node newNode = new Node('*', left.Frequency + right.Frequency)
        {
            Left = left,
            Right = right
        };

        nodes.Remove(left);
        nodes.Remove(right);
        nodes.Add(newNode);
    }
    
    return nodes[0];
}

 

허프만 코드 생성

이제 허프만 트리를 탐색하고 각 기호에 대한 코드를 생성하겠습니다.

public static void GenerateCodes(Node node, string code, Dictionary<char, string> codes)
{
    if (node.IsLeaf())
    {
        codes[node.Symbol] = code;
        return;
    }

    GenerateCodes(node.Left, code + "0", codes);
    GenerateCodes(node.Right, code + "1", codes);
}

 

테스트

Shape Of You라는 노래의 가사로 테스트를 진행

 

• 문자와 해당 빈도가 포함된 데이터세트 생성

string testString = "The club isn't the best place to find a lover So the bar is where I go Me and my friends at the table doing shots Drinking fast and then we talk slow Come over and start up a conversation with just me And trust me I'll give it a chance now Take my hand, stop, put Van the Man on the jukebox And then we start to dance, and now I'm singing like Girl, you know I want your love Your love was handmade for somebody like me I may be crazy, don't mind me Say, boy, let's not talk too much Grab on my waist and put that body on me Come on now, follow my lead Come, come on now, follow my lead I'm in love with the shape of you We push and pull like a magnet do Although my heart is falling too I'm in love with your body Last night you were in my room And now my bedsheets smell like you Every day discovering something brand new I'm in love with your body (Oh-I-oh-I-oh-I-oh-I) I'm in love with your body (Oh-I-oh-I-oh-I-oh-I) I'm in love with your body (Oh-I-oh-I-oh-I-oh-I) I'm in love with your body Every day discovering something brand new I'm in love with the shape of you One week in we let the story begin We're going out on our first date You and me are thrifty, so go all you can eat Fill up your bag and I fill up a plate We talk for hours and hours about the sweet and the sour And how your family is doing okay And leave and get in a taxi, then kiss in the backseat Tell the driver make the radio play, and I'm singing like Girl, you know I want your love Your love was handmade for somebody like me Come on now, follow my lead I may be crazy, don't mind me Say, boy, let's not talk too much Grab on my waist and put that body on me Come on now, follow my lead Come, come on now, follow my lead I'm in love with the shape of you We push and pull like a magnet do Although my heart is falling too I'm in love with your body Last night you were in my room And now my bedsheets smell like you Every day discovering something brand new I'm in love with your body (Oh-I-oh-I-oh-I-oh-I) I'm in love with your body (Oh-I-oh-I-oh-I-oh-I) I'm in love with your body (Oh-I-oh-I-oh-I-oh-I) I'm in love with your body Every day discovering something brand new I'm in love with the shape of you Come on, be my baby, come on Come on, be my baby, come on Come on, be my baby, come on Come on, be my baby, come on Come on, be my baby, come on Come on, be my baby, come on Come on, be my baby, come on Come on, be my baby, come on I'm in love with the shape of you We push and pull like a magnet do Although my heart is falling too I'm in love with your body Last night you were in my room And now my bedsheets smell like you Every day discovering something brand new I'm in love with your body Come on, be my baby, come on Come on (I'm in love with your body), be my baby, come on Come on, be my baby, come on Come on (I'm in love with your body), be my baby, come on Come on, be my baby, come on Come on (I'm in love with your body), be my baby, come on Every day discovering something brand new I'm in love with the shape of you";

Dictionary<char, int> frequencies = new Dictionary<char, int>();

foreach (char c in testString)
{
    if (!frequencies.ContainsKey(c))
    {
        frequencies[c] = 0;
    }
    frequencies[c]++;
}

List<Node> nodes = frequencies.Select(f => new Node(f.Key, f.Value)).ToList();

 

• 허프만 트리 구축

앞서 정의한 BuildHuffmanTree 함수를 사용하여 이제 허프만 트리를 구성할 수 있습니다.

Node root = Node.BuildHuffmanTree(nodes);

 

• 허프만 코드 생성 및 표시

Dictionary<char, string> huffmanCodes = new Dictionary<char, string>();
Node.GenerateCodes(root, "", huffmanCodes);

Console.WriteLine("Huffman Codes:");
foreach (var code in huffmanCodes)
{
    Console.WriteLine($"Character: {code.Key} Frequencies: {frequencies[code.Key]} Huffman Code: {code.Value}");
}

 

테스트 결과

Huffman Codes:
Character: o Frequencies: 274 Huffman Code: 000
Character: r Frequencies: 79 Huffman Code: 00100
Character: g Frequencies: 39 Huffman Code: 001010
Character: - Frequencies: 42 Huffman Code: 001011
Character: n Frequencies: 168 Huffman Code: 0011
Character:   Frequencies: 623 Huffman Code: 01
Character: b Frequencies: 85 Huffman Code: 10000
Character: d Frequencies: 87 Huffman Code: 10001
Character: v Frequencies: 43 Huffman Code: 100100
Character: p Frequencies: 22 Huffman Code: 1001010
Character: W Frequencies: 5 Huffman Code: 100101100
Character: E Frequencies: 6 Huffman Code: 100101101
Character: D Frequencies: 1 Huffman Code: 10010111000
Character: M Frequencies: 2 Huffman Code: 10010111001
Character: Y Frequencies: 3 Huffman Code: 1001011101
Character: L Frequencies: 3 Huffman Code: 1001011110
Character: T Frequencies: 3 Huffman Code: 1001011111
Character: f Frequencies: 24 Huffman Code: 1001100
Character: k Frequencies: 24 Huffman Code: 1001101
Character: , Frequencies: 49 Huffman Code: 100111
Character: l Frequencies: 99 Huffman Code: 10100
Character: h Frequencies: 111 Huffman Code: 10101
Character: e Frequencies: 224 Huffman Code: 1011
Character: I Frequencies: 54 Huffman Code: 110000
Character: ' Frequencies: 30 Huffman Code: 1100010
Character: S Frequencies: 3 Huffman Code: 1100011000
Character: G Frequencies: 4 Huffman Code: 1100011001
Character: O Frequencies: 7 Huffman Code: 110001101
Character: z Frequencies: 2 Huffman Code: 11000111000
Character: x Frequencies: 2 Huffman Code: 11000111001
Character: j Frequencies: 2 Huffman Code: 11000111010
Character: F Frequencies: 1 Huffman Code: 110001110110
Character: V Frequencies: 1 Huffman Code: 110001110111
Character: ( Frequencies: 9 Huffman Code: 110001111
Character: i Frequencies: 119 Huffman Code: 11001
Character: t Frequencies: 124 Huffman Code: 11010
Character: y Frequencies: 124 Huffman Code: 11011
Character: w Frequencies: 62 Huffman Code: 111000
Character: u Frequencies: 64 Huffman Code: 111001
Character: m Frequencies: 127 Huffman Code: 11101
Character: a Frequencies: 127 Huffman Code: 11110
Character: s Frequencies: 71 Huffman Code: 111110
Character: c Frequencies: 34 Huffman Code: 1111110
Character: ) Frequencies: 9 Huffman Code: 111111100
Character: A Frequencies: 10 Huffman Code: 111111101
Character: C Frequencies: 20 Huffman Code: 11111111

파일의 용량이 줄어들었다.

 

마무리

이제 Huffman 알고리즘과 C#에서의 구현을 명확하게 이해하게 되었습니다. 허프만 알고리즘은 많은 압축 방법의 초석이며 이를 이해하면 디지털 세계의 데이터 효율성에 대한 더 깊은 통찰력을 얻을 수 있습니다.

주요 목표는 자주 발생하는 기호를 더 짧은 코드로 인코딩하여 압축하는 것입니다. 더 복잡한 알고리즘에 대해 자세히 알아보고 싶거나 데이터 압축의 기본을 이해하고 싶다면 Huffman 알고리즘이 훌륭한 출발점이 될 것입니다!