В основе алгоритма Хаффмана лежит кодирование не байтами, а битовыми группами.
· перед началом кодирования производится частотный анализ кода документа и выявляется частота повтора каждого из встречающихся символов.
· чем чаще встречается тот или иной символ, тем меньшим количеством битов он кодируется (соответственно, чем реже встречается символ, тем длиннее его кодовая битовая последовательность).
· образующаяся в результате кодирования иерархическая структура прикладывается к сжатому документу в качестве таблицы соответствия.
В связи с тем, что к сжатому архиву необходимо прикладывать таблицу соответствия, на файлах малых размеров алгоритм Хафмана малоэффективен. Практика также показывает, что его эффективность зависит и от заданной предельной длины кода (размера словаря). В среднем, наиболее эффективными оказываются архивы с размером словаря от 512 до1024 единиц.
[58 слайд]
Используется идея адаптивного сжатия. Алгоритмы Лемпеля-Зива сводятся к поиску в потоке повторяющихся последовательностей и замене этих последовательностей на их номер в динамическом словаре. Различие состоит в способах кодирования номера и формировании словаря. За один проход по тексту одновременно динамически строится словарь и кодируется текст. При этом словарь не хранится – за счёт того, что при декодировании используется тот же самый алгоритм построения словаря, словарь динамически восстанавливается. В сжатое представление записывается найденный код слова и расширенная буква, а словарь пополняется расширенной комбинацией. Поскольку номер последовательности в словаре содержит больше битов, чем символы исходного потока, алгоритмы Лемпеля-Зива предполагают дальнейшее перекодирование преобразованного потока кодом Хаффмана. Большинство современных архиваторов, такие, как PkZip, GNU Zip, RAR, основаны на вариациях и аналогах алгоритмов Лемпеля-Зива.
Алгори́тм Ле́мпеля — Зи́ва — Ве́лча (Lempel-Ziv-Welch, LZW) — это универсальный алгоритм сжатия данных без потерь, созданный Абрахамом Лемпелем (англ. Abraham Lempel), Якобом Зивом (англ. Jacob Ziv) и Терри Велчем (англ. Terry Welch). Он был опубликован Велчем в 1984 году, в качестве улучшенной реализации алгоритма LZ78. Алгоритм разработан так, чтобы его можно было быстро реализовать, но он не обязательно оптимален, поскольку он не проводит никакого анализа входных данных. Акроним «LZW» указывает на фамилии изобретателей алгоритма: Лемпель, Зив и Велч. Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками (в случае 8-битных символов — это 256 записей). По мере кодирования, алгоритм просматривает текст символ за символом, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символ, где код ссылается на соответствующий первый символ.
[60 слайд]
После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки. Алгоритму декодирования на входе требуется только закодированный текст, поскольку он может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту. На момент своего появления алгоритм LZW давал лучший коэффициент сжатия, для большинства приложений, чем любой другой хорошо известный метод того времени. Он стал первым широко используемым на компьютерах методом сжатия данных. В 1987 году алгоритм стал частью стандарта на формат изображений GIF. Он также может (опционально) использоваться в формате TIFF. В настоящее время, алгоритм содержится в стандарте PDF.
