mega-compressie - deel 2 -

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.

quote:

Op vrijdag 29 juli 2005 14:35 schreef Barati het volgende:

[..]

Neem een film met een tijdsduur van 1 uur. Deze bevat 24 * 60 * 60 = 86400 beelden. In ieder beeld zou je één pixel iets kunnen wijzigen (het minst significante bit van deze pixel bijvoorbeeld). Het aantal mogelijke gewijzigde films is hiermee groter dan 2^64k. Als het origineel kijkbaar is dan zijn deze gewijzigde films dat ook (bij een kleurendiepte van 24 bit zul je geen verschil merken tussen het origineel en de gewijzigde film)

quote:

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

[..]

Ah, there you go, dat lijkt me wel een goed bewijs ja.

Bestaat er eigenlijk een formule waarmee de hoeveelheid "redundantie" in een willekeurig bestand is te berekenen, m.a.w. wat de maximaal haalbare compressie van dat bestand zou zijn?

quote:

Op vrijdag 29 juli 2005 15:05 schreef Barati het volgende:

[..]

nee

quote:

Op donderdag 21 juli 2005 17:18 schreef Danny het volgende:

[..]

heel simpel uitgelegd:
een bestand zet je om in een getal. dit kan gewoon het bestand in binaire stand zijn (nullen en enen), maar ook het bestand in decimale waarden (000-255).
Dat getal is vele miljoenen tot miljarden tekens lang, maar het blijft één enkel getal.

Dat getal ga je vervolgens omzetten in een optelsom vermenigvuldiging van priemgetallen, welke je wiskundig noteert (een paar bytes per priemgetal).
voila, je hebt het bestand gereduceerd tot een paar honderd Kb.
Probleem is dat er enorm veel rekenkracht nodig is om de juiste priemgetallen en formules te vinden.
Heb je dat eenmaal gedaan dan is de omschakeling naar het oorspronkelijke bestand relatief eenvoudig.

De wiskundige notaties worden gewoon voluit neergezet, de optelsommen worden gemaakt en je hebt je bestand weer in binaire/decimale notatie en dus je oorspronkelijke bestand.

(heel simpel gezegd, niet zo makkelijk uit te voeren)

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

quote:

Op vrijdag 29 juli 2005 19:41 schreef McCarthy het volgende:
geofysici werken met een compressie factor van 1%
De bestanden die ingepakt worden zijn data van de aarde

quote:

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

[..]

1% maar?

quote:

Maar goed, op de vele terabytes die een gemiddelde seismische meting opleveren scheelt dit aardig wat dollars.