Tiberius schreef: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.
Gian schreef: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.
wim schreef: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".
wim schreef: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.
wim schreef: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.
wim schreef:
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.
wim schreef:
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.
wim schreef: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.
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.
Jongere schreef:Ik snap er geen byte van.
Iedereen zo zijn vak.
parsifal schreef: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.
GAB schreef: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 ![:P](./images/smilies/langue2.gif)
)
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
![:P](./images/smilies/langue2.gif)
Klinkt goed.
![:)](./images/smilies/smile.gif)
Ik zou zeggen: vraag wat je nodig hebt en eventueel kun ik de sourcecode delen.
memento schreef: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.
parsifal schreef: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.