Datacompressie: Hoeveel is mogelijk?

[Anoniem: 33775]

Tegenwoordig heb je allerlei technieken om bestanden kleiner te maken. Bv zip, rar, arj, mp3 enz.

Ik vraag me af hoeveel je een bestand maximaal kunt verkleinen zonder verlies van gegevens.

Zou het mogelijk zijn om wiskundig aan te tonen hoever je een (willekeurig) bestand maximaal kunt verkleinen? Je moet het bestand natuurlijk zonder verlies van data weer uit kunnen pakken.

Zelf heb ik geen idee. Ik denk wel dat hoever je een bestand kan inpakken voor een groot deel afhangt van hoe groot je inpak programma is.
Het programma dat je bestand in- of uitpakt bevat volgens mij ook een deel van de informatie uit het bestand. Dit is echter universele informatie die je over elk (ingepakt) bestand moet hebben om het weer uit te pakken. (Ik weet ook niet hoe ik het beter uit kan leggen)

[Wouter]

Op Sunday 09 December 2001 18:57 schreef Melkor het volgende:
Zou het mogelijk zijn om wiskundig aan te tonen hoever je een (willekeurig) bestand maximaal kunt verkleinen?

Dat denk ik niet. Als dat zo zou zijn zou die maximale compressie ook mogelijk moeten zijn met de huidige technieken.

Je kan volgens mij moeilijk berekenen tot hoever je iets kan comprimeren met een nog niet bestaande techniek.

[Gnoom]

Het scheel gewoon net wat voor bestanden het zijn. Als het er een is waar heel vaak hetzelfde in voorkomt kan je hem een boel verkleinen, maar het is ook zo dat als je het comprimeerprogramma belachelijk groot maakt, je sommige bestanden echt heel erg klein kunt krijgen, maar dan is het weer de vraag hoe groot je een prgramma wilt hebben.

[Confusion]

http://www.howstuffworks.com/file-compression.htm

[Clay]

http://www.theproduct.de 64K, belachelijk.

[Anoniem: 41684]

http://www.theproduct.de 64K, belachelijk.

ik ken die lieden die dat gemaakt hebben (zelfde wereldje, demoscene)
en heb zelf ook zulke dingen gemaakt. Ik kan je melden dat het echt niet zo moeilijk is.

Er is aan dat hele ding niks gecompressed.

Ze beschrijven op een bepaalde manier een plaatje of een geluidje.
Zo is het kleiner om te zeggen 'lijn van x1y1 naar x2y2' dan de hele bitmap op te slaan. Hetzelfde kan je met muziek doen.

Ik heb dus ook met de tool gespeeld die zij (farbrausch) gebruikt hebben om the product te maken. Het is in principe niet veel meer dan een 3d modeller en een texture generator.

bv, 'genereer bol' in plaats van alle 3d-punten op te slaan.

het is voor een buitenstaander zeker indrukwekkend, als je door hebt hoe of wat, niet meer zo...

kijk eens naar http://www.aardbei.com/files/ptct-final.zip

zelfde principe (al moet ik bekennen dat the product er beter uitziet )

[Wirf]

Je kunt een bestand oneindig comprimeren, ga maar na, als je bij de comprimeerder en decomprimeerder afspreekt dat "a" staat voor 40GB aan nullen, dan heb je al een compressieratio van 100% (eigenlijk iets van 99,9999999999[..] maar door afronding word het 100%)

[Mx. Alba]

Maximale compressie krijg je met fractalcompressie. Als je dan ook nog toestaat dat het een beetje lossy is (wat voor multimedia wel kan), kan je echt ongelofelijke compressieratio's krijgen. Het probleem is alleen dat het inpakken verschrikkelijk veel tijd in beslag gaat nemen...

[Diadem]

Het hangt er gewoon helemaal van af wat je comprimeerd.

Elk willekeurig algoritme zal altijd een gemiddelde compressie halen van 0% bij willekeurige invoer.

Maar ja, invoer is natuurlijk niet willekeurig. Het hangt er helemaal vanaf wat je inpakt...

[Palomar]

die demo's van the product en aardbei zien er echt vet uit Heb je nog meer links naar dit soort demo's? Of zo'n soort screensaver?

[Anoniem: 41684]

http://www.scene.org
http://www.pouet.net (review site met ongeveer alle demos ooit)
http://ths.demoscene.org
http://www.monostep.org/demo/

[Blue-eagle]

Je kunt nooi alles in 1 bit kwijt zal ik maar zeggen maar 100 mb in 0.5 mb stouwen moet nog wel lukken, denk ik. Met de goede algoritmes, en een groot decompressie programma..

Misschien dat AI wat gaat toevoegen in de toekomst. Dan kies je of je een game, vcd, mp3 of datafile wilt decompressen, en aan de hand van andere keuzes zal het programma de beste keuzes maken voor z`n compressie.

Maarja, misschien lul ik wel weer te interessant ik wacht het wel af.

[woutertjez]

Op zondag 09 december 2001 23:47 schreef Wirf het volgende:
Je kunt een bestand oneindig comprimeren, ga maar na, als je bij de comprimeerder en decomprimeerder afspreekt dat "a" staat voor 40GB aan nullen, dan heb je al een compressieratio van 100% (eigenlijk iets van 99,9999999999[..] maar door afronding word het 100%)

Beetje onzin natuurlijk. Op deze manier kan je maar een beperkt aantal combinaties van bytes comprimeren. Hier zeg je dat 40 miljard bytes gelijk kan stellen aan eentje.

[FCA]

Je kunt wiskundig aantonen dat compressie van willekeurige data niks zal opleveren.
Uitleg:
Stel, je hebt een bestand van 4 miljoen bits. In principe zijn er 2^4.000.000 (best veel, op zich ) van dat soort bestanden. Stel nu dat je elk bestand daarvan op z'n minst 1 bit kon comprimeren. Dan zouden en op z'n hoogst 2^3.999.999 verschillende bestanden van 4 miljoen bits zijn. Maar, al die bestanden van 4 miljoen bits zijn verschillend. We hebben dus een tegenspraak, dus onze aanname dat we elk bestand kunnen comprimeren geldt niet.

Hoe kunnen we dan wel bestanden op onze computer comprimeren? Door te kijken naar patronen. Menselijk gegenereerd (of computer gegenereerde ) bestanden bevatten veel patronen. Daar kan dus veel bespaard worden, door te kijken naar korte bitvolgordes die niet gebruikt worden, en die te vervangen door een langere bitvolgorde die vaak gebruikt wordt.

Elke compressie verhoogt de entropie (willekeurigheid, platgezegd), en een perfecte compressie zal de entropie maximaal laten worden, wat mogelijk is voor een filegrootte. Ik geloof zelfs dat entropie in deze vorm behouden blijft, en dus kun je de maximale compressie uitrekenen (bereken entropie bestand, kijk welke naar minimale file-size die deze entropie kan bevatten).

[Mx. Alba]

De beste compressie heb je als het resultaat 100% ruis is. Maar ook dat klopt niet helemaal, want als je 100% ruis neemt, en daar tel je een signaal bij op, dan is het resultaat nog steeds 100% ruis, maar is niet gecomprimeerd. Het is slechts geëncodeerd - immers, als iemand aan de andere kant precies weet welke ruis is gebruikt, kan hij dat er weer aftrekken om het originele signaal terug te krijgen.

Een voorbeeldje pure ruis:

code:

14159 26535 89793 23846 26433 83279 50288 41971 69399 37510 58209 74944
59230 78164 06286 20899 86280 34825 34211 70679 82148 08651 32823 06647
09384 46095 50582 23172 53594 08128 48111 74502 84102 70193 85211 05559
64462 29489 54930 38196 44288 10975 66593 34461 28475 64823 37867 83165
27120 19091 45648 56692 34603 48610 45432 66482 13393 60726 02491 41273
72458 70066 06315 58817 48815 20920 96282 92540 91715 36436 78925 90360
01133 05305 48820 46652 13841 46951 94151 16094 33057 27036 57595 91953
09218 61173 81932 61179 31051 18548 07446 23799 62749 56735 18857 52724
89122 79381 83011 94912 98336 73362 44065 66430 86021 39494 63952 24737
19070 21798 60943 70277 05392 17176 29317 67523 84674 81846 76694 05132
00056 81271 45263 56082 77857 71342 75778 96091 73637 17872 14684 40901
22495 34301 46549 58537 10507 92279 68925 89235 42019 95611 21290 21960
86403 44181 59813 62977 47713 09960 51870 72113 49999 99837 29780 49951
05973 17328 16096 31859 50244 59455 34690 83026 42522 30825 33446 85035
26193 11881 71010 00313 78387 52886 58753 32083 81420 61717 76691 47303
59825 34904 28755 46873 11595 62863 88235 37875 93751 95778 18577 80532
17122 68066 13001 92787 66111 95909 21642 01989 38095 25720 10654 85863
27886 59361 53381 82796 82303 01952 03530 18529 68995 77362 25994 13891
24972 17752 83479 13151 55748 57242 45415 06959 50829 53311 68617 27855
88907 50983 81754 63746 49393 19255 06040 09277 01671 13900 98488 24012
85836 16035 63707 66010 47101 81942 95559 61989 46767 83744 94482 55379
77472 68471 04047 53464 62080 46684 25906 94912 93313 67702 89891 52104
75216 20569 66024 05803 81501 93511 25338 24300 35587 64024 74964 73263
91419 92726 04269 92279 67823 54781 63600 93417 21641 21992 45863 15030
28618 29745 55706 74983 85054 94588 58692 69956 90927 21079 75093 02955
32116 53449 87202 75596 02364 80665 49911 98818 34797 75356 63698 07426
54252 78625 51818 41757 46728 90977 77279 38000 81647 06001 61452 49192
17321 72147 72350 14144 19735 68548 16136 11573 52552 13347 57418 49468
43852 33239 07394 14333 45477 62416 86251 89835 69485 56209 92192 22184
27255 02542 56887 67179 04946 01653 46680 49886 27232 79178 60857 84383
82796 79766 81454 10095 38837 86360 95068 00642 25125 20511 73929 84896
08412 84886 26945 60424 19652 85022 21066 11863 06744 27862 20391 94945
04712 37137 86960 95636 43719 17287 46776 46575 73962 41389 08658 32645
99581 33904 78027 59009 94657 64078 95126 94683 98352 59570 98258 22620
52248 94077 26719 47826 84826 01476 99090 26401 36394 43745 53050 68203
49625 24517 49399 65143 14298 09190 65925 09372 21696 46151 57098 58387
41059 78859 59772 97549 89301 61753 92846 81382 68683 86894 27741 55991
85592 52459 53959 43104 99725 24680 84598 72736 44695 84865 38367 36222
62609 91246 08051 24388 43904 51244 13654 97627 80797 71569 14359 97700
12961 60894 41694 86855 58484 06353 42207 22258 28488 64815 84560 28506
01684 27394 52267 46767 88952 52138 52254 99546 66727 82398 64565 96116
35488 62305 77456 49803 55936 34568 17432 41125 15076 06947 94510 96596
09402 52288 79710 89314 56691 36867 22874 89405 60101 50330 86179 28680
92087 47609 17824 93858 90097 14909 67598 52613 65549 78189 31297 84821
68299 89487 22658 80485 75640 14270 47755 51323 79641 45152 37462 34364
54285 84447 95265 86782 10511 41354 73573 95231 13427 16610 21359 69536
23144 29524 84937 18711 01457 65403 59027 99344 03742 00731 05785 39062

Als je output er zo uit ziet heb je dus maximale compressie.

[Johannes Verelst]

Voor compressie moet je inzien dat je met talen bezig bent: je zet iets van de ene taal (bijvoorbeeld een nederlandse tekst, plaatje, etc) om in een andere taal (zip, lha, rar, etc.)

Het probleem wat je nu moet oplossen: stel ik heb een zin van 1000 tekens uit taal1, kan ik deze omzetten in een zin in taal2 die korter is? Voor veel talen (1) kan dat, kijk bijvoorbeeld naar het nederlands. Een woord 'computer' heeft betekenis, maar de tekenreeks 'fqafefbas' niet. Je moet dus weten hoeveel procent van de mogelijke zinnen ook daadwerkelijk tot taal1 behoren. Als je dat weet (voor engels is dat goed bekend, rond de 20% als ik me niet vergis) dan kan je inzien dat je niet oneindig kan comprimeren: je moet namelijk een 1-op-1 relatie hebben tussen zin in taal1 en in taal2.

Voorbeeldje: ik heb een zin van 100 letters, hier zijn er 26^100 van. We weten dat 20% hiervan goede zinnen zijn, dus dat wordt 0.2 * 26^100.
Ik ga het omzetten in een gecomprimeerde file waar alle 256 bytes mogelijk zijn. Deze file heeft minimale grote 'n' waar geldt dat:

256^n = 0.2 * 26^100
log(256^n) = log(0.2 * 26^100)
n * log(256) = log(0.2) + 100 * log(26)
n = 59

Als ik alle mogelijke nederlandse zinnen van 100 tekens in een even grote file wil kunnen comprimeren, zal deze minimaal 59 tekens lang moeten zijn.

Natuurlijk zijn er ook truukjes waarmee je voor bepaalde zinnen van 100 tekens kortere files kan maken, maar als prijs betaal je daarvoor dat je niet ALLE zinnen van 100 tekens meer in 59 tekens op kan slaan.

[Confusion]

Wizard_of_OS schreef:
[waar, maar:]

Je moet nog wel ergens de sleutel verbinden aan de zin. Als je ergens een centrale database met alle zinnen hebt, dan kan je met je n=59 alles aanduiden. Zonder een referentie aan de oorspronkelijke zin (die ook opslagruimte kost) weet je niets. Ik vind je beschrijving een beetje kort door de bocht, omdat deze voorbijgaat aan het reduceren van de hoeveelheid noodzakelijke data en slechts een manier om in minder data naar hetzelfde te verwijzen geeft.

[FCA]

Op maandag 10 december 2001 17:11 schreef Fused het volgende:

[..]

Je moet nog wel ergens de sleutel verbinden aan de zin. Als je ergens een centrale database met alle zinnen hebt, dan kan je met je n=59 alles aanduiden. Zonder een referentie aan de oorspronkelijke zin (die ook opslagruimte kost) weet je niets. Ik vind je beschrijving een beetje kort door de bocht, omdat deze voorbijgaat aan het reduceren van de hoeveelheid noodzakelijke data en slechts een manier om in minder data naar hetzelfde te verwijzen geeft.

Is dat dan niet het idee van loss-less compressie?
Goed, lossy compressie doet het 2de, maar dat is iets heel anders, en werkt niet met programma's en veel data, eigenlijk alleen met muziek, film en plaatjes....

[Anoniem: 39486]

Op maandag 10 december 2001 15:44 schreef FCA het volgende:
Je kunt wiskundig aantonen dat compressie van willekeurige data niks zal opleveren.
Uitleg:
Stel, je hebt een bestand van 4 miljoen bits. In principe zijn er 2^4.000.000 (best veel, op zich ) van dat soort bestanden. Stel nu dat je elk bestand daarvan op z'n minst 1 bit kon comprimeren. Dan zouden en op z'n hoogst 2^3.999.999 verschillende bestanden van 4 miljoen bits zijn. Maar, al die bestanden van 4 miljoen bits zijn verschillend. We hebben dus een tegenspraak, dus onze aanname dat we elk bestand kunnen comprimeren geldt niet.

[..]

Nice, hier een andere manier om hetzelfde te zeggen:

Stel we hebben een compressie methode die elke willekeurige verzameling data kan compressen. Dan kun je door herhaald toepassen van dat algoritme op een bepaalde invoer:

compress(compress(compress(...(compress(data))...)))

elke verzameling data tot 1 bit verkleinen, maar dat kan niet want met 1 bit kun je maar 2 verzamelingen data coderen. Tegenspraak.

[Anoniem: 40038]

Het compressen van data is dus alleen mogelijk als er bepaalde patronen in te ontdekken zijn. Om een voorbeeld te geven:

101010101010101010101010101010101010101010101010101010101010

kan ik comprimeren door de hele data te vervangen door dit:
zet '10' 30 keer achter elkaar.

Nu heeft deze instructie natuurlijk meer data nodig dan het origineel, maar als het verandert in: zet '10' een miljoen keer achter elkaar, dan kan ik er winst uit halen. Je kunt dus niet ieder willekeurige bit-string comprimeren, maar diegene met patronen WEL. En diegene met patronen bestrijken het overgrote deel van de toepassingen.

[Johannes Verelst]

Op maandag 10 december 2001 17:11 schreef Fused het volgende:

[..]

Je moet nog wel ergens de sleutel verbinden aan de zin. Als je ergens een centrale database met alle zinnen hebt, dan kan je met je n=59 alles aanduiden. Zonder een referentie aan de oorspronkelijke zin (die ook opslagruimte kost) weet je niets. Ik vind je beschrijving een beetje kort door de bocht, omdat deze voorbijgaat aan het reduceren van de hoeveelheid noodzakelijke data en slechts een manier om in minder data naar hetzelfde te verwijzen geeft.

waar ... maar ...
Het ging hier om een theoretisch maximum aan compressie, _hoe_ dat moet zeg ik er niet bij

Als ik wel wist hoe het moest zou ik gelijk millionair zijn denk ik, 59 tekens is in dit voorbeeld het minimum (weer er van uit gaande dat je _alle_ zinnen uit de brontaal in gemiddeld 59 tekens wil opslaan). Hoe dat moet ... geen idee, maar beter dan 59 tekens zal het in ieder geval nooit kunnen (dat was de vraag ook dacht ik).

[Anoniem: 38797]

het theoretisch minimum is 2bit, voor een bestand met bijvoorbeeld alleen maar 'A' erin staan 9 keer kun je een compressietechniek schrijven die maar 1 letter aankan in compressie en die op schrijft in de vorm "aantal x letter;letter" krijg je dus een 10 bits bestand 'AAAAAAAAA' wat wordt gecomprimeerd naar 2 bits '9A'

en in percentage is het verband bijna een hyperbool

hoe meer A's je neemt hoe groter de compressie

bijv. 1 miljoen A's =

10^6*A

als je het comprimeerd

nou dan maak je van 1 miljoen bits dus 6 bits

[Confusion]

Wizard_of_OS schreef:
Het ging hier om een theoretisch maximum aan compressie, _hoe_ dat moet zeg ik er niet bij

Als je de vraag op die manier opvat heb je natuurlijk helemaal gelijk.

[Anoniem: 29081]

Voor elke compressiemethode kan ik een brok data verzinnen die door die compressor minstens zo groot blijft. En in vrijwel alle gevallen (in ieder geval bij alle zinnige compressiemethoden) kan ik er zelfs een verzinnen die GROTER wordt.

Het maximum van een compressiealgorithme in absolute zin is dus 0% (compressie dat is, geen enkel algorithme kan dus ook maar een enkel bitje compressie garanderen).

[TERW_DAN]

Het ligt er gewoon aan hoe de machine gebouwd wordt. Als we met Quantum computers en Q-bits gaan werken, denk ik dat de compressie wel eens heel hoog zou kunnen worden.

[Anoniem: 27440]

Op maandag 10 december 2001 22:19 schreef DKtje het volgende:

nou dan maak je van 1 miljoen bits dus 6 bits

nee, 6 bytes! een bit kan alleen maar 1 of 0 zijn! en 8 bits(oftewl een byte) geeft genoeg combinaties om alle tekens in te zetten, 1 teken neemt dus 1 byte in.

maar ik had onder wiskunde ook een idee hoe je in theorie alles samen kan vatten in 1 bit! ik ben het nu aan het uitwerken, en als het wat word(mijn c++ kwaliteiten zijn niet je van het ) zal ik het wel posten. Ik zal vast wel een denkfout gemaakt hebben, zo slim ben ik namelijk niet, maar tot zo ver klopt mijn theorie nog

[Anoniem: 29081]

Nou, hou maar vast op dan, want het kan nooit

Je kunt geen algoritme bedenken wat elk stuk data comprimeert tot iets kleiners.

Stel namelijk dat je wel zo'n algoritme hebt. Dan kun je dus data van N bits compressen tot een nieuw stuk data van M bits (waarbij M < N).

Het aantal mogelijke brokken data van M bits is 2^M. Je hebt echter meer mogelijke combinaties voor de brondata (namelijk 2^N, wat minstens 2 keer zoveel is), er zijn dus verschillende bron data's die comprimeren tot dezelfde compressed data. Slim algoritme dat dan nog kan uitmaken tot welk origineel het moet worden uitgepakt.

Dat idee van 1 bit is helemaal bizar. Probeer het maar ff met 3 txt files van 1 byte elk, eentje met een A, een met B, en eentje met een C erin. De A wordt een 0, de B wordt een 1, voor die C heb je dan al geen combinaties meer over.

En ook quantumcomputers kunnen aan dit principe NIETS veranderen.

[Anoniem: 27440]

Op dinsdag 11 december 2001 18:28 schreef Juggalin_Juggalo het volgende:
Nou, hou maar vast op dan, want het kan nooit

Je kunt geen algoritme bedenken wat elk stuk data comprimeert tot iets kleiners.

Stel namelijk dat je wel zo'n algoritme hebt. Dan kun je dus data van N bits compressen tot een nieuw stuk data van M bits (waarbij M < N).

Het aantal mogelijke brokken data van M bits is 2^M. Je hebt echter meer mogelijke combinaties voor de brondata (namelijk 2^N, wat minstens 2 keer zoveel is), er zijn dus verschillende bron data's die comprimeren tot dezelfde compressed data. Slim algoritme dat dan nog kan uitmaken tot welk origineel het moet worden uitgepakt.

Dat idee van 1 bit is helemaal bizar. Probeer het maar ff met 3 txt files van 1 byte elk, eentje met een A, een met B, en eentje met een C erin. De A wordt een 0, de B wordt een 1, voor die C heb je dan al geen combinaties meer over.

En ook quantumcomputers kunnen aan dit principe NIETS veranderen.

het zit anders in elkaar ik ben al een stuk verder en het klopt nog steeds! ik vraag wel of de C-goeroe van school me helpt met uitwerken

[Anoniem: 37240]

Als je wil weten hoeveel er nu al mogelijk is moet je even hier: http://compression.ca/act-win.html kijken.
Ik heb me ook al eens een tijdje met compressie bezig gehouden. En ik denk dat de beste algoritmes die algemeen toepasbaar en lossless zijn binnen 1% van het maximaal haalbare afzitten. Maar compressie kan nog wel een stuk verbeterd worden door voor elk bestandsformaat een apart algoritme te gebruiken.

[Anoniem: 27440]

Op dinsdag 11 december 2001 19:02 schreef borganism het volgende:
Als je wil weten hoeveel er nu al mogelijk is moet je even hier: http://compression.ca/act-win.html kijken.
Ik heb me ook al eens een tijdje met compressie bezig gehouden. En ik denk dat de beste algoritmes die algemeen toepasbaar en lossless zijn binnen 1% van het maximaal haalbare afzitten. Maar compressie kan nog wel een stuk verbeterd worden door voor elk bestandsformaat een apart algoritme te gebruiken.

waarop baseer je dat dan?

[Confusion]

Op dinsdag 11 december 2001 16:23 schreef terw_dan het volgende:
Het ligt er gewoon aan hoe de machine gebouwd wordt. Als we met Quantum computers en Q-bits gaan werken, denk ik dat de compressie wel eens heel hoog zou kunnen worden.

Ach man, zwam toch niet over zaken waar je geen verstand van hebt. Kan je me enig algoritme voor een quantum computer laten zien? Zonee, hoe kan je dan in vredesnaam iets denken te weten over compressie?!

Ik heb het zo gehad met al die mafkezen, vooral op dr frontpage, die altijd maar uit hun nek kletsen over quantum computers zonder er ook maar ene ruk van te weten...

[Anoniem: 19725]

mp3 is toch niet alleen compressie?
er worden toch ook geluids freqeunties weggelaten die we niet kunnen horen, en bepaalde tonen na andere die we als mens toch niet kunnen opmerken?

[joepP]

Op woensdag 12 december 2001 09:23 schreef Gladiator het volgende:
mp3 is toch niet alleen compressie?
er worden toch ook geluids freqeunties weggelaten die we niet kunnen horen, en bepaalde tonen na andere die we als mens toch niet kunnen opmerken?

Klopt, dat is dus lossy compressie, het originele
signaal wordt niet bit voor bit behouden. Denk aan mp3, wma, mpeg, etc etc. Vooral beeld & geluid dus.

Er is ook lossless compressie, dat is wat hier bedoeld wordt. Hierbij blijft de data exacte behouden. Denk aan zip, rar, arj, lzh, etc etc.

[Confusion]

joepP schreef:
Klopt, dat is dus lossy compressie, het originele
signaal wordt niet bit voor bit behouden. Denk aan mp3, wma, mpeg, etc etc. Vooral beeld & geluid dus.

Er is ook lossless compressie, dat is wat hier bedoeld wordt. Hierbij blijft de data exacte behouden. Denk aan zip, rar, arj, lzh, etc etc.

Op zich zou je lossless compressie (dat definierende als compressie waarbij geen oorsprongelijke informatie verloren gaat) wel lossy kunnen implementeren (dat definierende als compressie waarbij tijdens het compressie proces de informatie niet eenduidig aanwezig is) denk ik. Je zou iets kunnen bedenken waardoor bijvoorbeeld een bitwaarde van 0.85 voor kan komen, wat dan het gevolg van loss is, waar 1 bedoelt wordt. Maar misschien zou zo'n proces aan beperkingen (qua bestandsgrootte oid.) onderhevig zijn...

[Anoniem: 29081]

het zit anders in elkaar ik ben al een stuk verder en het klopt nog steeds! ik vraag wel of de C-goeroe van school me helpt met uitwerken

Anders dan wat? Lees nou nog ff goed wat ik schreef, je kunt niet een compressie algoritme maken wat elk stuk data tot iets kleiners comprimeert. Indien je denkt van toch, dan gebruik je ergens stiekem extra data of heb je het niet meer over digitale informatie.

[joepP]

Op woensdag 12 december 2001 10:56 schreef Fused het volgende:

[..]

Op zich zou je lossless compressie (dat definierende als compressie waarbij geen oorsprongelijke informatie verloren gaat) wel lossy kunnen implementeren (dat definierende als compressie waarbij tijdens het compressie proces de informatie niet eenduidig aanwezig is) denk ik. Je zou iets kunnen bedenken waardoor bijvoorbeeld een bitwaarde van 0.85 voor kan komen, wat dan het gevolg van loss is, waar 1 bedoelt wordt. Maar misschien zou zo'n proces aan beperkingen (qua bestandsgrootte oid.) onderhevig zijn...

Dat zou je kunnen doen ja, maar dan hebben we het nog steeds over lossless compressie. De digitale data die je er in stopt komt er immers weer exact zo uit. Dat is ook zoals jpg kan werken: als je zeer hoge kwaliteit instelt (practisch lossless dus) hou je alleen geen compressie meer over.

Ik denk niet dat de lossy methodes erg geschikt zullen zijn voor lossless compressie. Maar wie weet wat de toekomst zal brengen

[Anoniem: 27440]

Op woensdag 12 december 2001 13:48 schreef Juggalin_Juggalo het volgende:

[..]

Anders dan wat? Lees nou nog ff goed wat ik schreef, je kunt niet een compressie algoritme maken wat elk stuk data tot iets kleiners comprimeert. Indien je denkt van toch, dan gebruik je ergens stiekem extra data of heb je het niet meer over digitale informatie.

Waarom kan dat niet? leg mij dat eens uit! ik heb nog geen wiskundig bewijs gezien dat het niet kan. maar ook al is dat er wel: het werkt nog steeds goed tot nu toe(de theorie dan he ) het inpakken gaat dan wel even duren, maar het resultaat mag er wezen.

ach, waar praat ik eigenlijk over een vage theorie xie wel wat het word

[Anoniem: 40038]

Goed, laten we zeggen dat er WEL een algoritme is die iedere willekeurige hoeveelheid data can compressen zonder verlies van data.

notatie: f(s) waarbij f() verwijst naar de algoritme en s de datastring is (bestaand uit 1's and 0's) die je erin stopt.

Dan kunnen we een nieuw algoritme bedenken dat deze informatie nog kleiner maakt, simpelweg door:

d(s) = f(f(s)) het nesten van de algoritme.

Maar: e(s) = f(d(s)) = f(f(f(s)))
Dit kan oneindig lang doorgaan totdat de uitkomst bestaat uit een datastring van 1 bit. 0 of 1.

Echter, we kunnen aantonen dat het niet mogelijk is om uit 1 bit een EENDUIDIGE 2-bit string te halen. Dat wil zeggen, de omgekeerde berekening (waarbij er 1 bit ingaat en er meerdere uitkomen) is NIET eenduidig. Oftewel, als de omgekeerde bereking niet mogelijk is, dan is de eerste berekening ook niet mogelijk. En omdat de berekening door het nesten van dezelfde algoritme werkt, werkt die berekening niet.

Bovendien is het niet mogelijk om een 1-bit string verder te comprimeren. Dus uiteindelijk is de data-string maximaal gecomprimeert. Maar we gingen er juist van uit dat f(s) IEDER willekeurige string (dus ook de string: 1) verder kon comprimeren.

Ergo, er bestaat GEEN algoritme die willekeurig iedere data-string kleiner kan maken dan hij al was.

[Anoniem: 27440]

Op woensdag 12 december 2001 15:19 schreef marcelvdpol het volgende:


Ergo, er bestaat GEEN algoritme die willekeurig iedere data-string kleiner kan maken dan hij al was.

dat zeg ik ook niet! kleiner dan 1 bit akn het echt niet
maar ach, wat boeit het ben bijna klaar, dan zal ik um hier posten zodat jullie um af mogen kraken...

[Anoniem: 13700]

Ten overvloede nogmaals, er zit een maximum aan lossless compressie, een hoogste entropie. Bij sommige vormen van lossless compressie wordt er al gerekend met "delen van bits" (arithmetische compressie), waardoor deze algoritmes beter comprimeren dan Burroughs-Wheeler/Lempel-Ziv/Huffman compressors (zoals zip, bzip, arj enz).

Sidejoke: Overigens heeft jaren geleden een student ontdekt hoe je kleine tekstbestanden lossless tot een filesize van 0 bytes kunt comprimeren, 10 punten voor iedereen die bedenken kan hoe

[FCA]

Hmmm...
laat me raden. Maximale grootte zo'n 259 tekens voor Windows, en zo'n 11 tekens voor een DOS versie van dit "compressie" programma?

[Anoniem: 13700]

Op woensdag 12 december 2001 16:31 schreef FCA het volgende:
Hmmm...
laat me raden. Maximale grootte zo'n 259 tekens voor Windows, en zo'n 11 tekens voor een DOS versie van dit "compressie" programma?

Tien punten voor FCA

[Anoniem: 27440]

Op woensdag 12 december 2001 16:34 schreef mietje het volgende:

[..]

Tien punten voor FCA

LOL tis wel een goeie

[FCA]

Voor een andere random data "compressie", lees

http://www.geocities.com/patchnpuki/other/compression.htm

[Varienaja]

Ik hoorde eens een cool verhaal van een 'nieuw revolutionair' compressie algoritme. En inderdaad: elk mp3-bestandje (of whatever bestandje) werd 10x zo klein. Wel groeide de c:\windows\system32\bladiebla\diepe map\onzichtbaar nogal

Iedereen was erg enthousiast, totdat iemand dit merkte. Alle bestanden werden dus ergens anders heengekopieerd, en die 10x zo kleine bestandjes waren niet meer dan een soort snelkoppeling daarnaartoe

[Turboman]

Om deze topic een iets andere wending te geven:
(Zal Melkor vast niet erg vinden hij is namelijk mijn broertje )

Ongeveer 2 eeuwen gelededen heeft een Franse wiskundige, Jean-Baptiste Joseph Fourier, aangetoond dat het mogelijk was een curve weer te geven als een functie. Een curve is gewoon een of andere lijn zoals dit:

code:

       /---\
--  /     \     /---------\
  \    /     \___/       \
   \__/              \
                       \___

Zo'n functie zou dan bestaan uit een helehoop sinussen en cosinussen.

Maar wat ik me nou zat af te vragen: Muziek / geluid bestaat ook uit een curve (golf). Als je nou een algorithme weet te verzinnen wat van een stuk muziek, dus een hele lange ingewikkelde golf, een functie kan maken, dan heb je een ontzettend goede compressie methode voor geluid gevonden. Een methode waarbij zelfs de kwaliteit van de muziek gewaarborgt blijft.

Mmmm ik ga weer's wat C++...

[Anoniem: 27031]

Compressiemethode op compressiemethode op.....

Het beste coderingsprogramma zou zijn het bekijken per compressie of er compressie ontstaat. Daarnaast zit er dan ook een compressiemethode in per een reeks bytes.
Het ligt er maar net aan hoe de bytes van een file eruit zien en of een compressiemethode 1 of 2 het korter maakt. (inclusief de byte die aangeeft welke methode er wordt gehanteerd).

Het belangrijkste lijkt op dit moment wel de tijd die het (de)comprimeren in beslag neemt. ik moet er niet aan denken dat er al meer dan een minuut over een (de)compressie ga zitten wachten

[Anoniem: 40038]

Eh, ja, dat is de Fourier Transformatie.

Voor diegene die Seti@home draaiien (dat zullen er wel een boel zijn) De data die je thuis gestuurt krijgt bestaat uit een signaal. Het Seti@home programma maakt er een fourier transformatie van en dan komt het signaal eruit als een som van sinussen. IPV een signaal met amplitude over de tijd is er dan de opdeling van het signaal in frequentie en de amplitude van de sinus die bij die frequentie hoort.

[Turboman]

Zo te horen kost zo'n Fourier transformatie een hoop rekenkracht (seti@home). Maar het gaat hier dan ook om hele grote, lange signalen (toch...)

Misschien dat een stuk muziek veel "kleiner" is dan zo'n signaal en zo op een gewone pc te transformeren is naar een wiskundige functie ???

[FCA]

Zo'n fourier-transformatie wordt gebruikt bij veel dingen. Volgens mij ook bij MP3 encoding, maar dat weet ik niet zeker. Wat een aankomende techniek is, zijn wavelets. Daarin worden niet cosinussen en sinussen gebruikt, maar meer algemenere functies, daardoor kan de tijd-resolutie mogelijk verbeterd worden. Of dat is mij verteld. Veel ervan snappen doe ik niet.

[Anoniem: 40260]

Op dinsdag 11 december 2001 16:23 schreef terw_dan het volgende:
Het ligt er gewoon aan hoe de machine gebouwd wordt. Als we met Quantum computers en Q-bits gaan werken, denk ik dat de compressie wel eens heel hoog zou kunnen worden.

of niet

[Anoniem: 29081]

Hmmm...
laat me raden. Maximale grootte zo'n 259 tekens voor Windows, en zo'n 11 tekens voor een DOS versie van dit "compressie" programma?

Hah! Die student was een n00b dan! Ik kan er 263 van maken voor windows, en 13 voor dos!

[Anoniem: 40038]

Eh? Is dat echt een bestant van 0 bits, of is het omdat windows als bestandsgrootte 0 bits geeft? Nogal een verschil.

[Anoniem: 29081]

spock13 schreef: Waarom kan dat niet? leg mij dat eens uit! ik heb nog geen wiskundig bewijs gezien dat het niet kan.

Zie mijn post daarboven met 2^N enzo. Da's geen formeel wiskundig bewijs (die van marcel is beter wat dat betreft), maar daar heb ik in normale woorden uitgelegd waarom het nooitkan.

maar ach, wat boeit het ben bijna klaar, dan zal ik um hier posten zodat jullie um af mogen kraken...

Graag, ik kan niet wachten!
Maar no shit, ik wil je niet afzeiken ofzo, ik hoop dat je vooral doorgaat en iets leuks uitvindt! Maar een algoritme wat elke data (ok, elke data groter dan een bepaald minimum aantal bits dan) compresst tot iets kleiner, bestaat NIET.

[Anoniem: 29081]

Eh? Is dat echt een bestant van 0 bits, of is het omdat windows als bestandsgrootte 0 bits geeft? Nogal een verschil.

Echt 0 bits. Het date/time field in een directory entry is 2 bytes En in windows heeft een file zelfs 3 van die timestamps (created, last modified, en last openend), echter het 'last opened' veld gaat verloren als je het bestand bekijkt, dus die tel ik maar ff niet mee dan

[Varienaja]

Op woensdag 12 december 2001 19:35 schreef Turboman het volgende:
Maar wat ik me nou zat af te vragen: Muziek / geluid bestaat ook uit een curve (golf). Als je nou een algorithme weet te verzinnen wat van een stuk muziek, dus een hele lange ingewikkelde golf, een functie kan maken, dan heb je een ontzettend goede compressie methode voor geluid gevonden. Een methode waarbij zelfs de kwaliteit van de muziek gewaarborgt blijft.

Op zich leuk, maar je brengt een stuk muziek echt niet terug tot een simpele functie als y=sin(x). Ik gok zelfs dat de fourrier-reeks groter is om op te slaan dan de WAV.

[Anoniem: 29081]

Op zich leuk, maar je brengt een stuk muziek echt niet terug tot een simpele functie als y=sin(x). Ik gok zelfs dat de fourrier-reeks groter is om op te slaan dan de WAV.

Even groot dan nog altijd
Anders had je trouwens een fijn nieuw compressiealgoritme: beschouw random data als fourier componenten en sla dan maar de wav op de daaruit komt.

Hoewel fourier data even groot is als het bijbehorende geluid, kun je uit fourier data veel makkelijker dingen weglaten (bijv. alles boven deze of deze freq horen we toch niet, dus chop, of ingewikkelder zoals MP3 doet). Bovendien zit er meestal een simpeler (dwz beter compressbaar) patroon in fourier data dan in rauwe "wav" vorm.

[joepP]

Op donderdag 13 december 2001 11:18 schreef Varienaja het volgende:

[..]

Op zich leuk, maar je brengt een stuk muziek echt niet terug tot een simpele functie als y=sin(x). Ik gok zelfs dat de fourrier-reeks groter is om op te slaan dan de WAV.

Je brengt een stuk muziek dus echt wel terug tot een (even grote) verzameling sinussen en cosinussen. Dat is exact de basis van mp3. En exact het principe van Fourier transformatie. Ga maar eens op internet rondsnuffelen

[Witte]

Kijk even hier

[Confusion]

Hmmm... die site noemt voor het gemak Nyquist maar helemaal niet, terwijl hij 20 jaar eerder al met het sampling theorema kwam.

[Anoniem: 29081]

(uit andere thread)
niet dat het altijd kleiner werd... maar waarom kan iets wat een 1 of een 0 is maar 2 waardes bevatten? dat ontgaat me

Ehm, nou, tel ze maar. Stel, je wilt iets in 1 bit opslaan, en dat 'iets' kan 2 waardes aannemen. Laten we zeggen: het kan A of B zijn. Dan heb je de keuze tussen ofwel A=0 en B=1, of A=1 en B=0. Heb je nou 3 waardes, dwz hetgeen je in 1 bit wilt opslaan kan A, B of C zijn, dan heb je een probleem. Je het maar 2 mogelijke bitwaarden (0 of 1), dus je moet 2 letters opslaan met dezelfde bitwaarde. Maar dan kun je bij het uitpakken nooit meer weten wat het was.

[Anoniem: 29081]

(edit) oh, laat maar.. oude & verkeerde topic