mega-compressie - deel 2 -

Deel 2 alweer? Zit bijna in een mega-depressie

Ik wil nog steeds de uitzending zien of t boek lezen. Wat ik er tot nu toe van begreep is dat ie is geliquedeerd door Phillips omdat hun mediadragers dan in 1 klap overbodig zouden worden

quote:

Op donderdag 21 juli 2005 00:29 schreef SunChaser het volgende:
Ik wil nog steeds de uitzending zien of t boek lezen. Wat ik er tot nu toe van begreep is dat ie is geliquedeerd door Phillips omdat hun mediadragers dan in 1 klap overbodig zouden worden

In het vorige topic had iemand erover dat ie door de makers van WinZip is vermoord!

Stel dat t waar zou zijn. Dan zouden de miljarden voor UMTS, ADSL, HD's, DVD, etc in een klap achterhaald zijn. Dus er spelen wel belangen mee. Mensen worden al vermoord voor 100 euro, laat staan honderden miljarden euro's.

Is de challenge nog on? (wat mij betreft wel! )

Volgens het pigeonhole-principe is het niet mogelijk om alle permutaties van X bytes te comprimeren tot een representatie die kleiner dan X bytes is. Als je dit wel doet loopt je tijdens het decomprimeren tegen het probleem aan dat er 1 gecomprimeerd bestand zich laat terugvertalen in meer dan 1 ongecomprimeerde mogelijkheden. Effectief heb je dus informatie weggegooid waardoor je niet het originele bestand terug kan halen.

Vandaar ook dat compressie (uberhaupt, alle vormen van datareductie, of Sloot het nu wel of geen compressie noemt is irrelevant) gebaseerd is op het principe: we reduceren sommige bestanden van X bytes tot een grootte die kleiner is dan X bytes, ten koste van de minder waarschijnlijke bestanden, die meer dan X bytes zullen moeten innemen.
Deze reductie staat of valt met de hoeveelheid informatie die in zo'n bestand is opgeslagen, de zgn. Entropie (bedacht door Shannon). En de entropie hangt af van de mate van voorspelbaarheid van deze gegevens. Hoge voorspelbaarheid -> lage entropie -> grote compressie. Lage voorspelbaarheid of onwaarschijnlijke combinatie gegevens -> hoge entropie -> expansie.
Gegeven de kansverdeling op het aantal mogelijke bestanden, kan men de bijbehorende entropie uitrekenen en, voor een bepaald bestand een zekere compressie bereiken.

Het feit dat deze maat van informatie, entropie, ook echt een absolute ondergrens bepaalt volgt uit inductie: stel dat elk bestand van X bytes teruggebracht kan worden tot een bestand van X-1 bytes. Wat let je om hetzelde algoritme nog een keer toe te passen op dat bestand van X-1 bytes om het te comprimeren tot X-2 bytes? Niks. En dan kan je dat nog een keer doen tot X-3 bytes, etc.
Net zolang totdat de bestandsgrootte 0 nadert. Iets wat pertinent onmogelijk is, omdat er zeker meer dan 256 films / bestanden bestaan.

Ergo: er moet wel een harde ondergrens bestaan aan de mate waarin je bestanden kunt comprimeren.

Vreselijk veel vat ik er niet van hoor, maar dat priemgetallen idee is best slim eigenlijk. Je zou dus als de dictionary de priemgetallen moeten gebruiken? Te kleine stukjes code zou je dan kunnen weergeven door het priemgetal en het aantal binaire cijfers dat er gelezen moet worden.
Misschien interessant: http://nl.wikipedia.org/wiki/Illegaal_priemgetal

quote:

Dat idee had ik jaren geleden al in een andere vorm. Dataopslag op videobanden, en dan niet het magnetische spoor uitlezen, maar de pixels op het beeldscherm. 256 kleuren * bepaalde intensiteit * resolutie van opname. Dat is nogal wat data per frame.

Sterker nog, daar is ooit een product van op de markt geweest. Als alternatief voor de computer tape recorder voor backups. Van wat ik met herinner van de test in de computer!totaal werkte het niet helemaal denderend.

quote:

Op donderdag 21 juli 2005 00:51 schreef Lynx666 het volgende:
*hamer* coderen *hamer*

What's the fucking difference, hebben we het nu over een film die in 4Kb past ja of nee!

Ik snap er echt geen reet van, maar intrigerend vind ik het wel

quote:

Op donderdag 21 juli 2005 00:47 schreef HenryHill het volgende:
Ergo: er moet wel een harde ondergrens bestaan aan de mate waarin je bestanden kunt comprimeren.

Inderdaad. Al sluit dit de mogelijkheid van het comprimeren van films tot 4 Kb nog niet direct uit: het aantal mogelijke sleutels van 32768 bits is veel groter dan alle films die ooit gemaakt zijn of de komende paar honderd jaar gemaakt zullen worden.

Dus wat betreft kun je in de praktijk iedere film wel coderen als (of liever gezegd identificeren met) een unieke sleutel van 4 Kb. Ten koste van 10^biljarden theoretische "films" met random noise of wat voor niet bestaande content dan ook, die je hiermee niet zou kunnen coderen of alleen groter kunt maken.

Maar leg eens uit in N00b-taal. Een complete film wordt compleet uit elkaar gehaald en door een sleutel weer in elkaar gezet? Net zoals Star Trek? Dat je een lichaam upbeamt, dus molecuul voor molecuul afbreekt en door een unieke steutel elders weer in elkaar zet?

Dus de complete ge-gzipte DeCSS code kun je samenvatten met
k*256211+99

da's toch geen onaardige compressiefactor lijkt me

Misschien komt er een overzichtelijk boekje van Dick Bruna: Nijntje en de Megacompressie

quote:

Op donderdag 21 juli 2005 01:01 schreef SunChaser het volgende:
Maar leg eens uit in N00b-taal. Een complete film wordt compleet uit elkaar gehaald en door een sleutel weer in elkaar gezet? Net zoals Star Trek? Dat je een lichaam upbeamt, dus molecuul voor molecuul afbreekt en door een unieke steutel elders weer in elkaar zet?

Zoiets denk ik ja.
Volgens mij moet je het zo zien:

A = B * C

Als je A (de uiteindelijke) wilt berekenen, en * C is een vaste waarde (het algoritme ofzo) dan moet je B invullen (de 'gezipte' film). Andersom kan dat dus ook als je B wilt berekenen door A in te vullen. Het algoritme C blijft natuurlijk hetzelfde.

Ik hoop dat dat simpel genoeg was, en dat ikzelf geen foute dingen verkondig

[ Bericht 4% gewijzigd door Boes-Poes op 21-07-2005 01:10:58 ]

quote:

Op donderdag 21 juli 2005 01:02 schreef Danny het volgende:
Dus de complete ge-gzipte DeCSS code kun je samenvatten met
k*256211+99

da's toch geen onaardige compressiefactor lijkt me

In dat geval zou je dus eigenlijk vrij simpel (met ENORM veel rekenkracht) ELK ge-gzipt bestand kunnen omrekenen naar een priemgetal en deze weergeven in slechts een paar bytes.
Met een de-priem programma zou je het priemgetal weer kunnen omzetten in de nullen en enen waarna je datzelfde bestand in g-zip formaat hebt. Uitpakken en je film, filmcollectie, complete harddisk etc is weer compleet.

quote:

Op donderdag 21 juli 2005 00:59 schreef Lynx666 het volgende:

[..]

Wil je een beetje in de buurt komen van wat ie gefabriceerd heeft, zul je toch op zijn manier moeten denken. Van het volgen van bekende denkwijzen is nog nooit iemand uitvinder geworden. .

Natuurwetten zijn nog nooit gebroken. Hooguit is het model van de natuurwetten aangepast aan de nieuwste bevindingen (zoals tegenwoordig bekend is dat atomen ook weer zijn samengesteld uit iets van 6 sub-atomaire deeltjes. Geloof ik).

Echter, compressie is een wiskundig gedefinieerd probleem. En de wetten van wiskunde zijn ook nog nooit gebroken, maar er bestaat geen enkele uitbreiding die de basisprincipes van de wiskunde ongedaan kunnen maken of er op een andere manier langsheen kunnen glippen. Dat komt omdat wiskunde, in tegenstelling tot natuurkunde, niet berust op een model maar op pure logica.

quote:

Op donderdag 21 juli 2005 01:05 schreef Danny het volgende:

[..]

In dat geval zou je dus eigenlijk vrij simpel (met ENORM veel rekenkracht) ELK ge-gzipt bestand kunnen omrekenen naar een priemgetal en deze weergeven in slechts een paar bytes.
Met een de-priem programma zou je het priemgetal weer kunnen omzetten in de nullen en enen waarna je datzelfde bestand in g-zip formaat hebt. Uitpakken en je film, filmcollectie, complete harddisk etc is weer compleet.

Dat zou moeten inhouden dat elk priemgetal die er tot nu toe gevonden is vastzit aan een vaststaande reeks enen en nullen om steeds hetzelfde bestand er weer uit te krijgen. Dit klinkt erg tegenstrijdig.

quote:

Op donderdag 21 juli 2005 01:02 schreef Danny het volgende:
Dus de complete ge-gzipte DeCSS code kun je samenvatten met
k*256211+99

da's toch geen onaardige compressiefactor lijkt me

Breng eens een bugfix uit voor het programma, waarvoor 1 instructie (1 a 2 bytes) veranderd moeten worden. En weg is je wiskundige expressie voor dat programma - en dus ook de bijbehorende compressie.

Dat is het hele idee achter compressie: sommige bestanden kunnen belachelijk klein worden gemaakt, ten koste van een hele hoop andere bestanden die onvermijdelijk groter zullen moeten worden.