В качестве примера давайте рассмотрим, как можно выполнить сжатие сообщения с использованием конкретной системы метода Lempel-Ziv. известной как LZ77.
Процесс начинается практически с переписывания начальной части сообщения, однако в определенный момент осуществляется переход к представлению будущих
сегментов с помощью триплетов, каждый из которых будет состоять из двух целых
чисел и следующего за ними одного символа тексте. Каждый триплет описывает
способ построения следующей части сообщения. Например, пусть распакованный
текст имеет следующий вид (символе.! греческого алфавита здесь использованы для
того, чтобы данному примеру не придавался никакой определенный смысл):
apVrappp(5,4.a)
Строка сфсшйрр является уже распакованной частью сообщения. Для того чтобы разархивироаать остальной текст сообщения, необходимо сначала расширить
строку, присоединив к ней ту часть, которая в ней уже встречается (рис. 1.2G).
Первый номер в триплете указывает, сколько символов необходимо отсчитать в
обратном направлении в строке, чтобы найти первый символ добавляемого сегмента. В данном случае необходимо отсчитать в обратном направлении 5 символов, и
мы попадем на второй слева символ и уже распакованной строки. Второе число в
триплете задает количество последовательных символов справа от начального, которые составляют добавляемый сегмент. В нашем примере это число I, и это означает, что добавляемым сегментом будет auftp. Копируем его в конец строки и получаем новое значение распакованной части сообщения:
арЧгарррЧшрр
Наконец, последний элемент (в нашем случае это символ и) должен быть помещен в конец расширенной строки, в результате чего получаем полностью распакованное сообщение:
сфсихррВоорро
Теперь предположим, что сжатая версия текста имеет такой вил:
сфоаррв (5,4. а) (0.0,5) (8.6. Р)
Вначале распакуем первый триплет, в результате чего получим сообщение
следующего вида:
ароаррваорра (0.0.6) (8.6. р)
Теперь распакуем второй триплет и получим следующий результат:
«рааррОоорраб!». б.р)
Обратите внимание, что второй триплет (0.0.8) использовался только потому,
что символ 6 еще не встречался в этом тексте. И наконец, распакуем третий
триплет и получим полностью распакованное сообщение:
aPaapppViaPpoopPaaPpp

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

Комментарии на сайте: