mega-compressie - deel 2 -

quote:

Op vrijdag 22 juli 2005 14:34 schreef BUG80 het volgende:

[..]

Ja inderdaad. Zip doet dat natuurlijk ook, maar die slaat de tree op bij de data, omdat elk bestand zijn eigen optimale tree heeft. Maar stel nu dat Sloot een tree heeft gevonden van bijvoorbeeld 1 GB die voor alle films goed werkt. Onwaarschijnlijk, maar stel.

quote:

Op vrijdag 22 juli 2005 14:12 schreef BUG80 het volgende:
Kijk, ik zie het verschil tussen 750 MB en 4 kB niet zo

quote:

Op vrijdag 22 juli 2005 14:42 schreef gelly het volgende:

Dat is net zo waarschijnlijk als in kladblok wat letters neerplempen, het door een compiler halen en dan windows XP nagemaakt hebben.

quote:

Je hoeft de data enkel te omschrijven, niet te comprimeren. 2^256 Geeft een enorm groot getal, maar is dus ook met 5 chars te beschrijven.

quote:

Op vrijdag 22 juli 2005 14:19 schreef Pietverdriet het volgende:

[..]

Hoe meer je comprimeert, hoe meer info je verliest.

quote:

Op vrijdag 22 juli 2005 14:31 schreef Pietverdriet het volgende:

[..]

dat is dan eigenlijk geen compressie maar de informatie ergens anders neerleggen.

quote:

Op vrijdag 22 juli 2005 14:51 schreef gnomaat het volgende:

[..]

Waar je naar moet kijken is de entropie of het data "gewicht" van een bestand. Een uncompressed film is een dikke 150 GB. Hier zit natuurlijk ontzettend vele redundancy in, zodat je de essentie van die content ook wel in 700 MB (minder dan een half % van het origineel) kwijt kunt. Maar daar zit natuurlijk een grens aan.

Waar die grens ligt hangt van de film af (en wat je nog als acceptabele losses beschouwt), maar voor een normale gemiddelde speelfilm zal die grens onder de 700 MB maar ver boven de 4 KB liggen. 4KB gewoon te weinig. Het is vast wel wiskundig te bewijzen met Shannon ondergrenzen e.d. maar bovendien voel je gewoon op je klompen aan dat 4096 bytes gewoon te weinig zijn om een film te representeren (ik wel althans).

quote:

Op vrijdag 22 juli 2005 14:57 schreef Kaalhei het volgende:

[..]

Dan heb je maar 1 bit nodig voor de Matrix op I-max. Staat de bit op 0 dan gebeurt er niets, zet je de bit op 1 dan kijk je naar de sleutel. De sleutel is dan vervolgens de film van een paar gigabyte.

quote:

Op vrijdag 22 juli 2005 15:02 schreef BUG80 het volgende:
Het blijft natuurlijk theoretisch gewauwel, maar 60 jaar geleden geloofde ook niemand dat je muziek op kon slaan op 1/7 van de grootte, zonder perceptioneel verlies. Zeg nooit nooit!

quote:

Op vrijdag 22 juli 2005 15:05 schreef SunChaser het volgende:
Waar hebben jullie allemaal gestudeerd In mijn tijd kregen we gewoon economie en geschiedenis over Willem van Oranje op school

quote:

Op vrijdag 22 juli 2005 15:06 schreef Pietverdriet het volgende:

[..]

De wet van Shannon is uit 1948..

quote:

Op vrijdag 22 juli 2005 15:08 schreef Pietverdriet het volgende:

[..]

Das best pittig voor de kappersschool, niet?

quote:

Op vrijdag 22 juli 2005 15:13 schreef SunChaser het volgende:

[..]

Och... Je hebt soms mensen die een Balthazar Gerards kapsel willen

quote:

Op vrijdag 22 juli 2005 15:20 schreef gelly het volgende:
Overigens heb ik nu even 'snel' een applet geschreven die mijn compressiemethode simpel laat zien, ik zal hem even ergens parkeren.

quote:

Op vrijdag 22 juli 2005 15:54 schreef gelly het volgende:

[..]

Hold your horses Het is een applet om te laten zien dat compressie van meer dan 50% mogelijk is en dat die compressie toeneemt naarmate het te coderen getal groter wordt...

Ik zoek alleen even een webspace om de boel te dumpen, ben het wachtwoord van de mijne kwijt...

quote:

Op vrijdag 22 juli 2005 16:15 schreef gelly het volgende:
http://www.free-space.us/primer/Applet1.html

Je kunt deze applet beter in een standalone viewer bekijken, zowel firefox als IE zweten nogal als het ingegeven getal erg groot wordt. Het loopt niet vast, al lijkt het wel zo.

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.

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.

quote:

Op vrijdag 22 juli 2005 16:42 schreef gelly het volgende:

[..]

Klopt, daarom werkt het ook niet bij kleine getallen, nou ja het werkt wel maar er is verlies. Ik gebruik enorm grote priemgetallen die in kleine notatie worden weergegeven. Test het maar in de applet, je zal zien dat hoe groter de getallen worden hoe groter de compressie wordt.

quote:

Op vrijdag 22 juli 2005 16:37 schreef XoxIx het volgende:

[..]

Je rekent niet correct. Je input mag maar 10 verschillende waarden hebben (0..9), maar het rangnummer van je priemgetal kan best 1.000.000 zijn (dus 1 miljoen verschillende waarden).

Als je het goed wilt doen moet je dus berekenen hoe lang de decimale representatie is van je priemgetallen. Bijvoorbeeld:

121 = 101 + 19 + 2
Dat wordt niet: 3 voor 3 met geen compressie, maar 6 voor 3 is 100% verlies.

Zelfs nu wordt er nog wat gesjoemeld, maar niet meer zo erg als dat in het applet gebeurt.

quote:

Op vrijdag 22 juli 2005 16:48 schreef gelly het volgende:

[..]

Ik kan elk gebruikt priemgetal opslaan in 1 byte, dus waarom zou ik daar rekening mee moeten houden ? Het integere getal dat je ingeeft is in feite de integere weergave van data. Het is niet zo dat dat getal in een bestand komt te staan.

quote:

Op vrijdag 22 juli 2005 16:51 schreef gelly het volgende:

[..]

Uhm nee. Ik kan met een byte aangeven welke plaats het priemgetal heeft in de index van Mesenne priemgetallen. Je moet die getallen niet als karakters zien maar als de integere weergave van bytes.

quote:

N‹'³aÜÛ˜æ

quote:

78 139 39 179 97 220 219 152 127 230

quote:

Used primes : 21 for 27 decimals
Compression is 77 %

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.

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.

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!!

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.

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.

quote:

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

[..]

Er is geen restant...

quote:

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

[..]

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

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.

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.

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.

quote:

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

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.

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?

quote:

x6YNsgK#mJ

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?

quote:

1792873102928338392382

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.

quote:

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

quote:

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

quote:

Op vrijdag 22 juli 2005 20:33 schreef gnomaat het volgende:

[..]

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

quote:

Op vrijdag 22 juli 2005 20:40 schreef BUG80 het volgende:
Bedoel je dat één getallenreeks kan staan voor meerdere ASCII files?

Ok, dan moet je dus inderdaad werken met A0 + 256*A1 + 256²*A3, enz.., met Ai de ASCII waarde van karakter 'i', maar dat maakt het uiteindelijke getal toch alleen maar nog langer?

quote:

Op zaterdag 23 juli 2005 00:10 schreef gnomaat het volgende:

[..]

Nog langer dan iets wat niet werkt ja, dus je moet wel

quote:

Op vrijdag 22 juli 2005 21:12 schreef BabeWatcher het volgende:
Ik heb al heel lang geleden een systeem proberen te maken gebaseerd op Chaos. Bij een willekeurig bestand neemt een tabel met verwijzingen gewoon meer ruimte in dan het origineel. Ik denk dat dat met priemgetallen niet veel beter zal zijn.

[[url=http://img280.imageshack.us/img280/3992/fb9yy.th.png]afbeelding][/URL]
Dit figuur is met een paar regels code te maken, het opgeslagen plaatje kost veel meer ruimte dan de broncode.

quote:

Op zaterdag 23 juli 2005 12:05 schreef Pietverdriet het volgende:

[..]

jaja, maar, dat zegt niet zoveel.
Er zijn ook programma´tje die een landschap genereren waar je dan virtueel zeg maar door heen gaat.
Dat is echter geen compressie, maar genereren van beelden.

Stel, en ik zeg stel, je kan een bitmap plaatje omrekenen naar een vectorgrafiek, en dat naar een fractale formule die dat zou genereren, en je doet dat 25 maal per seconde, dan zou je film kunnen omrekenen naar een fractale formule.
Dan zou je eventueel een compressie methode hebben (vooropgesteld dat het resultaat dan kleiner is)
Okay, stel dit zou kunnen, dan zou de hoeveelheid iteraties per film enorm groot zijn, en het is met zekerheid niet de methode die Sloot zou kunnen hebben gebruikt omdat
1) De wiskunde die daarvoor nodig is eerst eens moet uitgevonden worden.
2) De rekencapaciteit nodig is astronomisch.
3) Ook je met deze methode geen film naar 4K gaat krijgen.

quote:

Op zaterdag 23 juli 2005 12:41 schreef -erwin- het volgende:
Voornamelijk het laatste punt is waar het om gaat. De stelling dat het met 32768 bits mogelijk zou zijn om meer dan 32768 verschillende films te produceren is ridicuul.

quote:

Op zaterdag 23 juli 2005 11:15 schreef BUG80 het volgende:
Maar goed, dat deze specifieke methode niet werkt betekent nog niet dat we het idee van Gelly moeten afschrijven. Ik maakte al eerder een semi-grappige opmerking over "priemwoorden", maar misschien zit daar wel wat in. Stel nou dat we met een getallenstelsel gaan werken dat niet uit de decimalen 0-9 bestaat, maar uit ASCII waarden 0-255. Met zo'n getallenstelsel kun je net zo goed bewerkingen uitvoeren, zoals optellen en vermenigvuldigen. Vergelijk het met het hexadecimale stelsel 00-FF. Aangezien je lineaire operaties uit kunt voeren, zouden er ook equivalenten van priemgetallen moeten bestaan, toch?

quote:

Alleen ben ik bang dat de volgende stelling geldig is: Ontbinding van een getal in andere getallen zal gemiddeld genomen niet tot compressie leiden.

quote:

Op zaterdag 23 juli 2005 12:45 schreef gnomaat het volgende:

[..]

Ehm, meer dan 2³²⁷⁶⁸ films. En dat zijn er heel wat meer dan er ooit gemaakt zullen worden

quote:

Op zaterdag 23 juli 2005 12:48 schreef -erwin- het volgende:

[..]

ahum. mijn fout ik zal hem maar niet editen, anders lijkt het zo raar. goede morgen

quote:

Op zaterdag 23 juli 2005 12:46 schreef gnomaat het volgende:

[..]

Natuurlijk, die priemgetallen zijn hetzelfde als "onze" priemgetallen.

Het priem zijn van getallen hangt niet af van het talstelsel waarin je ze noteert.
[..]

Ik weet het wel zeker

quote:

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 zaterdag 23 juli 2005 12:53 schreef JasperE het volgende:
Stel dat de code bestaat, alsnog had geen enkele laptop in die tijd de benodigde rekenkrecht voorhet direct afspelen van 16 filmen simultaan

quote:

Op zaterdag 23 juli 2005 12:45 schreef gnomaat het volgende:

[..]

Ehm, meer dan 2³²⁷⁶⁸ films. En dat zijn er heel wat meer dan er ooit gemaakt zullen worden

quote:

Op zaterdag 23 juli 2005 13:03 schreef Pietverdriet het volgende:
en dan heb je 1 0 bit´s per film
De 2³²⁷⁶⁸ posities zijn dan alleen maar het catalogusnummer, je hebt niets meer over om informatie van de film op te slaan

quote:

Op zaterdag 23 juli 2005 12:57 schreef BUG80 het volgende:
Als zowel beeld als geluid ongecomprimeerd zijn zou het wel moeten kunnen, toch? Maarja, ze waren wel gecomprimeerd, dat is juist het punt.

quote:

Op zaterdag 23 juli 2005 12:55 schreef BUG80 het volgende:
Ja ik ook, gevoelsmatig. Heb je toevallig een link naar een wiskundig bewijs?

quote:

Op zaterdag 23 juli 2005 14:03 schreef gnomaat het volgende:

[..]

Nee zo niet, maar moet niet al te moeilijk zijn.
Wat voor ontbinding bedoel je precies, een getal normaal ontbinden in priemfactoren en dan voor iedere priemfactor opschrijven het hoeveelste priemgetal het is?
Of een zo groot mogelijk priemgetal vinden dat je van het getal af kunt trekken (eventueel alleen Mersenne priemgetallen of een andere bekende serie zodat je ze heel kort kunt noteren) en dan hetzelfde met het restant tot je 0 overhoudt. Dus een soort ontbinden in "priemsommen". Dat is geloof ik ook wat gelly deed?

quote:

Op zaterdag 23 juli 2005 14:00 schreef gnomaat het volgende:

[..]

Hoe zat dat eigenlijk bij die uitvinding van Jan Sloot, decomprimeerde zijn kastje de data? Of las hij alleen data uit dat kastje wat vervolgens met een normaal programma werd gedecomprimeerd?

quote:

Op zaterdag 23 juli 2005 14:22 schreef Pietverdriet het volgende:
Als je de vorige topics doorleest zal je zien dat de uitvinding geen van beide deed, omdat het helemaal niet kan.

quote:

Op dinsdag 26 juli 2005 00:31 schreef DirtyHarry het volgende:
Ik heb wiskundig bewijs dat Sloots verhaal niet kan kloppen.

quote:

Op dinsdag 26 juli 2005 00:31 schreef DirtyHarry het volgende:
Nu hebben we het nog niet eens over films. Neem een film van 640*480@25fps, 16bit kleurdiepte en 90 minuten lang.
Aantal mogelijkheden nu:
Totaal aantal pixels: 640x480x25x90x60 = 41472000000
2¹⁶ mogelijkheden per pixel

Totaal: (2¹⁶)^41472000000 = 2^663552000000 mogelijkheden.

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

quote:

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

[..]

lossy compression

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

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.

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

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.

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?

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.

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.

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.

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.

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.

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

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).

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

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.

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?

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).

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.

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

quote:

Op donderdag 28 juli 2005 21:56 schreef BUG80 het volgende:

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 donderdag 28 juli 2005 21:56 schreef BUG80 het volgende:

[..]

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:

Theorem:
No program can compress without loss *all* files of size >= N bits, for
any given integer N >= 0.

Proof:
Assume that the program can compress without loss all files of size >= N
bits. Compress with this program all the 2^N files which have exactly N
bits. All compressed files have at most N-1 bits, so there are at most
(2^N)-1 different compressed files [2^(N-1) files of size N-1, 2^(N-2) of
size N-2, and so on, down to 1 file of size 0]. So at least two different
input files must compress to the same output file. Hence the compression
program cannot be lossless.
[...]
Note that no assumption is made about the compression algorithm. The proof applies to
*any* algorithm, including those using an external dictionary, or repeated
application of another algorithm, or combination of different algorithms, or
representation of the data as formulas, etc... All schemes are subject to the
counting argument. There is no need to use information theory to provide a
proof, just very basic mathematics.

quote:

Op donderdag 28 juli 2005 21:56 schreef BUG80 het volgende:
[..]
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.

quote:

Op vrijdag 29 juli 2005 09:50 schreef Barati het volgende:

[..]

Het is gemakkelijk in te zien dat de verzameling mogelijke films groter is dan de verzameling "sleutels" van 64 kB. Je kunt (in theorie) bijvoorbeeld alle mogelijke reeksen van 65 kB op papier uitschrijven en van iedere reeks een film maken. Of iedere mogelijk plaatje genereren met een resolutie van 1000x1000 en van iedere plaatje een film maken. Met een sleutelgrootte van 64 kB worden verschillende films in deze voorbeelden op dezelfde sleutel afgebeeld.
[..]

(bron)

quote:

Op vrijdag 29 juli 2005 10:53 schreef BUG80 het volgende:
Ik kan het ook anders formuleren:

Je zou een random generator een film kunnen laten generen. Laat de generator 1,5 uur * 3600 sec * 25 frames * (720 * 480) pixels * 24 bits per pixel uitrekenen.

Hoe groot is de kans dat hier een film uitkomt die ook echt kijkbaar is? Ik denk verwaarloosbaar klein.

Kortom, kennelijk voldoet de data in films aan bepaalde conventies / patronen.

[edit]
Als je die generator alle mogelijke films van 1,5 uur zou laten berekenen (een onmogelijke klus, maar goed), dan zou je na afloop 99,999999999999999999..% weg kunnen gooien als zijnde waardeloos. Misschien is Sloot's algoritme daarop gebaseerd.
[/edit]

quote:

Op vrijdag 29 juli 2005 10:41 schreef BUG80 het volgende:

[..]

Ja dat klopt.

Maar. Er zijn zeker reeksen te verzinnen die zeker niet voor zullen komen, of onwaarschijnlijk. Bijvoorbeeld: films met alleen maar zwarte frames, of films die voor 50% uit ruis bestaan. Of films waarin in elk frame het complete mogelijke kleurenpallet voorkomt. En zo kun je nog wel even doorgaan. Het zou kunnen, dat het algoritme van Sloot "normale" films verkleint en "onwaarschijnlijke" films vergroot, net als WinZip.

quote:

Ergens moet er een ondergrens zijn van wat mogelijk is qua compressie van films en die ligt niet bij 80 GigaByte, lijkt me.

Ik kan het niet vaak genoeg zeggen: ik geloof er ook niet in. En als Sloot had gezegd dat zijn algoritme werkt op alle mogelijke bestanden viel dat ook wiskundig te bewijzen.

quote:

Op vrijdag 29 juli 2005 11:20 schreef Pietverdriet het volgende:

[..]

Nee, das volledige onzin.

quote:

Op vrijdag 29 juli 2005 11:26 schreef BUG80 het volgende:

[..]

Kun je ook uitleggen waarom?

quote:

Op vrijdag 29 juli 2005 11:26 schreef BUG80 het volgende:

[..]

Kun je ook uitleggen waarom?

Laten we zeggen dat voor een complete ongecomprimeerde film 80 GB nodig is. Ik durf te wedden dat elke film kleiner te maken is dan dat.

Kun jij dan bewijzen waar de ondergrens dan wel ligt?

quote:

Op vrijdag 29 juli 2005 11:28 schreef Pietverdriet het volgende:

[..]

Het genereren van random films en dan bijna alles weggooien is volledige onzin, dat hoef ik je toch niet uit te leggen, wel?

quote:

Op vrijdag 29 juli 2005 11:34 schreef Barati het volgende:
Als je slecht specifieke bitstrings wilt rekenen tot de verzameling films dan zult je precies moeten definiëren welke dit zijn.

quote:

Op vrijdag 29 juli 2005 10:53 schreef BUG80 het volgende:
Ik kan het ook anders formuleren:

Je zou een random generator een film kunnen laten generen. Laat de generator 1,5 uur * 3600 sec * 25 frames * (720 * 480) pixels * 24 bits per pixel uitrekenen.

Hoe groot is de kans dat hier een film uitkomt die ook echt kijkbaar is? Ik denk verwaarloosbaar klein.

Kortom, kennelijk voldoet de data in films aan bepaalde conventies / patronen.

[edit]
Als je die generator alle mogelijke films van 1,5 uur zou laten berekenen (een onmogelijke klus, maar goed), dan zou je na afloop 99,999999999999999999..% weg kunnen gooien als zijnde waardeloos. Misschien is Sloot's algoritme daarop gebaseerd.
[/edit]

quote:

Op vrijdag 29 juli 2005 11:46 schreef XoxIx het volgende:

[..]

Er zijn een enorme hoeveelheid films "kijkbaar". Neem een willekeurige film. Alleen al door films in verschillende talen na te synchroniseren en/of te ondertitelen groeit het al enorm. Daarnaast kun je alle mogelijke scenes toevoegen en weglaten of kleding, cast, bewoording, geluidseffecten en/of muziek aanpassen in elke wilekeurige combinatie. Zoals al eerder is opgemerkt is het aantal variaties op een enkele film al bijna eindeloos.

quote:

Op vrijdag 29 juli 2005 11:49 schreef BUG80 het volgende:

[..]

Zeker, maar draai het eens om: het aantal realisaties dat je kunt maken in 80 GB waar je niks aan hebt is nog veel groter.

quote:

Op vrijdag 29 juli 2005 11:49 schreef BUG80 het volgende:

[..]

Zeker, maar draai het eens om: het aantal realisaties dat je kunt maken in 80 GB waar je niks aan hebt is nog veel groter.

quote:

Op vrijdag 29 juli 2005 11:51 schreef Pietverdriet het volgende:

[..]

En?

quote:

Op vrijdag 29 juli 2005 11:51 schreef XoxIx het volgende:

[..]

Dan draai ik het gewoon nog een keer om. Het aantal combinaties dat je kunt maken met 64 KB is veel kleiner.

quote:

Op vrijdag 29 juli 2005 11:55 schreef BUG80 het volgende:

[..]

Ok voorbeeld: Neem een willekeurige film. Door eindeloos te variëren met acteurs, talen, scenes, enz kun je, zeg, 10¹⁰ verschillende versies maken.

Echter, door de film aan te passen zodat je er niks meer aan hebt, door bijvoorbeeld door elk 3e frame zwart te maken, of elk 4e, of de helft eruit te knippen, enz zijn er, zeg 10¹⁰⁰ versies te maken waar je niets aan hebt.

Net als met tekst, is het aantal films dat niet voor zal komen vele malen groter dan het aantal dat wel voor zal komen, dat is alles wat ik probeer te zeggen.

quote:

Op vrijdag 29 juli 2005 12:00 schreef Pietverdriet het volgende:

[..]

Ja, dat begrijp ik, maar wat heeft dat er mee te maken?

quote:

Op vrijdag 29 juli 2005 11:57 schreef BUG80 het volgende:

[..]

Inderdaad, maar nog steeds zo goed als oneindig (2^(64*1024*8) is heel, heel groot). Dus waar ligt de ondergrens nou echt?

quote:

Op vrijdag 29 juli 2005 12:04 schreef BUG80 het volgende:

[..]

Ik probeer de link te leggen met het comprimeren van andere typen bestanden, zoals tekst. Zodra je aan kunt geven dat er realisaties zijn die waarschijnlijker zijn dan andere, kun je gemiddeld genomen compressie bereiken.

Hoe kleiner de groep waarschijnlijke realisaties, hoe groter de maximaal haalbare compressie.

quote:

Op vrijdag 29 juli 2005 12:05 schreef Pietverdriet het volgende:

[..]

Welke ondergrens?
Waarom denk je dat ie hard zou zijn?
Als je een film als Patton op DVD (MPEG 2) zet van Film, heb je verlies, in oplossend vermogen, in kleur, etc.
Als je die MPEG 2 nog verder comprimeerd naar DIVX, XVID, MPEG4, MJPG whatever heb je nog meer verlies.
is je file dan 750 Mb is ie te groot voor een normale CD, ah, dan haal je wat resolutie weg, en dan past ie wel.
Zo kan je doorgaan, maar de kwaliteit wordt steeds minder.
Dus die ondergrens ligt daar waar je de minimale kwaliteit legt.

quote:

Op vrijdag 29 juli 2005 12:08 schreef Pietverdriet het volgende:

[..]

Ja, maar wat is nu je punt wat je daar mee wilt zeggen? Dat is allang en uitvoerig behandeld in de vorige topics. Dat je een database kan nemen met de filmbouwsteentjes, en een sleutel die ze achter elkaar plakt.

quote:

Op vrijdag 29 juli 2005 12:10 schreef BUG80 het volgende:

[..]

Ok, mijn fout, ik zal het allemaal nog eens aandachtig gaan lezen. Ik probeer alleen aan te ontkrachten dat er een wiskundig bewijs zou zijn dat de onmogelijkheid aantoont van deze compressie.

quote:

Op vrijdag 29 juli 2005 13:03 schreef Barati het volgende:

[..]

Definieer nu eerst eens wat je bedoelt met een film. Dan kunnen we verder.

quote:

Op vrijdag 29 juli 2005 09:50 schreef Barati het volgende:
Het is gemakkelijk in te zien dat de verzameling mogelijke films groter is dan de verzameling "sleutels" van 64 kB. Je kunt (in theorie) bijvoorbeeld alle mogelijke reeksen van 65 kB op papier uitschrijven en van iedere reeks een film maken.

quote:

Op vrijdag 29 juli 2005 13:07 schreef BUG80 het volgende:
Met kijkbaar bedoel ik dat het om echte beelden gaat, geen ruis-achtige verschijnselen. Een wiskundige definitie van kijkbaar is een Nobelprijs waard denk ik.

quote:

Op vrijdag 29 juli 2005 13:40 schreef gnomaat het volgende:

[..]

kijkbaar := comprimeerbaar tot +/- 700 MB

quote:

Op vrijdag 29 juli 2005 13:40 schreef gnomaat het volgende:

[..]

Zelfs in theorie niet, want de hoeveelheid papiermoleculen die je daarvoor nodig hebt is veel groter dan het aantal deeltjes in het heelal (dat laatste wordt geloof ik geschat op 10⁸⁰).

In de praktijk is het aantal films dat er bestaat en ooit in de toekomst gemaakt kan worden, veel kleiner dan het aantal combinaties dat je in 64 KB (of ook al in 4 KB) kwijt kunt.

quote:

Op vrijdag 29 juli 2005 14:14 schreef Barati het volgende:
Het is simpel om een programma te schrijven dat b.v. 2^1000000 unieke "kijkbare" films kan genereren (d.w.z. een zo'n film uit deze verzameling genereert).

quote:

Op vrijdag 29 juli 2005 14:19 schreef BUG80 het volgende:

[..]

Ja, daar heb jij weer een punt. Je zou van een film willekeurig beeldjes kunnen spiegelen, inverteren, enz en dan heb je zo veel meer realisaties. De vraag is: zijn al deze realisaties waarschijnlijk (intuitief zeg je van niet: je gaat niet naar een film zitten kijken waarin willekeurige beeldjes zijn gespiegeld). Een algoritme wat de waarschijnlijkheid van deze realisaties in acht neemt is waarschijnlijk niet te schrijven. In de praktijk, althans.