mega-compressie - deel 2 -

quote:

Op dinsdag 26 juli 2005 00:36 schreef -erwin- het volgende:

[..]

lossy compression

Maar ik geloof dat uit Sloot zijn "paper" ( ) niet te destilleren valt of hij nu wel of geen lossy compressie gebruikt of niet.

quote:

Op dinsdag 26 juli 2005 00:36 schreef HenryHill het volgende:

[..]

Da's mooi, maar hoe verklaar je dan dat je films kunt downloaden van 700Mb? Zelfs als je 512x384 als resolutie gebruikt dan zit je er nog een paar flinke factors naast...

Bij het comprimeren van films verlies je waanzinnig veel data. Als je een film van 640x480@25fps van 90 minuten verliesloos wil opslaan heb je volgens mij minstens 80 gigabyte ruimte nodig.

quote:

Op dinsdag 26 juli 2005 00:39 schreef HenryHill het volgende:

[..]

Maar ik geloof dat uit Sloot zijn "paper" ( ) niet te destilleren valt of hij nu wel of geen lossy compressie gebruikt of niet.

Hij zei dat ie verliesloos (pixel voor pixel) een film weer kon laten zien

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.

quote:

Op zaterdag 23 juli 2005 13:07 schreef Pietverdriet het volgende:
Maar goed, ik zie eigenlijk alleen maar het herkauwen van de dingen die in de vorige topics al uitvoerig herkauwt zijn.

quote:

Op dinsdag 26 juli 2005 00:36 schreef -erwin- het volgende:
lossy compression

Mja zodra iedereen het hier over eens is kunnen we verder. Dat het wiskundig anders niet kan is al 10.000 keer geschreven op tig manieren. Met lossy compression is wel de vraag hoe de kwaliteit was van de demo.

quote:

Op dinsdag 26 juli 2005 05:34 schreef ACT-F het volgende:
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?

quote:

Op dinsdag 26 juli 2005 10:43 schreef DirtyHarry het volgende:

[..]

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.

quote:

Op dinsdag 26 juli 2005 11:00 schreef BUG80 het volgende:

[..]

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.

quote:

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.

quote:

Op dinsdag 26 juli 2005 11:11 schreef DirtyHarry het volgende:

[..]

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.

quote:

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.

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?

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.

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.

quote:

Op dinsdag 26 juli 2005 11:37 schreef Pinobot het volgende:
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

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 drinken

quote:

Op dinsdag 26 juli 2005 13:36 schreef DirtyHarry het volgende:
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 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?

Laat ik het dan nog eens anders formuleren.

Zolang niet alle mogelijke combinaties gemaakt kunnen worden binnen het bestaan van het heelal, heb je ook niet alle bits nodig die dat kunnen representeren.

Stel dat er uiteindelijk in de hele geschiedenis maar vier films gemaakt worden:

0001
1010
1111
1010

Om deze ongecomprimeerd op te slaan heb je 4 bits nodig. Echter, er is vast wel een algoritme te verzinnen waarmee deze reeksen in maar 2 bits op te slaan zijn (want: er zijn maar 4 mogelijke films gemaakt).

quote:

Op dinsdag 26 juli 2005 13:46 schreef BUG80 het volgende:
Laat ik het dan nog eens anders formuleren.

Zolang niet alle mogelijke combinaties gemaakt kunnen worden binnen het bestaan van het heelal, heb je ook niet alle bits nodig die dat kunnen representeren.

Stel dat er uiteindelijk in de hele geschiedenis maar vier films gemaakt worden:

0001
1010
1111
1010

Om deze ongecomprimeerd op te slaan heb je 4 bits nodig. Echter, er is vast wel een algoritme te verzinnen waarmee deze reeksen in maar 2 bits op te slaan zijn (want: er zijn maar 4 mogelijke films gemaakt).

Ja ok dat klopt Alle mogelijke films zullen kwa aantal makkelijk in die 128 kilobyte passen. Maar dan moet je op de een of andere manier dat algoritme wijs maken welke combinaties niet bestaan en welke wel. En dat lijkt me praktisch gezien vrij lastig

quote:

Op dinsdag 26 juli 2005 14:19 schreef DirtyHarry het volgende:

[..]

Ja ok dat klopt Alle mogelijke films zullen kwa aantal makkelijk in die 128 kilobyte passen. Maar dan moet je op de een of andere manier dat algoritme wijs maken welke combinaties niet bestaan en welke wel. En dat lijkt me praktisch gezien vrij lastig

Inderdaad, zoniet onmogelijk. Dat betekent dat hij één of ander patroon had moeten vinden dat voor alle films geldt.

Ik ben het dus met je eens hoor, ik geloof er niet in, maar wiskundig bewijzen dat het onmogelijk is gaat niet volgens mij.

quote:

Op dinsdag 26 juli 2005 11:11 schreef DirtyHarry het volgende:

[..]

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.
[..]

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.

Compressie is eigenlijk het verkeerde woord, je noteert de getallen op een andere manier en het is van toepassing op elke bitstroom. Meer zeg ik niet

Ik heb het eerste deel van de Netwerk uitzending inmiddels gezien. Jammer dat ze geen sceptici aan het woord laten, het is wel erg eenzijdig zo.

Ik vraag me trouwens al een tijdje af waarom deze vermeende techniek alleen op films werd toegepast door Sloot.

1) Was het een algoritme dat optimaal of alleen maar voor films werkt?
2) Is het omdat dat makkelijker te demonstreren valt (spreekt tot de verbeelding)?
3) Is het omdat je dan makkelijker mensen kan bedriegen? (als je "gewone" of willekeurige bestanden gebruikt, zullen mensen als snel vragen of je ook andere bestande wilt proberen)

quote:

Op dinsdag 26 juli 2005 11:23 schreef BUG80 het volgende:
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?

Er is een verschil tussen nooit een bestand kunnen verkleinen = geen enkel bestand kunnen verkleinen, en niet alle bestanden kunnen verkleinen.
Als je een bestand neemt van bvb 2000 bits, en winzip comprimeert dit tot een bestand van 1024 bits, dan zal winzip dat bestand van 1024 bits niet meer kunnen comprimeren.
Tekstbestanden bijvoorbeeld comprimeren goed omdat tekst veel redundantie bevat.

Nu lijkt het misschien dat je de toch winst maakt met winzip over het totaal van de 2^1024 mogelijke files, omdat je een deel kleiner kunt maken. MAAR: er zullen ook files groter worden!!

vb: ik heb een bitmap X gecromprimeerd met winzip, het resultaat is een file Y van 1.325.093 bytes.
Nu ga ik deze file nog eens comprimeren, resultaat:file Z van 1.325.300 bytes
Waarom is deze file groter geworden? Winzip kan hem niet verder comprimeren, maar hij kan hem ook niet onveranderd laten, want als ik hem dan zou unzippen zou ik de oorspronkelijke bitmap X terugkrijgen en niet file Y.

Nu is winzip niet geoptimaliseerd voor het verwerken van reeds gecomprimeerde files, men zou het algoritme kunnen aanpassen zodat files hoogstens 1 bit groter kunnen worden. Die ene bit zou dan aangeven of het bestand gecomprimeerd is, of het origineel bevat. Blijkt compressie het bestand groter te maken,dan voeg je enkel deze bit toe aan het bestand (je zet een 0 ervoor), in het andere geval zet je een 1 voor het resultaat. Merk op dat hierdoor alle gecomprimeerde bestanden een bit groter worden.

Uiteindelijk, als je alle mogelijke files van 1024 bits comprimeert, dus 1024 * 2^1024 bits aan data, dan zal je als resultaat opnieuw 1024 * 2^1024 bits aan data krijgen. De compressie van een deel van de bestanden wordt gecompenseerd door de extra bit die een ander deel van de bestanden krijgen. (in werkelikheid zal je meer data krijgen dan waar je mee begonnen zijn, omdat winzip oa een CRC waarde toevoegd)

quote:

Op dinsdag 26 juli 2005 13:46 schreef BUG80 het volgende:
Laat ik het dan nog eens anders formuleren.

Zolang niet alle mogelijke combinaties gemaakt kunnen worden binnen het bestaan van het heelal, heb je ook niet alle bits nodig die dat kunnen representeren.

Stel dat er uiteindelijk in de hele geschiedenis maar vier films gemaakt worden:

0001
1010
1111
1010

Om deze ongecomprimeerd op te slaan heb je 4 bits nodig. Echter, er is vast wel een algoritme te verzinnen waarmee deze reeksen in maar 2 bits op te slaan zijn (want: er zijn maar 4 mogelijke films gemaakt).

Als er maar 4 films gemaakt zijn heb je inderdaad maar twee bits nodig om ze op te slaan, ongeacht de grootte van de films. Dit algoritme is eenvoudig, MAAR het data-gedeelte moet de volledige films bevatten!

Als je een compressie-algoritme ontwerpt voor een bepaald type files, dan kan je de compressie verhogen door het algoritme meer data te geven. Voor nederlandse teksten kan je bijv. heel de nederlandse woordenlijst gebruiken, en de woorden volgens een frequentietabel te nummeren. vb: de=001 een=010 het=011 met=1000 van=1001 op=1010 enzovoort. Je bekijkt een hoop texten om de frequentie van elk woord te bepalen, en dan geef je elk woord een unieke code, hoe frequenter het woord voorkomt, hoe korter de code.

Deze methode zal niet werken als je bestanden met willekeurige letterreeksen wil comprimeren, omdat elke combinatie van een gegeven aantal letters even vaak zal voorkomen.

quote:

Op donderdag 28 juli 2005 21:48 schreef Doderok het volgende:
Deze methode zal niet werken als je bestanden met willekeurige letterreeksen wil comprimeren, omdat elke combinatie van een gegeven aantal letters even vaak zal voorkomen.

Klopt, helemaal mee eens, net als je theorie over WinZip in je andere reactie.

Maar stel nou dat films, net als tekst, geen willekeurige tekenreeksen zijn en daadwerkelijk een bepaalde "magische" redundantie bevatten die toch in één algoritme te vangen is.

Het is allemaal hypothetisch, dat is waar. Nogmaals, het enige dat ik probeer aan te tonen, is dat het in mijn ogen niet *wiskundig* te bewijzen is dat de compressie van Sloot onmogelijk is, ook al is het intuitief nog zo onwaarschijnlijk.

quote:

Op dinsdag 26 juli 2005 16:11 schreef ACT-F het volgende:
Compressie is eigenlijk het verkeerde woord, je noteert de getallen op een andere manier en het is van toepassing op elke bitstroom. Meer zeg ik niet

Je hoeft geen verdere details te verklappen, maar het klinkt alsof je iets essentieels over het hoofd ziet. Even om duidelijk te krijgen waar we het over hebben:

- een manier om meer data in dezelfde hoeveelheid bits te kunnen vastleggen, dus dat je bijvoorbeeld een film die uncompressed 150 GB is, kwijt kunt op een flash kaartje van 128 MB? (of zelfs nog kleiner)

- of een manier om fysiek gezien efficiënter data op te slaan, dus een één of ander zelfbedacht opslagmedium met een hogere datadichtheid (meer bits/cm²) dan de huidige harddisks/dvd's/enz ?

Is het lossy of lossless?

En werkt het alleen voor bepaalde soorten data, bijvoorbeeld audiovisuele data (zoals films), of ook voor random data?

Is de methode ook van toepassing op zichzelf? M.a.w. kun je de kleinere bitstream die je volgens jouw idee krijgt (als het resultaat weer een bitstream is althans) zelf ook weer als een normale bitstream interpreteren en die op dezelfde manier "anders noteren"? Zodat je dus dubbele winst krijgt.