Pagina 29 van 30

Re: Mega-Compressie (Deel 2)

BerichtGeplaatst: za 21 jan 2012, 19:46
door Michael1954
From: Barati

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

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)

Re: Mega-Compressie (Deel 2)

BerichtGeplaatst: za 21 jan 2012, 19:47
door Michael1954
From: Barati

Er bestaat geen algoritme dat al deze mogelijke gewijzigde films lossless comprimeert tot 64kB

Re: Mega-Compressie (Deel 2)

BerichtGeplaatst: za 21 jan 2012, 19:59
door Michael1954
From: BUG80

Barati schreef:
[..]

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)

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

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?

Re: Mega-Compressie (Deel 2)

BerichtGeplaatst: za 21 jan 2012, 20:00
door Michael1954
From: Barati

BUG80 schreef:
[..]
Ah, there you go, dat lijkt me wel een goed bewijs ja. :oops:

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?

nee

Re: Mega-Compressie (Deel 2)

BerichtGeplaatst: za 21 jan 2012, 20:01
door Michael1954
From: BUG80

Barati schreef:
[..]
nee

Ok. Kort en bondig :)

De vraag of een bestand kan worden gecomprimeerd tot N bytes is alleen te weerleggen met een tegenvoorbeeld, het is niet te bewijzen dat het wel kan zonder de code erbij te geven.

Re: Mega-Compressie (Deel 2)

BerichtGeplaatst: za 21 jan 2012, 20:02
door Michael1954
From: McCarthy

gaaf topic

Re: Mega-Compressie (Deel 2)

BerichtGeplaatst: za 21 jan 2012, 20:05
door Michael1954
From: McCarthy

Danny schreef:
[..]

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)

dit klinkt wel leuk

jammer dat factorisatie van grote priemgetallen zo traag gaat :oops:

Re: Mega-Compressie (Deel 2)

BerichtGeplaatst: za 21 jan 2012, 20:06
door Michael1954
From: McCarthy

Gelly schreef:
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.

1231387

Calculating ...
Calculating ...
Calculating ...
New prime found
Calculating ...
New prime found
Calculating ...
New prime found
Used primes : 8 for 7 decimals
Compression is 114 %

Re: Mega-Compressie (Deel 2)

BerichtGeplaatst: za 21 jan 2012, 20:08
door Michael1954
From: McCarthy

Gelly schreef:
[..]
Ja, ik sla namelijk niet de priemgetallen zelf op, alleen het hoeveelste Mersenne priemgetal het is.

Mersenne :roll:

als je een echt krachtige computer hebt zou je natuurlijk ook gewoon de echte priemen kunnen fixen

Re: Mega-Compressie (Deel 2)

BerichtGeplaatst: za 21 jan 2012, 20:09
door Michael1954
From: McCarthy

maar wacht effe, als je met mersenne werkt kan je toch niet elk getal ontbinden in mersenne priem getallen