Run Length Encoding

[Verwijderd]

Ik moet een scriptie schrijven over MP3, en daar komt Run Length Encoding in voor.
Op de site waar ik mijn info vandaan haal wordt dat voorgesteld als 1 byte, in de vorm NNNNDDDD, waarvoor NNNN staat voor het aantal keer dat de 0 voorkomt, en de DDDD als de data, in dit geval dus alleen 0000. Dit is heel handig.
Maar ik ging er even over nadenken, en op deze manier kan je maar 16 0'en opslaan. (aangezien 2⁴ = 16).

Is dat dan wel zo'n handige methode? want dan kan je dus 16 0'en, die je normaalgesproken op zou slaan in 16 bytes, nu opslaan in 8 bytes. Dat is heel mooi, maar wat nou als je maar 2 nullen op hoeft te slaan. Dan krijg je dus mooi wel 8 bits om 2 bits (2 x een 0) op te slaan. Dus voor bepaalde waarden komt het echt heel mooi uit, maar voor andere waarden ook echt weer niet. Iemand een idee hierover? Is het gewoon gemiddeld zo dat deze manier van coderen je wel ruimte oplevert?

[Wouter Tinus]

2^4 = 16 ja, maar met 4 bits kun natuurlijk tellen van 0 tot 31 . Maar je hebt gelijk dat runlength-encoding op complexe data als een MP3 weinig effect heeft. Het is meer nuttig voor dingen als bitmaps en tekstfiles, en het *kan* de file inderdaad zelfs groter maken, omdat er ook aangegeven moet worden waar de overgangen zit tussen het NNNNDDDD formaat en het gewone DDDDDDDD-formaat.

[Verwijderd]

2^4 = 16 ja, maar met 4 bits kun natuurlijk tellen van 0 tot 31

huh?
in 4 bits heb je de eerste bit staan voor 8, de tweede voor 4, de derde voor 2 en de vierde bit staat voor 1 toch?

Dan heb je toch maximaal (als alle bits 1 zijn) 8+4+2+1 = 16 ?

Of heb ik iets gemist?

[Lord Daemon]

Er staat toch "NNNN maal DDDD"? Dan heb je dus maximaal 15 * "0000" = 60 nullen achter elkaar. Hoe je op 16 komt ontgaat me een beetje?

[Spaceman Spiff]

RLE kan heel inefficient zijn, daarom wordt er ook meestal met een bitje aangegeven of de volgende data RLE is of 'raw'.
In jou voorbeeld is het dan 15 keer '0000' (de data), dat zijn dan 60 '0'-en achter elkaar.

Ohja 8+4+2+1=15 volgens mijn rekenmachine

Deze getallen zijn officieel: 2^3 + 2^2 + 2^1 + 2^0 = 15, vandaar de verwarring van Wouter Tinus met 2^4.

[Lord Daemon]

Encoden wordt pas echt leuk als de kans op een '0' niet gelijk is aan de kans op een '1'. Dan kan je met typische en a-typische rijtjes gaan werken, en met wat mazzel best veel ruimte besparen.

[Verwijderd]

Een goede RLE schrijft alleen duplicaat tellers in de stream als er karakters inderdaad meermaals voorkomen. Een goede RLE is dus niet echt inefficient, hij maakt de stream alleen langer als er veel 2-karakter combinaties in zitten. Een goede RLE encode dus de stream "AAABCCCCD" naar "AA1BCC2D" en niet naar "4A1B4C1D".

Ik kan pseudocode posten voor het encoding en decoding algoritme, als er belangstelling voor is.

[ Voor 0% gewijzigd door Verwijderd op 25-10-2002 19:23 . Reden: verkeerd ge-encode ]

[Lord Daemon]

Verwijderd schreef op 25 oktober 2002 @ 19:17:
Een goede RLE schrijft alleen duplicaat tellers in de stream als er karakters inderdaad meermaals voorkomen. Een goede RLE is dus niet echt inefficient, hij maakt de stream alleen langer als er veel 2-karakter combinaties in zitten. Een goede RLE encode dus de stream "AAABCCCCD" naar "AA1BCC2D" en niet naar "4A1B4C1D".

Waarom niet naar "A3BC4D"? Overigens zou ik het wat inzichtelijker vinden als je het met '0'-en en '1'-en doet, want zo'n handige scheiding tussen letters en cijfers heb je normaal natuurlijk niet.

Ik kan pseudocode posten voor het encoding en decoding algoritme, als er belangstelling voor is.

Klinkt interessant.

[Verwijderd]

Lord Daemon schreef op 25 oktober 2002 @ 20:44:
Waarom niet naar "A3BC4D"? Overigens zou ik het wat inzichtelijker vinden als je het met '0'-en en '1'-en doet, want zo'n handige scheiding tussen letters en cijfers heb je normaal natuurlijk niet.

Juist omdat je geen scheiding tussen cijfers en letters hebt, codeer je de duplicaat-karakters 2x in de stream. Dat dubbele karakter is dan de scheiding tussen de karakters en de duplicaat-teller; of beter, een dubbel karakter in de encoded stream geeft het begin van een run aan, en het karakter erna de lengte van de run. (Het maakt overigens niet veel uit hoe groot zo'n karakter is, het hoeft niet percé een byte te zijn, daarom doe ik het niet in bits.)

Klinkt interessant.

Ik doe het maar in C, dat is bijna pseudocode

Encoding:

C:

int last = 0;
int c;
int count;
while ( ( c = getc( stdin ) ) >= 0 )  {
    putc( (char) c, stdout );
    if ( c == last ) {
        count = 0;
        while ( count < 255 && ( ( c = getc( stdin ) ) >= 0 ) ) {
            if ( c == last )
                count++;
            else
                break;
        }
        putc( (char) count, stdout );
        if ( count != 255 && c >= 0 )
            putc( (char) c, stdout );
    }
    last = c;
}

Decoding:

C:

int last = 0;
int c;
int count;
while ( ( c = getc( stdin ) ) >= 0 )  {
    putc( (char) c, stdout );
    if ( c == last ) {
        count = getc( stdin );
        while ( count-- > 0 )
            putc( (char) c, stdout );
    }
    last = c;
}

[Wouter Tinus]

Spaceman Spiff schreef op 25 oktober 2002 @ 18:24:
Deze getallen zijn officieel: 2^3 + 2^2 + 2^1 + 2^0 = 15, vandaar de verwarring van Wouter Tinus met 2^4.

Idd stomme fout

Zijn er eigenlijk (naast RLE en dictionairy-based systemen zoals RAR) nog andere belangrijke methodes voor lossless compressie? Ik vind het op zich jammer dat de ontwikkeling op dat gebied stil lijkt te staan.

[Lord Daemon]

[nohtml]

Verwijderd schreef op 25 oktober 2002 @ 22:54:
Ik doe het maar in C, dat is bijna pseudocode

Uhm ja. Ik snap er alleen niets van. Wat betekenen 'getc', 'stdin', 'putc' en 'stdout'?

[Verwijderd]

Lord Daemon schreef op 26 oktober 2002 @ 01:15:
[nohtml]
[...]
Uhm ja. Ik snap er alleen niets van. Wat betekenen 'getc', 'stdin', 'putc' en 'stdout'?

- getc pakt een character van een stream.
- putc plaatst een character op een stream.
- stdin is de 'standard input'.. de invoer stream, meestal verbonden aan de terminal waarin het programma is begonnen.
- stdout is de standard output.. de uitvoer stream, dat tevens wordt geplaatst waar het programma is begonnen.

[Verwijderd]

Zijn er eigenlijk (naast RLE en dictionairy-based systemen zoals RAR) nog andere belangrijke methodes voor lossless compressie? Ik vind het op zich jammer dat de ontwikkeling op dat gebied stil lijkt te staan.

Staat momenteel ook stil heb ik het idee ja.
Een ander encoding algoritme wat nog interessant is (en wat iedere zelf respecterende tweaker zou moeten kennen ) is Huffman-coding.
Kort samengevat gaat deze een string met letters, cijfers, whatever door en kijkt welk karakter hier het meest voorkomt. Dit meest voorkomende karakter wordt opgeslagen met 1 bit. Het daarna meest voorkomende karakter met 2 bits, dan 3 bits, 4 bits, etc ...

Als je meer wil weten: Google is je vriend!

edit:
typo

[Verwijderd]

Ik had geen tijd meer om het om te zetten in pseudocode, dus postte ik maar de source van een simpele rle filter. Dan nu toch maar de pseudocode als reprise

Encoding:

code:

laatste_karakter := 0
while <input> do
    read karakter
    write karakter
    if karakter = laatste_karakter then
        teller := 0
        while <input> and teller < 255 do
            read karakter
            if karakter = laatste_karakter then
                teller := teller + 1
            else
                goto xlus
            end if
        end while
xlus:   write teller
        if <input> and teller < 255 then
            write karakter
        end if
    end if
    laatste_karakter := karakter
end while

Decoding:

code:

laatste_karakter = 0
while <invoer> do
    read karakter
    write karakter
    if karakter = laatste_karakter then
        read teller
        while teller > 0 do
            teller := teller - 1
            write karakter
        end while
    end if
    laatste_karakter := karakter
end while

edit:
Toevoeging:

En de ontwikkeling in lossless compressietechnieken staat zo goed als stil, dat klopt. Daar is ook een goede reden voor, nl. dat de theoretisch best mogelijke lossless compressie al bereikt wordt door (hogere graads) arithmetische compressie... Aritmetische compressie is bv. beter dan Huffman encoding, omdat Hufman encoding een symbool im minimaal 1 bit codeert terwijl aritmetische compressie een veelvoorkomend symbool in minder dan 1 bit codeert. (Je vindt bijna geen aritmetische compressors op de markt omdat ze trager zijn dan Lempel-Ziv compressors en bijna alle aritmetische compressie-algoritmes gepatenteerd zijn.)

De laatste grote ontwikkeling waar ik over gehoord heb was de Burrows-Wheeler transform, een voorbewerking die Lempel-Ziv compressie in de buurt van aritmetische compressie brengt.

[Diadem]

Verwijderd schreef op 26 oktober 2002 @ 02:24:

edit:
Toevoeging:

En de ontwikkeling in lossless compressietechnieken staat zo goed als stil, dat klopt. Daar is ook een goede reden voor, nl. dat de theoretisch best mogelijke lossless compressie al bereikt wordt door (hogere graads) arithmetische compressie... Aritmetische compressie is bv. beter dan Huffman encoding, omdat Hufman encoding een symbool im minimaal 1 bit codeert terwijl aritmetische compressie een veelvoorkomend symbool in minder dan 1 bit codeert. (Je vindt bijna geen aritmetische compressors op de markt omdat ze trager zijn dan Lempel-Ziv compressors en bijna alle aritmetische compressie-algoritmes gepatenteerd zijn.)

De laatste grote ontwikkeling waar ik over gehoord heb was de Burrows-Wheeler transform, een voorbewerking die Lempel-Ziv compressie in de buurt van aritmetische compressie brengt.

Je verhaal ontgaat mij een beetje. Bedoel je met arithmetische compressie compressietechnieken die niet lossless zijn? Zoals mp3, jpg, mpg, etc? Want dat lijkt mij een logische verklaring, lossless compressie wordt niet meer ontwikkeld omdat lossy compressie veel en veel beter werkt voor bijna alle bestandtypes.

Er zijn altijd datasoorten die je niet lossy kunt opslaan, maar dat geeft niet, die nemen niet de bulk van de ruimte in. Een exe file van 3mb encode je met winzip iets van 50% ofzo, schrijf je een superieur algortime waarmee je hem tot 70% encode dan win je 600KB. Wat leuk is, maar niet zohard opschiet op een cd. Als daarentegen op diezelfde cd voor 300 MB aan filmpjes staat is het heel mooi als die de encoding daarvan kunt verbeteren van 90% naar 91%, namelijk 3MB.

Dus verdere ontwikkeling van lossless compressie is tegenwoordig eigenlijk min of meer overbodig.

En wat is een Lempel-Ziv compressor?

[Verwijderd]

Diadem schreef op 26 oktober 2002 @ 13:10:
Je verhaal ontgaat mij een beetje. Bedoel je met arithmetische compressie compressietechnieken die niet lossless zijn? Zoals mp3, jpg, mpg, etc? Want dat lijkt mij een logische verklaring, lossless compressie wordt niet meer ontwikkeld omdat lossy compressie veel en veel beter werkt voor bijna alle bestandtypes.

Nee, ik bedoel lossless compressie, arithmetische compressie is lossless en wordt bv. gebruikt in faxen. Arithmetische compressie werkt door de de bits in de input stream voor te stellen als een reeel getal tussen 0 en 1, er wordt als het ware een groot aantal binaire decimalen achter de komma berekend die de input stream representeren, zie hier voor een simpele uitleg van deze complexe materie.

En wat is een Lempel-Ziv compressor?

Lempel-Ziv is de meestgebruikte vorm van lossless compressie (oa. alle comp, lha, zip en rar programma's), die werkt door dubbele strings in de input stream te zoeken. Als er een dubbele string gevonden wordt dan wordt er een referentie naar de eerste string in de output geplaatst, ipv. de string zelf. Zie hier een animatie van LZ-compressie.

[Verwijderd]

He leuk animatie, houd ik wel van:
alleen een beetje trage compressie... is dit geen snellere LZ?

0	=(0)	= a	:a.b:baabbaababbaaaabaabba
1	=(1)	= b
2	=(0)+(1)	= ab	2:b.a:abbaababbaaaabaabba
3	=(1)+(0)	= ba	23:ab.ba:ababbaaaabaabba
4	=(2)+(3)	= abba	234:ab.ab:baaaabaabba
5	=(2)+(2)	= abab	2345:ba.a:aabaabba
6	=(3)+(0)	= baa	23456:a.a:baabba
7	=(0)+(0)	= aa	234567:baa.bba:
8	=(3)+(4)	= baabba	2345678

[Verwijderd]

Er zijn allerlei (betere) varianten op LZ-compressie bedacht, Lempel en Ziv bedachten er zelf minstens 3. Ook veel van deze LZ-varianten zijn (helaas) gepatenteerd, zoals de Lempel-Ziv-Walsch variant die bekend werd toen Unisys gebruik ging maken van haar patenten en zo het gif bestandsformaat opeens niet meer gratis bleek te zijn voor softwareproducenten (omdat het LZW compressie gebruikt).

Verder bestaan de meeste moderne compressieprogramma's uit "meertraps" compressie. Een veelgebruikte "pipeline": Run Length Encoding -> Burrows-Wheeler transform -> Move To Front encoding -> Run Length Encoding -> Lempel-Ziv 77 => (2x) Huffman.

edit:
Alle "trappen" voor de LZ77 dienen ertoe de input voor de LZ-compressie dusdanig te "sorteren" dat LZ betere resultaten haalt. De output van de LZ-compressie wordt dan nog Huffman encoded, met de LZ-pointers en lengtes als aparte streams.

[Verwijderd]

Gepatenteerd...? nou wat ik hier boven verzonnen heb, mag je wat mij betreft gebruiken. Dit soort manieren en ook de Huffman-codering zijn een beetje standaard oplossingen. Het is een beetje hetzelfde als dat je For-Next-Loop gaat patenteren.

[Verwijderd]

Verwijderd schreef op 27 oktober 2002 @ 14:35:
Gepatenteerd...? nou wat ik hier boven verzonnen heb, mag je wat mij betreft gebruiken.

Nee, dat mag ik niet. Sterker nog, jij mag het ook niet. Hoewel jij uit eigen kracht een beter LZ-algoritme bedacht hebt, heeft iemand anders voor jou dat al gedaan en de rechten ervoor opgeeist. Jij had dat kunnen (en moeten) weten voordat je het mij aanbood of het zelf ging gebruiken.

Dit soort manieren en ook de Huffman-codering zijn een beetje standaard oplossingen. Het is een beetje hetzelfde als dat je For-Next-Loop gaat patenteren.

Dit is het grote probleem voor de softwareindustrie op het moment. Zaken als Huffman zijn van voor de "een idee is een uitvinding" gekte, en daarom niet gepatenteerd en ook niet patenteerbaar, ze zijn public domain. Bijna alle nieuwe algoritmes worden echter gepatenteerd (ipv. gebruik te maken van copyright, dat normaal op ideeen van toepassing is) waardoor de softwareindusrtie zichzelf steeds verdergaand lam legt. Op dit moment is het al zo dat een hand vol grote softwareproducenten 90% van de softwarepatenten in hun portefuille hebben, en die regelmatig gebruiken om elkaars en andermans ontwikkeling te frustreren...

Het zelfde speelt overigens in andere wetenschapstakken, genetica schiet me zo te binnen (gepatenteerde muizen). Het is uiteraard niet goed voor de wetenschap om commerciele bedrijven een kennismonopolie te geven. Natuurlijk moeten bedrijven geen schade ondervinden van hun investeringen in R&D, maar waarom kan dat niet geregeld worden zoals voorheen (ideeen = copyright, materiele innovaties = patent)?

[Verwijderd]

Tja, onwetendheid blijft nogsteeds een zegen... hoewel ik dat patentie geintje wel ken.

Maar ik ga toch echt niet voor elk stukkie code in de patentiebak graaien om te kijken offie bestaat..

hehe, nu ik daar zo over denk eigenlijk...weet jij of zo'n sourcecode bak publiek beschikbaar is? Want anders kan ik natuurlijk nooit weten of die code ergens anders is gebruikt

Maar je begrijpt trouwens wel dat ik er nog een variatie op ga maken, het coderings idee is niet perfect.. dan ga ik er twee keer doorheen. ohnee dat bestaat al... nou dan ga ik er drie keer doorheen.. (eeh hoe zat het nou met het patent op een for/next?)

Als ik mijn code niet kan/mag vergelijken met met gepatenteerde code.. dan moet ik me toch beroepen op mijn onwetenheid en mijn incapatibeliteit om de ideeën van anderen te weten (hoe zit het met het vernederlandsen van engelse woorden?)

Voor je het weet zit er patent op bepaalde gedachten, en mag je het als normale burger niet meer denken.. Hoe zit dat dan met de vrijheid van gedachten en meningsuiting... (ohnee, vrijheid van gedachtenbepaling mag niet.. anders zou reclame geen zin hebben)

Ik zou bijna willen voorstellen om een wedstrijd te organiseren waarbij je een bijna LZ-compressie ontwerpt die nog net buiten het patent valt.. Wekelijk kun je dan de code laten controleren door de heren patent-bewaarders (wat natuurlijk mag je de originele code niet zien, toch?) En de prijs is: patent op het eigen idee.. want dat is volgens mij nog best prijzig