Forum för vetenskap och folkbildning

I förra veckans Metro Teknik stod följande artikel att läsa:
http://www.metro.se/se/article/2007/09/ ... /index.xml

Enligt artikeln kan en ny metod komprimera redan komprimerad data upp till 6 ggr. Det är strängt taget inte omöjligt på något sätt, men det får onekligen varningsklockorna att ringa. I artikeln påstås att ALL data kan komprimeras ytterligare, vilket definitivt är nonsens. Man kan aldrig komprimera data mer än vad som finns täckning för i resultatet. Om resultatfilen blir säg 4 byte lång, innehåller den 32 bitar och kan absolut maximalt koda för 2^32 olika okomprimerade filer förlustfritt.

Huruvida komprimeringen är förlustfri går inte att utläsa ur artikeln. Visseligen står det: "Programvaran som används kallas PAC , Pro Alias Compression, och är en så kallad icke-förstörande komprimering. Det innebär att ingen data går förlorad som med många andra komprimeringsmetoder. Ali Majeed är väldigt förtegen om exakt hur tekniken fungerar men påstår att filerna kan halveras upp till sex gånger med hans metod. PAC öppnar sedan filen till ursprungsstorlek igen.".

Ickeförstörande, alltså förlustfri komprimering. Så långt allt väl. Men sedan, längre ner, står det: "– Om du skickar in en mp3-fil får du tillbaka en mp3-fil och skickar du in en jpeg-bild får du tillbaka en jpeg-bild, förklarar han.
En viss kvalitetsskillnad uppstår vid komprimeringen och förstärks ytterligare för varje halvering. Detta beror på så kallat vitt brus och kan enligt Ali Majeed enkelt filtreras bort."

Vitt brus? Vitt brus?!? Vitt brus ska inte kunna introduceras någonstans i en förlustfri komprimering, och sällan i en förstörande komprimering heller. Jag vet inte tillräckligt mycket, men jag skulle tro att "bruset" som uppstår vid förlustkomprimering inte har formen "vitt" brus, utan någon annan form. Men det vet jag inte säkert.

Men ändå, antingen är en algoritm förlustfri eller så är den det inte. Några mellanting finns inte. Och att komprimera MP3 och jpeg 6 ggr kanske inte är stört omöjligt, men definitivt otroligt. T.ex. jpeg kan komprimeras ungefär 30% genom att man avkodar bildern och komprimerar cosinustransformationerna separat.

För mig luktar detta "snake oil". Kommentarer?

"halveras upp till sex gånger" låter som mycket dålig journalistik.

(Det blir en division med 2^6 istället för en division med 6.)

Dessutom är påståendet att all data kan komprimeras obegripligt eftersom även resultatet av denna komprimering är data. Går det då alltid att komprimera den komprimerade datan ytterligare?

Japp, efter tillräckligt många steg kommer all data komprimeras till en bit, en etta eller nolla. En viss kvalitetsskillnad uppstår som sagt, men det är nog bara att köra PAC-algoritmen baklänges så kommer ursprungsdata tillbaks igen (dränkt i vitt brus förstås, men det är ju bara att köra genom ett filter...).

Påminner om den där indiern som skulle lagra gigabyte i bilder. Omskriven på forumet.

Inte orkat läsa texten men förlustfri komprimering är i princip så bra den kan bli. Det finns ju en teoretisk gräns för hur mycket man kan komprimera någonting och den är baserad på dataströmmens entropi. När entropin är maximerad finns det ingen möjlighet att minska utrymmet datan tar utan att förlora någon information.

Entropi är ett mått på hur slumpmässig datan är. Maximal entropi för en bitström nås när nolla och etta är lika sannolika och oberoende av andra utfall. Om man undersöker en zippad fil kommer man se att den är i det närmaste helt slumpmässig. Jag skulle tro att en zippad fil på sin höjd kan komprimeras några enstaka procent mer.

Inte alls. Det är bara unzippa den och komprimera den med någon av de bättre program som finns. Zipformatet är långt ifrån idealt.

LZW, LHA, ARC, UC2, RAR, 7Z et cetera är alla olika bra på olika typer av data. PKZIP är kanske suboptimalt, men det är precis som Grim säger inte många procet som skiljer mellan ZIP och RAR+mediaflag till exempel, ens på den data som RARs medialäge är tillverkat för att hantera.

5%enheter är visserligen en rätt stor skillnad i lossless-sammanhang, men det är ändå några enstaka procent totalt sett.

Nja. Riktigt är det, men då utgår du från "noll" igen. Algoritmer som är effektivare än zip (LZ77, deflate, Huffman etc) finns visseligen det flera av (RAR, PAQ, etc), men de flesta skulle ha svårigheter att packa en zippad fil mer än originalet. Att applicera algoritmen direkt på originalet är således mer effektivt än att packa zippningen. Det var nog det som Grim avsåg - att det är svårt att packa en redan packad fil.

Många moderna komprimeringsalgoritmer är specialiserade för vissa data, t.ex. ljud, bild, medicinska bilder, etc. Klart att man i teorin skulle kunna ta fram en "state of the art"-algoritm specialiserad på att packa just zipfiler, men det förefaller rätt meningslöst. Även ett gammalt format som zip producerar en så svåranalyserad output med mycket lite redundans.

Edit: Packnings- och bandbreddskvack har vi hört förr. För att bruka lite våld på termerna skulle man kunna säga att det är informationsteorins motsvarighet till evighetsmaskiner eller brott mot termodynamiken.

Edt2: Förtydligande. Jag nämde PAQ som packningssätt. Blanda inte ihop det med artikelns "PAC". PAQ (till skillnad från PAC) finns, fungerar och packar nog bäst. Men det är inte ett praktiskt alternativ på grund av enorma minnes- och cputids-behov. http://en.wikipedia.org/wiki/PAQ

Han är ju elektroingenjör så man får väl anta att han har läst lite signalteori och datakompression. Men om kompressionen lägger till (kvantiserings)brus så är den ju definitivt inte förlustfri. Så antingen driver han med oss eller så har journalisten missförstått.

Visst kan man som MBY skriver "packa upp" en jpeg-fil och komprimera om koefficienterna och vinna lite på det men kan skriver ju att metoden funkar på alla filer vilket borde innebära att den är en mera generell metod som inte är optimerad till en viss filtyp.

Nä, jag är skeptisk. Som redan har sagts så finns den en absolut gräns för hurmycket man kan komprimera data förlustfritt och de metoder som finns idag kan komma rätt nära. Det finns definitivt inte utrymme för att komprimera det en faktor 6 till (eller 64 gånger om man vill tolka det så )

Att ta fram en sådan "state of the art-algoritm" är trivialt. Det är bara låta den dekomprimera zipfilen som förprocessning och sedan packa den med en bättre metod. Varför skulle inte en sådan algoritm räknas menar du?

Förvisso, men varför skulle en sådan algoritm räknas då? Det kräver ett svar tycker jag, inte tvärt om. Det jag tolkade med Grims inlägg var ju att han - fullt riktigt - sa att en zipfil svåreligen kan komprimeras ytterligare, dvs det är redundansen i zipfilen som komprimeras, inte originalet. Visst har du strängt taget rätt, men det är ändå en rätt fånig sidodiskussion.

Jag har prövat att söka lite på kombinationer av "PAC", "Pro Alias Compression", "Ali Majeed", "compression", "Captus Innovations" på google och kammat exakt noll (utom orelaterade träffar) - förutom Metros artikel.

Jag kan inte finna ett patent eller patentansökan, jag kan inte finna någonting om algoritmen, inget om Ali Majeed förutom en abstact som handlar om robotar (http://www.nada.kth.se/utbildning/grukt ... /0214.html).

Så tills vidare faller domen: "humbug"

Edit: Förtydligande.

I varje fall dålig journalistik. Det finns inga förlustfria komprimeringsalgoritmer som fungerar på godtyckliga data så att skriva det är dålig journalistik. (Och i rubriken dessutom.) Och det kan knapast finnas några icke-förlustfria heller. För med godtyckliga data finns det ju inget sätt att veta vad som är viktigt och vad som är oviktigt i filen man komprimerar.

Men Majeed menar kanske att man kan stoppa in vilken typ av fil som helst i hans algoritm. Och så kan det mycket väl vara, det är bara det att han måste öka storleken i så fall på vissa filar om han minskar den på andra.

Påståendet att filerna kan halveras upp till sex gånger är å andra sidan inte orimligt, om man lägger märke till uttrycket upp till. Artiklen säger inte att alla filer kan komprimeras till en 1/64-del. Å andra sidan så kan ju redan dagens algoritmer uppnå det när datakällan har låg entropi så det säger inte så mycket om hurvida algroritmen är bra.

Jag har ingen aning om hur nära dagens komprimeringsalgoritmer i digitalteve är till Shannongränsen så jag kan inte spekulera i om det finns utrymmer för stora förbättringar eller inte.

Jag skulle gissa att det är humbug men jag är inte helt säker. Det är möjligt, om man läser artiklen snällt, att Majeed verkligen uppfunnit en ny komprimieringsalgoritm, som kanske är bättre än de nuvarande och att journalisten sedan missuppfattat hans ensidiga men sannfärdiga beskrivning av den.

Problemet förstärks av Majeeds inlägg i kommentarstråden under artikeln. Där ursäktar han sig att "vitt brus" uppkommer genom att "brus alltid tillkommer signaler", vilket ju är sant i fysikaliska sammanhang, men inte har någon relevans här.

Om det verkligen är Majeed som kommentaret i tråden så hamnar han definitivt i humbug-kategorin. Av det skälet som du nämnar, och för att han inte tar avstånd från felatktigheterna och oklarheterna i artiklen.