Оптимизация алгоритма Хаффмана
13.04.2015, 02:32. Показов 2743. Ответов 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
|
(
Сообщение от rostman_rk
