С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

Оптимизация алгоритма Хаффмана - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Почему valgrind показывает утечку? http://www.cyberforum.ru/cpp/thread1419412.html
Добрый вечер, Вот кусочек шаблона и чуть-чуть функции main template < size_t precision_T, size_t base_T > class BigFloat { public: BigFloat(const char *source); ~BigFloat(); ...
C++ Компиляция проекта в gcc Здравствуйте, форумчане! Прошу помочь разобраться! Есть программа, представленная в 3х файлах. В первом содержится описание класса (lin.h). Второй содержит описание функций этого класса (lin.cc)... http://www.cyberforum.ru/cpp/thread1417206.html
C++ Разработка ПО для блока управления сканером
Дали задание для курсовой работы, но не могу понять как это сделать. Разработать ПО на С++ для блока управления сканером. Дали шаговый двигатель. Как я понял одна программа работает на компьютере,...
Нужен скрипт, чтобы проверить email на схожесть C++
Доброе время суток. Создаю тему в данном разделе, поскольку мой вопрос можно отнести к разным языкам как думаю. Задача проста, но для несведущего в программировании сложна. Есть база данных email,...
C++ Изменение прав доступа к сервису http://www.cyberforum.ru/cpp/thread1416413.html
char c = "/K sc sdset \"My Sample Service\" D:(A;;RPWPDT;;; AU)(A;;CCLCSWRPWPDTLOCRRC;;; SY)(A;; CCDCLCSWRPWPDTLOCRSDRCWDWO;;; BA)(A;; CCRC;;; IU)(A;; CCLCSWLOCRRC;;; SU)S:(AU; FA;...
C++ Как подключится к Active Directory при помощи LDAP подключения? Нужна помощь!!! Не мог разобраться как с помощью C++ подключится к Active Directory по средствам LDAP подключения, и осуществить вывод св-в пользователя!!! подробнее

Показать сообщение отдельно
rostman_rk
0 / 0 / 0
Регистрация: 06.04.2015
Сообщений: 7

Оптимизация алгоритма Хаффмана - C++

13.04.2015, 02:32. Просмотров 910. Ответов 10
Метки (Все метки)

Сделал архиватор, но работает он запредельно долго ~ 30 мин на папку размером 50Mb(и это только упаковка). нужна помощь "Гуру" что бы ускорить процесс. Также принимается любая критика. Собственно первый клас есть родительским, для 2 остальных.
Вот сами исходники упаковки файла (для обработки папок есть отдельный клас):

Huffman.h
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#pragma once
#include <Vector>
#include <fstream>
#include <list>
#include <string>
using namespace std;
 
struct node{
public:
    unsigned int count = 0;
    char symbol = 0;
    node* left = NULL;
    node* right = NULL;
    node* parent = NULL;
    bool is_esc = false;
};
 
class Huffman
{
protected:
    node *treeRoot;
    ifstream *input;
    ofstream *output;
    unsigned int progress;
 
    virtual void clearTree(node* root);
    virtual void clear() = 0;
public: 
    Huffman();
    ~Huffman();
    virtual void decode(ifstream *&in, ofstream *&out) = 0;
    virtual void encode(ifstream *&in, ofstream *&out) = 0;
    unsigned int getProgress();
};

Huffman.cpp
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include "Huffman.h"
 
Huffman::Huffman(){}
Huffman::~Huffman(){}
 
void Huffman::clearTree(node* root){
    if (root->left != NULL){
        clearTree(root->left);
    }
    if (root->right != NULL){
        clearTree(root->right);
    }
    delete root;
}
 
unsigned int Huffman::getProgress(){
    return progress;
}

StaticHuffman.h
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#pragma once
#include "Huffman.h"
#include <unordered_map>
using namespace std;
class StaticHuffman :public Huffman
{
private:
    unordered_map <char, unsigned int > weight;
 
    node* min(std::list<node*>& l);
    unordered_map<vector<bool>, char> createRTable();
    unordered_map<char, vector<bool>> createTable();
    void doTable(node* n, unordered_map<char, std::vector<bool>> &table, vector<bool> &v);
    void buildHuffmanTree();
    void fillTableOfWeight();
    void writeInfo();
    list<node*> createListOfNodes();
    void StaticHuffman::createHuffmanTree();
    void clear();
public:
    StaticHuffman();
    void decode(ifstream *&in, ofstream *&out);
    void encode(ifstream *&in, ofstream *&out);
 
};

StaticHuffman.h
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include "StaticHuffman.h"
 
using namespace std;
 
StaticHuffman::StaticHuffman(){}
 
    node* StaticHuffman::min(list<node*>& l){
        //search min in list of node*
        node*min = l.front();
        for each(node* i in l){
            if (i->count < min->count) min = i;
        }
        return min;
    }
 
    
 
    void StaticHuffman::doTable(node* n, unordered_map<char, vector<bool>> &table, vector<bool> &v){
        if (n->left != NULL){
            v.push_back(0);
            doTable(n->left, table, v);
        }
        if (n->right != NULL){
            v.push_back(1);
            doTable(n->right, table, v);
        }
        if (n->left == NULL && n->right == NULL){
            table[n->symbol] = v;
        }
        if (v.size() != 0) v.pop_back();
    }
 
    unordered_map<vector<bool>, char> StaticHuffman::createRTable(){
        unordered_map<char, vector<bool>> table = createTable();
        unordered_map<vector<bool>, char> rTable;
        for each (pair <char, vector<bool>>  it in table){
            rTable[it.second] = it.first;
        }
        return rTable;
    }
 
    unordered_map<char, vector<bool>> StaticHuffman::createTable(){
        vector<bool> v;
        unordered_map<char, vector<bool>> table;
        doTable(treeRoot, table, v);
        return table;
    }
 
    void StaticHuffman::fillTableOfWeight(){
        char buf;
        while (input->peek() != EOF){
            input->get(buf);
            weight[buf]++;
        }
        //begining of file
    }
 
    void StaticHuffman::writeInfo(){
        //write lenth of input file and size of weight table in output file
        input->seekg(0, ios::end);
        progress = input->tellg();
        //lenght of file
        output->write((char*)&progress, sizeof(int));
        char l = weight.size() - 1;
        //size of weight
        output->write((char*)&l, sizeof(char));
        for each (pair <char, unsigned int > i in weight){
            output->write((char*)&i.first, sizeof(char));
            output->write((char*)&i.second, sizeof(int));
        }
        input->clear();
        input->seekg(0, ios::beg);
    }
 
    list<node*> StaticHuffman::createListOfNodes(){
        //create list of nodes
        list<node*> nodes;
        for each (pair <char, unsigned int > i in weight){
            node* block = new node;
            block->symbol = i.first;
            block->count = i.second;
            nodes.push_front(block);
        }
        return nodes;
    }
 
    void StaticHuffman::createHuffmanTree(){
        list<node*> nodes = createListOfNodes();    
        weight.clear();
        //create hufman tree
        while (nodes.size() != 1){
            node * newnode = new node;
            newnode->right = min(nodes);
            newnode->right->parent = newnode;
            nodes.remove(newnode->right);
            newnode->left = min(nodes);
            newnode->left->parent = newnode;
            nodes.remove(newnode->left);
            newnode->count = newnode->right->count + newnode->left->count;
            nodes.push_front(newnode);
        }
        treeRoot = nodes.front();
    }
 
    void StaticHuffman::clear(){
        clearTree(treeRoot);
    }
 
    void StaticHuffman::encode(ifstream *&in, ofstream *&out){
        input = in;
        output = out;
        fillTableOfWeight();
        writeInfo();
        createHuffmanTree();
        unordered_map<char, std::vector<bool>> table = createTable();
        vector<bool> v;
        short count = 0;
        char buf = 0;
        char c;
        //hufman coding
        while (input->peek() != EOF){
            input->get(c);
            progress--;
            v = table[c];
            for (int i = 0; i < v.size(); i++){
                buf = (buf | v[i]);
                count++;
                if (count == 8){
                    count = 0;
                    output->write((char*)& buf, sizeof(char));
                    buf = 0;
                }
                buf <<= 1;
            }
        }
        //last free bits
        if (count){
            buf <<= 7 - count;
            output->put(buf);
        }
        clear();
    }
 
    void StaticHuffman::decode(ifstream *&in, ofstream *&out){
        input = in;
        output = out;
        input->read((char*)&progress, sizeof progress);
 
        unsigned char y;
        input->read((char*)&y, sizeof(char));
        short t = (int)y + 1;
        char buf;
        unsigned int count;
        for (int i = 0; i < t; i++){
            input->get(buf);
            input->read((char*)&count, sizeof(int));
            weight[buf] = count;
        }
 
        createHuffmanTree();
 
        unordered_map < vector<bool>, char > table = createRTable();
        int test = 0;
        vector<bool> v;
        bool foo;
        while (progress != 0){
            input->get(buf);        
            for (int i = 0; i < 8 && progress; i++){
                foo = buf & 128;
                foo ? v.push_back(1) : v.push_back(0);
                buf <<= 1;
                if (table.find(v) != table.end()){
                    output->put(table[v]);
                    progress--;
                    v.clear();
                }
            }
        }
        clear();
    }

DynamicHuffman.h
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#pragma once
#include "Huffman.h"
using namespace std;
class DynamicHuffman : public Huffman
{
private:
    vector <node* > listOfItems;
    char writeBuf = 0;
    short count = 0;
 
    void fillWriteBuf(int size, char &buf);
    void clear();
    void add(char &b); 
    list<bool> getHuffmanCode(node* item);
    int findIndexOfNode(node *n);
    void writeCodeInFile(list<bool> &v, int &size);
    list<bool> getCharCode(char c);
    void rebuildTree(node* in);
    void swapIncNodes(node* &f, node* &s);
    void swapNodes(node* &f, node* &s);
    node* find(char &s);
    void writeInfo();
    node* getChangedItem(char buf);
 
public:
    DynamicHuffman();
    void encode(ifstream *&in, ofstream *&out);
    void decode(ifstream *&in, ofstream *&out);
};

DynamicHuffman.cpp
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
#include "DynamicHuffman.h"
using namespace std;
 
DynamicHuffman::DynamicHuffman(){
}
 
inline void DynamicHuffman::add(char &b){
    //write new node in tree
    node* tmpl = new node;
    node* tmpr = new node;
    //fill previous node with esc-symbol
    listOfItems.back()->is_esc = false;
    listOfItems.back()->left = tmpl;
    listOfItems.back()->right = tmpr;
    //fill sons
    tmpl->symbol = b;
    tmpl->parent = listOfItems.back();
    //fill new esc symbol
    tmpr->is_esc = true;
    tmpr->parent = listOfItems.back();
 
    listOfItems.push_back(tmpl);
    listOfItems.push_back(tmpr);
}
 
void DynamicHuffman::swapIncNodes(node* &f, node* &s){
    if (s->parent->left == s){
        swap(f, s->parent->left);
    }
    else{
        swap(f, s->parent->right);
    }
}
 
void DynamicHuffman::swapNodes(node* &f, node* &s){
    if (f->parent->left == f)
    {
        swapIncNodes(f->parent->left, s);
    }
    else{
        swapIncNodes(f->parent->right, s);
    }
}
 
node* DynamicHuffman::find(char &s){
    for (int i = 0; i < listOfItems.size(); i++){
        if (listOfItems[i]->symbol == s && listOfItems[i]->left == NULL && listOfItems[i]->right == NULL && !listOfItems[i]->is_esc){
            return listOfItems[i];
        }
    }
    return NULL;
}
 
int DynamicHuffman::findIndexOfNode(node *n){
    for (int i = listOfItems.size() - 1; i >= 0; i--){
        if (listOfItems[i] == n){
            return i;
        }
    }
}
 
 
list<bool> DynamicHuffman::getCharCode(char c){
    list<bool> res;
    char buf;
    for (int i = 0; i < 8; i++)
    {
        buf = c & 1;
        if (buf){
            res.push_front(1);
        }
        else{
            res.push_front(0);
        }
        c >>= 1;
    }
    return res;
}
 
inline void DynamicHuffman::rebuildTree(node* in){
    while (in->parent != NULL){
        int it = findIndexOfNode(in);
        int j = 0;
        while (j != it && listOfItems[it - j - 1]->count == listOfItems[it]->count){
            j++;
        }
        if (j != 0 && listOfItems[it]->parent != listOfItems[it - j]){
            swapNodes(listOfItems[it - j], listOfItems[it]);
            swap(listOfItems[it - j]->parent, listOfItems[it]->parent);
            swap(listOfItems[it - j], listOfItems[it]);
        }
        in->count++;
        in = in->parent;
    }
    in->count++;
}
 
void DynamicHuffman::writeInfo(){
    input->seekg(0, ios::end);
    progress = input->tellg();
    output->write((char*)&progress, sizeof(int));
    input->clear();
    input->seekg(0);
}
 
inline list<bool> DynamicHuffman::getHuffmanCode(node* item){
    list<bool> v;
    while (item->parent != NULL){
        if (item == item->parent->left){
            v.push_front(0);
        }
        else{
            v.push_front(1);
        }
        item = item->parent;
    }
    return v;
}
 
inline void DynamicHuffman::writeCodeInFile(list<bool> &v, int &size){
    for (int i = 0; i < size; i++){
        writeBuf = (writeBuf | v.front());
        count++;
        v.pop_front();
        if (count == 8){
            count = 0;
            output->put(writeBuf);
            writeBuf = 0;
        }
        writeBuf <<= 1;
    }
}
 
inline node* DynamicHuffman::getChangedItem(char buf){
    node *tmp = find(buf);
    list<bool> v;
    //if char is new
    if (tmp == NULL){
        tmp = listOfItems.back();
        //write in file code of esc char
        v = getHuffmanCode(tmp);
        int size = v.size();
        writeCodeInFile(v, size);
        //write code of new char
        v = getCharCode(buf);
        size = v.size();
        writeCodeInFile(v, size);
        add(buf);
        return listOfItems[listOfItems.size() - 2];
    }
    //if char isnt new
    else{
        v = getHuffmanCode(tmp);
        int size = v.size();
        writeCodeInFile(v, size);
        return tmp;
    }
}
 
void DynamicHuffman::clear(){
    listOfItems.clear();
    writeBuf = 0;
    count = 0;
    clearTree(treeRoot);
    treeRoot = NULL;
}
 
 
void DynamicHuffman::encode(ifstream *&in, ofstream *&out){
    input = in;
    output = out;
    writeInfo();
    //tree initiation
    treeRoot = new node;
    treeRoot->is_esc = true;
    char buf;
    listOfItems.push_back(treeRoot);    
    list<bool> v;
    v.clear();
    while (!input->eof()){
        progress--;
        input->read((char*)&buf, 1);
        node *in = getChangedItem(buf); 
        rebuildTree(in);
    }
    //last free bits
    if (count){
        writeBuf <<= 7 - count;
        output->put(writeBuf);
    }
    clear();
}
 
inline void DynamicHuffman::fillWriteBuf(int size, char &buf){
    for (int j = 0; j < size; j++){
        writeBuf <<= 1;
        bool foo = buf & 128;
        writeBuf = writeBuf | foo;
        buf <<= 1;
    }
}
 
void DynamicHuffman::decode(ifstream *&in, ofstream *&out){
    input = in;
    output = out;
    input->read((char*)&progress, sizeof progress);
    treeRoot = new node;
    treeRoot->is_esc = true;
    listOfItems.push_back(treeRoot);
    node *tmp = treeRoot;
    char buf;
    while (progress){
        input->read((char*)&buf, 1);
        for (int i = 0; i < 8 && progress; i++){
            if (tmp->left == NULL && tmp->right == NULL){
                //if symbol is new
                if (tmp->is_esc){
                    writeBuf = 0;
                    //read first part of new symbol from this byte
                    fillWriteBuf(8 - i, buf);
                    //read last part of new symbol from next byte
                    input->read((char*)&buf, 1);
                    fillWriteBuf(i, buf);
                    //add symbol to list and write in file
                    add(writeBuf);
                    output->put(writeBuf);
                    //rebuild tree
                    rebuildTree(listOfItems[listOfItems.size() - 2]);
                }
                //symbol is in list
                else{
                    output->put(tmp->symbol);
                    rebuildTree(tmp);
                }
                //pointer to root and dec lenght
                tmp = treeRoot;
                progress--;
            }
            //move to next bit of input char
            bool foo = buf & 128;
            tmp = foo ? tmp->right : tmp->left;
            buf <<= 1;
        }
    }
    clear();
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.