Алгоритм Хаффмана
Применение алгоритма Хоффмана на практике. Кодирование текста, разделение его на символы. Построение дерева, создание узлов. Запись соответствия символов и их цифровых значений. Декодирование, передача закодированного текста. Виды алгоритма Хоффмана.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 12.12.2014 |
| Размер файла | 49,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Алгоритм Хаффмана
Веретенников А.Б.
2008
Алгоритм Хаффмана основывается на том, что символы в текстах как правило встречаются с различной частотой.
При обычном кодировании мы каждый символ записываем в фиксированном количестве бит, например каждый символ в одном байте, или в двух.
Однако, т.к. некоторые символы встречаются чаще, а некоторые реже ? можно записать часто встречающиеся символы в небольшом количестве бит, а для редко встречающихся символов использовать более длинные коды. Тогда суммарная длина закодированного текста может стать меньше.
Алгоритм Хаффмана на примере
Закодируем строку "Сжатие Хаффмана"
Вначале нужно подсчитать количество вхождений каждого символа в тексте.
|
С |
ж |
а |
т |
и |
е |
Х |
ф |
м |
н |
||
|
1 |
1 |
4 |
1 |
1 |
1 |
1 |
1 |
2 |
1 |
1 |
Эта таблица называется "таблица частот".
Теперь будем строить дерево
Узел дерева будет образован набором символов и числом - суммарным количеством вхождений данных символов в тексте. Назовем указанное число - весом узла.
Листьями дерева будут узлы, образованные одним символом:
Размещено на http://www.allbest.ru/
Теперь будем циклически делать следующее:
1) Ищем среди узлов, не имеющих родителя, два узла, имеющих в сумме наименьший вес.
2) Создаем новый узел, его потомками будут два выбранных узла. Его весом будет сумма весов выбранных улов. Его набор символов будет образован в результате объединения наборов символов выбранных узлов.
Создаем первый узел
Размещено на http://www.allbest.ru/
Создаем еще один узел
Размещено на http://www.allbest.ru/
Создаем еще один узел
Размещено на http://www.allbest.ru/
Создаем еще один узел
Размещено на http://www.allbest.ru/
Создаем еще один узел
Размещено на http://www.allbest.ru/
Создаем еще один узел
Размещено на http://www.allbest.ru/
Создаем еще один узел
декодирование алгоритм хоффман символ
Размещено на http://www.allbest.ru/
Создаем еще один узел
Размещено на http://www.allbest.ru/
Создаем еще один узел
Размещено на http://www.allbest.ru/
Создаем еще один узел
Размещено на http://www.allbest.ru/
Теперь для каждого узла, имеющего потомков, пометим дуги, идущие вниз, на одной дуге напишем 0, на другой 1.
Размещено на http://www.allbest.ru/
Теперь, чтобы получить код символа, надо, начиная с корня дерева идти вниз до листа соответствующего данному символу. При этом следует записывать те значения, которые написаны на тех дугах, которые мы проходим.
Получаются следующие коды
|
С |
0001 |
|
|
ж |
0000 |
|
|
а |
01 |
|
|
т |
0010 |
|
|
и |
0011 |
|
|
е |
1011 |
|
|
1010 |
||
|
Х |
111 |
|
|
ф |
110 |
|
|
м |
1000 |
|
|
н |
1001 |
Заметим, что код является префиксным, т.е. ни один код символа не является префиксом кода другого символа. Также видно, что для часто встречающихся символов коды короче.
Как будет выглядеть закодированная строка:
|
С |
ж |
а |
т |
и |
е |
Х |
а |
ф |
ф |
м |
а |
н |
а |
||
|
0001 |
0000 |
01 |
0010 |
0011 |
1011 |
1010 |
111 |
01 |
110 |
110 |
1000 |
01 |
1001 |
01 |
Т.е.
0001000001001000111011101011101110110100001100101
Декодирование
Для декодирования можно воспользоваться построенным деревом. Начинаем с корня дерева и в качестве текущего бита берем начало текста.
В цикле делаем следующее
1) Смотрим, какое значение у текущего бита, и идем в низ по дереву по дуге, на которой указано такое же значение.
2) Переходим к следующему биту.
3) Если сейчас находимся в листе дерева: читаем символ находящийся в этом листе и записываем его в результат декодирования, переходим снова в корень дерева.
Передача закодированного текста
Примечание: при передаче закодированных данных требуется также передавать дерево или таблицу частот, чтобы можно было восстановить дерево.
В данном примере, дуги помечались случайным образом, учитывалось только то, что на дугах, идущих к потомку узла должны быть разные значения.
Чтобы передавать таблицу частот нужно всегда помечать левую дугу 1, а правую 0 (или наоборот), чтобы можно было восстановить дерево по таблице.
Виды алгоритма Хаффмана
1) статический
2) динамический
3) адаптивный
Рассмотренный пример относится к динамическому алгоритму Хаффмана.
Статический алгоритм отличается от него тем, что таблица частот не вычисляется по тексту, а используется некоторая ранее вычисленная таблица. Соответственно, для динамического алгоритма требуется два прохода по тексту, первый для построения таблицы, второй ? для кодирования. Для статического алгоритма требуется только один проход, т.к. таблица уже есть.
Естественно, при использовании статического алгоритма возникает риск того, что алгоритм будет не эффективен из-за несоответствия реальных частот и значений в таблице.
Тем не менее иногда статический алгоритм можно применять, например, известно, что в обычных текстах, например художественная литература, журналы, частоты символов как правило примерно одинаковые для различных текстов.
Адаптивный алгоритм мы не рассматриваем здесь. Вкратце можно сказать, что в этом алгоритме также используется один проход, но при этом дерево постоянно перестраивается, т.е. меняются коды символов.
Замечание: в литературе часто рассматривают только два алгоритма Хаффмана, например
1) статический и динамический.
2) динамический и адаптивный.
При этом, когда рассматривают только динамический и адаптивный алгоритмы, часто называют тот алгоритм, который мы здесь называем динамическим как "Статический", а тот, который мы занимаем адаптивным ? "Динамическим". В результате возникает путаница в терминологии ? в разной литературе авторы называют одинаково разные алгоритмы.
Постановка задачи для курса "JScript"
Вход программы: некоторый текст.
Результаты работы программы:
1) таблица частот.
2) код каждого символа.
3) закодированный текст (без кодирования таблицы частот).
4) декодированный текст (с использованием дерева).
Пример
Вход программы: Сжатие Хаффмана
Результат работы программы:
Таблица частот:
С=1
ж=1
а=4
т=1
и=1
е=1
=1
Х=1
ф=2
м=1
н=1
Коды символов:
С=0001
ж=0000
а=01
т=0010
и=0011
е=1011
=1010
Х=111
ф=110
м=1000
н=1001
Закодированный текст:
0001000001001000111011101011101110110100001100101
Декодированный текст:
Сжатие Хаффмана
Пример создания дерева на Jscript
В следующем примере показано, как можно создавать дерево на языке Jscript с помощью объектов.
В примере создается и выводится на экран следующее дерево.
Размещено на http://www.allbest.ru/
Пример кода:
Node = new Object ()
Node. Text = "AB"
Node. Count = 5
Left = new Object ()
Left. Text = "A"
Left. Count = 2
Node. Left = Left
Right = new Object ()
Right. Text = "B"
Right. Count = 3
Node. Right = Right
function WriteTree (Prefix, N)
{
if (N == undefined)
return
WScript. Echo (Prefix + "text: "+N. Text+", count: "+N. Count)
WriteTree (Prefix+" ",N. Left)
WriteTree (Prefix+" ",N. Right)
}
WriteTree (" ",Node)
Данный пример выводит на экран:
text: AB, count: 5
text: A, count: 2
text: B, count: 3
Еще один пример (делает то же самое):
function TreeNode (Text, Count)
{
this. Text = Text
this. Count = Count
}
TreeNode. prototype. WriteTree = function (Prefix)
{
if (Prefix == undefined)
Prefix = " "
WScript. Echo (Prefix + "text: "+
this. Text+", count: "+this. Count)
if (this. Left! = undefined)
this. Left. WriteTree (Prefix+" ")
if (this. Right! = undefined)
this. Right. WriteTree (Prefix+" ")
}
Node = new TreeNode ("AB",5)
Node. Left = new TreeNode ("A",2)
Node. Right = new TreeNode ("B",3)
Node. WriteTree ()
Размещено на Allbest.ru
...Подобные документы
Описание и особенности некоторых алгоритмов архивации. Построение кода Хаффмана. Динамический алгоритм построения кода Хаффмана. Обратное восстановление текста. Способы двухступенчатого кодирования информации. Практическая реализация алгоритма LZ77.
курсовая работа [51,7 K], добавлен 24.12.2012Особенности кодирования информации с помощью метода Хаффмана. Реализация кодера и декодера с использованием статического алгоритма Хаффмана. Структура программы, оценка ее эффективности (степени сжатия) в зависимости от типа и размера сжимаемых файлов.
курсовая работа [136,2 K], добавлен 15.06.2013Оценка вычислительной сложности программы. Реализация алгоритма кодирования информации Хаффмана. Кодировка теста двоичным кодом и в дереве Хаффмана. Бинарный код символов. Символ и частота его появления в тексте. Вычисление трудоемкости алгоритма.
контрольная работа [21,0 K], добавлен 16.12.2012Программная реализация статической нейронной сети Хемминга, распознающей символы текста. Описание реализации алгоритма. Реализация и обучение сети, входные символы. Локализация и масштабирование изображения, его искажение. Алгоритм распознавания текста.
контрольная работа [102,3 K], добавлен 29.06.2010Обзор существующих программ сжатия данных без потерь. Анализ методов сжатия: алгоритмов группы, KWE, Lossless JPEG, кодирование Хаффмана. Обзор составляющих компонентов. Разработка кода программы-архиватора, работающей на основе алгоритма Хаффмена.
курсовая работа [487,3 K], добавлен 14.07.2011Методика и технологический прием структурного программирования; построение алгоритма программы логической задачи в виде блок-схемы из структур "следование, ветвление, цикл"; кодирование текста программы, языки структурного программирования Паскаль и Си.
реферат [623,5 K], добавлен 25.03.2012Составление алгоритма сортировки линейной вставкой. Понятие однонаправленного циклического списка символов, реализация процедуры подсчета суммы элементов и составление алгоритма. Прямое представление дерева, алгоритм работы с ним на абстрактном уровне.
контрольная работа [32,8 K], добавлен 20.01.2012Создание приложения для шифрования–дешифрования текста тремя алгоритмами (алгоритм "Цезаря","Модифицированного Цезаря", "Скитала"). Исходный текст компонента. Инструкция пользователя, возможность просмотра примерного алгоритма. Исходный текст программы.
курсовая работа [2,8 M], добавлен 27.02.2015Основные свойства алгоритма. Формальный и неформальный исполнитель алгоритма, система его команд. Способы записи алгоритма. Словесное описание, построчная запись, опорный конспект. Характеристики алгоритмического языка. Выполнение алгоритма компьютером.
презентация [2,0 M], добавлен 04.04.2014Построение эффективного алгоритма, главными свойствами которого являются детерминированность, массовость, результативность. Применение метода структурного программирования: разделение задачи на относительно независимые части и выполнение отладки частей.
курсовая работа [1,5 M], добавлен 14.11.2010Разработка криптографического алгоритма программы ручного шифра по таблице Виженера. Разработка программы, выполняющей шифрование и расшифрование. Особенности использования в качестве ключа самого открытого текста. Алгоритмы решения "обратных" задач.
курсовая работа [45,0 K], добавлен 13.11.2009Изучение методов кодирования Хаффмана, Фано. Модель информационной системы Шеннона. Среднестатистическая информационная емкость сообщений для эргодических источников с заданным распределением частот символов. Формулы Хартли для удельной емкости на символ.
презентация [528,9 K], добавлен 19.10.2014Двоичные деревья в теории информации. Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Обоснование выбора, описание алгоритма и структур данных. Обоснование набора тестов. Построение оптимального кода. Сущность алгоритма Хаффмана.
курсовая работа [241,6 K], добавлен 17.10.2008Последовательность работ при разработке объектно-ориентированных программ. Виды синтаксических анализаторов и способы их применения. Описание алгоритма и анализ результативности работы программы, написанной на языке С, ее константы, переменные и функции.
курсовая работа [441,7 K], добавлен 03.07.2011Кодирование информации в двоичном коде. Разработка приложения, реализующего следующее преобразование текста: каждая буква исходного текста заменяется третьей после нее буквой в алфавите, который считается написанным по кругу. Алгоритм работы программы.
курсовая работа [1,2 M], добавлен 20.12.2015Форматирование текста с помощью HTML. Задание цвета на веб-странице. Задание размера шрифта. Физическое и логическое форматирование символов. Вставка специальных символов. Удобочитаемость, содержание и форма шрифта. Подбор шрифта и верстка текста.
курсовая работа [1,3 M], добавлен 01.10.2014Возможности создания и обработки графики. Алгоритм шифрования текста в графику. Изменения цветовых каналов. Инициализация объектов html-сущностей. Формирование декодированной строки. Инструменты для обработки массивов, текстовых данных и графики.
курсовая работа [50,5 K], добавлен 26.11.2013Хранение важной информации в ненадежных источниках и передача ее по незащищенным каналам связи. Восстановление шифрованных данных. Программа реализующая шифрование текстового массива. Кодирование информации методом Цезаря. Описание алгоритма Атбаш.
курсовая работа [1,1 M], добавлен 18.01.2013Понятие и свойства алгоритма, виды, характеристики. Роль алгоритма в построении программы, представление и запись. Словесный, графический, табличный способ. Псевдокод. Примеры известных алгоритмов. Операции над массивами. Уточнение корней уравнения.
курсовая работа [1,1 M], добавлен 10.11.2016Разработка программы шифрования данных с использованием алгоритма DES. Структура алгоритма, режимы его работы. Электронный шифровальный блокнот. Цепочка цифровых блокнотов. Цифровая и внешняя обратная связь. Структура окна: функции основных кнопок.
лабораторная работа [830,3 K], добавлен 28.04.2014
