Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Алгоритм Хаффмана на примере
|
|
Алгоритм Хаффмана
Веретенников А. Б. 2008.
https://cs.usu.edu.ru/home/abv/
Алгоритм Хаффмана основывается на том, что символы в текстах как правило встречаются с различной частотой.
При обычном кодировании мы каждый символ записываем в фиксированном количестве бит, например каждый символ в одном байте, или в двух.
Однако, т. к. некоторые символы встречаются чаще, а некоторые реже − можно записать часто встречающиеся символы в небольшом количестве бит, а для редко встречающихся символов использовать более длинные коды. Тогда суммарная длина закодированного текста может стать меньше.
Алгоритм Хаффмана на примере
Закодируем строку " Сжатие Хаффмана"
Вначале нужно подсчитать количество вхождений каждого символа в тексте.
| С | ж | а | т | и | е | Х | ф | м | н | |
Эта таблица называется " таблица частот".
Теперь будем строить дерево
Узел дерева будет образован набором символов и числом - суммарным количеством вхождений данных символов в тексте. Назовем указанное число - весом узла.
Листьями дерева будут узлы, образованные одним символом:
Теперь будем циклически делать следующее:
1) Ищем среди узлов, не имеющих родителя, два узла, имеющих в сумме наименьший вес.
2) Создаем новый узел, его потомками будут два выбранных узла. Его весом будет сумма весов выбранных улов. Его набор символов будет образован в результате объединения наборов символов выбранных узлов.
Создаем первый узел
Создаем еще один узел
Создаем еще один узел
Создаем еще один узел
Создаем еще один узел
Создаем еще один узел
Создаем еще один узел
Создаем еще один узел
Создаем еще один узел
Создаем еще один узел
Теперь для каждого узла, имеющего потомков, пометим дуги, идущие вниз, на одной дуге напишем 0, на другой 1.
Теперь, чтобы получить код символа, надо, начиная с корня дерева идти вниз до листа соответствующего данному символу. При этом следует записывать те значения, которые написаны на тех дугах, которые мы проходим.
Получаются следующие коды
| С | |
| ж | |
| а | |
| т | |
| и | |
| е | |
| Х | |
| ф | |
| м | |
| н |
Заметим, что код является префиксным, т. е. ни один код символа не является префиксом кода другого символа. Также видно, что для часто встречающихся символов коды короче.
Как будет выглядеть закодированная строка:
| С | ж | а | т | и | е | Х | а | ф | ф | м | а | н | а | |
Т. е.
|