::: 강좌/소스/문서 :::

강좌/소스/문서 성격에 맞지 않는 광고,비방,질문의 글은 즉시 삭제하며
내용을 복사하여 사용할 경우 반드시 이곳(http://www.howto.pe.kr)을 출처로 명시하여 주세요


Category

  김영대(2003-03-18 22:37:28, Hit : 7819, Vote : 1504
 [소스] Huffman Code Encoder

// 제  목: Huffman Code Encoder
// 작성자: 김영대 ( http://www.howto.pe.kr )

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <math.h>

main(int argc, char **argv) {
  int ifd, ofd, fsize;
  unsigned char *src_data;
  int i, j;
  int Min, Max, Range, Pos, MinProb;
  int Buffer, BufLen;
  int *Prob, *Parent;
  char *Bit, *BitCode;
  int Len, TotalLen=0;
  char outfile[255];
  int debug = 0;
        
  if (argc != 2) {
    fprintf(stderr, "사용법: %s 파일명n", argv[0]);
    exit(1);
  }  
  
  if ((ifd = open(argv[1], O_RDONLY)) < 0) {
    fprintf(stderr, "%s 파일을 읽을 수 없습니다n", argv[1]);
    exit(1);
  }

  // source file 의 크기를 구하여 저장할 버퍼를 할당 받는다
  fsize = lseek(ifd, 0L, 2); // 파일크기
  lseek(ifd, 0L, 0); // 파일 포인터를 맨 앞으로 이동
  src_data = (char *)malloc(fsize);

  // source파일을 읽는다
  if (read(ifd, src_data, fsize) < fsize)
    exit(1);

  // target파일을 생성한다
  strcpy(outfile, argv[1]);
  strcat(outfile, ".huf"); // 확장자는 .huf
  if ((ofd = creat(outfile, 0644)) < 0) {
    fprintf(stderr, "%s 파일을 만들 수 없습니다n", outfile);
    exit(1);
  }
      
  // min,max byte 값을 구한다
  Min = Max = src_data[0];
  for (i = 1; i < fsize; i++) {
    if (Min > src_data[i])
      Min = src_data[i];
    else if (Max < src_data[i])
      Max = src_data[i];
  }
  Range = Max - Min + 1; // 분포된 byte 값들의 범위

  // 초기화
  Bit     = (char *)malloc(2*Range-1); // 코드로 할당할 bit를 저장(0 or 1)
  BitCode = (char *)malloc(2*Range-1); // 코드로 할당할 bit의 ASCII 저장('0' or '1')
  Prob    = (int *)malloc(sizeof(int)*2*Range-1); // 확률(0..Range-1), 모든 Prob를 더하면 Max 가 된다
  Parent  = (int *)malloc(sizeof(int)*2*Range-1);
  memset(Bit,     0, 2*Range-1);
  memset(BitCode, 0, 2*Range-1);
  memset(Prob,    0, sizeof(int)*2*Range-1);
  memset(Parent, -1, sizeof(int)*2*Range-1);

/* Example
   source data: 3 4 4 5 6 6 6 7 7 10
      src_data: 0 1 1 2 3 3 3 4 4  7
           Min: 3
           Max: 10
         Range: 10-3+1 = 8
                
   Probability:
        index: 0  1  2  3  4 5 6  7 8  9 10 11 12 13 14
         Prob: 1  2  1  3  2 0 0  1 0  1  2  3  4  6 10
       parent: 9 11 10 13 12 8 8 10 9 11 12 13 14 14 -1
*/

  for (i = 0; i < fsize; i++) {
    // byte 값에서 min을 빼서 0..Max-Min(= Range-1) 로 환산한다          
    // 그 이유는 Prob[]의 index를 0 부터 쓰기 위해서
    src_data[i] -= Min;  
    Prob[src_data[i]]++; // byte 값이 나타난 횟수(확률)을 구한다
  }    

  // Huffman code tree 를 만든다
  for (i = 0; i < (Range-1); i++) {
    /* 가장 작은 첫번째 확률을 구한다 */
    Pos = -1;
    MinProb = fsize; // 단지 가장 작은수를 구하기 위한 큰수
    // 이전에 구한 두 byte 의 확률도 loop 에 포함시킨다
    for (j = 0; j < Range+i; j++)
      if ((Prob[j] < MinProb) && (Parent[j] == -1)) {
        MinProb = Prob[j];
        Pos = j;
      }
    Bit[Pos] = 0; // 비트할당
    Parent[Pos] = Range + i; // tree로 가정할경우 상위(두 byte 의 확률을 가지고 있는) 노드의 위치
    Prob[Parent[Pos]] += MinProb; // 첫번째 가장 작은것과 두번째 가장 작은 두 byte 의 확률을 더한다

    /* 가장 작은 두번째 확률을 구한다 */
    Pos = -1;
    MinProb = fsize;
    for (j = 0; j < Range+i; j++)
      if ((Prob[j] < MinProb) && (Parent[j] == -1)) {
        MinProb = Prob[j];
        Pos = j;
      }
    Bit[Pos] = 1;
    Parent[Pos] = Range + i;
    Prob[Parent[Pos]] += MinProb;
  }
  
  /* Print Huffman code tree */
  if (debug) {
    for (i = 0; i < Range; i++) {
      // 확률이 0 인것도 코드가 부여되지만 의미가 없으므로 제외
      if (Prob[i] == 0)
        continue;
      
      // leaf 노드부터 parent 로 올라가면서 huffman code를 구한다
      Len = 0;
      Pos = i;
      printf("값 %.2X, 확률 %d/%d, 코드 ", i+Min, Prob[i], fsize);
      while (Parent[Pos] >= 0) {
        BitCode[Len++] = Bit[Pos]; // leaf의 bit부터 들어가지만 실제 사용시는 반대
        Pos = Parent[Pos]; // 상위 노드로 이동
      }
      
      // Huffman code로 encoding 하였을때의 소요되는 bit수 합산
      TotalLen += Len * Prob[i];
      
      // leaf의 bit부터 들어가 있으므로 역으로 출력
      while (Len > 0)
        printf("%c", '0' + BitCode[--Len]);
      printf("n");
    }
    printf("코드의 평균길이 %f bitsn", TotalLen / (float)(fsize));
  }    

  // Huffman encoded 파일의 헤더를 출력한다
  write(ofd, "HM", 2); // ASCII "HM"
  write(ofd, &Min, sizeof(Min)); // min Byte 값
  write(ofd, &Max, sizeof(Max)); // max Byte 값, Range 는 Max-Min+1 로 계산하여 구한다
  write(ofd, Prob, Range*sizeof(Prob[0])); // 확률

  // Huffman codes 를 이용하여 실제로 Encoding 하여 출력한다
  Buffer = 0;
  BufLen = 0;
  for (i = 0; i < fsize; i++) {
    // leaf 노드부터 parent 로 올라가면서 huffman code를 구한다
    Len = 0;
    Pos = src_data[i];
    while (Parent[Pos] >= 0) {
      BitCode[Len++] = Bit[Pos];
      Pos = Parent[Pos];
    }

    // Write Huffman code one bit at a time
    while (Len > 0) {
      // 이전 bit를 left shift(상위 bit로 이동) 시키고 현재 bit를 or 시킨다
      Buffer = (Buffer << 1) | BitCode[--Len];
      BufLen++;

      // Buffer full = 4 byte boundary
      if (BufLen == sizeof(Buffer)) {
        write(ofd, &Buffer, 1, sizeof(Buffer));
        Buffer = 0;
        BufLen = 0;
      }
    }
  }
  // Buffer 에 남아있으면 4 byte boundary 시켜 출력
  if (BufLen != 0) {
    // left most shift(상위 bit로 이동)
    Buffer = Buffer << (32 - BufLen);
    write(ofd, &Buffer, 1, sizeof(Buffer));
  }

  free(src_data);
  free(Bit);
  free(BitCode);
  free(Prob);
  free(Parent);
  
  close(ifd);
  close(ofd);
}      





13   [컴퓨터 전공] [소스] 이진 트리(Binary Tree)  김영대 2004/06/18 9792 1828
12   [컴퓨터 전공] [소스] MASM 간단한 계산기 어셈블리 프로그램 소스  김영대 2003/07/11 9635 1505
11   [컴퓨터 전공] [소스] Top-down parsing by Recursive-Descent 을 이용한 계산기 MASM 어셈블리 생성기  김영대 2003/07/11 7484 1604
  [컴퓨터 전공] [소스] Huffman Code Encoder  김영대 2003/03/18 7819 1504
9   [컴퓨터 전공] [소스] Windows RLE(BMP) Encoder  김영대 2003/03/18 7516 1326
8   [컴퓨터 전공] [소스] CompuServe RLE Encoder  김영대 2003/03/18 6174 1438
7   [컴퓨터 전공] [소스] 계산기를 위한 Lex & Yacc  김영대 2003/03/15 9807 1599
6   [컴퓨터 전공] [소스] ANSI-C 파서를 위한 Lex & Yacc  김영대 2003/03/13 8645 1931
5   [컴퓨터 전공] [소스] PL/0 Compiler 구현  김영대 2003/03/13 7436 1693
4   [컴퓨터 전공] [소스] Recursive-Descent 파싱을 이용한 계산기 구현  김영대 2003/03/13 10277 1613
3   [컴퓨터 전공] [소스] POSIX thread를 사용한 행렬계산  김영대 2003/03/13 7357 1510
2   [컴퓨터 전공] [소스] 0/1 배낭 문제(Knapsack Problem)  김영대 2003/03/13 9028 1601
1   [컴퓨터 전공] [소스] SIC/XE 어셈블러 구현  김영대 2003/03/13 18549 1860

1
 

Copyright 1999-2017 Zeroboard / skin by zero