Сжатие методом Хаффмана

@no swear · Регистрация: 01.07.2016

Студворк — интернет-сервис помощи студентам

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

Я хочу написать это в виде дерева но не могу понять как сохранять новые узлы полученные сложением минимальных частот символов

К примеру у нас такая последовательность: TAATTAGAAATTCTATTATA
Частота символа
A = 0.45 = 45%,
C = 0.05 = 5%,
G = 0.05 = 5%,
T = 0.45 = 45%.

В начале у нас будут 4 узла в которых в качестве значения будут храниться частоты символов. Ищем среди них минимальные значения, минимальными значениями будут здесь 0.05(символа C) и 0.05(символа G), суммируем их 0.1 получаем новый узел который будет связан с узлами 0.05(символа C) и 0.05(символа G). Вопрос, как сохранить этот новый узел чтобы при следующей итерации к нему можно было сразу обращаться?

@nmcf · 15.03.2018, 22:18

Были же реализации Хаффмана, хоть и кривоватые. Посмотри, как там делали.

@no swear · 15.03.2018, 22:30 **[ТС]**

Если честно, фиг поймёшь эти реализации. Там только голый код и несколько слов об алгоритме, а как строится само дерево совсем непонятно. Ну если не будет другого выхода останется только копаться в этих кодах и смотреть как там всё устроено, что собственно мне не очень хочется.

Добавлено через 2 минуты
Была мысль идти от начальных узлов к вершине(корню) но так проход будет очень долгим я думаю

@nmcf · 16.03.2018, 08:29

Вот тут есть комментарии в некоторых местах:
Хаффман. Выводит лишний элемент

@no swear · 16.03.2018, 19:08 **[ТС]**

Почему в map не сохраняются значения массива freq и структуры HaffmanNode?
Обратите внимание на строку 58 где цикл

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
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <map>
 
class Haffman
{
    struct HaffmanNode
    {
        HaffmanNode *left;
        HaffmanNode *right;
        char symbol;
        int val;
    };
 
private:
    //std::multimap<float, HaffmanNode*> tab;
    //std::multimap<float, HaffmanNode*>::iterator it_tab;
    std::multimap<float, HaffmanNode> tab;
    std::multimap<float, HaffmanNode>::iterator it_tab;
    HaffmanNode *start;
    const int size = 256;
    char *chr;
    float *freq;
    int *symbol;
    int diff_symbol;
 
    void count_freq_of_symbol(char *str)
    {
        int len = strlen(str);
        for (int i = 0; i < size; ++i)
            symbol[i] = 0;
        for (int i = 0; i < len; ++i)
            symbol[+str[i]]++;
        for (int i = 0; i < size; ++i)
        {
            if (symbol[i])
                diff_symbol++;
        }
        //printf("%d\n", diff_symbol);
        freq = new float[diff_symbol];
        chr = new char[diff_symbol];
        int j = 0;
        for (int i = 0; i < size; ++i)
        {
            if (symbol[i])
            {
                chr[j] = char(i);
                freq[j++] = (float)symbol[i] / len;
            }
        }
        //for (int i = 0; i < j; ++i)
            //printf("%c = %.2f\n", chr[i], freq[i]);
    }
 
    void build_first_node()
    {
        for (int i = 0; i < 1; ++i)
        {
            HaffmanNode hn;
            hn.left = hn.right = NULL;
            hn.symbol = chr[i];
            hn.val = freq[i];
            tab.insert(std::pair<float, HaffmanNode>(freq[i], hn));
            for (it_tab = tab.begin(); it_tab != tab.end(); ++it_tab)
                printf("%d - %d\n", it_tab->first, it_tab->second.val);
        }
    }
 
public:
    ~Haffman()
    {
        delete[] chr, freq, symbol;
    }
 
    void codify(char *str)
    {
        start = NULL;
        symbol = new int[size];
        diff_symbol = 0;
        count_freq_of_symbol(str);
        build_first_node();
    }
};
 
int main()
{
    //Haffman ob1("AAAAAAABBBBBBBBBBBBBBBBBBBBKKKKKKKKKKOOOOOOOOOOOOOOO");
    Haffman ob1;
    //ob1.codify("AAAAAAABBBBBBBBBBBBBBBBBBBBKKKKKKKKKKOOOOOOOOOOOOOOO");
    ob1.codify("TAATTAGAAATTCTATTATA");
    //ob1.show_code_of_symbol();
    //ob1.show_sequence_of_bit();
    //ob1.decifer();
    system("pause");
}

Добавлено через 3 минуты
Я даже пытаюсь их тут же вывести, в массиве chr храниться символ а в массиве freq частота этого символа оба не пустые но когда вывожу содержимое map-а то всё по нулям

Добавлено через 4 минуты
я ОШИБСЯ! Я нашел ошибку. Эта самая тупая ошибка которую я делал

@no swear · 17.03.2018, 19:21 **[ТС]**

Думаю не надо создавать новую тему поэтому спрошу тут.
Вот написал наконец то "сжатие методом Хаффмана", но я хочу реализовать настоящего Хаффмана так как моя программа не производит реального сжатия. Можете что нибудь порекомендовать мне?

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
 
class Haffman
{
    struct HaffmanNode
    {
        HaffmanNode *left;
        HaffmanNode *right;
        char symbol;
        float val;
    };
 
private:
    std::multimap<float, HaffmanNode*> tab;
    std::multimap<float, HaffmanNode*>::iterator it_tab;
    HaffmanNode *start;
    const int size = 256;
    char *chr;
    float *freq;
    int *symbol;
    int diff_symbol;
 
    void count_freq_of_symbol(const char *str)
    {
        int len = strlen(str);
        for (int i = 0; i < size; ++i)
            symbol[i] = 0;
        for (int i = 0; i < len; ++i)
            symbol[+str[i]]++;
        for (int i = 0; i < size; ++i)
        {
            if (symbol[i])
                diff_symbol++;
        }
        freq = new float[diff_symbol];
        chr = new char[diff_symbol];
        int j = 0;
        for (int i = 0; i < size; ++i)
        {
            if (symbol[i])
            {
                chr[j] = char(i);
                freq[j++] = (float)symbol[i] / len;
            }
        }
    }
 
    void build_first_node()
    {
        for (int i = 0; i < diff_symbol; ++i)
        {
            HaffmanNode *hn = new HaffmanNode;
            hn->left = NULL;
            hn->right = NULL;
            hn->symbol = chr[i];
            hn->val = freq[i];
            tab.insert(std::pair<float, HaffmanNode*>(freq[i], hn));
            //printf("%.2f\n", freq[i]);
        }
        build_tree();
    }
 
    void build_tree()
    {
        HaffmanNode *hf1, *hf2;
        float x, y;
        for (int i = 1; i <= diff_symbol - 1; ++i)
        {
            HaffmanNode *HF = new HaffmanNode;
            it_tab = tab.begin();
            x = it_tab->first;
            hf1 = it_tab->second;
            tab.erase(it_tab);
 
            it_tab = tab.begin();
            y = it_tab->first;
            hf2 = it_tab->second;
            tab.erase(it_tab);
 
            HF->left = hf1;
            HF->right = hf2;
            HF->symbol = '\0';
            HF->val = x + y;
            //printf("%.2f   %.2f\n", x, y);
            tab.insert(std::pair<float, HaffmanNode*>(x + y, HF));
        }
        it_tab = tab.begin();
        start = it_tab->second;
        //printf("%.2f", start->val);
        tab.clear();
    }
 
    void show_code(HaffmanNode *node, std::string code)
    {
        if (node != NULL)
        {
            if (node->symbol != '\0')
                std::cout << code << '-' << node->symbol << std::endl;
            show_code(node->left, code + '0');
            show_code(node->right, code + '1');
        }
    }
 
public:
    ~Haffman()
    {
        delete[] chr, freq, symbol;
    }
 
    void codify(const char *str)
    {
        start = NULL;
        symbol = new int[size];
        diff_symbol = 0;
        count_freq_of_symbol(str);
        build_first_node();
    }
 
    void show_code_of_symbol()
    {
        show_code(start, "");
    }
};
 
int main()
{
    Haffman ob;
    ob.codify("AAAAAAABBBBBBBBBBBBBBBBBBBBKKKKKKKKKKOOOOOOOOOOOOOOO");
    ob.show_code_of_symbol();
    printf("\n");
    system("pause");
}

@nmcf · 17.03.2018, 19:46

Что за реальное сжатие? Там же где-то в примере было формирование последовательности битов с записью в файл.

@no swear · 27.03.2018, 18:37 **[ТС]**

Всем ещё раз здравствуйте дорогие форумчанине

Что можете посоветовать для того чтобы создать реальный архиватор хотя бы txt файла

Моя программа создаёт кодировку, как теперь выделить эти биты и присвоить символам?

Добавлено через 2 минуты

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
#include <fstream>
#include <iostream>
#include <map>
#include <string>
 
class haffman
{
    struct haffman_node
    {
        haffman_node *left;
        haffman_node *right;
        char symbol;
        float val;
    };
 
private:
    std::multimap<float, haffman_node*> node_map;
    std::multimap<float, haffman_node*>::iterator it_node_map;
    std::map<char, std::string> symbol_code_map;
    std::map<char, std::string>::iterator it_symbol_code_map;
    std::map<std::string, char> code_symbol_map;
    std::map<std::string, char>::iterator it_code_symbol_map;
    std::string bit_sequence, str_code_of_symbol, str_deciphered_text;
    std::string text;
    haffman_node *start;
    const int size = 256;
    char *chr;
    float *freq;
    int *symbol;
    int diff_symbol;
 
    void count_freq_of_symbol()
    {
        int len = text.size();
        for (int i = 0; i < size; ++i)
        {
            symbol[i] = 0;
            freq[i] = 0;
            chr[i] = 0;
        }
        for (int i = 0; i < len; ++i)
            symbol[+text[i]]++;
        for (int i = 0; i < size; ++i)
        {
            if (symbol[i])
                diff_symbol++;
        }
 
        int j = 0;
        for (int i = 0; i < size; ++i)
        {
            if (symbol[i])
            {
                chr[j] = char(i);
                freq[j++] = (float)symbol[i] / len;
            }
        }
    }
 
    void build_first_node()
    {
        for (int i = 0; i < diff_symbol; ++i)
        {
            haffman_node *hn = new haffman_node;
            fill_node(hn, freq[i], chr[i]);
            node_map.insert(std::pair<float, haffman_node*>(freq[i], hn));
        }
        build_tree();
    }
 
    void fill_node(haffman_node *&node, const float num, const char ch, haffman_node *l = NULL, haffman_node *r = NULL)
    {
        node->left = l;
        node->right = r;
        node->val = num;
        node->symbol = ch;
    }
 
    void get_data(float &num, haffman_node *&hf)
    {
        it_node_map = node_map.begin();
        num = it_node_map->first;
        hf = it_node_map->second;
        node_map.erase(it_node_map);
    }
 
    void build_tree()
    {
        haffman_node *hf1, *hf2;
        float x, y;
        for (int i = 1; i <= diff_symbol - 1; ++i)
        {
            haffman_node *HF = new haffman_node;
 
            get_data(x, hf1);
            get_data(y, hf2);
 
            fill_node(HF, x + y, '\0', hf1, hf2);
            node_map.insert(std::pair<float, haffman_node*>(x + y, HF));
        }
        it_node_map = node_map.begin();
        start = it_node_map->second;
    }
 
    void code_of_symbol(haffman_node *&node, std::string code)
    {
        if (node != NULL)
        {
            if (node->symbol != '\0')
            {
                symbol_code_map.insert(std::pair<char, std::string>(node->symbol, code));
                str_code_of_symbol += code + " - " + node->symbol + "\r\n";
            }
            code_of_symbol(node->left, code + '0');
            code_of_symbol(node->right, code + '1');
        }
    }
 
    void sequence_of_bit()
    {
        for (int i = 0; i < text.size(); ++i)
        {
            it_symbol_code_map = symbol_code_map.find(text[i]);
            bit_sequence += it_symbol_code_map->second;
        }
    }
 
    void _decifer()
    {
        char ch;
        std::string bit;
        for (it_symbol_code_map = symbol_code_map.begin(); it_symbol_code_map != symbol_code_map.end(); ++it_symbol_code_map)
        {
            ch = it_symbol_code_map->first;
            bit = it_symbol_code_map->second;
            code_symbol_map.insert(std::pair<std::string, char>(bit, ch));
        }
        bit = "";
        for (int i = 0; i < bit_sequence.size(); ++i)
        {
            bit += bit_sequence[i];
            it_code_symbol_map = code_symbol_map.find(bit);
            if (it_code_symbol_map != code_symbol_map.end())
            {
                str_deciphered_text += it_code_symbol_map->second;
                bit = "";
            }
        }
    }
 
public:
    haffman()
    {
        start = NULL;
        symbol = new int[size];
        freq = new float[size];
        chr = new char[size];
    }
 
    ~haffman()
    {
        delete[] symbol, freq, chr;
    }
 
    void codify(const std::string &str)
    {
        node_map.clear();
        symbol_code_map.clear();
        code_symbol_map.clear();
        diff_symbol = 0;
        bit_sequence = str_code_of_symbol = str_deciphered_text = "";
        text = str;
        count_freq_of_symbol();
        build_first_node();
        code_of_symbol(start, "");
        sequence_of_bit();
        _decifer();
    }
 
    void show_code_of_symbol()
    {
        std::cout << str_code_of_symbol;
    }
 
    void show_code_of_symbol(const char *filename)
    {
        std::ofstream fout(filename);
        fout << str_code_of_symbol;
    }
 
    void show_sequence_of_bit()
    {
        std::cout << bit_sequence << std::endl;
    }
 
    void show_sequence_of_bit(const char *filename)
    {
        std::ofstream fout(filename);
        fout << bit_sequence << std::endl;
    }
 
    void decifer()
    {
        std::cout << str_deciphered_text << std::endl;
    }
 
    void decifer(const char *filename)
    {
        std::ofstream fout(filename);
        fout << str_deciphered_text << std::endl;
    }
};

@nmcf · 27.03.2018, 19:05

Там же есть обратное преобразование.
Придётся таблицу кодов в файл сохранять.

@no swear · 27.03.2018, 19:53 **[ТС]**

nmcf Сейчас читаю про бинарные файлы, вы можете пожалуйста объяснить подробно что делает вот эта строчка кода. В интернете читаю, её везде используют но каким образом она работает не объясняется

C++
1
outstrm.write((char *)&m[i], sizeof(int));

Код целиком

C++
1
2
3
4
5
6
7
/* открываем файл для записи */
    ofstream outstrm ("c:/binfiles/oonumber1.bin", std::ios::binary);
    if(outstrm.is_open())
    { for(int i = 0; i < 10; i++) // выводим массив в файл поэлементно
        outstrm.write((char *)&m[i], sizeof(int)); 
      outstrm.close();
    }

@nmcf · 27.03.2018, 22:42

Запись в файл массива. И цикл не нужен.

C++
1
outstrm.write((char *)m, sizeof(int) * 10);

@no swear · 28.03.2018, 18:56 **[ТС]**

Сообщение от nmcf

(char *)m

А это что значит? Не совсем понимаю смысл этой строчки

@nmcf · 28.03.2018, 19:05

Приведение типа.

C++
1
reinterpret_cast<char *>(m)

@no swear · 28.03.2018, 19:24 **[ТС]**

Ну я понял что это приведение типа но для чего она здесь нужна?

Зачем приводить к типу (char *)

@nmcf · 28.03.2018, 22:27

Функцию write() посмотри.

@no swear · 30.03.2018, 18:20 **[ТС]**

А где сохранять таблицу символов с кодами? Например заархивировал на одном компе и разархивировал на другом.

@nmcf · 30.03.2018, 18:29

Ну в тот же файл и сохранять.

@no swear · 30.03.2018, 21:15 **[ТС]**

Сообщение от nmcf

Ну в тот же файл и сохранять

А как именно? Что делать?

@nmcf · 30.03.2018, 21:25

Придумывать какой-то формат сохранения.

Новые блоги и статьи Все статьи Все блоги /
Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025

@no swear 192 / 166 / 82 Регистрация: 01.07.2016 Сообщений: 943

	Сжатие методом Хаффмана 15.03.2018, 22:07. Показов 5328. Ответов 18 Метки нет (Все метки) Хочу реализовать алгоритм "Сжатие методом Хаффмана" но столкнулся с такой проблемой. Проблема вот в чём, в описании алгоритма говорится что надо брать минимальные значение частот(частота символа это процент встречающегося символа) символов в последовательности(в строке которую мы сами же и задаём) и суммировать их, тем самым получаем новое значение. Я хочу написать это в виде дерева но не могу понять как сохранять новые узлы полученные сложением минимальных частот символов К примеру у нас такая последовательность: TAATTAGAAATTCTATTATA Частота символа A = 0.45 = 45%, C = 0.05 = 5%, G = 0.05 = 5%, T = 0.45 = 45%. В начале у нас будут 4 узла в которых в качестве значения будут храниться частоты символов. Ищем среди них минимальные значения, минимальными значениями будут здесь 0.05(символа C) и 0.05(символа G), суммируем их 0.1 получаем новый узел который будет связан с узлами 0.05(символа C) и 0.05(символа G). Вопрос, как сохранить этот новый узел чтобы при следующей итерации к нему можно было сразу обращаться? 0

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	15.03.2018, 22:18
	Были же реализации Хаффмана, хоть и кривоватые. Посмотри, как там делали. 1

@no swear 192 / 166 / 82 Регистрация: 01.07.2016 Сообщений: 943
	15.03.2018, 22:30 [ТС]
	Если честно, фиг поймёшь эти реализации. Там только голый код и несколько слов об алгоритме, а как строится само дерево совсем непонятно. Ну если не будет другого выхода останется только копаться в этих кодах и смотреть как там всё устроено, что собственно мне не очень хочется. Добавлено через 2 минуты Была мысль идти от начальных узлов к вершине(корню) но так проход будет очень долгим я думаю 0

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	16.03.2018, 08:29
	Вот тут есть комментарии в некоторых местах: Хаффман. Выводит лишний элемент 1

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	17.03.2018, 19:46
	Что за реальное сжатие? Там же где-то в примере было формирование последовательности битов с записью в файл. 1

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	27.03.2018, 19:05
	Там же есть обратное преобразование. Придётся таблицу кодов в файл сохранять. 1

@no swear 192 / 166 / 82 Регистрация: 01.07.2016 Сообщений: 943
	28.03.2018, 19:24 [ТС]
	Ну я понял что это приведение типа но для чего она здесь нужна? Зачем приводить к типу (char *) 0

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	28.03.2018, 22:27
	Функцию write() посмотри. 0

@no swear 192 / 166 / 82 Регистрация: 01.07.2016 Сообщений: 943
	30.03.2018, 18:20 [ТС]
	А где сохранять таблицу символов с кодами? Например заархивировал на одном компе и разархивировал на другом. 0

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	30.03.2018, 18:29
	Ну в тот же файл и сохранять. 1

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	30.03.2018, 21:25
	Придумывать какой-то формат сохранения. 0