LZ78: словарь фраз и проверка восстановления
Разобрать короткую буквенную строку в пары «индекс префикса, новый символ», показать словарь и восстановить исходное сообщение.
Ваш пример
Разбор примера
Восстановлено точно; пар: 6
| Шаг | Индекс префикса | Новый символ |
|---|---|---|
| 1 | 0 | A |
| 2 | 0 | B |
| 3 | 1 | A |
| 4 | 2 | A |
| 5 | 4 | A |
| 6 | 2 | (конец) |
- Индекс 0 обозначает пустой префикс.
- Новая непустая фраза добавляется после выдачи соответствующей пары.
- Логические пары не объявляются готовым архивным форматом или доказанной экономией байтов.
Метод и условия расчёта
Словарь начинается с пустой строки с индексом 0.
Берём длиннейший известный префикс и следующий символ; завершающий известный хвост передаётся парой (индекс, пусто).
Теория к методу
LZ78 создаёт словарь фраз во время чтения сообщения. Каждая новая фраза передаётся индексом уже известного префикса и следующим символом. Чтобы короткий пример был полностью воспроизводим, отдельно задают способ передачи хвоста, который уже целиком есть в словаре.
Начальный словарь содержит пустую строку с индексом ноль. В текущем месте сообщения найдите самый длинный префикс, который уже записан. Если после него есть новый символ, выдайте пару из индекса префикса и этого символа, добавьте полученную фразу в словарь и продолжайте после неё. Индексы присваиваются в порядке добавления. Ранее добавленная фраза не получает новый индекс при каждом повторе.
Пример: Для ABAB первые две пары равны (0,A) и (0,B). Затем известный префикс A вместе с B образует новую фразу AB и пару (1,B).
Для AA после пары (0,A) остаётся известный хвост A, поэтому последняя пара равна (1,пусто). Декодер выдаёт ещё A, не создавая дубликат словарной записи.
Вопросы по теме
Почему пустой символ в конце?
В этой явной договорённости остаток, уже имеющийся в словаре, передаётся ссылкой без добавления нового символа и новой записи.
Это число байтов после сжатия?
Нет. Пары и словарь показаны логически; размер зависит от способа кодирования индексов, алфавита и служебного формата.
Кодирование чисел, текста, изображения и звука: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.