Файл: Методы кодирования данных (Ключевые понятия кодирования данных).pdf

unsigned char ch;

float freq; //переменная, в которой будет хранится частота встречаемости символа

char code[255];

sym *left;

sym *right;

};

union code

{

unsigned char chhh;//переменная содержащая код для записи в сжатый файл

struct byte

{

unsigned b1:1;

unsigned b2:1;

unsigned b3:1;

unsigned b4:1;

unsigned b5:1;

unsigned b6:1;

unsigned b7:1;

unsigned b8:1;

}byte;

};

sym *makeTree(sym *psym[],int k)//рeкурсивная функция создания дерева Хофмана

{

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 ()

{

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

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

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

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

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

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

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

int fsize2=0;//счётчик количества символов из 0 и 1 в output

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

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

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

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

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

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

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

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

if(fp==NULL)

{

puts("Файл не открыт!");

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]/kk;

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

psym[i]=&simbols[i];

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