Форум программистов, компьютерный форум CyberForum.ru

Хаффман с++ - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 43, средняя оценка - 4.70
Hardcore
4 / 4 / 0
Регистрация: 24.10.2010
Сообщений: 200
30.03.2012, 10:30     Хаффман с++ #1
Здравстуйте.
Это код хаффмана.
У меня вопрос, я не понял часть int main ()
Расскажите подробнее что там происходит.

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
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
 
struct s_node
{
    int c;
    char ch;
    int n;
    std::vector<s_node*> br;
};
 
class my_ifstream: public std::ifstream
{
public:
    virtual my_ifstream& operator>>( char&);
    my_ifstream(const char *_Filename, std::ios_base::openmode _Mode = ios_base::in, int _Prot = (int)ios_base::_Openprot);
};
 
my_ifstream::my_ifstream(const char *_Filename, std::ios_base::openmode _Mode, int _Prot):std::ifstream(_Filename, _Mode, _Prot)
{
}
 
my_ifstream& my_ifstream::operator>>( char& ch)
{
    ch = get();
 
    return *this;
}
 
void tree_walk(s_node *);
void tree_del(s_node *);
void write_message();
 
std::ofstream fout("output.txt");
std::string table[256];
 
int main()
{
    my_ifstream fin("input.txt", std::ios_base::in | std::ios_base::binary);
    
    if (!fin.is_open())
    {
        std::cout << "Input file not found" << std::endl;
        
        system("pause");
 
        return 0;
    }
 
    std::vector< char> ch_set;
    std::vector<s_node> nodes;
    char ch;
    int j = 0;
 
    while (fin >> ch)
    {
        int i;
 
        for (i = 0; i < ch_set.size() && ch_set[i] != ch; i++);
 
        if (i == ch_set.size())
        {
            s_node t;
 
            ch_set.push_back(ch);
 
            t.ch = ch;
            t.n = 0;
            t.c = 0;
        
            nodes.push_back(t);
 
            my_ifstream fin2("input.txt", std::ios_base::in | std::ios_base::binary);
 
            while (fin2 >> ch)
                if (ch == nodes[j].ch)
                    nodes[j].n++;
 
            j++;
        }
    }
 
    for (int i = 0; i < nodes.size() - 1; i++)
        fout << "'" << nodes[i].ch << "'" << nodes[i].n << ", ";
    
    fout << "'" << nodes[nodes.size() - 1].ch << "'" << nodes[nodes.size() - 1].n << std::endl << std::endl;
 
    std::vector<s_node*> t;
 
    for (int i = 0; i < nodes.size(); i++)
    {
        t.push_back(new s_node);
        *t[i] = nodes[i];
    }
 
    while (t.size() > 1)
    {
        s_node *x;
 
        for (int i = 0; i < t.size(); i++)
            for (int j = 0; j < t.size(); j++)
                if (t[i]->n < t[j]->n)
                    x = t[i], t[i] = t[j], t[j] = x;
 
        s_node *min1 = t[0];
        int c1 = 0;
 
        t.erase(t.begin() + c1);
        
        s_node *min2 = t[0];
        int c2 = 0;
 
        s_node *tmp = new s_node;
 
        tmp->br.push_back(min1);
        tmp->br.push_back(min2);
 
        tmp->c = 2;
        tmp->n = min1->n + min2->n;
        t[c2] = tmp;
    }
 
    tree_walk(t[0]);
    write_message();
    tree_del(t[0]);
 
    return 0;
}
 
void tree_walk(s_node *root)
{
    static std::string s = "";
 
    if (root->c)
    {
        s += "1";
        
        tree_walk(root->br[1]);
        s.erase(s.size() - 1, 1);
        
        s +="0";
 
        tree_walk(root->br[0]);
        s.erase(s.size() - 1, 1);
    }
    else
    {
        fout << "'" << root->ch << "'" << " = " << s << std::endl;
        table[root->ch] = s;
    }
}
 
void tree_del(s_node *root)
{
    if (root->c)
    {
        tree_del(root->br[1]);
        tree_del(root->br[0]);
    }
    else
        delete root;
}
 
void write_message()
{
    my_ifstream fin("input.txt");
    char ch;
 
    fout << std::endl;
 
    while(fin >> ch)
        fout << table[ch];
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.03.2012, 10:30     Хаффман с++
Посмотрите здесь:

Хаффман и не правильное разархивирование C++
Хаффман Pascal
Хаффман- побитовая запись в файл. ПОБИТОВАЯ=) Delphi
C++ Хаффман, исходник
Delphi Хаффман и LZW

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
30.03.2012, 15:09     Хаффман с++ #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Ссылка на википедию, что такое код Хаффмана ниже.
Кодирование Хаффмана основано на том, что в тексте наверняка
отсутствуют какие-либо символы (буквы или знаки) из стандартной ASCII кодировки
И поэтому мы для текста создаём свой алфавит, который можно закодировать меньше, чем 8 бит на символ

ну, сначала открывается файл с текстом fin
из него по очереди берутся все символы(буквы) по одному
Из этих букв создаётся алфавит, т.е. мы хотим заполнить алфавит ch_set только теми буквами,
что встречаются в тексте, но без повторений.

Т.е. берётся символ ch (далее это действие будет повторяться с каждым символом в цикле,
но сейчас рассмотрим что делается с ch)
C
1
 while (fin >> ch)//загрузка CH из fin
потом мы должны составить алфавит из этих символов, т.е собрать все эти
символы и исключить повторения. Назовём алфавит ch_set.
C
1
for (i = 0; i < ch_set.size() && ch_set[i] != ch; i++);
В этом цикле мы сравниваем ch c каждым из уже добавленных в алфавит символов, чтобы в случае совпадения хотя б с одним
не добавлять в алфавит второй такой же.
C
1
if (i == ch_set.size())
это условие говорит нам, что мы дошли до конца алфавита и не нашли такого же символа,
т.е. в алфавите не хватает символа ch. Значит надо добавить.
Иначе возвращаемся в новый виток цикла "while (fin >> ch)"

Так вот, о добавлении в алфавит. Идёт добавление символа в алфавит, если как выяснилось выше надо его добавить
C
1
ch_set.push_back(ch);
используется стандартный метод класса Vector<char>

Вернёмся к коду. Счётчик j судя по всему подсчитывает количество символов в алфавите ch_set. Для меня это странно,
ведь можно использовать ch_set.size(). Ну не суть.
----------------------------------------------------------------------
Мы снова открываем "input.txt" и ищем в нём наш символ ch. при этом подсчитываем количество этих символов в файле
Ведь в зависимости от того как часто встречается символ в файле будет строится и его код Хаффмана.

C++
1
2
3
while (fin2 >> ch)
                if (ch == nodes[j].ch)
                    nodes[j].n++;
Я не совсем понял, зачем открывать файл заново, ведь можно было увеличивать счётчик вхождений ch в ранее рассмотренном цикле составления алфавита в условии, если мы обнаружили повторение символа в алфавите.

Ну не суть, так тоже работает.
C++
1
}//конец цикла while
Итак, промежуточный итог: весь алфавит загнан в массив ch_set
Кроме того создан вектор nodes в котором так же идут все символы алфавита,
кроме того там у каждого символа есть число вхождений.

Для наглядности эта информация выводится на экран.
C++
1
2
for (int i = 0; i < nodes.size() - 1; i++)
        fout << "'" << nodes[i].ch << "'" << nodes[i].n << ", ";
На этом чтение файла заканчивается и начинается составление дерева.


Дерево определит наш код Хаффмана.
Пример смотри в Википедии
http://en.wikipedia.org/wiki/File:Huffman_tree_2.svg
из узла дерева растёт либо новый узел, либо символ. Редко встречающиеся символы растут от самых последних узлов
Чтобы узнать код символа надо пройтись по дереву от корня, считая повороты. Поворот налево добавляет к коду 1, направо 0
Например
код символа 'u' на рисунке будет 11000
код символа 'о' на рисунке будет 11001
За счёт того, что часто встречающиеся символы мы поместили ближе к корню,
их код меньше по длинне. То есть длина кода, не постоянно 8 бит и даже не 5, как у 'o' и 'u',
а у одних 5 бит, а у более частых, например 'a'
код символа 'a' на рисунке будет 10 - видишь? На порядок короче!

Вернёмся к программе
Зачем-то составляется массив t полностью аналогичный массиву nodes
Он сортируется (кажется это сортировка выбором, причём неоптимальный её вариант,
хочу заметить, сортировку можно и оптимизировать или вообще воспользоваться стандартной функцией sort)
Но автор видимо решил просто пойти проверенным путём
C++
1
2
3
4
for (int i = 0; i < t.size(); i++)
            for (int j = 0; j < t.size(); j++)
                if (t[i]->n < t[j]->n)
                    x = t[i], t[i] = t[j], t[j] = x;
Вообще советую хорошо подумать над этой сорртировкой. Возможно даже, что она не работает.
ЭЙ ЛЮДИ ТАКАЯ СОРТИРОВКА ВРОДЕ НЕ ДОЛЖНА РАБОТАТЬ!!! ВАШЕ МНЕНИЕ???
Это была просто сортировка. Наиболее часто встречающиеся элементы оказываются в начале...
...ой... или в конце???
Короче.. разберись с сортировкой, потом продолжим разговор

Добавлено через 1 час 3 минуты
Ладно, напишу ещё про оставшуюся часть кода
C++
1
2
3
4
while (t.size() > 1){
s_node *x;
        /*тут была неработающая сортировка t*/
....
Переменные c1 и c2 всегда равны нулю, никогда не изменяются и вообще непонятно зачем их заводить было. Смело удаляй.
Мы запоминаем первые два элемента "отсортированного" неработающей сортировкой массива
у них это символы с самым малым n вхождений - редкие
их мы запоминаем в переменных min1 и min2 и удаляем из основного массива.
Далее создаём для них родительский узел (память при этом наверняка потечёт)
C++
1
s_node *tmp = new s_node;
В его список ветвей мы запихиваем эти два элемента
C++
1
2
3
4
tmp->br.push_back(min1);
        tmp->br.push_back(min2);
        tmp->c = 2;
        tmp->n = min1->n + min2->n;
строка tmp->c = 2; Похоже отмечает, что узел tmp теперь не ветка, а родитель:
узлы min1 и min2 скопированы в вектор потомков tmp - стали потомками tmp
А вес у этой ветки будет равен сумме весов её потомков. Теперь min1 можно удалять.
min2 по идее тоже, но нам нужно ещё добавить вновь созданный tmp в список узлов,
вместо этого для экономии мы копируем tmp вместо ненужного старого min2.


В итоге эту ветку добавляют в начало общего списка узлов (копируется вместо элемента min2, узел min1 удалён из списка)
C++
1
t[c2] = tmp;
Цикл повторяется снова, нам нужно рассовать все узлы по веткам.
Теперь становится ясно, зачем нужна была бредовая сортировка в начале, чтобы поставить tmp на нужное место в массиве.
Но это всё равно бред! Вместо этого предлагаю сначала отсортировать массив t один раз до цикла построения дерева, а затем выполнять единственную операцию вставки нового узла дерева в массив на нужное место.
Вот дерево и построилось!
beta-particle
 Аватар для beta-particle
4 / 4 / 0
Регистрация: 07.01.2013
Сообщений: 103
07.01.2013, 21:31     Хаффман с++ #3
Доброго дня суток. Мне нужно написать кодировку Хаффмана. Так как я пока что не понимаю классы, решил написать по своему. Это пока что начало.
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
// Метод сжатия по Хаффману
#include<iostream>
#include<string>
#include<fstream>
 
using namespace std ;
//Контейнер файлов
ifstream input("D:\\Mini_files\\haffman\\in-haff.txt",ios::binary) ;
ifstream code_in("D:\\Mini_files\\haffman\\code.txt") ;
ofstream code_out("D:\\Mini_files\\haffman\\code.txt") ;
 
int main ()
{
    //Контейнер переменных
    int frequency[255] ; for (int i = 0; i<=255; i++) frequency[i] = 0 ;
    int codes[255] ; for(int i = 0; i<=255; i++) codes[i] = 0 ;
    int g = 1, count = 0, h,k ;
    unsigned char a[1] ;
    //
    while (g == 1)
    {
        input.read((char*)a,1) ;
        
        h = input.gcount() ;
        if (h > 0)
        {
            k = int(a) ;
            frequency[k] ++ ;
            for (int j = 0; j<=255; j++) cout<<frequency[j] ;
        }
        else break ;
    }
 
    system("pause") ;
    return 0 ;
}
В результате получается, что k = очень большому числу. НЕ могу понять, в чем ошибка. Кто-понял, в чем загвоздка, будьте добры, разъясните.

Добавлено через 13 минут
По сути, должно считать один байт. Но что-то считывается не так. Я не могу понять что.

Добавлено через 30 минут
Я думаю, проблема вот в чем : тип unsign char имеет диапазон от 0 до 255, а char от -127 до 128. Тогда как быть с функцией .read(), если она требует первого аргумента в а типе char* ?
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
07.01.2013, 23:24     Хаффман с++ #4
Цитата Сообщение от beta-particle Посмотреть сообщение
input.read((char*)a,1)
input.read((unsigned char*)a,1)
или
input.read((char*)a,1);
a+=127;
beta-particle
 Аватар для beta-particle
4 / 4 / 0
Регистрация: 07.01.2013
Сообщений: 103
07.01.2013, 23:41     Хаффман с++ #5
Спасибо! Я поставил k = int(a[0]) вместо k = int(a) и все заработало, как хотелось бы. Про правильность работы пока ничего не могу сказать - будет видно при декодировке. А можно вопрос - как построить бинарное дерево для частот. Я их отсортировал, теперь нужно сотворить дерево. А где хранить составляющие будущего кода для символов? В самих узлах?
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
07.01.2013, 23:46     Хаффман с++ #6
в примере из первого поста для построения дерева использовался вектор структур узлов. Посмотри внимательно этот пример, там всё пояснено.
beta-particle
 Аватар для beta-particle
4 / 4 / 0
Регистрация: 07.01.2013
Сообщений: 103
08.01.2013, 00:05     Хаффман с++ #7
Проблема в том, что я еще не знаю про вектора ничего.((

Добавлено через 17 минут
Просто не совсем ясно, когда, например, встречаемость всех символов равно, то как делать дерево?
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
08.01.2013, 00:11     Хаффман с++ #8
это уже частный случай. Думай об алгоритме: бери массив узлов, сортируй, пару младших удаляй из массива, создавай им родителя и родителя добавляй на место в массив. всё.
beta-particle
 Аватар для beta-particle
4 / 4 / 0
Регистрация: 07.01.2013
Сообщений: 103
08.01.2013, 13:13     Хаффман с++ #9
Хорошо, спасибо, сейчас попробую.

Добавлено через 3 часа 19 минут
Почему при переводе из строки в строку выводит один нолик, а не 17, как нужно мне?
C++
1
2
3
4
                         istringstream iss(str);
             iss >> newmas.codes[i] ;
             cout<<newmas.codes[i]<<endl  ;
             str = "" ;
str содержит в себе 17 нулей

Добавлено через 1 час 14 минут
Описался - из строки в число.

Добавлено через 8 часов 24 минуты
И главное, что выводит только последнюю цифру, а не число полностью.
Lawlliet
2 / 2 / 0
Регистрация: 25.03.2010
Сообщений: 145
10.03.2013, 17:20     Хаффман с++ #10
А у меня вопрос, я взял код из первого поста, но он ен компилируесть , выдает 4 ошибки!
Devcpp использовал!
Хаффман с++
juli_J
0 / 0 / 0
Регистрация: 09.01.2013
Сообщений: 4
12.05.2013, 20:28     Хаффман с++ #11
Скажите, а кто-нибудь может мне помочь? мне нужно описание алгоритма Хаффмана, вроде блок-схемы, но можно текстом. Очень нужно!
Yandex
Объявления
12.05.2013, 20:28     Хаффман с++
Ответ Создать тему
Опции темы

Текущее время: 13:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru