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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
Vlad_7
0 / 0 / 0
Регистрация: 14.02.2011
Сообщений: 25
#1

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

30.10.2011, 19:42. Просмотров 1260. Ответов 0
Метки нет (Все метки)

Немного теории:
Дерево кодирования Хаффмена (Н-дерево) - двоичное дерево, у которого каждый узел имеет вес, и вес родителя равен суммарному весу его детей.

Классический алгоритм Хаффмена на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмена (Н-дерево). Алгоритм построения Н-дерева прост и элегантен.
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++):

Нужен код программы, которая вычисляет cos^n|x| - C++
Нужен код программы, которая вычисляет cos^n|x|, где n натуральное число и x вещественное число

Нужен код программы, который выводит sin и cos y - C++
Здравствуйте, подскажите пожалуйста код программы её условие: мне нужно ввести "x", для этого мн дан интервал чисел от 2 до 5, если я введу...

Кодирование текста методом Хаффмана - C++
Вроде бы всё правильно , НО : 1)вылезает "ё" в самом начале , хотя сортируется map по умолчанию по алфавиту и "ё" должно быть в конце.. ...

Ребят доработайте код программы (программа сортировки чисел методом Шелла) - C++
Нужна помощь Есть программа сортировки чисел методом шелла ее надо дописать чтоб она спрашивала 1 - введите сами 2 – рандом Если...

Алгоритм и код программы решения уравнения Пуассона методом матричной прогонки - C++
Объясните, пожалуйста алгоритм и код на Си++ задачи: ∂2P/∂x2+∂2P/∂y2=-f(x,y)

Нужен код, который сможет изменять порядок вопросов при запуске программы - C++
Нужен код,который сможет изменять порядок вопросов при запуске программы. Например:(при первом запуске) 1)Сколько тебе лет? 2)Ты...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.10.2011, 19:42
Привет! Вот еще темы с ответами:

Код Хаффмана - C++
Всем доброго дня! имеется код хафманна, работает, но считает неправильно! кто может объяснить в чем дело? #include <iostream> ...

Код Хаффмана - C++
Люди подскажите, что это за зверь? и как его реализовать на с?

Модифицированный код Хаффмана - C++
Каждому числу соответствует любое двоичное (специальная таблица пример 1 соответствует 00111, 2 соответствует 11 и так далее). При вводе...

Составить блок схему для программы упорядочивания чисел в массиве(код программы прилагается) - C++
#include <iostream> #include <stdlib.h> using namespace std; int main() { int N = 0; // N - количество элементов в массиве...


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

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

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