Paras vastaus
Jos sanalla ”paras” tarkoitat pakkaussuhdetta, niin Suuri tekstinpakkauksen vertailuarvo , se on CMIX. Ainoa ongelma on, että tarvitset tietokoneen, jossa on 32 Gt muistia. Ja sitten kestää 4 päivää 1 Gt: n tekstin pakkaamiseen tai purkamiseen.
Kuten useimmat parhaimmaksi luokitelluista ohjelmista, CMIX käyttää sanakirjojen esikäsittelyä ja PAQ-tyylistä kontekstimiksua. Esiprosessori korvaa sanat 1-3 bittisillä symboleilla sanakirjasta ja suorittaa muun käsittelyn, kuten korvaa isot kirjaimet erikoissymbolilla ja vastaavalla pienillä kirjaimilla. Se voi myös jäsentää yleisiä etuliitteitä ja jälkiliitteitä.
Kontekstimalli ottaa kontekstin (esimerkiksi viimeiset n bittiä) ja arvaa todennäköisyyden p että seuraava bitti on 0 tai 1. Tulos syötetään aritmeettiseen kooderiin, joka koodaa bitin hyvin lähellä log2: n Shannon-rajaa 1 / p bittiä. Pakkaussuhde riippuu siis täysin siitä, kuinka hyvin p arvioidaan. Kontekstin sekoitusalgoritmi tekee erittäin tarkat ennusteet yhdistämällä monien itsenäisten mallien ennusteet. CMIX käyttää useita satoja malleja, minkä vuoksi se vaatii niin paljon aikaa ja muistia. Syy niin monien mallien olemassaoloon on, että on olemassa monia erilaisia mahdollisia konteksteja, monia tapoja muuntaa konteksti ennustukseksi, monia tapoja päivittää malli ja monia tapoja yhdistää muiden mallien ennusteet mukavasti ja valita parhaat käyttämällä sekoittimien hierarkia. Käytännön kontekstimikserit saattavat käyttää 2 – 20 mallia, uhraamalla jonkin verran pakkaamista yksinkertaisuuden ja käytettävyyden vuoksi.
Parhaat kompressorit ovat lähellä ymmärrystä teksti. Ne mallintavat kielen leksikaalisen, semanttisen ja kieliopillisen rakenteen. Sanakirja järjestetään esimerkiksi ryhmittelemällä toisiinsa liittyvät sanat, kuten äiti ja isä ja maanantai ja tiistai . Tämä johtaa sanakoodeihin, jotka eroavat vain matalilla biteillä. Sitten jotkut kontekstimallit pudottavat matalat bitit, jolloin kompressori voi ennustaa Näin isäni maanantaina nähtyäni Näin äitini tiistaina .
Tekniset yksityiskohdat voivat olla mukana. Jos olet kiinnostunut oppimaan lisää, katso Tietojen pakkaus selitetty .
Vastaa
Olettaen, että puhut häviöttömästä pakkaus (tekstit voivat olla häviöllisesti pakattuja esimerkiksi tekstiviestikielellä), tiedetään hyvin, että et voi pakata häviöttömästi ”mitään” binaaritiedostoa. Toisin sanoen joidenkin tiedostojen koko kasvaa. Tämä johtuu kooderin otsikkotiedostoista ja perusmatematiikasta, joka sisältää mahdottomia bijektioita [0, …, N] – [0, …, N-1] välillä, tai Dirichlet-kyyhkyreiän periaatteesta (Schubfachprinzip). Katso http://en.wikipedia.org/wiki/Pigeonhole\_principle
Kuten aiemmin mainittiin, ”paras” viittaa yleensä johonkin keskimääräiseen pakkaussuhteeseen @ Sam-Jp. Myös tekstien merkistö (esim. Ascii 7 tai 8 bittiä on merkitystä) ja niiden tyyppi ovat tärkeitä. Puhtaiden ihmiskielisten kirjoitettujen tekstitiedostojen ”paras pakkaus” käyttäytyy eri tavalla kirjoitinta sisältävissä postscript-, rtf-, doc- tai jopa pdf-tiedostoissa, koska joissakin muodoissa pakkaus on jo koteloitu. Tästä johtuen pakkaussuhteen ”paras” riippuu tietokannan sisällöstä, homogeenisuudesta ja tekstitiedostojen typologiasta, kuten englanninkielinen tekstipakkaus näkyy @ Igor-Carron -linkissä: http://www.maximumcompression.com/data/text.php
Nopeus @ Jonathan-Hseu on myös melko tärkeä. Sovelluksestasi riippuen (arkistoinnista tietokannan vuorovaikutuksiin @ Daniel-Lemire) keskitytään joko pakkaamiseen tai purkamiseen (tavallisesti pakataan kerran, puretaan monet) tai molempiin.
Mutta muita ominaisuuksia voidaan arvioida hyvin, erityisesti valtavien tietojoukkojen ja monipuolisten hankintajärjestelmien myötä: – satunnainen pääsy suorituskykyyn tai hakukyky pakatuissa tiedostoissa – virheiden joustavuus (vastustuskyky vioittuneille biteille) – online-ominaisuus, eli mahdollisuus pakata tietovirta tehokkaasti – paitsi rasterijärjestyksessä, myös puissa, kaavioissa pakattujen tekstien pakkaus – kooderin tai dekooderin monimutkaisuus tai energiatehokkuus tai molemmat – mahdollinen rinnakkaistaminen – hajautetun koodauksen mahdollisuus (pakkaustyö jaettu verkon eri solmuissa)
Lopulta jopa tekstin osalta voidaan ajatella häviöttömästä laatikosta. Ja palaamme aiemmin lainattuihin tekstiviesteihin, joissa merkitys on tärkeä, mutta ehkä ei oikea kirjoitusasu, katso esim.Kaufman & Klein, puolihäviötön pakkaus http://www.computer.org/portal/web/csdl/doi/10.1109/DCC.2004.1281520
Kuten tavallisesti, kysymys ”paras” ratkaisee tarkentamalla todellisen tarkoituksen kysymystä, määrittelemällä lisäkysymyksiä laatumittarit ja näiden mittareiden asianmukainen painotus määritelläksesi ”paras” @ Alex-Kamil. Seuraavien lähteiden aiheet ovat inspiroivia:
* IEEE-transaktiot tietoteoriassa http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=18 * IRE-informaatioteorian tapahtumat http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=4547527 * Tiedon pakkauskonferenssi pages.cs.brandeis.edu/~dcc/
Lopuksi, koska en ole asiantuntija vaan amatööri häviöttömässä pakkauksessa, olen viime aikoina hämmästynyt Deplumpin (http://www.deplump.com/index.html) joillekin pitkille englanninkielisille tekstitiedostoille ja muutamalle binaaritiedostolle (verrattuna muihin vastauksiin lainattuihin suosikkini rar, Bzip2 ja 7zip). Voit testata sitä lyhyiden tiedostojen varalta verkossa. Katso lisätietoja F. Wood et ai. Sequence Memoizer, 2011 (katso http://www.sequencememoizer.com/) tai Franck Woodin verkkosivu http://www.stat.columbia.edu/~fwood/