Шустрый
Профиль
Группа: Участник
Сообщений: 51
Регистрация: 15.6.2009
Где: Donetsk
Репутация: нет
Всего: нет
|
Я уже долго работаю с кодировкой методом Хаффмана...сделано много(для меня), и вот: он уже строит дерево, архивирует файл, но разархивировать не получается!!! Почему не пойму(как всегда =) ). Алгоритм архивации таков: подсчитываем скок и каких символов в файле, строим дерево, записываем инфу(не много) для восстановления и потом кодируем в файл. Алгоритм разархивирования: из информации для разархивирования строим дерево, преобразуем в коды(0 и 1), и выводим в файл.(Вот здесь и проблема работы! =( ) | Код |
#include <iostream>
#include <fstream>
#include <string.h>
#include <windows.h>
#include <algorithm>
#include <vector>
using namespace std;
class Huffman
{
private:
char *key; //значение ветки
unsigned long int **mas; //храним таблицу символов
char *file; //файл
//тут добавить map<int, char>
unsigned long int all, plus; //кол-во всех элементов(в файле), и положительных(для таблицы)
Huffman *parent, *left, *right; //указатели на ближние значения
public:
Huffman(); //конструктор
~Huffman(); //деструктор
void Archive(char *path); //архивировать файл
void Extract(char *path); //разархивировать файл
void SetFile(char *f); //установить файл для работы(не нужно, если сделать пред. ф-ции)
void Write(); //считываем символ, сравниваем с базой, добаляем в масив дял дальнейшего...
void/*long int **/Read(); //
Huffman *GoUp(); //переход к корню(самый верх)
unsigned long int GetPlus(); //кол-во положительных элементов
unsigned long int * SearchMin(); //поиск двух наименьших в файле
char GetFromMas(unsigned long int k); //получить элемент из таблицы(символ)
void PutBit(unsigned long int &This, unsigned long int &count, int bit, ofstream &out); //шифруем
int Getbit(unsigned long int &This, unsigned long int &count, ifstream &in); //дешифруем
Huffman *CreateTree(char k1, char k2); //задаём "корень" дерева(можно будет изменить и задавать ток правый элемент...а дальше след. ф-цией)
Huffman *AddParent(char k); //задаём следующего предка
Huffman *AddLeaf(char k); //задаём значение в правой ветке
Huffman *CreateTabl(); //вывод всего дерева
void Print(); //вывод тек. значения
};
void main()
{
setlocale(LC_CTYPE, "Russian");
Huffman *tree = new Huffman();
char path[100]={0};
cout<<"Please input file: ";
cin>>path;
tree -> SetFile(path);
/*tree -> SearchMin();
tree = tree -> CreateTree(tree -> GetFromMas(0), tree -> GetFromMas(1));
cout << "\tStarting...\n";
int l = tree -> GetPlus();
for(unsigned long int i = 2; i < l; ++i)
{
char k = tree -> GetFromMas(i);
tree = tree -> AddParent(k);
}
tree -> CreateTabl();
unsigned long int i = 0;
tree -> Read();*/
tree -> Write();
cout << "\n\tFinish!!!\n\a";
}
void Huffman :: Read()
{
GoUp();
Huffman *obj = this;
unsigned long int k = 0, i = 1;
unsigned long int This = 0, count = 0, bit = 0;
char ch[2];
vector<int> my_vector;
ifstream in; in.open(file);
strcat(file, ".huf");
ofstream out; out.open(file, ios::binary);
//теги для разкодирования...
while(obj -> left)
obj = obj -> left;
out << plus << " ";
out << ((int)*(obj -> key)) << " ";
obj = obj -> parent;
out << ((int)*(obj -> right -> key));
obj = obj -> parent;
while(obj)
{
out << " " << ((int)*(obj -> right -> key));
obj = obj -> parent;
}
out << " ";
ch[1] = '\0';
for(i; i < all-1; ++i)
{
in.get(ch[0]);
Huffman *obj = this;
while(obj -> left != NULL)
{
if(strcmp(obj -> right -> key, &ch[0]) == 0)
{
my_vector.push_back(1);
break;
}
obj = obj -> left;
my_vector.push_back(0);
}
GoUp();
}
in.close();
cout << all << "\n";
k = my_vector.size();
ofstream out2("e:\\1.txt");
for(i = 0; i < 8*(k/8); ++i)
{
PutBit(This, count, my_vector[i], out);
out2 << my_vector[i];
}
for(i; i < k; ++i)
{
This = This | (my_vector[i] << count);
++count;
if(i == k-1)
{
out << (char)This;
count = 0;
This = 0;
}
}
out.close();
my_vector.clear();
}
void Huffman :: PutBit(unsigned long int &This, unsigned long int &count, int bit, ofstream &out)
{
This = This | (bit << count);
++count;
if(count == 8)
{
out << (char)This;
count = 0;
This = 0;
}
}
void Huffman :: Write()
{
Huffman *obj = this;
unsigned long int i, This = 0, count = 8;
char *f = new char;
vector<int> my_vector;
ifstream in; in.open(file);
strcat(file, ".uhuf");
ofstream out; out.open(file);
unsigned long int s, k;
in >> s;
for(i = 0; i < s; ++i)
{
in >> k;
mas[1][i] = k;
}
for(i = 0; i < s; ++i)
cout << (char)mas[1][i] << "\n";
obj -> mas = mas;
obj = obj -> CreateTree(obj -> GetFromMas(0), obj -> GetFromMas(1));
for(int j = 2; j < s; ++j)
{
char k = obj -> GetFromMas(j);
obj = obj -> AddParent(k);
}
system("cls");
obj -> CreateTabl();
ofstream out2("E:\\2.txt");
while(in)
{
my_vector.push_back(Getbit(This, count, in));
out2 << my_vector.back();
}
out2.close();
This = 0;
count = 0;
s = my_vector.size();
i = 8;
while(i < s)
{
obj = obj -> GoUp();
while(true)
{
if(i >= s)
break;
if(my_vector[i] == 0)
{
if(obj -> left)
obj = obj -> left;
else
obj = obj -> GoUp();
++i;
}
else
{
if(obj -> right)
f = obj -> right -> key;
else
f = key;
++i;
break;
}
}
out.write(f, strlen(f));
}
in.close();
out.close();
my_vector.clear();
}
int Huffman :: Getbit(unsigned long int &This, unsigned long int &count, ifstream &in)
{
char k;
int bit;
if(count == 8)
{
in.get(k);
This = k;
count = 0;
}
bit = (This >> count) & 1;
++count;
return bit;
}
unsigned long int *Huffman :: SearchMin()
{
/*
сделать map<int, char>... в котором буду хранить инфу о символах...
сделать сортировку так, чтобы в поле int сортировались(по убыванию???) все, кроме нулей(и отр, если баги)
ДОБАВИТЬ map в класс...как член!!!
*/
unsigned int j, k;
unsigned long int ch;
ifstream in(file);
while(in)
{
char k; in.get(k); j = k;
mas[0][j]++;
all++;
}
in.close();
for(int i = 0; i < 64; ++i)
{
for(int j = 0; j < 254; ++j)
{
if((mas[0][j] > mas[0][j+1] && mas[0][j+1] > 0) || (mas[0][j] < mas[0][j+1] && mas[0][j] == 0))
{
k = mas[0][j];
mas[0][j] = mas[0][j+1];
mas[0][j+1] = k;
ch = mas[1][j];
mas[1][j] = mas[1][j+1];
mas[1][j+1] = ch;
}
}
}
for(int i=0; i<255; ++i)
{
if(mas[0][i] != 0)
plus++;
cout << mas[0][i] << " " << (char)mas[1][i] << "\n";
}
plus++;
for(int j = 0; j < 20; ++j)
{
for(int i=0; i<plus; ++i)
{
if((mas[0][i] > mas[0][i+1] && mas[0][i+1] > 0)/* || (mas[0][i] < mas[0][i+1] && mas[0][i] == 0)*/)
{
k = mas[0][i];
mas[0][i] = mas[0][i+1];
mas[0][i+1] = k;
ch = mas[1][i];
mas[1][i] = mas[1][i+1];
mas[1][i+1] = ch;
}
}
}
system("cls");
for(int i = 0; i < plus; ++i)
{
cout << mas[0][i] << " " << (char)mas[1][i] << "\n";
}
return NULL;
}
Huffman *Huffman :: AddParent(char k)
{
Huffman *buf = new Huffman;
parent = buf;
delete[] buf -> mas[0];
delete[] buf -> mas[1];
buf -> mas = mas;
buf -> all = all;
buf -> plus = plus;
buf -> file = file;
buf -> left = this;
buf -> right = new Huffman;
buf -> right = buf -> right -> AddLeaf(k);
return buf;
}
Huffman *Huffman :: AddLeaf(char k)
{
strcpy(key, &k);
return this;
}
Huffman *Huffman :: CreateTree(char k1, char k2)
{
parent = NULL;
left = new Huffman;
strcpy(left -> key, &k1);
left -> parent = this;
right = new Huffman;
strcpy(right -> key, &k2);
right -> parent = this;
char *c = new char;
strcpy(c, &k1);
strcat(c, &k2);
key = c;
return this;
}
Huffman :: Huffman()
{
all = 0;
plus = 0;
key = new char;
file = NULL;
mas = new unsigned long int*[2];
mas[0] = new unsigned long int[255];
mas[1] = new unsigned long int[255];
for(int i = 0; i < 255; ++i)
{
mas[0][i] = 0;
mas[1][i] = i;
}
parent = NULL;
left = NULL;
right = NULL;
}
Huffman :: ~Huffman()
{
delete parent, right, left, key;
}
void Huffman :: SetFile(char *f)
{
file = f;
}
Huffman *Huffman :: GoUp()
{
Huffman *obj = this;
while(obj -> parent)
obj = obj -> parent;
return obj;
}
char Huffman :: GetFromMas(unsigned long int k)
{
return ((char)mas[1][k]);
}
unsigned long int Huffman :: GetPlus()
{
return plus;
}
Huffman *Huffman :: CreateTabl()
{
Huffman *obj = this;
while(obj -> left)
{
obj -> right -> Print();
cout << "\n";
obj = obj -> left;
}
obj -> Print();
obj = GoUp();
return obj;
}
void Huffman :: Print()
{
cout << key;
}
void Huffman :: Archive(char *path)
{
Huffman *tree = new Huffman;
tree -> SetFile(path);
tree -> SearchMin();
tree = tree -> CreateTree(tree -> GetFromMas(0), tree -> GetFromMas(1));
int l = tree -> GetPlus();
for(unsigned long int i = 2; i < l; ++i)
{
char k = tree -> GetFromMas(i);
tree = tree -> AddParent(k);
}
tree -> Read();
}
void Huffman :: Extract(char *path)
{
Huffman *obj = this;
unsigned long int i, This = 0, count = 8;
char *f = new char;
vector<int> my_vector;
ifstream in; in.open(path, ios_base::binary);
strcat(path, ".uhuf");
ofstream out; out.open(path, ios::binary);
unsigned long int s; in >> s; in.read(f, s+1); cout << f;
for(i = 5; i < s-5; ++i)
{
mas[1][i-5] = f[i];
}
s -= 10;
for(i = 0; i < s; ++i)
cout << (char)mas[1][i] << "\n";
obj -> mas = mas;
obj = obj -> CreateTree(obj -> GetFromMas(0), obj -> GetFromMas(1));
for(int j = 2; j < s; ++j)
{
char k = obj -> GetFromMas(j);
obj = obj -> AddParent(k);
}
system("cls");
obj -> CreateTabl();
while(in)
{
my_vector.push_back(Getbit(This, count, in));
}
This = 0;
count = 0;
s = my_vector.size();
i = 0;
while(i < s)
{
obj = obj -> GoUp();
while(true)
{
if(i >= s)
break;
if(my_vector[i] == 0)
{
if(obj -> left)
obj = obj -> left;
else
obj = obj -> GoUp();
++i;
}
else
{
if(obj -> right)
f = obj -> right -> key;
else
f = key;
++i;
break;
}
}
out.write(f, strlen(f));
}
in.close();
out.close();
my_vector.clear();
}
|
примечание: функция Read архивирует файл, разархивирует Write...во всяком случае должна... Спасибо за помощь. |
Хаффман и не правильное разархивирование, выводит лишние/не подходящие символы 
Загрузка ...
