[新着] Webテンプレートを仮オープンしました
//bit入出力関数
function BitIO(data,mode){
this.cnt=!mode<<3,
this.data=data||[],
this.buff=this.p=0}
BitIO.prototype={
//1bit読み込み
,getbit:function(){
return this.cnt--?this.buff>>this.cnt&1
:(this.buff=this.data[this.p++])>>(this.cnt=7)&1}
//n bits読み込み
,getbits:function(n){
for(var N;n;)N|=this.getbit()<<--n;
return N>>>0}
//1bit書き込み
,putbit:function(bit){
this.buff|=bit<<--this.cnt,
this.cnt||(this.data[this.p++]=this.buff&255,this.buff=0,this.cnt=8)}
//n bits書き込み
,putbits:function(n,x){
while(n)this.putbit(1<<--n&x)}
}
var A256=new Array(256),BASEFREQ=eval("["+A256.join("0,")+"0,1,2]")
//huffman木
function Huffman(n){
this.freq=BASEFREQ.slice(0),
this.bross=[257,256],
this.sworn=A256.concat(1,0),
this.parent=A256.concat(-257,0),
(this.right=[])[257]=256,
this.freq[this.bross[this.sworn[(this.left=[])[this.parent[n]=257]=n]=2]=n]++}
Huffman.prototype={
//符号化
encode:function(n,obj){
while(n=this.parent[n]||0)obj.putbit(n>0?0:(n=-n,1))}
//復号
,decode:function(obj){
for(var c=257;c>256;)c=this[obj.getbit()?"right":"left"][c];
return c}
//節追加
,addnode:function(c){
for(var d=this.bross.length-1,k=d,i=257+(k>>1),j;this.freq[this.bross[--k]]<=this.freq[this.bross[d]];);
j=this.parent[i]=this.parent[this.bross[++k]],
this.freq[j>0?this.left[j]=i:this.right[-j]=i]=1,
this.parent[this.right[i]=this.bross[k]]=-i,
this.parent[this.left[i]=c]=this.bross[this.sworn[i]=d+1]=i,
this.bross[this.sworn[c]=d+2]=c,
this.swapnode(k,d+1)}
//節交換
,swapnode:function(i,j,v,w){
v=this.bross[i],
w=this.bross[j],
this.bross[i]=w,
this.bross[j]=v,
i=this.sworn[w],
this.sworn[w]=this.sworn[v],
this.sworn[v]=i}
//木の更新
,update:function(i){
for(var j,v,w,y,z;j=w=this.sworn[i];i=(i=this.parent[i])<0?-i:i){
if(this.freq[this.bross[--w]]==this.freq[i]){
while(this.freq[this.bross[--w]]==this.freq[i]);
y=this.parent[v=this.bross[++w]],
z=this.parent[i],
this.parent[v]=z,
this.parent[i]=y,
z>0?this.left[z]=v:this.right[-z]=v,
y>0?this.left[y]=i:this.right[-y]=i,
this.swapnode(j,w)}
this.freq[i]++}
this.freq[i]++}
}
var N=256;//記号数
//圧縮
function compress(A){
var i=1,c=A[0],l=A.length,B=new BitIO(),j=c
,hc=[];//huffman木格納配列
for(B.putbits(24,l),B.putbits(8,c)
,hc[N]=new Huffman(c)//escape木
;(c=A[i++])>-1;j=c)
!hc[j]?( //まだ存在しない木?
hc[j]=new Huffman(c), //該当huffman木作成
escapeout(hc[N],B,c)) //escape符号出力
:hc[j].freq[c]?( //頻度情報がある?
hc[j].encode(c,B), //対応する符号出力
hc[j].update(c)) //木を更新
:(hc[j].encode(N,B),
escapeout(hc[N],B,c),
hc[j].addnode(c), //新しい節作成
hc[j].update(c));
if(hc[j])hc[j].encode(N,B);
hc[N].encode(N,B);return B.data}
//解凍
function decompress(A){
var i=0,B=new BitIO(A,1),l=B.getbits(24)-1,c=B.getbits(8),out=[c],j,hc=[];
for(hc[N]=new Huffman(c);i<l;)
!hc[j=c]? //対応する木が無い?
hc[j]=new Huffman(c=out[++i]=escapein(hc[N],B)) //escape符号入力,木を作成
:(c=hc[j].decode(B))<N? //復号値が256未満?
hc[j].update(out[++i]=c) //木を更新
:(hc[j].addnode(c=out[++i]=escapein(hc[N],B)),//escape符号の場合
hc[j].update(c));
return out}
function escapeout(H,B,c){
H.freq[c]? //既知のescape文字?
H.encode(c,B)
:(H.encode(N,B),
B.putbits(8,c),//escape文字出力
H.addnode(c)), //新しい節作成
H.update(c)} //escape木を更新
function escapein(H,B,c){
(c=H.decode(B))<N||H.addnode(c=B.getbits(8)),
H.update(c);
return c}
//実験
a=[[1,2,3,4,5],[1,2,1,2],[1,2,3,1,2,3]]
document.write(b=compress(a[0]),"<br>",decompress(b))