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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ В одномерном массиве состоящем из N вещественных элементов вычислить http://www.cyberforum.ru/cpp-beginners/thread534407.html
Здраствуйте. Пожалуйста сделайте эту же задачу то ко на С.Не на С++ а на C.
C++ В программе реализовать возможность записи объектов в файл и чтения объектов из файла Добрый день, помогите, пожалуйста! У меня есть программа: #include <iostream> #include <locale.h> using namespace std; class train { int number_id; char destination; int time; http://www.cyberforum.ru/cpp-beginners/thread534406.html
Перегрузка оператора * C++
Операция произведения применяется к объекту квадрат, при этом изменяются координаты центры фигуры. Результатом произведения является квадрат координаты центра которого равны произведению соответствующих координат умножаемых квадратов. То есть нам нужно сделать перегрузку оператора * при этом использовать дружественные функции, на экран должны выводится два любых квадрата с различными...
C++ Используя функции сформировать одномерный массив и отсортировать по возрастанию только те элементы массива, которые являются простыми числами
Помогите закончить две задачи. 1. Используя функции сформировать одномерный массив и отсортировать по возрастанию только те элементы массива, которые являются простыми числами(делятся на 1 и сами на себя). #include<iostream.h> #include<stdlib.h> #include<conio.h> void mass(int n) {
C++ Редактирование бинарного файла http://www.cyberforum.ru/cpp-beginners/thread534334.html
возможно ли написать такую функцию которая будет редактировать бинарный файл?
C++ '...' was not declared in this scope Доброго времени суток. Столкнулся с одной проблемой при создании класса: имеется описание класса : class CDateTime { public: int year,mon,day,hour,min,sec,MDay; CDateTime(); CDateTime(int y,int m,int d,int h,int mi,int s); void operator = (const string str); подробнее

Показать сообщение отдельно
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
30.03.2012, 15:09     Хаффман с++
Ссылка на википедию, что такое код Хаффмана ниже.
Кодирование Хаффмана основано на том, что в тексте наверняка
отсутствуют какие-либо символы (буквы или знаки) из стандартной 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 один раз до цикла построения дерева, а затем выполнять единственную операцию вставки нового узла дерева в массив на нужное место.
Вот дерево и построилось!
 
Текущее время: 02:57. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru