Предпосылкой для сжатия информации является следующее.
Символы сообщений не равновероятны, что обычно наблюдается в действительности. В связи с этим сообщение определенной длины I* имеет энтропию (количество информации), приходящуюся на один символ Н| < 1-^ . Это означает, что при используемой энтропии Н] можно было бы получить такое же количество сведений при меньшей длине сообщений, чем в случае равновероятности всех этих сообщений. Величина, на которую удлиняется сообщение, представляет собой избыточность по сравнению с минимальной длиной сообщений, потребной для передачи данной информации.
Избыточность информации определяют коэффициентом избыточности
г. 1 ** I
и устраняют кодированием, т.е. однозначным преобразованием одной последовательности символов в другую последовательность. При этом часто встречающимся сообщениям ставят в соответствие более краткие кодовые комбинации, а редко встречающимся - более длинные.
Пусть некоторое сообщение состоит из п символов и имеет вероятность появления р. При перекодировке этого сообщения в новое сообщение, имеющее т символов, коэффициент сжатия будет равен т/п.
Среднестатистическая величина этого отношения для п-символьных сообщений равна
Тогда предел значения ц при п — » оо называется коэффициентом сжатия при данном способе кодирования сообщений.
Способы сжатия информации можно классифицировать следующим образом:
1 . По виду элемента, на котором осуществляется сжатие: побуквен-ное, пословное, по словосочетаниям и фразам, по текстам.
2.По характеру операций сжатия: неравномерное кодирование символов
алфавита, укорочение символа, аббревиатуры, устранение символов, унифика
ция сообщений по источнику и потребителю, более плотная упаковка, анноти
рование, индексация, реферирование, библиографическое описание.
3.По характеру взаимосвязи элементов информации: статистическое
кодирование, разностное кодирование, апертурное сжатие, сжатие с учетом
вероятностных свойств сообщений, комбинаторное сжатие, рационализация
форм документов, сокращение протяженности потоков информации.
Статистическое кодирование представляет собой сокращение среднего числа символов, передаваемых в кодах от источника до потребителя. При кодировании элементам сообщения с высокой вероятностью ставятся в соответствие более короткие кодовые комбинации.
Зная статистические свойства источника сообщений, можно минимизировать среднее число двоичных символов, необходимых для выражения одного элемента сообщения. В основу статистического кодирования положена теорема К.Шеннона, в соответствии с которой каждый символ сообщения должен принимать значения 0 и 1 с равными вероятностями, а каждый выбор должен не зависеть от значений предыдущих символов.
Способ статистического кодирования рассмотрим на конкретном примере.
Пусть необходимо сжать информацию об осуществлении учета складских материалов. Перечень материалов и вероятности запроса на них показаны в табл. 2.1.
32
33
Таблица 2.1
| Наименование материала | Вероятность запроса | Традиционное кодирование | Статистическое кодирование | ||
| код | кол-во символов | код | кол-во символов | ||
| 1 . Бензин | 0,15 | 0 | 1 | 11 | 2 |
| 2. Керосин | 0,10 | 1 | 1 | 100 | 3 |
| З.Лес | 0,15 | 10 | 2 | 1 | 1 |
| 4. Стекло | 0,30 | И | 2 | 0 | 1 |
| 5. Гвозди | 0,18 | 100 | 3 | 10 | 2 |
| 6. Краска | 0,22 | 101 | 3 | 101 | 3 |
На представление всех сообщений о материалах с учетом вероятностей запроса необходимо в среднем использовать объем информации, определяемый формулой
где р! - вероятность запроса на 1-й материал,
т - количество двоичных символов в коде 1-го материала. Подставив значение таблицы в указанную формулу, имеем:
при традиционном кодировании О_т=0,15х1 + 0,10x1 + 0,05x2 + 0,30x2 + 0,18x2 + 0,22x3= 1,97 бит
при статистическом кодировании Ос=0,15х2 + 0,10x3 + 0,05x3 + 0,30x1 + 0,18x2 + 0,22x1= 1,63 бит
Сокращение информации составит:
дг^.^,^,0,2
От 1,97
или 20%.
Разностное кодирование представляет собой отражение информации о характере и величине изменения наблюдаемого процесса за определенный интервал времени. Изменение - это отклонение фактического параметра от нормативного, эталонного или планового его значения.
Данный способ позволяет значительно сократить количество передаваемых символов, обеспечивает лучшее восприятие информации ее потребителем, повышает оперативность и качество управления процессами. Способ не применим в системах, где управление осуществляется по абсолютной величине параметра или показателя.
Эффективность способа тем большая, чем меньшая величина отклонения. Она оценивается по формуле:
где Дс1 - отклонение фактической величины от нормативной в момент времени I);
А - фактическая величина параметра в момент 1(. М = Л(1<)-а„(11)
где й„ - нормативная, плановая или эталонная величина в момент времени I;.
Моменты времени съема фактической информации определяется предварительно исходя из условий протекания процесса. Если процесс слишком нестабильный, то такие моменты могут корректироваться в процессе мониторинга.
Суть апертурного сжатия состоит в устранении передачи тех сообщений, которые могут быть восстановлены путем анализа предшествующих или сопоставлением их с нормативными или эталонными сообщениями.
Основным критерием выделения избыточности является полоса допустимого отклонения, или апертура. Базируется апертурное сжатие либо на предсказании по предыдущим выборкам сообщений, либо на апостериорной интерполяции последующих выборок. При апертурном сжатии имеет место частично допустимая потеря информации. Потери информации возникают в результате пороговой фильтрации сведений в процессе сокращения избыточности.
Характерные черты апертурного сжатия - возможность восстановления исходной информации с требуемой для ее потребителя точностью, высокие коэффициенты сжатия, относительная простота реализации способа и высокая эффективность.
На практике могут использоваться три разновидности этого способа - с квантованием, априорной функцией и предсказанием.
Апертурное сжатие с квантованием представляет собой дискретизацию исходной непрерывной функции конечным числом точек. Минимальный объем сообщения обеспечивается в том случае, когда шаг квантования берется настолько большим, насколько это допустимо при условии, что потребитель не заметит искажения исходной функции в результате ее дискретизации.
Квантование можно осуществлять как по уровню показателей (параметров), так и по времени.
Примером применения этой разновидности апертурного сжатия является контроль за процессами производства. Квантование осуществляется одновременно по уровню параметров и по времени. Данный пример является наиболее распространенным в практике.
Апертурное сжатие с априорной функцией во многом аналогично разностному кодированию. Отличие состоит лишь в том, что информация о приращениях передается только в те моменты, когда отклонение текущих значений функции от заданного эталона превышают размеры установленной предварительно апертуры или допустимой зоны отклонений.
34
35
Апертура может иметь одинаковые и разные размеры, а также быть симметричной и асимметричной. Сведения, находящиеся в апертуре, считаются несущественными, поэтому не передаются потребителю.
Эффективность данной и предыдущей разновидности апертурного сжатия равна
э=1--
где ф - уровень фактического значения параметра, Д(1Ф - передаваемая величина отклонения параметра в момент 1;.
Апертурное сжатие с предсказанием осуществляется следующим образом. По предыдущим значениям выборок вычисляют величину следующей выборки. Если разность значений эталонной и фактической выборок находится в допустимых пределах, то считают предсказание правильным и устраняют значения фактической выборки. Если значения фактической выборки выходят за допустимые пределы эталонной, то осуществляют корректировку эталонной выборки с учетом имеющихся отклонений.
Эффективность данной разновидности апертурного сжатия равна
где Я„ - объем эталонной выборки, К„- объем избыточной выборки,
п„ , пц - соответственно количество передаваемых эталонных и избыточных выборок,
п^р т'ср - соответственно средний объем передаваемой эталонной выборки и избыточной выборки в информационных символах.
Суть сжатия с учетом вероятностных свойств сообщений состоит в исключении из передачи выборок сообщений с наибольшей вероятностью появления.
Алгоритм сжатия рассмотрим на конкретном примере статистики показателей выполнения плана по рабочим дням месяца. Статистику и результаты ее обработки проиллюстрируем таблицей 2.2.