Реферат: Коды без памяти. Коды Хаффмена. Коды с памятью

Коды без памяти. Коды Хаффмена

Простейшими кодами, на основе которых может выполняться сжатие данных, являются коды без памяти. В коде без памяти каждый символ в кодируемом векторе данных заменяется кодовым словом из префиксного множества двоичных последовательностей или слов.

Префиксным множеством двоичных последовательностей S называется конечное множество двоичных последовательностей, таких, что ни одна последовательность в этом множестве не является префиксом, или началом, никакой другой последовательности в S .

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

Таким образом, если необходимо закодировать некоторый вектор данных X = ( x ₁ , x ₂ ,… x_n ) с алфавитом данных Aразмера k , то кодирование кодом без памяти осуществляется следующим образом:

- составляют полный список символов a₁ , a₂ , a_j ... ,a_k алфавита A, в котором a_j - j -й по частоте появления в X символ, то есть первым в списке будет стоять наиболее часто встречающийся в алфавите символ, вторым – реже встречающийся и т.д.;

- каждому символу a_j назначают кодовое слово w_j из префиксного множества двоичных последовательностей S ;

- выход кодера получают объединением в одну последовательность всех полученных двоичных слов.

Формирование префиксных множеств и работа с ними – это отдельная серьезная тема из теории множеств, выходящая за рамки нашего курса, но несколько необходимых замечаний все-таки придется сделать.

Если S = { w₁ , w₂ , ... , w_k } - префиксное множество, то можно определить некоторый вектор v(S) = ( L₁ , L₂ , ... , L_k ), состоящий из чисел, являющихся длинами соответствующих префиксных последовательностей (L_i - длина w_i ).

Вектор (L₁ , L₂ , ... , L_k ), состоящий из неуменьшающихся положительных целых чисел, называется вектором Крафта. Для него выполняется неравенство

. (1)

Это неравенство называется неравенством Крафта. Для него справедливо следующее утверждение: если S - какое-либо префиксное множество, то v(S) - вектор Крафта.

Иными словами, длины двоичных последовательностей в префиксном множестве удовлетворяют неравенству Крафта.

Если неравенство (1) переходит в строгое равенство, то такой код называется компактным и обладает наименьшей среди кодов с данным алфавитом длиной, то есть является оптимальным.

Ниже приведены примеры простейших префиксных множеств и соответствующие им векторы Крафта:

S1 = {0, 10, 11} и v(S1) = ( 1, 2, 2 );

S2 = {0, 10, 110, 111} иv(S2) = ( 1, 2, 3, 3 );

S3 = {0, 10, 110, 1110, 1111} иv(S3) = ( 1, 2, 3, 4, 4 );

S4 = {0, 10, 1100, 1101, 1110, 1111} иv(S4) = ( 1, 2, 4, 4, 4, 4 );

S5 = {0, 10, 1100, 1101, 1110, 11110, 11111} иv(S5) = ( 1, 2, 4, 4, 4, 5, 5 );

S6 = {0, 10, 1100, 1101, 1110, 11110, 111110, 111111}

иv ( S 6) = (1,2,4,4,4,5,6,6).

Допустим мы хотим разработать код без памяти для сжатия вектора данных X = ( x ₁ , x ₂ ,… x_n ) с алфавитом Aразмером в k символов. Введем в рассмотрение так называемый вектор частот F = ( F₁ , F₂ , ... , F_k ), где F_i - количество появлений i -го наиболее часто встречающегося символа из A в X . Закодируем X кодом без памяти, для которого вектор Крафта L = ( L₁ , L₂ , ... , L_k ) .

Тогда длина двоичной кодовой последовательности B(X) на выходе кодера составит

L*F = L₁ *F₁ + L₂ *F₂ + ... + L_k *F_k . (2)

Лучшим кодом без памяти был бы код, для которого длина B(X) - минимальна. Для разработки такого кода нам нужно найти вектор Крафта L, для которого произведение L*F было бы минимальным.

Простой перебор возможных вариантов - вообще-то, не самый лучший способ найти такой вектор Крафта, особенно для большого k .

Алгоритм Хаффмена, названный в честь его изобретателя - Дэвида Хаффмена, - дает нам эффективный способ поиска оптимального вектора Крафта L для F , то есть такого L , для которого точечное произведение L*F – минимально. Код, полученный с использованием оптимального L для F , называют кодом Хаффмена.

Алгоритм Хаффмена

???????? ???????? ?????? ????????? ????? ???? ??????????????? ??????????? ? ?????????????? ?????????? ???????? ? ???????? ????????? ???????:1. ?????????? ? ??? ??? ??????? ???????? ? ??????? ??????????? ??? ???????? ??????????? ?? ????????? ? ??????.2. ??????????????? ?????????? ??? ??????? ? ??????????? ????????????? ????????? ? ????? ????????? ??????, ??????????? ????????? ???????? ???????? ?????? ????? ???????????? ???????????? ??? ????????. ? ????? ?????? ???????? ??????, ?????? ???? ???????? ????? ????????? ??????????? ???? ?????, ??????????? ???? ????.3. ???????????? ???? ? ??????? ????? ??????, ??????? ??????????? ? ??????? ???? (????????, ??????? - 1, ?????? - 0) . ?????????? ?????????????????? ???? ??????? ?????, ??????????????? ??????? ??????? (???. 1). ???????? ??????? ?????? ??? ????????? ?? ????????? ?????????: A B C D E 10 5 8 13 10B C A E D 5 8 10 10 13A E BC D 10 10 13 13BC D AE 13 13 20AE BCD 20 26AEBCD 46

--> ЧИТАТЬ ПОЛНОСТЬЮ <--