Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/15: Рейтинг темы: голосов - 15, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 10.06.2019
Сообщений: 6
1

Архиватор на основе алгоритма Хаффмана

22.06.2019, 12:06. Показов 3028. Ответов 6

Добрый день. Написал программу архивирования и разархивирования файлов на основе алгоритма Хаффмана. Вся информация об архивировании (имя файла, его дерево и словарь) храню в начале заархивированного файла. дерево хранится в виде D (спускаемся вниз и влево) и U(поднимаемся вверх и если правого узла нет то вниз вправо) символов.
На маленьких текстовых файлах все работает, но если размер увеличивается, то возникают ошибки. Например файл текстовый размером 6 Кб выбивает ошибку в unpacking.h в 56 строке "System.NullReferenceException: 'Ссылка на объект не указывает на экземпляр объекта.'"

У меня 2 версии:
1) Либо я неправильно считываю все байты из исходного файла и они не пишутся в словарь
2) Либо неправильно строю дерево при распаковке

Заранее спасибо за помощь

Node.h
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#pragma once
#include <iostream>
 
class Node
{
public:
    int a;
    char c;
    Node *left, *right;
 
    Node() { left = right = NULL; }
 
    Node(Node *L, Node *R) {
        left = L;
        right = R;
        a = L->a + R->a;
    }
};
info.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
#pragma once
#include <string>
#include <fstream>
#include <iostream>
 
 
class Info {
private:
    std::string filen;
    std::string packPath;
    std::string tree;
 
public:
    Info(std::string packedFile, std::string filePath) {
        filen = packedFile;
        packPath = filePath;
    }
    void getInfo(std::string treeSize);
    std::string getFileName(std::string s) {
        return s.substr(s.find_last_of("\\") + 1, s.size());
    }
};
 
int digs(int w) {
    int yield = 0;
    while (w > 10) {
        yield++;
        w /= 10;
    }
    return yield + 1;
}
 
void Info::getInfo(std::string treeSize) {
    std::basic_string<char> s_info = "";
    remove((this->packPath + "info.txt").c_str());
    std::ofstream inf((this->packPath + "info.txt").c_str(), std::ios::app | std::ios::out | std::ios::binary);
 
    if (inf.is_open()) {
        std::string name = getFileName(filen);
        s_info.append(name);
        s_info.append("||");
    }
 
    int fileNameSize = s_info.size();
    int am = treeSize.size() + 2;
    int res = fileNameSize + am + 2;
    int fd = digs(res);
 
    if (fd < 5) {
        for (int i = 5 - fd; i > 0; i--) {
            inf << "0";
        }
        //int s = digs(res);
        inf << res;
    }
    inf << "||";
    inf << s_info;
    inf.write(treeSize.data(), am - 2);
    inf << "||";
    inf.close();
}
packing.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
#pragma once
#include "Node.h"
#include <vector>
#include <fstream>
#include <list>
#include <string>
#include <map>
#include "info.h"
 
class Zip {
private:
    std::string filename;
    std::string path;
    std::string zippedFile;
    std::vector<bool> code;
    std::map<char, std::vector<bool> > table;
    std::list<Node*> t;
    std::string vocab = "";
    std::string writeTree = "";
 
public:
    Zip(std::string fileToPack, std::string pathToFile) {
        filename = fileToPack;
        path = pathToFile + "\\";
        zippedFile = path + "zipped.zipp";
    }
 
 
    struct MyCompare {
        bool operator()(Node *l, Node *r) const {
            return l->a < r->a;
        }
    };
    void zipping();
    void BuildTable(Node *root);
    void treeTable(Node *root);
};
 
void Zip::zipping() {
    std::ifstream inpFile(filename.c_str(), std::ios::out | std::ios::binary);
    std::map<char, int> m;
    char b = inpFile.get();
    while (!inpFile.eof())
    {
        m[b]++;
        b = inpFile.get();
    }
    std::map<char, int>::iterator i;
    for (i = m.begin(); i != m.end(); ++i)
    {
        Node *p = new Node();
        p->c = i->first;
        p->a = i->second;
        t.push_back(p);
    }
    //creating a tree
    while (t.size() != 1) {
        t.sort(MyCompare());
        Node *SonL = t.front();
        t.pop_front();
        Node *SonR = t.front();
        t.pop_front();
 
        Node *parent = new Node(SonL, SonR);
        t.push_back(parent);
    }
 
    Node *root = t.front();     //tree root                                             
    BuildTable(root);
    treeTable(root);
    writeTree = vocab + "||" + writeTree;
    inpFile.clear();
    inpFile.seekg(0);
 
    std::ofstream out(zippedFile.c_str(), std::ios::out | std::ios::binary);
    
    Info * inf = new Info(filename, path);
    inf->getInfo(writeTree);
    
    std::ifstream info((path + "info.txt").c_str(), std::ios::out | std::ios::binary);
    char c = info.get();
    while (!info.eof()) {
        out.put(c);// << c;
        c = info.get();
    }
    int count = 0;
    char buf = 0;
 
    while (!inpFile.eof()) {
        c = inpFile.get();
        std::vector<bool> x = table[c];
        for (int n = 0; n < x.size(); n++)
        {
            buf = buf | x[n] << (7 - count);
            count++;
            if (count == 8) {
                count = 0;
                out.put(buf);// << buf;
                buf = 0;
            }
        }
 
    }
    inpFile.close();
    out.close();
}
 
void Zip::treeTable(Node *root) {
    if (root->left != NULL) {
        writeTree.append("D");
        treeTable(root->left);
    }
    if (root->right != NULL) {
        writeTree.append("U");
        treeTable(root->right);
    }
};
 
void Zip::BuildTable(Node *root) {
    if (root->left != NULL) {
        code.push_back(0);
        BuildTable(root->left);
    }
    if (root->right != NULL) {
        code.push_back(1);
        BuildTable(root->right);
    }
    if (root->left == NULL && root->right == NULL) {
        table[root->c] = code;
        vocab += root->c;
    }
    if (!code.empty())
        code.pop_back();
};
unpacking.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
#pragma once
#include "Node.h"
#include <fstream>
#include <vector>
#include <string>
#include <iostream>
 
class Unzip {
private:
    std::string path;
    std::string treeStr = "";
    std::string vocab = "";
public:
    Unzip(std::string pathh) {
        path = pathh + "\\";
    }
    void unzipping(std::string fl);
    void BuildTree(Node *p);
    void Unzip::print_Tree(Node * p, int level);
};
 
void Unzip::unzipping(std::string fl) {
    std::ifstream inp(fl.c_str(), std::ios::out | std::ios::binary);
    char info_block_size[5];
    inp.read(info_block_size, 5);
    int size = atoi(info_block_size);
    char* infoBlock = new char[size];
    inp.read(infoBlock, size);
    std::vector<std::string> tokens;
    char *tok = strtok(infoBlock, "||");
 
    while (tok) {
        if (strlen(tok) == 0) break;
        tokens.push_back(tok);
        tok = strtok(NULL, "||");
    }
 
 
    std::string name = tokens[0];
    vocab = tokens[1];
    treeStr = tokens[2];
 
    std::string fullPath = path + name;
    Node *root = new Node();
 
    BuildTree(root);
 
    std::ofstream unzip(fullPath, std::ios::out | std::ios::binary);
 
    Node *p = root;
    int count = 0;
    char byte = inp.get();
    while (!inp.eof()) {
        bool b = byte & (1 << (7 - count));
        if (b) p = p->right; else p = p->left;
        if (p->left == NULL && p->right == NULL) {
            unzip << p->c;
            p = root;
        }
        count++;
        if (count == 8) {
            count = 0;
            byte = inp.get();
        }
    }
    inp.close();
    unzip.close();
 
    unzip.close();
}
 
void Unzip::BuildTree(Node *p) {
    if (treeStr[0] == 'D') {
        treeStr.erase(0, 1);
        p->left = new Node();
        BuildTree(p->left);
    }
    if (treeStr[0] == 'U' || treeStr.length() == 0) {
        if (p->left == NULL) {
            p->c = vocab[0];
            vocab.erase(0, 1);
        }
        if (p->left != NULL && p->right == NULL) {
            treeStr.erase(0, 1);
            p->right = new Node();
            BuildTree(p->right);
        }
    }
}
 
void Unzip::print_Tree(Node * p, int level)
{
    if (p)
    {
        print_Tree(p->left, level + 1);
        for (int i = 0; i < level; i++) std::cout << "   ";
        std::cout << "Nd" << std::endl;
        print_Tree(p->right, level + 1);
    }
}
main.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include "packing.h"
#include "unpacking.h"
 
int main(int argc, char* argv[]) {
    Zip *zip = new Zip("C:\\test\\3.txt", "C:\\test");
    zip->zipping();
    std::cout << "Zipping Done" << std::endl;
    Unzip *unz = new Unzip("C:\\test\\unpack");
    unz->unzipping("C:\\test\\zipped.zipp");
    std::cout << "Unzipping Done" << std::endl;
    system("Pause");
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.06.2019, 12:06
Ответы с готовыми решениями:

Написать архиватор на основе метода Хаффмана
Вот собственно задача состоит в том что нужно написать программу(архиватор) основываясь на методе...

Архиватор Хаффмана c++
Пишу архиватор на c++ методом Хаффмана. Не могу найти как считывать байты из файла в c++.

Оптимизация алгоритма Хаффмана
Сделал архиватор, но работает он запредельно долго ~ 30 мин на папку размером 50Mb(и это только...

Кодирование алгоритма Хаффмана
Доброго времени суток. У меня есть на руках рабочий код. Вопрос стоит следующим образом: Нужно...

6
6745 / 4540 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
Записей в блоге: 1
23.06.2019, 10:43 2
Цитата Сообщение от AllexKoval Посмотреть сообщение
На маленьких текстовых файлах все работает, но если размер увеличивается, то возникают ошибки. Например файл текстовый размером 6 Кб выбивает ошибку в unpacking.h в 56 строке "System.NullReferenceException: 'Ссылка на объект не указывает на экземпляр объекта.'"
А все файлы создаёшь ты, или берёшь какие-то эталонные?
0
0 / 0 / 0
Регистрация: 10.06.2019
Сообщений: 6
23.06.2019, 13:01  [ТС] 3
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
А все файлы создаёшь ты, или берёшь какие-то эталонные?
Мелкие файлы все созданы мной, побольше я просто нашел .txt файлы на компьютере у себя (логи, например). Но предполагается, что этот архиватор должен работать на любых форматах файлов. Сам то файл открываю я в бинарном виде.
0
6745 / 4540 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
Записей в блоге: 1
23.06.2019, 13:42 4
Цитата Сообщение от AllexKoval Посмотреть сообщение
Мелкие файлы все созданы мной, побольше я просто нашел .txt файлы на компьютере у себя (логи, например). Но предполагается, что этот архиватор должен работать на любых форматах файлов. Сам то файл открываю я в бинарном виде.
Имелась ввиду распаковка

Добавлено через 2 минуты
Но, в любом случае - в функции Unzip::unzipping, в цикле while (!inp.eof()) { не вижу проверки, что p->left ИЛИ p->right равно null
0
0 / 0 / 0
Регистрация: 10.06.2019
Сообщений: 6
23.06.2019, 18:27  [ТС] 5
Имелась ввиду распаковка
Строка 48 unpacking.h - создаётся файл с именем из информации в начале упакованного файла и открывается в бинарном виде.
0
6745 / 4540 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
Записей в блоге: 1
23.06.2019, 18:37 6
Цитата Сообщение от AllexKoval Посмотреть сообщение
if (p->left == NULL && p->right == NULL) {
Может здесь всё-таки нужно добавить проверку p - if (!p || (p->left == NULL && p->right == NULL))?
0
0 / 0 / 0
Регистрация: 10.06.2019
Сообщений: 6
23.06.2019, 22:43  [ТС] 7
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Может здесь всё-таки нужно добавить проверку p - if (!p || (p->left == NULL && p->right == NULL))?
тогда какой символ писать, если "p" не существует? Ведь алгоритм идет по ветвям: если 0 - налево, 1 - направо и в конце концов все заканчивается узлом, в котором есть символ. Получается, что все-таки проблема в построении дерева у меня, либо по какой то причине не записывается символ в конечную ветку.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.06.2019, 22:43

Исходник алгоритма Хаффмана на C
Пожалуйсто дайте исходник алгоритма Хаффмана на C.

Архиватор на основе алгоритма Хаффмана, помогите разобрать код.
Всем привет :) вот в чем собственно вопрос или просьба... мне задана курсовая работа &quot;Архиватор на...

Архиватор , в основе которого будет лежать алгоритм Хаффмана
Итак, приветствую всех=) случилась у меня беда, дали вот такую весёлую&quot; тему для курсача =)(не...

Реализовать свой собственный архиватор по алгоритму хаффмана
Хочу реализовать свой собственный архиватор по алгоритму хаффмана, но есть проблема, допустим я...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru