Сжатие LZW
LZW назван по именам Абрахама Лемпеля, Якоба Зива и Терри Велча, ученых, создавших этот алгоритм. Это алгоритм сжатия без потерь, работающий с использованием "словаря". Его основной принцип заключается в сканировании файла на последовательности данных, повторяющихся более одного раза. Такие последовательности заносятся в словарь, а в сжатом файле заменяются на ссылки.
Лемпель и Зив опубликовали серию статей о различных алгоритмах компрессии. Их первый алгоритм был опубликован в 1977 году и поэтому называется LZ77. Этот алгоритм хранит словарь вместе с данными.
Например, вы хотите сжать следующую строку текста: the quick brown fox jumps over the lazy dog. Слово 'the' встречается дважды, поэтому данные могут быть сжаты следующим образом: the quick brown fox jumps over << lazy dog. где << - указатель на первые четыре символа в строке.
В 1978 году Лемпель и Зив опубликовали вторую статью, описывающую подобный алгоритм под названием LZ78. В нем использовались отдельные словари.
Например, вы снова хотите сжать строку текста: the quick brown fox jumps over the lazy dog. Слово 'the' встречается дважды,поэтому оно помещается в словарь, добавляемый к сжатому файлу, а в исходном тексте заменяется на *. Сжатая строка будет выглядеть так: * quick brown fox jumps over * lazy dog.
Как работает LZW
В 1984 году Терри Велч работал над алгоритмом сжатия для высокопроизводительных дисковых контроллеров. Он создал простой алгоритм на основе алгоритма LZ78, который теперь называется LZW.
Алгоритм LZW заменяет последовательности символов отдельными кодами. Он не производит анализ поступающего потока данных. Вместо этого он добавляет каждую новую строку символов в таблицу строк. Компрессия происходит за счет замены в выходном потоке последовательности символов ее кодом.
Коды, которые алгоритм LZW помещает в выходной поток, могут быть произвольной длины, но должны содержать больше бит, чем одиночный символ. Первые 256 кодов по умолчанию представляют собой стандартную таблицу символов. Оставшиеся коды соответствуют строкам, которые обрабатывает алгоритм. Простые реализации алгоритма работают с кодами 12-битной длины. Это означает, что коды 0-255 соответствуют одиночным байтам, а коды 256-4095 соответствуют подстрокам.
Достоинства и недостатки
LZW сжатие отлично работает с файлами, содержащими большое число повторяющихся данных, например с текстами и монохромными битмапами. Уже сжатые файлы, не содержащие повторяющейся информации, при обработке по этому алгоритму могут стать больше!
LZW сжатие очень быстрое.
Требуются лицензионные отчисления за использование этого алгоритма в приложениях (см. ниже).
Где используется LZW сжатие
LZW сжатие может быть использовано в различных форматах файлов:
Замечания
Некоторые версии LZW сжатия защищены авторскими правами. Несколько лет назад их владелец, компания Unisys, потребовала лицензионных отчислений от компаний, которые используют этот алгоритм в своих программах. Это серьезно снизило популярность алгоритма и началась его замена на более дешевые (читай: бесплатные) алгоритмы. Конечные пользователи могут не беспокоиться, это требование относится только к разработчикам программ. Но в конечном итоге, эта цена ложится на стоимость программ.
