Mega-Compressie (Deel 2)

[Michael1954]

From: DirtyHarry

ACT-F schreef:
Dit fenomeen houdt me al bezig sinds 1994/95. Pas dit jaar heb ik van iemand die ik slechts één dag kende voor het eerst gehoord dat er nog iemand was die dit ook daadwerkelijk uitgevonden had, maar dat de broncode zoek was. Roel Pieper was in het spel. Sinds slechts enkele weken weet ik dat datgene waar ik al jaren over zit te piekeren, wellicht is uitgevonden door een zekere Jan Sloot. In al die jaren heb ik één ding altijd zeker geweten; de algoritme is kinderljk eenvoudig, maar je moet net weten hoe het in elkaar steekt. Toen ik de verhalen las over Jan Sloot ben ik best wel geschrokken van de overeenkomsten. Ook hij was als de dood over het feit dat zijn algoritme uit zou lekken, voordat deze beschermd was, omdat deze kinderlijk eenvoudig is. Bovendien heeft Jan Sloot een electro achtergrond, net als ik. En laat ik nu tijdens mijn MTS periode (1994/95 dus) tijdens de les op het zelfde idee gekomen zijn om getallen reeksen te reduceren, toen een leraar een bepaalde techniek aan het uitleggen was. Hmmm.

Vreemd toch, dat meedere mensen hetzelfde proberen uit te vinden en dan tot de ontdekking komen dat iemand anders wellicht de uitvinding gedaan heeft die jij hebt willen doen. De overeenkomsten zijn zo sterk, waardoor ik zeker weet dat Jan Sloot's algoritme werkt. Wat het is weet ik ook niet, maar ik weet in welke richting ik zoeken moet.

Interessant, maar hoe verklaar jij dan dat het wiskundig gezien onmogelijk is om films verliesloos op te slaan in een sleutel met zo'n kleine opslagcapaciteit?
En in welke richting zouden we dan moeten denken wat betreft de werking van dat algoritme?

[Michael1954]

From: BUG80

DirtyHarry schreef:
[..]
Interessant, maar hoe verklaar jij dan dat het wiskundig gezien onmogelijk is om films verliesloos op te slaan in een sleutel met zo'n kleine opslagcapaciteit?
En in welke richting zouden we dan moeten denken wat betreft de werking van dat algoritme?

Je bewijs is een beetje dubieus. Met hetzelfde bewijs kun je namelijk wiskundig aantonen dat 700 MB niet genoeg is, terwijl we allemaal weten dat dat wél zo is.

Theoretisch is het mogelijk, aangezien het aantal mogelijke permutaties dat je kunt maken met 32768 bits hoger is dan het aantal films dat ooit gemaakt zal worden. Praktisch haalbaar is een ander verhaal.

[Michael1954]

From: DirtyHarry

BUG80 schreef:
[..]
Je bewijs is een beetje dubieus. Met hetzelfde bewijs kun je namelijk wiskundig aantonen dat 700 MB niet genoeg is, terwijl we allemaal weten dat dat wél zo is.

Er is daarna al gezegd dat dat komt omdat er enorm veel lossy compressie is om een film naar 700MB te comprimeren. De clue is volgens mij nog altijd dat sloot beweerde het verliesloos te kunnen.

Theoretisch is het mogelijk, aangezien het aantal mogelijke permutaties dat je kunt maken met 32768 bits hoger is dan het aantal films dat ooit gemaakt zal worden. Praktisch haalbaar is een ander verhaal.

Het aantal mogelijke films is zo ontzettend veel groter dan het aantal mogelijke permutaties dat je kunt maken met die 32768 bits. Niet dat er zoveel films zullen worden gemaakt, maar in principe zouden alle mogelijke films die kunnen worden gemaakt met zijn algoritme in zo'n sleutel moeten passen. Nou dat past dus never nooit niet.

[Michael1954]

From: BUG80

DirtyHarry schreef:
[..]
Er is daarna al gezegd dat dat komt omdat er enorm veel lossy compressie is om een film naar 700MB te comprimeren. De clue is volgens mij nog altijd dat sloot beweerde het verliesloos te kunnen.

Ik bedoel alleen maar dat je bewijs geen bewijs is. Je zegt het volgende:

2^2663552000000 >> 2^32768, dus het is niet mogelijk.

Dan zeg ik, in 700 MB zitten 5872025600 bits.

2^2663552000000 >> 2^5872025600, dus ook niet mogelijk.

Je bewijs is niet sluitend. Het is intuitief, maar niet wiskundig. edit: Of het lossy of lossless is maakt niet uit.

Het aantal mogelijke films is zo ontzettend veel groter dan het aantal mogelijke permutaties dat je kunt maken met die 32768 bits. Niet dat er zoveel films zullen worden gemaakt, maar in principe zouden alle mogelijke films die kunnen worden gemaakt met zijn algoritme in zo'n sleutel moeten passen. Nou dat past dus never nooit niet.

2^32768 is megagroot, probeer het maar eens te berekenen. Zoveel films zullen er in het bestaan van het heelal nooit gemaakt worden. Het enige probleem is, dat je op een gegeven moment 1 mogelijke permutatie per film krijgt. Dat is praktisch onmogelijk te realiseren. Het is alleen niet te bewijzen dat het niet kan.

[Michael1954]

From: BUG80

Oja, nog een kleine toevoeging. Met jouw bewijs kun je ook aantonen dat je met WinZip nooit een bestand kunt verkleinen.

Immers, met 1024 bits kun je 2^1024 mogelijke bestanden maken, dat kun je dus nooit verkleinen naar 512 bits, bijvoorbeeld.

Snap je nu mijn probleem met jouw verhaal?

[Michael1954]

From: Pinobot

Het probleem met het sloot verhaal is niet zozeer of het wel of niet mogelijk is maar dat ie het deed op een Pentium 2 laptop.

[Michael1954]

From: BUG80

Ik heb trouwens een keer een gastcollege gehad van Roel Pieper, waarin hij maar bleef hameren op het feit dat je als ondernemer risico's moet durven nemen om verder te komen. Ik geloof dat hij zoiets zei als "9 op de 10 investeringen worden een grote flop, maar het gaat om die ene die wél een succes wordt".

Het zou heel goed kunnen dat Pieper ook sceptisch was over de vinding van Sloot, maar in het kader van zijn investeringstheorie nam hij het risico om er een paar miljoen in te steken.

[Michael1954]

From: LivEliveD

Pinobot schreef:
Het probleem met het sloot verhaal is niet zozeer of het wel of niet mogelijk is maar dat ie het deed op een Pentium 2 laptop.

Neuh

[Michael1954]

From: DirtyHarry

BUG80
Gegeven de volgende simpele situatie:
Een plaatje van 2x2 pixels met voor elke pixel de waarde zwart of wit. Het totaal aantal mogelijke plaatjes wat je in dit geval kan creeeren is 2^2x2 = 2⁴, mee eens?
Nou mag jij voor mij vertellen wat de kortst mogelijke sleutel is waarmee je alle mogelijke plaatjes mee weet te katalogiseren. (ik heb het nog niet eens over het genereren van het plaatje uit een unieke sleutel)

Ik ga ondertussen koffie drinken

[Michael1954]

From: BUG80

DirtyHarry schreef:
BUG80
Gegeven de volgende simpele situatie:
Een plaatje van 2x2 pixels met voor elke pixel de waarde zwart of wit. Het totaal aantal mogelijke plaatjes wat je in dit geval kan creeeren is 2^2x2 = 2⁴, mee eens?
Nou mag jij voor mij vertellen wat de kortst mogelijke sleutel is waarmee je alle mogelijke plaatjes mee weet te katalogiseren. (ik heb het nog niet eens over het genereren van het plaatje uit een unieke sleutel)

Ik ga ondertussen koffie drinken

Ja ik snap wel wat je bedoelt. Je gaat er in je redenering alleen van uit dat je eventuele redundantie niet uit de data kunt halen. Nogmaals, hoe denk je dat WinZip werkt? Dat gaat toch ook tegen jouw principe in, dat je minstens het aantal bits nodig hebt dat elke mogelijke combinatie kan representeren?