Алгоритмы и структуры данных

Алгоритм LZW

Метод без потерь для сжатия данных, который основан на построении и использовании словаря. Он был разработан Терри Велчем в 1984 году.

Алгоритм:
1. Создаем словарь, содержащий начальный набор символов (обычно это все возможные символы, например, ASCII).
2. Читаем символы исходной строки один за другим.
3. Проверяем, есть ли текущая последовательность символов в словаре:
а. Если да, добавляем текущий символ к последовательности.
б. Если нет, записываем индекс текущей последовательности в выходной поток и добавляем новую запись в словарь с текущей последовательностью символов.
4. Повторяем шаги 2-3 до тех пор, пока не прочитаем все символы исходной строки.
5. Записываем последний индекс в выходной поток.
6. Завершаем сжатие.

Сложность алгоритма LZW зависит от размера исходной строки и размера словаря. В худшем случае: O(n^2), где n - размер строки.

www.tgoop.com/the_algorithms/4607

6.5K viewsNov 18, 2023 at 09:04

Алгоритм LZW

Метод без потерь для сжатия данных, который основан на построении и использовании словаря. Он был разработан Терри Велчем в 1984 году.

Алгоритм:
1. Создаем словарь, содержащий начальный набор символов (обычно это все возможные символы, например, ASCII).
2. Читаем символы исходной строки один за другим.
3. Проверяем, есть ли текущая последовательность символов в словаре:
а. Если да, добавляем текущий символ к последовательности.
б. Если нет, записываем индекс текущей последовательности в выходной поток и добавляем новую запись в словарь с текущей последовательностью символов.
4. Повторяем шаги 2-3 до тех пор, пока не прочитаем все символы исходной строки.
5. Записываем последний индекс в выходной поток.
6. Завершаем сжатие.

Сложность алгоритма LZW зависит от размера исходной строки и размера словаря. В худшем случае: O(n^2), где n - размер строки.

BY Алгоритмы и структуры данных