Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


2.2.1. Недостатки

Перед тем, как обсуждать алгоритм LZ78, остановимся на недостатках метода LZ77 и его вариантов. Было уже отмечено, что этот алгоритм основывается на предположении, что похожие образцы сжимаемых данных находятся близко друг от друга. Если содержимое файла не удовлетворяет этому условию, то он будет сжиматься плохо. Простой пример это текст, в котором слово «economy» встречается часто и равномерно распределено по всему тексту. Может случиться, что когда это слово попадает в упреждающий буфер, его предыдущая копия уже вышла из буфера просмотра. Более лучший алгоритм мог бы сохранять часто встречающиеся слова в словаре, а не сдвигал бы их все время.

Другой недостаток метода - это ограниченные размеры упреждающего буфера. Размер совпадающей строки лимитирован числом , но  приходится держать маленьким, так как процесс сравнения строк основан на сравнении индивидуальных символов. Если удвоить , то степень сжатия могла бы возрасти, но одновременно с этим произойдет замедление процесса поиска совпадений. Размер  буфера поиска тоже ограничен. Большой буфер поиска мог бы тоже улучшить компрессию, но опять возрастет сложность поиска по дереву, даже двоичному. Увеличение буферов также означает удлинение меток, что сокращает фактор сжатия. Двухбайтовые метки сжимают последовательности из 2-х символов в два байта плюс один флаговый бит. Запись двух байтов кода ASCII в виде этого же кода плюс два флаговых бита дает весьма малую разницу в размере по сравнению с записью метки. Это будет лучший выбор для кодера в смысле экономии времени, а плата всего один лишний бит. Мы будем говорить, что в этом случае кодер имеет 2-х байтовую точку безызбыточности. Для более длинных меток точка безызбыточности вырастает до 3 байтов.

 



<< ПредыдущаяОглавлениеСледующая >>