PAQ

Зразок сесії PAQ8O

PAQ — серія вільних архіваторів стиснення без втрат із текстовим інтерфейсом, які спільними зусиллями розробників піднялись на перші місця рейтингів багатьох тестів стиснення даних (хоч і ціною процесорного часу й об'єму пам'яті). Спеціально налаштовані версії алгоритму PAQ виграли Приз Хаттера^[en] та Калгарі Челендж.[1] PAQ є вільним програмним забезпеченням і поширюється під ліцензією GNU General Public License.[2]

Алгоритм

PAQ використовує алгоритм context mixing^[en], який пов'язаний із алгоритмом стиснення PPM. При цьому, компресія поділяється на дві фази: моделювання та кодування. PAQ використовує алгоритм змішування контекстів, який, хоч і пов'язаний із PPM, відрізняється тим, що ймовірність виникнення наступного символу розраховується на основі великої кількості моделей, залежних від різних контекстів, але не обов'язково послідовних. У більшості версій PAQ для збору статистики передбачення ймовірності наступного символу використовують наступні моделі:

• n-грами — контекст, останні n байт перед передбаченим символом (як у PPM);
• словникові n-грами, які ігнорують регістр і несловникові символи (корисні в текстових даних);
• «рідкісні» контексти, наприклад, другий та четвертий символи перед кодованим (корисні у деяких бінарних форматах);
• «аналогові» контексти, які складаються з бітів вищого порядку попередніх 8- або 16-бітних слів (корисні в мультимедійних файлах);
• двовимірні контексти (корисні для зображень, таблиць). Довжина рядку визначається знаходженням повторів груп байтів;
• спеціалізовані моделі, такі, як x86-виконавчі файли, BMP, TIFF або JPEG-зображення. Ці моделі активуються, коли даний тип файлу визначається.

Всі версії PAQ передбачають і стискають за один раз один біт, але розрізняються в деталях застосування того, як передбачення комбінуються й обробляються після. Як тільки була визначена передбачена ймовірність появи наступного біту, біт стискається арифметичним кодером. Існує три способи для комбінування передбачень моделей у залежності від версії PAQ.

• від PAQ1 до PAQ3 кожне передбачення представлено парою бітових лічильників ${\displaystyle (n_{0},n_{1})}$. Ці лічильники комбінувались зваженим підсумовуванням, таким, що більша вага визначається довшим контекстом
• у PAQ4 до PAQ6 передбачення комбінувались, як і в попередньому випадку, але вага, яка належить кожній моделі, призначалась так, щоб більш точні моделі отримували перевагу
• у PAQ7 і пізніших версіях вихід кожної моделі є ймовірністю ${\displaystyle [0;4095]}$, на відміну від пари лічильників, ймовірності сумуються за допомогою штучних нейронних мереж.

PAQ1SSE і пізніші версії використовували пост-обробку передбачення шляхом вторинної оцінки символу (SSE). Комбіноване передбачення та невеликий контекст використовувались для обирання наступного передбачення згідно таблиці. Після того, як символ був закодований, дані в таблиці коректувались для зменшення помилки передбачення. Вторинна оцінка символу може бути об'єднана в один процес із різними контекстами, або може виконуватися паралельно, усереднюючись із виходами моделей.

Арифметичне кодування

Рядок s стискається в байтовий рядок, уявляючи число x у 256-значній системі вимірювання big endian на інтервалі [0;1], як P(r < s) ≤ x < P(r ≤ s), де P(r < s) — ймовірність, що випадковий рядок r такої ж самої довжини, як s, лексикографічно менш, ніж s. Завжди можна знайти такий рядок x, що його довжина хоча б на один байт була більша за ліміт Шеннона: -log2 P(r = s) біт. Довжина s зберігається на початку архіву.

Арифметичний кодер у PAQ здійснений шляхом збереження верхньої та нижньої мережі x для кожного кроку передбачення, спочатку [0;1]. Після кожного передбачення поточній інтервал ділився пропорційно ймовірності того, що наступний біт буде 0, потів 1, на підставі попередніх бітів s. Наступний біт кодується, обираючи відповідний інтервал нижньої градації у вигляді нового інтервалу.

Число x декомпресується в рядок s із ідентичною серією бітових передбачень (оскільки попередні біти s відомі). Інтервал ділиться як при стисканні. Частина, яка містить x, стає новим інтервалом і відповідний біт додається до s.

У PAQ верхня та нижня межа інтервалу інтерпретуються трьома частинами. Найбільш важливі розряди по основі 256 однакові, таким чином вони можуть бути записані як старші байти x. Наступні 4 байта зберігаються в пам'яті так, що старший байт відрізняється. Молодші біти передбачається, що є нулями для нижньої межі та всі для верхньої межі. Кодування завершується записом ще одного байта з нижньої межі.

Адаптивне зважування моделей

У PAQ версіях до PAQ6 кожна модель відображала велику кількість різних контекстів на пару лічильників: ${\displaystyle n_{0}}$ — кількість нульових бітів і ${\displaystyle n_{1}}$ — кількість одиничних бітів. Для збільшення значимості пізнішої історії бітів лічильник зменшувався майже в два рази, коли протилежний біт зустрічався. Наприклад, поточний стан моделі, асоціювання з контекстом ${\displaystyle (n_{0},n_{1})=(12,3)}$, біт 1 спостерігається на виході й лічильник оновлюється до стану (7,4).

Біт стискається арифметичним кодером відповідно його ймовірності або P(1), або P(0)=1-P(1). Ймовірності обчислюються зваженим підсумовуванням лічильників нулів та одиниць:

• ${\displaystyle S_{0}=\Sigma _{1}w_{i}n_{0i}}$
• ${\displaystyle S_{1}=\Sigma _{1}w_{i}n_{1i}}$
• ${\displaystyle S=S_{0}+S_{1}}$
• ${\displaystyle P(0)={\frac {S_{0}}{S}}}$
• ${\displaystyle P(1)={\frac {S_{1}}{S}}}$,

де ${\displaystyle w_{i}}$ — вага і-ї моделі. До PAQ3 ваги були фіксованими й встановлювались у випадковому порядку (контексти порядку n мали вагу n²). Починаючи з PAQ4 ваги обиралися адаптивно в напрямку зменшення помилки передбачення в однакових наборах контекстів. Якщо треба закодувати біт y, то ваги призначаються наступним чином:

• n_i = n_0i + n_1i
• помилка = y − P(1)
• ${\displaystyle w_{i}\gets w_{i}+{\frac {S\,n_{1i}-S_{1}n_{i}}{S_{0}S_{1}}}}$ помилка

Нейронні мережі для змішування

Починаючи з PAQ7 виходом кожної моделі є передбачення (замість пари лічильників). Передбачення усереднюються в логістичному домені:

• x_i = стиснути(P_i(1))
• P(1) = розмити(Σ_i w_i x_i),
  де P(1) — ймовірність того, що наступний біт буде одиницею, а P_i(1) — ймовірність, оцінена і-ю моделлю й

• стиснути(x) = ln(x / (1 - x))
• розмити(x) = 1 / (1 + e^-x) (операція, зворотня операції «стиснути»).

Після кожного передбачення модель оновлюється вирівнюванням ваги для зменшення ціни стискання.

• w_i ← η x_i (y — P(1)),
  де η — коефіцієнт навчання (зазвичай від 0.002 до 0.01), y — передбачений біт і (y-P(1)) — помилка передбачення. Алгоритм оновлення ваги відрізняється від звичайного у нейронних мережах навчаючого методу зворотнього поширення помилки в тому, що добуток P(0)P(1) не враховується, тому що мета нейронної мережі — мінімізація вартості кодування, а не стандартне відхилення.

Більшість версій PAQ використовує невеликий конекст під час вибору ваг для нейронної мережі. Деякі версії використовують 2-3-крокові передбачення, які складаються з відповідно двох або трьох множин нейронних мереж. Вихід кожної попередньої є виходом для наступної множини мереж, потужність якого менше. Потім йде вторинна оцінка символу. Більш того, для кожного вхідного передбачення може бути декілька входів, які є нелінійними функціями P_i(1) у доповненні до стиснути(P(1)).

Контекстне моделювання

Кожна модель поділяє вхідний потік біт s на множину контекстів і зображує кожний контекст на стан історії бітів, зображене 8 бітами. У версіях до PAQ6 стан був представлений парою лічильників (n₀, n₁). У PAQ7 і пізніших версіях стан містив за певних умов також останній біт і цілу послідовність. Значення станів відображаються у ймовірності, використовуючи 256-значну таблицю. Після табличного передбачення в таблиці вирівнювались (зазвичай до 0,4 %) для зменшення похибки передбачення.

У всіх PAQ8-версіях стан історії бітів містить наступну інформацію:

• Точна послідовність до 4 бітів.
• Пара лічильників і індикаторів для останнього біту для послідовностей від 5 до 15 біт.
• Пара лічильників для послідовностей від 16 до 41 біту.

Щоб зберегти кількість станів рівним 256, на лічильники були введені наступні обмеження: (41, 0), (40, 1), (12, 2), (5, 3), (4, 4), (3, 5), (2, 12), (1, 40), (0, 41). Якщо лічильник перевищує ліміт, наступний стан обирається подібним відношенням n₀ / n₁. Таким чином, якщо поточний стан (n₀ = 4, n₁ = 4, останній біт = 0) та 1 отримана на виході, тоді новий стан не (n₀ = 4, n₁ = 5, останній біт = 1), а (n₀ = 3, n₁ = 4, останній біт = 1).

Більшість контекстних моделей реалізовані як хеш-таблиці. Деякі невеликі контексти реалізовані як індексні масиви.

Попередня обробка тексту

Деякі версії PAQ, особливо PAsQDAa, PAQAR (обидві пішли від PAQ6), і від PAQ8HP1 до PAQ8HP8 (нащадки PAQ8 і ті, що здобули верх у Призі Хаттера) обробляють текст, продивляючись його й заміняючи слова з тексту, які містяться в зовнішньому словнику 1- і 3-байтними кодами. Додатково слова у верхньому регістрі кодуються спеціальним символом і перекладом у нижній регістр. У серії PAQ8HP словник організований групуванням синтаксично та семантично схожих слів разом. Це дозволяє використовувати моделі, які використовують тільки верхні біти словникових кодів як контексти.

Примітки

1. The Compression/SHA-1 Challenge. Mailcom.com. Архів оригіналу за 25 квітня 2015. Процитовано 19 травня 2010.
2. Homepage of the PAQ compressors. Архів оригіналу за 21 грудня 2016. Процитовано 10 липня 2007. You may download, use, copy, modify, and distribute these programs under the terms of the GNU general public license