днаково оптимальними (середнє число біт, що припадають на один символ для будь-якого такого алфавіту, буде ідентичним). Таким чином, коди Хафмана є оптимальним (найбільш економним), але не єдиним рішенням.
Можливе застосування стандартних алфавітів (кодових таблиць) для пересилання англійської, російської, французької і т.д. текстів, програмних текстів на С ++, Паскалі і т.д. Кодування при цьому не буде оптимальним, але виключається статистична обробка пересилаються фрагментів і відпадає необхідність пересилання кодових таблиць.
Нижче в таблиці представлена ??таблиця можливих кодів Хафмана для англійського алфавіту.
БукваКод ХафманаE100T001A1111O1110N1100R1011I1010S0110H0101D11011L01111F01000C01000M00011U00010G00001Y00000P110101W011101B011100V1101001K110100011X110100001J110100000Q1101000101Z1101000100
Нижче представлена ??аналогічна таблиця для російського алфавіту. У цій таблиці коди букв Е і Е ідентичні, аналогічна сутуація з кодами Ь і'. Слід також мати на увазі, що крім букв певні коди повинні бути присвоєні символам пунктуації, числам і деяким спеціальним символам (1 2 3 4 5 6 7 8 9 0.,:;!? ... '"~% # * + - = () [] {} _).
БукваОтносіт. частотаКод Хафмана- пробел0,175111O0,090110Е,Ё0,0721001А0,0621010И0,0621001T0,0531000Н0,0530111C0,0450110Р0,04001011В0,03801010Л0,03501001К0,02801000М0,02600111Д0,025001101П0,023001100У0,02100101Я0,018001001Ы0,016001000З0,016000111Ь,Ъ0,014000110Б0,014000101Г0,013000100Ч0,012000011Й0,0100000101Х0,0090000100Ж0,0070000011Ш0,00600000101Ю0,00600000100Ц0,00400000010Щ0,00300000001Э0,003000000001Ф0,002000000000
Можлива схема реалізації алгоритму формування кодів Хафмана для російського алфавіту показана на рис. 3.
Рис. 3. Середнє число елементарних сигналів для передачі літери при даному методі кодування одно 4,4
Метод Шеннона-Фано
Даний метод виділяється своєю простотою. Беруться вихідні повідомлення m (i) та їх ймовірності появи P (m (i)). Повідомлення упорядивается так, щоб ймовірність i-го повідомлення була не більша (i + 1) -го. Цей список ділиться на дві групи з приблизно рівною інтегральної ймовірністю. Кожному повідомленням з групи 1 присвоюється 0 в якості першої цифри коду. Повідомленнями з другої групи ставляться у відповідність коди, що починаються з 1. Кожна з цих груп ділиться на дві аналогічним чином і додається ще одна цифра коду. Процес?? родолжает доти, поки не будуть отримані групи, що містять лише одне повідомлення. Кожному повідомленням в результаті буде присвоєно код xc довжиною -lg (P (x)). Це справедливо, якщо можливо розподіл на підгрупи з абсолютно дорівнює сумарній ймовірністю. Якщо ж це неможливо, деякі коди будуть мати довжину -lg (P (x)) + 1. Алгоритм Шеннона-Фано не гарантує оптимального кодування.
Алгоритм Зива-Лемпеля
У 1977 році Абрахам Лемпелю і Якоб Зів запропонували алгоритм стиснення даних, названий пізніше LZ77. Цей алгоритм використовується в програмах архівування текстів compress, lha, pkzip і arj. Модифікація алгоритму LZ78 застосовується для стискування двійкових даних. Ці модифікації алгоритму захищені патентами США. Алгоритм передбачає кодування послідовності біт шляхом розбиття її на фрази з подальшим кодуванням цих фраз. Пізніше з'явилася модифікація алгоритму LZ78 - Lempel-Ziv Welsh (використовує словник для байтів для потоків октетів).
Суть алгоритму полягає в наступному:
Якщо в тексті зустрінеться повторення рядків символів, то повторні рядки замінюються посиланнями (покажчиками) на вихідну рядок. Посилання має формат lt; префікс, відстань, довжина gt ;. Префікс в цьому випадку дорівнює 1. Поле відстань ідентифікує слово в словнику рядків. Якщо рядки в словнику немає, генерується код символ виду lt; префікс, символ gt ;, де поле префікс=0, а поле символ відповідає поточному символу вихідного тексту. Звідси видно, що префікс служить для розділення кодів покажчика від кодів символ. Введення кодів символ, дозволяє оптимізувати словник і підняти ефективність стиснення. Головна алгоритмічна проблема тут полягає у оптимальному виборі рядків, так як це передбачає значний обсяг переборовши.
Розглянемо приклад з вихідною послідовністю U=0010001101 (без надії отримати реальне стиснення для настільки обмеженого обсягу вихідного матеріалу).
Введемо позначення: [n] - фраза з номером n.- результат стиснення.
Розкладання вихідної послідовності біт на фрази представлено в таблиці нижче.
N фразиЗначеніеФормулаІсходная послідовність U0-P [0] 001000110110P [1]=P [0] .00. 010001101201P [2]=P [1] .10.01.00011013010P [3]=P...
