Файл: Методы кодирования данных.pdf

Среднее значение длины кода k³ = 3,361. Предполагая возникновение знаков вторичного алфавита равновероятным, получаем среднюю информацию на знак равной I⁽²⁾ = log₂3 = 1,585 бит. Так как для русского алфавита I_l⁽¹⁾ — 4,356 бит, то:

Q^(r)= 1 -4,356/(3,361 - 1,585) 0,182

т.е. избыточность составляет около 18% (для английского языка *15%). Тем не менее, код Морзе имел в недавнем прошлом очень широкое распространение в ситуациях, когда источником и приемником сигналов являлся человек (не техническое устройство) и на первый план выдвигалась не экономичность кода, а удобство его восприятия человеком.

Табл. 3.1 Азбука Морзе

3.2. Помехоустойчивое кодирование

Надёжность электронных устройств по мере их развития всё время возрастает, но не смотря на это в их работе часто возникают ошибки, как систематические, так и случайные. Сигнал в канале связи может быть искажён помехой, поверхность магнитного носителя может быть повреждена, в разъёме может быть потерян контакт. Ошибки аппаратуры ведут к искажению или потере передаваемых, или хранимых данных. При определённых условиях, основные из которых будем рассматривать далее, можно применять методы кодирования, позволяющие правильно декодировать исходное сообщение, несмотря на возникающие ошибки в данных кода. В качестве рассматриваемой модели достаточно рассмотреть канал связи с помехами, потому что к такому случаю легко сводятся остальные. Например, запись па диск можно рассматривать как передачу данных в канал, а чтение с диска — как приём данных из канала.

Кодирование с исправлением ошибок.

Пусть имеется канал связи, содержащий источник неких помех. Помехи проявляются в том, что получаемое сообщение может отличаться от переданного. Опишем это отличие в функциональной форме:

K K′, K, K′ B*,

где К —множество переданных, а К' — соответствующее множество принятых по каналу сообщений, подразумевая, что разные вызовы «функции» С с одним и тем же аргументом могут возвращать различные результаты. Кодирование F (вместе с декодированием F^-1), обладающее тем свойством, что

S K K′ S, s A* (F^-1 C(F(s))) = s),

называется помехоустойчивым, или самокорректирующимся, или кодированием с исправлением ошибок. Без ограничения общности можно считать, что А = В = {0,1}. Кроме того, естественно предположить, что содержательное кодирование (вычисление F и F^-l) выполняется на устройстве, свободном от помех, то есть F и F^-l являются функциями в обычном смысле. Функция F^-1 является декодированием для кодирования F, но она не является обратной функцией для функции F.^[25]

Если про источник помех С ничего не известно, то функции F и F^-1 не могут быть определены, за исключением тривиальных случаев, когда S = или |S| = 1. Таким образом, для решения поставленной задачи необходимо иметь описание возможных ошибок (проявлений помех).

Ошибки в канале могут быть следующих типов:

0 → 1, 1 → 0 — ошибка типа замещения разряда;

0 → , 1 → — ошибка типа выпадения разряда;

→ 0, → 1 — ошибка типа вставки разряда.

Канал характеризуется верхними оценками количества ошибок каждого типа, которые возможны при передаче через канал сообщения определённой длины n. Общая характеристика ошибок канала (то есть их количество и типы) обозначается = , где ,, — верхние оценки количества ошибок каждого типа соответственно.

Допустим, что имеется канал с характеристикой = (1,0,0), то есть в канале возможно не более одной ошибки типа замещения разряда при передаче сообщения длины n. Пусть требуется передавать через этот канал поток сообщений, каждое длины n. Рассмотрим следующее кодирование: F(): = ааа (то есть каждый разряд в сообщении утраивается) и декодирование

F^-1(abc): = : = a + b + с > 1 (то есть разряд восстанавливается методом «голосования»). Это кодирование кажется помехоустойчивым для данного канала, однако на самом деле это не так. Дело в том, что хотя можно предполагать, что при передаче сообщения длины 3n возможно не более 3 ошибок типа замещения разряда, но места этих ошибок совершенно необязательно распределены равномерно по всему сообщению. Ошибки замещения могут произойти в соседних разрядах, и метод голосования восстановит разряд неверно. Чтобы метод голосования сработал, вместо одного сообщения длины Зn придётся передать 3 сообщения длины n, то есть уменьшить втрое скорость передачи потока сообщений через канал.

Возможность исправления всех ошибок.

Пусть — множество слов, которые могут быть получены из слова s в результате всех возможных комбинаций допустимых в канале ошибок типа , то есть s S A*, В*. Если s' , то кратчайшую последовательность ошибок, которая позволяет получить из слова s слово s', будем обозначать . Заметим, что таких последовательностей может быть несколько. Другими словами,

=

Количество ошибок в кратчайшей последовательности обозначим ||. Если характеристика канала подразумевается, то индекс не указывается.

Пример. Пусть 5 — (2,1,1) для слов длины 2. Тогда |F5(01,10)| = 2, причём существует несколько различных кратчайших последовательностей ошибок, в частности: 01 —> 11 —> 10; 01 —у 1 —у 10; 01 —у 010 —у 10.

Пример. Рассмотрим канал, для которого в любом передаваемом разряде происходит ошибка типа замещения с вероятностью р, причём замещения различных разрядов статистически независимы. Данный канал называется двоичным симметричным. В этом случае любое слово s может быть преобразовано в любое другое слово s' ; замещениями разрядов. Таким образом, s (E_s = ), исправить все ошибки в двоичном симметричном канале не представляется возможным даже при сколь угодно малом р > 0.

Положим, что F является кодированием с исправлением р ошибок типа , если существует декодирование F^-1 такое, что

s S ( s′ (| | ≤ p => F^-1(s′) = s))^[26]

3.3. Сжатие данных

Исходя из выше изложенного материала, можно сделать вывод, что при кодировании наблюдается некоторый баланс между временем и памятью. Затратив дополнительные усилия при кодировании и декодировании, можно сэкономить память, и наоборот, если пренебречь объемом используемой памяти, можно значительно выиграть во времени кодирования и декодирования. Несомненно, такая зависимость имеет место только в ограниченных пределах, и нельзя полностью исключить расход памяти или разработать мгновенно работающие алгоритмы кодирования. Для методов алфавитного кодирования пределы возможной оптимизации установлены. Для дальнейшего продвижения необходимо рассмотреть неалфавитное кодирование.

Сжатие текстов.^[[27]]

Предположим, что существует некоторое сообщение, закодированное каким-то общепринятым способом (для текстов это, например, код ASCII) и хранящееся в энергонезависимой памяти компьютера. Отметим, что равномерное кодирование (в частности, ASCII) не является оптимальным для текстов. Очевидно, в текстах обычно используется существенно меньше, чем 256 символов (в зависимости от языка — примерно 60-80 с учётом знаков препинания, цифр, строчных и прописных букв). Кроме того, частота появления букв различны, и для каждого естественного языка определены (с некоторой точностью) частоты появления букв в тексте. Таким образом, можно задаться некоторым набором букв и частотами их возникновения в тексте и с помощью алгоритма Хаффмена представить оптимальное алфавитное кодирование текстов (для заданного алфавита и языка). Нетрудные расчёты показывают, что такой метод кодирования для распространенных естественных языков будет иметь цену кодирования несколько меньше 6, то есть даст выигрыш по сравнению с кодом ASCII на 25% или несколько больше.

Способы кодирования, позволяющие создавать (без потери информации!) коды сообщений меньшей длины по сравнению с исходным сообщением, называются методами сжатия (или упаковки) данных. Эффективность сжатия определяется коэффициентом сжатия, который в большинстве случаев измеряется в процентах и показывает, на сколько процентов кодированное сообщение меньше исходного.

Известно, что практические программы сжатия (rar, zip и др.) имеют намного более лучшие показатели, чем код Хаффмена: при сжатии текстов коэффициент сжатия достигает более 70%. Это означает, что в таких программах используется не алфавитное кодирование.

Предварительное построение словаря

Рассмотрим следующий способ кодирования:

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

2. Полученное множество слов считается буквами нового алфавита. Для этого алфавита строится разделимая схема алфавитного кодирования (равномерного кодирования или оптимального кодирования, если для каждого слова подсчитать число вхождений в текст). Полученная схема обычно называется словарем, так как она сопоставляет слову код.

3. Далее код сообщения строится как пара — код словаря и последовательность кодов слов из данного словаря.

4. При декодировании исходное сообщение восстанавливается путем замены кодов слов на слова из словаря.

Допустим, что требуется кодировать тексты на русском языке. В качестве алгоритма деления на слова примем естественные правила языка: слова отделяются друг от друга пробелами или знаками препинания. Можно принять допущение, что в каждом конкретном тексте имеется не более 216 различных слов (обычно гораздо меньше). Таким образом, каждому слову можно сопоставить номер — целое число из двух байтов (равномерное кодирование). Поскольку в среднем слова русского языка состоят более чем из двух букв, такое кодирование даёт существенное сжатие текста (около 75% для обычных текстов на русском языке). Если текст достаточно велик (сотни тысяч или миллионы букв, то есть сотни и тысячи страниц), то дополнительные затраты на хранение словаря оказываются сравнительно небольшими.

Данный метод попутно позволяет решить задачу полнотекстового поиска, то есть определить, содержится ли заданное слово (или слова) в данном тексте, причём для этого не нужно просматривать весь текст (достаточно просмотреть только словарь).^[[28]]

Указанный метод можно усовершенствовать следующим образом. На шаге 2 следует применить алгоритм Хаффмена для построения оптимального кода, а на шаге 1 — решить экстремальную задачу разбиения текста на слова таким образом, чтобы среди всех возможных разбиений выбрать то, которое даёт наименьшую цену кодирования на шаге 2. Такое кодирование будет «абсолютно» оптимальным. К сожалению, указанная экстремальная задача очень трудоёмка, поэтому на практике не используется — время на предварительную обработку большого текста оказывается чрезмерно велико даже при использовании современных быстродействующих компьютеров