하프 만 트 리, 하프 만 인 코딩 과 디 코딩 실현 (c 언어)

실험 수업 에서 시작 하여 하프 만 트 리, 하프 만 인 코딩 과 디 코딩 을 실현 하도록 요구한다.나 는 직접 실험 요구 와 코드 를 붙 여 실현 했다.주: 시간 이 제한 되 어 있 었 기 때문에 이 코드 는 최적화 공간 이 있 었 고 출력 파일 은 0 / 1 문자열 텍스트 (UTF - 8) 였 습 니 다. ASCII 코드 인 코딩 파일 이 아니 었 습 니 다. 압축 률 을 8 로 나 누 면 됩 니 다.
실험 항목: 하프 만 인 코딩 과 디 코딩 방법
하 프 만 인 코딩 은 하 프 만 트 리 (최 적 화 된 이 진 트 리, 권한 경로 길이 가 가장 작은 이 진 트 리) 를 바탕 으로 통계학 을 바탕 으로 하 는 긴 인 코딩 방식 이다.그 기본 사상 은 사용 횟수 가 많은 코드 를 길이 가 짧 은 인 코딩 으로 바 꾸 고 사용 횟수 가 적은 것 은 긴 인 코딩 을 사용 하 며 인 코딩 의 유일한 가용성 을 유지 하 는 것 이다.컴퓨터 정보 처리 에 서 는 데이터 압축 에 자주 사용 된다.일치 성 인 코딩 법 (일명 엔트로피 인 코딩 법) 으로 데이터 의 무 손실 압축 에 사용 된다.이 실험 은 욕심 산법 을 이용 하여 완전한 하프 만 인 코딩 과 디 코딩 시스템 을 실현 할 것 을 요구한다.
실험 내용 과 실험 요구:

파일 에서 임의의 영문 텍스트 파일 을 읽 고 영문 텍스트 파일 의 각 문자 (구두점 기호 와 빈 칸 포함) 의 사용 빈 도 를 통계 합 니 다.

통 계 된 문자 에 따라 주파수 구조 하프 만 인 코딩 트 리 를 사용 하고 모든 문자 의 하프 만 인 코딩 (문자 집합의 하프 만 인 코딩 표) 을 제시한다.

텍스트 파일 을 하프 만 트 리 로 인 코딩 하여 압축 파일 (하프 만 인 코딩 파일) 로 저장 합 니 다.

하프 만 인 코딩 파일 의 압축 률 계산 하기;

하프 만 인 코딩 파일 을 텍스트 파일 로 디 코딩 하고 원본 파일 과 비교한다.C 코드:

#include 
#include 
#include 

#define n 65

//          
typedef struct{
    char data;
    int weight;
    int lchild;
    int rchild;
    int parent;
}Htnode;

typedef Htnode HuffmanT[129];

//           
typedef struct{
    char ch;        //        
    char bits[n+1]; //      
}CodeNode;

typedef CodeNode HuffmanCode[n];


//0-9   ；10-35     ；36-61     ；62-64     
void InitHT(HuffmanT T)   //   
{
    char sz = '0';
    char xzm = 'a';
    char dzm = 'A';
    char kong = ' ';
    char dh = ',';
    char jh = '.';

    for(int i=0; i<n; i++)        
    {
        T[i].lchild = T[i].rchild = T[i].parent = -1;
        T[i].weight = 0;
        if(i>=0&&i<=9)
        {
            T[i].data = sz;
            sz++;
        }
        if(i>=10&&i<=35)
        {
            T[i].data = xzm;
            xzm++;
        }
        if(i>=36&&i<=61)
        {
            T[i].data = dzm;
            dzm++;
        }
        if(i>=62&&i<=64)
        {
            T[62].data = kong;
            T[63].data  = dh;
            T[64].data= jh;
        }
    }

    for(int j = n; j<2*n-1; j++)
    {
        T[j].weight = 0;
        T[j].lchild = T[j].rchild = T[j].parent = -1;
    }

    printf("initHT over
");
}

void InputW(HuffmanT T)         //            
{
    FILE *fp;
    char ch;
    char Filename[20];

    printf ("input the filename:");
    scanf("%s",Filename);
   
    if((fp=fopen(Filename,"r"))==NULL)    printf("faild
");
    ch = fgetc(fp);

    while(ch != EOF)
    {
        for(int i = 0; i<n; i++)
        {
            if(T[i].data == ch) T[i].weight++;
        }
        ch = fgetc(fp);
    }

    for(int i =0; i<n; i++)
    {
        printf("%c weight is:",T[i].data);
        printf("%d
",T[i].weight);
        // printf("%d,%d,%d
",T[i].parent,T[i].lchild,T[i].rchild);
    }
    
    fclose(fp);
   
    printf("inputW over
");
}

void SelectMin(HuffmanT T, int length, int *p1, int *p2)    //           ，    
{
    int min1,min2;              //min1    ，min2    
    int i=0;
    int k,j=0;
    for(j; j<length; j++)
    {
        if(T[j].parent == -1)
        {
            min1=j;
            break;
        }
    }

    for(k=min1+1;k<length;k++)
    {
        if(T[k].parent == -1)
        {
            min2 = k;
            break;
        }
    }
    // for(i = 0;i
    while(i<length)
    {
        if(T[i].parent == -1)
        {
            
            if(T[i].weight<T[min1].weight)
            {
                min2 = min1;
                min1 = i;
            }
            else if((i!=min1)&&(T[i].weight<T[min2].weight))
            {
                min2 = i;
            }
        }

        i++;
    }

    // printf("%d,%d:%d,%d ",min1,min2,T[min1].weight,T[min2].weight);
    *p1 = min1;
    *p2 = min2;

    // printf("selectmin
");
}

void CreartHT(HuffmanT T)       //        
{
    int i,p1,p2;
    int wei1,wei2;
    InitHT(T);      //   
    InputW(T);      //    
    for(i=n; i<129; i++)
    {
        SelectMin(T,i,&p1,&p2);
        wei1 = T[p1].weight;
        wei2 = T[p2].weight;
        T[p1].parent = i;
        T[p2].parent = i;
        T[i].lchild = p1;
        T[i].rchild = p2;
        T[i].weight = wei1 + wei2;
    }

    printf("creatHT over
");
}

void CharSetHuffmEncoding(HuffmanT T, HuffmanCode H)    //             H
{
    int c,p,i;          //c p    T        
    char cd[n+1];       //      
    int start;          //     cd    
    cd[n]='\0';         //     
    for(i=0; i<n; i++)
    {
        H[i].ch = T[i].data;
        start = n;
        c=i;
        while((p=T[c].parent)>=0)   //   T[c]     
        {
            cd[--start] = (T[p].lchild==c) ? '0':'1';   //T[c] T[p]    ，    0    1
            c=p;
        }
        strcpy(H[i].bits,&cd[start]);
    }
    printf("creatHcode over
");
}

void PHUM(char *file,char *s);

char s[30000]={3};
void PrintHUffmancode(HuffmanCode H)        //                       txt  
{
    
    FILE *fp;
    char ch;
    char Filename[80];
    char file[80];

    printf ("output the Huffmancode of which file:");
    scanf("%s",Filename);
    if((fp=fopen(Filename,"r"))==NULL)    printf("failda
");
    ch = fgetc(fp);
    int L =0;
    printf("1");
    while(ch != EOF)
    {

        for(int i = 0; i<n; i++)
        {
            if(H[i].ch == ch) 
            {
                printf("%s",H[i].bits);
                sprintf(s+L,"%s",H[i].bits);
                L=strlen(s);
            }
        }

        ch = fgetc(fp);
    }
    printf("
");

    for(int k =0;k<n;k++)
    {
        printf("%c-%s
",H[k].ch, H[k].bits);
    }

    // printf("3
");
    fclose(fp);
    printf("stand by
");

    PHUM(file,s);
    
}

void PHUM(char *file,char *s)
{
    FILE *fp;
    int i=0;
    printf ("save your Huffmancode to the file:");
    scanf("%s",file);
    if((fp=fopen(file,"w"))==NULL)    printf("faild
");

    while(s[i]!='\0')
    {
        // fwrite(s,1,strlen(s),fp);
        // fprintf(fp,'%c',s[i]);
        fprintf(fp,"%c",s[i]);
        i++;
    }
    
    fclose(fp);
    printf("write over
");

    
}

void Printftxt(HuffmanT T,char a[])  // 0 1
{
    int root,c;
    int i = 0;
    FILE *fp;
    char ch;
    char Filename[30];

    printf ("print words acroding to Huffmancode:");
    scanf("%s",Filename);
    if((fp=fopen(Filename,"r"))==NULL)    printf("faild
");

    // printf("1
");
    for(int j =0; j<129; j++)     //     
    {
        if(T[j].parent==-1)
        {
            root = j;
            break;
        }
    }
    
    ch=fgetc(fp);
    while(ch!=EOF)
    {
        c=root;

        while((T[c].lchild != -1) || (T[c].rchild != -1))
        {
            if(ch=='0')
            {
                c=T[c].lchild;
                ch = fgetc(fp);
            }
            else if(ch=='1')
            {
                c=T[c].rchild;
                ch = fgetc(fp);
            }
            // printf("2");
        }

        printf("%c",T[c].data);
       
        // ch = fgetc(fp);

    }

    fclose(fp);
}

int main()
{
    HuffmanT T;
    HuffmanCode H;

    CreartHT(T);     //                            
    CharSetHuffmEncoding(T,H);   //            ，         
    PrintHUffmancode(H);        //               ，           
    
    Printftxt(T,s);   //               

}