Bestaat er zoiets als BIT-compressie?

[Verwijderd]

Tja ik bedoel het zoals ik het zeg:

Een bestand bestaat altijd uitendelijk uit bits (eigenlijk alle data natuurlijk),

zou het niet mogelijk kunnen zijn om deze bits te comprimeren waardoor je een
nieuwe reeks bits krijgt en deze weer kunt comprimeren etc.

Dit heeft natuurlijk dan een grens (voordat ik reply's krijg) want ik weet best dat het op een gegeven moment ophoudt...

maar bestaat er zoiets of is het onmogelijk?

[odysseus]

Nee, dat is niet mogelijk - de kleinste hoeveelheid data die je kunt aangeven is de keuze uit twee opties en dat is de bit. Je kunt wel reeksen bits comprimeren (door patronen te herkennen en dergelijke), zoals alle bekende programma's doen. Je zou zelfs nog af kunnen stappen van het hele bit-idee en bijvoorbeeld drie bits omzetten in één '8-stage bit' ofwel een 'bit' met acht standen. Ook dan comprimeer je echter meerdere bits en niet één bit.

[dominic]

Hier zijn echt al noemeloze aantallen topics over geweest.. Als je de search had gebruikt had je er zat gevonden..

[Verwijderd]

Ik was al bang dat ik het misschien niet duidelijk genoeg had geschreven (of ik begrijp jou verkeerd ) maar wat ik bedoelde was voor de zekerheid dit:

stel je hebt een willekeurig bestand, deze bestaat uiteindelijk uit allemaal 10101001101010101 etc.

Stel je zou dit kunnen comprimeren tot een nieuwe reeks bits
ditmaal 1010101101
enz. enz.

Daarmee zou je dus in principe alle typen bestanden evenveel kunnen comprimeren en ook steeds opnieuw omdat je de nieuwe reeks bits weer in minder bits kunt noteren totdat het niet meer rendabel is.

Oh en de topics die ik heb gevonden gaan over compressie in het algemeen of andere typen compressie, ik vraag me af of DEZE type compressie bestaat.

[ Voor 13% gewijzigd door Verwijderd op 19-02-2003 22:36 ]

[The Bad Seed]

Verwijderd schreef op 19 February 2003 @ 22:36:
Ik was al bang dat ik het misschien niet duidelijk genoeg had geschreven (of ik begrijp jou verkeerd ) maar wat ik bedoelde was voor de zekerheid dit:

stel je hebt een willekeurig bestand, deze bestaat uiteindelijk uit allemaal 10101001101010101 etc.

Stel je zou dit kunnen comprimeren tot een nieuwe reeks bits
ditmaal 1010101101
enz. enz.

Daarmee zou je dus in principe alle typen bestanden evenveel kunnen comprimeren en ook steeds opnieuw omdat je de nieuwe reeks bits weer in minder bits kunt noteren totdat het niet meer rendabel is.

Zip enzo werken op dat principe, geloof ik.
Als er pakweg 10101010 staat, dan wordt dat omgezet naar (code voor 4*)10

Als je dan een goed algoritme hebt kom je met een keer toe, dus opeenvolgende compressies hebben dan geen succes.

[Verwijderd]

Precies, dat is dus dan ook niet wat ik zocht. want op de manier die ik bedoel (die bepaalde wel of niet bestaande algoritme) zou je dus de 10101011110101110101010101 opslaan in een nieuwe reeks 10101010111011 maar omdat dit dus geen slimme reorganisatie is maar compressie kan je daarna opnieuw die reeks comrimeren.
Zo kan je dus elk bestand tot een bepaald percentage comprimeren.

[the_shadow]

Verwijderd schreef op 19 februari 2003 @ 22:47:
Precies, dat is dus dan ook niet wat ik zocht. want op de manier die ik bedoel (die bepaalde wel of niet bestaande algoritme) zou je dus de 10101011110101110101010101 opslaan in een nieuwe reeks 10101010111011 maar omdat dit dus geen slimme reorganisatie is maar compressie kan je daarna opnieuw die reeks comrimeren.

Als dat zou werken zou je de nieuwe reeks weer kunnen veranderen in een nieuwe reeks, en die weer veranderen, tot je niks meer over hebt . Als je nou mensen hebt die niks van computers afweten, dan zouden die nog wel eens een aantal belangrijke bestanden kunnen laten verdwijnen (want dat doe je eigenlijk).

[.oisyn]

Het punt is juist dat de patronen na een compressie geheel wegvallen, en het resultaat is eigenlijk een hoopje chaos, wat heel moeilijk te comprimeren is. Datzelfde is ook het geval als je een lossy compressed stuk data gaat comprimeren, zoals een mp3tje. Een mp3 comprimeert vrij slecht, terwijl een wav aan de andere kant juist weer veel betere compressie behaalt (let wel dat het gecomprimeerde wavje nog altijd groter is dan het mp3tje)

In de output van een compressie-algoritme staan gewoon heel erg weinig patronen, en dit is dan ook niet meer comprimeerbaar

[Verwijderd]

Als je een computer baseerd op licht heb je al minstens 4 standen voor 1 bit [Uit, blauw, rood en groen]. Dan zou je bit's kunnen comprimeren toch?

[Verwijderd]

Verwijderd schreef op 19 February 2003 @ 22:47:
Precies, dat is dus dan ook niet wat ik zocht. want op de manier die ik bedoel (die bepaalde wel of niet bestaande algoritme) zou je dus de 10101011110101110101010101 opslaan in een nieuwe reeks 10101010111011 maar omdat dit dus geen slimme reorganisatie is maar compressie kan je daarna opnieuw die reeks comrimeren.
Zo kan je dus elk bestand tot een bepaald percentage comprimeren.

Het grote probleem is dat je de data die je wilt comprimeren op deze manier eigenlijk gewoon verplaatst naar je compressiealgoritme.

Wil je beweren dat dit een goed algoritme is? Wat zou dat 'bepaalde percentage' zijn dan volgens jou?
Als je je voorstel beter doordenkt en na zou rekenen (hoeveelheid mogelijke bitpatronen, lengte van te vinden patronen, etc.) zou je tot de conclusie komen dat je er minder compressiemogelijkheden mee hebt dan je dacht.

[Verwijderd]

interessante link: http://www.faqs.org/faqs/compression-faq/

>Als je een computer baseerd op licht heb je al minstens 4 standen voor 1 bit
uh, eigenschap van een bit is juist dat er maar 2 mogelijkheden zijn.
En dat aantal mogelijkheden maakt dus ook helemaal niks uit voor 't comprimeren,
want 4 mogelijkheden is dus hetzelfde als 2 bits.

En dan ben dus weer bij gewoon binaire compressie

edit:
Als je nu eens begint met je discussiegenoten respectvol en zonder flame te benaderen, praten we daarna verder

edit:
Capt. Proton : Ik dacht dat het de bedoeling was dat mensen niet zomaar alles gingen vragen zonder eerst zelf gezocht te hebben ?
Google op 'Compression' en je hebt de compression-faq, lees 'm 10 minuutjes door en je hoeft niet meer zinloos te gaan speculeren over dingen die of al bekend zijn ov simpelweg nergens op slaan.

En dat nog afgezien van het feit dat er al meerdere threads over te vinden zijn ('search' anyone ?)...

GoT != GatheringOfSpoonfeeders imho...

[ Voor 62% gewijzigd door Verwijderd op 20-02-2003 12:56 . Reden: sigh.. ]

[Verwijderd]

in de eertse plaats Sahdow, heb ik erbij gezegd dat dit natuurlijk een grens heeft, maar het betekent wel dat bestanden steeds weer opnieuw gecomprimeerd zouden kunnen worden

stel je neemt een vaste reeks bits uit dat bestand, je comrpimeert iedere keer weer die reeks. nadat je het hebt gecomprimeerd sla je het op tijdelijk op in bytes (waarbij je dus uitgaat dat de lengte van de gecomprimeerde reeks in bytes niet groter mag zijn dan het aantal bits/8 waar je mee begon). Deze reeks bytes staan weer in bits genoteerd en die kun je dan WEER comprimeren tot een kleinere reeks bits die je weer opslaat om daarna weer te comprimeren etc. MET EEN GRENS wiskundig gezien weet ik echt wel dat je uit 2 mogelijkheden van 1 bit simpelweg niet 2^(lengte gecompr. bitreeks) mogelijkheden kunt halen

[Lord Daemon]

Even een simpel bewijs dat het onmogelijk is een compressie te verzinnen die elke string van x bits can comprimeren tot een aantal a < x.

De belangrijkste eis aan een compressie is dat deze reversibel is; uit het gecomprimeerde resultaat moet de oorspronkelijke string zijn terug te krijgen. Dit is slechts mogelijk wanneer de compressie een injectieve functie is. Wat betekent dat? Je kan de compressie zien als een functie van een ruimte met mogelijke input-strings naar een ruimte met mogelijke output-strings. Deze functie is injectief dan en slechts dan als twee verschillende input-string altijd op verschillende output-strings worden afgebeeld.

Dit is natuurlijk een noodzakelijke en voldoende voorwaarde voor reversibiliteit; als bij elke input-string een andere output-string hoort kan je altijd van de output-string naar de input-string.

Goed, laten we een compressie bekijken die strings van x bits op strings van a < x bits afbeeldt. Het aantal mogelijk input-strings is 2^x. Het aantal mogelijke output-strings is 2^a < 2^x. Dus is er niet voor elke input-string een bijbehorende unieke output-string te kiezen, en kan deze code niet injectief en dus niet reversibel zijn. Het is dus principieel onmogelijk om een compressie te maken die elke input kan comprimeren.

Waarom dingen als Winzip dan toch werken is omdat files over het algemeen veel meer structuur hebben dan random bitstrings.

[LauPro]

Ik heb ooit wel is een 'compressie-programma' gemaakt voor tekst, dat was dan gericht op het Nederlands. Zo werd het woordje '&' vervangen door een &-teken. Het &-teken komt namelijk minder voor dan het woordje 'en'. Maar de twee letters 'en' zitten ook in woorden, zo wordt 'lezen' dus 'lez&'. Ik ben zo verder gegaan en heb de taal 'geanalyseerd' en ook 'de' (@ ) en 'ge' (^ ) etc.

Ik kwam geloof ik bij een werkstuk op een compressie van toch wel 25% uit meen ik (maar dan ook alleen tekst, bij een bitmap kon ik natuurlijk niks doen).

Even nog een klein voorbeeldje:

W@ró ding& às Winzip dá toch werk& is ódat files over het àgeme& vél mér structúr hebb& dá randó bitstrings.

Als je zo even een middagje gaat zoeken naar veel korte woordjes (en, an, al, de, het,ge,ver,her etc) dan heb je zo een compressie, bijvoorbeeld handig voor een database, al hoewel het de load niet ten goede komt natuurlijk .

edit:
de 'echte' á é ó worden dan natuurlijk eerst 'geëscaped', en ja ik weet dat dit niet op bit-niveau is

[ Voor 23% gewijzigd door LauPro op 20-02-2003 12:56 ]

[Verwijderd]

Lord Daemon schreef op 20 February 2003 @ 12:38:
Even een simpel bewijs dat het onmogelijk is een compressie te verzinnen die elke string van x bits can comprimeren tot een aantal a < x.

De belangrijkste eis aan een compressie is dat deze reversibel is; uit het gecomprimeerde resultaat moet de oorspronkelijke string zijn terug te krijgen. Dit is slechts mogelijk wanneer de compressie een injectieve functie is. Wat betekent dat? Je kan de compressie zien als een functie van een ruimte met mogelijke input-strings naar een ruimte met mogelijke output-strings. Deze functie is injectief dan en slechts dan als twee verschillende input-string altijd op verschillende output-strings worden afgebeeld.

Dit is natuurlijk een noodzakelijke en voldoende voorwaarde voor reversibiliteit; als bij elke input-string een andere output-string hoort kan je altijd van de output-string naar de input-string.

Goed, laten we een compressie bekijken die strings van x bits op strings van a < x bits afbeeldt. Het aantal mogelijk input-strings is 2^x. Het aantal mogelijke output-strings is 2^a < 2^x. Dus is er niet voor elke input-string een bijbehorende unieke output-string te kiezen, en kan deze code niet injectief en dus niet reversibel zijn. Het is dus principieel onmogelijk om een compressie te maken die elke input kan comprimeren.

Waarom dingen als Winzip dan toch werken is omdat files over het algemeen veel meer structuur hebben dan random bitstrings.

Goed verhaal! Als je een beetje logisch nadenkt heb je het gevoel " dit had ik zelf kunnen verzinnen".

Ik stel voor dat we overgaan op de contest "Wie verzint er een bitstring van 1K die 0% compressie oplevert in WinZip" (maar dan niet valsspelen door een bitstring te comprimeren en dat resultaat dan opgeven!)

[zion]

LauPro schreef op 20 February 2003 @ 12:54:
W@ró ding& às Winzip dá toch werk& is ódat files over het àgeme& vél mér structúr hebb& dá randó bitstrings.

Dat schiet dus écht niet op hé.

Das allemaal leuk en aardig maar zoals ík het nu zie vervangt ie dan klakkeloos in mijn geval "écht" als je het terug wil zetten naar "eecht", of hoe had je dat anders ondervangen?

[FCA]

Verwijderd schreef op 20 February 2003 @ 16:24:
[...]

Goed verhaal! Als je een beetje logisch nadenkt heb je het gevoel " dit had ik zelf kunnen verzinnen".

Ik stel voor dat we overgaan op de contest "Wie verzint er een bitstring van 1K die 0% compressie oplevert in WinZip" (maar dan niet valsspelen door een bitstring te comprimeren en dat resultaat dan opgeven!)

Zet dit om in hex-code, en probeer eens te comprimeren:

code:

BF951FC7699913637A31E64D393D497C181BC025B8E4EC4B024FE35C176DDF4A
F15D4C3FFB75286BA5C4A198DD02F549E6F71590AB92F5DB04AC825BA171E658
042065860D045CE0B86FA62BB84BA50C3127E4C319E38241CF7302CF21762FE2
76E659116BE7BCF57488053B8D79E8D04CB19C6FF86C67C6EFB4E133553647B8
793767369D1BE2B79DB15F4AC9EA43DCDEDB7E6502C6C27BE4038BC4BF32FC7E
BAEE21D10255547342C627198C850DAECA60E5E2A0BB688AAACED1C9370A4EAE
07FFD834A36DFB9C0A378573FF6665DCF657D8E7C845B43AB267C96D38A09319
C5C602BC9581C585EEF25FB4E41F2B96272448FC84284B8B3225BF0C57C09BBC

Gegenereerd met HotBits, een site die "echte" random getallen produceert, die over het algemeen ontzettend moeilijk te comprimeren zijn (zoals een willekeurige FAQ over compressie je had kunnen vertellen).

[.oisyn]

FCA schreef op 20 February 2003 @ 18:06:
Gegenereerd met HotBits, een site die "echte" random getallen produceert, die over het algemeen ontzettend moeilijk te comprimeren zijn (zoals een willekeurige FAQ over compressie je had kunnen vertellen).

heb een 2k random binary gedownload

random.bin
size: 2048
packed: 2048
ratio: 0%

[Verwijderd]

FCA schreef op 20 februari 2003 @ 18:06:
[...]
zoals een willekeurige FAQ over compressie je had kunnen vertellen.

Oei, daar heb je me. Ik zit idd niet echt in de compressie. Bedankt voor de link!

[SilentStorm]

De meest bekende compressiemethode (die in praktisch alle compressieprogramma's wordt gebruikt met daarbij enige aanpassingen) is de 'huffman-codering'. Deze berust op een vrij simpel principe: Neem een stuk van een bestand, ga voor het gemak uit van een byte=8bits. Ons bestand is voor het uitleggen een tekstbestand.

Elke letter zou in de algemene ISO-8859-15 codering 1 byte groot zijn (2 bytes in unicode of utf8). Letters als de 'e' of de spatie, komen veel vaker voor als bijvoorbeeld de 'q' of de 'x'. (bij het inlezen van een bestand wordt een huffman-boom gebouwt (of zit al in het compressieprogramma), waarin de meest efficiente manier van aanschrijven van de de verschillende letters wordt opgebouwd. De 'e' komt vaak voor, dus ipv de normale waarde (01100101) maken we daar een kortere bitreeks voor. zeg voor het gemak '0000'. Voor de spatie maken we dan '0001' en voor de q '10011101110111011'.

Met een binair bestand ziet dit er natuurlijk iets anders uit, maar je snapt denk ik het principe. Het nadeel hiervan is dat voor een zo efficient mogelijke encryptie er een complete boom moet worden opgebouwd, wat vrij lang kan duren bij grote bestanden. Voorzover ik bekend ben zitten er een aantal 'standaardbomen' in elk compressieprogramma. Dit heeft meteen tot voordeel dat de binaire zoekboom, (de compressie boom), niet hoeft te worden meegezonden, wat toch weer een aantal bytes in je bestand opleverd.

[Exirion]

The_Shadow schreef op 20 februari 2003 @ 08:28:
Als dat zou werken zou je de nieuwe reeks weer kunnen veranderen in een nieuwe reeks, en die weer veranderen, tot je niks meer over hebt . Als je nou mensen hebt die niks van computers afweten, dan zouden die nog wel eens een aantal belangrijke bestanden kunnen laten verdwijnen (want dat doe je eigenlijk).

Inderdaad, en ik snap ook niet waarom hier nog geen slotje op zit

Persoon blaat: ik heb een idee, we gaan rijen bits inkorten zodat we comprimeren
*the crowd goes mad*

Is iedereen even vergeten dat de definitie van comprimeren het reduceren van de hoeveelheid informatiebits is? Of je nou over bytes of bits praat, het wordt (als het goed is) minder. De topicstarter dumpt een losse flodder, want hij zegt niets eens op wat voor manier die compressie dan zou moeten werken! Gewoon maar op goed geluk eentjes en nulletjes wegstrepen en hopen dat er wat nuttigs overblijft?

Enfin, er bestaan legio compressiealgoritmen en ze hebben allemaal 1 doel: het aantal bits reduceren. Waar moet nu nog over gediscussieerd worden? Er is genoeg wiskunde en informatica literatuur over compressie te vinden.

[Verwijderd]

nee, als je goed had gelezen had je gezien dat ik dus niet een idee heb voor een compressie, maar vraag of deze comressie bestaat. Daarbij klopt wat shadow zegt dus niet omdat ik zeg dat er een grens is! dus lees eerst ff.
Hoe ik zou denken dat deze compressie zou werken weet ik niet. Maar volgens mij heb je een groot voordeeel als je een methode vindt om bitstrings te comprimeren:
De compressie is unbiased (hij comprimeert bits, niet typen bestanden...) de technologie zeg ik niks over omdat ik geen idee heb hoe dat zou werken...

Het tweede voordeel zou zijn (boven huffman enzo) dat je het bestand meermalen achter elkaar kunt comprimeren, totdat de hoeveelheid bits te klein is om alle beginmogelijkheden op te slaan of dat de compressie niet meer rendabel is omdat notatie groter is dan begin.

(SNAPPIE??)

[Exirion]

Verwijderd schreef op 22 February 2003 @ 16:45:
(SNAPPIE??)

Ja, ik wel. Maar jij blijkbaar niet, want anders zou je begrijpen dat jouw 'benadering' niks nieuws is Jij bekijkt het op bitniveau, maar die bits zijn een representatie van datapatronen die direct of indirect uit bits zijn opgebouwd. Er zijn echter al genoeg compressiemethoden die tot op bitniveau naar comprimeerbare patronen zoeken. Lees gewoon wat meer over compressie voordat je dingen gaat bedenken die al bestaan

[Verwijderd]

ik zeg het nog maar een keertje, ik bedoel niet dat ze alleen kijken op bitniveau maar ook comprimeren op bitniveau daardoor zou je hetzelfde bestand meermalen kunnen comprimeren todat het niet meer rendabel is (DUS NIET ONEINDIG VAAK).
Bij de compressies waar jij het over hebt kan dit maar een keer omdat ze naar het bestand kijken en dan de tekens die het vaakst voorkomen de kleinste bit-codering geven en de tekens die het minst voorkomen de grootste. Dit kan je daarna niet meer opnieuw doen.

Maar als je 1010001101101 kunt noteren in 1010111101 (berust op een technologie die waarschijnlijk niet bestaat maar waavan ik vraag OF die bestaat) en die 1010111101 weer in 111011 (dit is natuurlijk een onmogelijk voorbeeld, daar zou je bijvoorbeeld hele lange bitreeksen voor nodig hebben etc. maar je snapt wel wat ik bedoel) dan heb je hem meermalen gecomprimeerd, althans zou het mogelijk moeten zijn.

[ Voor 5% gewijzigd door Verwijderd op 23-02-2003 17:36 ]

[Exirion]

Verwijderd schreef op 23 February 2003 @ 17:29:
ik zeg het nog maar een keertje, ik bedoel niet dat ze alleen kijken op bitniveau maar ook comprimeren op bitniveau daardoor zou je hetzelfde bestand meermalen kunnen comprimeren todat het niet meer rendabel is (DUS NIET ONEINDIG VAAK).

Dat doen (sommige) bestaande algoritmen ook al.

Bij de compressies waar jij het over hebt kan dit maar een keer omdat ze naar het bestand kijken en dan de tekens die het vaakst voorkomen de kleinste bit-codering geven en de tekens die het minst voorkomen de grootste. Dit kan je daarna niet meer opnieuw doen.

Waar zeg ik wat jij zegt dat ik zeg? Jij hebt gewoon een verkeerd idee van hoe bestaande algoritmen werken, dus je neemt aan dat ik bedoel wat jij denkt. Ik zeg het dus nog een keer: ga eens wat meer lezen over de wiskunde en algoritmiek achter compressie. Die is een stuk verder/complexer dan jij durft te vermoeden.