Новичок
Профиль
Группа: Участник
Сообщений: 45
Регистрация: 13.3.2012
Репутация: нет
Всего: нет
|
Было 6 файлов: .txt , .doc , .docx , .bmp , .jpg , .rar Составила таблицу частот встречаемости символов и посчитала энтропию. Затем в отдельной проге(таково условие) ссчитала с файла частоты и закодировала символы методом Хафмена. Проблема вот в чём. Средняя длина не должна быть меньше энтропии. Энтропия- это минимальная величина сжатия, а длина кодов должна быть больше, причём у текстовых не намного, а много на архивных, несжатых графич(bmp).....Так вот на большом текстовом разница аж в 0,2!!! ......хотя относительно друг друга всё правильно: min у текстовых max у архивных(вот только .doc странно себя ведёт- по идее должен обладать стпенью сжатия почти как txt, а средняя длина больше энтропии, хотя даже rar и bmp меньше). В текстовом из 3-х слов всё хорошо. и считает правильно- проверено отладчиком и сравнила вручную..... есть примерные результаты файлов, которые должны получиться. там всё как надо.......но коды символов не совсем совпадают- пару штук меньшей или большей длины, чем надо. (Длина- количество 0 и 1(001- длина 3, 10- длина 2)). Вот код | Код |
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <locale.h>
#include <stdlib.h>
#include <string.h>
struct sym //структуры или записи
{
float ch;
double freq;
char code[255];
sym *left;
sym *right;
};
sym *makeTree(sym *psym[],int k)//рeкурсивная функция создания дерева Хaфмана
{
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 ()
{
setlocale(LC_ALL, "Russian");
int k=0; //счётчик количества различных букв, уникальных символов
sym simbols[256]={0}; //инициализируем массив записей
sym *psym[256]; //инициализируем массив указателей на записи
char IN[100], OUT[100], name[15], siz[15], str[40], *leks;
double mas[2][256]={0}, ent, len=0;
int size, i=0, j=0;
FILE *f, *fp2;
printf("Введите путь к исследуемому файлу:\n");
scanf("%s", IN);
printf("Введите путь к конечному файлу:\n");
scanf("%s", OUT);
fp2=fopen(OUT,"wt");//открываем файл для записи бинарного кода
if((f=fopen(IN, "rb"))==NULL)
{
printf("Файл не может быть открыт.\n");
exit(1);
}
fgets(name, 20, f); //Считываем имя
fgets(siz, 20, f); //Считываем размер
sscanf(siz, "%d", &size); //Конвертируем размер
fgets(str, 40, f); //Считываем пустую строку
int fl=0;
while(fl==0) //Выполнять пока не встретим пустую строку
{
fgets(str, 40, f);
if(strcmp(str, "\r\n")!=0) //Встретили ли пустую строку?
{
k++;
leks=strtok(str," \t"); //Считывание кода
mas[0][i]=atof(leks);
leks=strtok(NULL," \t"); //Считывание вероятности
mas[1][i]=atof(leks);
i++;
}
else
fl=1; //Встретили пустую строку, установить флаг
}
fgets(str, 40, f); //Считываем строку с энтропией
leks=strtok(str, ":");
leks=strtok(NULL, ":"); //Отделяем число энтропии (вторая лексема)
ent=atof(leks);
sym *symbols=(sym*)malloc(k*sizeof(sym));//создание динамического массива структур simbols
sym **psum=(sym**)malloc(k*sizeof(sym*));//создание динамического массива указателей на simbols
// Фиксируем частоты встречаемости
for(int i=0;i<k;i++){
simbols[i].ch=mas[0][i];
simbols[i].freq=mas[1][i];}
for(int i=0;i<k;i++) //в массив указателей заносим адреса записей
psym[i]=&simbols[i];
sym *root=makeTree(psym,k);//вызов функции создания дерева Хафмана
makeCodes(root);//вызов функции получения кода
rewind(f);//возвращаем указатель в файле в начало файла
//записываем полученные в функциях коды в файл
fprintf(fp2,"%s%d\n\n", name, size);
for(i=0;mas[1][i]>0;i++){
if(mas[0][i]<10)
fprintf(fp2,"%.0f \t%s\n",mas[0][i],simbols[i].code);
if(mas[0][i]>10 && mas[0][i]<100)
fprintf(fp2,"%.0f \t%s\n",mas[0][i],simbols[i].code);
if(mas[0][i]>100)
fprintf(fp2,"%.0f\t%s\n",mas[0][i],simbols[i].code);}
//fputs(simbols[i].code,fp2);
for(int i=0;i<k;i++)
len+= ((int)strlen(simbols[i].code))*simbols[i].freq;
fprintf(fp2,"\r\n%s%.*f", "Средняя длина кода сжатия: ", 10, len);
fprintf(fp2,"\r\n%s%.*f", " Энтропия: ", 10, ent);
fcloseall();//закрываем все открытые файлы
return 0;
getch();
}
|
Среда: VS2010 В прикреплённом файле правильные и неправильные результаты+ в правильных код на паскале, с помощью которого знаю правильные. Но в паскале я не бум-бум, просто попросила обработать готовый код, а то у меня даже инсталятора его нет. Это сообщение отредактировал(а) Асоишница - 27.2.2013, 22:37
Присоединённый файл ( Кол-во скачиваний: 1 )
файлы.rar 35,85 Kb |
Код Хафмена. Не могу найти ошибку, энтропия, средняя длина кода сжатия 
Загрузка ...
