一个国外牛人JavaScript实现的Huffman对代码进行压缩的方法
2010-09-14 13:18:53 来源:WEB开发网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+")"
}
更多精彩
赞助商链接