Beste antwoord
Als je met “beste” de compressieverhouding bedoelt, dan volgens de Benchmark voor grote tekstcompressie het is CMIX. Het enige probleem is dat je een computer met 32 GB geheugen nodig hebt om het te kunnen gebruiken. En dan duurt het 4 dagen om 1 GB tekst te comprimeren of te decomprimeren.
Net als de meeste van de best gerangschikte programmas, gebruikt CMIX woordenboekvoorbewerking en PAQ-stijl contextmenging. De preprocessor vervangt woorden door 1 tot 3 bitsymbolen uit een woordenboek en voert andere bewerkingen uit, zoals het vervangen van hoofdletters door een speciaal symbool en het bijbehorende symbool voor kleine letters. Het kan ook algemene voorvoegsels en achtervoegsels parseren.
Een contextmodel neemt een context (bijvoorbeeld de laatste n bits) en raadt een kans p dat de volgende bit een 0 of 1 zal zijn. Het resultaat wordt naar een rekenkundige coder gestuurd, die de bit codeert die zeer dicht bij de Shannon-limiet van log2 ligt 1 / p bits. De compressieverhouding hangt dus volledig af van hoe goed p wordt geschat. Een algoritme voor contextmenging maakt zeer nauwkeurige voorspellingen door de voorspellingen van vele onafhankelijke modellen te combineren. CMIX gebruikt honderden modellen en daarom kost het zoveel tijd en geheugen. De reden dat er zoveel modellen zijn, is dat er veel verschillende mogelijke contexten zijn, veel manieren om een context om te zetten in een voorspelling, veel manieren om het model bij te werken en veel manieren om de voorspellingen van andere modellen adaptief te combineren en de beste te selecteren met een hiërarchie van mixers. Praktische contextmixers gebruiken mogelijk 2 tot 20 modellen, waarbij ze wat compressie opofferen voor eenvoud en bruikbaarheid.
De beste compressoren komen in de buurt van begrip de tekst. Ze modelleren de lexicale, semantische en grammaticale structuur van de taal. Het woordenboek is bijvoorbeeld georganiseerd door verwante woorden te groeperen, zoals moeder met vader en maandag met dinsdag . Dit resulteert in woordenboekcodes die alleen verschillen in de lage bits. Vervolgens laten sommige contextmodellen de lage bits vallen, waardoor de compressor kan voorspellen Ik zag mijn vader maandag na Ik zag mijn moeder dinsdag .
De technische details kunnen behoorlijk ingewikkeld zijn. Als u meer wilt weten, raadpleegt u Gegevenscompressie uitgelegd .
Antwoord
Ervan uitgaande dat u het hebt over verliesvrij compressie (teksten kunnen verliesvrij worden gecomprimeerd met bijvoorbeeld SMS-taal), het is algemeen bekend dat u “geen enkel” binair bestand lossless kunt comprimeren. Met andere woorden, sommige bestanden zullen groter worden. Dit komt door coder-headerbestanden en basisberekeningen van onmogelijke bijecties tussen [0, …, N] en [0, …, N-1], of het Dirichlet-duiventilprincipe (Schubfachprinzip). Zie http://en.wikipedia.org/wiki/Pigeonhole\_principle
Zoals eerder gezegd, verwijst “best” in het algemeen naar een gemiddelde compressieverhouding @ Sam-Jp. De tekenset van teksten (bijvoorbeeld ascii 7 of 8 bits is belangrijk) en hun type is ook belangrijk. “Beste compressie” op geschreven tekstbestanden in pure mensentaal gedragen zich anders op printerpostscript-, rtf-, doc- of zelfs pdf-bestanden die tekst bevatten, aangezien sommige formaten al compressie bevatten. Bijgevolg hangt “beste” in compressieverhouding af van de database-inhoud, homogeniteit en typologie van tekstbestanden, zoals te zien is in Engelse tekstcompressie gegeven in @ Igor-Carron link: http://www.maximumcompression.com/data/text.php
Snelheid @ Jonathan-Hseu is ook best belangrijk. Afhankelijk van uw toepassing (van archivering tot database-interacties @ Daniel-Lemire), concentreert men zich op compressie of decompressie (meestal eenmaal comprimeren, veel decomprimeren), of beide.
Maar andere functies kunnen worden beoordeeld als nou, vooral met de komst van enorme datasets en diverse acquisitiesystemen: -willekeurige toegangsprestaties of zoekmogelijkheden in gecomprimeerde bestanden -foutbestendigheid (weerstand tegen beschadigde bits) -online-mogelijkheid, dwz in staat zijn om de datastroom efficiënt te comprimeren zoals deze komt – compressie van teksten die niet alleen in een rastervolgorde zijn gestructureerd, maar ook in bomen, grafieken – lage complexiteit of energetische efficiëntie van de coder, of decoder, of beide – mogelijke parallellisatie – mogelijkheid tot gedistribueerde codering (compressiewerk gedeeld op verschillende knooppunten van een netwerk)
Uiteindelijk, zelfs voor tekst, kan men buiten de lossless box denken. En we gaan terug naar eerder geciteerde sms-berichten, waar betekenis belangrijk is, maar misschien niet de juiste spelling, zie bijv.Kaufman & Klein, semi-verliesloze compressie http://www.computer.org/portal/web/csdl/doi/10.1109/DCC.2004.1281520
Zoals gewoonlijk lost het stellen van de vraag “beste” op bij het verfijnen van de vraag naar het werkelijke doel, bij het definiëren van aanvullende kwaliteitsstatistieken en passende weging van die metrieken om “uw” beste @ Alex-Kamil te definiëren. Onderwerpen in de volgende bronnen zijn inspirerend:
* IEEE Transactions on Information Theory http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=18 * IRE Transactions on Information Theory http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=4547527 * Data Compression Conference pages.cs.brandeis.edu/~dcc/
Tot slot, als geen specialist maar amateur in lossless compressie, ben ik onlangs verbaasd over de prestaties (in compressieverhouding) van Deplump (http://www.deplump.com/index.html) op enkele lange Engelse tekstbestanden en een paar binaire bestanden (in vergelijking met mijn favorieten rar, Bzip2 en 7zip geciteerd in andere antwoorden). U kunt het online testen op korte bestanden. Voor meer informatie, zie F. Wood et al. The Sequence Memoizer, 2011 (zie http://www.sequencememoizer.com/) of de Franck Wood “s webpagina http://www.stat.columbia.edu/~fwood/