Mega-Compressie (Deel 2)

[Michael1954]

From: BUG80

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

[Michael1954]

From: DirtyHarry

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

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

[Michael1954]

From: BUG80

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

Inderdaad, zoniet onmogelijk. Dat betekent dat hij één of ander patroon had moeten vinden dat voor alle films geldt.

Ik ben het dus met je eens hoor, ik geloof er niet in, maar wiskundig bewijzen dat het onmogelijk is gaat niet volgens mij.

[Michael1954]

From: ACT-F

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

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

[Michael1954]

From: BUG80

Ik heb het eerste deel van de Netwerk uitzending inmiddels gezien. Jammer dat ze geen sceptici aan het woord laten, het is wel erg eenzijdig zo.

Ik vraag me trouwens al een tijdje af waarom deze vermeende techniek alleen op films werd toegepast door Sloot.

1) Was het een algoritme dat optimaal of alleen maar voor films werkt?
2) Is het omdat dat makkelijker te demonstreren valt (spreekt tot de verbeelding)?
3) Is het omdat je dan makkelijker mensen kan bedriegen? (als je "gewone" of willekeurige bestanden gebruikt, zullen mensen als snel vragen of je ook andere bestande wilt proberen)

[Michael1954]

From: Doderok

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

Er is een verschil tussen nooit een bestand kunnen verkleinen = geen enkel bestand kunnen verkleinen, en niet alle bestanden kunnen verkleinen.
Als je een bestand neemt van bvb 2000 bits, en winzip comprimeert dit tot een bestand van 1024 bits, dan zal winzip dat bestand van 1024 bits niet meer kunnen comprimeren.
Tekstbestanden bijvoorbeeld comprimeren goed omdat tekst veel redundantie bevat.

Nu lijkt het misschien dat je de toch winst maakt met winzip over het totaal van de 2^1024 mogelijke files, omdat je een deel kleiner kunt maken. MAAR: er zullen ook files groter worden!!

vb: ik heb een bitmap X gecromprimeerd met winzip, het resultaat is een file Y van 1.325.093 bytes.
Nu ga ik deze file nog eens comprimeren, resultaat:file Z van 1.325.300 bytes
Waarom is deze file groter geworden? Winzip kan hem niet verder comprimeren, maar hij kan hem ook niet onveranderd laten, want als ik hem dan zou unzippen zou ik de oorspronkelijke bitmap X terugkrijgen en niet file Y.

Nu is winzip niet geoptimaliseerd voor het verwerken van reeds gecomprimeerde files, men zou het algoritme kunnen aanpassen zodat files hoogstens 1 bit groter kunnen worden. Die ene bit zou dan aangeven of het bestand gecomprimeerd is, of het origineel bevat. Blijkt compressie het bestand groter te maken,dan voeg je enkel deze bit toe aan het bestand (je zet een 0 ervoor), in het andere geval zet je een 1 voor het resultaat. Merk op dat hierdoor alle gecomprimeerde bestanden een bit groter worden.

Uiteindelijk, als je alle mogelijke files van 1024 bits comprimeert, dus 1024 * 2^1024 bits aan data, dan zal je als resultaat opnieuw 1024 * 2^1024 bits aan data krijgen. De compressie van een deel van de bestanden wordt gecompenseerd door de extra bit die een ander deel van de bestanden krijgen. (in werkelikheid zal je meer data krijgen dan waar je mee begonnen zijn, omdat winzip oa een CRC waarde toevoegd)

[Michael1954]

From: Doderok

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

Als er maar 4 films gemaakt zijn heb je inderdaad maar twee bits nodig om ze op te slaan, ongeacht de grootte van de films. Dit algoritme is eenvoudig, MAAR het data-gedeelte moet de volledige films bevatten!

Als je een compressie-algoritme ontwerpt voor een bepaald type files, dan kan je de compressie verhogen door het algoritme meer data te geven. Voor nederlandse teksten kan je bijv. heel de nederlandse woordenlijst gebruiken, en de woorden volgens een frequentietabel te nummeren. vb: de=001 een=010 het=011 met=1000 van=1001 op=1010 enzovoort. Je bekijkt een hoop texten om de frequentie van elk woord te bepalen, en dan geef je elk woord een unieke code, hoe frequenter het woord voorkomt, hoe korter de code.

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.

[Michael1954]

From: BUG80

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

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.

[Michael1954]

From: Gomaat

ACT-F schreef:
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

Je hoeft geen verdere details te verklappen, maar het klinkt alsof je iets essentieels over het hoofd ziet. Even om duidelijk te krijgen waar we het over hebben:

- een manier om meer data in dezelfde hoeveelheid bits te kunnen vastleggen, dus dat je bijvoorbeeld een film die uncompressed 150 GB is, kwijt kunt op een flash kaartje van 128 MB? (of zelfs nog kleiner)

- of een manier om fysiek gezien efficiënter data op te slaan, dus een één of ander zelfbedacht opslagmedium met een hogere datadichtheid (meer bits/cm2) dan de huidige harddisks/dvd's/enz ?

Is het lossy of lossless?

En werkt het alleen voor bepaalde soorten data, bijvoorbeeld audiovisuele data (zoals films), of ook voor random data?

Is de methode ook van toepassing op zichzelf? M.a.w. kun je de kleinere bitstream die je volgens jouw idee krijgt (als het resultaat weer een bitstream is althans) zelf ook weer als een normale bitstream interpreteren en die op dezelfde manier "anders noteren"? Zodat je dus dubbele winst krijgt.

[Michael1954]

From: Pietverdriet

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

Lees de vorige topics eens door.