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

Сжатие на основе смыслового содержания данных

Сжатие данных как информационный процесс

 

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

Известны два основных принципа сжатия данных:

1) сжатие, основанное на анализе содержания данных;

2) сжатие, основанное на анализе статистических свойств кодируемых сообщений.

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

Рассмотрим оба этих принципа.

 

 

Пусть имеется алфавит A из n знаков (символов), т.е. A={ai}, i=1,…,n ,и по некоторому каналу связи нужно передать m сообщений (S={sj}, i=1,…,m). Каждое сообщение имеет длину lj, т.е. составляется из lj знаков алфавита A. Требуется передать сообщения через канал связи двоичными кодовыми словами минимальной длины.

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

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

(1.1)

Здесь […] – целая часть числа.

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

(1.2)

Здесь - длина самого большого сообщения.

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

Пусть способ кодирования выбран. Теперь решим вопрос о том, каким образом можно дополнительно сократить количество разрядов Rдвоичного кодового слова.

Из вышеприведенных формул следует, что:

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

при втором подходе можно, во-первых, уменьшить размерность алфавита, что на практике почти невозможно, потому что связано с сокращением выразительных возможностей языка – попробуйте, например, выбрасывать буквы из алфавита от А до Я – и, во-вторых, уменьшить количество знаков в передаваемых сообщениях путем их сжатия по контексту (на основе смыслового содержания данных). Это гораздо более реальный путь, который лежит в основе большого количества практических методов сжатия данных. Рассмотрим некоторые из них.

 

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

Например, дата записывается обычно в виде «26 сентября 2007 г.» (18 символов, включая пробелы) или в более краткой форме «26.09.07». При анализе смыслового содержания выясняется, что информацию о дате можно кодировать и шестью десятичными разрядами, если договориться, что первые два разряда несут информацию о числе, следующие два разряда – о месяце и последние два – о годе даты (существование американского формата даты, когда первыми идут две цифры месяца, доказывает, что вводимые соглашения вовсе не так очевидны, как это кажется на первый взгляд). В этом случае рассматриваемую дату можно будет записать в виде «260907» - еще менее наглядно, но зато более компактно.

Для посимвольного двоичного кодирования даты потребуется бита (в формуле 4.2 n=10, т.к. A={0,1,…,9}, и LSmax=6).

Однако, легко заметить, что многие кодовые комбинации – такие, как 331853 или 950011 – вообще никогда не используются и рассматриваемый способ кодирования является избыточным.

Вычислим количество возможных кодовых комбинаций (а, значит, и число m возможных сообщений о дате). Поскольку

ЧИСЛО = {01, 02, … , 31};

МЕСЯЦ = {01, 02, … , 12};

ГОД = {00, 01, … , 99},

то m ≤ 31∙12∙100 = 37200 и по формуле 1.1

бит, т.е. при кодировании сообщений целиком нам потребуется 16 двоичных разрядов, что на 33,3% экономнее, чем при посимвольном кодировании.

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

С учетом того, что m1=31, m2=12, m3=100 получим

бит.

Однако и этот способ кодирования не оптимален. Допустим, при анализе выясняется, что нас будут интересовать даты не от 1 января 2000 г. по 31 декабря 2099 г., а из более узкого диапазона, например, от 1 января 2007 г. по 17 сентября 2096 г. В этом случае можно еще больше сжать данные и кодировать информацию о дате не шестью, а пятью десятичными разрядами. Для этого применим способ, известный еще в средние века: записывать общее число дней, прошедших до некоторой даты от выбранной точки отсчета (начала диапазона), в нашем случае – от 1 января 2007 г. Так как от этой даты до 17 сентября 2096 г. прошло 32768 дней, то становится понятно, почему для кодирования потребуется пять десятичных разрядов. Получим ли мы выигрыш при двоичном кодировании дат в указанном диапазоне? Да, т.к. 32768=215 и бит.

Обратим внимание, что при раздельном кодировании числа, месяца и года дат этого диапазона выигрыша мы бы не получили:

бит.

Также экономия отсутствовала бы, если бы нас интересовали даты из более широкого диапазона, скажем, с 1 января 2006 г.: в этом случае количество дат в диапазоне до 17.09.96 превысило бы 215 дней и RI=16 бит.

Аналогично датам могут быть сжаты номера изделий, уличные адреса и т.п.