Розглянемо новий алфавіт A₁ = {a₁, …, a_n-2, a´} із розподілом ймовірностей P₁ = {p₁, …, p_n-2, p´}, де p´ = p_n-1 + p_n. Його одержано з алфавіту A об'єднанням двох найменших букв a_n-1 та a_n в одну букву а´ з ймовірністю p´ = p_n-1 + p_n. Говорять, що A₁ отримано стисненням алфавіту A.

Нехай для алфавіту A₁ побудовано схему ₁ з елементарними кодами ₁, ₂, …, _n-2, ´. Схемі ₁ можна поставити у відповідність схему  з елементарними кодами ₁, ₂, …, _n-2, _n-1, _n для початкового алфавіту A, узявши _n-1 = ´0, _n = ´1 (тобто елементарні коди _n-1 та _n одержують з елементарного коду  приписуванням справа відповідно 0 та 1). Процедуру переходу від ₁ до  називають розщепленням.

Теорема 21.7 (без доведення). Якщо схема ₁ оптимальна для алфавіту A₁, то схема  оптимальна для алфавіту A.

З цієї теореми випливає такий метод побудови оптимальної схеми алфавітного кодування. Спочатку послідовно стискають алфавіт A до отримання алфавіту з двох букв, оптимальна схема кодування для якого очевидна: першу букву кодують символом 0, другу – символом 1. Потім послідовно розщеплюють одержану схему. Очевидно, що отримана в результаті схема префіксна.

Цей метод кодування запропоновано 1952 р. американським математиком Д. Хаффманом.

Розглянемо використання цього алгоритму для попереднього прикладу з розділу 21.3. У процесі побудуємо так зване дерево Хаффмана. Це є бінарне дерево, що відповідає оптимальному коду, яке будується знизу вгору, починаючи з |A| = n листків за n – 1 крок (злиття). Під час кожного кроку (злиття) дві вершини з найменшими ймовірностями об'єднуються однією вершиною вищого рівня, яка буде мати ймовірність, що дорівнює сумі ймовірності початкових двох вершин. При цьому нові ребра позначають 0 та 1.

Збудоване дерево зображено на рис. 21.2.

Після застосування алгоритму отримуємо таку схему кодування:

Буква	Код
a	00
b	010
c	111
d	10
e	011
f	110

Середня довжина побудованого коду, як і у випадку алгоритму Шенона-Фано, становить 0,232 + 0,183 + 0,083 + 0,232 + 0,163 + 0,123 = 2,54.

---

Рис. 21.2

21.5. Стиск даних

Припустимо, що маємо деяке повідомлення, яке закодовано деяким загально прийнятим способом (для текстів це, наприклад, код ASCII) і зберігається в пам’яті комп’ютера. Відмітимо, що рівномірне кодування не є оптимальним для текстів. Дійсно, в текстах зазвичай використовується значно менше, ніж 256 символів (в залежності від мови – приблизно 60-80 з урахуванням розділових знаків, цифр, малих та великих літер). Крім того, ймовірності появи букв різні і для кожної природної мови відомі (з деякою точністю) частоти появи букв у тексті. Таким чином, можна задатися деяким набором букв та частотами їх появи у тексті і за допомогою алгоритмів Шенона-Фано або Хаффмана побудувати оптимальне алфавітне кодування текстів (для заданих алфавіту та мови). Прості підрахунки показують, що таке кодування для розповсюджених природних мов буде мати ціну кодування дещо меншу за 6, тобто дає виграш у порівнянні з кодом ASCII на 25% або дещо більше.

Відомо також, що практичні програми стиснення даних мають значно більші показники: при стисненні текстових документів коефіцієнт стиску досягає 70% й більше. Це означає, що у таких програмах використовується не алфавітне кодування.

Розглянемо наступний спосіб кодування.

1. Висхідне повідомлення за деяким алгоритмом розбивається на послідовності символів, які називаються словами (слово може мати одно або декілька входжень у висхідний текст повідомлення).

2. Отримана множина слів вважається буквами нового алфавіту. Для цього алфавіту будується роздільна схема алфавітного кодування (рівномірного кодування або оптимального кодування, якщо для кожного слова підрахувати кількість входжень у текст). Отримана схема зазвичай називається словником, тому що вона співставляє слову код.

3. Далі код повідомлення будується як пара – код словника та послідовність кодів слів з цього словника.

4. При декодуванні висхідне повідомлення відновлюється шляхом заміни кодів слів на слова зі словника.

Наприклад, нехай потрібно кодувати тексти на українській мові. В якості алгоритму розділення на слова візьмемо природні правила мови: слова відокремлюються одне від одного пробілами або розділовими знаками. Можна прийняти припущення, що в кожному конкретному тексті мається не більше 2¹⁶ різних слів (зазвичай набагато менше). Таким чином, кожному слову можна співставити номер – ціле число з двох байтів (рівномірне кодування). Оскільки в середньому слова української мови складаються більше ніж з двох букв, то таке кодування дає суттєве стиснення тексту (близько 75% для звичайних текстів української мови). Якщо текст достатньо великий (сотні тисяч або мільйони букв), то додаткові витрати на збереження словника виявляються порівняно невеликими.

Вказаний метод можна вдосконалити наступним чином. На кроці 2 слід застосовувати алгоритм Хаффмена або Шенона-Фано для побудови оптимального коду, а на кроці 1 – вирішувати екстремальну задачу розбиття тексту на слова таким чином, щоб серед всіх можливих розбиттів обрати те, яке дає найменшу ціну кодування на кроці 2. Таке кодування буде «абсолютно» оптимальним. Нажаль, вказана екстремальна задача дуже трудомістка, тому на практиці не використовується – час на попередню обробку великого тексту виявляється надто великим.

---

21.6. Алгоритм Лемпела-Зіва-Велча

Алгоритм Лемпела-Зіва-Велча (LZW) був опублікований Велчем у 1984 році в якості покращення реалізації алгоритму LZ78, який опублікували Лемпел та Зів у 1978 році. Він не є обов’язково оптимальним, тому що не проводить ніякого початкового аналізу даних.

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

Словник будується під час кодування наступним чином: певним послідовностям символів (словам) ставляться у відповідність групи бітів фіксованої довжини (звичайно 12-бітні). Словник ініціалізується усіма 1-символьними рядками (у випадку 8-бітових рядків – це 256 записів). Під час кодування, алгоритм переглядає текст символ за символом, та зберігає кожний новий, унікальний 2-символьний рядок у словник у вигляді пари код/символ, де код посилається у словнику на відповідний перший символ. Після того, як новий 2-символьний рядок збережений у словнику, на вихід передається код першого символу. Коли на вході зчитується черговий символ, для нього у словнику знаходиться рядок, який вже зустрічався і який має максимальну довжину, після чого у словнику зберігається код цього рядка з наступним символом на вході; на вихід видається код цього рядка, а наступний символ використовується в якості початку наступного рядка.

Розглянемо приклад. Нехай маємо алфавіт , який складається тільки з великих літер латинського і допоміжного символу # - маркер кінця повідомлення:  = {A, B, C,…, Z, #}. Таким чином, в алфавіті є 27 символів. Для представлення кожного символу алфавіту  нам достатньо 5 бітів. 5-бітні групи дають 2⁵ = 32 можливих комбінації біт, тому, коли у словнику з’явиться 33-е слово, алгоритм має перейти до 6-бітових груп.

Розглянемо кодування рядку із символів алфавіту :

TOBEORNOTTOBEORTOBEORNOT#

Початковий словник буде містити:

# = 00000

A = 00001

B = 00010

C = 00011

…

Z = 11010

Без використання алгоритму LZW повідомлення при передачі як воно є – 25 символів по 5 бітів кожний – воно займе 125 бітів. Порівняємо це з тим, що отримується при використанні алгоритму LZW (табл. 21.2).

Символ	Бітовий код (на виході)	Новий запис словнику
T	20 = 10100	27: TO
O	15 = 01111	28: OB
B	2 = 00010	29: BE
E	5 = 00101	30: EO
O	15 = 01111	31: OR
R	18 = 010010	32: RN
N	14 = 001110	33: NO
O	15 = 001111	34: OT
T	20 = 010100	35: TT
TO	27 = 011011	36: TOB
BE	29 = 011101	37: BEO
OR	31 = 011111	38: ORT
TOB	36 = 100100	39: TOBE
EO	30 = 011110	40: EOR
RN	32 = 100000	41: RNO
OT	34 = 100010	42: OT#
#	0 = 000000

---

Табл. 21.2.

Таким чином, використовуючи LZW ми скоротили повідомлення на 28 біт з 125 – це майже 22%. Якщо повідомлення буде довшим, то елементи словнику будуть представляти все більш й більші довші частини тексту, завдяки чому слова, які повторюються, будуть представлені дуже компактно.

---

Смотрите также файлы

• 22_Koduvannya_stiyke_do_zavad.doc

• 30_Algoritmi_poshuku_naykorotshikh_shlyakhiv.doc

• 35_Merezhi_ta_potoki.doc

• 37_Gramatiki.doc

• 38_Skinchenni_avtomati.doc