6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 359
1

Алгоритм Хаффмана

16.12.2014, 01:35. Показов 7652. Ответов 9
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Возможно и наболевшая тема на форуме, но всё же есть реализация алгоритма Хаффмана.
Допустим, у меня в файле есть следующая строка:
my mother meet my mouse and me.
Однако, в файл записи output.bin я получаю следующее:
ЉФЦжНЗвҐч•gН
Вряд ли дело в кодировке, пробовал Total Commander'ом открыть во всех.
Также отмечу, что при компиляции с данным файлом, после декодировки я получаю в консоли то же, что и было:
my mother meet my mouse and me.
При компиляции большого файла (для примера я брал 500 кб) в консоль также выводится что-то типо такого же мусора:
ЉФЦжНЗвҐч•gН
в файле то же самое, только уже много.

Код:
Кликните здесь для просмотра всего текста
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
#include "stdafx.h"
 
using namespace std;
 
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;// а его переменная суммой этих 2х переменных
    }
};
 
 
struct MyCompare
{
    bool operator()(const Node* l, const Node* r) const { return l->a < r->a; }
};
 
 
vector<bool> code; // 0 и 1
map<char,vector<bool> > table; // ассоциация символа с кодом.
 
void BuildTable(Node *root)
{
    if (root->left!=NULL) // если слева не 0
        {
            code.push_back(0); //пошёл по левому ребру и ставлю 0
            BuildTable(root->left); //для левого сына
        }
 
    if (root->right!=NULL) //...
        {
            code.push_back(1);
            BuildTable(root->right);
        }
 
    if (root->c) //если нашлась буква
        table[root->c]=code; // буква ассоцируется с кодом
 
    code.pop_back(); // сокращаем на 1
}
 
 
int main (int argc, char *argv[])
{
    srand(time(0));
    setlocale(LC_ALL, "RUS");
    int check;
    cout << "    Желаете закодировать Ваш файл?\n 1 - Да.\n 2 - Нет." << endl;
    cin >> check;
    int start_time =  clock();
    
////// считаем частоты символов
    if (check == 1)
    {
    ifstream f("1.txt");
 
    map<char,int> m; //ассоциативный массив 
 
    while (!f.eof())
        {
            char c = f.get(); // в с записываются символы из файла
            m[c]++;
        }
 
    //вывод ассоциативного массива (с помощью итератора, как ж ещё)
 
    /*
    map<char, int>::iterator i;
    for(i = m.begin(); i != m.end(); ++i)
        cout << i-> first <<":" << i->second << endl; //first - первый элемент, first - второй...
        */
 
 
 
////// записываем начальные узлы в список list
 
   list<Node*> t; //список указателей на Node
   for( map<char,int>::iterator itr=m.begin(); itr!=m.end(); ++itr) //итератор нужен чтобы пройтись по элементам контейнера, т.е. прохожусь по mар
 
    {
       Node *p = new Node; //создание нового узла
       p->c = itr->first; //его с становится itr->first
       p->a = itr->second;
       t.push_back(p); //указатель на всё это дело в лист, т.е. загрузка первоначальными узлами
       //т.е. идёт проход по map и загружаются ноды
    }
 
 
//////  создаем дерево
 
  while (t.size()!=1) //пока не останется 1 элемент (последний оставшийся - вершина(корень))
  {
     t.sort(MyCompare()); // сортировка
 
     Node *SonL = t.front(); //беру первый элемент и назначаю его 1м эл-том в списке
     t.pop_front(); //удаляю 1й элемент, на его место становится 2й
     Node *SonR = t.front();//котоырй на первом месте, теперь SonR тоже удаляю
     t.pop_front();
 
     Node *parent = new Node(SonL,SonR); //создане отца (новый узел)
     t.push_back(parent);// и кладётся в список
 
  }
 
    Node *root = t.front();   //root - указатель на вершину дерева
 
////// создаем пары 'символ-код':
 
    BuildTable(root);
 
////// Выводим коды в файл output.txt
 
    f.clear(); f.seekg(0); // перемещаем указатель снова в начало файла
 
    
    ofstream g("output.bin");
 
    int count=0;
    char buf=0;
 
    while (!f.eof())
    {
 
        char c = f.get();
        vector<bool> x = table[c];
        for(int n=0; n<x.size(); n++)
            {
                buf = buf | x[n]<<(7-count); //побитовое сложение, сдвиг влево
                count++;
        if (count==8) //как только  count===8 его надо обнулить
         {
             count=0;
             g<<buf;
             buf=0;
         }
        if(x[n] > 100)
            cout << x[n];
            }
    }
 
    f.close();
    g.close();
 
    int end_time = clock();
    int search_time = end_time - start_time;
    cout << "Затраченное время: " << search_time/1000.0 << "\n";
 
///// считывание из файла output.txt и преобразование обратно
 
    int number;
    cout <<endl << endl << "    Желаете декодировать Ваш файл?\n 1 - Да.\n 2 - Нет." << endl;
    cin >> number;
    //int start_decoding_time = clock();
    cout << endl;
 
    if (number == 1)
        {
            ifstream F("output.txt", ios::in | ios::binary);
            Node *p = root;
            count=0;
            char byte;
            byte = F.get();
 
            while(!F.eof())
                {
                    bool b = byte & (1 << (7-count) );
                    if (b)
                        p=p->right;
 
                    else p=p->left;
 
                    if ((p->left==NULL) && (p->right==NULL))
                        {
                            cout<<p->c; p=root;
                        }
                     count++;
 
                    if (count==8)
                        {
                            count=0;
                            byte = F.get();
                        }
                }
            
            F.close();
        //  int stop_decoding_time = clock();
        //  int search_decoding_time = stop_decoding_time - start_decoding_time;
        //  cout << "\nЗатраченное время: " << search_decoding_time/1000.0 << "\n";
            cout << "\nФайл декодирован.";
    }
 
    getch();
    return 0;}
 
    else
        return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.12.2014, 01:35
Ответы с готовыми решениями:

Алгоритм Хаффмана
Решил разобраться с этим алгоритмом, собственно он состоит из нескольких из таких шагов: 1)...

Алгоритм Хаффмана
Доброго времени суток, пишу сюда, так как отчаялся найти ошибку сам. Собственно проблема состоит в...

Алгоритм Хаффмана
Ребят, подскажите как реализовать кодирование по алгоритму Хаффмана.. Может есть какие то идеи или...

Канонический алгоритм Хаффмана
Здравствуйте! Нужен пример программы в которой реализован канонический алгоритм Хаффмана. Очень...

9
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
16.12.2014, 01:57 2
Цитата Сообщение от Aecttann Посмотреть сообщение
получаю следующее
Берем простенькую реализацию static Huffman и смотрим:
Код
HD 1.0 :  HexDump for file 'test.h' [00000000:00000029]

00000000:  1F 00 00 00 14 0F C4 06 38 40 65 DC 06 15 81 09  ......Д.8@eЬ..Ѓ.
00000010:  8C 02 28 5B 80 00 00 60 68 A3 64 35 6F 9A 37 AD  Њ.([Ђ..`hЈd5oљ7*
00000020:  9D 47 04 96 94 00 00 00 3A                       ќG.–”...:
Что не так?
1
6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 359
16.12.2014, 02:39  [ТС] 3
Цитата Сообщение от gazlan Посмотреть сообщение
простенькую реализацию
прям простенькую
для Вас, наверное)

но судя по Вашим:
......Д.8@eЬ..Ѓ.
Њ.([Ђ..`hЈd5oљ7*
ќG.–”...:
я так понимаю, что у меня верный вывод, но почему я не могу преобразовать в 0 и 1?

Добавлено через 7 минут
и ведь дальше в коде идёт обратный проход по дереву и восстанавливаются символы

Добавлено через 20 минут
т.е., как я понимаю, после декодирования файла, он должен иметь аналогичный, с исходным файлом, текст.
0
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
16.12.2014, 02:44 4
Цитата Сообщение от Aecttann Посмотреть сообщение
не могу преобразовать в 0 и 1?
Что понимается под: "преобразовать в 0 и 1"? У вас и так двоичный файл. И зачем вам "0 и 1"?

К слову, в код ваш не всматривался, но vector, очевидно, неподходящий ADT для Huffman. Посмотрите у Mark Nelson - "Priority Queues and the STL".

Добавлено через 1 минуту
Цитата Сообщение от Aecttann Посмотреть сообщение
после декодирования файла, он должен иметь аналогичный, с исходным
Для lossless data compression - идентичный.
1
6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 359
16.12.2014, 02:53  [ТС] 5
Цитата Сообщение от gazlan Посмотреть сообщение
Что понимается под: "преобразовать в 0 и 1"? У вас и так двоичный файл. И зачем вам "0 и 1"?
я просто думал, что на этапе кодировки в файле должны появиться 0 и 1.

Цитата Сообщение от gazlan Посмотреть сообщение
Для lossless data compression - идентичный.
но, допустим, я хочу открыть этот файл, обработанный алгоритмом и прочесть его, как я могу это сделать, если для меня это всего лишь набор символов?

Добавлено через 46 секунд
Цитата Сообщение от gazlan Посмотреть сообщение
неподходящий ADT для Huffman
что такое ADT?

Добавлено через 2 минуты
допустим, я хочу открыть этот файл, обработанный алгоритмом и прочесть его
иначе я тогда потерял суть кодировки, если я не могу просто взять и использовать сжатый текст...
0
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
16.12.2014, 03:00 6
Лучший ответ Сообщение было отмечено Aecttann как решение

Решение

Цитата Сообщение от Aecttann Посмотреть сообщение
на этапе кодировки
Единица хранения информации в системе - байт. То есть, поток кодов разбивается на байты (границы кодов игнорируются). Эти байты вы и видите в программах просмотра.

открыть этот файл, обработанный алгоритмом и прочесть его
Декодер этим и занимается. Нет другого способа токенизации (лексического анализа) потока неравномерных кодов, кроме использования словаря. Префиксность кода просто гарантирует однозначность декодирования.

Можете сравнить с транслитом или UTF-8, все то же самое.
1
6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 359
16.12.2014, 03:09  [ТС] 7
Цитата Сообщение от gazlan Посмотреть сообщение
Декодер этим и занимается. Нет другого способа токенизации (лексического анализа) потока неравномерных кодов, кроме использования словаря.
спасибо, понял
это как, допустим, в читалках на ПК, телефоне - декодер в них правильно предоставит мне эти файлы, да?
Префиксность кода просто гарантирует однозначность декодирования.
можно об этом немного подробнее?
на примере
в чём конкретно суть префиксного свойства? что в нём делает код однозначно декодируемым?

Добавлено через 1 минуту
просто, прочитав определение на википедии, я ещё больше запутался:
Кликните здесь для просмотра всего текста
Если промежутков или других знаков препинания между кодовыми комбинациями нет, то для однозначного декодирования комбинации 111011101 ни одна из кодовых комбинаций не может быть представлена перечисленными вариантами (префиксами). Код называется префиксным, если ни одна из его комбинаций не является префиксом другой комбинации того же кода. Часть кодовой комбинации, которая дополняет префикс до самой комбинации, называется суффиксом. Префиксные коды наглядно могут быть представлены с помощью кодовых деревьев. Если ни один узел кодового дерева не является вершиной данного кода, то он обладает свойствами префикса. Узлы дерева, которые не соединяются с другими, называются конечными. Комбинации, которые им соответствуют, являются кодовыми комбинациями префиксного кода.
0
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
16.12.2014, 03:24 8
Цитата Сообщение от Aecttann Посмотреть сообщение
в читалках на ПК, телефоне - декодер в них правильно предоставит мне эти файлы
Если вы разделяете модель: метод сжатия и словарь. Иначе, это будет разговор на разных языках.

Цитата Сообщение от Aecttann Посмотреть сообщение
суть префиксного свойства?
Prefix code

"Сжатие" - это простейший вариант трансляции.

"На пальцах", кодовые слова образуют дерево - каждый путь к листу уникален. Грамматика тривиальна: предпросмотра или учета контекста не требуется - как только прочитаны все биты кода, он может быть декодирован.
1
6 / 6 / 5
Регистрация: 19.10.2013
Сообщений: 359
16.12.2014, 03:29  [ТС] 9
Цитата Сообщение от gazlan Посмотреть сообщение
Если вы разделяете модель: метод сжатия и словарь. Иначе, это будет разговор на разных языках.
спасибо за объяснение
"На пальцах"
т.е. если совсем уж на пальцах, как Вы сказали, то когда я получу уникальный код для каждого из символов, мне не нужно будет кодировать каждый по отдельности, т.к. они сразу же декодируются, да?
0
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
16.12.2014, 03:47 10
Лучший ответ Сообщение было отмечено Aecttann как решение

Решение

Цитата Сообщение от Aecttann Посмотреть сообщение
прочитав определение на википедии
IMHO, это не поддается пониманию. Читайте в оригинале. Вот здесь, кажется, было популярно: М.Н.Аршинов, Л.Е.Садовский "КОДЫ И МАТЕМАТИКА (РАССКАЗЫ О КОДИРОВАНИИ)", М.: Наука, 1983 (Библиотечка «Квант». Вып. 30)

Добавлено через 17 минут
Цитата Сообщение от Aecttann Посмотреть сообщение
не нужно будет кодировать каждый по отдельности, т.к. они сразу же декодируются
Не уверен, что понял вопрос.

Кодер и декодер разделяют модель (можете думать о ней, как о двуязычном словаре: "symbol <--> code"). В статических методах словарь строится заранее и не изменяется, в динамических - обновляется по мере накопления статистики.

При кодировании: кодер "смотрит" в словарь и взамен каждого символа, записывает в выходной поток его код. Декодирование - обратно. Symbol - это один символ (атом) входного алфавита. Это может быть байт, слово натурального языка, обусловленная фраза итд. В простейшем случае, все атомы имеют равный битовый размер (обычно, 4, 8 или 16 бит).

Чтение и запись поточны - символ за символом. Если для равномерного кода возможен произвольный доступ к символу по индексу, то для неравномерного, позиция символа неизвестна, пока не прочитаны все ему предшествующие.
1
16.12.2014, 03:47
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.12.2014, 03:47
Помогаю со студенческими работами здесь

Алгоритм Хаффмана с записью в файл
Коды Хаффмана (сжатие информации). Реализовать процедуры кодирования и декодирования согласно...

Оптимизация расшифровки файла | алгоритм хаффмана
Привет, форумчани! Собственно сразу к вопросу. У меня имеется зашифрованный файл весом 390 КБ и...

Алгоритм Хаффмана, реализация через структуры
Добрый день, помогите пожалуйста найти ошибку в построении кодов Хаффмана. использую следующие...

Реализовать алгоритм оптимального кодирования Хаффмана
Добрый день! Нужно реализовать алгоритма Хаффмана. Помогите, пожалуйста.


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

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

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