Тезисы лекции Дәрістер тезистері Аbstracts of lectures про уа 03-09-20 Стр из 67


Кодирование по алгоритму Хаффмена



бет23/27
Дата21.10.2022
өлшемі99,96 Kb.
#44753
түріТезисы
1   ...   19   20   21   22   23   24   25   26   27
Байланысты:
Контенты лекции- комп графика

Кодирование по алгоритму Хаффмена


Международный консультативный комитет по телефонии и телеграфии (CCITT) разработал серию протоколов для факсимильной передачи изображений. Эти протоколы основываются на алгоритме, предложенном Д. Хаффменом в 1952г., и используются для обработки черно-белых изображений.
Метод Хаффмена строит таблицы кодов, базирующихся на частоте повторения элементов. Чем чаще встречается тот или иной элемент, тем короче будет заменяющий его код.
Степень сжатия 2:1 и 3:1.
По алгоритму Хаффмена для сжатия файла необходимо прочитать его полностью и подсчитать сколько раз встречается каждый элемент, подлежащий кодированию.
//Этот алгоритм разрабатывался для факсовых передач черно-белых изображений передачи данных. Также называется кодирование по алгоритму Хаффмана.
Он является неадаптивным, то есть не настраивается для кодирования каждого реестра оптимальным образом , используется фиксирование таблицы кодовых значений , которые были выбраны заранее для представления данных в степень сжатия по этим алгоритмам 5:1-8:1.
Кодирование:
Кодировщик определяет длину пиксельных групп в строке развертке и выводит двоичное кодовое слово, представляющее длину и цвет группы . Кодированное слова берутся из таблицы значений представляемых группами белых и черных пикселей. Двоичное кодовое слово по этому алгоритму бывает переменной длины. Размер каждого слова определяется на основе статистически усредненной частоты черно-белых групп, появляется в течение печатных документов. Длины групп, встречающиеся наиболее часто, присваивается наименьшее кодированное слово , чем длины групп, которые появляются менее часто.//

Алгоритм Хаффмена для символьных групп


Подсчитаем вхождение каждого символа в файл и получим следующие характеристики
Файл длиной 100 байт, имеет различные символы, длина каждого 1 байт.



Символ

A

B

C

D

E

F

Число вхожд-ий

10

20

30

5

25

10

на 100 символов


Сначала рассматриваются те символы, которые имеют самую низкую частоту вхождений.


Например D и F или D и A. Для них формируется узел, частота вхождения которого равна сумме частот вхождений этих символов.

A B C D E F


10 20 30 5 25 10
| | | | | |
| | | |______|______|
| | | 15 |
|_____|_____|_________| |
| 25 |___________|
|___| 55
45 |
|__________|
100

Если из вершины дерева идти по левой ветке, то присваиваем значение 0, по правой – 1.


C 10 E 11 B 00 A 010 F 0111 D 0110
Базируется на частоте повторений величин: чем чаще встречается величина, тем короче будет её код.
Существует целая группа протоколов, разработанных с использованием алгоритма Хаффмена. За счет модификации этого алгоритма достигается степень сжатия 4:1 и 5:1.


Достарыңызбен бөлісу:
1   ...   19   20   21   22   23   24   25   26   27




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет