84
правки
Изменения
м
Алгоритм не проводит анализ входных данных поэтому не оптимален, но быстро реализуем.
LZW - это способ сжатия данных, который извлекает преимущества при повторяющихся цепочках данных. Поскольку растровые данные обычно содержат довольно много таких повторений, LZW является хорошим методом для их сжатия и раскрытия.
В 1987 году алгоритм стал частью стандарта на формат изображений GIF. Он также может LZW отчасти используется во многих популярных программах сжатия данных (опциональноZIP, ARJ, LHA) использоваться . Этот метод позволяет достичь одну из наилучших степеней сжатия среди других существующих методов сжатия графических данных, при полном отсутствии потерь или искажений в исходных файлах. В настоящее время испольуется в формате файлах формата TIFF, PDF, GIF, PostScript и других.
В настоящее время алгоритм содержится в стандарте PDF.
Нет описания правки
}}
Он был создан Абрахамом Лемпелем(''Abraham Lempel''), Якобом Зивом (''Jacob Ziv'') и Терри Велчем (''Terry Welch''). Опубликован Велчем в 1984 году, в качестве улучшенной реализации [[Алгоритмы LZ77 и LZ78|алгоритма LZ78]], опубликованного Лемпелем и Зивом в 1978 году.
== Применение ==
== Описание ==
Процесс сжатия выглядит достаточно простоследующим образом. Считываются последовательно Последовательно считываются символы входного потока и проверяетсяпроисходит проверка, есть существует ли в созданной таблице строк такая строка. Если такая строка естьсуществует, то считывается следующий символ, а если строки нетстрока не существует, то заносится в поток заносится код для предыдущей найденной строки, далее строка заносится в таблицу и , а поиск начинается снова начинается поиск.<br> Например, если сжимают байтовые данные (текст), то строк в таблице окажется 256 (от "0" до "255"). Если используется 10-битный код, то под коды для строк остаются значения в диапазоне от 256 до 1023. Новые строки формируют таблицу последовательно, т. е. можно считать индекс строки ее кодом. <br>
Алгоритму декодирования на входе требуется только закодированный текст, поскольку он может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту.
<br><br>
Мало того, описанное выше правило кодирования мы можем применять в общем случае не только к подряд идущим одинаковым цветам точек, но и к последовательностям, у которых очередной добавляемый символ равен первому символу цепочки.
== Достоинства и недостатки ==
+ Не требует вычисления вероятностей встречаемости символов или кодов. <br>
+ Для выполнения обратного процесса ("распаковки") нет необходимости сохранять таблицу в документе.<br>
+ Данный тип компрессии не вносит искажений в исходный графический файл, и подходит для сжатия растровых данных любого типа - монохромных, черно - белых, или полноцветных. <br>
- Алгоритм не проводит анализ входных данных поэтому не оптимален. <br>
== Патенты ==
На алгоритм LZW и его вариации был выдан ряд патентов, как в США, так и в других странах.
<br>
