зково повинні кодуватися в префіксному вигляді, щоб декодировщик міг розрізнити їх у вихідному потоці:
06 05 02 01 06 03 01 5 Січень 3 квітня FF
Довжина-12 байт, ступінь стиснення-60%.
Можливий варіант алгоритму, коли замість довжини length кодується позиція щодо початку тексту distance першого символу, що відрізняється від попереднього. Для нашого прикладу це буде вихідна рядок виду:
01 05 07 01 09 03 0F 10 травня 11 Березня FF
Висновки
АлгорітмСтепень сжатіяСко-ростьПамятьСжатіе без потерьПро-ходиРОВІRLE2-31010Да1НетВозм.
Тут і далі прийняті наступні позначення: РВ - поширення помилки, ВІ - зростання надмірності. Ступінь стиснення, швидкість і використовувана оперативна пам'ять оцінюються за десятибальною системою з точки зору автора. Чим більше величина, тим краще вказаний параметр (вище швидкість роботи, вище ступінь стиснення і менша споживана пам'ять). p align="justify"> Робота: в реальному масштабі часу і в потоці.
Основне застосування: РСХ, стиснення зображень.
2) Коди Хаффмана.
Найбільш ефективним кодом змінної довжини, у якій жодне слово не співпадає з початком іншого (тобто префіксний код) є код Хаффмана.
Нехай l1, ..., lk-позитивні цілі числа (k> 0). Для того, щоб існував префіксний код, довжини слів якого рівні l1, ..., lk, необхідно і достатньо виконання нерівності Крафта:
В
Всі префіксние коди є кодами з властивістю однозначного декодування, але не навпаки (наприклад, однозначно декодіруемий код 0, 01, 011, 0111, ... не є префіксним). Надмірність дешіфріруемого кодування неотрицательна. Для коду Гоффмана (Шеннона) надмірність не перевищує 1, тобто 0 ВЈ R ВЈ 1. Довжина коду Шеннона дорівнює
| ai | = Г©-log (p (ai)) Г№,
а довжина коду Хаффмана не перевищує величини | ai |.
Звідси, зокрема випливає висновок, що чим більше довжина Т символів вхідного алфавіту (для якого будується код Хаффмана), тим менше надмірність вихідного тексту і тим вище ступінь стиснення. Однак, як буде видно надалі, при цьому значно зростають вимоги до пам'яті даних і до швидкодії програми, оскільки кількість кодів дорівнює кількості символів вихідних букв. Надмірність коду Хаффмана значною мірою залежить, як випливає з наведеної формули, від того, на скільки ймовірності появи символів близькі до негативних ступенями числа 2. Для двохсимвольного алфавіту, наприклад, код Хаффмана ніколи не зможе дати скорочення надмірності, нехай навіть ймовірності розрізняються на декілька порядків. p> Розглянемо побудову коду Хаффмана на простому прикладі:
нехай є текст ABACCADAА. При кодуванні двійковим кодом постійної довжини вид...
