Compress

Razmišljam, kako najučinkoviteje kompresirati neko dato. Ideja je sledeča:

- datoteka se prebere in se za vse enake znake napravi sekvenca mest, ki jih zasedajo

Primer:

Znanost in tehnologija ...

z 1
n 2,4,10,15
a 3,22
o 5
....

- poišče se funkcijo(algoritem) za vsako sekvenco (to kar znata Eureqa ali Critticall)

- zapiše se komprimirana datoteka

Primer:

z 1
n 1.1917622+1.0221367*y*y-1.5289234*sin(0.8993634-1.0661639*y*y)-0.47005865*y 4
a 3,22
o 5
...

4 na koncu druge vrstice pove do kam naj šteje f(x) - za x = 1 to 4

Funkcija se zgenerira tako natančno, da z zaokroževanjem prideš do željenih rezultatov.
Če je funkcija daljša od sekvence, zapiši sekvenco.
Če funkcije ni mogoče najti, zapiši tako, ki pokrije največ vrednosti, nepokrite pa z novo funkcijo oz. sekvenco, če je ta krajša, ki je ločena s presledkom, itd...

Potem se pa novonastala kompresirana datoteka še zazipa

Ker nimam pojma kako delujejo drugi kompresi, prosim za mnenja?

Ja, tule se jasno bolj splača zapisat, samo če pa imaš par mega enakih znakov razsutih po datoteki, se pa imho ne.

Sam format je prikazan principelno, končen zapis bi bil seveda drugačen.

Ne vem zakaj nebi delovalo?

Eh, ne. Ni nujno, da je zapisan s polinomi. Si kdaj videl kakšne funkcije izpljune Eureqa?

Separatorji ne bodo pobrali nič več, kot je zgoraj napisano. V bistvu bi bili separatorji in markerji (ki bi povedali ali je funkcija ali sekvenca ali število do kam šteje) v enem.

Ne trdim, da so čarovnija. Nekatere sekvence se lahko zapišejo zelo enostavno, nekatere pa ne.

Razmišljam pa to, da bi imel na internetu look up tabelo vseh možnih sekvenc do recimo 10^12. Vsaka bi bila oštevilčena. Zapis bi bil enak zgornjemu, le namesto funkcije bi bila zaporedna številka sekvence v look up tabeli. Ker drugače bi zadeva predolgo trajala.

Sekvenca sama, njena formula, ni zastonj, gledano z vidika števila potrebnih bitov. Včasih sicer je, precej ceneje, kakor pa direktni zapis, v splošnem pa ne.

Vprašanje je, kaj je s človeku uporabnimi datami. Te morda celo imajo (večkrat) skrite vzorce, ki nam omogočajo, da jih zapišemo na učinkovit način.

Se ne ve. Treba bi bilo probat bruta forca, šele potem bi zares vedeli.

fave, proof is in the puding.
Poskusi sprogramirat prototipni kompres in v praksi preveri svojo idejo.

Men se v glavi že dolgo kuha kompresija z implicitnim privzetkom - pri kompresiji se del informacije sploh ne zapiše v datoteko ampak je ta privzeto znana uporabniku kompresirane datoteke. Poleg kompresije je hkrati to tudi tako švoh/crap šifriranje.

Recimo, da svojo datoteko poiščeš v nekem diskretnem zaporedju cifer 0..9 al pa števil 0..254, ki so rezultat neke funkcije. Za katero funkcijo točno gre, v sam kompres ne vpišeš ampak vpišeš samo začetno mesto Z in dolžino datoteke D. Detajli funkcije so tuki tisti implicitni privzetek.

Varianta je tut, da maš na razpolago N vnaprej določenih različnih funkcij, ki generirajo zaporedja ki so "pogosteje vsebujejo" določene tipe datotek. Tuki poleg Z in D v kompres vpišeš še id te v naprej določene funkcije.

Je pa res, da si ne predstavljam še praktičnega algoritma kompresije na ta način. Obstoječe zaporedne mašine so v principu neprimerne za takšno opravilo.

Katerega morš na koncu pretvorit v binarnega.

Razmišljaš prav a ne dovolj daleč.
122 v decimalnem zapisu zahteva tri bajte, ker imaš na vsakem mestu 256 možnih različnih znakov, "tebi uporabnih" je pa samo 10.
7A v hex obliki pokuri le dva bajta še, ker izmer 256 možnih na vsakem mestu ponucaš 16 različnih.
z ponuca samo en bajt ker "izkoristiš" vseh 256 možnih.

Ko razmišljaš o kompresiji moraš razmišljat v svoji temeljni abecedi, ki pa je binarna. 256-iški sistem zahteva 256 različnih simobolov. Teh v obstoječih mašinah nimaš, imaš le dva.

Kaj pa če vzamemo neko številko, ki ima neponavljujoče cifre.. recimo PI.

Vsakič, preden kompresiramo fajl, zaženemo kalkulator PI in zgeneriramo file velik 100GB ter pretvorimo v 0 in 1ke. Po tem pa vzamemo recimo prvih 10 cifer iz fajla, ki ga kompresiramo: pr: 0100010101 in poiščemo kje se ta sekvenca nahaja v našem PIju. Nato pa namesto zaporedja zapišemo koordinato te sekvence.

Zdej edino ne vem, kako velik bi mogel biti naš PI file, da bi lahko poiskali dovolj velike kose, da bi se taka kompresija splačala... dolžina koordinate VS iskanega zaporedja.

Pač osnova bi bila, pa to je moja blodnja - ne vem če to tudi stoji, da je v PIju ŽE skrito vsako zaporedje... samo koordinate le tega rabimo.

Kar se tiče kompresa s PI, distanca do tapravega stringa, zapisana binarno, je približno enako dolga kot tisti string. "1010101010" mora biti kakšnih 1024 bitov daleč. Neka random sekvenca se ne sme kaj bistveno podaljšati v tem načinu zapisovanja, ali pa Pi ni normalno število.

Kar se tiče kompresiranja s sekvencami, velja isto. Preveč podaljšati nekega random binarnega stringa, z zanj optimalno sekvenco ali funkcijo, ne bi smel. Katere bi pa bistveno skrajšal in koliko bi jih skrajšal, je pa everybody's guess.

moraš poleg odmika povedat še dolžino.

Right. Ampak dolžina je majhna napram temu. Dvojiški logaritem. Dvajset bitov za megabit velik string. Mogoče 40, če upoštevaš vso režijo.

Prvo pa zadnjo črko v besedi ohranimo, vmesne črke pa uredimo in damo v dictionary. To bi lahko bil primer lossy kompresiranega a še vedno berljivega teksta, kot je to dokazal nek profesor na Cambriški univerzi.

Bolj kot Huffmanov kod se teoretični meji približa Aritmetični kod.

Vsak zapis se izvede z neko abecedo. Zapis (2^n)+x predstavlja ID zaporedja v ASCII abecedi. Ker lahko v tej abecedi zapišeš tudi "neveljvane" IDje, ki ne generirajo veljavnega zaporedja imaš v abecedi nekaj redundance, kar pomeni da tako zapisan ID pobere več bitov, kot bi blo treba.

Še enkrat osnovni nasvet: poskusi sprogramirat nek kompresor in nato naštudiraj zakaj je rezultat takšen kot bo, glej velikost izhodne datoteke v bajtih. Tako boš skapiral osnovne probleme, tkole na suho preveč stvari narobe razumeš.

Ne sekiraj se, še vedno krepko zaostajaš za mano ;)

Tako je!

Saj veš tisto: En "neumen" lahko več vpraša kot 10 pametnih odgovori.

(Ali pa tisto: En pameten lahko več odgovori kot 10 "neumnih" vpraša.)

o+ nevone

Nevone, to je pa eno hudo protislovje :D