PAQ

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Зразок сесії PAQ8O

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

Алгоритм[ред.ред. код]

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

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

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

  • від PAQ1 до PAQ3 кожне передбачення представлено парою бітових лічильників . Ці лічильники комбінувались зваженим підсумовуванням, таким, що більша вага визначається довшим контекстом
  • у PAQ4 до PAQ6 передбачення комбінувались, як і в попередньому випадку, але вага, яка належить кожній моделі, призначалась так, щоб більш точні моделі отримували перевагу
  • у PAQ7 і пізніших версіях вихід кожної моделі є ймовірністю , на відміну від пари лічильників, ймовірності сумуються за допомогою штучних нейронних мереж.

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 кожна модель відображала велику кількість різних контекстів на пару лічильників:  — кількість нульових бітів і  — кількість одиничних бітів. Для збільшення значимості пізнішої історії бітів лічильник зменшувався майже в два рази, коли протилежний біт зустрічався. Наприклад, поточний стан моделі, асоціювання з контекстом , біт 1 спостерігається на виході й лічильник оновлюється до стану (7,4).

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

  • ,

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

  • ni = n0i + n1i
  • помилка = y − P(1)
  • помилка

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

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

  • xi = стиснути(Pi(1))
  • P(1) = розмити(Σi wi xi),
    де P(1) — ймовірність того, що наступний біт буде одиницею, а Pi(1) — ймовірність, оцінена і-ю моделлю й
  • стиснути(x) = ln(x / (1 - x))
  • розмити(x) = 1 / (1 + e-x) (операція, зворотня операції «стиснути»).

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

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

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

Контекстне моделювання[ред.ред. код]

Кожна модель поділяє вхідних потік біт s на множину контекстів і зображує кожний контекст на стан історії бітів, зображене 8 бітами. У версіях до PAQ6 стан був представлений парою лічильників (n0, n1). У 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). Якщо лічильник перевищує ліміт, наступний стан обирається подібним відношенням 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 словник організований групуванням синтаксично та семантично схожих слів разом. Це дозволяє використовувати моделі, які використовують тільки верхні біти словникових кодів як контексти.

Примітки[ред.ред. код]

  1. The Compression/SHA-1 Challenge. Mailcom.com. Процитовано 2010-05-19. 
  2. Homepage of the PAQ compressors. Процитовано 2007-07-10. «You may download, use, copy, modify, and distribute these programs under the terms of the GNU general public license»