'Alternatieve' compressie

[Sponge]

Gisternacht zat ik dus wat te denken over (data) compressie, en kreeg ik een (misschien wel interessant) idee. Ik heb het niet volledig uitgedacht, dus misschien zitten er wel logica fouten in.

Zover ik weet werken alle compressie algorithmes (voor formaten zoals:ARJ,ZIP, ARC, CAB,) tegenwoordig met vaste algorithmes: Dictionary, Run Length Encoding (RLE), Sequential*, en vast nog wel een paar methodes.

* (Sequential = als je bytes hebt van bijvoorbeeld, 1,2,3,4,5, er slechts staat "1 t/m 5")

Nou zat ik dus te denken als je nou de compressie zelf een soort programmeer taal laat zijn. Het programma waar mee je comprimeert (of compiled ) bedenkt de juiste "code" voor het te comprimeren bestand.

Want met huidige formaten zit je vast aan een methode (Meerdere keren een andere compressie methode is niet altijd geweldig). MEt die programmeer taal zou je bijvoorbeeld makkelijk kunnen switchen tussen RLE en sequential, en als je goed met de bits omgaat, kun je een redelijk 'programmeer' taaltje bedenken die met 1 byte werkt (met 2 bits heb je al 4 mogelijke instructies, en in 1 byte zitten er 8 dus..)

Als je dus in ASCII waarden een bestandje hebt zoals dit:
12345671111111111187654
\--seq--/ \-----RLE-----/\-seq-/

Dan zou je die kunnen verdelen in 3 'instructies', zoals je hierboven kunt zien. Volgens mij is het mogelijk om een instructie met 2 bytes werkend te krijgen (weer door de bits), maar ik ga uit van 3:

'opcode' (1b), instructie(1b, 2 bit gebruikt), 'opcode' (1b)

Voor seq: asciistart,instructie, "stap grootte"
Voor rle: asciicode, instructie, "hoevaak?"

Ik zit alleen te denken hoe het mogelijk is om een dictionary te kunnen maken, waarschijnlijk door een simpele BSP tree met de ascii waarden van elke karakter, moet ik nog maar eens over nadenken

Als het gedecomprimeert wordt, dan worden de 'instructies' uitgevoert en komt er hopelijk dezelfde file weer uit. Deze methode zou in principe het hele compressie proces dynamischer moeten maken, met het hopelijk uiteindelijke resultaat om alles klein(er) te krijgen

Nou ben ik benieuwd of dit eigenlijk zou kunnen werken, en wat jullie ervan vinden . Misschien slaat het nergens op, maar ja ik heb er ook nogal laat om zitten te denken

[klinz]

Klinkt een beetje als lzhuf met delta compression. Ik zou zeggen: implementeer het en test de efficientie van je algorithme.

[Gerco]

Voor zover ik weet gebruiken goede compressieprogjes toch al verschillende technieken om te comprimeren. Verder denk ik dat het goed mogelijk is wat je voorstelt, alleen kan ik niet zo snel een methode bedenken om een huffmann tree in je "instructieset" in te passen.

[martinvw]

Hmmz, klinkt interessant, als je wat verder hebt uitgewerkt is het misschien leuk om in dit topic geinteresseerde op de hoogte te houden en evt problemen waar je tegen aan loopt hier neer te gooien.

[ruuds]

offtopic:
heet jij toevallig Almar?

[Sponge]

Ik zal eens kijken of ik wat in elkaar kan zetten

offtopic:
Ja.

[Exirion]

Gerco schreef op 10 augustus 2002 @ 14:11:
Voor zover ik weet gebruiken goede compressieprogjes toch al verschillende technieken om te comprimeren. Verder denk ik dat het goed mogelijk is wat je voorstelt, alleen kan ik niet zo snel een methode bedenken om een huffmann tree in je "instructieset" in te passen.

Absoluut. Zelfs de allereerste DOS versies van PKZIP hadden verschillende methoden om de comprimeren, en volgens mij werd voor het comprimeren gewoon bepaald welke waarschijnlijk de efficientste methode voor een bepaalde file zou zijn.

Lees dit eens door: http://orca.st.usm.edu/~altemus/paper.htm

[_Thanatos_]

Houd wel in je achterhoofd dat er een theoretische maximumcompressie voor een stuk data bestaat. Ik weet niet wat de formule is, maar de absoluut maximaal haalbare compressie is gewoon een stuk algebra en is dus te berekenen.

Gezien er al compressie-algoritmen bestaan die *heel* dicht in de buurt van die maximum compressie komen (RAR, CAB) moet je wel met iets geniaals komen.

Maargoed, veel verder dan RAR of CAB zul je nooit kunnen komen. (ja tenzij je dus op de MPEG of JPEG manier gaan 'comprimeren' )

[Verwijderd]

_Thanatos_ schreef op 11 augustus 2002 @ 05:23:
Houd wel in je achterhoofd dat er een theoretische maximumcompressie voor een stuk data bestaat. Ik weet niet wat de formule is, maar de absoluut maximaal haalbare compressie is gewoon een stuk algebra en is dus te berekenen.

Gezien er al compressie-algoritmen bestaan die *heel* dicht in de buurt van die maximum compressie komen (RAR, CAB) moet je wel met iets geniaals komen.

Maargoed, veel verder dan RAR of CAB zul je nooit kunnen komen. (ja tenzij je dus op de MPEG of JPEG manier gaan 'comprimeren' )

Je bedoelt dus het weglaten van data

[Verwijderd]

Zo ziet een zip-file eruit: http://www.pkzip.com/support/appnote.html
Misschien heb je er wat aan...

Gerco> Programma's kunnen (eventueel) de compressie-methode per file bekijken, niet per 'segment' zoals 41.6C.6D.61.72 voorstelt.
Exirion> DOS-Zip comprimeerde eerst volgens de opgegeven methode, als het gecomprimeerde bestand groter werd, dan stopte DOS-Zip gewoon het originele bestand in de zip-file (geen compressie dus...).

[Sponge]

Verwijderd schreef op 11 augustus 2002 @ 07:20:
Je bedoelt dus het weglaten van data

Er was ooit een compressie 'algoritme' bedacht door iemand die 99% compressie garandeerde. Eerst werden alle 1'tjes van de bits weg gehaald, en daarna een RLE compressie over de resterende nullen. Uiteraard niet lossless (het spreekt voor zich dat het een grapje was, er is wel een site ergens van.. )

Die URL is wel intreressant Exirion, ik had eens eerder zoiets gevonden, die misschien ook wel interessant is voor anderen:

http://www.rasip.fer.hr/research/compress/algorithms/ (Met omschrijving hoe de meeste algorithmes werken!, voorbeelden hoe het eruit zal zien, e.d. aanrader )