Het compressiegeheim van Jan Sloot ontrafeld

Het compressiegeheim van Jan Sloot ontrafeld

Re: Het compressiegeheim van Jan Sloot ontrafeld

Berichtdoor Michael1954 » zo 17 okt 2010, 08:24

From: Lampje74

vooruit ik wilde het toch onder GPL licentie zetten. dus bij deze is onderstaande info vallend onder GPL...

Het idee is om een veld van X*Y te vullen met bytes. Door deze velden per rij, kolom en de 2 diagonaal richtingen op te tellen komt er een waarde uit welke kleiner is (byte wise) dan de originele reeks. met 32bit (4byte) kan je tot 16,...miljoen tellen. om daar te komen met het op tellen van een reeks bytes kan je met een gerust hart een veld van 1024*1024 maken.
Als voorbeeld.. 8 bits leverdt max 255 (decimaal)op. 2 bytes opgeteld leverdt 510 en dat past in 9 bit. in 10 bit past 4byte. enz.
Ivm magische vierkanten kan je ipv een vierkant veld ook een rechthoekig veld opgeven, scheeld iets.
dus in een veld van 256*256 bytes gaat die 65K aan data in. en komt er 4096byte uit. (256*4richtingen)*4byte. ok. had ik dus een klein rekenfoutje in excel.. met overhead ff over de 5KB.
Omdat ik op byte nivo werk maakt het eigenlijk niet uit wat voor data er in het in te pakken bestand staat. En je verwerkt net zo veel velden als nodig is om het gehele bestand ingelezen te hebben. Hierbij zal in het laatste veld een deel gevuld worden met 0 als waarde. Daar je de uitkomsten e.d. ook weer als bytes kan inlezen kan je het resultaat van de eerste verwerkings ronde nog (meer) maals inlezen en inpakken. beetje als een zip in een zip in een zip bestand, waarbij het bij zip niet kleiner wordt maar hier het resultaat wel.
Het uitpakken doe je (brute force) door de resultaat waardes langs de kanten van het veld te zetten en dan het veld net zo lang invullen/muteren tot je bij het optellen van de velden op de resultaten komt. Presto...

Duidelijk?
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Het compressiegeheim van Jan Sloot ontrafeld

Berichtdoor Michael1954 » zo 17 okt 2010, 08:28

From: Anonymous Coward

Het idee is om een veld van X*Y te vullen met bytes. Door deze velden per rij, kolom en de 2 diagonaal richtingen op te tellen komt er een waarde uit welke kleiner is (byte wise) dan de originele reeks. met 32bit (4byte) kan je tot 16,...miljoen tellen. om daar te komen met het op tellen van een reeks bytes kan je met een gerust hart een veld van 1024*1024 maken.
Als voorbeeld.. 8 bits leverdt max 255 (decimaal)op. 2 bytes opgeteld leverdt 510 en dat past in 9 bit. in 10 bit past 4byte. enz.
Ivm magische vierkanten kan je ipv een vierkant veld ook een rechthoekig veld opgeven, scheeld iets.
dus in een veld van 256*256 bytes gaat die 65K aan data in. en komt er 4096byte uit. (256*4richtingen)*4byte. ok. had ik dus een klein rekenfoutje in excel.. met overhead ff over de 5KB.

Ah ok. Stel ik neem een bestand van 16 bytes als voorbeeld. Dan zou ik die 16 bytes in een vierkant van 4 bij 4 moeten zetten. De rijen, kolommen en diagonallen tel ik dan op. En die 10 waardes (4 rijen, 4 kolommen en 2 diagonalen) sla ik dan op?

De som van 4 bytes past in 10 bits. Dus mijn originele bestand was 16*8 = 128 bits en packed gaat dat dus naar 10*10=100 bits. En 100 is minder dan 128 dus we hebben het ingepakt. Dat is voor een bestand van 16 bytes. Voor grotere bestanden is de ratio veel hoger, dat snap ik.

Het probleem is dat er in die 100 bits die je opslaat niet genoeg informatie aanwezig is om de originele 128 bits terug te krijgen. Er zijn 2^100 bestanden van 100 bits en 2^128 bestanden van 128 bits. Het is dus onvermijdelijk, helaas, dat er meerdere 128 bits bestanden verwijzen naar hetzelfde packed bestand van 100 bits.

Laat ik een weinig origineel voorbeeld geven. Beschouw het volgende bestand van 16 bytes:

1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16

Niet bijster origineel en even gewoon in decimale notatie opgeschreven voor het gemak. Deze zet ik dan dus zo in een vierkant:

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

De rijen optellen geeft: 10, 26, 42 en 58. De kolommen optellen geeft: 28, 32 36 en 40. Voor beide diagonalen krijg ik dan 34.

De compressie verloopt dus als volgt:

1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16 -> 10-26-42-58-28-32-36-40-34-34

Dat ziet er nog allemaal goed uit toch?

Nu een ander voorbeeld. Een ander bestand van 16 bytes:

2-3-2-3-4-5-8-9-9-10-11-12-13-14-15-16

Krijgen we dit vierkant:

2 3 2 3
4 5 8 9
9 10 11 12
13 14 15 16

De rijen optellen geeft: 10, 26, 42 en 58. De kolommen optellen geeft: 28, 32 36 en 40. Voor beide diagonalen krijg ik dan 34. Valt je iets op:

2-3-2-3-4-5-8-9-9-10-11-12-13-14-15-16 -> 10-26-42-58-28-32-36-40-34-34

Nog een voorbeeld:

3-4-1-2-3-4-9-10-9-10-11-12-13-14-15-16 -> 10-26-42-58-28-32-36-40-34-34

Dit is het grote probleem van jouw methode. Een bepaald packed bestand kun je op meerdere manieren uitpakken. Dit probleem gaat niet alleen voor jouw methode op, het is fundamenteel. En onoplosbaar. Het is dezelfde getalsmatige realiteit waar Sloot tegenaan was gelopen.
Omdat ik op byte nivo werk maakt het eigenlijk niet uit wat voor data er in het in te pakken bestand staat. En je verwerkt net zo veel velden als nodig is om het gehele bestand ingelezen te hebben. Hierbij zal in het laatste veld een deel gevuld worden met 0 als waarde.Daar je de uitkomsten e.d. ook weer als bytes kan inlezen kan je het resultaat van de eerste verwerkings ronde nog (meer) maals inlezen en inpakken.

Dan zou jouw methode nog beter zijn dan die van sloot. Je begint met een film van tig gigabyte, die zet je in een heel groot vierkant. Het packed bestand zet je in een kleiner vierkant en zo verder net zolang totdat je bij een 4x4 vierkant uitkomt. Dat zou je een hele film in 100 bits kunnen comprimeren. Jammer dat het niet werkt, anders waren die miljarden die Pieper aan het eind van de regenboog zag nu voor jou geweest...
beetje als een zip in een zip in een zip bestand, waarbij het bij zip niet kleiner wordt maar hier het resultaat wel.
Het uitpakken doe je (brute force) door de resultaat waardes langs de kanten van het veld te zetten en dan het veld net zo lang invullen/muteren tot je bij het optellen van de velden op de resultaten komt.

Hehe nu snap ik dat het uitpakken van het bestand zo lang moet duren. Als een bestand, dat origineel zeg 1 gb was, zou willen uitpakken moet je alle bestanden van 1 gb gaan aflopen. Dat hoeft niet met brute-force, je kunt veel sneller een origineel vinden. Het grote probleem is dat je dus een heleboel originelen zult vinden.
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Het compressiegeheim van Jan Sloot ontrafeld

Berichtdoor Michael1954 » zo 17 okt 2010, 08:29

From: Bolleke

Het grote probleem is dat je dus een heleboel originelen zult vinden.

Damn, je was me voor omdat ik nog op jou aan het reageren was :)

De omschreven methode zou eventueel kunnen werken als je ook bijhoudt wat voor /soort/ bestand het is. Immers, niet elke binaire blob is bv een geldige MP3. Maar dan nog gaat het maar tot een bepaalde grootte goed, want vanaf een x aantal bytes krijg je vanzelf meerdere geldige MP3s. En het uitpakken, tja, dat is een issue. Je zou daarbij al rekening moeten houden met het soort bestand, maar dan moet je dus in je programma allerlei codecs gaan inbouwen wat ook niet praktisch is. Maar ik denk dat het /in theorie/ nog wel tot op zekere hoogte zou kunnen. Zeker als je bv. samen met het gecomprimeerde bestand een checksum levert waar het uitgepakte bestand aan moet voldoen. Het is wel zo dat het met de huidige rekenkracht van de gemiddelde PC niet per se meer een gigantisch probleem hoeft te zijn om zoiets uit te pakken als je de niet-ter-zake-doende mogelijkheden eruit filtert. Het voorbeeld van Alon kun je zo nooit inpakken omdat het betekenisloze getallen zijn, maar als je een educated guess kunt maken over het eindresultaat...

Stel je downloadt zo een (kleine) film en je krijgt 16 mogelijke resultaten na decompressie. Er zal er maar 1 afspelen via een player, de rest is garbage... ik vind het idee niet eens zo gek, maar er zijn wel wat praktische bezwaren en daarnaast heb ik al bier op ;)
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Het compressiegeheim van Jan Sloot ontrafeld

Berichtdoor Michael1954 » zo 17 okt 2010, 08:30

From: Lampje74

Je mist nog een paar diagonalen... in je 1/6 vierkant heb je de diagonalen:
1-6-11-16
2-7-12-13
3-8-9-14
4-5-10-15
en de andere richting
1-8-11-14
2-5-12-15
3-6-9-16
4-7-10-13

Verder is het NIET de bedoeling het hele bestand in 1 'op maat' veld te zetten maar in een reeks behapbare velden. Ik ben op de hoogte van het probleem dat er mogenlijk meerdere veld vullingen zijn die in de 4 tel richtingen gelijke waardes op leveren. E.e.a. kan (deels) worden opgelost door een reeks seeds toe te voegen. Maar dan moet je bij de decompressie in de gaten houden of en veld lokatie een seed is of niet. dit kost dus een extra controle regel op je veld, en je veld wordt dan een record met daar in de veld waarde en de true/false van de seed. een seed mag je immers niet muteren.

Ik sla de som van de telrichting op. het maakt dus niet uit hoe vaak welk caracter voor komt.

Een methode om te checken of dit systeem werkt kan je natuurlijk een reeks eind waardes nemen (veld uitrekenen) en vervolgens het veld uitpakken. en gewoon door blijven gaan na het vinden van een oplossing om te zien of de decomressor nog meerdere oplossingen vind.
Mocht je meerdere oplossingen vinden is de methode inderdaad gefaald.... MAAR je kan dan evt kijken welke van de uitkomsten overeenkomt met de input. en dan ook die waarde (bv 4e oplossing) opslaan. en dan bij het uiteindelijke echte uitpakken dus doorgaan tot de 4e oplossing... PRESTO :)

Om mijn systeem te bewijsen is dan dus ook een goed bruikbaar (lees efficient) decompressie methode, anders dan brute-force, handig. Brute force duurt wat lang om een 64*64 veld na te rekenen...
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Het compressiegeheim van Jan Sloot ontrafeld

Berichtdoor Michael1954 » zo 17 okt 2010, 08:33

From: Anonymous Coward

Je mist nog een paar diagonalen...

Ok ik begrijp het. Daar los je het fundamentele probleem helaas niet mee op.
Verder is het NIET de bedoeling het hele bestand in 1 'op maat' veld te zetten maar in een reeks behapbare velden.

Dat begrijp ik, maar het is even makkelijk voor de voorbeeldjes om daar vanuit te gaan.
Ik ben op de hoogte van het probleem dat er mogenlijk meerdere veld vullingen zijn die in de 4 tel richtingen gelijke waardes op leveren. E.e.a. kan (deels) worden opgelost door een reeks seeds toe te voegen.

Nee dat kan niet. Dat probleem is onoplosbaar. De enigste manier dat je dat zou kunnen oplossen is door zoveel waarden of seeds op te slaan dat je packed bestand net zo groot is als je origineel (of groter).
Mocht je meerdere oplossingen vinden is de methode inderdaad gefaald.... MAAR je kan dan evt kijken welke van de uitkomsten overeenkomt met de input. en dan ook die waarde (bv 4e oplossing) opslaan. en dan bij het uiteindelijke echte uitpakken dus doorgaan tot de 4e oplossing... PRESTO :)

Nee dat werkt ook niet. Je moet dan net zolang extra informatie opslaan totdat je packed bestand niet meer kleiner is dan het origineel.
Om mijn systeem te bewijsen is dan dus ook een goed bruikbaar (lees efficient) decompressie methode, anders dan brute-force, handig. Brute force duurt wat lang om een 64*64 veld na te rekenen...

Voor een 64*64 veld sla je als ik het goed heb 4*64 waarden op in je packed file. Om van je packed file naar het origineel terug te gaan moet je dan 64*64 onbekenden vinden en om dat te doen heb 4*64 vergelijkingen. Dat wil zeggen dat je 4*60 posities moet gokken en op basis van die gok de rest kunt berekenen. Even voor de duidelijke, dit wil zeggen dat je 4*60 verschillende oplossingen per packed file krijgt (alhoewel dit niet allemaal natuurlijke getallen tussen de 0 en 256 hoeven te zijn).

Ik heb trouwens nog een aardige link met informatie voor je gevonden: http://www.faqs.org/faqs/compression-faq/part1/
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Het compressiegeheim van Jan Sloot ontrafeld

Berichtdoor Michael1954 » zo 17 okt 2010, 08:35

From: Lampje74

Gewoon proberen. zoveel tijd kost het ook weer niet om e.e.a. te testen. en wie weet...
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Het compressiegeheim van Jan Sloot ontrafeld

Berichtdoor Michael1954 » zo 17 okt 2010, 08:35

From: Anonymous Coward

Ik weet. Het gaat niet werken.
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Het compressiegeheim van Jan Sloot ontrafeld

Berichtdoor Michael1954 » zo 17 okt 2010, 08:36

From: Grr

Het probleem van de (te) vele mogelijke originelen wat naar voren komt in de heldere beschouwing van Alon doet mij denken aan de tekst compressie die de assyriers lang geleden al bedacht zouden hebben: zij lieten alle klinkers weg in een tekst. Ik heb het wel eens geprobeerd met wat eigentijdse teksten. Het levert je een hoop rimpels in je voorhoofd op maar soms kun je de tekst nog aardig lezen omdat je brein op zoek naar betekenis en contekst bij het lezen braaf meerekent. De excercitie bezorgde mij wel het zuiver intuitieve gevoel dat een compressie van een factor 2 heel gemiddeld wel eens een heel ruwe limiet zou kunnen zijn. Zo zouden de historici met het probleem zitten dat ze niet goed weten hoe de koning van de assyriers heette. Zijn naam was Nbkdnsr en men was er niet over uit of dat voor bijvoorbeeld Nabukodonosor of Nebukadnezar stond.

Overigens staat mij dit verhaal over de assyriers en hun koning bij uit mijn lagere schooltijd dus ik weet niet in hoeverre het apocrief is. Illustratief vind ik het in elk geval wel.
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Het compressiegeheim van Jan Sloot ontrafeld

Berichtdoor Michael1954 » zo 17 okt 2010, 08:37

From: Anonymous Coward

Ik heb het wel eens geprobeerd met wat eigentijdse teksten. Het levert je een hoop rimpels in je voorhoofd op maar soms kun je de tekst nog aardig lezen omdat je brein op zoek naar betekenis en contekst bij het lezen braaf meerekent.

Ja, ik weet ook dat er behoorlijk wat psychologen onderzoek doen daar dit soort verschijnselen. Het blijkt dat er in een opgeschreven woord veel informatie redundant is en onze hersenen daar gebruik van kunnen maken als, bijvoorbeeld, de spelling niet correct is (of letters ontbreken) van een woord.
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Het compressiegeheim van Jan Sloot ontrafeld

Berichtdoor Michael1954 » zo 17 okt 2010, 08:38

From: Bolleke

Daar je de uitkomsten e.d. ook weer als bytes kan inlezen kan je het resultaat van de eerste verwerkings ronde nog (meer) maals inlezen en inpakken. beetje als een zip in een zip in een zip bestand, waarbij het bij zip niet kleiner wordt maar hier het resultaat wel.

Nou, ik ben inmiddels wat helderder en die 2e inpakronde gaat natuurlijk sowieso niet werken omdat je data dan echt willekeurig wordt (die opmerking had ik ff gemist). Daarnaast moet je van elke rij en elke kolom bijhouden wat het totaal is om het vierkant te kunnen reconstrueren (bij 256x256 gaat dat dus niet om 4 checksums maar om 514) en dat getal loopt evenredig op met de grootte van je vierkant. Dan nog zou het kunnen dat je voor niet-willekeurige data het aantal eindresultaten zodanig weet te beperken dat het enigzins efficient te krijgen is, maar daar zou ik meer onderzoek naar moeten doen. Mijn gut feeling zegt dat het toch nooit gaat werken, anders had dit vast al bestaan ;-) In feite stuur je een hash (CRC, MD5, SHA-1, welk type maakt niet zoveel uit) incl. originele afmetingen en gaat vervolgens alle mogelijkheden af tot je een match vindt. Interessant zou zijn uit te rekenen hoeveel matches dat voor welke bestandgrootte oplevert; daar moet een formule van te brouwen zijn :-)
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

VorigeVolgende

Keer terug naar WebWereld (0808)