Втрати ж складатимуть у середньому 1/2 біт на символ при відсутності блокування, а за його наявності – 1/4 і 1/6 біт для блоків довжини 2 та 3 відповідно. Великий коефіцієнт стискання, що не залежить від близькості значень імовірностей символів до степенів 1/2, може дати так зване арифметичне кодування.
Арифметичне кодування – це метод, що дозволяє стискати символи вхідного алфавіту без втрат за умови, що відомий розподіл частот цих символів. Концепцію методу наведено у роботах Еліаса в 60-х роках. Пізніше метод було розвинено та значно модифіковано.
Арифметичне кодування є оптимальним, досягаючи теоретичної границі стискання – ентропії вхідного потоку.
Текст, який стиснено арифметичним кодером, розглядається як деякий двійковий дріб з інтервалу [0,1). Результат стискання можна подати як послідовність двійкових цифр із цього дробу.
Ідея методу полягає в наступному: початковий текст розглядається як запис цього дробу, де кожен вхідний символ є “цифрою” з вагою, що пропорційна ймовірності його появи. Пояснимо роботу кодера на прикладі.
Нехай алфавіт складається із двох символів: a та b з імовірностями відповідно 3/4 та 1/4. Як вже згадувалося вище, кодування Хаффмена не може стискати слова в даному алфавіті.
Розглянемо (відкритий справа) інтервал [0,1). Розіб’ємо його на частини, довжина яких пропорційна імовірностям символів. В нашому випадку це – [0, 3/4) i [3/4, 1). Принцип дії алгоритму полягає в наступному: кожному слову в початковому алфавіті відповідає певний підінтервал із [0,1). Порожньому слову відповідаю весь інтервал [0,1). Після отримання кожного наступного символу арифметичний кодер зменшує інтервал, обираючи ту його частину, яка відповідає символу, що надійшов. Кодом ланцюжка є інтервал, виділений після обробки всіх його символів, а точніше, двійковий запис координати будь-якої точки з цього інтервалу.
Таким чином, довжина отриманого інтервалу пропорційна ймовірності появи кодованого ланцюжка.
Виконаємо алгоритм для ланцюжка aaba (див. табл.2). В якості коду можна взяти будь-яке число з інтервалу, що отриманий на кроці 4, наприклад, 0.1.
| Крок | Ланцюжок, що розглядається | Інтервал |
| 0 | “” | [0,1)=[0,1) |
| 1 | а | [0, 3/4)=[0, 0.11) |
| 2 | аa | [0, 9/16)=[0, 0.1001) |
| 3 | аab | [27/64, 36/64)=[0.011011, 0.100100) |
| 4 | аaba | [108/256,135/256)=[0.01101100, 0.10000111) |
Таб. 2. Арифметичне кодування.
Арифметичний декодер працює синхронно з кодером: почавши з інтервалу [0,1), він послідовно визначає символи вхідного ланцюжка.
Зокрема, в нашому випадку він спочатку поділить (пропорційно частотам символів) інтервал [0,1) на [0, 0.11) та [0.11,1). Оскільки число 0.1 (код ланцюжка аaba, переданий кодером) знаходиться в першому з них, можна отримати перший символ: а. Потім ділимо перший підінтервал [0, 0.11) на [0, 0.1001) та [0.1001, 0.1100) (пропорційно частотам символів). Знову обираємо перший, оскільки 0 < 0.1 < 0.1001. Продовжуючи цей процес, ми однозначно декодуємо всі чотири символи. Для того, щоб декодер зміг визначити кінець ланцюжка, можна або передавати його довжину окремо, або додати до алфавіту символ “кінець ланцюжка”.
Під час реалізації цього методу виникають дві проблеми: по-перше, необхідно використовувати дійсну арифметику необмеженої точності, і по-друге, результат кодування стає відомим лише після закінчення вхідного потоку. Однак, досліди показали, що можна практично без втрат обмежитися цілочисельною арифметикою невеликої точності (16-32 розряди), а також домогтися покрокової (інкрементальної) роботи алгоритми: цифри коду можуть видаватися послідовно під час читання вхідного потоку.
Як вже згадувалося вище, кодування являє собою лише частину процесу стискання. Не менш важливим є т. зв. моделювання (modelling). Ми вже говорили про те, що арифметичне кодування має мінімальну надлишковість за певного розподілу. Але звідки береться цей розподіл? І про який алфавіт йдеться?
Відповіді на ці питання дає модель потоку, що являє собою деякий спосіб передбачення розподілу імовірностей під час надходження кожного наступного символа. Саме кожного, оскільки статичні моделі (у яких розподіл не змінюється в процесі кодування) в більшості випадків не забезпечують максимальної якості стискання.
Значно цікавіші так звані адаптивні моделі, які враховують поточний контекст. Такі моделі дозволяють будувати швидкі однопрохідні алгоритми стискання, що не вимагають апріорних знань про вхідний потік даних і будують розподіл під час роботи. Також виділяють клас “локально адаптивних” алгоритмів, які під час побудови розподілу відмічають більшою вагою частоти останніх символів із тих, що надійшли.
Можливі різні підходи до цієї проблеми: найпростіший з них – збір статистики появи кожного символа незалежно від інших (моделювання лічильником Бернуллі: ймовірність появи символа не залежить від того, які символи зустрілися перед ним). Інший варіант – використання марківської моделі, коли розподіл ймовірностей символів будується з урахуванням деякої кількості попередніх символів (у марківському джерелі першого порядку ймовірність появи першого символа залежить тільки від одного останнього отриманого символа, і т.д.). Марковські моделі дають більш точну картину джерела, але кількість станів у них істотно більша, відповідно більший обсяг таблиць частот, що зберігаються. Окрім того, при використанні кодування Хаффмена вони можуть навіть зменшити ступінь стискання, оскільки ймовірності, що породжуються ними, зазвичай гірше наближуються ступенями 1/2.
Стискання за допомогою купки книжок
Говорячи про моделі вхідного потоку та адаптивні алгоритми стискання, не можна не згадати простий та досить ефективний метод кодування джерела з невідомим розподілом частот, відомий як стискання за допомогою купки книжок.
Метод було вперше відкрито та досліджено Рябко в 1980 р., а потім перевідкрито Бентлі, Слейтером, Тар’яном і Веі в 1986 р.
Ідея методу полягає в наступному: нехай алфавіт джерела складається з N символів із номерами 1,2,.....,N. Кодер зберігає список символів, що являє собою деяку перестановку алфавіту. При надходженні на вхід символа с, що має в цьому списку номер і, кодер передає номер і. Потім кодер переміщує символ с на початок списку, збільшуючи на 1 номери всіх символів, що стояли перед с. Таким чином, найбільш “популярні” символи сконцентруються на початку списку і матимуть коротші коди.
В якості коду для метода купки книжок можна використовувати так званий монотонний код – універсальний код джерела, для якого відома лише впорядкованість імовірностей символів (самі ймовірності невідомі).
Усі методи та моделі кодування, розглянуті вище, розглядали в якості вхідних даних ланцюжки символів (тексти) в деякому нескінченому алфавіті. При цьому залишалося відкритим питання про зв’язок цього вхідного алфавіту кодера з даними, що підлягають стисканню (і представлені у вигляді ланцюжків в (іншому) алфавіті, який зазвичай складається із 256 символів-байтів).
В найпростішому випадку можна використовувати в якості вхідного алфавіту саме ці символи (байти) вхідного потоку. Саме так працює метод squashing програми РКРАК (використане статичне кодування Хаффмена, двопрохідний алгоритм). Ступінь стискання при цьому відносно невеликий – близько 50% для текстових файлів.
Значно якісніше стискання можна отримати виділенням із вхідного потоку ланцюжків, що повторюються, і кодування посилань на ці ланцюжки.
Цей метод, про який піде мова, належить Лемпелю та Зіву і називається LZ77-compression (за роком публікації). Він полягає в наступному: компресор постійно зберігає певну кількість останніх оброблених символів у деякому буфері (який також називається ковзаючим словником – sliding dictionary). Назва “ковзаючий” зумовлена тим, що його довжина постійна: кожного разу, коли компресор кодує наступний ланцюжок, він дописує її в кінець словника та “відрізає” відповідну кількість символів на початку буфера. Під час обробки вхідного потоку символи, що надійшли, потрапляють у кінець буфера, зсуваючи попередні символи та витісняючи найстаріші.
Розміри цього буфера є різними в різних реалізаціях. Очевидно, що використання буфера більших розмірів дозволяє отримати якісніший результат. Алгоритм виділяє (шляхом пошуку в словнику) найдовший початковий підрядок вхідного потоку, що співпадає з одним із підрядків у словнику, і подає на вихід пару (length, distance), де length – довжина знайденого у словнику підрядка, а distance – відстань від нього до вхідного підрядка (тобто фактично індекс підрядка в буфері, віднятий від його розміру). В разі, коли такого підрядка не знайдено, до вихідного потоку просто копіюється черговий символ вхідного потоку.
У найпершій версії алгоритму пропонувалося виконувати найпростіший пошук по всьому словнику. Час стискання за такої реалізації був пропорційний добутку довжини вхідного потоку на розмір буфера, що не є придатним для практичного використання. Але потім було запропоновано використовувати двійкове дерево для пошуку в словнику, що дозволило на порядок збільшити швидкість роботи.