Mega-Compressie (Deel 2)

Mega-Compressie (Deel 2)

Re: Mega-Compressie (Deel 2)

Berichtdoor Michael1954 » za 21 jan 2012, 18:56

From: Barati

BUG80 schreef:
[..]
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.

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.

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.

(Bron)
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Mega-Compressie (Deel 2)

Berichtdoor Michael1954 » za 21 jan 2012, 18:57

From: XoxIx

BUG80 schreef:
[..]
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.

Tekst is vooral niet willekeurig omdat het vooral afhankelijk is van ongeveer 50 tekens (letters, cijfers en speciale tekens), terwijl er in een byte 256 kunnen worden gerepresenteerd. Films bestaan inderdaad al uit een heleboel redundantie, daarom kun je een enorme film met DivX of een gelijkwaardig compressie-algoritme al behoorlijk verkleinen. De ongeloofwaardigheid komt niet voort uit het kunnen comprimeren van films, maar het hebben van een chipknip met daarop 32 volledige films.
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Mega-Compressie (Deel 2)

Berichtdoor Michael1954 » za 21 jan 2012, 19:00

From: BUG80

Barati schreef:
[..]
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)

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.

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.
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Mega-Compressie (Deel 2)

Berichtdoor Michael1954 » za 21 jan 2012, 19:00

From: BUG80

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]
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Mega-Compressie (Deel 2)

Berichtdoor Michael1954 » za 21 jan 2012, 19:01

From: Pietverdriet

BUG80 schreef:
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]

Nee, das volledige onzin.
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Mega-Compressie (Deel 2)

Berichtdoor Michael1954 » za 21 jan 2012, 19:04

From: Barati

BUG80 schreef:
[..]
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.

Dit kan ook niet anders. Zie bewijs hierboven.

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.

Sloot beweerde dat een film ongeacht de lengte verkleind kon worden tot een sleutel van 64 kB.
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Mega-Compressie (Deel 2)

Berichtdoor Michael1954 » za 21 jan 2012, 19:05

From: BUG80

Pietverdriet schreef:
[..]
Nee, das volledige onzin.

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?
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Mega-Compressie (Deel 2)

Berichtdoor Michael1954 » za 21 jan 2012, 19:07

From: Pietverdriet

BUG80 schreef:
[..]
Kun je ook uitleggen waarom?

Het genereren van random films en dan bijna alles weggooien is volledige onzin, dat hoef ik je toch niet uit te leggen, wel?
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Mega-Compressie (Deel 2)

Berichtdoor Michael1954 » za 21 jan 2012, 19:08

From: Barati

BUG80 schreef:
[..]
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?

We moeten eerst afspreken wat we bedoelen met een film. Als iedere mogelijke bitstring in aanmerking komt bestaat er geen algoritme dat iedere film lossless verkleint.
Als je slecht specifieke bitstrings wilt rekenen tot de verzameling films dan zult je precies moeten definiëren welke dit zijn.
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

Re: Mega-Compressie (Deel 2)

Berichtdoor Michael1954 » za 21 jan 2012, 19:10

From: BUG80

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

Ik gebruikte dit gedachtenexperiment om aan te geven dat er kennelijk reeksen zijn te verzinnen die onwaarschijnlijk zijn, net als dat WinZip gebruik maakt van het feit dat er een hele hoop teksten zijn die onwaarschijnlijk zijn. Waar ga ik de fout in?
Avatar gebruiker
Michael1954
 
Berichten: 3618
Geregistreerd: zo 22 aug 2010, 16:39

VorigeVolgende

Keer terug naar Forum.Fok.NL (0705)

cron