Задача Q. 9. LZ77 шифрование
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 с
Ограничение по памяти: 1024 МБ
LZ77. Алгоритм Лемпеля-Зива
Одной из причин широкой популярности словарно-ориентированных алгоритмов сжатия является их исключительная простота при высокой эффективности сжатия.
Основная идея LZ77 состоит в том, что второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на ее первое вхождение.
LZ77 использует "скользящее" по сообщению окно, разделенное на две неравные части.
- Первая, большая по размеру, является словарем, включает уже просмотренную часть сообщения.
- Вторая, намного меньшая, является буфером, содержащим еще незакодированные символы входного потока.
Обычно размер окна составляет несколько килобайт, а размер буфера - не более ста байт.
LZ77 использует уже просмотренную часть сообщения как словарь. Чтобы добиться сжатия, он пытается заменить очередной фрагмент сообщения, находящийся в буфере, указателем на содержимое словаря. Алгоритм LZ77 выдает коды, состоящие из трех элементов:
- смещение в словаре (относительно его начала) подстроки, совпадающей с началом содержимого буфера;
- длина этой подстроки;
- первый символ буфера, следующий за подстрокой.
Пример. Закодировать по алгоритму LZ77 строку "AAAAAAAAAAAA"
Длина кода алгоритма LZ77
Длина кода вычисляется следующим образом:
- длина подстроки не может быть больше размера буфера,
- а смещение не может быть больше размера словаря -1.
Следовательно,
- длина двоичного кода смещения будет ⌈𝑙𝑜𝑔2 (размер словаря)⌉,
- длина двоичного кода для длины подстроки будет ⌈𝑙𝑜𝑔2(размер буфера+1)⌉.
- Символ кодируется 8 битами (например, ASCII+).
В примере длина полученного кода равна 4*(3+3+8)=56 бит, против 12*8=96 бит исходной длины строки.
В компактном представлении полученный код можно записать строкой битов:
00000001000001111001010000011010110100000100110001000001
Или в HEX-формате:
0107941ad04c41
LZ77-алгоритм распаковки
Для распаковки надо знать длину словаря.
Пример. Распаковка текста, сжатого алгоритмом LZ77. Пусть длина словаря - 8 байт (символов). Коды сжатого сообщения:
(0, 0, 'A'), (7, 1, 'A'), (5, 3, 'A'), (1, 4, 'A')

Формат входных данных

Строка шестнадцатеричных цифр (строка в HEX-формате) – компактное представление кодов алгоритма LZ77

Формат выходных данных

Восстановленная исходная строка

Примеры

стандартный вводстандартный вывод
0020f85040 AAA
0020f8507468200410 AAAAAAAA
00410042c24184420142 ABABABABABAB