Категория
Информатика
Тип
реферат
Страницы
8 стр.
Дата
13.04.2013
Формат файла
.html — Html-документ
Архив
381802.zip — 6.29 kb
Оцените работу
Хорошо  или  Плохо


Текст работы

«Коды без памяти. Коды Хаффмена. Коды с памятью» МИНСК, 2009 Коды без памяти. Коды Хаффмена Простейшими кодами, на основе которых может выполняться сжатие данных, являются коды без памяти. В коде без памяти каждый символ в кодируемом векторе данных заменяется кодовым словом из префиксного множества двоичных последовательностей или слов. Префиксным множеством двоичных последовательностей

S называется конечное множество двоичных последовательностей, таких, что ни одна последовательность в этом множестве не является префиксом, или началом, никакой другой последовательности в S. К примеру, множество двоичных слов S1 = {00, 01, 100, 110, 1010, 1011} является префиксным множеством двоичных последовательностей, поскольку, если проверить любую из 30 возможных совместных комбинаций (wi wj) из S1, то видно, что wi никогда не явится префиксом (или началом) wj.

С другой стороны, множество S2 = { 00, 001, 1110 } не является префиксным множеством двоичных последовательностей, так как последовательность 00 является префиксом (началом) другой последовательности из этого множества - 001. Таким образом, если необходимо закодировать некоторый вектор данных X = ( x1, x2,… xn ) с алфавитом данных A размера k, то кодирование кодом без памяти осуществляется следующим образом: - составляют полный список символов a1, a2, aj ,ak алфавита

A , в котором aj - j-й по частоте появления в X символ, то есть первым в списке будет стоять наиболее часто встречающийся в алфавите символ, вторым – реже встречающийся и т.д.; - каждому символу aj назначают кодовое слово wj из префиксного множества двоичных последовательностей S; - выход кодера получают объединением в одну последовательность всех полученных двоичных слов. Формирование префиксных множеств и работа с ними – это отдельная серьезная тема из теории множеств,



Ваше мнение



CAPTCHA