Алгоритмы семейства LZ77 довольно просты в реализации и обладают большим быстродействием по сравнению с LZ78. Поэтому именно они широко используются в популярных архиваторах. Эффект сжатия у этих алгоритмов достигается за счет замены уже встречавшихся ранее в тексте фраз на пару значений (ссылка назад, длина фрагмента). Все алгоритмы этого семейства отличаются друг от друга размером окна обзора предыдущего текста и максимальным и минимальным размером заменяемого фрагмента. От выбора этих параметров существенным образом зависит быстродействие конкретной реализации алгоритма. Приведем схему наиболее популярного варианта LZSS, обладающего самым большим быстродействием при соответствующем подборе параметров:
while (lookAheadBuffer not empty)
get a pointer (position, lenght) to the longest match in
the window for lookahead buffer;
if (lenght > MINIMUM_MATCH_LENGHT)
output a pair (position, lenght);
shift the window lenght characters along;
else
output the first character in the lookahead buffer;
shift the window 1 character along;
endif
endwile
Алгоритм распаковки еще более прост и быстр: если на вход поступает пара (position, length) - выдать на выход фрагмент текста из окна длиной lenght символов начиная с позиции position, если же на вход поступает один символ, то он копируется в выходной поток. После этого окно сдвигается на соответствующее число символов.
| Изменена 19.03.2011 06:45 MSK |
|
|