Тезисы лекции Дәрістер тезистері Аbstracts of lectures про уа 03-09-20 Стр из 67
Кодирование по алгоритму Хаффмена
жүктеу/скачать 99,96 Kb.
|
- Бұл бет үшін навигация:
- Алгоритм Хаффмена для символьных групп
Кодирование по алгоритму ХаффменаМеждународный консультативный комитет по телефонии и телеграфии (CCITT) разработал серию протоколов для факсимильной передачи изображений. Эти протоколы основываются на алгоритме, предложенном Д. Хаффменом в 1952г., и используются для обработки черно-белых изображений. Метод Хаффмена строит таблицы кодов, базирующихся на частоте повторения элементов. Чем чаще встречается тот или иной элемент, тем короче будет заменяющий его код. Степень сжатия 2:1 и 3:1. По алгоритму Хаффмена для сжатия файла необходимо прочитать его полностью и подсчитать сколько раз встречается каждый элемент, подлежащий кодированию. //Этот алгоритм разрабатывался для факсовых передач черно-белых изображений передачи данных. Также называется кодирование по алгоритму Хаффмана. Он является неадаптивным, то есть не настраивается для кодирования каждого реестра оптимальным образом , используется фиксирование таблицы кодовых значений , которые были выбраны заранее для представления данных в степень сжатия по этим алгоритмам 5:1-8:1. Кодирование: Кодировщик определяет длину пиксельных групп в строке развертке и выводит двоичное кодовое слово, представляющее длину и цвет группы . Кодированное слова берутся из таблицы значений представляемых группами белых и черных пикселей. Двоичное кодовое слово по этому алгоритму бывает переменной длины. Размер каждого слова определяется на основе статистически усредненной частоты черно-белых групп, появляется в течение печатных документов. Длины групп, встречающиеся наиболее часто, присваивается наименьшее кодированное слово , чем длины групп, которые появляются менее часто.// Алгоритм Хаффмена для символьных группПодсчитаем вхождение каждого символа в файл и получим следующие характеристики Файл длиной 100 байт, имеет различные символы, длина каждого 1 байт.
на 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. жүктеу/скачать 99,96 Kb. Достарыңызбен бөлісу:
|