PAQ — серія вільних архіваторів стиснення без втрат із текстовим інтерфейсом, які спільними зусиллями розробників піднялись на перші місця рейтингів багатьох тестів стиснення даних (хоч і ціною процесорного часу й об'єму пам'яті). Спеціально налаштовані версії алгоритму PAQ виграли Приз Хаттера[en] та Калгарі Челендж.[1] PAQ є вільним програмним забезпеченням і поширюється під ліцензією GNU General Public License.[2]
PAQ використовує алгоритм context mixing[en], який пов'язаний із алгоритмом стиснення PPM. При цьому, компресія поділяється на дві фази: моделювання та кодування. PAQ використовує алгоритм змішування контекстів, який, хоч і пов'язаний із PPM, відрізняється тим, що ймовірність виникнення наступного символу розраховується на основі великої кількості моделей, залежних від різних контекстів, але не обов'язково послідовних. У більшості версій PAQ для збору статистики передбачення ймовірності наступного символу використовують наступні моделі:
Всі версії PAQ передбачають і стискають за один раз один біт, але розрізняються в деталях застосування того, як передбачення комбінуються й обробляються після. Як тільки була визначена передбачена ймовірність появи наступного біту, біт стискається арифметичним кодером. Існує три способи для комбінування передбачень моделей у залежності від версії PAQ.
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 кожна модель відображала велику кількість різних контекстів на пару лічильників: n 0 {\displaystyle n_{0}} — кількість нульових бітів і n 1 {\displaystyle n_{1}} — кількість одиничних бітів. Для збільшення значимості пізнішої історії бітів лічильник зменшувався майже в два рази, коли протилежний біт зустрічався. Наприклад, поточний стан моделі, асоціювання з контекстом ( n 0 , n 1 ) = ( 12 , 3 ) {\displaystyle (n_{0},n_{1})=(12,3)} , біт 1 спостерігається на виході й лічильник оновлюється до стану (7,4).
Біт стискається арифметичним кодером відповідно його ймовірності або P(1), або P(0)=1-P(1). Ймовірності обчислюються зваженим підсумовуванням лічильників нулів та одиниць:
де w i {\displaystyle w_{i}} — вага і-ї моделі. До PAQ3 ваги були фіксованими й встановлювались у випадковому порядку (контексти порядку n мали вагу n²). Починаючи з PAQ4 ваги обиралися адаптивно в напрямку зменшення помилки передбачення в однакових наборах контекстів. Якщо треба закодувати біт y, то ваги призначаються наступним чином:
Починаючи з PAQ7 виходом кожної моделі є передбачення (замість пари лічильників). Передбачення усереднюються в логістичному домені:
Після кожного передбачення модель оновлюється вирівнюванням ваги для зменшення ціни стискання.
Більшість версій PAQ використовує невеликий конекст під час вибору ваг для нейронної мережі. Деякі версії використовують 2-3-крокові передбачення, які складаються з відповідно двох або трьох множин нейронних мереж. Вихід кожної попередньої є виходом для наступної множини мереж, потужність якого менше. Потім йде вторинна оцінка символу. Більш того, для кожного вхідного передбачення може бути декілька входів, які є нелінійними функціями Pi(1) у доповненні до стиснути(P(1)).
Кожна модель поділяє вхідний потік біт s на множину контекстів і зображує кожний контекст на стан історії бітів, зображене 8 бітами. У версіях до PAQ6 стан був представлений парою лічильників (n0, n1). У PAQ7 і пізніших версіях стан містив за певних умов також останній біт і цілу послідовність. Значення станів відображаються у ймовірності, використовуючи 256-значну таблицю. Після табличного передбачення в таблиці вирівнювались (зазвичай до 0,4 %) для зменшення похибки передбачення.
У всіх PAQ8-версіях стан історії бітів містить наступну інформацію:
Щоб зберегти кількість станів рівним 256, на лічильники були введені наступні обмеження: (41, 0), (40, 1), (12, 2), (5, 3), (4, 4), (3, 5), (2, 12), (1, 40), (0, 41). Якщо лічильник перевищує ліміт, наступний стан обирається подібним відношенням n0 / n1. Таким чином, якщо поточний стан (n0 = 4, n1 = 4, останній біт = 0) та 1 отримана на виході, тоді новий стан не (n0 = 4, n1 = 5, останній біт = 1), а (n0 = 3, n1 = 4, останній біт = 1).
Більшість контекстних моделей реалізовані як хеш-таблиці. Деякі невеликі контексти реалізовані як індексні масиви.
Деякі версії PAQ, особливо PAsQDAa, PAQAR (обидві пішли від PAQ6), і від PAQ8HP1 до PAQ8HP8 (нащадки PAQ8 і ті, що здобули верх у Призі Хаттера) обробляють текст, продивляючись його й заміняючи слова з тексту, які містяться в зовнішньому словнику 1- і 3-байтними кодами. Додатково слова у верхньому регістрі кодуються спеціальним символом і перекладом у нижній регістр. У серії PAQ8HP словник організований групуванням синтаксично та семантично схожих слів разом. Це дозволяє використовувати моделі, які використовують тільки верхні біти словникових кодів як контексти.
You may download, use, copy, modify, and distribute these programs under the terms of the GNU general public license
Lokasi Pengunjung: 3.14.145.83