Временная сложность
Лучший: O(n)
Средний: O(n)
Худший: O(n)
LZW (Lempel–Ziv–Welch) — это адаптивный алгоритм сжатия на основе словаря, опубликованный Терри Уэлчем в 1984 году. Кодировщик и декодировщик на лету создают одинаковый словарь на основе потока данных — передавать отдельный словарь не требуется.
Как это работает:
1. Инициализировать словарь всеми строками из одного символа
2. Поддерживать текущую фразу w (изначально пустую)
3. Для каждого следующего символа c:
- Если w+c уже есть в словаре, установить w = w+c
- Иначе выдать код для w, добавить w+c в словарь и установить w = c
4. После обработки последнего символа выдать код оставшейся фразы w
Почему это работает:
Повторяющиеся фразы получают короткие целочисленные коды. Более длинные фразы автоматически добавляются в словарь. Декодировщик повторяет действия кодировщика: каждый полученный код преобразуется в строку, а следующая ещё не встречавшаяся фраза добавляется по тому же правилу. Благодаря этому обе стороны остаются синхронизированными.
Временная сложность:
Лучшая: O(n)
Средняя: O(n)
Худшая: O(n) при использовании хеш-словаря
Пространственная сложность: O(d), где d — количество записей в словаре
Свойства:
- Адаптивное словарное кодирование без потерь
- Исторически использовался в GIF и Unix compress
- Не требует предварительного анализа частот
- Рост словаря можно ограничить (фиксированной разрядностью кодов) для потоковых форматов
LZW показывает, как растущая таблица кодов преобразует повторяющиеся структуры в более короткие целочисленные коды без отдельной модели источника данных.
Похожие алгоритмы
Частые вопросы
- Что такое LZW?
- LZW (Lempel–Ziv–Welch) — это адаптивный алгоритм сжатия на основе словаря, опубликованный Терри Уэлчем в 1984 году. Кодировщик и декодировщик на лету создают одинаковый словарь на основе потока данных — передавать отдельный словарь не требуется.
- Какова сложность LZW?
- Время (среднее): O(n) · Память: O(d)
- Для кого предназначена визуализация LZW?
- Визуализация LZW рассчитана на средний уровень в категории «Сжатие данных». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с LZW?
- В той же категории (Сжатие данных) вы можете изучить: Run-Length Encoding, LZ77, Huffman Coding. Каждый из них имеет интерактивную визуализацию.