Алгоритм сжатия PalmDoc

Алгоритм сжатия PalmDoc — это метод сжатия данных без потерь, основанный на алгоритме LZ77, который использовался для уменьшения объёма текстовых файлов (в первую очередь книг и документов) в операционной системе Palm OS. Алгоритм был разработан компанией Palm, Inc. для устройств на базе Palm OS и стал стандартом де-факто для хранения электронных книг на платформе Palm. Отличается простотой реализации и высокой скоростью декомпрессии, что было критично для ограниченных вычислительных ресурсов КПК (карманных персональных компьютеров) конца 1990-х — начала 2000-х годов.

История

Алгоритм PalmDoc был создан в середине 1990-х годов как часть экосистемы Palm OS. Основной задачей было обеспечить возможность хранения больших объёмов текстовой информации (например, книг, справочников, документации) на устройствах с крайне ограниченной памятью — типичные КПК того времени имели от 2 до 8 МБ оперативной памяти. Использование сжатия позволяло увеличить эффективный объём хранимых текстов в 2–4 раза.

PalmDoc стал основным форматом для программ чтения электронных книг на Palm OS, таких как AportisDoc (позже — Palm Reader), TealDoc и других. Он также использовался для сжатия системных файлов и текстовых баз данных (Palm Database — PDB). С упадком платформы Palm OS в середине 2000-х годов алгоритм утратил массовое распространение, однако его реализация сохранилась в некоторых конвертерах и эмуляторах.

Принцип работы

Алгоритм PalmDoc является вариантом алгоритма LZ77, адаптированным для сжатия текста. Он использует скользящее окно и кодирование повторяющихся последовательностей символов.

Основные компоненты

• Скользящее окно: размер окна составляет 4096 байт (4 КБ). Это означает, что алгоритм ищет повторяющиеся фрагменты в пределах последних 4096 байт уже обработанных данных.
• Минимальная длина совпадения: совпадение должно быть длиной не менее 3 байт.
• Максимальная длина совпадения: до 256 байт.

Процесс сжатия

1. Алгоритм последовательно обрабатывает входные данные, начиная с первого байта.
2. Для каждого текущего положения (позиции) в данных алгоритм ищет в окне (предыдущие 4096 байт) самую длинную последовательность, совпадающую с текущей.
3. Если найдено совпадение длиной 3 байта или более, оно кодируется парой: смещение (расстояние от текущей позиции до начала совпадения в окне) и длина совпадения.
4. Если совпадение не найдено или его длина меньше 3 байт, текущий байт копируется в выходной поток как литерал (незакодированный байт).

Структура сжатых данных

Сжатые данные состоят из последовательности токенов. Каждый токен может быть либо литералом (один байт), либо ссылкой на совпадение (пара «смещение, длина»). Для различения типов токенов используется битовый флаг:

• Битовый флаг: перед каждым токеном в выходном потоке идёт один бит, указывающий его тип:
• 0 — следующий токен является литералом (1 байт).
• 1 — следующий токен является ссылкой на совпадение (2 байта: 12 бит на смещение + 4 бита на длину).

Таким образом, ссылка на совпадение всегда занимает 2 байта (16 бит), а литерал — 1 байт плюс 1 бит флага. Эффективность сжатия достигается за счёт того, что ссылки заменяют длинные повторяющиеся последовательности (от 3 до 256 байт) всего двумя байтами.

Процесс декомпрессии

Декомпрессия выполняется быстро и просто:

1. Алгоритм последовательно читает битовые флаги.
2. Если флаг 0 — читается следующий байт как литерал и записывается в выходной поток.
3. Если флаг 1 — читаются 2 байта, из которых извлекаются смещение (12 бит) и длина (4 бита). Затем из уже декомпрессированных данных (в пределах окна) копируется последовательность указанной длины, начиная с позиции, отстоящей на смещение назад.
4. Процесс повторяется до конца сжатых данных.

Формат файла PalmDoc

Данные, сжатые алгоритмом PalmDoc, обычно хранятся в файлах формата Palm Database (PDB). Структура такого файла включает:

• Заголовок PDB (78 байт): содержит имя базы, атрибуты, даты создания и модификации, версию, количество записей и другие метаданные.
• Записи (Records): каждая запись представляет собой сжатый блок данных. Записи могут быть разного размера, но обычно имеют фиксированный размер (например, 4096 байт несжатых данных). Каждая запись сжимается независимо, что позволяет осуществлять произвольный доступ к отдельным частям документа без необходимости декомпрессии всего файла.

Сжатые записи содержат заголовок, указывающий на тип сжатия (PalmDoc), и собственно сжатые данные.

Характеристики

• Тип сжатия: без потерь.
• Алгоритмическая основа: LZ77.
• Размер скользящего окна: 4096 байт.
• Минимальная длина совпадения: 3 байта.
• Максимальная длина совпадения: 256 байт.
• Степень сжатия: для типичных текстов на английском языке — от 40% до 60% от исходного размера (то есть сжатие в 1,5–2,5 раза). Для русского текста степень сжатия может быть несколько ниже из-за большей средней длины слов и особенностей кодировки (CP1251 или UTF-8).
• Скорость декомпрессии: очень высокая (порядка 10–20 МБ/с на процессорах того времени), что делало алгоритм пригодным для устройств с частотой процессора 16–33 МГц.
• Скорость сжатия: относительно низкая (из-за необходимости поиска совпадений в окне), но это не критично для однократного сжатия при конвертации книг.

Применение

• Электронные книги на Palm OS: основной формат для хранения книг в программах AportisDoc, Palm Reader, TealDoc.
• Системные базы данных: некоторые системные файлы Palm OS (например, базы данных адресной книги, календаря) также могли использовать сжатие PalmDoc.
• Конвертеры: для преобразования текстовых файлов (TXT, HTML) в формат PDB с сжатием PalmDoc использовались утилиты, такие как MakeDoc, DocConverter и онлайн-сервисы.
• Эмуляторы: современные эмуляторы Palm OS (например, POSE, Cloudpilot) поддерживают чтение файлов PDB со сжатием PalmDoc.

Критика и ограничения

• Устаревание: с появлением более мощных алгоритмов сжатия (например, deflate, bzip2) PalmDoc уступает им в степени сжатия. Современные форматы электронных книг (EPUB, FB2) используют более эффективные методы (ZIP, deflate).
• Ограниченный размер окна: 4 КБ недостаточно для эффективного сжатия больших объёмов текста; более длинные повторяющиеся структуры (например, главы книги) не могут быть закодированы.
• Неэффективность для нетекстовых данных: алгоритм плохо сжимает двоичные файлы (изображения, исполняемые коды), так как они содержат мало повторяющихся последовательностей.
• Зависимость от кодировки: для русского языка в кодировке Windows-1251 степень сжатия может быть ниже, чем для английского, из-за особенностей частотности символов.

Интересные факты

• PalmDoc был одним из первых алгоритмов сжатия, специально разработанных для мобильных устройств с ограниченными ресурсами.
• Алгоритм не запатентован и является общественным достоянием (public domain), что способствовало его широкому распространению.
• В современных операционных системах (Windows, Linux, macOS) существуют утилиты и библиотеки (например, palm-db-tools), позволяющие сжимать и распаковывать файлы PalmDoc.
• Некоторые модели КПК Palm (например, Palm V, Palm III) могли хранить до 10–15 книг среднего объёма (300–400 страниц) в сжатом формате PalmDoc.

Источники

• Palm OS Programmer’s Companion (1998), Palm Computing, Inc.
• Документация к утилите MakeDoc (версия 1.2, 1999).
• Спецификация формата Palm Database (PDB) — Palm OS SDK, 2001.
• Статья «PalmDoc Compression Algorithm» на сайте The Palm OS Developer’s Guide (архивная версия).
• Анализ алгоритмов сжатия данных для мобильных устройств (журнал «Программирование», 2003).