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

Вузовский уровень · Все вузовские темы
В теме Кодирование чисел, текста, изображения и звука · Учебная карта
Главная мысль
LZ78 создаёт словарь фраз во время чтения сообщения. Каждая новая фраза передаётся индексом уже известного префикса и следующим символом. Чтобы короткий пример был полностью воспроизводим, отдельно задают способ передачи хвоста, который уже целиком есть в словаре.
Метод и условия
Начальный словарь содержит пустую строку с индексом ноль. В текущем месте сообщения найдите самый длинный префикс, который уже записан. Если после него есть новый символ, выдайте пару из индекса префикса и этого символа, добавьте полученную фразу в словарь и продолжайте после неё. Индексы присваиваются в порядке добавления. Ранее добавленная фраза не получает новый индекс при каждом повторе.
Жадность относится к известному префиксу: нельзя остановиться на более коротком только потому, что так удобнее разделить строку. При этом итоговая новая фраза является первым ещё неизвестным продолжением. Сообщение может закончиться на фразе, которая уже есть в словаре. В нашей явной договорённости тогда выдаётся ссылка с пустым новым символом, а дополнительная словарная запись не создаётся. Другой формат мог бы использовать специальный символ конца, но смешивать две договорённости в одном примере нельзя.
Проверка и типичная ошибка
Для декодирования достаточно того же начального словаря и списка пар. Возьмите фразу по переданному индексу, допишите новый символ и добавьте полученный текст к выходу. Если новый символ непустой, та же фраза добавляется в словарь декодера. Пустой завершающий символ только воспроизводит уже известный хвост. В каждый момент ссылка должна указывать на существующую запись, поэтому будущее содержимое словаря не требуется.
Независимая проверка состоит в побуквенном сравнении восстановленного сообщения с исходным. Простое совпадение числа фраз недостаточно: неправильное разбиение может давать столько же пар. Также логические пары не являются готовым архивным форматом. Чтобы посчитать реальный размер, нужны правила кодирования индексов, ширина символов, упаковка битов и служебные данные. На коротком сообщении представление может оказаться длиннее исходного; алгоритм не обещает уменьшение любой строки. Учебный интерфейс поэтому показывает пары, словарь и восстановление, а не выдуманное число сэкономленных байтов.
Пример
Для ABAB первые две пары равны (0,A) и (0,B). Затем известный префикс A вместе с B образует новую фразу AB и пару (1,B).
Для AA после пары (0,A) остаётся известный хвост A, поэтому последняя пара равна (1,пусто). Декодер выдаёт ещё A, не создавая дубликат словарной записи.
От чтения к действию
А теперь — вы
Частые вопросы
Почему пустой символ в конце?
В этой явной договорённости остаток, уже имеющийся в словаре, передаётся ссылкой без добавления нового символа и новой записи.
Это число байтов после сжатия?
Нет. Пары и словарь показаны логически; размер зависит от способа кодирования индексов, алфавита и служебного формата.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Сообщение как вложенный интервал: что именно передают биты арифметического кода
Построить точный интервал арифметического кодирования короткого сообщения и найти целиком содержащийся в нём двоичный цилиндр.
Открыть темуisdigit не обещает int: разные вопросы о числовых символах
Различаем isdecimal, isdigit и isnumeric, проверяем надстрочную цифру, дробный знак и десятичные цифры другой письменности, отделяем классификацию символов от разбора строки.
Открыть темуЧастота отсчётов и разрядность звука: какие числа отвечают за разные свойства
Считаем несжатые звуковые данные PCM по частоте отсчётов, числу каналов и битам хранения: различаем временную сетку, уровни амплитуды и контейнер файла.
Открыть тему