Алгоритъм за изчисляване на кодове на Шанън-Фано - Studiopedia
Кодът на Шанън-Фано е изграден с помощта на дърво. Изграждането на това дърво започва от корена. Целият набор от кодирани елементи съответства на корена на дървото (горната част на първото ниво). Той е разделен на две подгрупи с приблизително еднакви общи вероятности. Тези подмножества съответстват на два върха от второ ниво, които са свързани с корена.
Освен това всяко от тези подмножества е разделено на две подмножества с приблизително еднакви общи вероятности. Те съответстват на върховете на третото ниво. Ако подмножеството съдържа един елемент, тогава той съответства на крайния възел на кодовото дърво; такова подмножество не може да бъде разделено. Продължаваме по този начин, докато получим всички крайни върхове. Маркираме разклоненията на кодовото дърво със символите 1 и 0, както в случая с кода на Хъфман.
При конструирането на кода на Шанън-Фано, разделянето на множеството от елементи може да се извърши, най-общо казано, по няколко начина. Изборът на разделяне на ниво n може да влоши опциите за разделяне на следващото ниво (n + 1) и да доведе до неоптимален код като цяло. С други думи, оптималното поведение на всяка стъпка от пътя все още не гарантира оптималността на целия набор от действия.
Следователно кодът на Шанън-Фано не е оптимален в общия смисъл, въпреки че дава оптимални резултати при определени вероятностни разпределения. Най-общо казано, няколко кода на Шанън-Фано могат да бъдат конструирани за едно и също вероятностно разпределение и всички те могат да дадат различни резултати. Ако изградим всички възможни кодове на Шанън-Фано за дадено вероятностно разпределение, тогава сред тях ще има всички кодове на Хъфман, тоест оптимални кодове.
Пример за кодово дърво
Оригинални знаци:
А(честота на поява 50)
B (честота на поява 39)
C (честота на поява 18)
D (честота на поява 49)
E (честота на поява 35)
F (честота на поява 24)
Получен код: A - 11, B - 101, C - 100, D - 00, E - 011, F - 010.
Кодирането на Шанън-Фано е доста стар метод за компресиране и днес не представлява голям практически интерес. В повечето случаи дължината на последователност, компресирана с този метод, е равна на дължината на компресирана последователност, използваща кодирането на Huffman. Но в някои последователности могат да се формират неоптимални кодове на Шанън-Фано, така че методът на компресиране на Хъфман се счита за по-ефективен.
Пример 1. Нека кодираме буквите от азбуката в кода на Шанън-Фано.
Нека има случайна променлива X (x1, x2, x3, x4, x5, x6, x7, x8), имаща осем състояния с вероятностно разпределение
За да кодираме азбука от осем букви, без да отчитаме вероятностите с единен двоичен код, имаме нужда от три знака:
Това е 000, 001, 010, 011, 100, 101, 110, 111
За да отговорите дали този код е добър или не, трябва да го сравните с оптималната стойност, тоест да определите ентропията
След като определихме излишъка L по формулата L=1-H/H0=1-2.75/3=0.084, виждаме, че е възможно да се намали дължината на кода с 8.4%.
Всички букви се записват в низходящ ред на техните вероятности, след което се разделят на еднакво вероятни групи, които се обозначават с 0 и 1, след което отново се разделят на еднакво вероятни групи и т.н. (виж таблица 4.1)
| х | П | Кодове | |
| x1 | 1/4 | ------- | ------- |
| x2 | 1/4 | ------- | ------- |
| х3, | 1/8 | ------- | |
| x4 | 1/8 | ------- | |
| x5 | 1/16 | ||
| x6 | 1/16 | ||
| x7 | 1/16 | ||
| x8 | 1/16 |
Средната дължина на получения код ще бъде равна на
И така, получихме оптималния код. Дължината на този код съвпада с ентропията. Този код се оказа успешен, тъй като вероятностите бяха точно разделени на еднакво вероятни групи.
Да вземем 32 две букви от българската азбука. Честотите на тези букви са известни. Азбуката включва и интервал, чиято честота е 0,145. Методът на кодиране е представен в таблицата
| Писмо | Пи | Код | ||
| ? | 0,145 | - | ||
| О | 0,095 | - | ||
| д | 0,074 | |||
| А | 0,064 | |||
| И | 0,064 | |||
| н | 0,056 | |||
| T | 0,056 | … | … | - |
| с | 0,047 | … | … | |
| . | … | |||
| f | 0,03 |
Средната дължина на този код ще бъде равна на, битове/буква;
Ентропия H=4,42 бита/буква. Ефективността на получения код може да се определи като съотношението на ентропията към средната дължина на кода. Равно е на 0,994. Когато стойността е равна на единица, кодът е оптимален. Ако кодираме с код с еднаква дължина, тогава ефективността ще бъде много по-ниска.
Не намерихте това, което търсихте? Използвайте търсачката:
Деактивирайте adBlock! и обновете страницата (F5)наистина е необходимо