LZW алгоритм
Пакует и распаковывает строку алгоритмом сжатия Лемпель-Зив-Велч (LZW)
Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/9069/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).
На этой странице представлены калькуляторы для сжатия и распаковки строки методом LZW. Метод прост и надежен, не требует хранения словаря - словарь создается динамически при сжатии и распаковке. Для изучения работы алгоритма установите галочку "Показать детали" - калькуляторы будут выдавать журнал работы и сформированные справочники. Для представления строк в памяти можно выбрать какую-либо стандартную кодировку строк, либо задать начальный словарь вручную.
LZW сжатие текста
Запакованную предыдущим калькулятором строку или файл можно передать в следующий калькулятор для проверки распаковки. Кроме битового массива или файла необходимо задать способ формирования начального словаря (выбрать ту же самую кодировку или задать словарь явно).
LZW распаковка
- Перетащите сюда файлы
Алгоритм Lempel-Ziv-Welch
Алгоритм сжатия без потерь LZ78 был опубликован в 1978-году Авраамом Лемпелем и Яаковом Зивом и затем был доработан Терри Велчем в 1984. После публикации Велча алгоритм получил название LZW по перым буквам фамилий авторов (Lempel, Ziv, Welch). Алгоритм был запатентован, но к настоящему времени сроки действия всех патентов истекли, что дает нам прекрасную возможность опубликовать свою реализацию тут.
Описание алгоритма LZW
- Формируется начальный словарь на основе всех возможных символов.
- Во входную фразу W заносится первый символ.
- Считать следующий символ K.
- Если достигли конца, то выдать код для W, иначе:
Если фраза WK уже имеется в словаре, то присвоить входной фразе значение WK и перейти к пункту 3 ,
Иначе выдать код W, добавить WK в словарь и присвоить входной фразе значение K. Перейти к пункту 3.
Для декодирования сформированных таким способом данных, не нужно хранить словарь, он воссоздается сам в процессе работы алгоритма распаковки:
- Формируется начальный словарь на основе всех возможных символов.
- Во входную фразу W заносится первый код сообщения.
- Считать следующий код K из сообщения.
- Если достигли конца, то выдать символ, с кодом W, иначе:
Если фразы c кодом WK нет в словаре, выдать фразу, с кодом W, а фразу с кодом WK добавить в словарь.
Иначе присвоить входной фразе код WK и перейти к 3.
В оригинале статьи Велча предполагалось кодировать фразу в словаре кодом фиксированного размера 12 бит, однако для небольших сообщений такой подход может даже увеличить длину закодированного сообщения. Поэтому довольно часто используют динамическую длину кода, изменяемую всякий раз при достижении предела словаря.
Управление размером словаря
В описанном выше алгоритме сжатия размер словаря ничем не ограничен. На практике это может приводить к проблемам при упаковке больших объемах данных.
Известны модификации алгоритма, пытающихся исправить эту проблему:
- LZC - реализация алгоритма в утилите compress ограничивает максимальный размер словаря 16-ю битами. При достижении максимального размера, словарь перестает изменяться. Алгоритм отслеживает степень сжатия и при ее значительной деградации сбрасывает словарь и начинает формировать его заново.
- LZT - при переполнении удаляет из словаря фразу, которая дольше всех не использовалась
Особенности нашей реализации
Начальный словарь
Наша реализация алгоритма подразумевает бесконечно растущий словарь, что для очень больших данных может быть слишком затратно. Размер кодов фраз начинается от 8 бит для начального словаря, определяемого стандартной кодировкой или меньше, для словаря заданного вручную. В последнем случае размер кодов фраз - это минимальное число бит, необходимое для выражения количества символов в словаре см. Сколько бит занимает число.
Многобайтовые кодировки
Некоторые кодировки могут занимать больше 1 байта на символ, например, кодировка UTF-8 содержит символы переменной длины от 1-го до 4-х байт. Но тем не менее с любой выбранной кодировкой начальный словарь будет содержать 256 элементов с кодами от 0 до 255.
Для многобайтовых кодировок динамически формируемый словарь будет выглядеть достаточно экзотично - фразы его неизбежно будут составляться из разных частей соседних символов. В этом случае для наглядности в описании словаря мы используем заполнитель пропущенных байтов (по умолчанию это символ '~'). К примеру, при сжатии фразы "9 €", представленной в кодировке UTF-8, динамический словарь может быть заполнен комбинациями из следующих символов:
9 - девятка,
' ' - пробел,
€~~ - первый байт символа евро,
~€~ - второй байт символа евро,
~~€ - третий байт символа евро,
€~ - два первых байта символа евро,
~€ - два последних байта символа евро,
€ - все три байта символа евро.
Такое описание символа введено нами лишь для удобства восприятия, стоит помнить что составные части многих многобайтовых символов совпадают.
Например:
€~~ - первый байт символа евро, код в utf-8 = 226
₽~~ - первый байт символа рубля, код в utf-8 = 226.
Заполнение концовки нулями
Алгоритм сжатия может выдать битовый массив, размер которого не кратен 8. В этом случае калькулятор упаковки дозаполняет выходной массив нулевыми битами. Так как наша реализация алгоритма использует переменный размер слова, такой подход может породить проблемы, если вручную заданный начальный словарь очень мал.
Например, вот с такими параметрами конечное сообщение составит всего 18 бит и 6 бит придется дополнить нулями, чтобы сохранить все сообщение в двоичном файле. Так как с указанными параметрами, размер слова составляет всего 4 бита, то при распаковке будет считано лишнее слово, и если бы мы создавали исходный словарь с кодом первого символа = 0, то распаковался бы лишний символ. Мы решаем эту проблему путем добавления в словарь нулевого символа, который принято интерпретировать, как конец строки. При использовании 8-битной кодировки в качестве начального словаря эта проблема никогда не возникнет, так как размер слова всегда как минимум 8 бит.
Комментарии