Основной принцип работы алгоритмов этого семейства в следующем: в соответствии с поступающими на вход словами-символами алгоритм заносит специальным образом построенные фразы в свой словарь, и затем, когда встречает во входном потоке эти фразы, то заменяет их на индекс в словаре. Почти все существующие алгоритмы этого класса отличаются в основном способом ведения этого словаря.
Самым известным алгоритмом этого класса (частенько ошибочно называемый методом Лемпеля-Зива) является алгоритм Тэри Уэлча (Terry Welch), описанный им в 1984 г. для применения в высокопроизводительных контроллерах диска. Однако, наиболее широкое применение он нашел в скоростных модемах и вошел составной частью в протокол связи v.42bis. (Метод обозначается LZW).
Метод LZW в своей работе пользуется словарем, содержащим 4096 элементов. Элементы с номерами 0 - 255 указывают на отдельные символы. эти элементы словаря постоянны, т.е. не изменяются в процессе работы алгоритма. остальные элементы с номерами 256 - 4095 изначально имеют пустые ссылки, а в процессе работы указывают на фразы, составленные по следующему правилу: новая фраза образуется добавлением текущего символа к концу текущей фразы. Схема LZW алгоритма сжатия выглядит следующим образом:
w = NIL
loop
read a character K
if wK exists in the dictiontary
w = wK
else
output the code for w
add wK to the dictionary
w = K
endloop
Когда словарь переполняется, алгоритм Уэлча приписывает нулевые ссылки элементам словаря с номерами 256 - 4095, т.е. как бы начинает свою работу сначала. Уже существуют модификации этого алгоритма, сбрасывающие при переполнении не весь словарь, а только какую-то его часть, например, первую половину.
Алгоритм распаковки несколько сложнее:
input oldcode
output dictionary[oldcode]
loop
input code
w = dictionary[oldcode]
if dictionary[code] <> NIL
output dictionary[code]
K = first character of dictionary[code]
else
K = first character of w
endif
add wK to the dictionary
oldcode = code
endloop
Все алгоритмы данного семейства можно легко классифицировать по способу образования новых фраз словаря и по способу преодоления переполнения этого словаря.
Метод LZW с некоторыми специфичными изменениями также входит в состав формата записи компьютерных изображения GIF.
| Изменена 19.03.2011 06:45 MSK |
|
|