一个国外牛人JavaScript实现的Huffman对代码进行压缩的方法

functionMakeIntoString(S){
　S=StringReplace("","\",S);
　S=StringReplace(""",""",S);
　S=StringReplace("n"," ",S);
　returnS;
}
functionBitsToBytes(i){
　o=42;
　if(i.charAt(0)=='1')
　　　o+=32;
　if(i.charAt(1)=='1')
　　　o+=16;
　if(i.charAt(2)=='1')
　　　o+=8;
　if(i.charAt(3)=='1')
　　　o+=4;
　if(i.charAt(4)=='1')
　　　o+=2;
　if(i.charAt(5)=='1')
　　　o+=1;
　if(o>=92)
　　　o++;
　returnString.fromCharCode(o);
}
functionCompressConfirm(){
　if(confirm("Areyousurethatyouwanttodothis?　Itcantakealongtime!")){
　　　CompressCode();
　}
}
functionCompressCode(){
　//Doinitialscan
　varLetters=newArray(256);
　varLetterCodes=newArray(256);
　varC=document.daForm.Comp;
　varP=document.daForm.Progress;
　varov=document.daForm.Orig.value;
　C.value="Working";
　P.value="CountingLetters";
　for(i=0;i<256;i++)
　{
　　　Letters[i]=0;
　}
　for(i=0;i<ov.length;i++)
　{
　　　if((i&0xFF)==0)
　　　　P.value="CountingLetters-"+
　　　　Math.floor((100*i)/ov.length)+"%"
　　　Letters[ov.charCodeAt(i)]++;
　}
//　Thisisatestingtree
//　Itshouldproducealistlikethis:
//　　　　　　　__[　]__
//　　　　[　]~~　　　　~~[　]__
//　　　50　　51　　　　52　　　~~[　]
//　　　　　　　　　　　　　　　53　　54
//
//　Letters[50]=7;
//　Letters[51]=6;
//　Letters[52]=5;
//　Letters[53]=2;
//　Letters[54]=1;
　//BuildaHuffmantreefromthelettercountfrequencies
　varNodeLetter=newArray(512);
　varNodeCount=newArray(512);
　varNodeChild1=newArray(512);
　varNodeChild2=newArray(512);
　NextParent=0;
　P.value="Constructingnodelist";
　for(i=0;i<256;i++)
　{
　　　if(Letters[i]>0)
　　　{
　　　　NodeLetter[NextParent]=i;
　　NodeCount[NextParent]=Letters[i];
　　NodeChild1[NextParent]=-1;
　　NodeChild2[NextParent]=-1;
　　NextParent++;
　　　}
　}
　//Builtnodelist.　Nowcombinenodestomakeatree
　P.value="Constructingtree";
　SmallestNode2=1;
　while(SmallestNode2!=-1)
　{
　　　SmallestNode1=-1;
　　　SmallestNode2=-1;
　　　for(i=0;i<NextParent;i++)
　　　{
　　　　if(NodeCount[i]>0)
　　{
　　　　if(SmallestNode1==-1)
　　　　{
　　　　　SmallestNode1=i;
　　　　}
　　　　elseif(SmallestNode2==-1)
　　　　{
　　　　　if(NodeCount[i]<NodeCount[SmallestNode1])
　　　　　{
　　　　　　　SmallestNode2=SmallestNode1;
　　　　　SmallestNode1=i;
　　　　　}
　　　　　else
　　　　　{
　　　　　　　SmallestNode2=i;
　　　　　}
　　　　}
　　　　elseif(NodeCount[i]<=NodeCount[SmallestNode1])
　　　　{
　　　　　SmallestNode2=SmallestNode1;
　　　　　SmallestNode1=i;
　　　　}
　　}
　　　}
　　　if(SmallestNode2!=-1)
　　　{
　　　　NodeCount[NextParent]=NodeCount[SmallestNode1]+
　　　　NodeCount[SmallestNode2];
　　NodeCount[SmallestNode1]=0;
　　NodeCount[SmallestNode2]=0;
　　//ReversedSmallestNodenumbersherefororderinginthetree
　　NodeChild1[NextParent]=SmallestNode2;
　　NodeChild2[NextParent]=SmallestNode1;
　　NextParent++;
　　　}
　}
　//Wehaveconstructedthenodes.　Nowrewritethelistintoasingle
　//array.
　//Thevalueofanarrayelementwillbepositiveifitisthe
　//charactercodewewant.　Otherwise,itbranches.　Theleftbranch
　//willbethenextarrayelement.　Thevalueofthearraywillbe
　//(offset*-1),whichistherightbranch.
　P.value="Makingfinalarray";
　varFinalNodes=Array(NextParent);
　varDepthIndex=Array(256);
　Depth=0;
　NextFinal=0;
　DepthIndex[Depth]=SmallestNode1;
　while(Depth>=0)
　{
　　　//Ifthereisaleftandright,pushthemonthestack
　　　if(NodeChild1[DepthIndex[Depth]]>-1&&
　　　　NodeChild2[DepthIndex[Depth]]>-1)
　　　{
　　　　idx=NodeChild1[DepthIndex[Depth]];
　　NodeChild1[DepthIndex[Depth]]=-2-NextFinal;
　　Depth++;
　　DepthIndex[Depth]=idx;
　　NextFinal++;
　　　}
　　　//Ifthereisaleftandaright,buttheleftwastaken,
　　　//pushtherightonthestack.
　　　elseif(NodeChild1[DepthIndex[Depth]]<0&&
　　　　NodeChild2[DepthIndex[Depth]]>-1)
　　　{
　　//UpdatetheFinalNodes[]withthelocationfortheright
　　//branch.
　　idx=NodeChild1[DepthIndex[Depth]];
　　idx=0-idx;
　　idx-=2;
　　FinalNodes[idx]=-NextFinal;
　　//Traverserightbranch
　　　　idx=NodeChild2[DepthIndex[Depth]];
　　NodeChild2[DepthIndex[Depth]]=-2
　　Depth++;
　　DepthIndex[Depth]=idx;
　　　}
　　　//Iftherewasaleftandaright,buttheywerebothtaken,
　　　//popupalevel
　　　elseif(NodeChild1[DepthIndex[Depth]]<-1&&
　　　　NodeChild2[DepthIndex[Depth]]<-1)
　　　{
　　　　Depth--;
　　　}
　　　//Ifwehaveachildhere,addittothefinalnodes,popup
　　　elseif(NodeChild1[DepthIndex[Depth]]==-1&&
　　　　NodeChild2[DepthIndex[Depth]]==-1)
　　　{
　　　　FinalNodes[NextFinal]=NodeLetter[DepthIndex[Depth]];
　　NextFinal++;
　　Depth--;
　　　}
　　　//Thisshouldn'teverhappen
　　　else
　　　{
　　　　alert('Badalgorithm!');
　　return;
　　　}
　}
　//Wehavethetree.　Associatecodeswiththeletters.
　P.value="Determiningcodes";
　varCodeIndex=newArray(256);
　DepthIndex[0]=0;
　CodeIndex[0]="";
　Depth=0;
　while(Depth>=0)
　{
　　　if(FinalNodes[DepthIndex[Depth]]<0)
　　　{
　　　　c=CodeIndex[Depth];
　　　　idx=DepthIndex[Depth];
　　　　DepthIndex[Depth+1]=DepthIndex[Depth]+1;
　　CodeIndex[Depth+1]=c+'0';
　　DepthIndex[Depth]=0-FinalNodes[idx];
　　CodeIndex[Depth]=c+'1';
　　Depth++;
　　　}
　　　else
　　　{
　　　　LetterCodes[FinalNodes[DepthIndex[Depth]]]=CodeIndex[Depth];
　　Depth--;
　　　}
　}
　//Buildresultingdatastream
　//Thebitsstringcouldgetverylarge
　P.value="Buildingdatastream";
　bits="";
　bytes="";
　for(i=0;i<ov.length;i++)
　{
　　　if((i&0xFF)==0)
　　　{
　　　　P.value="BuildingDataStream-"+
　　　　Math.floor((100*i)/ov.length)+"%";
　　　}
　　　bits+=LetterCodes[ov.charCodeAt(i)];
　　　while(bits.length>5)
　　　{
　　　　bytes+=BitsToBytes(bits);
　　bits=bits.slice(6,bits.length);
　　　}
　}
　bytes+=BitsToBytes(bits);
　P.value="Writingfinalscript"
　S="<scr"+"iptlanguage="JavaScript1.2">n<!--n";
　encodedNodes="";
　for(i=0;i<FinalNodes.length;i++){
　　　varx,y;
　　　x=FinalNodes[i]+512;
　　　y=x&0x3F;
　　　x>>=6;
　　　x&=0x3F;
　　　x+=42;
　　　y+=42;
　　　if(x>=92)
　　　　　x++;
　　　if(y>=92)
　　　　y++;
　　　encodedNodes+=String.fromCharCode(x)+String.fromCharCode(y);
　}
　S+='a=';
　while(encodedNodes.length>74)
　{
　　　S+='"'+encodedNodes.slice(0,74)+""n+";
　　　encodedNodes=encodedNodes.slice(74,encodedNodes.length);
　}
　S+='"'+encodedNodes+"";n";
　S+="l=newArray();n";
　S+="while(a.length){l.push((Y(a.charCodeAt(0))<<6)+Y(a.charCodeAt(1))-512);n"
　S+="a=a.slice(2,a.length)}n";
　S+='d=';
　while(bytes.length>74)
　{
　　　S+='"'+bytes.slice(0,74)+""n+";
　　　bytes=bytes.slice(74,bytes.length);
　}
　S+='"'+bytes+"";n";
　S+='c='+ov.length+";e=b=a=0;o="";n";
　S+="functionY(y){if(y>92)y--;returny-42}n";
　S+="functionB(){if(a==0){b=Y(d.charCodeAt(e++));a=6;}n";
　S+="return((b>>--a)&0x01);}n";
　S+="while(c--){i=0;while(l[i]<0){if(B())i=-l[i];elsei++;}n";
　S+="o+=String.fromCharCode(l[i]);}document.write(o);n";
　S+="//--></scr"+"ipt>";
　C.value=S;
　P.value="Done.　Compressedby"+
　　　Math.floor(100*(ov.length-S.length)/
　　　ov.length)+"%("+
　　　ov.length+"->"+S.length+")"
}