вхідного тексту - як наслідок, однопроходний алгоритм;
В· дерево Хаффмана для таких джерел може бути представлено у вигляді вектора з декількох байтів, кожен з яких позначає кількість кодів дерева певної довжини (див. Завдання), наприклад: запис 1,1,0,2,4 говорить про те, що в дереві є по одному коду довжин 1 і 2 біти, 0 кодів довжиною 3 біти, 2 коду довжиною 4 біта і 4 коду довжиною 5 біт. Сума всіх чисел у записі дасть кількість символів в алфавіті.
Основне застосування: універсальний, стиснення текстів і бінарної інформації. Динамічний алгоритм побудови коду Хаффмана використовується в архіватор ICE, статичний - у LHA, ARJ. Статичний алгоритм Шеннона-Фано використовується архіватором PKZIP. Застосовується для стиснення зображень (формат JPEG). p align="justify"> алгоритм архівація код Хаффман
АлгорітмСтепень сжатіяСко-ростьПамятьСжатіе без потерьПро-ходиРОВІХаффмен статіч.5-688Да2ДаРедкоХаффмен дінаміч.4-567Да1ДаРедкоХаффмен фіксір.3-699Да1ДаВозм.Монотон.3-489Да1ДаВозм.
3) Метод В«стопки книгВ» (MTF).
Порівняно недавно з'явився ще один різновид адаптивного алгоритму Гоффмана, описана Рябко, а потім Бентлі і названа, відповідно, алгоритмом стопки книг або довгий вгору ( MTF-Move To Front ). Кожному символу (букві) присвоюється код залежно від його положення в алфавіті - чим ближче символ до початку алфавіту - тим коротше код (в якості коду можна використовувати, наприклад, код дерева для монотонних джерел). Після кодування чергового символу ми поміщаємо його на початок алфавіту, зрушуючи всі інші літери на одну позицію вглиб. Через деякий час найбільш часто зустрічаються символи згрупуються на початку, що й потрібно для успішного кодування. Робота алгоритму, дійсно, нагадує перекладання найбільш потрібних книг з глибин бібліотеки ближче до верху, внаслідок чого потім їх буде легше знайти (аналогія з повсякденною життям).
АлгорітмСтепень сжатіяСко-ростьПамятьСжатіе без потерьПро-ходиРОВІСтопка кніг3-578Да1ДаВозм.
4) Арифметичне кодування.
Арифметичне кодування є методом, що дозволяє стиснути символи вхідного алфавіту без втрат за умови, що відомий розподіл частот цих символів. Арифметичне кодування є оптимальним, досягаючи теоретичної границі ступеня стиснення H0. Однак, коди Хаффмана у попередньому розділі ми теж називали оптимальними. Як пояснити цей парадокс? Відповідь полягає в наступному: коди Хаффмана є неблочнимі, т.е кожній букві вхідного алфавіту ставиться у відповідність певний вихідний код. Арифметичне кодування-блокове і вихідний код є унікальним для кожного з можливих вхідних повідомлень; йо...
