Begripsuitleg:
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?

Even een paar vragen van een geïnteresseerde leek:

Hoe kun je 8000 bits (enen en nullen) opslaan in 1 bit? Hoe stel ik me dat voor?
Wat heb je aan een programma dat met grote waarschijnlijkheid de volgende bit kan voorspellen? Ik wil gewoon mijn oorspronkelijke foto zien en niet een kans (hoe klein ook) dat ik niets meer zie, vanwege een foutieve voorspelling.

refo schreef:Even een paar vragen van een geïnteresseerde leek:

Hoe kun je 8000 bits (enen en nullen) opslaan in 1 bit? Hoe stel ik me dat voor?
Wat heb je aan een programma dat met grote waarschijnlijkheid de volgende bit kan voorspellen? Ik wil gewoon mijn oorspronkelijke foto zien en niet een kans (hoe klein ook) dat ik niets meer zie, vanwege een foutieve voorspelling.

1. http://en.wikipedia.org/wiki/Arithmetic_coding

2. De voorspelling is exact en dus steeds op dezelfde plekken goed of fout. Daardoor is het bestandje altijd weer terug te halen.

Het is echt geen magie hoor. Je kunt je hier vast wel een voorstelling van maken: stel je voor dat ik 8000 keer 'e' in zou typen. Menselijk gezien kun je dan ook gewoon zeggen: 8000*'e' en als mens weet je dan voldoende. Daaraan en dan iets meer geavanceerd moet je aan denken wanneer ik het heb over 8000 bits in 1 bit. Je kunt die situatie krijgen doordat je bijv. een database aan het compresseren bent en er achter komt dat een flink groot veld al eerder is langs gekomen en dan hoef je maar 1 bit op te slaan. De bit van: 'ja weer dat veld ja. Dat heb je goed ingeschat'. Zit het algoritme fout, dan komen er juist meer bits dan dat het oplevert. Door het algoritme fout te gebruiken en foute inschattingen te maken, worden bestanden juist groter in plaats van kleiner.

Kaw schreef:

refo schreef:Even een paar vragen van een geïnteresseerde leek:

Hoe kun je 8000 bits (enen en nullen) opslaan in 1 bit? Hoe stel ik me dat voor?
Wat heb je aan een programma dat met grote waarschijnlijkheid de volgende bit kan voorspellen? Ik wil gewoon mijn oorspronkelijke foto zien en niet een kans (hoe klein ook) dat ik niets meer zie, vanwege een foutieve voorspelling.

1. http://en.wikipedia.org/wiki/Arithmetic_coding

2. De voorspelling is exact en dus steeds op dezelfde plekken goed of fout. Daardoor is het bestandje altijd weer terug te halen.

Het is echt geen magie hoor. Je kunt je hier vast wel een voorstelling van maken: stel je voor dat ik 8000 keer 'e' in zou typen. Menselijk gezien kun je dan ook gewoon zeggen: 8000*'e' en als mens weet je dan voldoende. Daaraan en dan iets meer geavanceerd moet je aan denken wanneer ik het heb over 8000 bits in 1 bit. Je kunt die situatie krijgen doordat je bijv. een database aan het compresseren bent en er achter komt dat een flink groot veld al eerder is langs gekomen en dan hoef je maar 1 bit op te slaan. De bit van: 'ja weer dat veld ja. Dat heb je goed ingeschat'. Zit het algoritme fout, dan komen er juist meer bits dan dat het oplevert. Door het algoritme fout te gebruiken en foute inschattingen te maken, worden bestanden juist groter in plaats van kleiner.

Alleen bij de laatste zin kan ik me iets voorstellen.
Hoewel wiskunde mijn lievelingsvak was, zie ik wel in dat je mijn hulp niet kunt gebruiken.

Enfin, ik lees het t.z.t. wel in de krant, als je de Nobel-prijs hebt gewonnen.

jvdg schreef:Hoewel wiskunde mijn lievelingsvak was, zie ik wel in dat je mijn hulp niet kunt gebruiken.

Dan mag jij dit topic modereren.

Kaw, ik denk dat je de meeste kans bij Parsifal maakt.

Tiberius schreef:

jvdg schreef:Hoewel wiskunde mijn lievelingsvak was, zie ik wel in dat je mijn hulp niet kunt gebruiken.

Dan mag jij dit topic modereren.

Kaw, ik denk dat je de meeste kans bij Parsifal maakt.

Ik heb in het verleden Parsifal hier al eens mee lastig gevallen, maar hij heeft toen aangegeven dat hij het niet zo interessant vond dat hij zijn tijd hierin wilde steken. Misschien is met de crisis het één en ander anders geworden? Parsifal kennende spiekt hij binnen 7 dagen wel even in deze topic en merken we het vanzelf of de kaarten nu anders liggen.

Als het sneller en efficiënter comprimeert dan 7zip ga ik het graag gebruiken.

Ik ben voorspelbaar. Ik zal er nog een keer naar kijken . Maar ik ga er weer niet uitgebreid voor zitten (Eerst maar eens een onderzoeksvoorstel schrijven waardoor ik ook de volgende jaren op jullie belastinggeld de volksgezondheid op niveau kan houden ).

Heb het idee dat zippen beetje uit de mode is.
Tegenwoordig allemaal TB schijven, en high speed abbo's..

Ik volg lang niet alles (bijvoorbeeld dat renormaliseren), maar het algoritme ziet er zo op het eerste gezicht elegant uit. Je moet er maar opkomen.

De volgende zin snap ik niet zo: "de kans dat de volgende byte na het gevonden patroon de goede is, gemiddeld gezien groter wordt wanneer het gevonden patroon groter is". Kun je dat toelichten?

Is het nu zo dat je bit-voor-bit gaat coderen? In dat geval heb je toch maar twee symbolen? Een 0 met een bepaalde kans en een 1 met een bepaalde kans (dus twee intervallen)? Of codeer je byte-voor-byte? Of snap ik er helemaal niets van als ik dit zeg?

Als je aangeeft dat je 'meer waarde hecht' aan grotere patronen, bedoel je dan dat je een soort weegfactor gebruikt? Maak je bijvoorbeeld verschillende kansverdelingen voor verschillende patroongroottes en gooi je daar een weging overheen?

Geef eens een heel concreet voorbeeld van een te coderen bitregel en hoe je dit dan op dit moment aanpakt.

Kortom: er is me nog veel onduidelijk. Maar goed, ik ben dan ook geen wiskundige.

Ik ben trouwens erg benieuwd naar je algoritme om in een fractie van een seconde elk overeenkomstig patroon van elke lengte te vinden.

Kaw schreef:Wat is de kans dat de gevonden byte, van een patroon met een bepaalde lengte, de juiste is?

Kun je deze vraag misschien herformuleren of toelichten? Wat is een 'gevonden' byte? Wat is een 'juiste' byte?
Wat is de relatie met het patroon.

Ik zie nu voor me dat je een mapping maakt van bytes (de te coderen symbolen) met patronen. Maar of dat echt zo is of hoe dat precies werkt weet ik nu niet.

Ik snap er geen byte van.

Gian schreef:Heb het idee dat zippen beetje uit de mode is.
Tegenwoordig allemaal TB schijven, en high speed abbo's..

Juist die high speed modems gebruiken geavanceerde compressietechnieken om die hoge snelheden mogelijk te maken, volgens mij.
Al sluit ik me verder gauw bij Jongere aan.

Even een snelle gedachte. Ik heb het probleem niet meer helemaal voor me.

Je wint mogelijk heel wat informatie over een bit als je niet alleen weet wat er aan deze bit voorafging maar ook weet wat er op volgt. Het is bijvoorbeeld vaak waarschijnlijker dat je in een rijtje x_1,?,x_3, de waarde van het vraagteken goed kunt voorspellen, dan in het rijtje x_1,x_2,?. Ik weet niet of het mogelijk is hier gebruik van te maken en of je dat al doet.

Hallo,

krijg dit topic doorgestuurd door mn moeder (Helma) en het klinkt wel heel interresant.
Ik heb een paar computerscience course achter de rug en ben momenteel bezig met het vak "theory of statistics and data analysis"
Niet dat ik er nu expert in ben, maar misschien kan je me wat extra informatie sturen, of uitleggen wat je precies wilt doen. Het klinkt iig beter dan de compressie van Jan Sloot (zie http://nl.wikipedia.org/wiki/Jan_Sloot )
Ook heb een leraar die er eventueel (denk ik) een kijkje naar wil nemen als het de moeite waard is. (http://www.roac.nl/roac/sci-dept.phtml?st=meijer)
hoop van je te horen,

Groetjes Gerhard

PS oh ja, en ik ben vaak ook erg druk