[Java] Huffman Coding 1/2

공학수학2 / 2002년 2학기 / 박근수 교수님

[설명]
Huffman Coding : 각 문자의 Frequency를 이용한 텍스트 압축
Huffenc.java : 입력텍스트(Huffman.in)로부터 압축파일(Huffman.cmp)과 빈도파일(Huffman.frq) 생성
Huffdec.java : 압축파일과 빈도파일로부터 출력텍스트(Huffman.out) 생성
HuffmanTree.java : 코딩&디코딩에 사용되는 트리

[Huffenc.java]
import java.io.*;

class HuffOutputStream                                // 비트단위 출력을 담당하는 클래스
{
       public HuffOutputStream(OutputStream os) throws IOException
       {
               buffer = 0;                                        // 한 바이트를 읽어 저장하는 버퍼
               position = 0;                                // 현재 비트가 바이트 내에서 몇번째 비트인지를 가리킴.
               out = new DataOutputStream(os);
       }

       public void writeCode(String code) throws IOException                // 0과 1의 스트링으로 된 코드를 출력
       {
               for (int i=0; i<code.length(); i++)
                       writeBit(code.charAt(i));                                                        // 한 비트씩 출력
       }

       private void writeBit(char c) throws IOException                        // 0 또는 1의 한 비트 출력
       {
               if (c == '1')
                       buffer |= (1<<position);                                                        // '00000001' 을 포지션만큼 왼쪽으로 쉬프트 시켜서 버퍼에 OR 시킴.
               else if (c != '0')
                       throw new IOException("Wrong Code!");
               position++;                                                                                                // 포지션을 한 칸 이동.
               if (position == 8)                                                                                // 마지막 비트까지 채웠으면 파일에 씀
                       flush();
       }

       public void flush() throws IOException                                                // 한 바이트가 되었을때 파일에 씀.
       {
               if (position == 0)                                                                                // 만약 한비트도 써지지 않았으면 아무것도 쓰지 않음
           return;
       out.write(buffer);
       position = 0;                                                                                        // 포지션 초기화
       buffer = 0;                                                                                                // 버퍼 초기화
       }

       public void close() throws IOException
       {
               flush();                                                                                                // 현재까지 쓰여진 1바이트가 안된 비트들을 파일에 씀
               out.close();
       }

       private DataOutputStream out;
       private int buffer;
       private int position;
}

public class Huffenc
{
       public static String inputFileName = "Huffman.in";
       public static String freqFileName = "Huffman.frq";
       public static String outputFileName = "Huffman.cmp";

       public static void main(String[] args) throws IOException
       {
               HuffmanTree tree = new HuffmanTree();

               InputStream fin = new BufferedInputStream(new FileInputStream(inputFileName));
               tree.charCount(fin);                                                                                        // 문자들의 프리퀀시를 셈
               fin.close();

               DataOutputStream freqOut = new DataOutputStream(new FileOutputStream(freqFileName));
               tree.writeFreq(freqOut);                                                                                // 프리퀀시 파일을 씀
               freqOut.close();
               
               fin = new BufferedInputStream(new FileInputStream(inputFileName));                // 한번 더 읽기 위해 다시 open
               HuffOutputStream fout = new HuffOutputStream(new FileOutputStream(outputFileName));
               int buf = fin.read();                                                                                        // 한 글자 읽음
               while (buf != -1)                                                                                                // 파일이 끝날때까지
               {
                       fout.writeCode(tree.getCode(buf));                                                        // 글자를 코드로 변환해서 출력
                       buf = fin.read();                                                                                        // 다시 한 글자 읽음
               }
               fout.writeCode(tree.getCode(tree.EOF));                                                        // 마지막임을 뜻하는 문자 쓰기
               fout.close();
       }
}

[Huffdec.java]
import java.io.*;

class HuffInputStream                                        // 비트단위 입력을 담당하는 클래스
{
       public HuffInputStream(InputStream is) throws IOException
       {
               position = 8;                                        // 현재 비트의 위치 기본값 지정
               in = new DataInputStream(is);   // 바이너리 인풋
       }

       public int readCode(HuffmanTree tree) throws IOException
       {
       String code = "";                                // 코드를 저정할 스트링
       int bit = readBit();                        // 한 비트를 읽어서 저장 (0 또는 1)
               int decodedKey;

       while(true)
       {
           code += bit;                                                                        // 스트링에 방금 읽은 비트 추가
                       decodedKey = tree.getKey(code);                                        // 지금 까지 스트링을 decode 해본다
                       if (bit==-1 || decodedKey==tree.ERROR)                        // EOF가 나오기 전에 파일이 끝나거나 디코딩 에러가 날 경우
                       {
                               System.out.println("Decoding Error!");
                               System.exit(0);
                       }
                       else if (decodedKey == tree.NOT_A_VALUE)                // 아직 하나의 코드가 아닐 경우
                       {
                               bit = readBit();                                                        // 새로운 비트를 읽고 다음 loop을 실행
                               continue;
                       }
                       else
                               return decodedKey;                                                                // 제대로 디코딩 되었으면 디코드한 결과를 리턴
               }
       }

       private int readBit() throws IOException                                // 한 비트를 읽음
       {
               if ( position == 8 )                                                                // 현재 남은 비트가 없으면 (혹은 처음이면)
       {
           buffer = in.read();                                                                // 한 바이트를 읽어서
           if( buffer == -1 )                                                                // 끝이면 끝이라고 리턴
               return -1;
           position = 0;                                                                        // 포지션을 맨 앞으로
       }

               return (buffer & (1<<position++)) == 0 ? 0 : 1;                // '00000001'을 포지션만큼 왼쪽으로 쉬프트시켜서 버퍼랑 AND 시킨 결과가 현재 비트!
       }

       public void close() throws IOException
       {
               in.close();
       }

       private DataInputStream in;
       private int buffer;
       private int position;
}

public class Huffdec
{
       public static String inputFileName = Huffenc.outputFileName;
       public static String freqFileName = Huffenc.freqFileName;
       public static String outputFileName = "Huffman.out";

       public static void main(String[] args) throws IOException
       {
               HuffmanTree tree = new HuffmanTree();
               DataInputStream freqIn = new DataInputStream(new FileInputStream(freqFileName));
               tree.readFreq(freqIn);                                                                                                                                // 프리퀀시 파일을 읽음
               freqIn.close();

               HuffInputStream fin = new HuffInputStream(new FileInputStream(inputFileName));
               OutputStream fout = new BufferedOutputStream(new FileOutputStream(outputFileName));
               int currentChar = fin.readCode(tree);                                                                                        // 디코드된 글자 하나를 읽음
               while (currentChar != tree.EOF)                                                                        // 마지막 이전까지
               {
                       fout.write(currentChar);                                                                                        // 글자를 씀
                       currentChar = fin.readCode(tree);                                                                        // 다시 글자 하나를 읽음
               }
               fin.close();
               fout.close();
       }
}