Информатика · объяснение и практика

Как проверить LZ78 по парам, словарю и завершающему хвосту

Разобрать сообщение жадным словарём LZ78, явно передать известный последний хвост и проверить декодирование без оценки выдуманной экономии байтов.

Синие фигурные скобки держат между собой оранжевый квадрат.

Вузовский уровень · Все вузовские темы

В теме Кодирование чисел, текста, изображения и звука · Учебная карта

Главная мысль

LZ78 создаёт словарь фраз во время чтения сообщения. Каждая новая фраза передаётся индексом уже известного префикса и следующим символом. Чтобы короткий пример был полностью воспроизводим, отдельно задают способ передачи хвоста, который уже целиком есть в словаре.

Метод и условия

Начальный словарь содержит пустую строку с индексом ноль. В текущем месте сообщения найдите самый длинный префикс, который уже записан. Если после него есть новый символ, выдайте пару из индекса префикса и этого символа, добавьте полученную фразу в словарь и продолжайте после неё. Индексы присваиваются в порядке добавления. Ранее добавленная фраза не получает новый индекс при каждом повторе.

Жадность относится к известному префиксу: нельзя остановиться на более коротком только потому, что так удобнее разделить строку. При этом итоговая новая фраза является первым ещё неизвестным продолжением. Сообщение может закончиться на фразе, которая уже есть в словаре. В нашей явной договорённости тогда выдаётся ссылка с пустым новым символом, а дополнительная словарная запись не создаётся. Другой формат мог бы использовать специальный символ конца, но смешивать две договорённости в одном примере нельзя.

Проверка и типичная ошибка

Для декодирования достаточно того же начального словаря и списка пар. Возьмите фразу по переданному индексу, допишите новый символ и добавьте полученный текст к выходу. Если новый символ непустой, та же фраза добавляется в словарь декодера. Пустой завершающий символ только воспроизводит уже известный хвост. В каждый момент ссылка должна указывать на существующую запись, поэтому будущее содержимое словаря не требуется.

Независимая проверка состоит в побуквенном сравнении восстановленного сообщения с исходным. Простое совпадение числа фраз недостаточно: неправильное разбиение может давать столько же пар. Также логические пары не являются готовым архивным форматом. Чтобы посчитать реальный размер, нужны правила кодирования индексов, ширина символов, упаковка битов и служебные данные. На коротком сообщении представление может оказаться длиннее исходного; алгоритм не обещает уменьшение любой строки. Учебный интерфейс поэтому показывает пары, словарь и восстановление, а не выдуманное число сэкономленных байтов.

Пример

Для ABAB первые две пары равны (0,A) и (0,B). Затем известный префикс A вместе с B образует новую фразу AB и пару (1,B).

Для AA после пары (0,A) остаётся известный хвост A, поэтому последняя пара равна (1,пусто). Декодер выдаёт ещё A, не создавая дубликат словарной записи.

От чтения к действию

А теперь — вы

Что делает пара с пустым новым символом в принятом формате?

Частые вопросы

Почему пустой символ в конце?

В этой явной договорённости остаток, уже имеющийся в словаре, передаётся ссылкой без добавления нового символа и новой записи.

Это число байтов после сжатия?

Нет. Пары и словарь показаны логически; размер зависит от способа кодирования индексов, алфавита и служебного формата.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться