LZ77:          

Это была первая опубликованная версия LZ-метода [118]. В ней указатели обозначают фразы в окне постоянного pазмеpа, пpедшествующие позиции кода. Мак- симальная длина заменяемых указателями подстрок определяется параметром F (обычно 10-20). Эти ограничения позволяют LZ77 использовать "скользящее окно" из N символов. Из них первые N-F были уже закодированы, а последние F состав- ляют упpеждающий буфер. При кодировании символа в первых N-F символах окна ищется самая длинная, совпадающая с этим буфером, строка. Она может частично перекрывать буфер, но не может быть самим буфером. Hайденное наибольшее соответствие затем кодируется триадой <i,j,a>, где i есть его смещение от начала буфера, j - длина соответствия, a - первый символ, не соответствующий подстроке окна. Затем окно сдвигается вправо на j+1 символ, готовое к новому шагу алгоритма. Привязка определенного символа к каждому ука- зателю гарантирует, что кодирование будет выполнятся даже в том случае, если для первого символа упpеждающего буфера не будет найдено соответствия. Объем памяти, требуемый кодировщику и раскодировщику, ограничивается раз- мером окна. Смещение (i) в триаде может быть представлено [log(N-F)] битами, а количество символов, заменяемых триадой, (j) - [logF] битами. Раскодирование осуществляется очень просто и быстро. При этом поддержива- ется тот же порядок работы с окном, что и при кодировании, но в отличие от по- иска одинаковых строк, он, наоборот, копирует их из окна в соответствии с оче- редной триадой. На относительно дешевой аппаратуре при раскодировании была до- стигнута скорость в 10 Мб/сек [43]. Зив и Лемпелл показали, что, при достаточно большом N, LZ77 может сжать текст не хуже, чем любой, специально на него настроенноый полуадаптированный словарный метод. Этот факт интуитивно подтверждается тем соображением, что по- луадаптированная схема должна иметь кроме самого кодируемого текста еще и сло- варь, когда как для LZ77 словарь и текст - это одно и то же. А размер элемента полуадаптированного словаря не меньше размера соответствующей ему фразы в ко- дируемом LZ77 тексте. Каждый шаг кодирования LZ77 требует однакового количества времени, что яв- ляется его главным недостатком, в случае, если оно будет большим. Тогда прямая реализация может потребовать до (N-F)*F операций сравнений символов в просмат- риваемом фрагменте. Это свойство медленного кодирования и быстрого раскодиро- вания характерно для многих LZ-схем. Скорость кодирования может быть увеличена за счет использования таких СД, как двоичные деревья[5], деревья цифрового по- иска или хэш-таблицы [12], но объем требуемой памяти при этом также возрастет. Поэтому этот тип сжатия является наилучшим для случаев, когда однажды закоди- рованный файл (предпочтительно на быстрой ЭВМ с достаточным количеством памя- ти) много раз развертывается и, возможно, на маленькой машине. Это часто слу- чается на практике при работе, например, с диалоговыми справочными файлами, руководствами, новостями, телетекстами и электронными книгами. е.

 

Hosted by uCoz