Кодирование сообщений

1.

КОДИРОВАНИЕ СООБЩЕНИЙ
Сжатие на основе смыслового содержания данных

2.

КОДИРОВАНИЕ СООБЩЕНИЙ
Сжатие на основе смыслового содержания данных

3.

КОДИРОВАНИЕ СООБЩЕНИЙ
Сжатие на основе смыслового содержания данных
Очевидно, что выбор наиболее экономного способа кодирования зависит от
сравнения целочисленных величин RI и RII: при наличии небольшого числа длинных
сообщений предпочтителен первый подход, если же имеется много коротких
сообщений, составленных из небольшого количества знаков, то предпочтительнее
второй подход. Однако, количество передаваемых сообщений может быть заранее
неизвестно. В этом случае необходимо производить посимвольное кодирование.
Пусть способ кодирования выбран. Теперь решим вопрос о том, каким образом
можно дополнительно сократить количество разрядов R двоичного кодового слова.

4.

КОДИРОВАНИЕ СООБЩЕНИЙ
Сжатие на основе смыслового содержания данных
Из вышеприведенных формул следует, что:
1) при первом подходе нужно постараться уменьшить число передаваемых
сообщений m, например, путем отбрасывания повторяющихся сообщений. В тех случаях,
когда точное число сообщений неизвестно, необходимо по возможности снижать значение
верхней границы их оцениваемого количества. Однако существенное сокращение
размерности множества сообщений, как правило, невозможно, потому что на практике
каждое сообщение несет информацию о некоторой ситуации, число которых может быть
фиксировано;
2) при втором подходе можно, во–первых, уменьшить размерность алфавита, что на
практике почти невозможно, потому что связано с сокращением выразительных
возможностей языка – попробуйте, например, выбрасывать буквы из алфавита от А до Я –
и, во–вторых, уменьшить количество знаков в передаваемых сообщениях путем их сжатия
по контексту (на основе смыслового содержания данных). Это гораздо более реальный
путь, который лежит в основе большого количества практических методов сжатия данных.
Рассмотрим некоторые из них.

5.

КОДИРОВАНИЕ СООБЩЕНИЙ
Переход от естественных обозначений к более компактным
Многие данные, несущие информацию о каких-либо объектах, как правило, имеют
вид, удобный для их чтения человеком. При этом они содержат обычно больше символов,
чем это необходимо для адекватного восприятия передаваемой с их помощью информации.
Наличие такой избыточности позволяет перекодировать информацию более компактно,
поступаясь наглядностью ее представления в интересах эффективности передачи по каналу
связи.
Например, дата записывается обычно в виде «26 сентября 2007 г.» (18 символов,
включая пробелы) или в более краткой форме «26.09.07». При анализе смыслового
содержания выясняется, что информацию о дате можно кодировать и шестью десятичными
разрядами, если договориться, что первые два разряда несут информацию о числе,
следующие два разряда – о месяце и последние два – о годе даты (существование
американского формата даты, когда первыми идут две цифры месяца, доказывает, что
вводимые соглашения вовсе не так очевидны, как это кажется на первый взгляд). В этом
случае рассматриваемую дату можно будет записать в виде «260907» – еще менее наглядно,
но зато более компактно.

6.

КОДИРОВАНИЕ СООБЩЕНИЙ
Переход от естественных обозначений к более компактным

7.

КОДИРОВАНИЕ СООБЩЕНИЙ
Переход от естественных обозначений к более компактным

8.

КОДИРОВАНИЕ СООБЩЕНИЙ
Подавление повторяющихся символов

9.

КОДИРОВАНИЕ СООБЩЕНИЙ
Кодирование часто используемых данных
Некоторые данные, такие как имена и фамилии, принадлежат множеству возможных
значений очень большого размера. Однако в большинстве случаев используется лишь малая
часть возможных значений (действует так называемое «правило 90/10» – в 90% случаев
используется 10% возможных значений). Поэтому для сжатия данных можно определить
множество наиболее часто используемых значений, экономно закодировать его элементы и
использовать эти коды вместо обычного представления.
В частности, можно составить список из 256 наиболее употребительных имен людей и
кодировать их одним байтом. Одновременно следует обеспечить возможность записи имен, не
входящих в закодированные: например, используя признак, аналогичный признаку
повторения, кодируемый одним байтом и указывающий на то, что последующие байты
содержат полное написание имени. Таким же образом может быть произведено кодирование
наиболее употребительных фамилий (для этого могут потребоваться двухбайтовые коды).
Многие сообщения и файлы данных содержат текстовые фрагменты из некоторых
областей знаний. В таких текстах можно выделить множество наиболее употребительных
слов, например, терминов, пронумеровать их и закодировать по вышеизложенному способу.
Данный метод, таким образом, сочетает в себе оба подхода к кодированию (см. формулы
1.1 и 1.2).

10.

КОДИРОВАНИЕ СООБЩЕНИЙ
Сжатие данных на основе сравнения
В упорядоченных наборах данных часто совпадают начальные символы или даже целые
последовательности начальных символов записей. Поэтому можно кодировать данные на
основе их сравнения с предыдущими. В этом случае сжимаемым элементам данных может
предшествовать специальный признак, указывающий на то, что элемент данных:
– совпадает с предыдущим;
– имеет следующее по порядку значение;
– совпадает с предыдущим кроме m последних символов;
– не имеет связи с предыдущим.
При использовании подобных признаков закодированные данные содержат только
отличия текущих элементов от предыдущих.

11.

КОДИРОВАНИЕ СООБЩЕНИЙ
Целесообразность сжатия данных
Реализация сжатия данных в информационных процессах требует дополнительных
программных и аппаратных затрат, а также затрат времени и памяти на предварительное
кодирование с целью сжатия и последующее декодирование для восстановления данных в
первоначальном виде. Это означает, что сжатие данных – это не всегда целесообразное
мероприятие.
Например, в базах данных обычно сжимаются архивные файлы с невысокой частотой
использования. Сжатие применяется также для сокращения размеров индексных таблиц,
используемых для организации поиска данных в индексно–последовательных файлах.

12.

КОДИРОВАНИЕ СООБЩЕНИЙ
Сжатие на основе статистических свойств данных и неравномерные коды
Методы такого сжатия изучаются в
специальном
разделе
теории
информации (подразделе теоретической
информатики),
который
называется
теорией экономного или эффективного
кодирования. Экономное кодирование
основано на использовании систем
кодирования с переменной длиной
кодового слова.

13.

КОДИРОВАНИЕ СООБЩЕНИЙ
Сжатие на основе статистических свойств данных и
неравномерные коды
При использовании таких неравномерных кодов сразу же возникает проблема выделения
кодовых слов из закодированной последовательности символов для однозначного декодирования
сообщений. Например, в коде Морзе для этого предусмотрена специальная кодовая комбинация–
разделитель (тройная пауза). Однако более экономным является использование при кодировании
так называемого условия префиксности кода (условия Фано): никакое кодовое слово не должно
являться началом другого кодового слова. Выполнение этого условия гарантирует однозначное
разбиение последовательности символов на кодовые слова без применения разделителей:
очередное кодовое слово получается последовательным считыванием символов до тех пор, пока
получающаяся комбинация не совпадет с одним из кодовых слов.

14.

КОДИРОВАНИЕ СООБЩЕНИЙ
Сжатие на основе статистических свойств данных и
неравномерные коды
Пусть, например, A={0,1, … ,9}. Закодируем символы данного алфавита наборами
двоичных знаков следующим образом:
0 – 00
1 – 01
2 – 1000
3 – 1001
4 – 101
5 – 110
6 – 1110
7 – 11110
8 – 111110
9 – 111111
Нетрудно видеть, что перед нами – префиксный код. Теперь появляется возможность
однозначного
декодирования
любого
сообщения.
Например,
последовательность
1110110111110100000000110011111110101 допускает лишь одно разбиение на кодовые слова
1110 110 111110 1000 00 00 01 1001 111111 01 01 и соответствует сообщению 65820013911.
Префиксный код называется примитивным, если его нельзя сократить, т.е. при
вычеркивании любого знака хотя бы в одном кодовом слове код перестает быть префиксным.
Префиксный код, приведенный выше в качестве примера, является примитивным.