Алгоритм универсального кодирования методом Лемпела-Зива.
Этот алгоритм относится к классу универсальных потому, что он не требует априорных знаний о статистике символов. Такой метод носит менее математически обоснованный характер, но более практический.
Первый алгоритм разработан в 1971 году в Израиле Лемпелом и Зивом (LZ 77). Одной из причин популярности алгоритма LZ 77, а также семейства алгоритмов LZ 77, является их исключительная простота при высокой эффективности сжатия.
LZ 77 использует уже просмотренную часть сообщения как словарь, а чтобы добиться сжатия он пытается заменить очередной фрагмент сообщения на соответствующий указатель в содержимое словаря, т.е. LZ 77 использует как бы скользящее окно по сообщению, разделенное на две части. Большая часть окна - словарь, включающий уже просмотренную часть сообщения, меньшая часть окна является буфером, содержащим еще не закодированные символы входного потока.
Алгоритм пытается найти в словаре фрагмент сообщения, совпадающий с содержимым буфера. На практике размер словаря составляет несколько кбайт, а размер буфера - до 100 байт. В результате кодирования формируется совокупность групп по три элемента в каждой < a,l,z >, где a- относительный адрес в словаре, т.е. смещение в словаре относительно его начала до первого символа фрагмента, с которым совпадает содержимое буфера; l - число совпадений элементов буфера и словаря; z –первый несовпадающий со словарем символ в буфере.
Пример. КРАСНАЯ КРАСКА
Шаг кодирования |
Словарь (8) |
Буфер (5) |
Код |
1 |
…….. |
КРАСН |
< 0,0,К> |
2 |
…….К |
РАСНА |
< 0,0,Р> |
3 |
……КР |
АСНАЯ |
< 0,0,А> |
4 |
…..КРА |
СНАЯ_ |
< 0,0,С> |
5 |
….КРАС |
НАЯ _К |
< 0,0,Н> |
6 |
…КРАСН |
АЯ_КР |
< 5,1,Я> |
7 |
.КРАСНАЯ |
_КРАС |
< 0,0,_> |
8 |
КРАСНАЯ_ |
КРАСК |
< 0,4,К> |
9 |
АЯ_КРАСК |
А |
< 0,0,А> |
Для данного кода длину кодовой комбинации можно определить по следующей формуле:
-
операция округления в большую сторону.
Такой алгоритм еще часто называют словарным. Очевидно, что сжатие будет иметь место, если длина полученной кодовой комбинации будет меньше кода того же сообщения при непосредственном кодировании. Для словарного кодирования учтено:
1.Часто повторяющиеся цепочки кодируются очень эффективно.
2.Редко повторяющиеся символы и их последовательности с течением времени удаляются из словаря.
3.Можно доказать, что словарное кодирование асимптотически оптимально, т.е. что длина кодового слова стремится к энтропии этого текста.
4.Практически достижимая степень сжатия для этих кодов 50-60 %.
В семейство алгоритмов LZ входит несколько моделей, которые модифицированы различными авторами в аспекте механизмов формирования кодовых групп, но во всех механизмах используется словарь. В настоящее время наибольшее распространение получил алгоритм LZW (1984 г.). В этом алгоритме длина кода уменьшается, так как не используется буфер. А кодирование проводится только по словарю, следовательно, кодовая группа определяется только длиной словаря.
Декодирование словарного кода происходит в обратном порядке и упрощается тем, что не требует поиска совпадений в словаре.