Методи стискання інформації: огляд та порівняльний аналіз, Детальна інформація

Методи стискання інформації: огляд та порівняльний аналіз
Тип документу: Реферат
Сторінок: 5
Предмет: Комп`ютерні науки
Автор: фелікс
Розмір: 22.9
Скачувань: 1069
Текст, який стиснено арифметичним кодером, розглядається як деякий двійковий дріб з інтервалу [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% для текстових файлів.

The online video editor trusted by teams to make professional video in minutes