Метод Хаффмена

Тема в разделе "C/C++/C#", создана пользователем Rivass, 17 окт 2011.

  1. Rivass

    Rivass Гость

    Может уже кто-то знаком с этим методом кодирования букв. Помогите адаптировать код представленный ниже к заданию (В задании другой язык, но исходный нужен С++) Скрины с заданием ниже кода.

    IMG_0065.jpg
    IMG_0067.jpg
     
  2. Rivass

    Rivass Гость

    Нашел что-то более похожее на правду, но прошу помочь доработать.
    Код (C++):
    #include <iostream>
    #include <string>
    using namespace std;
    const int MAX_SYM = 256;
    #include "class.hpp"

    int main()
    {
    hmn.Init();
    hmn.LoadSymbols();
    hmn.ComputeFreak();
    hmn.OutPut();
    return 0;
    }


    class Haf
    {
    char ArrSym[257];
    int ArrFreak[257];
    int TaleSym;
    char MeetSym[257];
    int MeetFreak[257];
    public:
    string CinStr;
    void Init();
    void OutPut();
    void LoadSymbols();
    void ComputeFreak();
    }hmn;

    void Haf::Init()
    {
    for(int i = 0; i < MAX_SYM;i++)
    ArrFreak[i] = 0;
    TaleSym = 0;
    }

    void Haf::LoadSymbols()
    {
    for(int i = 0; i < MAX_SYM;i++)
    ArrSym[i] = (char)i;
    }

    void Haf::ComputeFreak()
    {
    cout << "Введите строку:";
    getline(cin,CinStr);

    for(int i = 0;i < CinStr.size();i++)
    for(int j = 0;j < MAX_SYM;j++)
    {
    if(CinStr[i] == ArrSym[j])
    {
    ArrFreak[j]++;
    break;
    }
    }

    for(int i = 0;i < MAX_SYM;i++)
    {
    if(ArrFreak[i] > 0)
    {
    MeetSym[TaleSym] = ArrSym[i];
    MeetFreak[TaleSym] = ArrFreak[i];
    TaleSym++;
    }
    }

    for(int i = TaleSym - 1;i >= 0;i--)
    for(int j = 0;j < i;j++)
    {
    if(MeetFreak[j] > MeetFreak[j + 1])
    {
    int Old = MeetFreak[j];
    MeetFreak[j] = MeetFreak[j + 1];
    MeetFreak[j + 1] = Old;

    Old = (int)MeetSym[j];
    MeetSym[j] = MeetSym[j + 1];
    MeetSym[j + 1] = (char)Old;
    }
    }
    }


    void Haf::OutPut()
    {
    for(int i = 0;i < TaleSym;i++)
    cout << MeetSym[i] << " " << MeetFreak[i] << endl;
    }
     
  3. Rivass

    Rivass Гость

    Дело в том что я не могу понять задание из-за того, что написано на мне непонятном языке, если кто сможет переделать хотябы на С может и сам смогу написать...Буду очень признателен.
     
  4. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    ты скажи что именно непонятно, т.к. тут почти на Си написано... и тут не весь код
    Код (Text):
    #include "class.hpp"
    что в этом файле было?
    А еще, тут походу другой алгоритм какой-то реализован. МБ хаффмен, но не тому словесному описанию, которое написано в прикрепленных файлах.
     
  5. Rivass

    Rivass Гость

    Ну я из всего понял что дается строка символов, записывается в массив одномерный, потом каждый символ кодируется именно этим методом хаффмена и на выходе уже будет закодированая строка, но я не очень разобрался в самом методе и не знаю как его реализовать. Что было в файле я к сожалению не знаю) Мне этот код дали просто как пример посмотреть...
     
  6. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    так пойдет? :
    Код (Text):
    #include <iostream>
    #include <string>
    using namespace std;
    const int MAX_SYM = 256;


    char ArrSym[257];
    int ArrFreak[257];
    int TaleSym;
    char MeetSym[257];
    int MeetFreak[257];
    string CinStr;

    void Init();
    void OutPut();
    void LoadSymbols();
    void ComputeFreak();

    int main() {
    Init();
    LoadSymbols();
    ComputeFreak();
    OutPut();
    return 0;
    }


    void Init()
    {
    for(int i = 0; i < MAX_SYM;i++)
    ArrFreak[i] = 0;
    TaleSym = 0;
    }

    void LoadSymbols()
    {
    for(int i = 0; i < MAX_SYM;i++)
    ArrSym[i] = (char)i;
    }

    void ComputeFreak()
    {
    cout << "Введите строку:";
    getline(cin,CinStr);

    for(int i = 0;i < CinStr.size();i++)
    for(int j = 0;j < MAX_SYM;j++)
    {
    if(CinStr[i] == ArrSym[j])
    {
    ArrFreak[j]++;
    break;
    }
    }

    for(int i = 0;i < MAX_SYM;i++)
    {
    if(ArrFreak[i] > 0)
    {
    MeetSym[TaleSym] = ArrSym[i];
    MeetFreak[TaleSym] = ArrFreak[i];
    TaleSym++;
    }
    }

    for(int i = TaleSym - 1;i >= 0;i--)
    for(int j = 0;j < i;j++)
    {
    if(MeetFreak[j] > MeetFreak[j + 1])
    {
    int Old = MeetFreak[j];
    MeetFreak[j] = MeetFreak[j + 1];
    MeetFreak[j + 1] = Old;

    Old = (int)MeetSym[j];
    MeetSym[j] = MeetSym[j + 1];
    MeetSym[j + 1] = (char)Old;
    }
    }
    }


    void OutPut()
    {
    for(int i = 0;i < TaleSym;i++)
    cout << MeetSym[i] << " " << MeetFreak[i] << endl;
    }
    Надеюсь, стало понятней. Правильно или нет это работает, я не проверял, но запускается.
     
  7. Rivass

    Rivass Гость

    Да, спасибо большое, чуток стало понятнее, но конечно все равно тут чего-то не хватает....
     
  8. Rivass

    Rivass Гость

    Теперь у меня есть более подробный и понятный код (даже с комментариями). Конечно он посложнее и со структурами. Работает думаю правильно, но дело в том что тут идет работа с файлами, и причем с конкретными из контекста, прошу немного подкорректировать так, чтобы можно было вводить данные с клавиатуры. Заранее спасибо :(
    Код (C++):
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    struct sym //структуры или записи
    {
    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("777.txt","rb"); //открываем конкретный файл для сжатия
    fp=fopen("123.txt","rb"); //открываем конкретный файл
    fp2=fopen("teemp.txt","wb");//открываем файл для записи бинарного кода
    fp3=fopen("7777.txt","wb");//открываем файл для записи сжатого файла

    int chh; // в эту переменную читается информация из файла
    int  k=0; //счётчик количества различных букв, уникальных символов
    int kk=0; // счётчтк количества всех знаков в файле
    int fsize2=0;//счётчик количества символов из 0 и 1 в промежуточном файле teemp
    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("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]/kk;

    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\tSummir=%f\n",kk,summir);

    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("teemp.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();//закрываем все открытые файлы

    return 0;
    }
     
Загрузка...

Поделиться этой страницей