Bit: 0 of 1
Byte: 8 bits, 256 verschillende waarden, (2^8)
Patroon: In mijn definitie is dat een stukje informatie (in dit geval bytes) met een bepaalde lengte, die exact ook elders gevonden kan worden in een gegevensverzameling.
Ik ben nu (privé) 1,5 jaar bezig met het ontwikkelen van een goed stukje software voor data compressie. Dat is min of meer een hobby van me geworden. Al vanaf mijn tienerjaren heb ik pogingen gedaan om zelfstandig een algoritme te ontwikkelen om data compressie te bewerkstelligen. Één van mijn eerste pogingen was om zelf een soort van database te maken van veel voorkomende stukjes Nederlands en dat dan verkleint op te slaan. Daarmee bereikte ik 50% kleinere bestandjes, maar was wel beperkt tot Nederlandse tekst bestandjes
Later heb ik het niet kunnen nalaten om ook eens andere compressietechnieken onder de loep te nemen, maar echt spannend waren ze niet. De laatste jaren is daar juist veel ontwikkeling in geweest en heeft wat spannende algoritmes opgeleverd. Één daarvan is Arithmetic coding en dat is echt een mooi stukje werk, dus die heb ik geïmplementeerd. Dit is de eerste stap in een tweetrapsraket. Dit algoritme verzorgt de opslag van gegevens op een geweldige manier. Een voorbeeldje: indien ik met 99% zeker weet wat de komende bit in het bestand is, dan kan ik door dit algoritme deze bit in 1/100e van een bit opslaan. Wanneer ik 99.9% zeker weet dat de volgende bit bijv. 1 is, dan kan ik het zelfs in 1/1000e van een bit dit gegeven opslaan door dit knappe algoritme. Gok ik fout, dan kost het me juist veel bits om 1 bit op te slaan. Het gaat dus om de voorspelbaarheid. Hoe beter ik kan voorspellen wat de volgende bit zal worden, hoe beter ik de gegevens kan compresseren. Dat gedeelte is inmiddels klaar en afgerond. Tot 1/8000e nauwkeurigheid kan ik bits opslaan of ophalen met behulp van dit algoritme. Theoretisch kan ik hiermee 8000 bits proppen in 1 bit. Ruim voldoende om als ondergrond te gebruiken voor de volgende trap.
Wat meteen opvalt in het vorige voorbeeld is dat ik wel zo goed mogelijk moet weten wat de volgende bit zal zijn om goede compressie te bereiken. Ik heb daar het volgende voor gemaakt: mijn programma kan in een fractie van een seconde elk mogelijk overeenkomstig patroon vinden binnen een bestand van elk gewenste lengte. Daarin is deze uniek, want andere compressieprogramma's gaan niet verder dan het herkennen van patronen van 4 tot 5 en soms 6 bytes, terwijl mijn programma niet beperkt is in patroongrootte en vind moeiteloos patronen van 10000 bytes en meer. Het grote voordeel van het vinden van grote patronen is dat (en dit heb ik bewezen) de kans dat de volgende byte na het gevonden patroon de goede is, gemiddeld gezien groter wordt wanneer het gevonden patroon groter is. Dit mechanisme is ook bekend bij andere ontwikkelaars, maar het wordt niet gebruikt, omdat deze methode in de praktijk een lagere compressie oplevert dan de door velen optimaal geachte patronen van 5 bytes. Dit komt omdat het gebruik van de langste patroon het algoritme blind maakt voor de mogelijkheid van het bestaan van een andere byte. Als het algoritme het mis heeft, dan kost dat extreem veel bits. Het algoritme ziet alleen maar 1 patroon en denkt dat hij 100% goed zit met zijn inschatting, omdat hij maar 1 patroon heeft. Dit is op te heffen door elk gevonden patroon van elke lengte mee te nemen in de beslissing, maar gewoon meer waarde te hechten aan de byte die gekoppeld is aan het patroon met een grotere omvang. Dat doe ik nu en de resultaten zijn even goed als de resultaten van bijv. 7zip, een programma met een algoritme die zeer goed presteert en veel gebruikt wordt.
Mijn probleem is als volgt: Ik heb nu dat algoritme en ik kan ook voor elke gewenste byte de bijbehorende patronen vinden binnen een bestand. Alleen de kansrekening van mij is een troepje. Ik doe maar wat. Door wat met de hand te prutsen kom ik tot goede resultaten, maar ben ik niet beter dan de concurrentie. Ik wil graag hulp hebben met het bepalen van het volgende: Wat is de kans dat de gevonden byte, van een patroon met een bepaalde lengte, de juiste is? Als ik dat goed weet in te schatten, dan geloof ik echt dat het algoritme beter zal presteren ten opzichte van alle concurrenten. Wie oh wie heeft wat meer verstand van kansrekening dan ik?
Parsifal kennende spiekt hij binnen 7 dagen wel even in deze topic en merken we het vanzelf of de kaarten nu anders liggen.
)