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

Нужен код программы для кодировки методом ХафФмана - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
Vlad_7
0 / 0 / 0
Регистрация: 14.02.2011
Сообщений: 25
30.10.2011, 19:42     Нужен код программы для кодировки методом ХафФмана #1
Немного теории:
Дерево кодирования Хаффмена (Н-дерево) - двоичное дерево, у которого каждый узел имеет вес, и вес родителя равен суммарному весу его детей.

Классический алгоритм Хаффмена на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмена (Н-дерево). Алгоритм построения Н-дерева прост и элегантен.
1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количест¬ву вхождений символа в сжимаемое сообщение.
2. Выбираются два свободных узла дерева с наи¬меньшими весами.
3. Создается их родитель с весом, равным их сум¬марному весу.
4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.
5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.
6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Классический алгоритм Хаффмена имеет один су¬щественный недостаток. Для восстановления содер¬жимого сжатого сообщения декодер должен знать таб¬лицу частот, которой пользовался кодер. Следова¬тельно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения. Кроме того, необходимость на¬личия полной частотной статистики перед началом собственно кодирования требует двух проходов по со¬общению: одного для построения модели сообщения (таблицы частот и Н-дерева), другого для собственно кодирования.


Что должно быть в программе:
1.Вход программы: произвольный текстовый файл. Реализуйте только первую итерацию классического алгоритма. На первой итерации происходит построение модели данных: построение таблицы частот и Н-дерева.
2.Вывод программы: "таблица" кодов для каждого символа.
Если можно:
Код был с кометариями и не очень объёмен. А то я на С++ новичок
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.10.2011, 19:42     Нужен код программы для кодировки методом ХафФмана
Посмотрите здесь:

C++ Строки. нужен код для соритровки символов
Модифицированный код Хаффмана C++
C++ Ребят доработайте код программы (программа сортировки чисел методом Шелла)
C++ Нужен код, который сможет изменять порядок вопросов при запуске программы
C++ Алгоритм и код программы решения уравнения Пуассона методом матричной прогонки
C++ Нужен правильный код для BORLAND c++ пожалуйста
C++ Код Хаффмана
C++ Код Хаффмана реализованный через построение бинарного дерева
C++ Нужен код программы, который выводит sin и cos y
Нужен код программы, которая вычисляет cos^n|x| C++
C++ Код шеннон или хаффмана в dev c++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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