Алгоритм LZW. Способ сжатия данных, который извлекает преимущества при повторяющихся цепочках данных

Алгоритм LZW является развитием алгоритма [[LZ78]], предложенного Лемпелем и Зивом в 1978 году.

Этот алгоритм импользуется при сжатии изображений в таких форматах как [[GIF]] и [[TIFF]]. Следует отметить что данный алгоритм был защищен патентом, которым обладает компания [[Unisys]].

==Основные характеристики==

; Степень сжатия : от 5/7 до 4 раз, в наилучшем случае до 1000 (!)

; Специализация : Ориентирован на 8-ми битные изображения машинного происхождения, т.е. не фотографии

; Симметричность : почти симметричен

==Стив Блэксток: Объяснение LZW и GIF==

Я надеюсь, что этот маленький документ поможет просветить тех, кто хочет знать немного больше об алгоритме сжатия Lempel-Ziv Welch и, конкретно, о его реализации для формата GIF.

Перед тем, как мы начнем, немного о терминологии в свете данного документа:

; "Символ" : фундаментальный элемент данных. В обычных текстовых файлах это отдельный байт. В растровых изображениях, которыми вы заинтересовались, это индекс, который указывает цвет данного пиксела. Я буду ссылаться на произвольный символ как на "K".

; "Поток символов" : поток символов такой, как файл данных.

; "Цепочка" : несколько последовательных символов. Длина цепочки может изменяться от 1 до очень большого числа символов. Я могу указывать произвольную цепочку как "[...]K".

; "Префикс" : почти то же самое, что цепочка, но подразумевается