Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Пример 3.1.

Да предположим, че има следната таблица с префикс кодове:

Изисква се за декодиране на съобщението:

00100010000111010101110000110

Декодирането се извършва чрез циклиране на следните действия:

а) отрязва най-левия символ от текущото съобщение, добавя се вдясно от работната кодова дума;

б) сравняват работната кодова дума с кодовата таблица; ако няма съвпадение, преминете към (а);

в) да декодира работната кодова дума, да я изчисти;

г) проверява дали има повече знаци в съобщението; ако да, преминете към (а).

Използването на този алгоритъм дава:

Привеждане на процедурата до края, ние получаваме съобщение: "Мама измие рамката."

По този начин, използването на префикс кодиране ви позволява да направите съобщението по-кратко, тъй като няма нужда да прехвърляте символи. Условието на Fano обаче не създава метод за генериране на префикс код, и по-специално, най-добрия възможен. Разглеждаме две схеми за конструиране на префикс кодове.

Код за префикс на Шанън-Фано

Този вариант на кодиране беше предложен през 1948-1949. каквото и да е R. Fano и C. Shannon, и по тази причина, именувани за тях. Разгледайте схемата в следния пример: да има основна азбука А, състояща се от шест знака a 1 ... и 6 с вероятности за поява в съобщението, съответно, 0,3; 0.2; 0.2; 0.15; 0.1; 0.05. Ние подреждаме тези знаци в таблицата по ред на намаляващи вероятности (виж Таблица 3.2). Разделяме знаците на две групи, така че сумите на вероятностите във всяка от тях да бъдат приблизително равни. В нашия пример първата група ще получи 1 и 2 с сума от вероятности 0,5 - ще им присвоим първата цифра от кода "0". Сумата от вероятностите за останалите четири знака също е 0,5; те ще имат първия знак от кода "1". Ние продължаваме разделянето на всяка група на подгрупи по същата схема, т.е. така че сумите на вероятностите на всяка стъпка в съседни подгрупи ще бъдат възможно най-близки. Резултатът е:

Лесно е да се види от процедурата за изграждане на код, че те отговарят на условието Fano и следователно кодът е префикс. Средната дължина на кода е:

I 1 ( A ) = 2.390 бита. Като замести посочените стойности в (3.5), получаваме излишния код Q ( A, 2) = 0.0249, т.е. около 2.5%. Този код обаче не може да се счита за оптимален, тъй като вероятностите за поява на 0 и 1 не са еднакви (съответно 0,35 и 0,65). Прилагането на посочената строителна схема към руската азбука дава код за излишък от 0.0147.

Префикс код на Huffman

Методът за оптимално префиксно двоично кодиране е предложен от Д. Хафман. Ще обмислим изграждането на кодове на Huffman на същия пример. Създайте нова помощна азбука A 1 , комбинирайки двата знака с най-малки вероятности ( a 5 и a 6 ) и замествайки ги с един знак (например a (1) ); вероятността за нов знак ще бъде равна на сумата от вероятностите на тези, които са включени в нея, т.е. 0.15; останалите знаци от оригиналната азбука ще бъдат включени в новата непроменена; Общият брой символи в новата азбука очевидно ще бъде 1 по-малък от оригинала. По същия начин ще продължим да създаваме нови азбуки, докато в него не останат два знака; ясно е, че броят на тези стъпки ще бъде равен на N - 2, където N е броят на знаците на оригиналната азбука (в нашия случай N = 6, следователно е необходимо да се изградят 4 помощни азбуки). В междинните азбуки всеки път ще пренареждаме знаците с намаляващи вероятности. Цялата процедура на изграждане е представена под формата на таблица:

Сега в обратна посока ще извършим процедурата на кодиране. Нека да зададем кодове 0 и 1 на двата знака от последната азбука (на които човек не играе роля; нека се съгласим, че горният символ ще има код 0, а най-долният - 1). В нашия пример знакът 1 (4) азбука А (4) , имаща вероятност 0,6, ще получи код от 0 и 2 (4) с вероятност 0.4 - код 1. В азбука A (3) знакът 1 (3) получава от 2 (4) вероятността 0.4 и кода (1); кодовете на знаците a 2 (3) и 3 (3) , произхождащи от знака a 1 (4) с вероятност 0.6, вече ще са двуцифрени: първата им цифра ще бъде техният родителски код (т.е. втората цифра - както е договорена - в горната част 0, в долната част - 1; следователно 2 (3) ще има код 00, а 3 (3) - код 01. Процедурата за пълно кодиране е представена в таблицата на стр. 70.

От процедурата за строителни кодове отново е ясно, че те отговарят на условието Fano и следователно не изискват сепаратор. Средната дължина на кода, както в предишния пример, е:

K (A, 2) = 0.3 + 2 + 0.2 2 + 0.2 2 + 0.15 + 3 + 0.1 4 + 0.05 = 4 = 2.45.

Излишъкът отново е равен на Q ( A, 2) = 0.0249, но вероятностите 0 и 1 са се сближили (съответно 0.47 и 0.53). По-високата ефективност на кодовете на Huffman в сравнение с кодовете на Shannon-Fano става очевидна, ако сравним кодовете на излишък за всеки естествен език. Прилагането на описания метод за буквите на руската азбука генерира кодовете, представени в таблица. 3.2. (за удобство на сравнението те са дадени във формата на таблица 3.1).

Таблица 3.2

Средната дължина на кода е равна на K (r , 2) = 4.395; излишък код Q ( r , 2) = 0.0090, т.е. не надвишава 1 %, което е значително по-малко от излишъка на кода на Шанън-Фано (вж. по-горе).

Кодексът на Хафман е теоретично важен, тъй като може да се докаже, че той е най -икономичен от всички възможни, т.е. за всеки метод за кодиране по азбучен ред дължината на кода не може да бъде по-малка от кода на Huffman (вж [49, с.209-211]).

По този начин можем да заключим, че има начин да се изгради оптимален неравномерен азбучен код. Не трябва да се мисли, че той представлява редица теоретични интереси. Методът на Хафман и неговата модификация - адаптивният метод на кодиране (динамично кодиране на Хафман) - намериха широко приложение в програмите за архивиране, архивиране и архивиране на дискове, в системи за компресиране на информация в модеми и факсове.





Вижте също:

Структури от данни и тяхното представяне в RAM

Общата схема на предаване на информация в комуникационната линия

Нормални марковски алгоритми

Пример А.5

Ентропия и информация

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru