WEB开发网
开发学院网页设计JavaScript 一个国外牛人JavaScript实现的Huffman对代码进行压... 阅读

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

 2010-09-14 13:18:53 来源:WEB开发网   
核心提示:functionMakeIntoString(S){S=StringReplace("","\",S);S=StringReplace(""",""",S);S=StringReplace("n",&

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+")"
}

1 2  下一页

Tags:一个 国外 牛人

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接