mega-compressie - deel 2 -

Heb dat boek (De Broncode) twee maandjes geleden voor 1,5 euro gekocht als afgeschreven boek bij m'n bieb... Raar dat het er toen al lag: in perfecte nieuwstaat en met een voorwoord van augustus 2004.

Hier nog een link naar een ietwat slordig geschreven Word document met daarin een verhaal waarin de auteur probeert uit te leggen dat er een kern van waarheid zou kunnen zitten in de verhalen van Sloot, hoewel hij wel stevig moest hebben overdreven volgens die theorie.

quote:

Op vrijdag 22 juli 2005 16:27 schreef gelly het volgende:
Ja, ik sla namelijk niet de priemgetallen zelf op, alleen het hoeveelste Mersenne priemgetal het is.

Maar wat heeft dat voor zin, dan kun je alleen data (getallen) van precies die vorm compressen, of anders maakt het restant wat je ook nog moet compressen het totaal groter dan het origineel.

quote:

Op vrijdag 22 juli 2005 17:37 schreef gnomaat het volgende:

[..]

Maar wat heeft dat voor zin, dan kun je alleen data (getallen) van precies die vorm compressen, of anders maakt het restant wat je ook nog moet compressen het totaal groter dan het origineel.

Zie mijn voorbeeld.

Het idee is mooi, dat wel.

Misschien had Sloot wel priemwoorden gevonden in plaats van priemgetallen

quote:

Op vrijdag 22 juli 2005 17:01 schreef BUG80 het volgende:
Weet je wat, ik geef even een voorbeeld. Het volgende is een willekeurig bestand van 10 bytes:
[..]

Als ik dit omzet naar (ASCII) getallen wordt het:
[..]

In getallen 0-9 heeft het dus een lengte van 27 bytes. Jouw applet geeft:
[..]

Kortom, hij vergroot het bestand van 10 naar 21 bytes!!

Dat is geen eerlijke vergelijking.
In je eerste stap, als je het omzet naar ASCII, zeg je "dit getal heeft een lengte van 27 bytes". Maar op die manier hangt het van de data af, als er veel bytes met ascii waarde onder de 100 in zitten worden het veelal getallen van 2 decimalen, en veel boven de 100, dan 3.

Je moet het hele bestand als één groot getal zien: 78 + 256*139 + 256²*39 + ... enz

Vervolgens, als hij een getal van 27 decimalen comprimeert naar 21 decimalen, kun je niet zeggen "dat zijn 21 bytes, en da's groter dan 10". Dat getal van 21 decimalen moet je dan weer splitsen in ASCII waarden en die bytes schrijf je weg. Dat zijn er dan veel minder dan 21. Zo begon je tenslotte ook met je oorspronkelijke bestand.

Dus je schrijft een byte weg met de waarde (getal mod 256), en vervolgens deel je het getal door 256 (afronden naar beneden). Dit herhaal je tot je nul overhoudt.

Overigens heeft deze methode van het interpreteren van een bestand als getal nog het probleem dat je geen verschil kunt zien tussen een bestand bestaande uit twee nul-bytes of uit tweehonderd nul-bytes.

quote:

Op vrijdag 22 juli 2005 17:45 schreef gnomaat het volgende:

[..]

Dat is geen eerlijke vergelijking.
In je eerste stap, als je het omzet naar ASCII, zeg je "dit getal heeft een lengte van 27 bytes". Maar op die manier hangt het van de data af, als er veel bytes met ascii waarde onder de 100 in zitten worden het veelal getallen van 2 decimalen, en veel boven de 100, dan 3.

Ik heb dit met een random generator gedaan, het viel toevallig hoog uit. De verwachtingswaarde voor de lengte van een ASCII getal is (100*1 + 100*2 + 56*3)/256 = 1,82 decimalen.

quote:

Vervolgens, als hij een getal van 27 decimalen comprimeert naar 21 decimalen, kun je niet zeggen "dat zijn 21 bytes, en da's groter dan 10". Dat getal van 21 decimalen moet je dan weer splitsen in ASCII waarden en die bytes schrijf je weg. Dat zijn er dan veel minder dan 21. Zo begon je tenslotte ook met je oorspronkelijke bestand.

Dat doet het applet van Gelly ook precies, dus volgens mij is dit wel een eerlijke vergelijking.

edit: Het applet van Gelly schrijft '186' dus weg als 1 ASCII byte i.p.v. "1", "8" en "6".

quote:

Op vrijdag 22 juli 2005 17:49 schreef gelly het volgende:

[..]

Er is geen restant...

Hij bedoelt met restant: alles wat niet in de range 0-9 valt.

quote:

Op vrijdag 22 juli 2005 17:56 schreef gelly het volgende:

[..]

Dat kan omdat dat 'karakter' onderdeel is van een groter getal.

Snap je wat ik bedoel met mijn getallenvoorbeeld? Dat bestand van 10 bytes?

quote:

Op donderdag 21 juli 2005 15:48 schreef Danny het volgende:

[..]

Veel getallen die je niet in 1 notatie samen kunt vatten kun je wellicht wel in meerdere wiskundige notaties samenvatten waar je dan na bewerking (optellen bv) WEL het juiste getal uitkrijgt.
Zelfs al zou je een getal van 20 miljoen cijfers dan moeten opdelen is 10.000 van die korte notaties heb je alsnog van 20Mb 100Kb gemaakt.

hierbij geldt hetzelfde principe als hierboven al aangehaald. ik kan in een paar bytes een heel groot getal produceren, maar ik kan niet in een paar bytes elk groot getal produceren. zoiets valt via relatief eenvoudige logica te bewijzen.

quote:

Op vrijdag 22 juli 2005 15:02 schreef BUG80 het volgende:

[..]

Wat dat betreft ben ik het helemaal met je eens, maar ben jij het met mij eens dat als je in het bezit bent van een soort super database/Huffman tree (die niet bestaat denk ik), het dan wel mogelijk moet zijn om veel verder te comprimeren dan dat, zolang je die database maar apart opslaat.

Klopt. Echter is 4kb daarvoor veel en veel te klein. Zelfs met 1 film kun je door alle scenes in andere volgordes te zetten al bijna genoeg verschillende mogelijkheden produceren om 4kb vol te krijgen. Laat staan dat je alle mogelijke films zou kunnen opslaan op die manier.

Voor mij staan een aantal zaken als een paal boven water.
1. Het is een lossy compressie.
2. 4kb is onmogelijk. Ordes in de tientallen danwel honderden megabytes lijken aannemelijker.
3. De grootte van de data ligt niet vast. Langere film betekent meer data.
4. Het systeem heeft waarschijnlijk nooit bestaan.

quote:

Op vrijdag 22 juli 2005 17:50 schreef BUG80 het volgende:
Ik heb dit met een random generator gedaan, het viel toevallig hoog uit. De verwachtingswaarde voor de lengte van een ASCII getal is (100*1 + 100*2 + 56*3)/256 = 1,82 decimalen.

Okee, dan heb ik twee briljante manieren om files te compressen:

1. Schrijf een bestand 1000 bytes uit als decimalen zoals bovenstaand. Naar verwachting krijg je dan zo'n 1828 decimalen (hangt natuurlijk van je bestand af, maar gemiddeld).
Aangezien je makkelijk 2 decimalen per byte kunt opslaan (dat worden bytes met ascii waarden 0 t/m 99) heb je dus 914 bytes nodig om die decimalen weer op te slaan. Blijft over: 914/1000 = 91%. Dit is recursief toepasbaar.

2. Voordat je dit doet tel je eerst de frequentie van alle bytes. Vervolgens verwissel je de bytes zodat de meest veelvoorkomende bytes de laagste ascii waarden krijgen. Op die manier heb je zoveel mogelijk bytes die zo min mogelijk decimalen kosten. Het verwisselen kost enkel een re-map tabel van 256 bytes, ongeacht hoe groot het bestand.

En, zie je al waar de fout zit?

Gelly, om inzicht te krijgen in het feit dat je methode niet doet wat je claimt stel ik voor dat je een willekeurig inputbestand genereert dat je vervolgens comprimeert met jou methode waarna je het decomprimeert en vergelijkt met het origineel. Kijk dan eens naar de compressie ratio.

quote:

Op vrijdag 22 juli 2005 17:49 schreef gelly het volgende:
Er is geen restant...

Alleen als het precies een groot priemgetal is.
Als de input data bijvoorbeeld 618970019642690137449562111 is, dan kun je volstaan met "89" (omdat 2⁸⁹-1 = dat getal), of zelfs "9" (omdat 2⁸⁹-1 het tiende Mersenne priemgetal is en je begint te tellen vanaf 0).

Maar dat is een zeer uitzonderlijke input. Wat nu als de input bijvoorbeeld 761825315945362690850838009 is?

Oh ja dit klopt trouwens ook niet helemaal:

quote:

Op vrijdag 22 juli 2005 17:50 schreef BUG80 het volgende:
Ik heb dit met een random generator gedaan, het viel toevallig hoog uit. De verwachtingswaarde voor de lengte van een ASCII getal is (100*1 + 100*2 + 56*3)/256 = 1,82 decimalen.

Moet zijn (10*1 + 90*2 + 156*3)/256 = 2.57 decimalen gemiddeld per byte.

Maar dat was niet eens de grootste fout in mijn "briljante" nieuwe compressiemethode van hierboven

quote:

Op vrijdag 22 juli 2005 18:30 schreef gnomaat het volgende:

[..]

Okee, dan heb ik twee briljante manieren om files te compressen:

1. Schrijf een bestand 1000 bytes uit als decimalen zoals bovenstaand. Naar verwachting krijg je dan zo'n 1828 decimalen (hangt natuurlijk van je bestand af, maar gemiddeld).
Aangezien je makkelijk 2 decimalen per byte kunt opslaan (dat worden bytes met ascii waarden 0 t/m 99) heb je dus 914 bytes nodig om die decimalen weer op te slaan. Blijft over: 914/1000 = 91%. Dit is recursief toepasbaar.

2. Voordat je dit doet tel je eerst de frequentie van alle bytes. Vervolgens verwissel je de bytes zodat de meest veelvoorkomende bytes de laagste ascii waarden krijgen. Op die manier heb je zoveel mogelijk bytes die zo min mogelijk decimalen kosten. Het verwisselen kost enkel een re-map tabel van 256 bytes, ongeacht hoe groot het bestand.

En, zie je al waar de fout zit?

Ehh nee. Volgens mij heb je zojuist gewoon een eerste opzet voor een Huffman tree ontworpen, alleen dan met behulp van bytes ipv bits _{of ik mis iets}

En inderdaad de verwachtingswaarde voor de lengte in decimalen van een ASCII waarde is 2.57, mijn fout, sorry

[edit]Methode 1 vervalt dus al, aangezien gemiddeld genomen je bestanden groter worden met deze methode. Je bestand van 1000 bytes worden 2570 decimalen. Dit gedeeld door 2 = 1285[/edit]

Waar het verhaal van Gelly fout gaat is het volgende: hij comprimeert decimalen terug naar bytes met behulp van ontbinding in priemgetallen, in plaats van bytes naar bytes, wat veel eerlijker zou zijn. Dat is wat ik probeer duidelijk te maken.

[ Bericht 5% gewijzigd door BUG80 op 22-07-2005 19:13:49 ]

Probeer anders eens het volgende bestand te comprimeren met behulp van de methode van Gelly, je zult zien dat het groter wordt:

quote:

x6YNsgK#mJ

Ik heb expres 'leesbare' karakters gebruikt. Succes.

quote:

Op vrijdag 22 juli 2005 18:45 schreef gnomaat het volgende:

[..]

Alleen als het precies een groot priemgetal is.
Als de input data bijvoorbeeld 618970019642690137449562111 is, dan kun je volstaan met "89" (omdat 2⁸⁹-1 = dat getal), of zelfs "9" (omdat 2⁸⁹-1 het tiende Mersenne priemgetal is en je begint te tellen vanaf 0).

Maar dat is een zeer uitzonderlijke input. Wat nu als de input bijvoorbeeld 761825315945362690850838009 is?

Nogmaals, volgens mij bedoelde hij niet restant als in "modulo", maar het restant als je alleen de decimalen in een bestand comprimeert. Een gemiddeld bestand bestaat namelijk uit veel meer dan alleen decimalen.

Gelly, please

Je vergelijkt appels met peren. Je begint met decimalen met een bandbreedte van 0-9, die je vervolgens ontbindt in priemgetallen, die je opslaat als bytes in bandbreedte 0-255. Vind je het gek dat je compressie bereikt.

Neem het volgende getal (lengte 22 decimalen):

quote:

1792873102928338392382

Jouw applet maakt daar 16 priemgetallen van, die je opslaat als bytes met waarde 0-255. Met de hand kan ik er echter ook bytes van maken:

179 28 73 102 92 83 38 39 238 2

Nou zijn het er ineens nog maar 10! Kortom met de hand bereik ik meer compressie dan met jouw methode!

quote:

Op vrijdag 22 juli 2005 19:35 schreef gelly het volgende:
Dit is ook een ruwe opzet hoor, ben nog druk bezig te kijken wat het beste werkt. Je kunt je voorstellen dat je door het scannen van datareeksen getallen tegenkomt die je door een veel kortere notatie kunt vervangen. Een combinatie van verschillende logaritmen moet zeker een forse compressie oplever mijns inziens.

Gemiddeld levert dat minder winst op dan de extra ruimte die het je kost om de metadata voor zo'n notatie op te slaan. Ongeacht je methode of het type korte notatie dat je gebruikt.

Maar goed, mijn challenge staat nog steeds, werk je idee gerust uit. Als je een appje weet te bakken dat mijn 10KB bestand onder de 9 KB krijgt (dus een file van maximaal 9216 bytes) dan

quote:

Op vrijdag 22 juli 2005 18:30 schreef gnomaat het volgende:
En, zie je al waar de fout zit?

gnomaat, kun je deze vraag nog even beantwoorden?

quote:

Op vrijdag 22 juli 2005 20:22 schreef BUG80 het volgende:
gnomaat, kun je deze vraag nog even beantwoorden?

Hint: als het decimale getal 112131032202120121 is, van welke ascii waardes komt dat dan? (m.a.w. welke originele file hoort hierbij?)