аффмана.
Нехай повідомлення вхідного алфавіту A {a1, a2, a3 ... ak} мають відповідно ймовірності їх появи p1, p2, p3 ... pk.
Тоді алгоритм кодування Хаффмана полягає в наступному:
. Повідомлення розташовуються в стовпець спадний ймовірності їх появи. p>. Два самих малоймовірних повідомлення об'єднуємо в одне повідомлення b, яке має ймовірність, що дорівнює сумі ймовірностей повідомлень ak-1, ak тобто pk-1 + pk. В результаті отримаємо повідомлення a1, a2, a3 ... ak-1, b, ймовірності яких p1, p2, p3 ... pk-2, pk-1 + pk. p>. Повторюємо кроки 1 і 2 до тих пір, поки не отримаємо єдине повідомлення, ймовірність якого дорівнює 1. p>. Проводячи лінії, що об'єднують повідомлення і утворюють послідовні підмножини, отримуємо дерево, в якому окремі повідомлення є кінцевими вузлами. Відповідні їм кодові слова можна визначити, приписуючи правим гілкам об'єднання символ 1, а лівим - 0. Втім, поняття праві і ліві гілки в даному випадку відносні (Мал. 3.2.2). br/>В
Рис. 3.2.2 Алгоритм Хаффмана
На підставі отриманої таблиці можна побудувати кодове дерево малюнок 3.2.3:
В
Рис. 3.2.3 Кодова дерево
Так як в процесі кодування повідомленнями зіставляються тільки кінцеві вузли, отриманий код є префіксним, і завжди однозначно декодуємо.
При рівномірних кодах одиночна помилка в кодової комбінації приводить до неправильного декодуванню тільки цієї комбінації. Одним із серйозних недоліків префіксних кодів є поява треку помилок, тобто одиночна помилка в кодової комбінації, за певних обставин, здатна привести до неправильного декодуванню не тільки даної, а й кількох наступних кодових комбінацій.
Арифметичне кодування
Ще одним методом кодування є арифметичне кодування.
Арифметичне кодування є методом, що дозволяє стиснути символи вхідного алфавіту без втрат за умови, що відомий розподіл частот цих символів і є найбільш оптимальним, тому досягається теоретична межа ступені стиснення. Передбачувана необхідна послідовність символів, при стисненні методом арифметичного кодування розглядається як деякий двійковий дріб з інтервалу [0,1). Результат стиснення представляється як послідовність двійкових цифр із запису цього дробу. Ідея методу полягає в наступному: початковий текст розглядається як запис цього дробу, де кожен вхідний символ є "цифрою" з вагою, пропорційним ймовірності його появи. Цим пояснюється інтервал, відповідний мінімальної і максимальної ймовірності появи символу в потоці. Пояснимо роботу методу на прикладі. p> Математично процес описується таким чином:
Кодування:
. Межі робочого інтервалу d0 і u0 спочатку рівні 0 і 1 відповідно. Довжина робочого інтервалу? 0 = 1. p>. Визначаємо нижню межу робочого інтервалу (тобто кордони першого закодованого повідомлення):
i = di-1 + Qi В·? i-1
І верхню межу:
ui = di-1 + Qi? i-
де Qi - кордон кодованого повідомлення ...
