Алгоритм Лемпеля–Зива (LZ), или Лемпеля–Зива–Уэлча (LZW).

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

Если заменить 60–70 % текста символами, длина кода которых составляет менее половины первоначальной длины, можно достигнуть сжатия приблизительно в 50 %. При попытке применить этот алгоритм к исполняемым файлам получаются менее впечатляющие результаты (от 10 до 20 % сжатия), так как избыточность кода, создаваемого компиляторами, значительно меньше избыточности текста на естественном языке. Файлы баз данных – еще один трудный случай: записи, содержащие имена, адреса и номера телефонов, редко повторяются, а поэтому плохо поддаются сжатию.

Именно алгоритмы Лемпеля-Зива лежат в основе наиболее известных архиваторов: zip, arj, rar.

Сжатие ведется до тех пор пока имеет смысл записывать это сжатие.

Таким образом, для реального сжатия информации используются комбинированные методы с целью оптимизации для любого варианта информации.

Обозначим N – количество равновероятных событий (неопределенность), i – количество информации в сообщении о том, что произошло одно из N событий.

Ранее решали задачи, используя показательное уравнение.

Тогда эти величины связаны формулой 2ⁱ =N, i=log₂N – формула Хартли.

Количество информации в сообщении об одном из N равновероятных событий.

N	i	N	i	N	i	N	i
	0,00000 1,00000 1,58496 2,00000 2,32193 2,58496 2,80735 3,00000 3,16993 3,32193 3,45943 3,58496 3,70044 3,80735 3,90689 4,00000		4,08746 4,16993 4,24793 4,32193 4,39232 4,45943 4,52356 4,58496 4,64386 4,70044 4,75489 4,80735 4,85798 4,90689 4,95420 5,00000		5,04439 5,08746 5,12928 5,16993 5,20945 5,24793 5,28540 5,32193 5,35755 5,39232 5,42626 5,45943 5,49185 5,52356 5,55459 5,58496		5,61471 5,64386 5,67243 5,70044 5,72792 5,75489 5,78136 5,80735 5,83289 5,85798 5,88264 5,90689 5,93074 5,95420 5,97728 6,00000

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

Для этих целей служит алфавитный подход. Алфавитом будем называть все множество используемых в языке символов. Полное число символов называют мощностью алфавита.

Мощность алфавита русских букв равна 54.

Понятно, что в каждой очередной позиции текста может появиться любой из N символов. Каждый символ несет i бит информации. Тогда из уравнения 2ⁱ =N

i=5,755 бит – столько информации несет 1 бит русского текста.

Задача. Подсчитаем количество информации на одной странице русскоязычного текста объемом 3000 знаков. Объем информации равен 5,755х3000=17256 бит.

Правило: количество информации в символьном сообщении равно Kxi, где K– число символов в сообщении, а i – информационный вес символа, определяемый по формуле Хартли.

Равновероятные и взаимно независимые события в реальной жизни встречаются довольно редко.

Во всех разговорных языках одни буквы встречаются чаще, другие - гораздо реже. Исследования говорят, что на 10 00 букв приходится следующее число повторений:

В русском языке::

О 110, Е 87, А 75, И 75, Т 65 …

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

информации в сообщениях, построенных из символов любого разговорного язы­ка, нельзя точно оценивать по формуле Хартли.

Общая оценка количества информации, названная вероятностной мерой, была разработана американским инженером-связистом и ученым Клодом Шен­ноном в 1948 г в известных работах по теории информации. С этого времени на­чалось интенсивное развитие теории информации вообще и углубленное иссле­дование вопроса об измерении ее количества в системах телекоммуникации в ча­стности.

Формула Шеннона I =- ∑ p_i log₂ p_i, где i=1... N

Здесь: I - количество информации, получаемое в результате проведения опыта; N - общее количество исходов в опыте; p_i - вероятность i-го исхода. Если вероятности всех исходов в опыте равны p₁ = p₂ =... = p_n = 1/N (бросание монеты, игрального кубика, вытаскивание карты из колоды и т.п.), то формула Шеннона превращается в формулу Хартли (1928 г.): I = log₂N.

Сообщение о том, что произошло одно из событий, содержит количество информации

i= - log₂ p_i (*).

Задача1. В классе находится 32 ученика и учитель решил спросить одного из них. Сколько информации содержится в сообщении учителя о том, кого именно он решил спросить?

Решение:

Считаем, что любого ученика учитель может вызвать с одинаковой вероятностью. Тогда по формуле Хартли (N=32) имеем: i=log₂32=5 бит.

Дата добавления: 2015-07-11