VPF::Проблемы с алгоритмом Хаффмана

Servantes

Дата 21.5.2009, 21:19 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 21.5.2009

Репутация: нет
Всего: нет

Ве4ер добрый всем. Я реализую программу на Visual Studio - сжатие файлов по лагоритму Хаффмана. Программу написать было не сложно. Но проблемы оказались при проверке. Когда входной файл относительно(по меркам байт) большой - обходы дерева и построение дерева оказываются процессами скажем прямо не быстрыми. Я завел эту тему ,потому что хо4у ,чтобы программа работала быстрее. Ниже приведен код. Надеюсь на вашу помощь.

Код



#include <stdio.h>
#include <string>
#include <string.h>
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <vector>
using namespace std;

void BuildTree(vector <struct table> TBL);
void AroundTree(struct tree *A);
void ReadFile(FILE *fin1);
void WriteFile();
void DReadFile(FILE *df);

struct tree {
        struct tree *left;
        struct tree *right;
        char Symbol;
        int mass;
            };

struct table {
        string S;
        int mass;
        struct tree *adress;
            };

struct code {
        string S;
        char ch;
            };


vector <struct code> TCD;
vector <struct table> ITBL,WTBL,DTBL;
struct table Temp;
struct code CTemp;
char c,cTemp;
int  N=0,K=0,K1=0,i=0,j=0,min1,min2,Ktemp=-1,K1temp=-1,Rej=1;
bool flag;
FILE *fin;
struct tree *Ttemp, *TMain;
string InputS, OutputS, S1, SOUT,TempS1;
long Bits;
FILE *f;
char *pm;
//------------------------------------------
void ReadFile(FILE *fin1){
    cout<<"Reading file"<<endl;
    long nFileLen = 0, Now = 0;
    if (fin1)
    {
       fseek(fin1, 0, SEEK_END);
       nFileLen = ftell(fin1);
       fseek(fin1, 0, SEEK_SET);
    }
    pm = (char *)malloc((nFileLen+1)*sizeof(char));
    fread(pm,nFileLen,1,fin1); 
    pm[nFileLen]=0;
        while (Now < nFileLen)
        {
            c = pm[Now];
            InputS.push_back(c);    
            N = ITBL.size();
            flag = 0;
            for (int i=0; i<N; i++)
            {
                if (ITBL[i].S.size() != 0)
                if ((ITBL[i].S.at(0) == c))
                {
                    ITBL[i].mass++;
                    flag = 1;
                    i = N;
                };
            }
            if (flag == 0) 
            {
                Temp.S.push_back(c);
                Temp.mass = 1;
                Temp.adress = NULL;
                ITBL.push_back(Temp);
                Temp.S.erase(Temp.S.begin());
            }
            Now++;
        }
        WTBL = ITBL;
        free((char *) pm);
    cout<<"Reading complete"<<endl;
};
void BuildTree(vector <struct table> TBL){
    
    while (TBL.size() > 1)
        {
            K=0;
            K1=-1;
            min1 = TBL[0].mass;
            for (int i=0;i<TBL.size();i++)
            {
                if (TBL[i].mass < min1) 
                {
                    min1= TBL[i].mass;
                    K = i;
                }
            }
            if (K == TBL.size()-1)
            {
                min2 = TBL[TBL.size()-2].mass;
            } else min2 = TBL[TBL.size()-1].mass;
            for (int i=TBL.size()-1;i>=0;i--)
            {
                if ((TBL[i].mass <= min2) && (i != K))
                {
                    min2= TBL[i].mass;
                    K1 = i;
                }
            }
//            if ((K != KTemp) || (K != K1Temp))
            Ttemp = (struct tree *) malloc (sizeof(struct tree));
            Ttemp->left = NULL;
            Ttemp->right = NULL;
            Ttemp->Symbol = 0;
            Ttemp->left = (struct tree *) malloc (sizeof(struct tree));
            Ttemp->right = (struct tree *) malloc (sizeof(struct tree));
            Ttemp->left->Symbol = 0;
            Ttemp->right->Symbol = 0;
            if (TBL[K].S.size() != 0)
            {
                c = TBL[K].S.at(0);
                Ttemp->left->Symbol = c;
                Ttemp->left->left = NULL;
                Ttemp->left->right = NULL;
            } else
            {
                Ttemp->left = TBL[K].adress;
            };
            if (TBL[K1].S.size() != 0)
            {
                c = TBL[K1].S.at(0);
                Ttemp->right->Symbol = c;
                Ttemp->right->left = NULL;
                Ttemp->right->right = NULL;
            } else
            {    
                Ttemp->right = TBL[K1].adress;
            };
            Ttemp->left->mass = TBL[K].mass;
            Ttemp->right->mass = TBL[K1].mass;
            Ttemp->mass = TBL[K].mass + TBL[K1].mass;
            if (K > K1)
            {
            TBL.erase(TBL.begin() + K);
            TBL.erase(TBL.begin() + K1);
            } else
            {
            TBL.erase(TBL.begin() + K1);
            TBL.erase(TBL.begin() + K);
            }
            Temp.mass = Ttemp->mass;
            Temp.adress = Ttemp;
            TBL.push_back(Temp);
            Temp.adress = NULL;
            Temp.mass = 0;
        }
    TMain = TBL[0].adress;
};

void WriteFile(){
    f = fopen("C://1.htxt", "wb");

    Bits = OutputS.size();
    fwrite((long *) &Bits, 4, 1, f);
    unsigned char d = 0;
    while (OutputS.size()>0)
    {
        d = 0;
        if (OutputS.size()  > 7)
        {
            for (int i =0; i<8; i++)
            {    
                d<<=1;
                if (OutputS.at(0) == '0')
                d |= 0; else d|= 1;
                OutputS.erase(OutputS.begin());    
            }
            fwrite((unsigned char *) &d, 1, 1, f);
        } else
        {
            N = OutputS.size();
            for (int i =0; i<N; i++)
            {
                d<<=1;
                if (OutputS.at(0) == '0')
                d |= 0; else d|= 1;
                OutputS.erase(OutputS.begin());
            }    
            fwrite((unsigned char *) &d, 1, 1, f);
        }
    }
    short num;
    d = 0;
    for (int i=0;i<WTBL.size();i++)
    {
        d = WTBL[i].S.at(0);
        fwrite((unsigned char *) &d, 1, 1, f);
        num = WTBL[i].mass;
        fwrite((short *) &num, 2, 1, f);
    }
    fclose(f);
}
void AroundTree( struct tree *A){

    
    if ((A->left == NULL))
    {
        CTemp.ch = A->Symbol;
        CTemp.S = S1;
        TCD.push_back(CTemp);
    } else
    {
    if (A->left != NULL)
    {
        S1.push_back('1');
        AroundTree(A->left);
        S1.erase(S1.begin()+S1.size()-1);
    }
    if (A->right != NULL)
    {
        S1.push_back('0');
        AroundTree(A->right);
        S1.erase(S1.begin()+S1.size()-1);
    }}
};

void DReadFile(FILE *df)
{
    fread((long *) &Bits, 4, 1, df);
    long byte;
    long q = 0;
    if (Bits %8 !=0)
        byte = Bits/8 + 1;
    else 
        byte = Bits/8;
    
    for (int i=0;i<byte;i++)
    {
        c = 0;
        fread((unsigned char *) &c, 1, 1, df);
        if (i == byte-1)
        for (int j=0;j<(8-byte*8+Bits);j++)
            {
                if (c & 1) 
                    SOUT.insert(SOUT.begin()+q,'1');                    
                else 
                    SOUT.insert(SOUT.begin()+q,'0');
                c>>=1;
            }
        else
        for (int j=0;j<8;j++)
            {
                if (c & 1) 
                    SOUT.insert(SOUT.begin()+q,'1');                    
                else 
                    SOUT.insert(SOUT.begin()+q,'0');
                c>>=1;
            }
        q+=8;
    }
    short temps=0;
    while ((c= fgetc(df)) != EOF)
    {
        Temp.S.push_back(c);
        fread((short *) &temps, 2, 1, df);
        Temp.mass =temps;
        DTBL.push_back(Temp);
        Temp.S.erase(Temp.S.begin());
    }

    fclose(df);

}
//------------------------------------------
void main(){
    cout<<"Rejim: 1 - coding file, 2 - decoding file"<<endl;
    Rej = 0;
    cin>>Rej;
    if ((Rej != 1) && (Rej != 2))
        cout<<"Wrong parametr"<<endl;
    else
    if (Rej == 1)
    {
    if ((fin  = fopen( "C://1.txt", "rb" )) == NULL )
        cout<<"Fail not found"<<endl;
    else
    {
    ReadFile(fin);
    if (ITBL.size() > 1)
    {
        BuildTree(ITBL); 
        AroundTree(TMain);
        int l = InputS.size();
        int l1 =0;
        while (l1<l)
        {
            for (int i=0; i< TCD.size(); i++)
            {
                if (TCD[i].ch == InputS[l1])
                {
                    OutputS=OutputS + TCD[i].S;
                    i = TCD.size();
                    l1++;
                }
            }
        }
        WriteFile();
 
    cout<<"Vse prosholo horosho, Fail zakodirovan"<<endl;
    }
    else 
        cout<<"Empty file"<<endl;
    }
    } else
    {
    if ((f = fopen( "C://1.htxt", "rb" )) == NULL )
        cout<<"Fail not found"<<endl;
    else
    {
    DReadFile(f);
    int i = 0;
    
    BuildTree(DTBL);
    Ttemp = TMain;
    f = fopen( "C://1.dtxt", "wb" );
    for (int i=0;i<SOUT.size();i++)
    {
        if (SOUT.at(i) == '1')
        { 
            Ttemp = Ttemp->left;
        } 
        else
        {
            Ttemp = Ttemp->right;             
        };
        if (Ttemp->Symbol != 0)
        {
            fwrite((char *) &Ttemp->Symbol,1,1,f);
            Ttemp = TMain;
        }
    
    }    
    fclose(f);
    }
    };
 getchar();
}

andrew_121

Дата 22.5.2009, 10:02 (ссылка)

(нет голосов)

Загрузка ...

Кодофей

Профиль
Группа: Завсегдатай
Сообщений: 3448
Регистрация: 3.1.2008

Репутация: 6
Всего: 33

Цитата(Servantes @ 21.5.2009, 21:19

)

vector <struct code> TCD;
vector <struct table> ITBL,WTBL,DTBL;

В векторе лучше хранить указатели.

Цитата(Servantes @ 21.5.2009, 21:19

)

vector <struct code> TCD;
vector <struct table> ITBL,WTBL,DTBL;
struct table Temp;
struct code CTemp;
char c,cTemp;
int N=0,K=0,K1=0,i=0,j=0,min1,min2,Ktemp=-1,K1temp=-1,Rej=1;
bool flag;
FILE *fin;
struct tree *Ttemp, *TMain;
string InputS, OutputS, S1, SOUT,TempS1;
long Bits;
FILE *f;
char *pm;

Присутствие глобальных переменных говорит о не правильном проектировании.

Если в коде используешь векторы, значит это С++. Почему тогда используешь malloc() ?

P.S.
Половину кода нужно переписать. Качество ужасное.

--------------------

Удалил аккаунт. Прощайте!

xvr

Дата 22.5.2009, 10:39 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

ITBL организованна неправильно - нужен массив на 256 элементов и при заполнении массива не нужно искать в нем элемент циклом, адресуйся прямо по индексу.

Собственно алгоритм формирования кода Хафмана вообще понять невозможно, названия рабочих переменных TCD, ITBL,WTBL,DTBL,Temp,CTemp ясности не прибавляет (не говоря уже о полном отсутствии каких либо комментариев)

vinick

Дата 22.5.2009, 11:59 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 285
Регистрация: 9.6.2005

Репутация: 3
Всего: 22

Код


  while (TBL.size() > 1)
        {
      //.........
            if (K > K1)
            {
            TBL.erase(TBL.begin() + K);
            TBL.erase(TBL.begin() + K1);
            } else
            {
            TBL.erase(TBL.begin() + K1);
            TBL.erase(TBL.begin() + K);
            }
//............
            TBL.push_back(Temp);
        }

удалять что-то из вектора в цикле - плохая идея, он для этого не приспособлен.

Код


    if (TBL[K].S.size() != 0)
            {
                c = TBL[K].S.at(0);

Использование at() вместе с проверкой size здесь и в других местах бессмысленно. Лучше что-то одно.

Код


void BuildTree(vector <struct table> TBL){

Вектора используются только по 1 разу, так что тут можно передавать по ссылке.

Servantes

Дата 22.5.2009, 17:03 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 21.5.2009

Репутация: нет
Всего: нет

Я не силен в C++. У меня возник вопрос во время удаления 4уши всякой мною же написанной - я читаю файл разом. При чтении ехе этот способ неприемлим ибо нулевых байтов там хоть отбавляй. Как быть??? Вернуться к побайтовому чтению?

andrew_121

Дата 22.5.2009, 19:04 (ссылка)

(нет голосов)

Загрузка ...

Кодофей

Профиль
Группа: Завсегдатай
Сообщений: 3448
Регистрация: 3.1.2008

Репутация: 6
Всего: 33

Servantes, Может взять готовый код?

--------------------

Удалил аккаунт. Прощайте!

Servantes

Дата 22.5.2009, 20:05 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 21.5.2009

Репутация: нет
Всего: нет

Я бы с удовольствием, но в интернете коды сложные

xvr

Дата 22.5.2009, 21:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

Цитата(Servantes @ 22.5.2009, 17:03)

Твой код замечательно будет читать любые символы, в том числе и нулевые

Цитата

Вернуться к побайтовому чтению?

Лучше к мэпированию файла в память.

Цитата

Servantes, Может взять готовый код?

Я бы с удовольствием, но в интернете коды сложные

По сравнению с твоим они просто кристально прозрачные, к тому же они работают smile

Кроме того, лучше сначала разобраться с основами языка, и уж тем более с основами stl, что бы не лепить плохо приспособленные контейнеры к месту и не к месту.
Изложи алгоритм, простым (можно русским) языком, потом можно будет выбрать наиболее подходящие структуры данных (и stl контейнеры в том числе), и только потом можно будет начинать кодировать алгоритм.
Ты пока пытаешься пройти этот путь наоборот - с конца к началу smile

Servantes

Дата 22.5.2009, 22:30 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 21.5.2009

Репутация: нет
Всего: нет

Для начала я считываю файл. И тут изза не знания языка я не могу рационально считать файл - только по байтам, так как при считывынии сразу в char целиком могут встретиться нулевые байты - а они для чара именуют конец строки. Считывая каждый символ, я заношу его в массив из 256 элементов в ячейку с номером кода символа(здесь он не написан, но я переписал). После этого я из таблицы частот которую мы построили начинаю выбирать два самых редких элемента и из них формировать узел, удаляя элементы из таблицы и добавляя в конец сам узел(структура таблицы - символ, число повторении, адрес для узла). И так пока не останется один элемент. Следующий этап - обхожу построенное дерево сначало слева потом справа пока не встре4у символ(изза нулевого символа я сделал проверку на дерево->left == NULL). И вормирую новую таблицу символов и кодов им соответствующих. Затем собираю из кодов выходную строку и блоками по 8 элементов загоняю их в элемент типа char поразрядными сдвигами. в кодированном файле хранится в первых 4-х байтах число кодированных бит(т.к. у нас их может быть и не кратно 8), потом сама строка и потом таблица с кодами- символ и заним в двух байтах число посторений во входном файле. По этой таблице при декодировании строю дерево и восстанавливаю исходный файл. Вот алгоритм действий моих.

xvr

Дата 25.5.2009, 16:10 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

Цитата(Servantes @ 22.5.2009, 22:30)

Для начала я считываю файл. И тут изза не знания языка я не могу рационально считать файл - только по байтам,

Ты его в самом первом твоем посте вполне нормально считал целиком

Цитата

так как при считывынии сразу в char целиком могут встретиться нулевые байты - а они для чара именуют конец строки.

Они для С строк именуют конец строки, но не для массивов с явно заданной длинной.

Цитата

Считывая каждый символ, я заношу его в массив из 256 элементов в ячейку с номером кода символа(здесь он не написан, но я переписал).

Угу

Цитата

После этого я из таблицы частот которую мы построили начинаю выбирать два самых редких элемента и из них формировать узел, удаляя элементы из таблицы и добавляя в конец сам узел(структура таблицы - символ, число повторении, адрес для узла).

Эдесь напрашивается map с ключем - частотой конкретного символа.

Цитата

И так пока не останется один элемент. Следующий этап - обхожу построенное дерево сначало слева потом справа пока не встре4у символ

Не понял, какой символ? Здесь напрашивается сделать обход дерева (однократный) и построить массив выходных кодов (в виде битовых строк) для каждого возможного байта

Цитата

И вормирую новую таблицу символов и кодов им соответствующих.

Это оно, я правильно понял?

Цитата

Затем собираю из кодов выходную строку и блоками по 8 элементов загоняю их в элемент типа char поразрядными сдвигами.

Почему по 8? Количество элементов на байт выхода будет переменным (возможно даже дробным)

Цитата

в кодированном файле хранится в первых 4-х байтах число кодированных бит(т.к. у нас их может быть и не кратно 8), потом сама строка и потом таблица с кодами- символ и заним в двух байтах число посторений во входном файле.

Кто такие 'посторений во входном файле'?
Порядок полей несколько неочевиден, я бы сохранил так -

Таблица частот входых данных (по ней однозначно восстанавливается дерево)
Количество битов данных в последнем байте (из п3)
Закодированные Хафманом данные (битовый поток)

Servantes

Дата 25.5.2009, 19:21 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 21.5.2009

Репутация: нет
Всего: нет

Сори за очепятки) - повторений.

Цитата

Почему по 8? Количество элементов на байт выхода будет переменным (возможно даже дробным)

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

xvr

Дата 25.5.2009, 21:50 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

Цитата(Servantes @ 25.5.2009, 19:21)

Сори за очепятки) - повторений.

Цитата

Почему по 8? Количество элементов на байт выхода будет переменным (возможно даже дробным)

Посмотрел еще раз исходники - понял. У вас выходной поток накапливается в строке в виде символов '1' и '0'. Наверное сделать медленнее можно, но очень сложно smile

Несколько советов:

Не упоминай 'new' или 'malloc' всуе! У вас нет ни одной структуры данных, которые нельзя было бы уместить в статически заданные массивы (даже дерево)
Не надо использовать std::string для накопления бинарных данных (да еще в виде символьной строки битов). Это КРАЙНЕ неэффективно. Нужно создать специальный класс, для накопления битов. Класс должен поддерживать как накопление их в собственной памяти, так и сброс на файл (поток - ostream)
std::vector здесь тоже не нужен (см предыдущий пункт)
Дерево кодов можно сохранить в выходном файле в виде закодированного порядка обхода дерева (1 бит на не терминальную вершину, всего 255 битов/ 32 байта) и содержимого терминальных вершин (256 байтов)
Начать нужно с написания класса битовых строк - все будет крутится вокруг него

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »