KMS13 : C++(Hurffman code)을 이용한영문 txt 파일 압축기 (source)

KMS13 - English compression program

이번 포스팅에 쓰인 프로그램은 사실 KMS프로그램에 속하지 않는 놈이었습니다. 
국어 모의고사 지문에서 허프만 코드에 관한 설명이 나왔는데, 상당히 흥미롭더군요 (꼭 자기 분야가 아니면 흥미로움;;)

그래서 지문에 있던 내용을 기반으로 하여, 비효율적인 모든 부분들은 다 잘라내고 몇 가지 테크닉을 터 추가해서 코드를 짰습니다.

생각없이 이틀동안 두다다다 만들었는데, 예상 외로 결과가 뛰어나서 이렇게 KMS 13이라는 새로운 이름을 붙여 블로그에 내보내게 되었습니다.

 

개인적으로 C, algorithm, 암호화 이런것만 하고 C++은 vector나 priority_queue STL잠깐식 얹어 쓰는 상황이었는데, 이 프로그램을 개발하면서 대강 알고 있던 클래스를 사용했습니다. 물론 상속같은 것은 1도 없는 클래스 단 한 개이기 때문에, 구현에 큰 어려움은 없었지만, 상당히 새롭더군요.

 

실행 방법은 아래에 적어 놓았으니 참고하시면 됩니다.

---

technology

기술이랄 것은 없지만, 이 프로그램에서 쓴 약간의 절차? 프로세스가ㅇ 있습니다.

top이 존재하는 Binary tree를 기반으로 구현한, Huffman code length 만으로 코드를 복구하는 프로세스인데, 이런 방식이 기존 허프만 코드 알고리즘에도 존재하는지를 모르겠군요.

허프만 코드는 기본적으로 이진 트리 위에서 구현됩니다.
그런데, 제 프로그램에서 사용한 이진 트리는 기존의 이진 트리와는 다른 점이 존재하는데, 노드가 그 노드의 두 자식 노드의 주소를 저장할 뿐 아니라, 부모 노드의 주소 또한 저장한다는 점입니다.
 이렇게 이진 트리가 구성될 경우의 장점은 허프만 코드가 사전 순으로 정렬되어 있을 때, 허프만 코드의 길이만을 이용해서 허프만 코드를 완벽하게 재구성할 수 있습니다. 즉 압축 파일의 용량이 소량 감소하는 효과를 볼 수 있습니다. 파일 크기의 감소량은 허프만 코드의 압축 효율성이 증가할수록 더 커집니다.
 허프만 코드로 구성된 이진 트리는 허프만 코드가 한 개만 존재하지 않는 이상 모든 노드에서 자식 노드는 항상 둘 다 존재하거나 둘 다 존재하지 않는 상태이기 때문에 구현 가능했으며, 그 과정은 꽤 간단하니 코드를 보시면 바로 이해가 될겁니다. (extend 함수 초반부의 이중 for문이 이 과정을 처리하는 부분)

---

source

main.cpp

#include <iostream>
#include <fstream>
#include <sstream>

#include <algorithm>
#include <vector>

using namespace std;

/*
* [file construction]
* contents file is constructed by [size of key file, [key file], [contents file]]
* size of key file means the number of element in key file, which can expressed in two pair of character
* it also means the number of Huffman code
*/

/*
* [key file construction]
*
* key file is constructed by loop of [character, code length]
* 
* specially, key file include not code but code length
* since In this program, Huffman code will be formed, sorted regularly, 
* so code can be rebuilt by only code length 
* 
* character and code length is just one char valueable, so it can read and write easily
* 
* (It's definitely not that code length is bigger than 127, 
* since this program apply 128 character, so Huffman code cannot exceed 127)
*/

/*
* [data file construction]
*
* data file is constructed by one number and successive code list which is converted from original file
* file's first number is "length of successive code %(mod) 8", this number help program to read file correctly
* and the others are part for save code list.
* (code will stored in reverse state due to convenient of reading/writing)
*
* for instance, if code of 'a', 'b', 'c', is "0110", "1011" and "110", "accbac" will be converted like:
*           01101101 10101101 10110, and expressed like:
*           00000101 10110110 10110101 00001101
*/

namespace KmsStd {
    typedef long long intll;

    enum { FILE_CON_ERR = 0x11, FILE_EMPTY_ERR = 0x12, SUCCESS = 0x00 };

    template<typename T>
    std::ostream& write_typed_data(std::ostream& stream, const T& value) {
        return stream.write(reinterpret_cast<const char*>(&value), sizeof(T));
    }
    template<typename T>
    std::istream& read_typed_data(std::istream& stream, T& value) {
        return stream.read(reinterpret_cast<char*>(&value), sizeof(T));
    }

    /* ////////////////////////////// pressing ////////////////////////////// */
    namespace prs {
        typedef pair < pair < intll, char >, string > TYP1;

        bool CLC1(TYP1 a, TYP1 b) { return a.second < b.second; }
        void CLC2(string& BPF, ofstream& fout, int cycle, unsigned char ODF = 0) {
            for (int j = 0; j < cycle; j++) { ODF |= (unsigned char)(BPF[j] - '0') << j; }
            write_typed_data(fout, ODF);
        }

        //input file name, key file name, data file name
        int press(string IFN = "input.txt", string DFN = "data") {
            ifstream fin;

            string IFC; //input file contents
            stringstream ss;
            int IFS; //input file size

            bool registed[128] = { 0, };
            int IIV[128] = { 0, }; //index in vector
            int SEM; //semi valuable for calculation

            int vector_size;
            pair<int, intll> CM; //calculation supporter about constructing minimun value
            intll CS; //calculation support valuable

            ofstream fout;

            intll PFS; //predicted pressed file size (just in range of data file)
            intll PWS; //predicted whole file size

            vector < TYP1 > code; //use_count, char, code
            string BPF; //buffer for writing file

            /* read file */
            fin.open(IFN);
            if (!fin) { return FILE_CON_ERR; }
            ss << fin.rdbuf();
            IFC = ss.str();
            IFS = IFC.size();
            if (!IFS) { return FILE_EMPTY_ERR; }
            fin.close();

            /* caclulate use count */
            SEM = 0;
            for (int i = 0; i < IFS; i++) {
                if ((IFC[i] > 127) || (IFC[i] < 0)) { IFC[i] = '?'; }

                if (registed[IFC[i]]) {
                    code[IIV[IFC[i]]].first.first++;
                }
                else {
                    registed[IFC[i]] = 1;
                    IIV[IFC[i]] = SEM++;

                    code.push_back(make_pair(make_pair(1, IFC[i]), ""));
                }
            }
            cout << "get file & organize file successfully ( " << IFC.size() * 8 << " bit )" << endl;

            sort(code.rbegin(), code.rend());

            /* construct huffman code */
            code[0].second = "0";
            if (code.size() > 1) { code[1].second = "1"; }

            vector_size = code.size();
            for (int i = 2; i < vector_size; i++) {
                CM = make_pair(-1, LLONG_MAX);
                for (int j = 0; j < i; j++) {
                    CS = code[j].first.first + (code[i].first.first * (code[j].second.size() + 1));
                    if (CS < CM.second) { CM.first = j; CM.second = CS; }
                }
                code[i].second = code[CM.first].second + "0";
                code[CM.first].second += "1";
            }
            sort(code.begin(), code.end(), CLC1);

            /* construct key file & calculate pressed file size*/
            fout.open(DFN, std::ios::binary);
            if (!fout) { return FILE_CON_ERR; }
            PFS = 0;
            write_typed_data(fout, (char)vector_size);//
            for (int i = 0; i < vector_size; i++) {
                write_typed_data(fout, code[i].first.second);
                write_typed_data(fout, (char)code[i].second.size());

                PFS += code[i].first.first * code[i].second.size();
                IIV[code[i].first.second] = i;
            }
            PWS = PFS + 8 + (16 * vector_size);
            cout << "construct huffman code & key file successfully ( " << PWS << " bit )" << endl;
            cout << "  { " << (double) PWS * 12.5 / IFS << " % }" << endl;

            /* construct data file */
            BPF = "";
            write_typed_data(fout, (unsigned char)((PFS - 1) % 8 + 1));
            for (int i = 0; i < IFS; i++) {
                BPF += code[IIV[IFC[i]]].second;
                while (BPF.size() >= 8) {
                    CLC2(BPF, fout, 8);
                    BPF.erase(0, 8);
                }
            }
            if (BPF.size()) { CLC2(BPF, fout, BPF.size()); }
            fout.close();

            return SUCCESS;
        }
    }


    /* ////////////////////////////// extending ////////////////////////////// */
    namespace ext {
        enum { lft, rht };
        //this calss may be unsafe 
        class BTnode {
        public:
            char data;
            BTnode* left;
            BTnode* right;
            BTnode* top;

            BTnode(BTnode* left = nullptr, BTnode* right = nullptr, BTnode* top = nullptr) {
                this->data = 0x0;
                this->left = left;
                this->right = right;
                this->top = top;
            }
            BTnode(char data, BTnode* left = nullptr, BTnode* right = nullptr, BTnode* top = nullptr) {
                this->data = data;
                this->left = left;
                this->right = right;
                this->top = top;
            }
            ~BTnode() {
                if (this->left != nullptr) { delete(this->left); }
                if (this->left != nullptr) { delete(this->right); }
            }

            void BTnode_con_unsafe(int dir, char V = 0x0) {
                BTnode* lt = new BTnode;
                if (dir == lft) {
                    this->left = lt;
                    this->left->data = V; //left code = this code + "0"
                }
                else {
                    this->right = lt;
                    this->right->data = V; //right code = this code + "1"
                }
                lt->top = this;
            }

            //are node's left and right filled?
            bool isF(void) {
                if ((this->left != nullptr) && (this->right != nullptr)) { return true; }
                else { return false; }
            }
        };

        //calculation 2 (cur and BTtree, fout must be initalized, opened)
        void CLC1(const unsigned char IPI, BTnode*& cur, BTnode*& BTR, ofstream& fout, int cycle = 8) {
            for (int i = 0; i < cycle; i++) {
                if (IPI & (1 << i)) { cur = cur->right; }
                else { cur = cur->left; }

                if (cur->data) {
                    fout.put(cur->data);
                    cur = BTR;
                }
            }
        }

        //result file name, key file name, data file name
        int extend(string RFN = "extended_file.txt", string DFN = "data") {
            ifstream fin;
            ofstream fout;

            unsigned char IHS; //input Huffman code size
            unsigned char IPC; //input character
            unsigned char SKF; //size of key file
            bool LVO; //logic valuable for optimization

            BTnode* BTR = new BTnode; //binary tree root node
            BTnode* cur = BTR; //
            int DPT; //depth of tree

            unsigned char LFS; // last file size
            unsigned char IPI; //input string data
            unsigned char BIPI; //before input string data

            /* read key file & construct BT tree */
            fin.open(DFN, std::ios::binary);
            if (!fin) { return FILE_CON_ERR; }
            if (fin.eof()) { return FILE_EMPTY_ERR; }

            read_typed_data(fin, SKF);
            DPT = 0;
            for (int k = 0; k < SKF; k++) {
                read_typed_data(fin, IPC);
                read_typed_data(fin, IHS);

                for (LVO = cur->isF(); (DPT < (IHS - 1)) || LVO; LVO = cur->isF()) {
                    if (LVO) { cur = cur->top; DPT--; }
                    else {
                        if (cur->left == nullptr) {
                            cur->BTnode_con_unsafe(lft);
                            cur = cur->left;
                        }
                        else {
                            cur->BTnode_con_unsafe(rht);
                            cur = cur->right;
                        }
                        DPT++;
                    }
                    LVO = cur->isF();
                }

                if (cur->left == nullptr) { cur->BTnode_con_unsafe(lft, IPC); }
                else { cur->BTnode_con_unsafe(rht, IPC); }
            }
            cout << "read / construct Huffman code tree sucessfully" << endl;

            /* read data file & make extended file */
            fout.open(RFN);
            if (!fout) { return FILE_CON_ERR; }

            cur = BTR;
            read_typed_data(fin, LFS);
            read_typed_data(fin, IPI);
            for (;;) {
                BIPI = IPI;
                read_typed_data(fin, IPI);
                if (fin.eof()) { break; }
                CLC1(BIPI, cur, BTR, fout);
            }
            CLC1(BIPI, cur, BTR, fout, LFS);
            delete BTR;

            fin.close();
            fout.close();
            cout << "write extended file successfully" << endl;

            return SUCCESS;
        }
    }
}

int FNC1(int RST) {
    switch (RST) {
    case KmsStd::FILE_CON_ERR:
        cout << "file connect error\n";
        return 1;
    case KmsStd::FILE_EMPTY_ERR:
        cout << "file empty error\n";
        return 1;
    case KmsStd::SUCCESS:
        cout << "success\n";
        return 0;
    default:
        cout << "unknown error\n";
        return 1;
    }
}

int main() {
    int INP, RST;
    string FNM;

    for (;;) {
        cout << "\n     [  compress : 1  |  extend : 2  |  auto compress & extend : 3  |  exit : 4  ]\n";
        do {
            cout << "->";
            cin >> INP;
        } while ((INP < 1) || (INP > 4));

        if (INP == 1) {
            cout << "     input file name\n->";
            cin >> FNM;
            if (FNM == "auto") { FNM = "input.txt"; }
            RST = KmsStd::prs::press(FNM);
            FNC1(RST);
        }
        else if (INP == 2) {
            cout << "     result file name\n->";
            cin >> FNM;
            if (FNM == "auto") { FNM = "output.txt"; }
            RST = KmsStd::ext::extend(FNM);
            FNC1(RST);
        }
        else if (INP == 3) {
            RST = KmsStd::prs::press();
            if (!FNC1(RST)) { RST = KmsStd::ext::extend(); }
            FNC1(RST);
        }
        else { break; }
    }
    return 0;
}

대략 350줄 정도의 C++ 코드입니다. 주석이 상당히 많아서 실제로는 300줄 정도 되겠네요.

---

실행방법

1) 압축

사용자는 프로그램 실행 후, 1을 입력합니다.
이후 "input file name"이라는 메세지가 나오면, 압축하고자 하는 영문 텍스트 파일의 이름을 위치와 확장자인 ".txt"를 포함하여 입력합니다. ex ) C:\Users\mskang\Desktop\input.txt
입력후, 프로그램은 압축을 진행합니다. 압축된 파일의 데이터는 "data"라는 이름으로 저장됩니다. 위치는 프로그램이 있는 위치입니다.

 

* "auto"를 입력하시면 "input.txt"로 인식합니다.

 

2) 압축 해제

사용자는 반드시 1번 과정을 통해 data파일을 소스파일이 있는 위치에 저장하고 있어야 합니다.
프로그램 실행 후, 2를 입력합니다.

이후 "result file name"이라는 메세지가 나오면, 압축 해제된 데이터가 저장될 텍스트 파일의 이름음 위치와 확장자인 ".txt"를 포함한 영문 텍스트 파일을 입력합니다. ex) C:\Users\mskang\Desktop\result.txt
입력후, 프로그램은 압축 해제를 진행합니다. 결과 텍스트 파일은 사용자가 입력한 경로에 저장될 것이며, 경로가 없다면 프로그램이 있는 위치에 파일이 저장될 것입니다.

 

* "auto"를 입력하시면 "output.txt"로 받아들입니다.

 

3) 기타 기능

프로그램 소스가 있는 파일에 "input.txt"라는 이름을 가진 텍스트 파일이 있어야 합니다.

프로그램 실행 후, 3을 입력합니다.

프로그램이 자동으로 프로그램이 있는 위치의 "input.txt"파일을 압축하고, 압축 결과물들을 압축 해제한 뒤, 결과물을 프로그램이 있는 위치의 "output.txt"에 저장합니다. 이 기능은 프로그램의 신뢰성을 테스트하기 위해 개발되었습니다.

* 4를 입력하면 종료됩니다.

 

* 모든 파일 이름들에는 띄어쓰기가 없어야 합니다.

 

* 함수 선언 형태를 보시면 알겠지만, main함수를 개량하면 key file, data file의 위치, 이름까지 직접 지정하실 수 있습니다. 개량은 상당히 간단하기 떄문에, 개량은 직접 하시길 바랍니다.
이미 함수부에 많은 개량을 적용한 상태라 상당히 지치는군요.

---

실행파일

사실 실행파일을 블로그에 올리는 것은 바람직하지 않다 생각합니다. 지난번 글에서 깨달았는데, .exe파일을 웹에서 다운 받은 후, 실행할려고 하면 온갖 보안 경고가 다 뜹니다.

그래서 저는 소스코드를 다운로드하신 후 실행파일은 직접 만드시는걸 권장하지만, 그래도 실행 파일을 올려는 드리겠습니다.

 

* 참고로 UI는 없습니다. 사용방법만 보셔도 감이 오죠?

 

KMS 13소스 전문

https://drive.google.com/file/d/195Ma4t63Bpf0ZRBiQXWoHUkYIM4X4Oy6/view?usp=sharing 

KMS13 source.txt

 

KMS 13 테스트 자료 (세계 인권 선언문 전문)

https://drive.google.com/file/d/1yp2zJXdGFbDXbokHd-vN3oSZ6EU1tsN3/view?usp=sharing 

KMS13_input.txt

 

KMS 13 실행파일

https://drive.google.com/file/d/12o1ktbzQQueByYTV8cfW_gzRFJF65g_V/view?usp=sharing

KMS13.exe

 

참고 : 실행화면 영상

https://www.youtube.com/watch?v=PpgypqE-cOU 

 

이상으로 KMS였습니다. 감사합니다.