PAQ

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 словник організований групуванням синтаксично та семантично схожих слів разом. Це дозволяє використовувати моделі, які використовують тільки верхні біти словникових кодів як контексти.