Bestandscompressie in Pi of andere transcendente getallen

[Quinny]

Stel: Een stuk data (een videofile oid.) wordt omgezet tot een reeks getallen (simpel).

Zoek nu in bijv. Pi deze zelfde reeks getallen op, Pi is oneindig dus deze reeks komt een oneindig aantal keer voor in Pi.
Bewaar het decimaal waar deze reeks begint (tellen..) en hoe lang deze reeks is.

Om de data terug te krijgen gebruik je de bewaarde "adressen" om de reeks weer op te zoeken in Pi.

Het op deze manier comprimeren en decomprimeren van data vergt enorm veel rekenkracht, maar de compressie is erg goed. Een file van een paar gigabyte kan op deze manier gecomprimeerd worden tot een paar Bytes of KiloBytes.


Er zijn waarschijnlijk te weinig decimalen van Pi of andere transcendente getallen bekend om dit te kunnen doen, ik wilde het toch even posten om te horen wat voor reacties er komen en of er misschien al anderen geweest zijn met dit idee. (Ik kan me niet voorstellen dat niemand dit nog bedacht heeft...)

[Cpt.Morgan]

Het belangrijkste probleem lijkt me dat het niet altijd tot compressie zal leiden, maar vaak juist tot expansie van de hoeveelheid data:

Als een bepaalde reeks getallen (stel 4 getallen) pas relatief laat in Pi voorkomt (zeg na iets meer dan 1 miljoen cijfers), dan is het adres (in dit geval 7 cijfers) groter dan de uitgangstekst.

En hoe ingewikkelder de reeks getallen die je wilt hebben, hoe groter het adres zal zijn (bij willekeurige data)....

[Paul]

1 miljoen past in 3 bytes Nog korter ook, maar goed

Een van de problemen die je tegenkomt is: wanneer stop je? Match je blokken van 1 kilobit? een halve? begin je met een kleiner iets en zoek je steeds groter? Want wie zegt dat je (stel dat we het beperken tot een file pi.dat van 700MB, of zelfs 4.7TB, om het iig nog redelijk distribueerbaar te houden) die grote blokken tegenkomt?

Een van de grootste bottlenecks, zelfs met een bijna oneindig grote pi.dat (of misschien juist met een bijna oneindige grote dataset), is je zoek-algoritme. Pi doorzoeken, is door zijn "random" natuur, een een O(n) operatie, gemiddeld zul je per blok data de helft van je file moeten doorzoeken, aangenomen dat alles te vinden is. Zijn er dingen niet te vinden dan loopt het snel op, want je moet dan een kleiner blok nemen, waardoor je er dus meer hebt. Je hebt dan wel een grotere kans dat je het blok vind, maar het kostte je dus al minimaal 1x de hele dataset doorlopen.

Je krijgt denk ik een langere comprimeer-tijd dan dat je wint aan overdrachtstijd, want wat is het doel nu helemaal van comprimeren? Minder schijfruimte? Tja, als je dan 4 uur moet rekenen voordat je die film kunt gaan kijken? Sneller over internet sturen? Met de huidige verbindingen ook steeds minder interessant.

[Jimbolino]

Pi.dat hoef je helemaal niet mee te leveren bij het programma...
je kunt er gewoon zelf een genereren?

het klinkt als een leuke compressie techniek, maar niet echt haalbaar in snelheid

houd er ook rekening mee dat je de data om moet zetten van hexadecimaal naar decimaal (en dus groter wordt)

[Cpt.Morgan]

Paul Nieuwkamp schreef op 20 september 2004 @ 00:56:
1 miljoen past in 3 bytes Nog korter ook, maar goed

Okay Niet helemaal goed voorbeeld dus, maar het idee blijft staan: om een specifieke grote dataset terug te vinden in bijv Pi, kan het adres groter worden dan die dataset...

[Semyon]

Statisch gezien haal je hier precies geen compressie mee. Je zal gemiddeld evenveel ruimte nodig hebben om je index op te slaan als je data, als de reeks echt goed random is. Als je erg veel geluk hebt met je data kan je compressie krijgen, heb je een beetje pech dan kan het leiden tot expansie.

[Paul]

Je zou pi.dat inderdaad kunnen berekenen. Weet je helemaal zeker dat je bestand pas over een week gecomprimeerd is Hoe lang doe je over het berekenen van pi tot 700 miljoen cijfers achter de komma? Als je het als decimaal uitschrijft en voor iedere digit 1 byte neemt heb je dan 700MB. Die je het binair dan passen er in 700MB nog veel meer cijfers achter de komma.

En wat semyon zegt, daar speelt dus je doel voor de compressie in mee Wil je het data-deel versturen, dan zou dit wel een goede manier zijn, omdat beide kanten die index hebben.
Het klopt overigens niet helemaal, want je kunt duizenden dingen comprimeren met die ene index. Gaat het slechts om 1 file dan komen de grootes inderdaad redelijk overeen. Er kan natuurlijke enige overlap zitten in de blokken die je controleerd. De laatste helft van het ene blok komt overeen met de eerste helft van een ander blok ergens uit de file, en je index _kan_ al een stukje kleiner.

[Verwijderd]

Beide de te comprimeren gegevens en PI zijn random. Waar je op hoopt is dat de random batterij getallen van PI efficienter is dan een zelf gegenereerde reeks. Dit zal nooit zo zijn want er is overlap binnen een random serie. Sterker: als coderen met PI efficient blijkt, is PI niet random, want dan kan PI gecodeerd worden met de te coderen datan. En dat is in tegenspraak met het random zijn van de getallen binnen PI.

[RobIII]

Jimbolino schreef op 20 september 2004 @ 01:08:
houd er ook rekening mee dat je de data om moet zetten van hexadecimaal naar decimaal (en dus groter wordt)

Dit volg ik dus weer eens niet... Waarom zou 't van hex naar decimaal moeten? Waarom zou er uberhaupt iets van talstelsel a naar b moeten? Of je je film of je pi.dat nu representeert als hex, octaal, decimaal of whatever, uiteindelijk blijft het gewoon een bult enen en nullen. En om die op te slaan heb je evenveel ruimte nodig.

Als voorbeeld:
FF_hex neemt evenveel ruimte in beslag als 255_dec en evenveel als 11111111_bin... Allemaal 1 byte.

Maar, ontopic: Hoewel het idee leuk klinkt, als je er wat langer over na denkt is het natuurlijk erg onrealistisch. Ten eerste heb je een joekel van een "pi.dat" nodig. Die zul je OF zelf moeten uitrekenen (weken, maanden, jaren voor nodig) OF moeten downloaden (en die tijd zul je dan dus weer moeten goedmaken met de kleinere downloads^* die je compressie techniek oplevert). Hoewel de downloadtijd, bij erg veel downloads, waarschijnlijk wel eens een keer een break-even point zal halen en daarna winstgevend zal worden lijkt me dit niet haalbaar in een mensenleven.

Ten tweede zal de "index", zoals al eerder aangegeven, waarschijnlijk een behoorlijk getal zijn waarvoor je ook erg veel ruimte, misschien wel evenveel of meer, nodig hebt om op te slaan. Ga je je bestand in stukjes hakken en die matchen met delen uit pi, dan heb je uiteindelijk, effectief, dus alleen maar een dictionary en dan zie ik dus weer niet waarom je daarvoor pi of een ander trancedent getal zou moeten gebruiken. Dan kun je net zo goed een eigen dictionary bepalen, en die, per bestand dat je gaat comprimeren, beter afstemmen op het bestand zelf (zoals bijv. Huffman).

Wel moet ik toegeven dat, met het oog op de ontwikkelingen in de quantum-computing, de benodigde rekentijd waarschijnlijk drastisch kan worden verkort in de toekomst zodat het wel weer renderend kan worden. Helaas vrees ik dat we dan ook heel andere vormen van compressie gaan zien. (Disclaimer: Ik ken alleen een érg klein topje van de ijsberg wat betreft quantum computing, dus misschien sla ik hier de plank finaal mis. Dit is dan ook niet echt een erg "zelfverzekerd" statement )

^* of, for that matter, gegevens- en bestandsoverdrachten in zijn algemeenheid.

[ Voor 66% gewijzigd door RobIII op 20-09-2004 02:51 ]

[Jimbolino]

lijkt ook een beetje hierop: Search for your name in Pi

Your chances: 3 or fewer letters: about 100% 7 or more letters: about 0%

[RobIII]

Jimbolino schreef op 20 september 2004 @ 03:54:
lijkt ook een beetje hierop: Search for your name in Pi

[...]

Doel je nu weer op die conversie? Want je hebt volgens mij geen flauw idee wat ik bedoel

[Thijsch]

Het grootste probleem is het comprimeren. Daar moet je de reeks echt zoeken. Het decomprimeren gaat weer wel snel. Er waren nl agloritmes die in Hex het x-ste decimaal uit konden rekenen zonder alle decimalen daar voor uit te hoeven rekenen.

[Semyon]

Het is wel leuk om over snelheid van decoderen en coderen door te babbelen Maar compressie krijg je dus niet met deze techniek. Met wat rekenwerk is wel in te zien dat de verwachtings waarde voor de index precies even groot is als je weg te schrijven data.

[Reptile209]

offtopic:
I searched 1048571 digits of p, and found GOD 46 times. The first occurrence was at position 29639
I searched 1048571 digits of p, and found GOT 55 times. The first occurrence was at position 6976

GoT 0wnd God

In videofiles e.d. heb je bovendien ongecomprimeerd enorme blokken repeterende getallen (afaik) die je in iets randoms als pi niet zult vinden. Dus moet er hoe dan ook een codec of andere compressor overheen. En dan vraag ik me idd af hoeveel zin het nog heeft om dat met veel pijn en moeite verder te proberen te comprimeren via pi, e, 2^1/2, enz. Zeker ook gezien de dalende prijzen van bulk-opslag (dvd, etc) en breedbandverbindingen.

[baexem]

Ik denk dat onderstaande hetgeen is wat de TS precies bedoeld, ik probeer het even te visualiseren - Sorry voor de layout:

code:

Pi:                3.1415926543126846843541534684346516984646546949846984651351654887687354316546798798768432198673574986746984684654987354132164568798746541237
Waarde van file:                                                               6548876873543165467987987684321986735749867469846846

Je hoeft nu toch allen de begin en eindpositie te weten?
Want mijn te zoeken waarde match met de reeks van positie 60 tot en met 111.
Met deze twee getallen kun je dus meteen weer opzoeken wat de originele tekst is?
En ja, inderdaad, een zoek algoritme kán idd erg langzaam worden, maar da's slechts éénmalig!

Of denk ik nou toch echt te simpel???

offtopic:
alweer een op "De Broncode" gebaseerd topic...

[Verwijderd]

Dat is inderdaad wat de TS bedoelt. Echter, de index (het getal dat de beginpositie weergeeft van een willekeurige file) zal gemiddeld minstens even groot zijn als de bijbehorende file zelf. In andere woorden, je hebt voor een file van 700 MB alsnog 700MB nodig om de positie waarop de file begint, op te slaan...

[G33rt]

Volgens mij zit in dit stuk redenering een foutje:

Zoek nu in bijv. Pi deze zelfde reeks getallen op, Pi is oneindig dus deze reeks komt een oneindig aantal keer voor in Pi.

Een computer kan niet een oneindig getal adresseren, dan loopt zijn geheugen vol. Omdat verschillende computers dan ook nog andere hoeveelheden intern geheugen hebben, weet je dus nooit in hoeverre ze allebei pi even 'goed' kennen. Tevens gaat de redenering dat elke reeks in Pi moet voorkomen dan niet meer op, omdat het getal immers niet meer oneindig is. Het lijkt mij dat daar een fout in een redenering zit, maar zeker weten doe ik het niet.

Verder is, zoals door velen voor me al gezegd, het met het oog op de huidige verbindingen een enorm zwaar algorithme niet meer intressant. De argumenten daarvoor ben ik het mee eens, daarom herhaal ik ze niet voor de tigste keer.

[elnino]

Is het trouwens bewezen dat iedere getalvolgorde in pi moet voorkomen? Het zijn natuurlijk heel veel getallen en vele combinaties zijn mogelijk, maar is het niet mogelijk dat bijv. 1 combinatie helemaal niet zal voorkomen?

[RobIII]

elnino schreef op 20 september 2004 @ 12:10:
Is het trouwens bewezen dat iedere getalvolgorde in pi moet voorkomen? Het zijn natuurlijk heel veel getallen en vele combinaties zijn mogelijk, maar is het niet mogelijk dat bijv. 1 combinatie helemaal niet zal voorkomen?

In een oneindige reeks moet ieder getal altijd voorkomen. Waar dat getal voorkomt is een andere zaak, en kan dus héél ver weg zitten.

Maar goed, ik heb geen wiskundige achtergrond, dus misschien zit ik er wel langs. Dit is puur zoals ik het begrijp.

[Verwijderd]

Verwijderd schreef op 20 september 2004 @ 09:57:
Dat is inderdaad wat de TS bedoelt. Echter, de index (het getal dat de beginpositie weergeeft van een willekeurige file) zal gemiddeld minstens even groot zijn als de bijbehorende file zelf. In andere woorden, je hebt voor een file van 700 MB alsnog 700MB nodig om de positie waarop de file begint, op te slaan...

Volgens mij klopt dat niet, je kunt die index weergeven in log₂ n / 8 bytes. (65536 = 2¹⁶ in een 2-byte index, 4294967296 = 2³² in 4 bytes, enz.)

G33rt schreef op 20 september 2004 @ 09:59:
Een computer kan niet een oneindig getal adresseren, dan loopt zijn geheugen vol. Omdat verschillende computers dan ook nog andere hoeveelheden intern geheugen hebben, weet je dus nooit in hoeverre ze allebei pi even 'goed' kennen. Tevens gaat de redenering dat elke reeks in Pi moet voorkomen dan niet meer op, omdat het getal immers niet meer oneindig is. Het lijkt mij dat daar een fout in een redenering zit, maar zeker weten doe ik het niet.

Er is een algoritme om decimalen van pi te berekenen zonder alle voorgaande decimalen te berekenen, dus geheugen vormt geen probleem. Het ware probleem is rekentijd, ik heb in een (zeer) grijs verleden eens een vergelijkbare naieve datacompressie bedacht door te proberen pseudo-random generatoren te construeren, maar zodra je realistisch naar kansverdelingen gaat kijken blijkt snel dat dit soort compressie vrij kansloos is. (De kans om n bytes correct te genereren is 1/256ⁿ).

[Verwijderd]

In een oneindige reeks moet ieder getal altijd voorkomen. Waar dat getal voorkomt is een andere zaak, en kan dus héél ver weg zitten.

Maar goed, ik heb geen wiskundige achtergrond, dus misschien zit ik er wel langs. Dit is puur zoals ik het begrijp.

Mja, in de reeks 111111111..... enzovoorts, zal je toch lang moeten zoeken naar een 0, ondanks dat de reeks oneindig lang is. Alleen in een oneindige reeks die op geen enkele manier aan een bepaalde regelmaat voldoet, zal elke willekeurige combinatie oneindig vaak voorkomen. Ik meen me te herinneren dat er sterke aanwijzingen zijn dat Pi een dergelijke reeks is.

[RobIII]

Verwijderd schreef op 20 september 2004 @ 12:20:
[...]


Mja, in de reeks 111111111..... enzovoorts, zal je toch lang moeten zoeken naar een 0, ondanks dat de reeks oneindig lang is. Alleen in een oneindige reeks die op geen enkele manier aan een bepaalde regelmaat voldoet, zal elke willekeurige combinatie oneindig vaak voorkomen. Ik meen me te herinneren dat er sterke aanwijzingen zijn dat Pi een dergelijke reeks is.

Dat zeg ik

[Zoijar]

Hoe bereken je eigenlijk de verwachte grootte van je index? Stel pi is random, en je wilt k getallen matchen.

(ik heb wel een idee, maar kan geen berekening bedenken. Het zal wel iets van (1/10)^(-k) zijn. En dan heb je naar verwachting dus 10log((1/10)^(-k)) = k characters nodig. Het is hetzelfde probleem als "hoe vaak moet ik gooien om naar verwachting 3x een zes te gooien". Ik zit er mee dat de aantal set oneindig is, en de reeks niet convergent. Dus hoe doe je dit dan? Ben het even kwijt)

[ Voor 74% gewijzigd door Zoijar op 20-09-2004 12:38 ]

[Verwijderd]

Zoijar schreef op 20 september 2004 @ 12:30:
Hoe bereken je eigenlijk de verwachte grootte van je index? Stel pi is random, en je wilt k getallen matchen.

(ik heb wel een idee, maar kan geen berekening bedenken. Het zal wel iets van (1/10)^(-k) zijn.

De kans om k bits te matchen is 1/2^k, dus de gemiddeld te verwachten lengte van de bitstring is 2^k; de gemiddelde lengte van de te verwachten index wordt daarmee k bits. (Dit is volgens mij wat CP bedoelde maar verkeerd uitdrukte.)

[Zoijar]

Verwijderd schreef op 20 september 2004 @ 12:40:
De kans om k bits te matchen is 1/2^k, dus de gemiddeld te verwachten lengte van de bitstring is 2^k; de gemiddelde lengte van de te verwachten index wordt daarmee k bits. (Dit is volgens mij wat CP bedoelde maar verkeerd uitdrukte.)

Ja, dat is ook wat ik net als zei uit intuitie. Maar, bewijs?

Oh, binomiaal experiment...laat maar. (more coffee! )

[ Voor 8% gewijzigd door Zoijar op 20-09-2004 12:46 ]

[Verwijderd]

Zoijar schreef op 20 september 2004 @ 12:41:
Ja, dat is ook wat ik net als zei uit intuitie. Maar, bewijs?

Hoezo bewijs, dit is simpele kansrekening. Een bit is 2-waardig dus de kans om een bit correct te voorspellen is 1/2; daar de kansen onafhankelijk zijn multipliceren we de kans voor meerdere bits dus krijgen we 1/2^k. De lengte van de bitstrings volgen hieruit; de indexlengte van zo'n bitstring berekenen is een log₂ nemen.

[TlighT]

elnino schreef op 20 september 2004 @ 12:10:
Is het trouwens bewezen dat iedere getalvolgorde in pi moet voorkomen? Het zijn natuurlijk heel veel getallen en vele combinaties zijn mogelijk, maar is het niet mogelijk dat bijv. 1 combinatie helemaal niet zal voorkomen?

Volgens wikipedia:

The most pressing open question about π is whether it is a normal number, i.e. whether any digit block occurs in the expansion of π just as often as one would statistically expect if the digits had been produced completely "randomly". This must be true in any base, not just in base 10. Current knowledge in this direction is very weak; e.g., it is not even known which of the digits 0,...,9 occur infinitely often in the decimal expansion of π.

Nee dus (het is nog niet bewezen).

Edit:
Maar anders maak je gewoon een getal waarbij dat wel zo is: 0.01234567890001020304050607080910111213141516171819202122... Als je met dit getal al geen compressie behaald, lijkt het me sterk dat je dat met pi welk kunt...

[ Voor 13% gewijzigd door TlighT op 20-09-2004 13:02 ]

[Verwijderd]

Een specifieke getallenreeks zal waarschijnlijk eerder voorkomen in de reeks:

1234567891011314151617181920212232425...

dan in de decimaalontwikkeling van Pi. Bovenstaande reeks is dus bij voorbaat al geschikter. Het lijkt me echter ook evident dat het getal dat je zoekt veel kleiner is dan het getal dat correspondeert met de plaats waar het voorkomt...

Zo is bijvoorbeeld bekend dat het getal 123456789 komt niet voor voor de 500.000.000 ste decimaal in Pi. Dan kan je dus maar beter het getal 123456789 zelf opslaan.

Niet echt effectief dus (hoewel wel minder desatreus dan ik gedacht had, ik dacht dat het getal veel en veel groter zou worden, maar het lijkt nogal mee te vallen).

P.S. Dat laatste heeft natuurlijk te maken met het feit dat de verwachtingswaarde van de decimaal waar het getal te vinden is precies even groot is als het getal zelf.

[ Voor 11% gewijzigd door Verwijderd op 21-09-2004 17:06 ]

[Verwijderd]

ik was nog even aan het ronddenken... stel nu dat pi oneindig is en dat je alle informatie, bestanden etc zou kunnen omzetten in een getallenreeks...

dan staat nu dus eigenlijk ook al elk document vast omdat het past binnen pi. Hoe kan dat?

[RobIII]

Verwijderd schreef op 20 september 2004 @ 13:09:
ik was nog even aan het ronddenken... stel nu dat pi oneindig is en dat je alle informatie, bestanden etc zou kunnen omzetten in een getallenreeks...

dan staat nu dus eigenlijk ook al elk document vast omdat het past binnen pi. Hoe kan dat?

Nogmaals, je hoeft helemaal niks om te zetten... Dat je pi nou eenmaal makkelijker onthoudt in z'n decimale representatie (3,141592...) wil niet zeggen dat pi anders is in zijn binaire of octale representatie. Een document, data of whatever is in een computer, net als pi gewoon een bult enen en nullen. Er hoeft dus niks "geconverteerd" te worden ofzo. Je CPU ziet het verschil niet hoor.

Wat betreft hoe dat kan: Pi is oneindig groot/lang. Dat je hersenen (en overigens de mijne ook niet hoor) het begrip "oneindig" niet helemaal kunnen bevatten wil niet zeggen dat het niet kan.

Wat hier stond had in een TR gemoeten.

[ Voor 25% gewijzigd door Confusion op 21-09-2004 20:08 ]

[Zoijar]

Verwijderd schreef op 20 september 2004 @ 12:50:
Hoezo bewijs, dit is simpele kansrekening. Een bit is 2-waardig dus de kans om een bit correct te voorspellen is 1/2; daar de kansen onafhankelijk zijn multipliceren we de kans voor meerdere bits dus krijgen we 1/2^k.

ja, dat is waar.

De lengte van de bitstrings volgen hieruit; de indexlengte van zo'n bitstring berekenen is een log₂ nemen.

Uit deze reeks: sum(n=1->inf) n*(1-p)^(n-1)*p = 1/p, waar ik even niet op kwam. Geometrische verdeling is het. Zoiets moet er toch wel even bij hoor, zeg dan in ieder geval volgens de geometrische verdeling die verwachting 1/p heeft is de verwachte lengte nu zoveel.

Maar zijn de proeven wel onafhankelijk? (ik bedoel, als er in het midden bv in jouw reeks "11" staat, en in pi "22", dan weet je al dat de volgende proef ook zeker gaat mislukken, ongeacht het volgende begin getal.)

Verwijderd schreef op 20 september 2004 @ 13:09:
dan staat nu dus eigenlijk ook al elk document vast omdat het past binnen pi. Hoe kan dat?

Omdat oneindig behoorlijk groot is

[ Voor 24% gewijzigd door Zoijar op 20-09-2004 13:37 ]

[nhimf]

Waarom persé pi?

Waarom "verzin" je niet zelf een gezellig getal, zet dat in een bestand en gebruik dat.
Zorg dat er zo min mogelijk sequenties dubbel voorkomen.
Als je dan iets wil decompressen, lees je het bestand in en gaat op zoek naar de vertaling, zodat je het originele betand terug hebt. M.a.w. je getal wordt onderdeel van je (de)compressie programma.

En al zou het getal 500.000.000 tekens bevatten en 500mb op je hdd in beslag nemen, maar als je genoeg compressed, dan levert het meer op dan dat het kost (is dat niet het idee van compressie?)

Wel moet je natuurlijk blokken nemen van meer dan 8 bytes, omdat je begin en eind index samen al 8 bytes zijn.(uitgaande van 32bits integers).

Om het uit te proberen zou je het kunnen testen door een getal te produceren en een testbestandje te compressen.

Ik denk dat je een best aardige compressie kan krijgen, maar of het extreem zal zijn... dat weet ik niet.

edit:

reken even met mij mee:
stel je gaat uit van 16byte blokken (en dus een compressie van 50%, je indices zijn 8 bytes, originele data 16 bytes)
16 bytes = 128 bits = 3,4028236692093846346337460743177e+38 mogelijkheden, dat is meer dan er in een integer past en dat is een hoop data op je hdd. Dus om een haalbare compressie te krijgen met een niet generiek genereerbaar getal, zal het niet echt haalbaar zijn om een goede compressie te krijgen ben ik bang......

edit:
@ RobIII:
ik was er al achter dat je idd iets als pi moet gebruiken om het haalbaar te maken.
Maar dan nog, hoe kan je van een totaal willekeurig getal de positie binnen pi berekenen?
Of moet je dan op zoek gaan? Dan ben je volgens mij wel even bezig.

[ Voor 31% gewijzigd door nhimf op 20-09-2004 13:41 ]

[RobIII]

nhimf schreef op 20 september 2004 @ 13:31:
Waarom persé pi?
Waarom "verzin" je niet zelf een gezellig getal, zet dat in een bestand en gebruik dat.
Zorg dat er zo min mogelijk sequenties dubbel voorkomen.
Als je dan iets wil decompressen, lees je het bestand in en gaat op zoek naar de vertaling, zodat je het originele betand terug hebt. M.a.w. je getal wordt onderdeel van je (de)compressie programma.

Omdat PI oneindig is in tegenstelling tot het 500Mb bestand dat je nu aangeeft. En omdat je van PI een willekeurig decimaal kan berekenen zonder voorgaande decimalen te weten. Zo kun je dus "relatief makkelijk" het umpty-ste decimaal berekenen die normaliter vér buiten jouw 500mb bestand zouden vallen en toch een flink "matchend" blok zou opleveren.

Wel moet je natuurlijk blokken nemen van meer dan 8 bytes, omdat je begin en eind index samen al 8 bytes zijn.(uitgaande van 32bits integers).

Om het uit te proberen zou je het kunnen testen door een getal te produceren en een testbestandje te compressen.

Ik denk dat je een best aardige compressie kan krijgen, maar of het extreem zal zijn... dat weet ik niet.

Allemaal leuke theorie, de praktijk lijkt me anders. Je kunt (zoals ik al eerder aangaf) beter een dictionary samenstellen op basis van de gegevens die je hebt, en daarmee gaan compressen. Dat levert altijd meer op (en daarom werkt bijna elke (huidige) compressie methode met een (hierop lijkende) techniek). Ga je met een vaste data-set werken, dan heb je per definitie overhead. Zie ook eens huffman compression, om maar eens een voorbeeld te nemen.

[ Voor 14% gewijzigd door RobIII op 20-09-2004 13:42 ]

[LtMarx]

Maar er wordt nu constant uitgegaan van een een variabele string van cijfers. Als je nu bijvoorbeeld een kleinere pi.dat neemt (wat dus al wegneemt dat iedereen daar veel tijd in zou moeten steken in zoqwel downloaden als zelf berekenen). Is er dan niet simpel een de kans te optimaliseren dat je de data comprimeert?
Ik bedoel dus dit: Zeg dat je er voor kiest om alleen maar blokken met een grootte van tien decimalen zoekt. dit betekend dat de verwijzing naar dit blok niet grote mag zijn dan 2x5 getallen oftewel tot 99.999. Op deze maniet moet het toch te berekenen zijn waar een optimum ligt voor de grootte van pi.dat en hoe groot je bijbehorende blok moet zijn?

Op bovenstaande site staat bijvoorbeeld dat elke 3 letter combinatie een kans van 100% heeft om gevonden te hebben in een pi bestand van 1.500.000 decimalen. Voor blokken van 5 zijn er 16 miljoen nodig voor dezelfde kans. Dus een dergelijke optimalisatie kan wel...

[Verwijderd]

Zoijar schreef op 20 september 2004 @ 13:23:
Uit deze reeks: sum(n=1->inf) n*(1-p)^(n-1)*p = 1/p, waar ik even niet op kwam. Geometrische verdeling is het. Zoiets moet er toch wel even bij hoor, zeg dan in ieder geval volgens de geometrische verdeling die verwachting 1/p heeft is de verwachte lengte nu zoveel.

Oh, zo bedoelde je, ik vond het zo vanzelfsprekend dat ik je even niet begreep

Maar zijn de proeven wel onafhankelijk? (ik bedoel, als er in het midden bv in jouw reeks "11" staat, en in pi "22", dan weet je al dat de volgende proef ook zeker gaat mislukken, ongeacht het volgende begin getal.)

Daarom ga ik uit van individuele bits, dat maakt het meestal duidelijker: als ik een 0 voorspel en er staat een 1 in de string, dan heeft dat geen invloed op mijn volgende voorspelling (noch op het volgende bit in de string), dus zijn de voorspellingen en kansen onafhankelijk.

[Verwijderd]

Een reeks gehele getallen (theoretisch elke) is zonder veel poespas om te zetten in een getal tussen de 0 en de 1. Het aantal en de grootte van die getallen bepalen wel in hoeverre dat getal mag worden afgerond (of ook wel hoeveel data het in beslag neemt)

[ Voor 4% gewijzigd door Verwijderd op 21-09-2004 03:18 ]

[Verwijderd]

Oke, maar nu neem ik een ander getal. Het getal dat achtereenvolgens alle getallen opsomt, behalve als deze al in het getal voorkwamen. Dus het getal:

123456789101131415161718192021224252627282930...

Komt een willekeurig getal n hier niet naar verwachting eerder voor dan op de n-de decimaal?

Vast niet hoor, maar als we nu eens een zo optimaal mogelijk dergelijk getal proberen te construeren (dus een getal dat met zo weinig mogelijk decimalen (zeg n), alle getallen onder de n bevat), lukt dat misschien? En zo nee, waarom niet?

[ Voor 5% gewijzigd door Verwijderd op 21-09-2004 17:19 ]

[Verwijderd]

Voor 1 en 2 digits:

01234567890020304050607080910113141516171819212242526272829323353637383943446474849545575859656686976779878899

Is trouwens precies 110 karakters lang....


Edit ok dit is iets korter:
00102030405060708091121314151617181922324252627282933435363738394454647484955657585966768697787988990

[ Voor 44% gewijzigd door Verwijderd op 21-09-2004 19:06 ]

[Zoijar]

Verwijderd schreef op 21 september 2004 @ 03:17:
Een reeks gehele getallen (theoretisch elke) is zonder veel poespas om te zetten in een getal tussen de 0 en de 1. Het aantal en de grootte van die getallen bepalen wel in hoeverre dat getal mag worden afgerond (of ook wel hoeveel data het in beslag neemt)

Dat komt neer op arithmetic coding toch? Dat wordt veel gebruikt in bestaande compressie.

[Verwijderd]

Inderdaad, maar AC kan op een moeilijke en makkelijke manier.
De makkelijkste is zelfs zonder voorkennis van de gegevens met een rekenmachine te doen.

[MSalters]

TlighT schreef op 20 september 2004 @ 12:55:
quote:
elnino schreef op 20 september 2004 @ 12:10:
Is het trouwens bewezen dat iedere getalvolgorde in pi moet voorkomen? Het zijn natuurlijk heel veel getallen en vele combinaties zijn mogelijk, maar is het niet mogelijk dat bijv. 1 combinatie helemaal niet zal voorkomen?
Volgens wikipedia:
quote:
The most pressing open question about π is whether it is a normal number, i.e. whether any digit block occurs in the expansion of π just as often as one would statistically expect if the digits had been produced completely "randomly". This must be true in any base, not just in base 10. Current knowledge in this direction is very weak; e.g., it is not even known which of the digits 0,...,9 occur infinitely often in the decimal expansion of π.

Nee dus (het is nog niet bewezen).

De eis die op wikeipedia wordt gesteld lijkt me sterker; daar gaat het om "just as often" en elnino vroeg om >=1. Als het cijfer 9 maar in 5% van de decimalen voorkomt, dan is het getal niet normaal.
Overigens zijn getalvolgordes van N decimale cijfers te transformeren naar losse cijfers in het 10^N tallige stelsel.

[genosis]

Paul Nieuwkamp schreef op 20 september 2004 @ 00:56:
(stel dat we het beperken tot een file pi.dat van 700MB, of zelfs 4.7TB, om het iig nog redelijk distribueerbaar te houden)

ik neem aan dat je GB bedoelt?