REFERATUA.ORG.UA — База українських рефератів



Головна Інформатика, комп'ютери, програмування → Методи стискання інформації: огляд та порівняльний аналіз

вигляді двійкового дерева, в якому символи знаходяться на листках, а ребра помічені 0 або 1. Тоді код символа можна задати як шлях від кореня дерева до листа, що містить цей символ.

Нехай вхідний алфавіт складається з чотирьох символів: a, b, c, d, частоти яких відповідно дорівнюють 1/2, 1/4, 1/8, 1/8.

Кодування Хаффмена для цього алфавіта подається таблицею 1.

Символ

Частота

Вхідне кодування

Вихідне кодування

A

1/2

00

0

B

1/4

01

10

C

1/8

10

110

D

1/8

11

111

Таб. 1. Кодування Хаффмена.

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

Мал. 1. Дерево Хаффмена.

Наприклад, кодом ланцюжка abaaacb, поданого на вході як

00 01 00 00 00 10 01

буде

0 10 0 0 0 110 10

(проміжки додано для зручності читання). Отже, 14 біт на вході дали 11 біт на виході – стискання очевидне! На мал. 1 подано двійкове дерево Хаффмена для наведеного коду.

При використанні адаптивного кодування Хаффмена необхідно постійно коректувати дерево у відповідності до статистики вхідного потоку, яка весь час змінюється. Під час реалізації, як правило, вимагаються значні витрати на балансування кодового дерева відповідно до нових частот символів на кожному кроці.

Перевагами методу Хаффмена є його досить висока швидкість і так само висока якість стискання. Цей алгоритм порівняно давно відомий і є на сьогодні дуже розповсюдженим: прикладами є програма compact OC UNIX (програмна реалізація), а також стандарт кодування факсів (апаратна реалізація).

Кодування Хаффмена має мінімальну надлишковість за умови, що кожний символ кодується окремим ланцюжком в алфавіті {0,1}.

Недоліком кодування Хаффмена є залежність коефіцієнту стискання від близькості імовірностей символів до від'ємних ступенів 2; це пов'язано з тим, що кожен символ кодується цілою кількістю біт. Найбільш помітно це під час кодування двосимвольного алфавіту: в цьому випадку стискання неможливе, незважаючи на відмінності імовірностей символів; алгоритм фактично "округляє" їх до 1/2!

Цю проблему можна частково вирішити за рахунок блокування вхідного потоку (тобто включення до розгляду нових символів вигляду "ab", "abc",..., де a, b, c – символи початкового алфавіту). Однак це не дозволяє повністю позбутися втрат (вони лише зменшуються пропорційно розміру блока) і призводить до стрімкого росту кодового дерева: якщо, наприклад, символами вхідного алфавіту є 8-бітові байти зі значеннями 0...255, то при блокуванні по два символи ми отримуємо алфавіт (і кодове дерево!) із 65536 символів, а при блокуванні по три – 16777216! Таким чином, зростають вимоги до пам'яті та час побудови дерева (а у випадку адаптивного кодування – і час поновлення дерева, а звідси і час стискання).

Втрати ж складатимуть у середньому 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, переданий кодером) знаходиться в першому з них, можна отримати перший символ: а. Потім ділимо перший


 
Загрузка...