"Doorbraak compressietechniek onmogelijk"

Een paar dagen geleden schreven we over een nieuwe compressiemethode die zonder dataverlies tot honderd keer zou kunnen comprimeren. Het bedrijf ZeoSync zou dit in samenwerking met een aantal gerenommeerde Amerikaanse universiteiten bereikt hebben. Wegens het ontbreken van een concrete publicatie zijn specialisten echter nog wel uitermate sceptisch over de nieuwe methode.

Huidige technologieën die data zonder verlies verkleinen, waarvan ZIP het bekendste is, comprimeren gegevens vaak nog niet eens twee maal. Een betere compressie van muziek en beeldmateriaal is wel mogelijk, maar mechanismen zoals bijvoorbeeld respectievelijk MP3 en JPEG zijn niet zonder verlies. Een analist van het bekende onderzoeksbureau Forrester Research vertelt dan ook dat het volgens hem gewoonweg onmogelijk is, wat het bedrijf beweert.

ZeoSync vergist zich, of anders werkt het principe alleen in zeer selectieve gevallen, aldus de wetenschapper. ZeoSync vermeldt echter duidelijk in haar persbericht dat het gelukt is om 'praktisch willekeurige informatieseries' in grootte te kunnen reduceren. Binnen enkele weken is het bedrijf van plan een publieke demonstratie te geven, waar uiteraard met spanning naar uitgekeken wordt, aldus WebWereld.

Reacties (127)

[GarBaGe]

Compressie werkt over het algemeen door informatie wat slimmer op te schrijven en te ordenen en herhalende patronen eruit te filteren.
Daar een benadering van de originele data te gebruiken kan compressie nog flink worden verhoogd (MP3, JPG, MPG etc) maar gewoon nog "ff factoortje 100" is mijns inziens onmogelijk.

Vector-compressie is ook lossy en gebruikt een AI-achtig principe om de allerbeste compressie te vinden voor een plaatje. En deze methode maakt plaatje nog veel kleiner dan JPG (en mooier), maar dan praat je over factor 25-30 beter. Maar vergeet niet dat je compressietijd omhoog gaat van een paar millisecs naar minuten (op huidendaagse PCs) voor 1 plaatje

Het enige voordeel van Vector compressie is dat decompressie sneller is dan wat dan ook. Dus ideaal voor videokaarten met gecomprimeerde textures. Texture comprimeren gebeurd dan 1 keer als een game wordt gemaakt en decompressie kost veel minder bandbreedte en veel minder tijd dan andere compressie technieken of zelfs zonder compressie techniek

[Verwijderd]

Vector-compressie is ook......

Alles wat je daar zei ging over fractal compressie. Een voorbeeld van Vectorcompression is de Huffman-encoding. En dat wordt weer in het RAR formaat gebruikt. Dit formaat is totaal niet lossy.

Meer info over Fractal compression:
http://links.uwaterloo.ca/fractals.papers.html

knock yourself out

[Verwijderd]

Ik geloof dat huffman wel zowat overal wordt gebruikt. Ik meen mij te herinneren dat de header van een zip-file gecodeerd wordt met een vaste huffman-codetabel. Natuurlijk is dit niet het hoofd-compressie-algoritme.

[jvo]

Klopt, is een soort de facto standaard en is volgens mij niet gepatenteerd. Heeft overigens helemaal niks met vectorcompressie te maken.

Huffman pakt in door veel voorkomende bytes (of andere eenheden) een kortere bitcode te geven en minder vaak voorkomende een langere. Het algoritme doet dit ook nog eens bewezen optimaal, maar houdt verder geen rekening met patronen.

[jp]

De compressie tijd maakt me niet zo veel uit... als het decomprimeren maar snel gaat

[boner]

Wel lullig dan voor de mensen met een realtime broadcast van een of andere nieuws site.

Life beelden van CNN of zow? Als dan de compressie 1 uur duurt kun je net zo goed niets doen......

Maar ik ben het met je eens decomressietijden zijn ALIJD belangrijk en is korter beter.

[The Noid]

Yep, en een perfect random datastream is niet te comprimeren omdat er te weinig herhaling in zit.

Grote compressie halen kost veel rekenkracht. Als iemand nou es een algoritme ontwikkelde om een mod/s3m/it module te maken van een geluidsfile

[trenjeska]

JAAAA eindelijk iemand die nog aan modules denkt. Dacht ff dat iedereen dat al opgegeven had
Is een mooie vorloper om toch kleine maar leuke muziek bestandjes te hebben en nog beter ripbaar en bewerkbaar ook!

[AdLentis]

Er zijn al wel programma's om wav om te zetten naar midi, dus naar mod moet ook geen probleem zijn...

[Verwijderd]

hehe dat leek me nou ook altijd zo'n goed idee toen ik nog trackte. Waarom maakten ze niet allemaal .xmetjes van nummers.. die zijn toch veel kleiner? Kwam er natuurlijk wel een miliseconde later achter dat zoeits totaal onmogelijk is, maar toch

[Verwijderd]

naar minuten ? pff
jpeg2000 is echt wel rap genoeg
ga jij d'r maar es echt induiken, dan zie je dat zelf ook..

minuten ? wat een grap een vette 3dsmax scene render je in minuten, niet een gecomprimeerd plaatje

edit:

mijn fout dat ik dacht dat je decompressie bedoelde, maar dan nog vind ik 't onzin

[jvo]

Bij een tijd van minuten werd gedoeld op vectorcompressie. En dat klopt echt wel. Voor een beetje goede fractalcompressie mag je nog wel een stuk meer tijd uittrekken.

[Verwijderd]

Daar een benadering van de originele data te gebruiken kan compressie nog flink worden verhoogd (MP3, JPG, MPG etc) maar gewoon nog "ff factoortje 100" is mijns inziens onmogelijk

zeg nooit: "nooit"

de huidige coderingstheorie (zip/rar etc) is nog steeds gebaseerd op gewichtsbomen en prefixcodes.
Dat is een duur woord voor alle veel gebruikte bitreeksen vervangen door een korte bitreeks (de prefix) en weinig voorkomende bitreeksen vervangen door langere prefixcodes. Met de daaruit voortkomende bitreeks en de vertaling ervan kun je het weer makkelijk decoderen.

Dit is uiteraard de simpele versie van winzip, die ongetwijfeld allerlei slimmigheidjes ingebouwd heefd.

Soms zie je wel eens dat het verpakte bestand groter is dan het bestand zelf !! probeer maar eens een simpel tekstbestandje bestaande uit 10 verschillende letters in te pakken.. dan denk je toch echt: "dit is toch wel een hele dikke verpakking" Dit komt omdat winzip de vertaling en allerlei onzin ook nog moet opslaan..

Om een lang verhaal kort te maken, dit is maar een manier en je weet nooit wat voor slimmigs die lui nu weer uitgevonden hebben..

[Verwijderd]

Ik weet niet of er hier ooit een thread over verschenen is, maar ik heb vorige maand in een belgisch magazine een interview gelezen over een kerel die het voor mekaar speelt om meerdere films op een CDR te proppen die full-screen de kwaliteit van DVD benaderden, let wel, 'meerdere' films op 'één' CDR. Ook kon hij bijv een grafisch bestand van pakweg 30MB verkleinen tot 1KB ofzo. De redeactie van het magazine mocht tijdens de compressie niet aanwezig zijn dus het kan niet 100% geverifiëerd worden, maar ze hebben dus wel dat bestandje van 1Kb zien openen met de originele foto. Dus als dit kan, dan geloof ik ook best dat ZeoSync dit kan. Maar we zullen zien als beiden (want die kerel zou binnen afzienbare tijd ook zijn uitvinding publiek demonstreren) ook daadwerkelijk de bewijzen leveren!

[RG]

Een plaatje comprimeren van 30 MB hoeft echt niet moeilijk te wezen. Als alle pixels dezelfde kleur hebben is het gewoon een kwestie van de afmetingen opslaan en laten opvullen met die kleur. Je maakt mij niet wijs dat je een foto die uit je digitale camera komt in 1 Kb kan opslaan...

[Verwijderd]

Regelmatige lezers van news:comp.compression weten dat er zich ongeveer elk halfjaar iemand (lees persoon of bedrijf) meldt met een 'doorbraak' op het gebied van compressie technologie. Vaak zijn de claims fantastisch: 100:1 lossless, 100 dvd's op 1 cdr, of nog 'beter'. Genoemde personen en/of bedrijven zijn vrijwel zonder uitzondering volledig onbekend, zeker binnen het vakgebied.

In Nederland hebben we onlangs nog gezien in de vorm van Jan Sloot die beweerde 16 volledige speelfilms op een chipcard met 64 kilobyte ram op te kunnen slaan. Volgens de Quote (feb 2001) zijn o.a. Roel Pieper en de ABN erin gestonken maar Jan Sloot --- die zo paranoide was als maar kan --- heeft zijn geheim (zo dat er al was ) meegenomen in zijn graf. De verhalen (hier en hier) over de demonstratie van zijn vinding zijn bijzonder leuk leesvoer.

Voor de twijfelaars het advies subject 9 te lezen uit de comp.compression FAQ.


edit: url toegevoegd

[Verwijderd]

100 op 1? dat is niks

Kan me nog goed herinneren toen een kennis tegen me zei dat hij iets van 10 spellen op een 3.5" disk had gezet.... (spellen zoals unreal kwa formaat) Ja en hij had winzip gebruikt e.d.... Ik verklaarde hem voor gek maar hij moest en zou het bewijzen... Achteraf bleek dat hij de snelkoppelingen had gezipt.

[/waargebeurd]

edit:
Whoops verkeerde thread

[procyon]

Misschien is het wel een grote stunt
Is het een beursgenoteerd bedrijf, waar sommige mensen heel erg rijk van zijn geworden

[Verwijderd]

Is het "binnen enkele weken" soms al 1 april?

[agent327]

Inderdaad, snel even de koers omhoog jagen.

[BadRespawn]

veel kans dat die er met terugwerkende kracht alsnog arm van worden.

[v0LrAtH]

Het is quasi onmogelijk om 'praktisch willekeurige informatieseries' met 100x te verkleinen want dit zou betekenen dat je het gecompresseerde bestand nog eens 100x zou kunnen verkleinen enzovoort en zoverder ... Puur verzinsel zou ik denken

[machiel]

Wat ik me zo voorstel is dat je bijvoorbeeld de punten van een parabool op slaat in een tabel (bv 1, 2, 4, 9, 16, 25, 36...250000) Als je nou een compressie-algoritme hebt dat herkent dat het om de punten op een parabool gaat hoeft deze alleen de functie van de parabool op te slaan (en eventueel het domein). Op die manier kan je de tabel opslaan als de functie y = x^2, 1 - 500) in plaats van vijfhonderd getallen. Dat is een enorme winst (en die functie kan je niet opnieuw inpakken)

[jvo]

Whoho, ik hoor hier een hoop dingen door elkaar.

Het idee van de functie is op zich niet slecht. Je maakt dan een procedurele beschrijving van de data. Probleem is wel dat het erg moeilijk (zo niet practisch onmogelijk) om bij willekeurige data een goede procedurele beschrijving te vinden. De parabool gaat niet overal op passen

Bij fractalscompressie wordt gezocht naar herhaling in bijvoorbeeld een plaatje. Een kleinere sproet wordt dus opgeslagen als 0,8 maal een grotere sproet. Ook het vinden van deze herhaling is erg tijdrovend, maar wel redelijk mogelijk.

Bij vectorcompressie wordt gepoogd de functies van contouren te vinden. Dit is een vorm van procedurele beschrijving, maar staat daar dus niet gelijk aan.

Wat alle bovenstaande technieken wel gemeen hebben is dat ze nooit kunnen bepalen of ze de optimale oplossing gevonden hebben. Of dat ze er ook maar in de buurt van zitten.

[0rbit]

Ja, leuk... dan heb je een parabool... en dan?

Digitale informatie zit meestal niet zo eenvoudig in elkaar aangezien informatie nu juist in het ontbreken van regelmaat zit en in veel mindere mate in regelmaat zelf.

[Verwijderd]

Een dergelijke techniek gebaseerd op fractals bestaat al....

[raptorix]

En dat heet nou een vector bestand
Maar punt is dat je niet zo makkelijk vectoren maakt van realtime beelden simpelweg omdat dit vrijwel altijd met kwaliteits verlies teweeg gaat.

[Verwijderd]

[naïef mode]

Dat woord 'praktisch' geeft aan dat het niet in alle gevallen geldt, dus bijvoorbeeld niet voor reeds met de techniek gecomprimeerde bestande.

[naïef mode]

[The Noid]

Het woord practisch wordt gebruikt omdat echt random data niet te genereren is. `Practisch willekeurige datastreams' betekend gewoon 'elke datastream'

Helaas is het onmogelijk om 'ieder bestand van N bytes te comprimere tot N-1 bytes'

Stel we hebben alle bestanden van 64 bits groot. dit zijn dus 2^64=1.8E19 bestanden.
we gaan die allemaal comprimeren tot 63 bits...
Er zijn maar 2^63=9.2E18 verschillende bestanden van 63 bits, dit zijn er minder dan van 64.
Een aantal bestanden van 64 bits zijn dus gecomprimeerd tot HETZELFDE bestand van 63 bits... hoe wou je 2x hetzelfde bestand ooit weer decomprimeren tot 2 verschillende bestanden?

DUS:
Een (elk) algoritme dat bepaalde bestanden verkleint zal andere bestanden vergroten.

[Ortep]

Dat kan dus niet. Zodra je gecomprimeerd hebt is de reeks niet meer willekeurig. Je kan dus niet aan de gang blijven.

[Verwijderd]

Dit hadden de meeste tweakers dus ook al bedacht. Het verschil was gewoon te groot om waar te zijn.

[Verwijderd]

Zeg nooit "onmogelijk" als je niet alle feiten hebt... Het is niet totaal onmogelijk dat een nieuw revolutionair algoritme ontwikkeld wordt waar niemand ooit aan had gedacht.

En ik vraag me alleen af of de gemiddelde tweaker de technische kennis heeft om te kunnen beoordelen of iets wel of niet mogelijk is.... Soort van beste stuurlui verhaal.....

[Verwijderd]

Ehmm. ONMOGELIJK!

Zoek de platte driehoek met zijden van 3, 4, en 9 cm.....

Dat kan je zelf ook wel uitrekenen dat dat niet kan. In dit geval is het iets ingewikkelder, maar: HET KAN NIET!

Zie eventueel mijn reactie op het originele bericht hier op tweakers of op slashdot.

Rogier.

[Verwijderd]

waarom, als er een specifiek algoritme bij elke compressiesessie wordt gegenereerd , kost beetje CPU maarja, een xp 1900 zou dan met een 100MB proggie (wat dus 1 mb wordt+algoritme van paar MB) een weekje bezig zijn, dan is de data 100x verkleind, niet gesroken over het algoritme wat erbij zit, kom je totaal op een factor 10 ongeveer(gemiddeld, zijn erg veel uitersten), maar het KAN

[Verwijderd]

Zeg nooit "onmogelijk" als je niet alle feiten hebt...

In jouw driehoek verhaaltje heb je wel alle feiten... Dus kan je idd gerust zeggen dat het onmogenlijk is.

Maar over die compressiemethode... Eerst zien dan geloven

[Psychostase]

//offtopic

Uiteindelijk werd er 15 jaar geleden ook gedacht dat het onmogelijk was kleindere computers te maken dan een zaal en kijk nu eens... er ging ook niet meer dan 650MB op een schijfje ter grote van een CD en nu hebben we DVD.

Het is inderdaad dat de wonder de wereld nog niet uit zijn. Maar het is onzin om cd - dvd en computer-revolutie als argument te geven. Dit is echt geen "alternatieve manier van denken" Het is vooruit borduren op oude techniek. Ze kunnen alles gewoon steeds kleiner maken. In de nieuwste generatie processor zijn er meerdere transistor nodig dan de voorgaande generatie, die transistors zijn alleen kleiner geworden, netzo als een DVD kleiner gaatjes en meerdere lagen, dus meer bitjes bevat.

En een bitje is een bitje hoe klein dat bitje ook is.

Ik wacht weer op het volgende broodje aap verhaal.

[Verwijderd]

Off-topic, maar....
Volgens mij is één van de principiële axioma's van de 3D ruimte dat drie punten altijd in een vlak liggen. Hoe zou een niet-platte driehoek er dan uitzien?

[The Noid]

In 3D hoeven de zijden niet recht te zijn.

[Verwijderd]

lol

B.T.W.

Dit zal niet een doorbraak zijn alleen voor de 'telefooner' maar helemaal voor de illigale warez sites... een spel van 800 mb... word 8 mb! dat betekend voor kabel 10 minuuten ( @HOME ) , dus is dit goed voor ons... of juist enorm slecht voor de economie ( kwa games en software )

we zien het binnenkort

[Verwijderd]

offtopic:
Goed dat je platte driehoek zei, ik dacht net te replyen dat het wel ging in een 3D ruimte

Alle gekheid op een stokje, dit is nu al de 2e die beweert zo'n techniek uitgevonden te hebben, Guillaume Defossé beweert net hetzelfde van zijn "DGS" en die techniek zou gebaseerd zijn op

een digitale taal van meer dan 72000 tekens

, aldus Defossé zelf.

Waarom zou het niet mogelijk zijn? Uiteindelijk werd er 15 jaar geleden ook gedacht dat het onmogelijk was kleindere computers te maken dan een zaal en kijk nu eens... er ging ook niet meer dan 650MB op een schijfje ter grote van een CD en nu hebben we DVD. Etc etc, wat ik gewoon wil zeggen is, een alternatieve manier van denken kan altijd een revolutie betekenen, just give the guys some slack...

Als het BS is zullen ze zichzelf zo al genoeg belachelijk maken nietwaar?

Nog even dit:

Ingenieurs kijken naar de huidige grenzen van de technologie en beginnen die dan te verkennen en te verleggen. Ik vertrek van het standpunt dat er geen grenzen zijn...

(uit Netwerk 01/2002, het artikel over DGS)

[Olaf van der Spek]

'praktisch willekeurige informatieseries'

Is de uitvoer van dit algoritme misschien ook weer een praktisch willekeurige informatieserie?
Dan kunnen we 100^2 keer beter comprimeren ;->

[leonardo1504]

Jeroen Vonk schreef:

Zeg nooit "onmogelijk" als je niet alle feiten hebt... Het is niet totaal onmogelijk dat een nieuw revolutionair algoritme ontwikkeld wordt waar niemand ooit aan had gedacht.

Het is aantoonbaar niet mogelijk. Ieder compressie algoritme maakt maar een beperkt aantal bestanden kleiner. Zo is er ook een set bestanden voor elk compressiealgoritme dat juist groter wordt. Zip werkt erg goed voor tekst, gif voor tekeningen, en jpg voor foto's.
Het zit zo: Neem een verzameling die bestaat uit alle bestanden ter grootte van n bits. Dan zijn er dus 2^n verschillende bestanden. Als je een bestand wil representeren in bits dan heb je daar dus weer n bits voor nodig. Wil je comprimeren, en dus minder dan n bits gebruiken om een bestand te representeren, dan heb je in principe twee keuzes:

1. Er gaat informatie verloren : bestanden die erg op elkaar lijken kan je niet meer van elkaar onderscheiden. De zogenaamde 'lossy' algoritmen als MPEG en JPEG gebruiken deze vorm van compressie.
2. Er gaat geen informatie verloren, je kan alle mogelijke bestanden van oorspronkelijk n bits nog van elkaar onderscheiden. Maar je wilde kleinere bestanden, dus zoek je een algoritme dat deelverzameling van bestanden die je ook werkelijk zal gebruiken (bijvoorbeeld: je weet al dat je alleen tekstbestanden gebruikt) kleiner maakt. Dat impliceert dus dat daar tegenover een deelverzameling van bestanden bestaat die bij gebruik van dit algoritme juist groter wordt, anders kan je niet meer elk bestand representeren. Dit zijn in geval van zip bijvoorbeeld alle bestanden die gezipte bestanden zijn. (Anders zou je een gezipt bestand kunnen zippen, en dat weer kunnen zippen, etc. tot je nog maar 1 bit over houdt. Daarmee kun je echter maximaal twee verschillende bestanden representeren en van elkaar onderscheiden).

Veel plezier, ook zonder alle algoritmes van tevoren te kennen kan je dit soort zaken bewijzen. Eens in de zoveel tijd staat er iemand op die beweert dat hij wel alle algemene bestanden enorm kan comprimeren zonder informatieverlies. Net zoals er af en toe iemand met de aankondiging van een perpetuum mobile komt, of beweert de hoekdriedeling met passer en lineaal te hebben opgelost.

[Verwijderd]

Tja een muziek bestand of een film bestand kun je best comrimeren, je hebt dan te maken met het oog of het oor foppen. Bij mp3 op 1op8 merk je geen verschil in kwaliteit maar het is er wel, ook bij zeer goede DivX'en is het zeer fraai.
MAAR data bestanden kunnen niet met foefjes gecomrimeerd worden. een 0 is een 0 en een 1 is een 1.
Zip, RAR,ACE, RJ zijn allemaal aan elkaar gewaagd.

De proffesor met zijn verhaal in het graf

[Brent]

offtopic:
Maar cab is het beste (met LZH compressie. Ik kom dan altijd een procent 5-10 onder rar uit. toch mooi meegenomen).

[Access]

Ze hebben hun techniek natuurlijk op een txt bestandje uitgeprobeerd

[hellbringer]

Ze hebben hun techniek natuurlijk op een txt bestandje uitgeprobeerd

Zeker een leeg text bestand (met alleen maar spaties) zoals deze
(400MB .txt file gecomprimeert met ZIP naar 397KB)

Dit type zip file stond beter bekend als 'ansibom' en werden ooit gebruikt om Bulletin Board Systems (BBS) lam te leggen.
Ooit nog een proggie voor geschreven in TurboPascal

[tikimotel]

1 gigabyte textfile gevuld met a's past dan wel op 1 floppy als je hem inpakt.

[Verwijderd]

Dan is het zeer nuttig voor toepassing op internet..

[wildhagen]

Valt wel mee... hoeveel .TXT-files ken jij op Internet? Meeste is toch .ASP of .HTM(L) ofzo...

[The Noid]

Goh... en wat IS HTML...??

nou??

Jaaa... TEXT

[Verwijderd]

is toch ook gewoon tekst

too late...

[Cipri]

Alsof er zo'n gigantisch verschil is tussen een txt en een html bestand. html zou zelfs nog beter compressen

[Verwijderd]

Zelfs dan zou ik het nog zeer knap vinden hoor.

[RG]

Op een simpel txt bestand kan je sowieso al een behoorlijke compressie ratio halen, aangezien je als je aan in tekst toch hoogstens 40 tekens gebruikt, terwijl er 256 mogelijk zijn. met een beetje slim comprimeren, frot je dan wel een aantal tekens in 1 byte. En dan nog herkennen van structuren, moet je toch een heel eind kunnen komen, vooraal bije en groot tekst bestand...

[pilo2710]

Ja, maar als het mogelijk is, dan is het wel mooi..

Het moet kunnen, want er was een keer een documantaire over een vent uit Nederland die een slimme manier van programmeren had uitgevonden. Je kon iets van 3 films op een chipcard kwijt.. Kreeg hartaanval en code is niet meer gevonden..

Maar ik hoop wel dat het mogelijk. Het zal een hoop ruimte schelen

[Rudi Vader]

Dat verhaal staat hier http://www.tweakers.net/nieuws/15456 te lezen. Roel Pieper is er ooit mee bezig geweest en heeft er in de diversen actualiteitenprogramma's over gesproken. Die man was naar Philips (waar Roel Pieper werkte) toegelopen maar zagen niets in het systeem en toen is Roel Pieper er zelf mee aan het lobbyen geweest. Diverse investeerders over de hele wereld hebben het zien werken en er was een dusdanig godsvermogen voor geboden dat de hartkleppen van de man, ene Jan Sloot, gesneuveld zijn.
Er zou een demonstratie model van zijn. Het zou dus mogelijk moeten zijn.

[Verwijderd]

Belg, Antwerpenaar denk ik, staat met een artikel in het huidige nummer multimedia magazine "netwerk" met zijn versie... de interviewers zouden hem opgezocht hebben en een demonstratie gekregen hebben...

Misschien hebben jullie hier nog al van gehoord: "20 volledige films op 1 doodnormale cd" en nee, geen dvd of dergelijke, of niet overburned

een file van slechts "+-700 bytes" blijkt heuse kwaliteitsfoto te zijn en rolt na enkele seconden al uit de printen voor het afdrukken...

De man is al sinds z'n jeugd bezig met het anders oplossen van wiskundige dinges etc... en het verbeteren van allerlei andere dingen. Zo kwam hij tot een splinternieuwe compressie zoals andere... De man in kwestie zou een splinternieuwe "compresseertaal" bedacht hebben, bestaande uit meer dan 70.000 "dingskes" (sorry kan niet onmiddellijk op de naam komen ) waardoor zo'n compressietechniek zou mogelijk zijn

Extra nota: de films zouden (bijna) dvd kwaliteit zijn op volledig scherm, dus divx, EN het zou mogelijk zijn gewoon een filmpje af te spelen via de windows mediaplayer...

volgens mij is zoiets werkelijk mogelijk..

update:

dit is de link: www.cdfreaks.com/news2.php3?ID=2990



Digitale duizendpoot Defossé perst tot 20 films op een cd-rom

Een dvd-recorder kopen van 80.000 frank? Overbodig, als je het verhaal van Guillaume Defossé hoort. Hij slaagt er met zijn eigen computertaal DGS (Defossé Guillaume Systems) in om een volledige film - al gauw een paar gigabyte - te verkleinen tot slechts 30 MB. Goed nieuws voor de mobiele multimediamarkt. Of juist niet?

[Parlor_Inventor]

geloof jij in die hartaanval? Zo iemand zou een gevaar zijn voor de muziek- film- en softwareindustrie. Laatst ook een Belg die dergelijke dingen beweerde uitgevonden te hebben. Ook nix meer van gehoord....

[Verwijderd]

Ok, je kan een film vlugger illegaal downloaden, maar langs de andere kant is het dan pas echt interessant om films tegen betaling te laten afhalen.... Ze hadden die man vitamientjes moeten geven ipv hem neer te leggen

[Johannes Verelst]

Het valt me elke keer weer op dat op dit verhaal reacties komen als 'vroeger dacht men ook dat de aarde plat was' of dingen in die trend.

Het leuke van compressietechnieken is, dat het manipulatie is van informatie, en dat dus bepaalde wetmatigheden (uit de wiskunde en informatica) toepasbaar zijn. Dat betekent dus dat je er dingen over kan bewijzen: in de wiskunde zin. Bewijzen die niet weerlegbaar zijn, en waarmee je 'ware' uitspraken kan maken.

Alle reacties hierboven (zonder te flamen) kan je allemaal overbodig maken door gewoon voor jezelf het bewijs te geven dat lossless compressie van een willekeurige (en dan _echt_ willekeurige) rij bits onmogelijk is.

Het bewijs gaat ongeveer zo (ik heb geen zin om het helemaal formeel te doen, want dat bevordert de leesbaarheid niet).

1. Stel dat ik elke willekeurige string met een factor 100 kan comprimeren en dat ik later de oorspronkelijke string kan terughalen.
2. Neem een willekeurige string 's' van lengte 'n' bits.
3. Er zijn in totaal 2^n van deze strings mogelijk
4. Volgens (1) kan ik de string comprimeren tot lengte 'n/100'.
5. Van deze compressiestrings zijn er in totaal 2^(n/100).
6. Omdat ik (volgens 1) elke de string weer terug moet kunnen halen, is er een 1-op-1 relatie van compressie-string naar originele-string (een gecomprimeerde string kan maar naar 1 ongecomprimeerde string decomprimeren, anders zou ik een keuze moeten maken welke ik zou moeten kiezen tussen een aantal ongecomprimeerde versies)
7. Bij decompressie zijn er dus 2^(n/100) ongecomprimeerde strings mogelijk
8. Contradictie met punt 3.
9. De enige aanname die ik had gemaakt was punt 1, dus punt 1 kan niet waar zijn

Een zogenaamd "bewijs uit het ongerijmde".

edit:

Naar aanleiding van de reacties: de waarde 100 kan in het bewijs vervangen worden door elke waarde > 1, het was dus inderdaad netter geweest als ik ervoor een variabele had gebruikt. De waarde 100 had ik genomen omdat deze in het persbericht gebruikt werd.

Gelukkig had ik al vermeld dat het geen puur wiskundig bewijs zou zijn

[Verwijderd]

Meneer heeft ook een college TAAL&BEWIJS gevolgd.

Helaas is je deductie niet helemaal zuiver, aangezien het voor een andere waarde dan 100 ook niet zou werken, wat wel het geval is in de praktijk.

Maximale compressie is gerelateerd aan de mate van entropie van gegevens, ik zou daar nog maar eens wat meer over lezen.

mvg,
Martijn Kuipers

[Johannes Verelst]

Heb ik wel gedaan hoor, maar je kan bovenstaand probleem op meerdere manieren aanpakken.

Het bewijs uit het ongerijmde wat ik boven gaf kan je vervangen door het bewijs dat een random string entropie 1 heeft, de maximale compressie die een algoritme ooit kan bereiken kan je inderdaad ook uitdrukken in de entropie van de taal waarin de string zich bevind.

Wat de waarde 100 betreft, zie de edit

[Jochem]

Ik zou best hier heel intelligent op in willen gaan maar als ik de factor vervang met 2 in plaats van honderd.... Dan kom je nog steeds tot dezelfde conclusie.

Het feit wat je over het hoofd ziet is dat er aan patroon herkenning wordt gedaan binnen een set nullen/enen. heel simpel: het omschrijven van 000000 in 6 x 0.

Bij ZIP bereikt die een bepaalde complexiteit doordat patronen destijds werden bepaald door computerkracht benodigd door compressie/decompressie (uit de 8086 tijd!). Stel dat je nu in de encoder/decoder een hele berg patronen meegeeft en dat je zorgt dat de encoder heel slim die patronen uitkiest (eventueel gekruisd met modifiers) en een optimalisatie doet voor de patroonbeschrijving.
dan.... zou je theoretisch zeer hoge compressie kunnen krijgen.

Ik heb het geprobeerd in MATLAB een keertje en het werkte aardig. De grote van de compressiebloks waarop de patroonkeuze wordt geoptimaliseerd wordt bepaald door geheugenruimte. Ook valt of staat de compressiefactor bij de keuze van de patronen die ingebakken zitten in de de/encoder. Anyway... technisch allemaal.

[Johannes Verelst]

Ja, je hebt gelijk, een zuiverder bewijs zou de 100 ook als variabele hebben gehad, maar dat maakt voor het idee niet uit en ik heb de 100 hier genomen omdat het persbericht over een factor 1:100 spreekt.

Zodra er patronen in een tekst voorkomen kan je inderdaad deze gebruiken om te comprimeren, maar bij random strings schiet je daarmee niets op. Als je bijvoorbeeld alle patronen van 8 bits bekijkt: hiervan zijn er 256. Je moet alle patronen van 8 bits op kunnen slaan, dus als je een korte codering voor de ene string kiest, moet je een andere string met meer bits coderen. Op een puur-random string bereik je dus effectief niets, omdat alle patronen met even grote waarschijnlijkheid optreden. (ik heb het niet erg netjes geformuleerd nu, maar ik neem aan dat je begrijpt wat ik bedoel )

[procyon]

Ik weet dat lossless compressie wel mogelijk is.
kijk naar winzip.

Wat versta jij dan onder een "echt willekeurige rij bits"

willekeurig> 10100010001010101010101001010100101

stukjes 0000 kan je comprimeren
stukjes 101010 kan je comprimeren enz

dus leg even uit..

[Johannes Verelst]

Ik heb het hier over echt willekeurig: je weet van te voren NIETS over de rij bits die je krijgt.

Er is altijd compressie mogelijk op _bepaalde_ files, bijvoorbeeld:

- lossless compressie op files die maar een beperkte randomness (complexiteit) hebben. Bijvoorbeeld tekst-files: hier worden maar een beperkt aantal karakters gebruikt, dus daar kan je bij compressie rekening mee houden. Als je een programma maakt dat random bytes 'uitspuugt', dan kan geen enkel lossless compressie-algoritme er iets mee.

-lossy compressie
Hier gebruik je kennis van de informatie (bijvoorbeeld dat het muziek of beeld is) om bepaalde delen weg te halen die niet zichtbaar/hoorbaar zijn. Je gooit dus informatie weg, en daardoor kan je de overgebleven informatie efficienter opslaan.

[procyon]

Ja dat begrijp ik maar er is toch nooit een situatie waarin je niet van tevoren weet wat je in gaat pakken?

Zelfs al krijg je realtime willekeurige bits binnen dan cache je die toch tot je een pakketje hebt die je vervolgens toch weer kunt comprimeren?

[Zenuka]

Kijk deze man heeft zijn wiskunde huiswerk gedaan

[Verwijderd]

Maar volgens jouw bewijs kan je dan geen enkele willekeurige string comprimeren. Niet met een factor 2, niet met enige factor >1.

[Verwijderd]

Dat is niet waar. Het bewijs zegt niet dat je geen enkele string kan comprimeren, het zegt gewoon dat "er geen enkel algoritme kan bestaan dat IEDERE string van bepaalde lengte n kan comprimeren naar een string met bepaalde lengte m (met m < n)". Dit is logisch. Hoe kan je iedere string van 8 bits neerschrijven als 7 bits zonder iedere 7-bit code twee keer te moeten gebruiken?

Ik denk ook niet dat we moeten zoeken naar een algoritme dat bijna alle data goed kan comprimeren. Ik denk het eerder beter is om specifieke algoritmes te hebben die geschikt zijn voor bepaalde informatie. Ik heb het dan nog wel steeds over lossless compression (géén JPG, MP3, ...). Archivers zoals ACE en UHARC hebben een multimedia-compression optie waarbij er speciaal aandacht wordt besteed aan bepaalde types (executable, picture, sound, ...). Deze archivers hebben consistent een betere compression ratio dan 'gewone' archivers (ZIP bijvoorbeeld) op alledaagse data (dus geen random bitstream, maar wel een map op je hardeschijf). Bij random-appearing-data zijn ze 'maar' even goed.

[Verwijderd]

Natuurlijk kan je geen algoritme ontwerpen dat *iedere* datastream met een factor 100 kan comprimeren, maar bijvoorbeeld wel dat je het overgrote deel van mogelijke data verkleint, en slechts een klein deel vergroot. Ik zeg niet dat het vorige artikel geen grap is, maar ik heb zo het idee dat er maar al te vaak wordt gezegd "we hebben de limiet al bereikt met zip, ace, rar....". We hebben nu méér processortijd beschikbaar, dus kunnen we ook ingewikkeldere algoritmes gaan gebruiken die vroeger misschien niet toegepast werden door de tijdsfactor. Net de reden waarom dingen als DivX pas de laatste jaren zijn ontstaan: het moet snel genoeg (in het geval van video, realtime) gedecomprimeerd kunnen worden.