Жадные алгоритмы. Код Хаффмана

{

    sym *temp;

    temp=(sym*)malloc(sizeof(sym));

    temp->freq=psym[k-1]->freq+psym[k-2]->freq;

    temp->code[0]=0;

    temp->left=psym[k-1];

    temp->right=psym[k-2];

 

    if(k==2)

        return temp;

    else //внесение в массив в нужное место элемента дерева Хофмана

    {

        for(int i=0;i<k;i++)

            if (temp->freq>=psym[i]->freq)

            {  

                for(int j=k-1;j>i;j--)

                    psym[j]=psym[j-1];                                 

               

                psym[i]=temp;

                break;

            }      

    }

return makeTree(psym,k-1);

}

 

void makeCodes(sym *root)//Рекурсивная функция кодирования

{

    if(root->left)

    {

        strcpy(root->left->code,root->code);

        strcat(root->left->code,"0");

        makeCodes(root->left);

    }

    if(root->right)

    {

        strcpy(root->right->code,root->code);

        strcat(root->right->code,"1");

        makeCodes(root->right);

    }

}

 

 

int main ()

{   clock_t time = clock();

    FILE *fp,*fp2,*fp3; //указатели на файлы

    //fp=fopen("777.txt","rb"); //открываем конкретный файл для сжатия

    fp=fopen("input.txt","rb"); //открываем конкретный файл

    fp2=fopen("output.txt","wb");//открываем файл для записи бинарного кода

    fp3=fopen("derevo.txt","wb");//открываем файл для записи сжатого файла

 

    int chh;  // в эту переменную читается информация из файла

    int k=0; //счётчик количества различных букв, уникальных символов

    int kk=0; // счётчик количества всех знаков в файле

    int fsize2=0;//счётчик количества символов из 0 и 1 в промежуточном файле temp

    int ts;//размер хвоста файла (то, что не кратно 8 в промежуточном файле)

    int kolvo[256]={0};//инициализируем массив количества уникальных символов

    sym simbols[256]={0}; //инициализируем массив записей

    sym *psym[256]; //инициализируем массив указателей на записи

    int summir=0;//сумма частот встречаемости

    int mes[8];//массив 0 и 1

    char j=0;//вспомогательная переменная

   

    //Обработка ошибок чтения файла

    if(fp==NULL)

    {

        puts("FILE NOT OPEN!!!!!!!");

        return 0;

    }

 

    sym *symbols=(sym*)malloc(k*sizeof(sym));//создание динамического массива структур simbols

    sym **psum=(sym**)malloc(k*sizeof(sym*));//создание динамического массива указателей на simbols

   

    //Начинаем побайтно читать файл и составлять таблицу встречаемости

    while((chh=fgetc(fp))!=EOF)

    {      

        for(int j=0; j<256; j++)

        {

            if (chh==simbols[j].ch)

            {

                kolvo[j]++;

                kk++;              

                break;

            }

            if (simbols[j].ch==0)

            {

                simbols[j].ch=(unsigned char)chh;

                kolvo[j]=1;

                k++; kk++;

                break;

            }          

        }      

    }

 

    // Рассчёт частоты встречаемости

    for(int i=0;i<k;i++)

        simbols[i].freq=(float)kolvo[i];

   

    for(int i=0;i<k;i++) //в массив указателей заносим адреса записей

        psym[i]=&simbols[i];

   

 

//Сортировка по убыванию 

    sym tempp;

    for(int i=1;i<k;i++)

        for(int j=0;j<k-1;j++)

            if(simbols[j].freq<simbols[j+1].freq)

            {

                tempp=simbols[j];

                simbols[j]=simbols[j+1];

                simbols[j+1]=tempp;

            }

 

for(int i=0;i<k;i++)

{

    summir+=simbols[i].freq;   

    printf("Ch= %d\tFreq= %f\tPPP= %c\t\n",simbols[i].ch,simbols[i].freq,psym[i]->ch,i);

}

    printf("\n Slova = %d\t\n",kk);

   

    sym *root=makeTree(psym,k);//вызов функции создания дерева Хофмана

   

    makeCodes(root);//вызов функции получения кода

 

    rewind(fp);//возвращаем указатель в файле в начало файла

//в цикле читаем исходный  файл, и записываем полученные  в функциях коды в промежуточный  файл

while((chh=fgetc(fp))!=EOF)

{

    for(int i=0;i<k;i++)

        if(chh==simbols[i].ch)

            fputs(simbols[i].code,fp2);

}

fclose(fp2);

 

//Заново открываем файл  с бинарным кодом, но теперь  для чтения

int i=0;

fp2=fopen("output.txt","rb");

//Считаем размер бинарного  файла(количество символов в нём)

while((chh=fgetc(fp2))!=EOF)

        fsize2++;

 

ts=fsize2%8;//находим остаток, количество символов не кратных 8 (хвост)

 

//формируем заголовок  сжатого файла через поля байтов

fwrite("compresing!!!",sizeof(char),24,fp3);//условная подпись

fwrite(&k,sizeof(int),1,fp3);//количество уникальных символов

fwrite(&ts,sizeof(int),1,fp3);//величина хвоста

//Записываем в сжатый  файл таблицу встречаемости

for(i=0;i<k;i++)

{

    fwrite(&simbols[i].ch,sizeof(sym),1,fp3);

    fwrite(&simbols[i].freq,sizeof(sym),1,fp3);

}

 

rewind(fp2);//возвращаем указатель в промежуточном файле в начало файла

 

union code code1;//инициализируем переменную code1

//Читаем бинарный файл, занося последовательно каждые 8 элементов в массив для последующей  побитовой обработки в объединении  union

j=0;

for(int i=0;i<fsize2-ts;i++)

{

    mes[j]=fgetc(fp2);

    if(j==7)

    {      

        code1.byte.b1=mes[0]-'0';

        code1.byte.b2=mes[1]-'0';

        code1.byte.b3=mes[2]-'0';

        code1.byte.b4=mes[3]-'0';

        code1.byte.b5=mes[4]-'0';

        code1.byte.b6=mes[5]-'0';

        code1.byte.b7=mes[6]-'0';

        code1.byte.b8=mes[7]-'0';

        fputc(code1.chhh,fp3);

        j=0;

    }

    j++;   

}

//Записываем хвост

j=0;

for(int i=0;i<=ts;i++)

{

    mes[j]=fgetc(fp2);

    if(j==ts)

    {      

        code1.byte.b1=mes[0]-'0';

        code1.byte.b2=mes[1]-'0';

        code1.byte.b3=mes[2]-'0';

        code1.byte.b4=mes[3]-'0';

        code1.byte.b5=mes[4]-'0';

        code1.byte.b6=mes[5]-'0';

        code1.byte.b7=mes[6]-'0';

        code1.byte.b8=mes[7]-'0';

        fputc(code1.chhh,fp3);     

    }

    j++;

 }  

 

fcloseall();//закрываем все открытые файлы

 time = clock() - time;

 cout<<"Time = "<<time;

 system("pause");

return 0;

}

 

Для измерения времени  работы алгоритмов запишем системное  время до его выполнения, и вычтем это время из системного времени  после выполнения алгоритма:

 

4. Реализация

 

Рeкурсивная функция создания дерева Хофмана

 

sym *makeTree(sym *psym[],int k)

{

    sym *temp;

    temp=(sym*)malloc(sizeof(sym));

    temp->freq=psym[k-1]->freq+psym[k-2]->freq;

    temp->code[0]=0;

    temp->left=psym[k-1];

    temp->right=psym[k-2];

 

    if(k==2)

        return temp;

    else //внесение в массив в нужное место элемента дерева Хофмана

    {

        for(int i=0;i<k;i++)

            if (temp->freq>=psym[i]->freq)

            {  

                for(int j=k-1;j>i;j--)

                    psym[j]=psym[j-1];                                 

               

                psym[i]=temp;

                break;

            }      

    }

return makeTree(psym,k-1);

}

 

Рекурсивная функция кодирования

void makeCodes(sym *root)

{

    if(root->left)

    {

        strcpy(root->left->code,root->code);

        strcat(root->left->code,"0");

        makeCodes(root->left);

    }

    if(root->right)

    {

        strcpy(root->right->code,root->code);

        strcat(root->right->code,"1");

        makeCodes(root->right);

    }

}

 

 

 

 

 

 

 

5. Тестирование

Проведем тестирование программы:

1. Вносим в input.txt набор символов, который надо закодировать.
2. Начинаем отладку программы.

 

 

 

 

 

 

 

 

 

3. Программа строит дерево Хаффмана

4. В соответствии с деревом кодируется набор символов бинарным кодом Хаффмана.
5. Строим временную диаграмму работы программы

6. Руководство  программиста

6.1. Назначение и условия применения  программ

Программа предназначена  для кодирования набора символов бинарным кодом Хаффмана. Системные требования:

• ОС: Windows XP/Vista/7, с установленным .NET Framework 4
• Оперативная память: 24MB
• Место на жестком диске: 26MB
• Устройство ввода (мышь/клавиатура)

6.2. Характеристика программы

• Программа способна закодировать кодом Хаффмана набор до 1000 символов. Максимальное время работы программы составляет ~27 сек.

 

6.3. Обращение к программе

 

 

7. Выводы

В процессе выполнения курсовой работы был рассмотрен жадный алгоритм, в частности код Хаффмана. Был  реализован сам алгоритм на языке  высокого уровня.

Помимо этого были сопоставлены ожидаемое время работы алгоритма, полученное из его математической модели, с реальным, полученным на практике. Выполнение реализованного в курсовой работе алгоритма заняло в 2 раза больше времени, чем ожидалось.