[Algorithm] Huffman Coding 3: Decoding 예제 설명 과 구현

Huffman 개념

https://vprog1215.tistory.com/232

[Algorithm] Huffman Coding 1: 개념

 

 

 

Decoding

• 앞서 encoding 한 파일을 decoding 하면 된다.
• 방법은 간단하다
• 이미 file 에는 run 의정보 가 담겨 있다.
• run 을 읽고 codeword 를 따라서 트리를 조회 하면 된다.

 

 

run 을 읽어들이는 코드

    private void inputFrequencies(RandomAccessFile fIn)
            throws IOException
    {
        int dataIndex = fIn.readInt();
        totalWordSize = fIn.readLong();

        for (int j = 0; j < dataIndex; j++) {
            byte symbol = (byte) fIn.read();
            int runLength = fIn.readInt();
            int freq =  fIn.readInt();

            Run r = new Run(symbol, runLength, freq);
            runs.add(r);
        }
    }

 

 

 

run 을 huffman 트리로 만드는 코드 (인코딩과 동일)

    public void createHuffmanTree() {
        for(int i = 0; i <runs.size(); i++) {
            minHeap.insert(runs.get(i));
        }

        while (minHeap.size() != 1) {
            Run childRun1 = minHeap.extractMin();
            if (childRun1 == null) {
                break;
            }

            Run childRun2 = minHeap.extractMin();
            if (childRun2 == null) {
                break;
            }

            Run parentRun =  createRunTree(childRun1, childRun2);
            minHeap.insert(parentRun);
        }

        root = minHeap.getMinRun();
    }

    public Run createRunTree(Run run1, Run run2) {
        int num = -1;
        num = run1.getFreq() + run2.getFreq();
        Run parentRun = new Run((byte)0, 0, num);
        if (run1.compareTo(run2) > 0) {
            parentRun.setLeftChild(run1);
            parentRun.setRightChild(run2);
        } else {
            parentRun.setLeftChild(run2);
            parentRun.setRightChild(run1);
        }
        return parentRun;
    }

 

 

codeword를 부여하는 코드(인코딩과 동일)

    private void assignCodewords(Run p, int codeword, int length) {
        if(p.getLeftChild() == null && p.getLeftChild() == null) {
            p.setCodeword(codeword);
            p.setCodewordLen(length);
        } else {
            assignCodewords(p.getLeftChild(), (codeword << 1 | 0), length+1);
            assignCodewords(p.getRightChild(), (codeword << 1 | 1), length+1);
        }
    }

 

 

decode 코드

    private boolean decode(RandomAccessFile fIn, RandomAccessFile fOut) throws IOException {
        int numberCounter = 1;
        String tmpString = "";
        int readCount = 0;
        Run rootRun = root;
        String symbol = "";

        try {
            while (true)
            {

                if(rootRun.getRightChild() == null && rootRun.getLeftChild() == null) {
                    for(int i = 0; i < rootRun.getRunLength(); i++) {
                        symbol += (char)rootRun.getSymbol();
                        readCount++;
                    }
                    rootRun = root;
                }

                byte codeword = fIn.readByte();

                if(codeword != 0) {
                    rootRun = rootRun.getRightChild();
                } else {
                    rootRun = rootRun.getLeftChild();
                }

                if (readCount == totalWordSize) {
                    break;
                }
            }
        }
        catch (EOFException ex)
        {
            System.out.println("Total number " + numberCounter);
            System.out.println("End of file reached!");
        }
        fOut.writeChars(symbol);
        System.out.println("Decoding: "+symbol);
        return true;
    }

 

 

결과

===========================================
Huffman Tree
===========================================
0,0 0
 0,0 0
  65,1 0
  0,0 0
   66,1 2
   65,3 3
 0,0 0
  0,0 0
   67,1 4
   66,2 5
  0,0 0
   67,2 6
   65,2 7


===========================================
decoding
===========================================
AAABCCAABBCAA

 

 

전체코드

https://github.com/rnrl1215/algorithm-study/tree/main/src/main/java/algorithm/huffman

GitHub - rnrl1215/algorithm-study