Расшифровка по длинам кодов
Архив в формате DEFLATE не хранит дерево Хаффмана. В начале блока записаны только длины кодов всех знаков, а сами коды получатель восстанавливает по общему правилу — каноническому коду:
- знаки упорядочиваются по длине кода, а при равной длине — по номеру знака в Юникоде;
- первый знак получает код из одних нулей;
- каждый следующий — код предыдущего плюс один, записанный в двоичном виде; если длина выросла, к числу справа дописываются нули до новой длины.
Например, при длинах A — 1, B — 2, C — 2 коды такие: A = 0, B = 10, C = 11. Дано описание кода и поток бит. Восстановите текст.
Один из тестов — кусок первого тома «Войны и мира», закодированный кодом Хаффмана всего романа: 165 знаков, коды длиной от 3 до 21 бита.
Вход
В первой строке число знаков n (1 ≤ n ≤ 1000). Дальше n строк: номер знака в Юникоде и длина его кода, от 1 до 30. Длины задают правильный префиксный код. В последней строке — поток из нулей и единиц длиной до 106; он состоит из целого числа кодов.
Выход
Расшифрованный текст. В нём могут быть пробелы и переводы строк — выводите их как есть.
Примеры
Пример 1
10 32 3 44 4 1072 2 1074 3 1076 4 1077 4 1085 4 1086 4 1088 3 1090 4 11010001010110111110100110001011111000001100101001011010001011111000001111000101011100111001100
на дворе трава, на траве дрова
Пример 2
3 65 1 66 2 67 2 0101100
ABCAA
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сначала восстановите коды по правилу из условия и проверьте на первом примере: у «а» длина 2, у пробела, «в» и «р» — 3, у остальных — 4. Какой код получит запятая?
2Подсказка 2
Самое коварное место — переход к большей длине. После трёхбитных кодов 010, 011, 100 следующее число — 101, и к нему дописывается ноль: 1010. Если ноль не дописать, получится 0101 — а этот код начинается с 010, и префиксность пропала.
3Подсказка 3
Можно сложить коды в словарь «код → знак» и читать поток, набирая биты в строку. Это работает, но строка растёт и сравнивается на каждом бите. Коды одной длины — подряд идущие числа: нельзя ли узнать знак вычитанием?
4Идея
Для каждой длины L запомним первый код этой длины first[L], сколько их count[L] и с какого места в каноническом порядке они начинаются. Читая поток, держим число code и длину len прочитанного куска. Если code − first[len] меньше count[len], прочитан целый код, и знак — номер first_index[len] + (code − first[len]) в каноническом порядке. Иначе читаем следующий бит.
5Разбор
Первые коды считаются так же, как в RFC 1951: first[L] = (first[L − 1] + count[L − 1]) · 2. Это то же правило «плюс один и дописать нули», записанное сразу для целой длины.
Почему проверки code − first[len] < count[len] достаточно? В каноническом коде все коды длины L численно меньше, чем начала длиной L у более длинных кодов: длинные коды идут позже, и их первые L бит — число не меньше first[L] + count[L]. А меньше first[L] прочитанное число быть не может: тогда его начало было бы целым более коротким кодом, и мы бы уже остановились.
Ровно так, только сразу по нескольку бит, работают декодеры DEFLATE: смотрят на следующие биты таблицей и узнают знак за одно обращение.
5+Решение
6Сложность
Подготовка — O(n log n) на сортировку. Декодирование — O(1) на бит, всего O(B) для потока из B бит. Словарь «строка → знак» тоже даёт O(B) обращений, но каждое — со строкой длиной до 30 бит.
7Типичные ошибки
- Нет сдвига при росте длины. Коды перестают быть префиксными, и расшифровка рассыпается с первого же длинного кода.
- Порядок только по символу. Канонический порядок — сначала по длине, и только при равной длине по номеру знака.
- Один знак. Его код — один бит 0; поток из 1000 нулей — это 1000 знаков.
- Перевод строки в тексте. Знак с номером 10 — обычный знак кода; выводите его, а не пропускайте.