[c#] 간단한 유틸을 만들어보자! - [DIY 압축기] 편

해당 포스팅은 C#을 이용하여 간단한 유틸리티 프로그램을 개발하면서, 그 안에 쓰이는 라이브러리나 알고리즘(로직) 등을 다뤄보고 학습하는 포스팅입니다. 이 글을 통해 기존에 있던 프로그램과 비교하면서 해당 프로그램의 쓰임새, 동작 방식 등을 분석하거나 조금은 다른 관점으로 접근하여 생각해 보는것이 이 글과 앞으로 있을 포스팅의 목표입니다.

---

# 개요

이번 유틸리티 프로그램은 파일의 용량을 줄여 저장 공간의 활용성을 높여주는 일명 [압축기]입니다. 오늘날 인터넷의 발전으로 데이터 통신의 대한 효율을 높이는 노력이 많아져, 그림이나 동영상 데이터를 보다 적은 용량으로 최대한 원본에 가깝게 압축하는 작업이 활발히 이루어지고 있습니다. 압축 파일로 알려진 .zip, .rar, .7z 뿐만 아니라 미디어 데이터로 흔히 접하는 .jpg, .gif, .avi, .mp3, .mp4 등등 역시, 인코딩과 압축과정을 거친 일종의 압축 파일입니다. 전자의 .zip과 같은 파일은 압축을 풀었을때 원본의 데이터를 그대로 복원할 수 있는 무손실 압축기법을 사용하며, 후자의 미디어 데이터들은 사람의 시각과 청각이 인지하지 못하거나 구분이 어려운 부분을 제거해 원본과 크게 다르지 않지만 용량을 크게 줄일 수 있는 손실 압축기법을 사용합니다. 

이번에 다룰 데이터 압축기법은 무손실 압축기법에 대한 몇몇 알고리즘을 다뤄보고 직접 적용할 예정입니다.

무손실 압축기법이 사용된 대표적인 zip 파일은 국내에서는 "집"이라는 발음을 본떠서 "알집", "빵집"...... 등 등의 여러 압축 프로그램을 통해 사용되고 있습니다. 이들 대부분이 개인에게 프리웨어로 제공하거나 오픈소스로 공개한 덕분에 많은 사람들이 압축 프로그램에 쉽게 접근 할 수 있었고, 오늘날의 압축 프로그램은 단순한 압축 기능에 끝나지 않고 다양한 압축기능(여러 압축 확장자, 분할 기능, 빠른 압축 등 등)과 편의 기능을 제공하고 있어 사용자가 사용하는데 있어서 크게 도움을 주고 있습니다.

알집을 이용하여 파일을 압축하는 모습

무손실 압축기법은 중복되는 데이터값을 최대한 짧게 치환하여 데이터를 줄이는것이 핵심입니다. 이러한 핵심을 관통하는 압축 기법들 중에 대표적인 기법이 Run-Length 압축(RLE)과 허프만 압축 알고리즘입니다. 

먼저 Run-Length 압축은 중복된 데이터값을 표시하고 몇개가 중복되었는지 표시하기 때문에 같은 데이터값이 연속적으로 존재하는 파일을 효과적으로 압축할 수 있는 알고리즘입니다. 예를 들어 다음과 같은 데이터들이 순서대로 저장되어 있다고 가정하고 기법을 적용해보겠습니다.

원본 : AAAAAAAAAEEEEGSDHTTTTTTTT

과정 1 : 첫번째로 A가 연속적으로 9개 있으므로, "AAAAAAAAA"를 "A9"로 대체

과정 2 : 그 다음 E가 연속적으로 4개 있으므로, "E4"로 대체

과정 3 : 이어서 GSDH는 중복되어 있지 않지만, [데이터 값, 갯수]로 표기되는 알고리즘 규칙상 "G1S1D1H1"로 대체

과정 4 : 마지막으로 T가 연속적으로 8개 있으므로, "T8"로 대체

결과 : A9E4G1S1D1H1T8

이렇게 27바이트(한 문자당 1바이트로 계산)였던 파일이 14바이트로 압축됩니다. 하지만 이 방법만으로는 값들이 연속되지 않는 경우엔 오히려 파일 크기가 늘어나는 현상이 발생합니다. 이를 개선하기 위해 값이 연속될때만 위의 알고리즘을 적용하고, 원본데이터와 구분하기 위해 특수 문자를 앞에 추가하는 규칙을 추가합니다. 즉, 연속적으로 있는 데이터값들은 [특수문자, 데이터 값, 갯수]으로 표기됩니다. 이를 적용하여 위의 원본을 다시 압축하면 ~A9~E4GSDH~T8로 표현할 수 있게되고, 13바이트로 압축됩니다.

다음으로 허프만 압축 알고리즘은, 전체 데이터값의 빈도수를 계산하여 빈도수가 많은 값을 짧은 길이로 표현하고 반대로 빈도수가 적은 값은 길게 표현하는 기법입니다. 치환되는 문자가 바이트(Byte) 단위가 아닌 010, 00, 011 등 등의 비트(bit) 단위로 치환되기 때문에 용량을 매우 크게 줄일 수 있지만, 단순히 빈도수가 많은 글자는 짧게, 빈도수가 적은 글자에는 길게 치환하는 방식으로 치환하게 되면 원본으로 바꿀때 변환이 모호해질 수 있어, 허프만 압축 알고리즘은 이진 트리를 사용합니다.

압축할 때 빈도수 순으로 이진 트리를 구성하고, 배치된 트리에 따라 비트를 할당합니다. 그 후 원본으로 변환할 때 헤더에 같이 저장했던 이진 트리를 참고하여 원본 데이터로 되돌립니다. 예시로 TTTHACJJTTTQJDDAQJJTDDTTT 데이터를 허프만 압축 알고리즘으로 압축 해보도록 하겠습니다.

우선 각 문자에 대한 빈도수를 구한 뒤, 빈도수를 기준으로 정렬한 뒤 두개씩 짝지어 트리를 형성합니다.

이 후 합한 빈도수를 기준으로 재정렬한 뒤, 또 다시 두 개씩 짝지어 줍니다.

위의 과정을 반복하면 아래와 같은 이진 트리가 완성됩니다.

허프만 알고리즘을 적용하여 허프만 트리를 구축한 모습

위의 트리를 참고하여 C에 할당되는 비트는 000이 됩니다. 반면 T에 할당되는 비트는 11이 됩니다. 비트 문자로 치환한 다음 바이트 단위로 다시 묶어서 표현하면 다음과 같습니다.

11111100

10100001

01101111

11101110

11001000

10011101

10111100

10011111

10000000

이진 트리를 구성하는 헤더 부분을 제외한다면 총 9바이트로 변환 가능해집니다.

이제 허프만 트리 알고리즘을 적용하여 [DIY 압축기]를 구현해보도록 하겠습니다.

---

# [DIY 압축기] 기능

허프만 알고리즘에 대한 코드는 「속전속결 알고리즘 입문」((주)영진닷컴) 이라는 책에서 데이터 크기를 줄이는 압축 알고리즘 페이지를 참고하였습니다. 책은 C언어를 기준으로 코드가 작성되어 있어서 C# 구문으로 변경하여 코드를 작성하였습니다.

[허프만 노드 클래스]

    public class HuffmanNode
    {
        public byte mValue;
        public int mFreq;
        public HuffmanNode mRight;
        public HuffmanNode mLeft;

        public HuffmanNode()
        {
            mValue = 0;
            mFreq = 0;
            mRight = null;
            mLeft = null;
        }

        public void DeleteNode()
        {
            mValue = 0;
            mFreq = 0;
            mRight = null;
            mLeft = null;
        }
    }

    public partial class Form1 : Form
    {
        ......
        ......
        ......
        private void DeleteHuffTree()
        {
            Stack>HuffmanNode< nodes = new Stack>HuffmanNode<();
            nodes.Push(headNode);

            while (nodes.Count > 0)
            {
                HuffmanNode i = nodes.Pop();

                if (i.mRight !=  null)
                    nodes.Push(i.mRight);

                if (i.mLeft != null)
                    nodes.Push(i.mLeft);

                i.DeleteNode();
            }

            for (int i = 0; i < 256; i++)
            {
                huffList[i] = null;
                freq[i] = 0;
                huffCode[i] = 0;
                huffLength[i] = 0;
            }

            cmpByte = 0;
            cmpBit = 7;

            extByte = 0;
            extBit = -1;
        }
        ......
        ......
        ......
    }

허프만 트리 구성을 위해 HuffmanNode 클래스를 선언하여 사용합니다. 클래스의 멤버 변수로는 데이터 값과 빈도수, 그리고 왼쪽 자식 노드와 오른쪽 자식 노드를 가지고 있습니다. 빈도수 값은 압축 할 때 파일 헤더 부분에 허프만 코드를 형성할 수 있도록 허프만 트리를 구축하는데 사용됩니다. 압축 해제 시에는 이미 파일 헤더 부분에 허프만 코드가 저장되어 있기 때문에 따로 사용하지는 않습니다. 

[압축]

        private void button2_Click(object sender, EventArgs e)
        {
            SaveFileDialog fd = new SaveFileDialog();
            fd.FileName = fileName;
            fd.DefaultExt = "cmp";

            if (fd.ShowDialog() == DialogResult.OK)
            {
                fsout = new FileStream(fd.FileName, FileMode.Create);
                fsout.Seek(0, SeekOrigin.Begin);
                Compress();

                DeleteHuffTree();    // 압축이 완료된 후 모든 인스턴스를 제거하고 변수들을 초기화 함.

                fsin.Dispose();
                fsout.Dispose();

                fsin.Close();
                fsout.Close();
            }
        }

        private void Calcfrequency()    // 파일 데이터값의 빈도수를 체크함.
        {
            do
            {
                int value = fsin.ReadByte();
                freq[value]++;
            }
            while (fsin.Position < fsin.Length);


            fsin.Seek(0, SeekOrigin.Begin);
        }

        private int FindMinFrequency(int index)
        {
            int minIndex = 0;

            for (int i = 0; i < index; i++)
            {
                if (huffList[i].mFreq < huffList[minIndex].mFreq)
                    minIndex = i;
            }

            return minIndex;
        }

        public void MakeHuffmanTree()      // 빈도수를 기반으로 허프만 트리를 만듦.
        {
            nodeCount = 0;

            for (int i = 0; i < 256; i++)
            {
                if (freq[i] > 0)
                {
                    HuffmanNode node = new HuffmanNode();
                    node.mValue = (byte)i;
                    node.mFreq = freq[i];
                    node.mRight = null;
                    node.mLeft = null;

                    nodeCount++;

                    huffList[nodeCount - 1] = node;
                }
            }

            int head = nodeCount;

            while (head > 1)
            {
                int min = FindMinFrequency(head);
                HuffmanNode node1 = huffList[min];

                head--;
                huffList[min] = huffList[head];

                min = FindMinFrequency(head);
                HuffmanNode node2 = huffList[min];

                HuffmanNode node = new HuffmanNode();

                node.mValue = 0;
                node.mFreq = node1.mFreq + node2.mFreq;
                node.mLeft = node1;
                node.mRight = node2;

                huffList[min] = node;
            }

            headNode = huffList[0];
        }

        public void MakeCode(HuffmanNode node, uint code, int length)    // 형성된 허프만 트리 정보를 참고하여 허프만 코드를 만듦.
        {
            if (node.mLeft == null && node.mRight == null)
            {
                huffCode[node.mValue] = code;
                huffLength[node.mValue] = length;
            }
            else
            {
                code = code << 1;
                length++;
                MakeCode(node.mLeft, code, length);

                code = code | 1u;
                MakeCode(node.mRight, code, length);
                code = code >> 1;
                length--;
            }
        }

        public void WriteByteFromBit(uint code, bool flush)    // 허프만 코드의 비트들을 바이트 단위로 묶는 작업을 수행함. 
        {
            if (cmpBit < 0 || flush == true)
            {
                fsout.WriteByte((byte)cmpByte);
                cmpBit = 7;
                cmpByte = 0;
            }

            cmpByte = cmpByte | code << (cmpBit--);
        }

        public bool Compress()
        {
            Calcfrequency();

            MakeHuffmanTree();

            MakeCode(headNode, 0u, 0);

            for (int i = 0; i < 256; i++)    // 파일 앞부분에 허프만 코드에 대한 정보를 넣음.
            {
                fsout.WriteByte((byte)huffLength[i]);
                fsout.WriteByte((byte)huffCode[i]);
            }

            long fileSize = fsin.Length;
            byte[] result = new byte[8];

            for (int i = 7; i >= 0; i--)    
            {
                result[i] = (byte)(fileSize & 0xFF);
                fileSize >>= 8;
            }

            fsout.Write(result,0, result.Length);    // 원본 파일의 사이즈를 넣음.

            do        // 허프만 코드로 치환
            {
                int index = fsin.ReadByte();

                for (int i = huffLength[index] - 1; i >= 0; i--)
                {
                    uint bit = 0;
                    bit = (huffCode[index] >> i) & ~(~0 << 1);
                    WriteByteFromBit(bit, false);
                }
            }
            while (fsin.Position < fsin.Length);


            WriteByteFromBit(0, true);

            return true;
        }

압축이 시작되면 일단 파일의 모든 데이터 값을 체크하여 빈도수를 계산합니다. 그 이후 빈도수를 기준으로 허프만 트리를 형성합니다. 형성된 트리를 토대로 압축 해제에 필요한 데이터 값 각각의 허프만 코드를 출력 파일에 저장합니다. 예를 들면, "원본의 "95" 데이터값은 "0101"으로 치환할 것이므로 압축 해제시에 이를 참고 바람"과 같은 의미입니다. 각 값의 대한 허프만 코드 입력을 마치면, 원본 파일의 사이즈를 넣습니다. 이는 압축 해제를 좀 더 쉽고 간편하게 하기 위함입니다.

이렇게 헤더 부분이 완성되면 본격적인 치환 작업을 시작하고 완료되면, 변환 작업이 끝납니다.

[압축 해제]

        private void button3_Click(object sender, EventArgs e)
        {
            SaveFileDialog fd = new SaveFileDialog();
            fd.FileName = fileName;

            if (fd.ShowDialog() == DialogResult.OK)
            {
                fsout = new FileStream(fd.FileName, FileMode.Create);
                fsout.Seek(0, SeekOrigin.Begin);
                Extract();

                DeleteHuffTree();    // 압축 해제가 완료된 후 모든 인스턴스를 제거하고 변수들을 초기화 함.

                fsin.Dispose();
                fsout.Dispose();

                fsin.Close();
                fsout.Close();
            }
        }

        bool ReadBitFromFile(ref uint uBit)    // 읽은 파일의 값을 비트 단위로 읽어들임.
        {
            if (extBit < 0)
            {
                extByte = (uint)fsin.ReadByte();
                extBit = 7;
            }

            if (fsout.Position > oriFileSize)
                return false;

            uint bit = 0;
            bit = (extByte >> extBit) & ~(~0 << 1);
            extBit--;

            uBit = bit;

            return true;
        }

        void InsertIntoHuffTree(int value)    // 파일 앞 부분에 저장된 허프만 정보에 따라 허프만 트리를 구성함.
        {
            try
            {
                if (headNode == null)
                {
                    headNode = new HuffmanNode();
                }

                HuffmanNode curNode = headNode;

                int length = huffLength[value];
                uint code = huffCode[value];

                while (length > 0)
                {
                    uint bit = (code >> length - 1) & ~(~0 << 1);

                    if (bit == 0)
                    {
                        if (curNode.mLeft == null)
                        {
                            curNode.mLeft = new HuffmanNode();
                        }
                        curNode = curNode.mLeft;
                    }
                    else
                    {
                        if (curNode.mRight == null)
                        {
                            curNode.mRight = new HuffmanNode();
                        }
                        curNode = curNode.mRight;
                    }

                    length--;
                }

                curNode.mValue = (byte)value;    // length값이 끝났다는 것은 원본 데이터 값이 지정된 노드에 도달했다는 것을 의미함.
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.StackTrace + ", (" + ex.Message + ")");
            }
        }

        bool Extract()
        {
            fsin.Seek(0, SeekOrigin.Begin);

            for (int i = 0; i < 256; i++)
            {
                huffLength[i] = fsin.ReadByte();
                huffCode[i] = (byte)fsin.ReadByte();

                if (huffLength[i] > 0)
                    InsertIntoHuffTree(i);
            }

            oriFileSize = 0;

            for (int i = 0; i < 8; i++)    // 원본 파일의 크기를 읽어옴.
            {
                oriFileSize <<= 8;
                oriFileSize |= (long)(fsin.ReadByte() & 0xFF);
            }

            uint bit = 0;
            HuffmanNode node = headNode;

            ReadBitFromFile(ref bit);

            do
            {
                while (node.mLeft != null && node.mRight != null)
                {
                    if (bit == 0)
                        node = node.mLeft;
                    else
                        node = node.mRight;

                    ReadBitFromFile(ref bit);
                }

                fsout.WriteByte(node.mValue);
                node = headNode;
            }
            while (fsout.Position < oriFileSize);    // 원본 파일의 크기까지 쓰기를 완료했을때 while문을 종료함.

            return true;
        }

압축 해제는 저장된 헤더를 읽어들여 허프만 코드에 대한 정보를 변수에 저장하고, 이를 토대로 원본 데이터 값으로 다시 되돌리는 작업을 수행합니다. 압축 파일에 원본 파일의 크기값을 저장했으므로 변환 작업을 수행할 때는 원본 파일 크기 값만큼 while문을 반복하면 됩니다.

---

# 완성 및 마무리

- [DIY 탐색기] 소스 파일 : https://github.com/hyunil-stdlib/SimpleCompressor

(소스코드와 실행 파일을 받으실 수 있습니다.)

[DIY 압축기] 프로그램 구동 모습

파일 압축과 해제 전에는 반드시 파일 선택 버튼을 통해 파일을 선택해야 하고, 압축 해제는 .cmp 확장자의 파일만 정상적으로 압축 해제가 가능합니다. (그 이외의 파일에 대한 예외처리는 없음)

허프만 알고리즘을 적용하는 것만 중점적으로 구현하다보니 여러 파일을 대상으로 몇 가지 크고 작은 이슈가 있었습니다.

첫 번째로는 역시 헤더를 저장하기 때문에 파일 용량이 512Byte 보다 작은 파일에 대해서는 오히려 파일 크기가 더 늘어나는것을 확인할 수 있었습니다. 이런 현상은 상용화된 압축 프로그램 역시 나타나는 현상이긴 하지만, [DIY 압축기]와는 꽤 큰 차이의 압축 효과를 확인 할 수 있었습니다.

[DIY 압축기]는 156→578로 크게 늘어난 반면, 알집은 156→231로 약간 증가함

두번째로는 미디어 데이터, 즉 이미 손실 압축된 파일을 압축했을 때는 압축 효과를 전혀 볼 수 없었습니다. png 파일을 대상으로만 테스트하긴 했지만, 미디어 데이터 파일들은 대부분 이미 그 자체가 높은 압축률을 보이는 파일들이기 때문에 다른 압축 알고리즘을 적용하지 않는 이상은 크게 줄지는 않을것으로 보여집니다. 다른 상용화된 압축 프로그램들이 여러 압축 기능을 제공하는 이유도 바로 이런 상황이 있기 때문이지 않을까 추측합니다.

png 파일을 압축했을 때 미세하게 용량이 늘어남. 압축 효과 없음.

마지막으로 종종 압축 해제가 원본과 다르게 변환되었습니다. 특히 특정 프로그램에 쓰이는 데이터(예 : .ppt, .doc......)들은 원본 파일과는 완전 다른 파일로 복구되는 현상이 있었습니다. 좀 더 자세히 디버깅을 해보거나 자료를 찾아보면 알겠지만, 추측으로는 압축 과정 중 값이 의도한 값이 아닌 엉뚱한 값으로 저장되는 것이 아닌가 생각합니다. 이 현상은 [DIY 압축기]의 코드를 좀 더 수정작업이 필요한 현상으로 보여집니다.

원본 파일로 복원하지 못한 모습

마지막 이슈는 좀 더 코드를 살펴 보면서 수정하도록 하겠습니다. 수정이 완료되는대로 글을 수정하도록 하겠고, 이것으로 [DIY 압축기]에 대한 포스팅을 마치겠습니다. 다음에 올릴 포스팅도 기대해주시면 정말 감사하겠습니다.

# 참조

- 마이크로소프트 Developer Network (msdn)  : https://msdn.microsoft.com/ko-kr/library/618ayhy6.aspx

- 허프만 코딩 설명 영상 : https://youtu.be/jSOmfTx5lbs

- 김순근 · 웰기획(2005). 「속전속결 알고리즘 입문」. (주)영진닷컴. p365~396.