PAQ

PAQ  je řada bezplatných textových archivátorů , které se společným úsilím vývojářů dostaly na první místa v hodnocení mnoha testů komprese dat (i když za cenu procesorového času a paměti). Nejlepšího výsledku v této sérii ve většině testů dosáhl archivátor PAQ8JD, vytvořený společným úsilím Matta Mahoneyho (Matt Mahoney), Alexandra Ratushnyaka, Sergeje Osnacha, Przemysława Skibińského a Billa Pettise a vydaný 30. prosince 2006 . V některých testech však zaostává za WinRK (vytvořeným Malcolmem Taylorem v lednu 2005 ) v režimu PWCM. PWCM(Angličtina  PAQ vážené kontextové míchání , „PAQ vážené kontextové míchání“) je vlastní implementace algoritmu PAQ od třetí strany . Speciálně vyladěné verze algoritmu PAQ vyhrály ceny v Hutterově ceně a Calgary Corpus Challenge .

Algoritmus

Algoritmus je založen na myšlence kontextového modelování . Kontextem je, řečeno přístupným jazykem, historie vzhledu postavy, tedy informace o postavách, které předcházejí tu aktuální ve stlačitelném proudu. V tomto případě je proces komprese rozdělen do dvou fází: modelování a kódování . PAQ používá algoritmus pro míchání kontextu . Kontextové míchání ( Context mixing ) je technika blízce příbuzná s algoritmem PPM , ale rozdíl je v tom, že pravděpodobnost dalšího znaku se vypočítává na základě vážené kombinace velkého počtu modelů v závislosti na různých kontextech, ne nutně po sobě jdoucí V rodině PAQ se následující modely používají hlavně ke sběru statistik a předpovídání pravděpodobnosti dalšího symbolu:

• n-gramy - kontext; předchozích n bytů (jako v PPM).
• slovníkové n-gramy, které ignorují velká a malá písmena a neabecední znaky (užitečné v textových datech).
• "řídké" kontexty, jako je druhý a čtvrtý znak před zakódovaným (užitečné v některých binárních formátech ).
• "analogové" kontexty sestávající z horní poloviny binární reprezentace 8 nebo 16 bitových slov (užitečné v multimediálních datových formátech).
• 2D kontexty (užitečné pro obrázky, tabulková data). Délka řádku je určena nalezením opakujících se vzorů bajtů.
• specializované modely, jako jsou binární soubory x86 nebo Windows Bitmap , TIFF , obrázky JPEG . Tyto modely se aktivují, když je definován daný typ souboru.

Všechny verze PAQ předpovídají a komprimují jeden bit po druhém , ale liší se v detailech implementace, jak jsou předpovědi kombinovány a následně zpracovávány. Jakmile byla prediktivně určena pravděpodobnost výskytu dalšího bitu, bit je komprimován aritmetickým kodérem . Existují tři způsoby, jak kombinovat předpovědi modelu v závislosti na verzi PAQ.

• od PAQ1 do PAQ3 je každá predikce reprezentována dvojicí bitových čítačů . Tyto čítače byly kombinovány váženým součtem, takže větší váha je určena delším kontextem.
• v PAQ4 až PAQ6 byly předpovědi kombinovány jako v prvním případě, ale váhy patřící každému modelu byly přiřazeny tak, aby měly přednost přesnější modely.
• v PAQ7 a novějších je výstupem každého modelu pravděpodobnost , na rozdíl od dvojice čítačů se pravděpodobnosti sčítají pomocí umělých neuronových sítí .

PAQ1SSE a novější verze používaly predikci sekundárního odhadu symbolu ( SSE  ) post-processing , tj. kombinovaná predikce a malý kontext byly použity k výběru další predikce z tabulky. Po zakódování symbolu byla data v tabulce upravena, aby se snížila chyba predikce. Odhad sekundárních znaků může být kombinován do jednoho procesu s různými kontexty nebo může být prováděn paralelně, průměrování s výstupy modelů.

Aritmetické kódování

Řetězec s je zkomprimován do bajtového řetězce představujícího x v 256 big endianu v intervalu [0;1) tak, že P(r < s) ≤ x < P(r ≤ s), kde P(r < s) je pravděpodobnost, že náhodný řetězec r stejné délky jako s je lexikograficky menší než s . Vždy je možné najít řetězec x takový, že jeho délka přesahuje Shannonův limit alespoň o jeden byte : -log 2 P(r = s) bitů. Délka s je uložena v hlavičce archivu.

Aritmetický kodér v PAQ je implementován uložením horní a dolní meze x pro každý krok predikce, zpočátku [0;1]. Po každé predikci se aktuální interval rozdělí proporcionálně k pravděpodobnosti, že další bit bude 0 a další bit bude 1, na základě předchozích bitů s . Další bit je zakódován výběrem odpovídajícího dílčího slotu jako nového slotu.

Číslo x je dekomprimováno do řetězce s s identickou řadou bitových předpovědí (protože předchozí bity s jsou známé). Interval je rozdělen jako při kompresi. Část obsahující x se stane novým intervalem a odpovídající bit se přidá k s .

V PAQ jsou horní a dolní hranice intervalu reprezentovány třemi částmi. Nejvýznamnější bity v základu 256 jsou identické, takže je lze zapsat jako vysoké bajty x . Další 4 bajty jsou uloženy v paměti, takže horní bajt je jiný. Předpokládá se, že všechny nejméně významné bity jsou nuly pro dolní mez a všechny jedničky pro horní mez. Kódování je dokončeno zápisem jednoho dalšího bajtu ze spodní hranice.

Adaptivní vážení modelů

Ve verzích PAQ před PAQ6 každý model mapoval mnoho různých kontextů na dvojici čítačů:  - počet nulových bitů a  - počet jedniných bitů. Pro zvýšení významu pozdější historie bitů bylo počítadlo sníženo na polovinu, když došlo k opačnému bitu. Na vstupu je například sledován aktuální stav modelu spojeného s kontextem a bitem 1 - čítač je aktualizován do stavu (7,4).

Bit je komprimován aritmetickým kodérem podle své pravděpodobnosti buď P(1) nebo P(0)=1-P(1). Pravděpodobnosti se počítají váženým součtem čítačů nul a jedniček:

• 
• 
• 
• 
• ,

kde je hmotnost i-tého modelu. Před PAQ3 byly váhy fixovány a randomizovány (kontexty řádu n měly váhu n²). Počínaje PAQ4 byly váhy voleny adaptivně ve směru snižování chyby predikce ve stejných souborech kontextů. Pokud je potřeba zakódovat bit y , pak se váhy přiřadí následovně:

• n i = n 0i + n 1i
• chyba = y − P(1)
• chyba

Neuronové sítě pro míchání

Počínaje PAQ7 je výstupem každého modelu předpověď (místo dvojice čítačů). Předpovědi jsou zprůměrovány přes logistickou doménu pomocí vzorce:

• x i = zmenšit (P i (1))
• P(1) = rozostření (Σ i w i x i ),

kde P(1) je pravděpodobnost, že další bit bude jedna, a P i (1) je pravděpodobnost odhadnutá i -tým modelem a

• zmenšit(x) = ln(x / (1 - x))
• blur(x) = 1 / (1 + e -x ) (opačná operace "stlačení").

Po každé predikci je model aktualizován úpravou vah, aby se snížily náklady na kompresi.

• w i ← η x i (y - P(1)),

kde η je faktor učení (typicky 0,002 až 0,01), y  je predikovaný bit a (y - P(1)) je chyba predikce. Algoritmus aktualizace váhy se liší od trénovací metody backpropagation běžné v neuronových sítích v tom, že se nebere v úvahu součin P(0)P(1), protože cílem neuronové sítě je minimalizovat náklady na kódování, nikoli průměr. čtvercová chyba .

Většina verzí PAQ používá malý kontext při výběru sady vah pro neuronovou síť. Některé verze používají dvou- a tříkrokové prediktory, skládající se ze dvou nebo tří sad neuronových sítí, přičemž výstup každé předchozí je vstupem pro další sadu sítí, jejíž síla je menší, a pak sekundární následuje odhad symbolu . Navíc pro každou vstupní predikci může existovat více vstupů, které jsou nelineárními funkcemi P i (1) navíc ke komprimaci (P(1)) .

Kontextové modelování

Každý model rozděluje příchozí bitové proudy do sady kontextů a mapuje každý kontext na stav bitové historie reprezentovaný 8 bity. Ve verzích před PAQ6 byl stav reprezentován dvojicí čítačů (n 0 , n 1 ) . V PAQ7 a novějších obsahoval stav za určitých podmínek také poslední bit nebo celou sekvenci. Hodnoty stavu jsou zobrazeny v pravděpodobností pomocí tabulky o 256 znacích. Po tabulkové predikci byla hodnota v tabulce mírně zploštělá (obvykle do 0,4 %), aby se snížila chyba predikce .

Ve všech verzích PAQ8 obsahují stavy bitové historie následující informace:

• Přesná sekvence do 4 bitů.
• Dvojice čítačů a indikátor pro poslední bit pro sekvence od 5 do 15 bitů.
• Dvojice čítačů pro sekvence od 16 do 41 bitů.

Aby počet stavů zůstal na 256, byla na pulty zavedena následující omezení: (41, 0), (40, 1), (12, 2), (5, 3), (4, 4), (3 , 5), (2, 12), (1, 40), (0, 41). Pokud čítač překročí limit, zvolí se další stav s podobným poměrem n 0 / n 1 . Pokud je tedy aktuální stav (n 0 = 4, n 1 = 4, poslední bit = 0) a jako vstup je přijata 1, pak nový stav není (n 0 = 4, n 1 = 5, poslední bit = 1), ale (n 0 = 3, n 1 = 4, poslední bit = 1).

Většina kontextových modelů je implementována jako hashovací tabulky . Některé malé kontexty jsou implementovány jako indexovaná pole .

Předzpracování textu

Některé verze PAQ, zejména PAsQDAa, PAQAR (obě pocházejí z PAQ6) a PAQ8HP1 až PAQ8HP8 (potomci PAQ8 a vítězové Hutterovy ceny [1] ), zpracovávají text tak, že se na něj podívají a nahrazují slova z textu obsaženého v externím slovník, jedno- a tříbajtové kódy. Slova psaná velkými písmeny jsou navíc kódována speciálním znakem a překladem slova na malá písmena. V řadě PAQ8HP je slovní zásoba organizována seskupením syntakticky a sémanticky podobných slov. To umožňuje modely, které jako kontexty používají pouze horní bity kódů slovníku.

Historie

Následuje seznam nejvýznamnějších změn v algoritmu PAQ. Kromě toho jsou vynechána menší vícenásobná vylepšení.

• PAQ1 byl vydán 6. ledna 2002 Mattem Mahoneym. Používal pevné váhy a nezahrnoval řídké a analogové modely. Celkem bylo použito 5 modelů [1] .
• PAQ1SSE/PAQ2 byl vydán 11. května 2003 Sergejem Osnachem. Výrazně zlepšil kompresi přidáním odhadu sekundárního symbolu mezi prediktor a kodér. Sekundární vyhodnocení symbolu vložilo do malého kontextu a aktuální predikce a výstupem byla nová predikce z tabulky. Hodnota tabulky byla poté aktualizována, aby odrážela aktuální bit.
• PAQ3N byl vydán 9. října 2003 . Byl přidán řídký model.
• PAQ4 , vydaný 15. listopadu 2003 Mattem Mahoneym, použil adaptivní vážení. PAQ5 ( 18. prosince 2003) a PAQ6 ( 30. prosince 2003) byla drobná vylepšení včetně analogového modelu. V této době PAQ soutěžil s nejlepšími PPM kompresory a přitahoval pozornost komunity pro kompresi dat, což vedlo k četným vylepšením do dubna 2004 . Berto Destasio doladil modely a opravil sekvenci procházení čítače. Johan de Bock provedl vylepšení uživatelského rozhraní . David A. Scott vylepšil aritmetický kodér. Fabio Buffoni zrychlil program.
• Mezi 20. květnem 2004 a 27. červencem 2004 Alexander Ratushnyak vydal sedm verzí archivátoru PAQAR , ve kterých byl kompresní poměr výrazně zvýšen přidáním mnoha nových modelů, mnoha mixérů s výběrem hmotnosti podle kontextu, přidáním hodnocení sekundárních znaků do výstup každého směšovače a nakonec přidáním předběžného zpracování spustitelných souborů architektury procesoru Intel . PAQAR zůstal na vrcholu bezztrátových programů pro kompresi dat až do konce roku 2004, ale byl mnohem pomalejší než jeho předchůdci.
• Od 18. ledna do 7. února 2005 Przemysław Skibinski vydal čtyři verze PAsQDa založené na PAQ6 a PAQAR a doplněné o anglický slovníkový preprocesor. Dosáhl nejlepšího skóre na Calgary Corpus, ale ne na většině ostatních testů.
• Upravená verze PAQ6 Matta Mahoneyho převzala cenu na Calgary Corps Challenge 10. ledna 2004 . Tento úspěch byl pokryt deseti po sobě jdoucími verzemi PAQAR od Alexandra Ratushnyaka. Nejnovější byla vydána 5. června 2006 , sestávala z dat a programového textu komprimovaných dohromady a zabírala 589 862 bajtů.
• PAQ7 byl propuštěn v prosinci 2005 Matt Mahoney. PAQ7  je kompletní přepis PAQ6 a jeho variant ( PAQAR , PAsQDa ). Kompresní poměr byl podobný PAQAR , ale doba provedení byla 3krát kratší. Ale postrádal x86 a slovník, takže nebyl tak dobrý v komprimaci spustitelných souborů Microsoft Windows a anglických textů jako PAsQDa . Přestože obsahoval modely pro barevné soubory BMP , TIFF a JPEG , komprimoval je lépe. Hlavním rozdílem oproti PAQ7 bylo to, že ke kombinování modelů používal neuronovou síť, na rozdíl od mixeru snižujícího gradient. Další funkcí PAQ7 byla schopnost komprimovat bitmapové a JPEG obrázky vložené do souborů Excel , Word a PDF .
• PAQ8A byl vydán 27. ledna 2006 a PAQ8C 13. února . Toto byl experimentální náhled očekávaného PAQ8. Opravil některé kompromisy v PAQ7, zejména slabou kompresi v některých případech. PAQ8A také obsahoval modely pro x86 spustitelné soubory.
• PAQ8F byl vydán 28. února 2006 . PAQ8F obsahoval tři vylepšení oproti PAQ8A: lepší využití paměti v kontextovém modelu, nový nepřímý kontextový model a nové uživatelské rozhraní pro podporu drag-n-drop ve Windows. Neobsahoval anglický slovník jako varianty PAQ8B/C/D/E.
• PAQ8G byl vydán 3. března 2006 Przemysławem Skibinskim. PAQ8G je PAQ8F, ale se slovníky a revidovaným modelem preprocesoru textových dat, který nezlepšil kompresi netextových souborů.
• PAQ8H se objevil 22. března 2006 díky Alexandru Ratushnyakovi a byl aktualizován 24. března 2006 . PAQ8H byl u některých modelů vylepšením PAQ8G.
• Pavel L. Goloborodko vydal PAQ8I 18. srpna 2006 s opravami chyb 24. srpna, 4. září a 13. září . Obsahoval přidání polotónového černobílého obrazového modelu pro soubory PGM .
• Bill Pettis vydal PAQ8J 13. listopadu 2006 . Program byl založen na PAQ8F s některými vylepšeními textového modelu převzatými z PAQ8HP5. Ačkoli to nezahrnovalo slovníky z PAQ8G nebo PGM z PAQ8I .
• Serge Osnach vydal řadu vylepšení modelu: PAQ8JA 16.  listopadu 2006 , PAQ8JB 21.  listopadu a PAQ8JC 28.  listopadu .
• PAQ8JD byl propuštěn 30. prosince 2006 díky úsilí Billa Pettise. Program byl portován na Win32 a 32bitové a 64bitové platformy Linux .
• Bill Pettis vyrobil PAQ8K 13. února 2007 . Byly do něj přidány další modely pro binární soubory.
• PAQ8L se objevil 13. března 2007 . Model pro Dynamic Markov Compression byl přidán do stávající sady modelů od Matta Mahoneyho.
• PAQ8O byl vydán 24. srpna 2007 Andreasem Morphisem. Obsahuje vylepšené modely bmp a jpg ve srovnání s PAQ8L. Volitelně může být zkompilován s podporou SSE2 také pro 64bitový Linux. Na 64bitovém jádře poskytuje algoritmus znatelné zvýšení výkonu.
• PAQ8P byl vydán 25. srpna 2008 Andreasem Morphisem. Obsahuje vylepšený model bmp a přidává model wav.
• PAQ8PX se objevil 25. dubna 2009 díky Janu Ondrusovi. Obsahuje různá vylepšení jako lepší kompresi souborů WAV a EXE.
• PAQ9A byl vydán 31. prosince 2007 Mattem Mahoneym. Nová experimentální verze. Nezahrnuje modely pro konkrétní typy souborů a má preprocesor LZP.

Hutterova cena

Sérii archivátorů PAQ8HP1 - PAQ8HP8 napsal Alexander Ratushnyak od 21. srpna 2006 do 18. ledna 2007 jako uchazeči o Hutterovu cenu . Hutterova cena je 100 MB komprese 100 MB anglického textu ve formátu xml a kódování UTF-8 ( Wikipedia dump snippet ). Řada PAQ8HP se vyvinula z PAQ8H. Součástí programů byly slovníky pro předzpracování textu a specializované ladění modelů pro testování. Netextové modely byly z programů odstraněny. Slovník byl seskupen ze syntakticky a sémanticky příbuzných slov s běžnými příponami. Syntaktické seskupování umožnilo komprimovat textová data, protože slova s ​​podobným pravopisem se často objevovala společně a kódy jejich slovní zásoby byly snadno modelovány na vysokých bitech. Sémantické seskupení usnadnilo komprimaci slovníku. Test vzal v úvahu velikost programu spolu s komprimovaným slovníkem.

27. října 2006 byla vyhlášena Hutterova cena Jace Bowery [2] . Cena byla obdržena 30. října 2006 po vydání PAQ8HP5 ve výši 3416 eur .

23. května 2009 se Alexander Ratushniak stal třetím vítězem Hutterovy ceny s modifikací PAQ8HP12 .

Výsledky testu

Maximální komprese

Test maximální komprese provádí Werner Bergmans. Využívá dva testovací případy – jeden veřejný a jeden soukromý. Veřejná sada se skládá z asi 55 MB v 10 souborech různých typů: texty různých formátů, spustitelné soubory a obrázky. Programy jsou testovány v režimu maximální komprese z důvodu využití RAM a procesorového času na úkor rychlosti. Test používá dvě kritéria, která je třeba vzít v úvahu: systém účtování komprese pro každý soubor a celkovou velikost komprimovaných dat. K 10. únoru 2007 se testu zúčastnilo 169 kompresorů. Podle prvního kritéria se PAQ8JD umístil na druhém místě po WinRK 3.0.3. Z hlediska celkové velikosti komprimovaných dat byl PAQ8JD první.

Druhá sada dat je soukromá . Skládá se z 316 355 757 bytů v 510 souborech různých typů. Programy jsou seřazeny podle tří kritérií: celková velikost, doba komprese a vzorec, který bere v úvahu velikost a dobu komprese. Proběhlo 200 testovacích jízd, které zahrnovaly některé starší verze; některé programy byly spuštěny s různými možnostmi pro stejný kompresor. Pokud jde o celkovou velikost, jako první byl rozpoznán WinRK 3.0.3, následovaný PAQ8JC a PAQ8JD . PAQ je uveden na konci seznamu pro dobu komprese. PAQ8JD běžel 47 558 sekund (196.) – relativně pomalu ve srovnání s nejrychlejším programem (4 sekundy), ale není špatný ve srovnání s nejpomalejším (70 444 sekund).

Graf (diagram) komprese

Stephen Bush Compression Chart řadí programy podle celkové velikosti komprimovaných dat 16 nepublikovaných datových sad o celkové velikosti 3 271 105 873 bajtů. K 20. únoru 2007 byl PAQ8JC první v testu 201 kompresního programu. PAQ8JD nebyl testován.

Black Fox Test

Test Black Fox hodnotil 111 verzí 69 kompresorů na 12 nepublikovaných souborech o celkové velikosti 30 309 194 bajtů k 4. únoru 2007 . PAQ8JD vyšel jako první.

Velký textový test

Velký test komprese textu ( LTCB ) od Matta Mahoneyho řadí programy podle komprimované velikosti veřejně dostupného 109bytového anglického textového souboru Wikipedie . Na rozdíl od jiných testů zahrnuje velikost dekompresoru a všech souborů potřebných pro kompresi jako archiv zip ve velikosti komprimovaného souboru. K 9. únoru 2007 byl PAQ8HP8 prvním z 62 programů.

PAQ je velmi náročný na paměť a zdroje CPU. Následující tabulka porovnává časy komprese a dekomprese na 2,2 GHz počítači Athlon-64 a také spotřebu paměti v megabajtech pro některé oblíbené programy v tomto testu.

Potomci PAQ

PAQ je svobodný software distribuovaný za podmínek GNU General Public License . To umožňuje ostatním autorům rozvětvovat PAQ a provádět změny, jako je grafické uživatelské rozhraní , nebo zlepšit rychlost komprese na úkor kompresního poměru. Nejznámější klony PAQ:

• WinUDA 0.291 , založený na PAQ6, ale rychlejší [2]
• UDA 0.301 je založen na algoritmu PAQ8I [3]
• KGB Archiver je v podstatě PAQ6v2 s GUI (beta podporuje kompresní algoritmus PAQ7)
• Emilcont založený na PAQ6 [4]
• PeaZip  - GUI (pro Microsoft Windows a GNU/Linux ) pro PAQ8F, PAQ8JD a PAQ8L [5]

Viz také

• Bezeztrátová komprese
• PPM kompresní algoritmus

Poznámky

1. ↑ PAQ1: Model Description Archived 27. října 2016 na Wayback Machine , 2002, Matt Mahoney, v1.02
2. ↑ Oleksandr Ratushniak vyhrál první platbu Hutterovy ceny Archivováno 8. září 2007 na Wayback Machine 

Literatura

• D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin Metody komprese dat. Uspořádání archivátorů, komprese obrazu a videa Dialog-MEPhI, 2002, 384 s. ISBN 5-86404-170-X . 3000 kopií Kniha, bez jejího porozumění by překlad tohoto článku nebyl možný.

Odkazy

• Web projektu  (anglicky)  (Datum přístupu: 16. října 2010)
• PAQ Linux Binaries  ( přístup  7. června 2009)  – zkompilované binární soubory PAQ pro Linux
• MaximumCompression.com  ( přístup  7. června 2009)  je stránka, která testuje a poskytuje data o kompresorech na základě různých softwarových nástrojů.
• Největší zdroj komprese dat v Rusku  (rus.)  (Datum přístupu: 7. června 2009)
• Největší katalog kompresních zdrojů Archivováno 16. července 2006 na Wayback Machine  ( přístup  7. června 2009)