Back to site
Since 2004, our University project has become the Internet's most widespread web hosting directory. Here we like to talk a lot about web development, networking and server security. It is, after all, our expertise. To make things better we've launched this science section with the free access to educational resources and important scientific material translated to different languages.

Kompresija Javascripta, Ludilo

Florian Boesch
Rođen 1978
Volim da pišem softvere, igram se
3d stvarčicama i čitam naučnu
fantastiku.
Živim u Baselu, Švajcarska
pyalot@gmail.com
@pyalot

 

 

 

programiranje javascripta

____________________________________________________________________________

 

Pre nekoliko dana, napisao sam post o tome kako izvršiti n-body simulaciju u javascript-u pomoću canvas-a. Ali, ako bih želeo da to pothranim u js1k , moralo bi da stane u 1024 bajta. U postu koji sledi se radi o mom javascript kompresoru napisanomu u python-u. Počeću sa 3.1kb, a onda smanjivanjem doći do 1.4kb, a sa mojim algoritmom za kompresovanje do 0.9kb.

Ako ste već upoznati sa yui-compressor-om i sa daljim podešavanjem, možda ćete želeti da odmah pređete na Korak 3, gde objašnjavam kako sam napravio samo-deflacionirani kod za javascript.

bash

ls -l gravity.js -rw-r--r-- 1 pyalot pyalot 3253 2010-08-25 13:48 gravity.js

Nekompresovanu verziju koda želim da pothranim do veličine od 3253 bajta. Uh, to je mnogo veće od 1024 bajta.

Preuzmite

Možete preuzeti izvor za ludi kompresor ako želite sami da se igrate njime

Korak 1 - YUI Compressor

Ovo je prilično fin javascript kompresor, on analizira javascript i radi sve vrste optimizacija. Pokretanje mog koda kroz sledeće:

bash

yui-compressor gravity.js > script.js ls -l script.js -rw-r--r-- 1 pyalot pyalot 1800 2010-08-25 15:59 script.js

Aha, to je već bolje, smanjio sam na 1800 bajtova. Pogledajmo šta smo dobili i da li ima prostora za neko poboljšanje.

javascript

function Vector(a,b){this.x=a;this.y=b;this.sub=function(c) {return new Vector(this.x-c.x,this.y-c.y)};this.isub=functi on(c){this.x-=c.x;this.y-=c.y};this.iadd=function(c){this.x +=c.x;this.y+=c.y};this.size=function(){return Math.sqrt(th is.x*this.x+this.y*this.y)};this.idiv=function(c){this.x/=c ;this.y/=c};this.zero=function(){this.x=this.y=0};this.vali date=function(){if(isNaN(this.x+this.y)){this.x=this.y=0}}} function Particle(a){this.acceleration=new Vector(0,0);this .velocity=new Vector(Math.random()-0.5,Math.random()-0.5);t his.position=new Vector(Math.random()*a.width,Math.random() *a.height);this.step=function(b){this.acceleration.validate ();this.velocity.iadd(this.acceleration);speed=this.velocit y.size();if(speed>4){this.velocity.idiv(speed/4);speed=4}th is.position.iadd(this.velocity);this.acceleration.zero();if (this.position.x<0){this.position.x=0;this.velocity.x/=-2}e lse{if(this.position.x>a.width){this.position.x=a.width;thi s.velocity.x/=-2}}if(this.position.y<0){this.position.y=0;t his.velocity.y/=-2}else{if(this.position.y>a.height){this.p osition.y=a.height;this.velocity.y/=-2}}color=Math.round(sp eed*128);b.fillStyle="rgba("+(color-50)+","+(300-color)+",0 ,1)";b.beginPath();b.arc(this.position.x,this.position.y,sp eed+2,0,Math.PI*2,false);b.fill()}}gc="globalCompositionOpe ration";new (function System(){var a=document.getElementByI d("c");a.width=a.height=300;var c=a.getContext("2d");var d= [];for(var b=0;b<30;b++){d.push(new Particle(a))}setInterva l(function(){c[gc]="source-over";c.fillStyle="rgba(0,0,0,0. 2)";c.fillRect(0,0,a.width,a.height);c[gc]="lighter";for(va r l=0,g=30;l<g;l++){var f=d[l];for(var h=l+1;h<30;h++){var e=d[h];var k=f.position.sub(e.position);k.idiv(Math.pow(Mat h.max(10,k.size()),3)/5);e.acceleration.iadd(k);f.accelerat ion.isub(k)}f.step(c)}},40)});

Uradio je vrlo dobar posao, ali neke stvari bi mogle biti kompaktnije kao klasna imena Vektora/Čestica i gomila naziva metoda.

Korak 2 - Kompaktujte još

Postoji nekoliko vrlo jednostavnih paterna koje mogu ubiti regularnom ekspresijom. Naravno, nije baš bezbedno raditi to inače, ali za kratak kod koji je napisan da bi bio kompresovan, to je sasvim u redu. Napisao sam kratak script da bih još malo počistio:

python

#!/usr/bin/env python import re, sys method_re = re.compile(r'\.([a-zA-Z]+)') objects_re = re.compile('new ([a-zA-Z]+)') blacklist = [ 'length', 'random', 'getElementById', 'getContext', 'beginPath', 'arc', 'fill', 'push', 'globalCompositeOperation', 'fillStyle', 'pos', 'pow', 'sqrt', 'width', 'height', 'PI', 'fillRect', 'log', 'join', 'round', 'min', 'max', ] if __name__ == '__main__': source = sys.stdin.read() # replace method names with short symbols method_names = 'abcdefghijklmnopqrstuvwxyz' methods = set() for match in method_re.finditer(source): method = match.group(1) if method not in blacklist and len(method) > 1: methods.add(method) i = 0 for method in methods: source = source.replace(method, method_names[i]) i += 1 # replace obvious objectnames with symbols objects = set() for match in objects_re.finditer(source): name = match.group(1) objects.add(name) object_names = 'abcdefghijklmnopqrstuvwxyz'.upper() i = 0 for name in objects: source = source.replace(name, object_names[i]) i += 1 print source

Ono što radi je pretraživanje očiglednih imena metoda i ako se ona ne nalaze na pozadinskoj listi metoda, menja ih kodom jednog karaktera. Zatim traži očigledna imena objekata, i menja ih kodom jednog karaktera. Ako napišete dovoljno jednostavan kod, ta vrsta zamene je razumno bezbedna, za demo od 1024 bajta u svakom slučaju jeste.

Da vidimo šta sam dobio:

bash

yui-compressor gravity.js | ./compact > script.js ls -l script.js -rw-r--r-- 1 pyalot pyalot 1462 2010-08-25 16:05 script.js

Super, nije mnogo bolje, ali sam stigao do 1462 bajta, uklonivši 338 bytes. Bolje nego ništa, ali je i dalje preveliko.

Pogledajmo ponovo šta smo dobili i da li smo nešto propustili:

javascript

function A(a,b){this.x=a;this.y=b;this.c=function(c){return new A(this.x-c.x,this.y-c.y)};this.b=function(c){this.x-=c .x;this.y-=c.y};this.j=function(c){this.x+=c.x;this.y+=c.y} ;this.k=function(){return Math.sqrt(this.x*this.x+this.y*th is.y)};this.e=function(c){this.x/=c;this.y/=c};this.f=funct ion(){this.x=this.y=0};this.i=function(){if(isNaN(this.x+th is.y)){this.x=this.y=0}}}function B(a){this.a=new A(0,0);th is.h=new A(Math.random()-0.5,Math.random()-0.5);this.g=new A(Math.random()*a.width,Math.random()*a.height);this.d=func tion(b){this.a.i();this.h.j(this.a);speed=this.h.k();if(spe ed>4){this.h.e(speed/4);speed=4}this.g.j(this.h);this.a.f() ;if(this.g.x<0){this.g.x=0;this.h.x/=-2}else{if(this.g.x>a. width){this.g.x=a.width;this.h.x/=-2}}if(this.g.y<0){this.g .y=0;this.h.y/=-2}else{if(this.g.y>a.height){this.g.y=a.hei ght;this.h.y/=-2}}color=Math.round(speed*128);b.fillStyle=" rgba("+(color-50)+","+(300-color)+",0,1)";b.beginPath();b.a rc(this.g.x,this.g.y,speed+2,0,Math.PI*2,false);b.fill()}}g c="globalComgOperation";new (function System(){var a=docume nt.getElementById("c");a.width=a.height=300;var c=a.getCont ext("2d");var d=[];for(var b=0;b<30;b++){d.push(new B(a))}s etInterval(function(){c[gc]="source-over";c.fillStyle="rgba (0,0,0,0.2)";c.fillRect(0,0,a.width,a.height);c[gc]="lighte r";for(var l=0,g=30;l<g;l++){var f=d[l];for(var h=l+1;h<30; h++){var e=d[h];var k=f.g.c(e.g);k.e(Math.pow(Math.max(10,k .k()),3)/5);e.a.j(k);f.a.b(k)}f.d(c)}},40)});

Ne, izgleda da ništa ne nedostaje. Šta sada?

Korak 3 - Ja nisam odgovoran za vaše zdravlje

Predgovor: sve što sada sledi je potpuno beskorisno za generalnu upotrebu sem za 1k demo kompeticije i sličnog.

Kod i dalje sadrži sekvence koje se ponavljaju vrlo često, kao "this." ili "function" itd. Ne mogu ih umanjiti uobičajenim kompresorima zboj toga što sadrže ključne reči javascript-a. Samo kad bih imao neki mehanizam da ih prikuplja...

Ono što mi je potrebno je algoritam za pravu kompresiju. Problem sa njima leži u tome što obično grade tabele simbola i koriste višebajtovne kodove da ih indeksiraju. Nemam dovoljno prostora za tako nešto, ali mi jeste potrebna tabela simbola i neke vrste indeksa u njoj.

Slobodni karakteri?

Da vidimo da li postoji neki neiskorišćeni ascii karakter za kod.

python

def find_free(data): exclude = set('\n\\\r\t\x0b\x0c\'"') candidates = set(string.printable) - exclude return candidates - set(data) if __name__ == '__main__': data = sys.stdin.read().strip() data = data.replace('"', "'").replace('\n', '\\n') keys = find_free(data) print len(keys), keys

Isključujem line feed (\n), carriage return (\r), vertical tab (x0b) duple znake navoda (") i formiram izvod za novu stranicu (x0c) zbog toga što oni ne rade u javascript nizovima bez izlaženja. Isključujem tab (\t) zbog toga što želim da ga koristim kasnije. Sada zaista ima 32 neiskorišćena karaktera!

!#%$&769:?@DGFHKJLQUTWVYXZ_^`z|~

Poklapanje paterna

Kada bih mogao da zamenim zajedničke paterne u kodu sa ovim karakterima, mogao bih da uštedim prostor. Moram da pronađem zajedničke paterne, zato hajde da izbrojimo sve paterne koje kod sadrži.

python

def window_iter(data, length): for i in range(len(data) - length): yield data[i:i+length]

Ovo je klizni prozor iteratora, ako pozovete ovaj kod:

python

for window in window_iter(data, 10): print window

Dobićete nešto ovako:

&h.xLelse{ h.xLelse{i .xLelse{if xLelse{if( Lelse{if(9 else{if(9x lse{if(9x> se{if(9x>: e{if(9x>:$ ...

Ako izračunam broj javljanja paterna u izvoru i izračunam javljanje * len(patern), znaću šta je najbolje. Ovo je posao funkcije find_best.

python

def find_best(data): symbols = {} for size in range(2, 100): hit = False for window in window_iter(data, size): count = data.count(window) if count > 1: hit = True symbols[window] = count * size if not hit: break return sorted(symbols, key=symbols.__getitem__)[-1]

Izvođenje kompresije

Zamenio sam sva najbolja javljanja uspešno dok mi nije ponestalo stavki:

python

if __name__ == '__main__': data = sys.stdin.read().strip() data = data.replace('"', "'").replace('\n', '\\n') keys = find_free(data) symbols = [] while keys: sequence = find_best(data) key = keys.pop() data = data.replace(sequence, key) symbols.insert(0, key+sequence)

Sastavljanje

Sada imam tabelu simbola sa sekvencama odnosa i deo nečitljivog teksta. Potreban mi je javascript algoritam koji ih može dekompresovatit.

javascript

symbols = "the symbol table".split("\t"); data = "the remaining data"; do{ previous = data.length; for(i=0; i<symbols.length; i++){ symbol = symbols[i]; key = symbol[0]; sequence = symbol.substr(1,99); data = data.replace(key, sequence); } } while(previous != data.length) eval(data);

Ovaj algoritam širi svaki simbol u niz podataka sa sekvencama iz tabele za tu stavku, dok podaci ne prestanu da se šire.

Sada mi je potrebno da uvijem moju tablu simbola i podatke u šablon, a šablon mora biti i veoma kratak:

def wrap(symbols, data): template = '''\ s="%(symbols)s".split("%(symsep)s");d="%(data)s";\ do{p=d.length;for(i=0;i<s.length;i++){q=s[i];\ d=d.replace(q[0],q.substr(1,99))}}while(p!=d.length)\ eval(d)''' return template % { 'symsep' : '\t', 'data' : data, 'symbols' : '\t'.join(symbols), }

I konačno kompresovani kod mora biti izlazan za stdout:

print wrap(symbols, data)

python

Ovo verovatno ne može da radi, ili možda može?

Postoji oko 120 bajtova dodatnog koda za dekompresor, a format tabele simbola ima još dva bajta za svaki od 32 simbola. Ako malo svedemo račun, 1024-120-64 = 872 bajta. Potrebna mi je kompresija pre serijalizacije na 57% njegove originalne veličine, samo sa 32 simbola. Da li je uspelo?

bash

yui-compressor gravity.js | ./compact | ./jszip > script.js -rw-r--r-- 1 pyalot pyalot 1012 2010-08-25 17:25 script.js

Da! Uspelo je, smanjio sam na 1012 bajta! Ako želite da proverite , videćete da je javascript validan posle dekompresije.

Kako kod izgleda sada? Uvrnuto.

javascript

s="~=Yx&y |a. zif( `Kc$J ^=HA( _/=-2}} Zc[gc]=' X)} Yc. V&h. Wcolor T$return U$J=!y=0} Q;for(6 L0 , J!x K=#( Hnew FMath. G); D/=-2}else{if(? @speed ? !g. :.fillStyle='rgba( 9a.width 6var 7a.height &;! $){ %Math.random() #function !this.".split(" ");d="# A(a,b$J=a&y=b&cKcTHA(J-Yx,!y-YyX&b`-~-=Yy}&j`+~+=Yy}&kKTFs qrt(J*J+!y*!yX&e`/=c&y/=c}&fKU&iK$zisNaN(J+!y)U}}# B(a$!a^L 0)&h^%-0.5,%-0.5)&g^%*9,%*7)&dKb$!|i()Vj(!aG@=!h.k(Gz@>4$!h .e(@/4G@=4}?j(!h)&|f(Gz?x<0$?x=0VxDx>9$?x=9Vx_z?y<0$?y=0VyD y>7$?y=7Vy_W=Fround(@*128Gb:'+(W-50)+','+(300-W)+',L1)';b.b eginPath(Gb.arc(?x,?y,@+2,LFPI*2,falseGb.fill(X}gc='globalC omgOperation';H(# System($6a=document.getElementById('c'G9= 7=300;6c=|getContext('2d'G6d=[]Qb=0;b<30;b++$d.push(HB(a)Xs etInterval(#($Zsource-over';c:LLL0.2)';YfillRect(LL9,7GZlig hter'Ql=Lg=30;l<g;l++$6f=d[l]Qh=l+1;h<30;h++$6e=d[h];6k=f.g .c(e.gGk.e(Fpow(Fmax(1Lk.k()),3)/5Ge.|j(kGf.|b(kXf.d(cX},40 XG";do{p=d.length;for(i=0;i<s.length;i++){q=s[i];d=d.replac e(q[0],q.substr(1,99))}}while(p!=d.length)eval(d)

Moja js1k submisija je završena, i veoma se nadam počasnom pominjanju u vezi najboljeg elaborata šeme kompresije :)





Published (Last edited): 27-02-2013 , source: http://codeflow.org/entries/2010/aug/25/javascript-compression-madness/