Wiskundige gezocht voor kansrekening binnen hobbyproject

[Tiberius]

PS oh ja, en ik ben vaak ook erg druk

Zo moeder, zo zoon.

[helma]

PS oh ja, en ik ben vaak ook erg druk

Zo moeder, zo zoon.

Ik heb er meer met ADHD

[MarthaMartha]

Ik snap er geen byte van.

[parsifal]

Mijn eerste poging voor compressie van een tekst zou trouwens de volgende zijn:

geef voor iedere serie leestekens (inclusief spaties, voor het gemak even zonder getallen) een meest waarschijnlijke volgend leesteken, mogelijk met een cut-off bij 10 leestekens ofzo. Geef vervolgens de tekst weer als een reeks letters en getallen:

Als de eerste n tekens van de oorspronkelijke tekst wordt weergegeven door x_n, en het n-de leesteken is z_n.

en de samengevatte versie van x_n is van de vorm y_n=(a_i,b), waarbij a_i een reeks leestekens of getallen is en b een geheel getal.
als z_(n+1) juist voorspeld wordt op grond van y_n, dan wordt y_(n+1)
(a_i,b+1) (waarbij dus b met 1 opgehoogd wordt) als z_(n+1) niet juist voorspeld wordt door y_n dan geldt y_n+1=(a_i,b,z_(n+1)). Als y_n niet op een getal eindigt, dan is y_(n+1) ofwel een 1 (in geval van juiste voorspelling) ofwel een leesteken (in geval van onjuiste voorspelling).

Dit is vast al eens bedacht of niet zinnig (ik weet niets van coderingstheorie en computers in het algemeen), maar ik ben wel benieuwd waarom het eventueel niet werkt.

[memento]

Kaw, misschien is het handig om de tekst bij het compressen eerst te analyseren, en dus per te compressen bestand een tabel op te stellen, die je helpt de volgende waarde te voorspellen. Want de voorspelbaarheid van een volgend bit/byte kan per bestand(type) verschillen.

[wim]

Kaw, misschien is het handig om de tekst bij het compressen eerst te analyseren, en dus per te compressen bestand een tabel op te stellen, die je helpt de volgende waarde te voorspellen. Want de voorspelbaarheid van een volgend bit/byte kan per bestand(type) verschillen.

Het algoritme waar Kaw naar verwijst kan volgens mij zelfs adaptief zijn. Dus dat het binnen een bestand (tijdens het coderen) wijzigt. Een willekeurig deel van een document kan heel andere statistieken opleveren. Neem bijvoorbeeld het geval dat je (in het geval van een plaatje) een strakblauwe lucht zou willen coderen boven een zeer kleurrijk en gevarieerd landschap. Dan is één statistiek wat magertjes.

[Kaw]

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

Sneller is absoluut niet mijn doel. Gezien de aard van het algoritme ten opzichte van het algoritme van 7zip is het ook onwaarschijnlijk dat het ooit zal lukken.
Betere compressie is mijn enige doel op dit moment.

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

Nou, dat heb je mis. Een film wordt niet gezipt of muziek ook niet, omdat de onderliggende codering al supersterke compressie kent. Bijv. MP3 en .H264 kunnen niet nog een keer zinvol ingepakt worden. Het is al vrijwel optimaal opgeslagen. Zip dus niet meer, maar ondertussen zijn juist de onderliggende bestanden vaak veel beter gecompresseerd.

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?

Stel je voor dat je een patroon heb die er als volgt uit ziet: "hui"
Dan heb je menselijkerwijs de mogelijkheid voor de volgende woorden: "huis", "huig", "huil", "huid", enz.
Of je ziet het volgende: "huidziekt", dan zou je vrij zeker weten dat je zoekt naar de letter "e".

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?

Nee, goede vraag. Wat ik wil doen is voor elke stap in het proces de volgende byte voorspellen. Om tot een goede voorspelling te komen wil ik voor de 256 mogelijkheden elk vaststellen hoe groot de kans is dat die waarde de gezochte waarde is. Vervolgens sla ik wel per bit de kans op of het een 0 of een 1 is. Doordat ik een kanslijst heb van de 256 mogelijke waarden kan ik simpel per bit de kans bepalen. Het voordeel van deze methode is dat per bit je het lijstje kansen kan halveren, omdat je inmiddels 1 bit van de uitkomst heb. In de praktijk verhoogt deze techniek de compressie een beetje.

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?

Voor elk patroon met lengte L geef ik de volgende score: score = (l * l * l * l) / 1.8; en die tel ik op als score bij 1 van de 256 mogelijkheden van de byte. Zoals je ziet is dit een waardeloze benadering is en compleet uit de lucht gegrepen, maar het werkt eigenlijk nog best goed.

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

Geen zin in. Dan moet je de code maar eens bekijken. Dat snap je wel.

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

Door een gesorteerde lijst bij te houden van de inhoud.

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.

Stel je voor: je hebt een tekstbestandje en ben aangekomen bij de volgende reeks bytes: "huidz" en je ziet dat er een eerder stukje tekst in het bestand staat met "huidz" en waar de volgende byte een "i" is. Dan is die "i" de gevonden byte en de gezochte byte die gelijk de juiste byte is, is de byte die je daadwerkelijk aantreft als volgende byte bij het opbouwen van het bestand. De verwachte byte is ook de "i" in dit voorbeeld, maar dat kan natuurlijk fout zijn.

Ik snap er geen byte van.

Iedereen zo zijn vak.

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.

Parsifal, dat is een goede vraag en terecht opgemerkt, maar volgens mij is in de praktijk van de compressie dit een stellingname die niet op gaat. Bijv. bij het herconstructueren van een DNA-string zou je het missende gaatje op die manier heel goed kunnen opvullen. Bij het toepassen van T9 op je mobiel voor een bepaalde tekst die de gebruiker tussen de al geschreven tekst wil typen zou je opmerking ook zeer zeker opgaan. Maar stel je voor dat je met 0 kennis begint. Dan maakt het niet uit of je het begin en het einde van het bestand tegelijk opbouwt, of juist in het midden naar beide punten toewerkt, of dat je willekeurig in bestand bytes probeert te voorspellen, omdat je altijd zult hebben dat je geen x_1,?,x_3 zult hebben en in het geval van ?,?,x_3,?,x_5,? weet je misschien prettig veel voor x_4, maar zal x_3 en x_5 niet goed zijn te voorspellen waardoor je voor die bytes geen compressie berijkt. Sommige bestanden zijn voor deze opvatting wel geschikt zoals video en plaatjes, omdat je bijv. bij video de frames kunt gebruiken ter referentie en het is een veel gebruikte praktijk om bij plaatjes dit ook toe te passen, omdat je bij plaatjes vaak kunt zeggen dat x_4 niet ver zal afwijken van het gemiddelde van x_3 en x_5.

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

Klinkt goed. Ik zou zeggen: vraag wat je nodig hebt en eventueel kun ik de sourcecode delen.

Kaw, misschien is het handig om de tekst bij het compressen eerst te analyseren, en dus per te compressen bestand een tabel op te stellen, die je helpt de volgende waarde te voorspellen. Want de voorspelbaarheid van een volgend bit/byte kan per bestand(type) verschillen.

In de praktijk is dat niet nodig, omdat je in het begin van elk bestand er van uit kan gaan dat hij volledig onvoorspelbaar start en tijdens de loop van het proces kom je stapsgewijs zelf wel achter de voorspelbaarheid. Bovendien kan een bestand regionaal juist vaak heel voorspelbaar zijn en plaatselijk dan weer juist niet. Door dit in een tabel op te slaan door vooranalyse is het ook nodig om deze tabel mee te sturen bij het bestand dat je hebt gecomprimeerd. Dit verknalt de compressie, want je zit immers met een tabel die je mee moet leveren. Dat is ook de fout geweest in het verhaal van die kerel die beweerde dat je 16 films in 64kb kon proppen. Hij had zeer waarschijnlijk een hardeschijf in zijn apparaat gebouwt die domweg de volledige films bevatte en die 64kb waren niets anders dan verwijzingen naar de informatie op de hardeschijf. Op het oog is dat een heel andere kwestie, maar je deelt hetzelfde probleem. Informatie vooraf moet ook meegestuurd worden. Je verschuift dan als het ware het probleem.

Mijn eerste poging voor compressie van een tekst zou trouwens de volgende zijn:

geef voor iedere serie leestekens (inclusief spaties, voor het gemak even zonder getallen) een meest waarschijnlijke volgend leesteken, mogelijk met een cut-off bij 10 leestekens ofzo. Geef vervolgens de tekst weer als een reeks letters en getallen:

Als de eerste n tekens van de oorspronkelijke tekst wordt weergegeven door x_n, en het n-de leesteken is z_n.

en de samengevatte versie van x_n is van de vorm y_n=(a_i,b), waarbij a_i een reeks leestekens of getallen is en b een geheel getal.
als z_(n+1) juist voorspeld wordt op grond van y_n, dan wordt y_(n+1)
(a_i,b+1) (waarbij dus b met 1 opgehoogd wordt) als z_(n+1) niet juist voorspeld wordt door y_n dan geldt y_n+1=(a_i,b,z_(n+1)). Als y_n niet op een getal eindigt, dan is y_(n+1) ofwel een 1 (in geval van juiste voorspelling) ofwel een leesteken (in geval van onjuiste voorspelling).

Dit is vast al eens bedacht of niet zinnig (ik weet niets van coderingstheorie en computers in het algemeen), maar ik ben wel benieuwd waarom het eventueel niet werkt.

Het werkt. Wat je dan eigenlijk krijgt is http://nl.wikipedia.org/wiki/Lempel_Ziv_Welch als je het iets verder doorvoert, maar http://nl.wikipedia.org/wiki/Aritmetische_codering is in de praktijk krachtiger.

Ik heb gisteravond nog even gebrainstormt over een statistisch model. Volgens mij is er spraken van een samengestelt experiment.

De eerste kans (P) die je moet weten is of de patronen die je hebt gevonden de gezochte byte bevatten. Laten we die P1 noemen. In het begin is P1 0%, want we hebben nog geen referentiepatronen, dus we weten zeker dat er 0% zekerheid is over de gezochte byte. Langzamerhand kunnen we P1 aanpassen aan de praktijk door de successen te delen met de som van de pogingen.
Deelexperiment p2 is de kans of de gevonden byte van patroon x voldoet aan de gezochte byte. Ik denk dat p2 vastgesteld moet worden voor elke patroonlengte. In de praktijk heb ik dit al eens gedaan en wat je ziet is dat bij lengte 0 zoals te verwachten viel de p2 van een willekeurige byte 0.04 is of kleiner en dat loopt langzaam op waarbij bij l(lengte)=5 de p2 rond 0.5 begint te schommelen, terwijl bij l>10 de p2>0.9 wordt.

Wat mijn probleem is, is dat ik niet weet of ik hiermee volledig ben of dat er nog meer deelexperimenten zijn te benoemen. Als we dit duidelijk hebben, dan komt de issue dat we deze wetenschap in praktijk moeten gaan brengen en dat ik met die informatie uit moet vinden wat de (p) is voor een willekeurige byte.

[wim]

Bedankt voor de toelichting. Ik snap het nu iets beter. Maar wat ik ook beter snap is dat ik waarschijnlijk tegen dezelfde problemen op ga lopen.
Als ik genoeg tijd en zin had zou ik er vast wel een keer uitkomen. Maar dat geldt ook voor jou, neem ik aan. Kortom: aan mij heb je niets in dit geval.

Ik weet wel dat je voor de best mogelijke kansverdeling niet voldoende hebt aan het bestand dat je aan het coderen ben.
Als je een een tekstbestand hebt waar meer eenmaal het woord huidziekte in voorkomt (maar eventueel wel een paar woordjes met de uitgang 'te'), dan is de kans op een e na de t wel heel groot, maar dit is dan niet voldoende af te leiden uit dit bestand.

Toch een halfslachtige poging (een slag in de lucht):
De kansen van elk patroonlengte eerst onafhankelijk berekenen (door gewoon het aantal gezochte voorkomens te tellen en te delen door het aantal patronen van die lengte dat géén match heeft op de gezochte byte). (Je zou dan ervoor kunnen kiezen om hieruit de voorkomens weg te laten die ook onderdeel zijn van een groter patroon.)
Deze P noem ik even Pvoorkomens

Vervolgens vermenigvuldig je deze kansen met de kansen vanwege de patroonlengtes (Ppatroonlengte)

Psubtotaal = Pvoorkomens * Ppatroonlengte

Dit doe je voor elk patroonlengte.
Vervolgens tel je deze kansen onafhankelijk op (ook al zullen ze in werkelijkheid niet echt onafhankelijk zijn).
Volgens mij gaat dat zo:

Ptotaal = 1.0 - (1.0 - Psubtotaal1) * (1.0 - Psubtotaal2) * (1.0 - Psubtotaal3) *....

[MarthaMartha]

door gewoon het aantal gezochte voorkomens te tellen en te delen door het aantal patronen van die lengte dat géén match heeft op de gezochte byte

heel gewoon...

[wim]

door gewoon het aantal gezochte voorkomens te tellen en te delen door het aantal patronen van die lengte dat géén match heeft op de gezochte byte

heel gewoon...

Ja sorry. Mijn woordenschat is niet toereikend voor een betere formulering.

[MarthaMartha]

door gewoon het aantal gezochte voorkomens te tellen en te delen door het aantal patronen van die lengte dat géén match heeft op de gezochte byte

heel gewoon...

Ja sorry. Mijn woordenschat is niet toereikend voor een betere formulering.

geeft niet hoor, het zou evengoed spaans voor me zijn denk ik.............

[wim]

door gewoon het aantal gezochte voorkomens te tellen en te delen door het aantal patronen van die lengte dat géén match heeft op de gezochte byte

Volgens mij klopt het ook niet eens wat ik hier schrijf.

Ik bedoel dit: Als je het patroon 'huiX' als uitgangspunt neemt. waarin X het gezochte teken is. Dan tel je het aantal voorkomens van dit patroon.
Vervolgens kijk je voor elk teken (symbool) hoe vaak dat voorkomt op de plek van X. Voor elk teken bereken je de kans (voor het teken d geldt: het aantal voorkomens van huid gedeeld door het aantal voorkomens van huiX is de kans (voor een patroonlengte van 4)).
Dat is dan voor de letter d de Pvoorkomens voor patroonlengte 4.

Voor de rest geldt dan het verhaal wat ik al opschreef.

[Kaw]

Hoi Wim,

Je hebt dan de verdeling binnen patroon 4 om het zo te zeggen, maar het zegt nog niets over een kans in het licht van alle patronen en de uiteindelijke uitslag.

Ik heb van het weekend het probleem kunnen verschuiven naar het volgende puzzeltje:
Stel je voor dat we een flinke groep (niet occulte ) waarzeggers hebben en van elke waarzegger is bekent hoe groot de kans is dat hij gelijkt heeft. Die heb ik voor de het gemak ook weer in groepen ingedeeld.
a. 100 waarzeggers die 0.3 keren van de tijd de waarheid spreken.
b. 30 waarzeggers die 0.4 keren van de tijd de waarheid spreken.
c. 10 waarzeggers die 0.6 van de tijd de waarheid spreken
d. 3 waarzeggers die 0.8 keer van de tijd de waarheid spreken
e. 1 waarzegger die 0.95 keer van de tijd de waarheid spreken

Je hebt 4 mogelijke uitkomsten. (rood, blauw, groen en geel) (In mijn geval zijn dat er 256, maar voor het voorbeeldje maakt het niet uit)
De verdeling is als volgt
Groep a zegt: 40 keer rood, 30 keer blauw, 15 keer groen en 15 keer geel
Groep b zegt: 10 keer rood, 5 keer blauw, 5 keer groen, 10 keer geel
Groep c zegt: 3 keer rood, 3 keer blauw, 3 keer groen, 1 keer geel
Groep d zegt: 1 keer rood, 0 keer blauw, 0 keer groen, 2 keer geel
Groep e zegt: 0 keer rood, 0 keer blauw, 0 keer groen, 1 keer geel

Ik moet weten wat de kans uiteindelijk is per kleur op basis van deze kennis.

[Da Capo]

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

Integendeel, het wordt almeer gebruikt. Het nieuwe bestandsformaat van de MS Office programma's (dus de docx, xlsx, pptx e.d.) zijn gewoon ordinaire zip bestanden.
Dat kan je zo testen: hernoem bijv. een docx naar .zip en je kan 'm uitpakken. Je krijgt dan een folder structuur met een een aantal xml bestanden. Dat maakt het bestandsformaat voor programmeurs erg aantrekkelijk, maar dat ff terzijde.

[albion]

door gewoon het aantal gezochte voorkomens te tellen en te delen door het aantal patronen van die lengte dat géén match heeft op de gezochte byte

heel gewoon...

Ja sorry. Mijn woordenschat is niet toereikend voor een betere formulering.

geeft niet hoor, het zou evengoed spaans voor me zijn denk ik.............

Spaans lijkt me nog eenvoudiger....