Een nieuwe compressietechniek - Wat denk je?

[Webdoc]

Beste Mede-Tweakers,

Ik zit al een tijdje met dit idee te spelen, en ik dacht zo bij mijzelf - wellicht is he leuk om dit eens aan jullie hier voor te leggen, want na jaren gedenk kan ik maar niet met een reden komen waarom dit idee niet kan werken. Tijd dus voor een reality-check.

OK. Het is eigenlijk erg simpel. Men neme een stukje data. Dat stukje data, in zijn puurste vorm, is een getal. Een heel erg lang getal wellicht, maar een getal nevertheless. En toen dacht ik... stel nou je "comprimeert" dat stukje data, door alleen de berekening op te slaan die dat getal als resultaat heeft.

Dus stel, het is toevallig zo dat mijn stukje data is 1414213562373095048801688724, dan "comprimeer" ik dat door te schrijven √2(28) (zo van, tot 28 tekens na de komma). Desnoods met +x erbij om de data exact te hebben (per slot van rekening is het nogal onwaarschijnlijk dat de data die ik wil comprimeren nou precies wortel 2 is ) maar - je snapt het idee. De compressie is enorm, tot wel 80%.

En nou is dit even een snel, lomp voorbeeld, maar stel nou dat je een soort compressie-engine maakt die de hele tijd data (getallen) aan het "Reverse-berekenen" is om zo tot de kleinst mogelijke berekening te komen die die data als resultaat volledig kan reproduceren. Kan ook best zo zijn dat je data uiteindelijk een klein lijstje van een stuk of 10-30 berekeningen is, hoeft natuurlijk niet maar 1 te zijn. Maar, het idee is duidelijk. En het leuke is dat je dit op natuurlijk net zo makkelijk op "conventioneel" gecomprimeerde data kan loslaten, waardoor je nog meer ruimte bespaart.

Dus de vraag is - wat denken jullie? Is dit een levensvatbaar idee? Is dit wellicht wat die geheimzinnige gast heeft uitgevonden paar jaar terug (je weet wel, meneer ik-comprimeer-een-hele-DVD-op-een-floppy-disk...?

Hoor graag jullie meningen Dank W

[Sleepkever]

Grappig idee, zeker een keer het experimenteren waard denk ik, al is het alleen maar voor de ervaring

Ik heb zelf geen flauw idee ervan hoe andere compressietechnieken werken, maar ik zie wel zo al een aantal problemen.

Je vergeet alleen dat een computer al redelijk efficient is in het opslaan van binaire data, ze doen namelijk niet anders. Die "1,414213562373095048801688724" ziet er impressive uit, maar zal niet meer zijn dan 8 bytes aan data (64 bits).
De berekening die jij voorstelt (√2(28)) ziet er korter uit, maar is een x aantal bits voor het type berekening (laten we zeggen 3, dan kan je 7 types berekeningen kwijt voorlopig), x aantal bits voor het eerste nummer (kommagetallen nodig misschien, in ieder geval een grote range, dus laten we zeggen, 32 bits minimaal, en voor de afronding of eventuele tweede getal voor vermengvuldiging of deling ook een bitje of 5 a 6 ofzo?
dan moet je dus voor 64 bit aan data minimaal 41 bits aan data opslaan. Wat al een stuk minder impressive klinkt.

En wat als het getal nou eentje hoger ligt? Dan ga je nooit de wortel kunnen trekken van een mooi getal om juist uit te komen. Om op 1je hoger uit te komen moet je bijvoorbeeld sqrt(2,0000000000000000000000000022353) doen. En als je zoveel getallen achter de komma weer wilt garanderen heb je weer meer bits nodig

Kortom, ik denk niet dat dit levensvatbaar is, in ieder geval niet in de huidige vorm. Een leuk idee is het wel. Misschien binnenkort maar eens een simpel prototype schrijven om te kijken of het wel wat oplevert

[Koppensneller]

Sleepkever schreef op donderdag 10 januari 2013 @ 15:27:
En wat als het getal nou eentje hoger ligt? Dan ga je nooit de wortel kunnen trekken van een mooi getal om juist uit te komen. Om op 1je hoger uit te komen moet je bijvoorbeeld sqrt(2,0000000000000000000000000022353) doen. En als je zoveel getallen achter de komma weer wilt garanderen heb je weer meer bits nodig

Dan doe je sqrt(x) - 1

Naast de vraag of het echt winst oplevert (een leuk experiment is het zeker), is het nog wel een uitdaging om van de eerste x getallen de kortste berekening te vinden.

[Sleepkever]

Koppensneller schreef op donderdag 10 januari 2013 @ 15:31:
[...]


Dan doe je sqrt(x) - 1

Naast de vraag of het echt winst oplevert (een leuk experiment is het zeker), is het nog wel een uitdaging om van de eerste x getallen de kortste berekening te vinden.

Ja, maar dan moet je dus weer extra bits toevoegen aan je compressie omdat je weer een extra berekening wilt

Mooier is natuurlijk om modulair op te proberen te bouwen en bij de eerste bit zeggen of het bij de vorige berekening hoort of dat deze weggeschreven moet worden en opnieuw moet beginnen. Er zijn zeker mogelijkheden om mee te prutsen.

[Smuggler]

is wel het spelen waard al deed het me denken aan: Wikipedia: Letter frequency wat natuurlijk ook op bytes is toe te passen na een analyze van het programma...

[Webdoc]

Dank voor de reacties zo ver... zelf denk ik dat het grootste probleem het vinden van de berekening zal zijn, vooral voor de echte grote getallen, en dat is zo ongeveer alle data. Neem nou een Word-doc, dat is al gauw 100KB, ok, dat is een "getal" van 819200 bit. Zie daar maar een berekening van te maken die dat als resultaat heeft. Ook al splits je het op in, zeg, 100 stukjes (die wellicht elk 100 bytes per berekening nodig hebben) zit je op 10KB, is alsnog 90% winst.. maar of dat even snel kan...? Ik denk dat dit nogal veel CPU kracht nodig heeft (om die berekeningen te vinden) en die berekening moet elke keer opnieuw want jah, data varieert.

Wellicht dat je een soort library kan opslaan waarbij je "blokken" berekent.... zo van

00101010101010101010110101010 = berekening A
00101010101010101010110101011 = berekening A+1

enzo voorts - om het wat sneller/efficienter te maken.

[Mx. Alba]

Ik denk dat het probleem vooral zal zijn dat het heel moeilijk is om bij een bepaald resultaat (dat getal van 819200 bits) een passende berekening te vinden.

[MSalters]

Werkt niet. De Kolmogorov complexiteit van een willekeurige input string is niet kleiner dan de string zelf.

[Techneut]

Heel aardig, dat wel, ook als uitdaging en zeker als hersenoefening. Maar laten we wel wezen, ook niet meer dan dat. Want wat is het echte nut ervan? Met name nu computergeheugen vrijwel niets meer kost.

[MrAcid]

Techneut schreef op vrijdag 11 januari 2013 @ 10:52:
Heel aardig, dat wel, ook als uitdaging en zeker als hersenoefening. Maar laten we wel wezen, ook niet meer dan dat. Want wat is het echte nut ervan? Met name nu computergeheugen vrijwel niets meer kost.

Dat lijkt me een non-argument, er zijn zat cases te bedenken waarbij compressie van data wenselijk is. Bijvoorbeeld compressie van data over (mobiele) verbindingen?

[Z-Dragon]

http://www.keyword.nl/compressie.pdf vat het mooi samen.

[Sebas1979]

MSalters schreef op vrijdag 11 januari 2013 @ 10:31:
Werkt niet. De Kolmogorov complexiteit van een willekeurige input string is niet kleiner dan de string zelf.

Wikipedia: Kolmogorov-complexiteit

Als ik dit doorlees, kom ik uit op 'werkt alleen niet voor strings waarin geen patronen te herkennen zijn'.

Kan zijn dat ik het verkeerd begrijp, kun je wat meer toelichting geven?

[LiquidT_NL]

Sebas1979 schreef op vrijdag 11 januari 2013 @ 13:27:
[...]


Wikipedia: Kolmogorov-complexiteit

Als ik dit doorlees, kom ik uit op 'werkt alleen niet voor strings waarin geen patronen te herkennen zijn'.

Kan zijn dat ik het verkeerd begrijp, kun je wat meer toelichting geven?

Ik haal er hetzelfde uit. Die link onderschrijft juist dat data wel degelijk te comprimeren valt op die manier, alleen niet alle. Daarnaast vraag ik mij af, gezien die link enkel spreekt over UDL, of er met een slim algoritme dit niet beter kan dan met een UDL.

[Sissors]

Probleem is als er een patroon in te herkennen is, kunnen standaard compressietechnieken dat er al probleemloos uithalen.

[Mx. Alba]

furby-killer schreef op vrijdag 11 januari 2013 @ 14:57:
Probleem is als er een patroon in te herkennen is, kunnen standaard compressietechnieken dat er al probleemloos uithalen.

Nee natuurlijk niet, want compressietechnieken kunnen natuurlijk niet alle patronen herkennen. Neem het getal π of e tot 1 miljard cijfers achter de komma, ik durf te stellen dat er geen enkel compressieprogramma is dat dat herkent, terwijl die 1 miljard cijfers toch echt te comprimeren zijn tot één karakter.

[Sissors]

Oké daar heb je een punt, maar je blijft het probleem houden dat alle standaard patronen probleemloos door huidige compressiealgorithmes eruit worden gehaald, wat zou dit algorithme dan meer doen? (Ja je kan elk bestand controleren of pi er niet in voorkomt, maar denk niet dat dat heel nuttig is).

[Mx. Alba]

En dus moet je een afweging maken: welke patronen komen vaak genoeg voor om herkenning ervan nuttig te maken? Dus herkent compressiesoftware per definitie niet alle patronen...

[verleemen]

Klinkt een beetje naar fractalcompression waar fotos terug gebracht worden tot klenie formules. Is wel een lossy format dus niet geschikt voor tekst. Wikipedia: Fractal compression.

Voor t algoritme van TS hoef je natuurlijk niet alles te comprineren, je zou een soort RAR formaat kunnen hebben dat verschillende algoritmes gebruikt

[begintmeta]

Mx. Alba schreef op vrijdag 11 januari 2013 @ 18:21:
En dus moet je een afweging maken: welke patronen komen vaak genoeg voor om herkenning ervan nuttig te maken? Dus herkent compressiesoftware per definitie niet alle patronen...

Precies. Achteraf is het geen kunst om zelfs een random reeks bits te reduceren tot 1 bit (of als gewenst meer bits), de kunst is om een vooraf gemaakte methode te hebben die diverse mogelijke reeksen kan reduceren.

[ Voor 3% gewijzigd door begintmeta op 12-01-2013 00:45 ]

[MSalters]

Precies. Ik kan een simpele familie van compressiealgoritmes schrijven dat elke bitsequence B tot 1 bit comprimeert. Dat gaat zo: Als de input B is, dan is de output 0, en anders 1+Input.

Elk lid van die familie comprimeert dus 1 string perfect. Maar ja, om door te geven welk compressiealgoritme ik gebruik moet je dat dus eerst doorgeven.

Kortom, het probleem is nooit 1 specifieke inputstring, maar het complete domein van mogelijke inputstrings.

[Bodevinaat]

Zie deze thread nu pas... heb met exact hetzelfde idee al jaren geleden wat zitten knutselen met Delphi om te kijken of dit levensvatbaar is. Wat ik mij ervan kan herinneren dat ik uiteindelijk in een soort polynomiaal terecht kwam.. je hebt het antwoord maar wilt er de kortste en efficientste berekening bij vinden.

Die geheimzinnige meneer was Jan Sloot. Hij beweerde dat hij een hele film kon comprimeren naar uiteindelijk 16 kb, maar stierf voordat hij openheid van zaken kon geven.

[Edit]
Kan de source niet meer vinden maar wat ik deed was de Asciiwaarde van elke letter achter elkaar plakken zodat er uiteindelijk een reusachtig getal overbleef. Dat getal deelde ik herhaaldelijk door 2 totdat ik een ondeelbaar restant (1) overhield. Brongetal N deelde ik dan bijv. 1753 x dus de hele pagina tekst (bijv 1024 tekens) werd uiteindelijk (2^1753)+1. Dan per 3 cijfers de Chr() vinden en de tekst weer aan elkaar plakken. Probleem is dat de opslag pakumbeet 9 bytes is maar de berekening vreet enorm veel tijd.

[ Voor 37% gewijzigd door Bodevinaat op 17-01-2013 14:34 ]

[MSalters]

Oh, je kunt nog wel verder comprimeren. Tot 1 bit zelfs.

Het probleem is en blijft dat je het resultaat niet kunt decomprimeren. Als je input 16 of 17 is, dan kun je in beide gevallen 4 keer delen totdat het "gecomprimeerde" resultaat 1 is.

[Bodevinaat]

Volgens mij niet. Het gecomprimeerde gegeven is (2^1753)+1
Het algoritme om te decomprimeren is:
1. doe de machtsverheffing
2. maak van het resulterende getal een string
3. loop de string door en bepaal de character per 3 posities
4. plak deze character aan elkaar en je hebt je gecomprimeerde string gedecomprimeerd.

[BartS12]

Het probleem is en blijft dat je het resultaat niet kunt decomprimeren. Als je input 16 of 17 is, dan kun je in beide gevallen 4 keer delen totdat het "gecomprimeerde" resultaat 1 is.

Dit klopt wel degelijk, maar misschien is het met voorbeelden 16 en 17 niet helemaal duidelijk. Hoe comprimeren 18 t/m 31 dan? Allemaal 2^4 + een beetje. Niet allemaal +1, maar ja, in het beschreven algorithme komt dit nog even niet voor:

Dat getal deelde ik herhaaldelijk door 2 totdat ik een ondeelbaar restant (1) overhield.

Je houdt - zeker met grotere getallen - al heel snel een ondeelbaar restant over. Wat heet : (decimaal) getal 1111111111111111111 is meteen al ondeelbaar door 2; restant 111111111111111111. En toen?

Of bedoel je dat ook 31 'deelbaar' door 2 is? Uitkomt 15, restant 1. Maar dan...? 15 is niet te schrijven als 2^n. Andersom geformuleerd - er zijn maar heel weinig getallen te schrijven als 2^n+1. Dus ja, op zich kun je wel decomprimeren. Maar *ofwel* slechts een heel beperkt aantal getallen (=teksten) valt uberhaupt te comprimeren (diegene die te schrijven zijn als 2^n of 2^n+1). *Ofwel* alle getallen zijn te 'comprimeren, maar dan moet je gaan schrijven als 2^n+m, waarbij m hele grote waarden kan aannemen. En dan zelf weer gecomprimeerd moet worden....

[ Voor 16% gewijzigd door BartS12 op 17-01-2013 15:00 ]

[Zoijar]

Mx. Alba schreef op vrijdag 11 januari 2013 @ 15:21:
Nee natuurlijk niet, want compressietechnieken kunnen natuurlijk niet alle patronen herkennen. Neem het getal π of e tot 1 miljard cijfers achter de komma, ik durf te stellen dat er geen enkel compressieprogramma is dat dat herkent, terwijl die 1 miljard cijfers toch echt te comprimeren zijn tot één karakter.

Als we even aannemen (onbewezen maar wel vermoed) dat de decimalen van pi elke eindige reeks bevatten, dan kan de pi compressie dat in een byte. Je zoekt op bij welke begin positie de decimalen van pi gelijk zijn aan je bestand; als de opslag van die begin positie groter is dan je bestand sla je het bestand zelf op. Ik vermoed echter dat je over alle input geen hoge gemiddelde compressie behaalt.

---

Bestaande lossless compressie technieken zitten al vrij dicht bij het optimaal haalbare onder aanname van bepaalde verdelingen van de data. Voor hele specifieke data kan je het misschien verbeteren, maar niet in het algemene geval. De zoektocht is dan ook voornamelijk naar snellere en bruikbaardere algoritmes (zoals random access) en niet zozeer naar betere compressie factoren.

[ Voor 23% gewijzigd door Zoijar op 17-01-2013 15:26 ]

[dwaas]

Webdoc schreef op donderdag 10 januari 2013 @ 15:09:
Beste Mede-Tweakers,

Ik zit al een tijdje met dit idee te spelen, en ik dacht zo bij mijzelf - wellicht is he leuk om dit eens aan jullie hier voor te leggen, want na jaren gedenk kan ik maar niet met een reden komen waarom dit idee niet kan werken. Tijd dus voor een reality-check.

OK. Het is eigenlijk erg simpel. Men neme een stukje data. Dat stukje data, in zijn puurste vorm, is een getal. Een heel erg lang getal wellicht, maar een getal nevertheless. En toen dacht ik... stel nou je "comprimeert" dat stukje data, door alleen de berekening op te slaan die dat getal als resultaat heeft.

Dus stel, het is toevallig zo dat mijn stukje data is 1414213562373095048801688724, dan "comprimeer" ik dat door te schrijven √2(28) (zo van, tot 28 tekens na de komma). Desnoods met +x erbij om de data exact te hebben (per slot van rekening is het nogal onwaarschijnlijk dat de data die ik wil comprimeren nou precies wortel 2 is ) maar - je snapt het idee. De compressie is enorm, tot wel 80%.

En nou is dit even een snel, lomp voorbeeld, maar stel nou dat je een soort compressie-engine maakt die de hele tijd data (getallen) aan het "Reverse-berekenen" is om zo tot de kleinst mogelijke berekening te komen die die data als resultaat volledig kan reproduceren. Kan ook best zo zijn dat je data uiteindelijk een klein lijstje van een stuk of 10-30 berekeningen is, hoeft natuurlijk niet maar 1 te zijn. Maar, het idee is duidelijk. En het leuke is dat je dit op natuurlijk net zo makkelijk op "conventioneel" gecomprimeerde data kan loslaten, waardoor je nog meer ruimte bespaart.

Dus de vraag is - wat denken jullie? Is dit een levensvatbaar idee? Is dit wellicht wat die geheimzinnige gast heeft uitgevonden paar jaar terug (je weet wel, meneer ik-comprimeer-een-hele-DVD-op-een-floppy-disk...?

Hoor graag jullie meningen Dank W

Ik ben niet gehinderd door enige kennis van zaken dus als het onzin is hoor ik het graag.

Kan je dan niet beter de binaire code van je data gaan ontbinden of naar verwijzen in een tabel of...

[MSalters]

De verwijzing naar een tabel is tenminste net zo groot als de data zelf.

Al dit soort ideeen falen direct op het piegonhole principle. Er zijn 2^n mogelijke bitstrings van lengte n. Als er een compressie bestond tot lengte m, met m<n, dan heb je maar 2^m mogelijke gecomprimeerde bitstrings, met 2^m < 2^n. Zonder de exacte mapping te weten, weet je dan dat je ook maar 2^m resultaten uit je decompressie algoritme krijgt. Er zijn dus 2^n-2^m bitstrings die niet tot lengte m gecomprimeerd kunnen worden.

Dit principe staat dus los van het exacte algoritme, want dat bepaalt alleen welke bitstrings gecomprimeerd kunnen worden. En als je denkt: dan heb ik in elk geval nog een compressie voor sommige bitstrings, nee. Je moet eerst een 0 of een 1 zenden (dus 1 extra bit) om aan te geven of de volgende bitstring gecomprimeerd is.

[Bodevinaat]

BartS12 schreef op donderdag 17 januari 2013 @ 14:58:
[...]


Dit klopt wel degelijk, maar misschien is het met voorbeelden 16 en 17 niet helemaal duidelijk. Hoe comprimeren 18 t/m 31 dan? Allemaal 2^4 + een beetje. Niet allemaal +1, maar ja, in het beschreven algorithme komt dit nog even niet voor:


[...]


Je houdt - zeker met grotere getallen - al heel snel een ondeelbaar restant over. Wat heet : (decimaal) getal 1111111111111111111 is meteen al ondeelbaar door 2; restant 111111111111111111. En toen?

Of bedoel je dat ook 31 'deelbaar' door 2 is? Uitkomt 15, restant 1. Maar dan...? 15 is niet te schrijven als 2^n. Andersom geformuleerd - er zijn maar heel weinig getallen te schrijven als 2^n+1. Dus ja, op zich kun je wel decomprimeren. Maar *ofwel* slechts een heel beperkt aantal getallen (=teksten) valt uberhaupt te comprimeren (diegene die te schrijven zijn als 2^n of 2^n+1). *Ofwel* alle getallen zijn te 'comprimeren, maar dan moet je gaan schrijven als 2^n+m, waarbij m hele grote waarden kan aannemen. En dan zelf weer gecomprimeerd moet worden....

Ik denk dat je gelijk hebt. Overigens is het decomprimeren dan weer erg eenvoudig, vooropgesteld dat je een datatype hebt waar deze enorme integers ingepropt kunnen worden, want het coderen van tekst naar cijfers levert een buitengewoon groot getal op.

Bijv. 'ik loop naar school' wordt '105107321081111111123211097971143211599104111111108'

[Argantonis]

Hou er rekening mee dat het moeten uitvoeren van arbitraire berekeningen wisselend in complexiteit vaak niet gewenst is, juíst op devices waarbij de hoeveelheid data-opslag of overdracht nog relevant is.

[Verwijderd]

ik claim 500 Terabytes, op een 1TB schijf te kunnen zetten, zonder data verlies, en met een factor van 500 aan leessnelheden,
probleem is alleen, daarvoor moet ik een circuit bouwen met ongeveer 100 Miljard diodes en transistoren,
Het ide klopt volgens experts, alleen wordt er voorlopig niks mee gedaan

[MSalters]

Nee. Je idee klopt niet volgens experts.

Het circuit met 100 miljard transistoren bestaat al. Dat is een PC. Programmeerbaar, dus je kunt de transistoren schakelen zoals je wil.

Niet dat je de transistoren nodig hebt voor het wiskundig algoritme. Dat kun je ook in text uitleggen.
En doe dat nu eens niet voor terabytes maar gewone bytes. Hoe stop jij 500 bytes in 1 byte? Concreet: hoe stop je de eerste 257 sequences van lengte 500 bytes (dus 0x0000....0000 tot 0x00000...100) in 1 byte? Uiteraard moeten die 257 verschillende inputs ook 257 verschillende outputs hebben.

Zoals eerder gezegd, al dit soort nonsens faalt direct onder het pigeonhole principle. Dat jij probeert om 2^{500.000.000.000.000} pigeons in 2^{1.000.000.000.000} pigeonholes te stoppen is een doorzichtige truc om een falend algoritme te maskeren met grote getallen.

[Verwijderd]

MSalters schreef op maandag 04 februari 2013 @ 14:46:
Nee. Je idee klopt niet volgens experts.

Het circuit met 100 miljard transistoren bestaat al. Dat is een PC. Programmeerbaar, dus je kunt de transistoren schakelen zoals je wil.

Niet dat je de transistoren nodig hebt voor het wiskundig algoritme. Dat kun je ook in text uitleggen.
En doe dat nu eens niet voor terabytes maar gewone bytes. Hoe stop jij 500 bytes in 1 byte? Concreet: hoe stop je de eerste 257 sequences van lengte 500 bytes (dus 0x0000....0000 tot 0x00000...100) in 1 byte? Uiteraard moeten die 257 verschillende inputs ook 257 verschillende outputs hebben.

Zoals eerder gezegd, al dit soort nonsens faalt direct onder het pigeonhole principle. Dat jij probeert om 2^{500.000.000.000.000} pigeons in 2^{1.000.000.000.000} pigeonholes te stoppen is een doorzichtige truc om een falend algoritme te maskeren met grote getallen.

die zelfde vraag die jij steld hoe prop je 500 bytes in 1 byte, dat lukt inderdaad niet, nooit.
dat vragen er heel veel af.

deze compressie techniek werkt anders, met variabelen, positieven en negatieven,


stel, je hebt 255 Bit ruimte, afhankelijk hoe de bit volgorde is, kun je hier maximaal 2048 Bit opslaan,
( positief), is de bit volgorde zo drastisch, bijv. allemaal eentjes 11111111 dan kun je slecht 8Bit opslaan ( negatief) door middel van een algoritme kun je dit negatieve effect naar de positieve kant proppen .

je gemiddelde compressie is dan ongeveer 4 op 1,

heb je 511 bit opslag, dan kun je in het negatieve 9 bit opslaan, en het positieve 4599 Bit,
nu is je compressie verhouding gemiddeld 4,5 op 1

met andere woorden hoe meer opslag je hebt, hoe groter de compressie verhouding is.

maar je hebt te maken met een variabele opslag , afhankelijk wat je opslaat hoe beter het te comprimeren valt. bijv. 000 001 010 100 101 , is beter op te slaan dan 111 111 111 111 , hiervoor moet er een 2e opslag worden aangemaakt die deze reeks met een factor omzet naar positieve waarden

( positief betekent in deze compressie techniek geen 1, maar als een bestand gecomprimeerd kan worden, Negatief betekent dat hij meer ruimte in beslag zou nemen dan zijn oorsprong, dit wordt dus geconverteerd met een factor)

ik weet dat er 100 Miljard transistoren op een chip gebakken kunnen worden,
maar wie gaat dit nou geloven , en in investeren.

een 255 bit versie, die nu op de klassieke manier wordt gesoldeerd, eist meer dan 5000 soldeer verbindingen

het zou software matig te maken zijn, ik ben geen programmeur, maar dat zou vreten van je CPU,

Uiteraard kan ik er niet te veel van verklappen,

[MSalters]

Haha, maar nee. "Positief" en "negatief" is een interpretatie. Als je een byte zo interpreteert dat die negatief kan zijn, dan wordt het bereik normaal gesproken -128...127 (2s complement) of -127...+127 (1s complement, met aparte +0 en -0). Het totaal aantal mogelijke waarden van een byte blijft dus precies 256.

Jouw idee is dus samengevat: 1 bit algoritme-ID ("positief algoritme" of "negatief algoritme"), gevolgd door de bits uit het gekozen algoritme. Dat is voor de meeste amateurs de eerste poging. Het probleem: Je begint met een bit extra nodig te hebben, om je set van mogelijke inputs te verdelen in tweeen. De beste verdeling is 50/50. Dat wil zeggen dat een input set ter grootte van 2^N wordt gedeeld in twee sets van 2^(N-1). Het aantal bits wat je dan nodig hebt is N-1, ongeacht de input. Tel daar de eerste algoritme-keuze bit bij op en je bent terug op de originele N bits.

Als je set niet 50/50 deelt, dan is 1 van de sets groter dan 2^(N-1), heb je daarvoor N bits nodig, en is het resultaat van je "compressie" dus mogelijk N+1 bits groot.

Let wel: dit bewijs geldt dus voor alle compressie-algoritmes die opgebouwd zijn uit een keuze tussen twee algoritmes. Je hoeft dus niets te verklappen over de onderliggende twee algoritmes.

[Zoijar]

Verwijderd schreef op vrijdag 01 februari 2013 @ 02:17:
ik claim 500 Terabytes, op een 1TB schijf te kunnen zetten, zonder data verlies, en met een factor van 500 aan leessnelheden,
probleem is alleen, daarvoor moet ik een circuit bouwen met ongeveer 100 Miljard diodes en transistoren,
Het ide klopt volgens experts, alleen wordt er voorlopig niks mee gedaan

Niet als ik de 500 TB mag aanleveren

http://www.drdobbs.com/ar...-compressing-ra/240049914

The original version of the challenge is basically unchanged. Your goal is to find the shortest program possible that will produce the million random-digit file. In other words, demonstrate that its Kolmogorov complexity is less than its size. So the heart of Challenge 1 is the question of whether the file is compressible à la Kolmogorov and standard, general-purpose computing machines.

The interesting part about this challenge is that it is only very likely impossible. Turing, and Gödel before him, made sure that we can't state with any certainty that there is no program of size less than 415,241 bytes that will produce the file. All it takes is a lucky strike. Maybe the digits are a prime? Maybe they just happen to be nested in the expansion of some transcendental number? Or better yet, maybe the RANDians overlooked some redundancy, hidden somewhere in a fifth order curve, just waiting to be fit. There are no telling how many different ways you could hit the jackpot.

However, the dismal logic of The Counting Argument tells us that there are always going to be some files of size 415,241 bytes that are not compressible by the rules of Challenge 1. And of course, it's actually much worse than that — when you cast a critical eye on the task, it turns out that nearly all files are incompressible. But for a given file, we don't really have any way of proving incompressibility.

[... maar ...]

Challenge 1 is interesting because it is nearly, but not assuredly, impossible. Challenge 2 is more along the lines of troll bait, because it is patently impossible: Create a system to compress and then decompress any file of size 415,241 bytes. In other words, create a compressed file that is smaller than the input, then use only that compressed file to restore the original data.

Unlike Challenge 1, there are no size limitations on Challenge 2. Your compressor and decompressor can be as large as you like. Because the programs have to be able to handle any input data, size is of no particular advantage — there is no data to hide.

Als je een MB random aangeleverde data kan compressen met ook maar 1 enkele byte, dan wacht je eeuwige beroemdheid in de informatica. Let wel, dan wordt de informatiecapaciteit van je hardware (als je iets ervan gebruikt om daadwerkelijk data op te slaan) ook meegeteld. Maar dat maakt in jouw geval niet uit, want dan schaal je het gewoon wat naar beneden met minder transistoren. Dit is dus nog het makkelijke geval 1 waar de data gegeven en bekend is! Voor alle mogelijke input is het geval 2...

[ Voor 80% gewijzigd door Zoijar op 07-02-2013 17:37 ]

[Sissors]

Verwijderd schreef op maandag 04 februari 2013 @ 19:43:
[...]
Uiteraard kan ik er niet te veel van verklappen,

Omdat het niet werkt misschien? Verder blijft het een nogal vaag verhaal. Maar geef dan een voorbeeld van je 256 bit versie, moet een computer echt geen tijd kunnen doen. Optimaliseren kan dan later wel.

En als je wilt beweren dat je per sé hardware nodig hebt die het doet, koop een FPGA en laat het daarmee zien. Die dingen zijn echt niet duur en daar heb je een hele hoop transistoren op zitten waar je met veel plezier digitale schakelingen mee kan maken. Werkt je revolutionaire idee daarop, dan kunnen ze het daarna wel als ASIC bakken. Maar een digitaal ASIC kan niks wat een FPGA ook niet kan, het is enkel zuiniger/sneller.

[Onbekend]

Een FPGA is niet per sé nodig. Ook al gaat het traag, je hebt het principe dan al aangetoond.

[Verwijderd]

Interessant topic, sorry voor mijn late reactie.

Je theorie lijkt me in principe bruikbaar. Maar helaas zit de praktijk in de weg.

- Standaard compressietechnieken werken meestal al volgens de methode die jij beschrijft. Neem een willekeurig stuk data en vertaal dat naar een uniek getal. Als je datzelfde stuk data tegenkomt dan vervang je dat steeds door het unieke getal. Zie http://nl.wikipedia.org/wiki/Datacompressie. Er zijn vele algoritmes in omloop maar de essentie is: vervang iets groots door een kleinere representatie ervan.

- Wat jij beschrijft, lijkt wel wat op hardware-compressie. In plaats van een vertaaltabel (library) mee te sturen met je gecomprimeerde data, gebruik je een library die in firmware is opgeslagen. Bijvoorbeeld in een chip in een tapestreamer, of in jouw circuit. Het nadeel van de beperkte (statische) library wordt deels goedgemaakt doordat je de library niet met je data hoeft mee te sturen.

Jij wilt in feite hetzelfde als men in 1980 al deed. Maak een circuit dat (bijna) alle mogelijke datarepresentaties van tekst, foto's, enz. bevat. Je scant je bestand en vervangt de data (of delen daarvan) door 1 of meer getallen uit je circuit. In feite wil jij geen library, maar een berekening. Dat doet weinig ter zake, want jouw complexe berekening doet in feite hetzelfde als het library-mechanisme: het levert een getal op dat een representatie van de data vormt.

De decompressor kan erg eenvoudig zijn. Hij ziet een getal en vervangt dat door het deel van zijn library waar het getal naar verwijst. Of, in jouw model, reconstrueert hij de originele data middels een algoritme dat je in hardware hebt gebakken.

Maar als je dit in de praktijk brengt, dan loop je stuk. Want helaas is het aantal mogelijke combinaties van bytes oneindig. Omdat jouw circuit niet oneindig snel kan rekenen, loop je tegen dezelfde berperkingen op als alle andere compressiemethoden.

a) Als je toch oneindig snel kan rekenen, dan nog bestaat de kans dat het nummer dat je berekent zo enorm groot is dat het langer wordt dan de originele data. Bedenk wel dat integers, real, float variabelen zelf ook ruimte in beslag nemen, en dat alle variabelen een beperking hebben in het grootste getal dat ze kunnen bevatten.

b) Door praktische beperkingen ben je genoodzaakt om je rekentijd te begrenzen. Dat heeft tot gevolg dat de effectiviteit van je algoritme omgekeerd evenredig is met de complexiteit van de originele data. Dat geldt onverbiddelijk voor alle compressiealgoritmen.

Daarom denk ik dat jouw systeem wel kan werken, maar dat het praktisch alleen bruikbaar is voor niet al te grote en niet erg complexe data, zoals b.v. documenten. En zelfs dan zal je gecomprimeerde data niet uit 1 getal bestaan, maar uit een reeks getallen. Meer complexe data levert automatisch een groter gecomprimeerd bestand op.

Toch denk ik dat je idee kan werken, maar dan alleen voor korte, niet te complexe stukken data. Maar om het praktisch bruikbaar te maken denk ik dat je effectiviteit moet inleveren. Anders duurt het comprimeren zo lang

[MSalters]

Nee. Je punt (a) klopt niet.

dan nog bestaat de kans dat het nummer dat je berekent zo enorm groot is dat het langer wordt dan de originele data

. Over alle mogelijke input gemiddeld is dat geen kans, maar een absolute zekerheid.

[Zoijar]

Precies. Zoals boven ook al meerdere keren uitgelegd... Als je een bestand hebt van 8 bits, dan zijn er 256 mogelijke bestanden. Als je die nu allemaal zou kunnen compressen naar 6 bits ("slechts" 25% compressie) dan zijn er 64 mogelijke gecompressde representaties/bestanden. Je ziet meteen dat het pertinent onmogelijk is om uit slechts 64 verschillende input bestanden 256 verschillende output bestanden te genereren. Want waar beslis je dan om een ander bestand te genereren als de input hetzelfde is? Dat kan niet.

Lossless compressie is een vrij afgebakend gebied. Een specifieke random string is bijvoorbeeld vrijwel zeker niet te compressen. De theorie van Wikipedia: Kolmogorov complexity gaat op ongeacht wat voor belachelijk slim algoritme je gebruikt.