Топоркова О.М. Информатика - файл n1.doc

приобрести
Топоркова О.М. Информатика
скачать (1710.5 kb.)
Доступные файлы (1):
n1.doc1711kb.26.08.2012 21:38скачать
Победи орков

Доступно в Google Play

n1.doc

1   ...   4   5   6   7   8   9   10   11   ...   30

4.3. Эффективное кодирование



Д

(4.3)
ля кодирования символов исходного алфавита используют двоичные коды переменной длины: чем больше частота символа, тем короче его код. Эффективность кода определяется средним числом двоичных разрядов для кодирования одного символа – lср по формуле (4.3):

где k – число символов исходного алфавита;

ns – число двоичных разрядов для кодирования символа s;

f
sчастота символа s; причем

Существуют два классических метода эффективного кодирования: методы Шеннона-Фано и Хаффмена. Входными данными для обоих методов является заданное множество исходных символов для кодирования с частотами; результат - эффективные коды.

4.3.1. Метод Шеннона-Фано


Этот метод требует упорядочения исходного множества символов по не возрастанию их частот. Затем выполняются следующие шаги:

а) список символов делится на две части (назовем их первой и второй частями) так, чтобы суммы частот обеих частей (назовем их 1 и 2) были точно или примерно равны. В случае, когда точного равенства достичь не удается, разница между суммами должна быть минимальна;

б) кодовым комбинациям первой части дописывается 1, кодовым комбинациям второй части дописывается 0;

в) анализируют первую часть: если она содержит только один символ, работа с ней заканчивается, – считается, что код для ее символов построен, и выполняется переход к шагу г) для построения кода второй части. Если символов больше одного, переходят к шагу а) и процедура повторяется с первой частью как с самостоятельным упорядоченным списком;

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

д) анализируется оставшийся список: если он пуст – код построен, работа заканчивается. Если нет, – выполняется шаг а).

Пример 4.6. Даны символы a, b, c, d с частотами fa = 0,5; fb = 0,25; fc = 0,125; fd= 0,125. Построить эффективный код методом Шеннона-Фано.

Сведем все построение в таблицу (табл. 4.7), где разместим исходные данные, упорядочив их, как требует метод.

Первая линия деления проходит под символом a: соответствующие суммы 1 и 2 равны между собой и равны 0,5. Тогда формируемым кодовым комбинациям дописывается 1 для верхней (первой) части и 0 для нижней (второй) части. Поскольку это первый шаг формирования кода, двоичные цифры не дописываются, а только начинают формировать код. В силу того, что верхняя часть списка содержит только один элемент (символ а), работа с ней заканчивается, а эффективный код для этого символа считается сформированным.

Второе деление выполняется под символом b: суммы частот 1 и 2 вновь равны между собой и равны 0,25. Тогда кодовой комбинации символов верхней части дописывается 1, а нижней части – 0. Таким образом, к полученным на первом шаге фрагментам кода, равным 0, добавляются новые символы. Поскольку верхняя часть нового списка содержит только один символ (b), формирование кода для него закончено.

Третье деление проходит между символами c и d: к кодовой комбинации символа c приписывается 1, коду символа d приписывается 0.

Таким образом, получили коды:

a - 1,

b - 01,

c - 001,

d - 000.

Определим эффективность построенного кода по формуле (4.3):

lср = 0,5*1 + 0,25*01 + 0,125*3 + 0,125*3 = 1,75.

При кодировании четырех символов кодом постоянной длины требуется два двоичных разряда (см. пример 4.1).

Таким образом, сэкономлено 0,25 двоичного разряда в среднем на один символ.

Таблица 4.7

Исход-

ные

сим-

волы

Час-

тоты символов

Этапы построения кода

Формируемый код


первое деление


второе деление


третье деление

первое

деление

второе

деление

третье деление


линия деления
a

0,5

1 = 0,5

код для символа a сформирован

1

-

-


линия деления
b

0,25




1 = 0,25

код для символа b сформирован

0

1

-


линия деления
c

0,125

2=0,25+0,125+



2 = 0,125+0,125 = 0,25

1 = 0,125
2 = 0,125

0

0

1

d

0,125

0,125=0,5

0

0

0

4.3.2. Метод Хаффмена


Этот метод имеет два преимущества по сравнению с методом Шеннона-Фано: он устраняет неоднозначность кодирования, возникающую из-за примерного равенства сумм частот при разделении списка на две части (линия деления проводится неоднозначно), и имеет, в общем случае, большую эффективность кода.

Исходное множество символов упорядочивается по не возрастанию частоты и выполняются следующие шаги:

1) объединение частот:

2) построение кодового дерева:

3) формирование кода: для получения кодов листьев (исходных кодируемых символов) продвигаются от корня к нужной вершине и «собирают» веса проходимых ребер.

Пример 4.7. Даны символы a, b, c, d с частотами fa = 0,5; fb = 0,25; fc = 0,125; fd= 0,125. Построить эффективный код методом Хаффмена.

1) объединение частот:

Таблица 4.8

Исходные символы s

Частоты fs

Этапы объединения

первый

второй

третий

a

0,5

0,5

0,5

1

b

0,25

0,25

0,5




c

0,125

0,25







d

0,125











2) построение кодового дерева:

1

  1. 0



0,5 a 0,5

  1. 0

0,25 b 0,25

  1. 0

0,125 c 0,125 d
3) формирование кода:

a - 1;

b - 01; (4.4)

c - 001;

d - 000.

Как видно, полученные коды совпадают с теми, что были сформированы методом Шеннона-Фано, следовательно, они имеют одинаковую эффективность.

4.3.3. Повышение эффективности кодирования


Повысить эффективность кодирования можно, строя код не для символа, а для блоков из n символов. Рассмотрим этот тезис на примере.

Пример 4.8. Даны символы a и b с частотами, соответственно, 0,9 и 0,1. Построить эффективный код методом Шеннона-Фано для блоков из двух символов (n = 2).

Сформируем список возможных блоков и их частот. При этом частоту блока будем рассчитывать как произведение частот символов, входящих в блок. Тогда имеем:

Блоки исходных Частоты блоков

символов f блока = f1 * f2

aa 0,81

ab 0,09

ba 0,09

bb 0,01

Построение кода сведем в табл. 4.9.

Таблица 4.9

Блоки исходных символов

Частоты блоков

Этапы построения кода

первый

второй

третий

aa

0,81

1

код построен

ab

0,09

0

1

код построен

ba

0,09

0

0

1

bb

0,01

0

0

0

Таким образом, получены коды:

aa - 1;

ab - 01;

ba - 001;

bb - 000.

Определим эффективность построенного кода. Для этого рассчитаем сначала показатель эффективности для блока символов по формуле (4.3):

lср блока = 0,81*1 + 0,09*2 + 0,09*3 + 0,01*3 = 1,28.

Поскольку в блоке 2 символа (n=2), для одного символа lср = lср блока/2 = 1,28/2 = 0,64.

При посимвольном кодировании для эффективного кода потребуется по одному двоичному разряду. В самом деле, применение метода Шеннона-Фано дает результат, представленный в табл. 4.10.

Таблица 4.10

Исходные символы

Частоты символов

Построение кода

a

0,9

1

b

0,1

0


Таким образом, при блочном кодировании выигрыш составил 1 - 0,64 = 0,36 двоичных разрядов на один кодируемый символ в среднем.

Эффективность блочного кодирования тем выше, чем больше символов включается в блок.

4.3.4. Декодирование эффективных кодов


Особенностью эффективных кодов является переменное число двоичных разрядов в получаемых кодовых комбинациях. Это затрудняет процесс декодирования.

Рассмотрим, как происходит декодирование сообщения, если использовались коды постоянной длины.

Пусть коды формировались по табл. 4.2 и полученное сообщение имеет вид:

001000011101.

Поскольку длина кода равна двум символам, в исходном сообщении слева направо выделяются по два двоичных символа и сопоставляются с кодовой табл. 4.2.

Имеем: 001000101101

a c a b d b

Тогда в исходном сообщении содержится текст acabdb. Декодирование выполнено.

Для декодирования кодов переменной длины рассмотренный подход не годится. Тем не менее закодированные сообщения могут декодироваться благодаря свойству префиксности эффективных кодов: ни одна более короткая кодовая комбинация не является началом более длинной кодовой комбинации.

Для раскрытия данного тезиса вернемся к кодам из примера 4.7. Там самым коротким кодом был код для символа a со значением 1. Как видно, ни один другой код (более длинный) не имеет в начале символ 1. Второй по длине код для символа b имеет значение 01 и, как показывает анализ, не является началом ни для кода 001, ни для кода 000. Таким образом, код из примера 4.7 является префиксным.

Свойство префиксности позволяет декодировать сообщения, закодированные эффективными кодами.

Пусть получено сообщение 1010010001, составленное из кодов, построенных в примере 4.7; выполним его декодирование.

В сообщении слева направо выделяется по одному двоичному символу и делается попытка декодирования в соответствии с таблицей кодов (4.4). Если попытка успешна, двоичный символ (или символы) исключается из исходной цепочки и заменяется соответствующим исходным символом. Если попытка не удается, во входной цепочке выделяется следующий двоичный символ и уже с двумя двоичными символами делается попытка их декодирования по таблице кодов. Если попытка и тогда неудачна, выделяют следующий третий и т.д.

Итак, имеем:

направление просмотра цепочки

1 0 1 0 0 1 0 0 0 1

a - - - a

b - -
с d

Здесь знак «-» означает, что попытка декодирования не удалась.

Таким образом, при декодировании получили строку abcda.

Отметим, что методы Шеннона-Фано и Хаффмена строят префиксные коды.

4.3.5. Специальные методы эффективного кодирования


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

4.3.5.1. Методы эффективного кодирования числовых последовательностей


Различают два метода – разностное кодирование и кодирование повторений.

Суть разностного кодирования заключается в хранении вмес­то абсолютных значений либо разностей двух смежных чисел, либо отк­лонения чисел от их среднего значения. Например, для последо­вательности чисел:

2 14 18 27 34

первый способ даст после­довательность:

2 12 4 9 7.

Этот метод эффективен для медленно меняющихся после­довательностей. Его недостаток состоит в том, что для получения значения n-го члена последовательности надо декодировать все предыдущие (n-1) членов.

Второй способ порождает последо­вательность:

-17 -5 -1 8 15 ,

поскольку среднее значение для исходной последовательности - 19.

Этот способ эффективен, когда максимальное отклонение от сред­него значительно меньше абсолютного значения среднего. Достоинство данного подхода заключается в независимости декодирования любого n-го члена числовой последовательности от декодирования остальных ее составляющих: для этого нужно знать только значение среднего арифметического данной последовательности, что вынуждает хранить это число вместе с самой закодированной последовательностью.

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

В самом деле, внутреннее представление символьной информации выполнено с использованием одной из систем кодирования по образцу, например ASCII-кода (см. п. 4.1.2), который представляет собой двузначные шестнадцатеричные числа для каждого кодируемого символа. Иными словами, внутреннее представление любой информации – массив двузначных шестнадцатеричных чисел, к которому может быть применен один из указанных выше методов.

Кодирование повторений заключается в замене цепочки оди­наковых цифровых символов самим символом и числом повторений (возможно включение разделителей). Напри­мер, для последовательности:

55556666888888

применение этого способа даст последовательность:

5(4)6(4)8(6),

где круглые скобки играют роль разделителей.

Данный метод может быть использован для эффективного кодирования растровых форматов изображений. Растровыми называются форматы изображений, которые получаются во время ввода изображения путем кодирования каждой точки – пиксела (pixel – PIсture ELement) – двумерного пространства, на котором расположено исходное изображение, даже если эта точка не содержит самого изображения. Например, на рис. 3.1а пространство изображения – воображаемый прямоугольник, включающий само изображение функции вместе с осями координат и введенными обозначениями. Очевидно, изображение занимает не все пространство. Тем не менее, кодированию подлежат и «пустоты», при этом те точки, которые содержат изображение, в простейшем случае кодируются двоичной 1, точки без изображения кодируются двоичным 0 (подробнее о восприятии изображений см. далее). В результате получаются числовые последовательности, подобные следующей:

00000000000000000000000000000000000000000000000010000000000000000000.

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

00000000000080000.

Очевидно, к таким последовательностям можно применить метод кодирования повторений. В результате для нашего случая получим (круглые скобки используем как разделители):

0(С)8000,

что означает: 0 повторяется 12 раз (С16 = 12), для остальных символов число повторений не вводится.

Поскольку результирующая последовательность должна также быть шестнадцатеричной, полученное выражение преобразуем следующим образом: заменим круглые скобки соответствующими ASCII-кодами. Тогда открывающей скобке соответствует код 2816, закрывающей – 2916. Получим:

028С2980000.

Длина результата меньше исходной последовательности (11 символов против 17), поэтому получен эффект в 6 символов.

4.3.5.2. Методы эффективного кодирования словарей


Словари очень часто применяются в современных прикладных программных продуктах, например, при проверке орфографии в текстовом процессоре WinWord. Для их рационального хранения применяются рассмотренные ниже методы.

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

Пусть есть фрагмент словаря со словами:

вычислитель ,

вычислительный ,

вычислять.

Очевидно, у двух подряд расположенных слов есть общие буквы в начале. Тогда можно выполнить следующую замену:

вычислитель ,

11ный ,

6ять ,

где числа означают, сколько букв из предыдущего слова надо взять, чтобы восстановить данное слово. Здесь слово «вычислитель» можно рассматривать как некоторое базовое слово, которое не подвергается кодированию.

Недостаток данного подхода заключается в необходимости декодировать все (n-1) слов, начиная с базового слова, для декодирования n-го слова словаря.

Второй подход состоит в том, что формируется вспомогательный словарь, в который включаются наиболее часто повторяющиеся части слов (в нашем случае, например, это фрагменты слов «вычисл» и «ител»). Каждому такому фрагменту назначается код, например, его порядковый номер во вспомогательном словаре. Затем в основном словаре фрагменты слов заменяются их кодами из вспомогательного словаря.

Для нашего примера будут сформированы два словаря:

основной вспомогательный

12ь 1 - вычисл

12ьный 2 - ител

1ять .

4.3.5.3. Методы эффективного кодирования естественно-языковых текстов


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

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

Например, пусть задан исходный текст:

«информатика изучает способы обработки информации».

В этом тексте дважды повторяются фрагменты «информа» длиной 7 символов (они выделены жирным стилем). Построим эффективно закодированный текст:

а) с указателями назад. Текст просматривается от начала к концу и специальный механизм определяет, что повторно встречается указанный выше фрагмент. Алгоритм строит адресный указатель взамен этого фрагмента со структурой: количество символов, которые надо отсчитать в обратном направлении к началу первого вхождения фрагмента, и длина фрагмента. Таким образом, для нашего примера имеем:

«информатика изучает способы обработки 38/7ции»,

38 символов

где знак / играет роль разделителя.

б) с указателями вперед. Текст просматривается от конца к началу и специальный механизм определяет, что повторно встречается указанный выше фрагмент. Алгоритм строит адресный указатель взамен этого фрагмента со структурой: количество символов, которые надо отсчитать в обратном направлении к началу первого вхождения фрагмента, и длина фрагмента.

Таким образом, для нашего примера имеем:

«31/7тика изучает способы обработки информации».

31 символ

Очевидно, в обоих случаях полученный результат короче исходного текста.
1   ...   4   5   6   7   8   9   10   11   ...   30


4.3. Эффективное кодирование
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации