📄 de-compression.js
字号:
/* Copyright 2006 Christian Gross http://www.devspace.com From the book Ajax Patterns and Best Practices Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.*/<HTML><HEAD><TITLE>Huffman JavaScript Compression</TITLE><link REL="SHORTCUT ICON" HREF="/favicon.ico"><script language="JavaScript"><!-- function MakeIntoString(S) { S = StringReplace("\\", "\\\\", S); S = StringReplace("\"", "\\\"", S); S = StringReplace("\n", "\\n", S); return S;}function BitsToBytes(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 ++; return String.fromCharCode(o);}function CompressConfirm() { if (confirm("Are you sure that you want to do this? It can take a long time!")) { CompressCode(); }}function CompressCode() { // Do initial scan var Letters = new Array(256); var LetterCodes = new Array(256); var C = document.daForm.Comp; var P = document.daForm.Progress; C.value = "Working ..."; P.value = "Counting Letters"; for (i = 0; i < 256; i ++) { Letters[i] = 0; } for (i = 0; i < document.daForm.Orig.value.length; i ++) { if ((i & 0xFF) == 0) P.value = "Counting Letters - " + Math.floor((100 * i) / document.daForm.Orig.value.length) + "%" Letters[document.daForm.Orig.value.charCodeAt(i)] ++; }// This is a testing tree// It should produce a list like this:// __[ ]__// [ ]~~ ~~[ ]__// 50 51 52 ~~[ ]// 53 54//// Letters[50] = 7;// Letters[51] = 6;// Letters[52] = 5;// Letters[53] = 2;// Letters[54] = 1; // Build a Huffman tree from the letter count frequencies var NodeLetter = new Array(512); var NodeCount = new Array(512); var NodeChild1 = new Array(512); var NodeChild2 = new Array(512); NextParent = 0; P.value = "Constructing node list"; for (i = 0; i < 256; i ++) { if (Letters[i] > 0) { NodeLetter[NextParent] = i; NodeCount[NextParent] = Letters[i]; NodeChild1[NextParent] = -1; NodeChild2[NextParent] = -1; NextParent ++; } } // Built node list. Now combine nodes to make a tree P.value = "Constructing tree"; SmallestNode2 = 1; while (SmallestNode2 != -1) { SmallestNode1 = -1; SmallestNode2 = -1; for (i = 0; i < NextParent; i ++) { if (NodeCount[i] > 0) { if (SmallestNode1 == -1) { SmallestNode1 = i; } else if (SmallestNode2 == -1) { if (NodeCount[i] < NodeCount[SmallestNode1]) { SmallestNode2 = SmallestNode1; SmallestNode1 = i; } else { SmallestNode2 = i; } } else if (NodeCount[i] <= NodeCount[SmallestNode1]) { SmallestNode2 = SmallestNode1; SmallestNode1 = i; } } } if (SmallestNode2 != -1) { NodeCount[NextParent] = NodeCount[SmallestNode1] + NodeCount[SmallestNode2]; NodeCount[SmallestNode1] = 0; NodeCount[SmallestNode2] = 0; // Reversed SmallestNode numbers here for ordering in the tree NodeChild1[NextParent] = SmallestNode2; NodeChild2[NextParent] = SmallestNode1; NextParent ++; } } // We have constructed the nodes. Now rewrite the list into a single // array. // The value of an array element will be positive if it is the // character code we want. Otherwise, it branches. The left branch // will be the next array element. The value of the array will be // (offset * -1), which is the right branch. P.value = "Making final array"; var FinalNodes = Array(NextParent); var DepthIndex = Array(256); Depth = 0; NextFinal = 0; DepthIndex[Depth] = SmallestNode1; while (Depth >= 0) { // If there is a left and right, push them on the stack if (NodeChild1[DepthIndex[Depth]] > -1 && NodeChild2[DepthIndex[Depth]] > -1) { idx = NodeChild1[DepthIndex[Depth]]; NodeChild1[DepthIndex[Depth]] = -2 - NextFinal; Depth ++; DepthIndex[Depth] = idx; NextFinal ++; } // If there is a left and a right, but the left was taken, // push the right on the stack. else if (NodeChild1[DepthIndex[Depth]] < 0 && NodeChild2[DepthIndex[Depth]] > -1) { // Update the FinalNodes[] with the location for the right // branch. idx = NodeChild1[DepthIndex[Depth]]; idx = 0 - idx; idx -= 2; FinalNodes[idx] = - NextFinal; // Traverse right branch idx = NodeChild2[DepthIndex[Depth]]; NodeChild2[DepthIndex[Depth]] = -2 Depth ++; DepthIndex[Depth] = idx; } // If there was a left and a right, but they were both taken, // pop up a level else if (NodeChild1[DepthIndex[Depth]] < -1 && NodeChild2[DepthIndex[Depth]] < -1) { Depth --; } // If we have a child here, add it to the final nodes, pop up else if (NodeChild1[DepthIndex[Depth]] == -1 && NodeChild2[DepthIndex[Depth]] == -1) { FinalNodes[NextFinal] = NodeLetter[DepthIndex[Depth]]; NextFinal ++; Depth --; } // This shouldn't ever happen else { alert('Bad algorithm!'); return; } } // We have the tree. Associate codes with the letters. P.value = "Determining codes"; var CodeIndex = new Array(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 --; } } // Build resulting data stream // The bits string could get very large P.value = "Building data stream"; bits = ""; bytes = ""; for (i = 0; i < document.daForm.Orig.value.length; i ++) { if ((i & 0xFF) == 0) { P.value = "Building Data Stream - " + Math.floor((100 * i) / document.daForm.Orig.value.length) + "%"; } bits += LetterCodes[document.daForm.Orig.value.charCodeAt(i)]; while (bits.length > 5) { bytes += BitsToBytes(bits); bits = bits.slice(6, bits.length); } } bytes += BitsToBytes(bits); P.value = "Writing final script" S = "<scr" + "ipt language=\"JavaScript1.2\">\n<!--\n"; S += "l=new Array("; for (i = 0; i < FinalNodes.length; i ++) { if (i > 0) S += ","; // The % operator acts funny in a few browsers if (i > 0 && Math.floor(i / 20) == Math.ceil(i / 20)) S += "\n"; S += FinalNodes[i]; } S += ");\n"; S += "d="; while (bytes.length > 74) { S += '"' + bytes.slice(0, 74) + "\"\n+"; bytes = bytes.slice(74, bytes.length); } S += '"' + bytes + "\";\n"; S += 'c=' + document.daForm.Orig.value.length + ";b=a=0;o=\"\";\n"; S += "function GetBit(){if(a==0){b=d.charCodeAt(0)-42;\n"; S += "if(b>50)b--;d=d.slice(1,d.length);a=6;}a--;\n"; S += "return ((b >> a) & 0x01);}\n"; S += "window.status='Decompressing';\n"; S += "while(c--){i=0;while(l[i]<0){if(GetBit())i=-l[i];else i++;}\n"; S += "o+=String.fromCharCode(l[i]);}document.write(o);\n"; S += "window.status='Document Loaded';\n"; S += "// --></scr" + "ipt>"; C.value = S; P.value = "Done. Compressed by " + Math.floor(100 * (document.daForm.Orig.value.length - S.length) / document.daForm.Orig.value.length) + "% (" + document.daForm.Orig.value.length + " -> " + S.length + ")"}function CreatePopup(str){ ShowMeWindow = window.open("", "", "location=no,directories=no,menubar=no," + "resizable=yes,scrollbars=yes,status=yes,toolbar=no,width=300,height=240"); ShowMeWindow.document.write(str); ShowMeWindow.document.close();}--></script><!-- These pages are (C)opyright 2002-2005, Tyler Akins --><!-- Fake email for spambots: jsimmons@rumkin.com --><link rel="stylesheet" type="text/css" media="screen, projection" href="/inc/normal.css" title="Default"><link rel="stylesheet" type="text/css" media="print" href="/inc/print.css" title="Print"><script language=javascript src="/inc/site.js"></script><script language="JavaScript1.2" src="/inc/site2.js"></script></head><body><p><div> <table align=left border=0 cellpadding=0 cellspacing=0 class=menutable> <tr><td align=center><div class=menu> <a class="menu" href="/" onmouseover="CheckVer(1.2, 'MenuDesc(-1)')">Rumkin</a> | <a id="ml1" href="/fun/" onmouseover="CheckVer(1.2, 'MenuDesc(1)')" class="menu" onmouseout="CheckVer(1.2, 'SetMenuHide()')">Fun</a> | <a id="ml2" href="/reference/" onmouseover="CheckVer(1.2, 'MenuDesc(2)')" class="menu" onmouseout="CheckVer(1.2, 'SetMenuHide()')">Info</a> | <a id="ml0" href="/software/" onmouseover="CheckVer(1.2, 'MenuDesc(0)')" class="menu" onmouseout="CheckVer(1.2, 'SetMenuHide()')">Software</a> | <a id="ml3" href="/tools/" onmouseover="CheckVer(1.2, 'MenuDesc(3)')" class="menu" onmouseout="CheckVer(1.2, 'SetMenuHide()')">Tools</a> <ilayer name=dep1><layer name=dep2></layer></ilayer> <div class=submenu id=describe></div> </div> </tr></td></table> <h1 class="pagetitle">Huffman JavaScript Compression</h1></div></p><p>Huffman encoding is based on the principle that letters that appear morefrequently should have a smaller code than the ones that are used moreoften. So, in the English language, vowels would be used more than theletter 'z', and would get shorter codes. This javascript-based compressionexample uses this method to compress whatever you give it. It can work onweb pages, javascript code, and tons more. The downfall is that it isextremely slow. It also re-encodes the binary data in a method similar toUUEncode, which inflates 3 bytes of binary data to 4 bytes of textual data,so some of the awesome compression that is possible will be eliminated fromthe expansion of data.</p> <p>Here are my thoughts on this experiment:</p> <table align=center><tr><th>Good</th><th>Bad</th></tr><tr><td> <ul> <li>It works! <li>The decompression code really isn't all that big. <li>The decompression code isn't all that slow either. </ul></td><td> <ul> <li>The array for the nodes looks like it consumes way too much space. <li>Re-encoding the binary data (33% increase) negates the compression savings. <li>JavaScript <b>really</b> shouldn't be used for compressing data (too slow) </ul></td></tr></table><p>Test it out for yourself. Insert web pages, javascript, or just simpletext and then press the button. It can take quite a while (15k of a webpage takes minutes on my computer). The advantages of having it run allclient-side in JavaScript are that it is all client-side (you don't send anyconfidential data to my server) and it's quick to write.Start with small files and work your way larger.</p> <p>I have a feeling that this would work great if you performed thecompression across all of your pages if you could generate the "l" arraybased on the letter frequency of all of your web pages, and then put thedecompression code and the "l" array in an external .js file. You could dothis with only moderate difficulty with this script -- just edit the code and make a static Letters[] array.</p><form name="daForm"><P><B>Original:</b></p><textarea name="Orig" rows=10 cols=60></textarea><br><input type=button onClick="CompressConfirm()" value="Compress Code!"><br><B><input type=text size=60 name="Progress"></p><p>View results of the compression in a <ahref="javascript:CreatePopup(document.daForm.Comp.value);">popupwindow</a>.</p><p><B>Compressed:</B></p><textarea name="Comp" rows=10 cols=60></textarea></form><hr size=3><table cellpadding=0 cellspacing=0 width=100% border=0><tr><td valign=top width=65%><div class=topic><iframe width="100%" height=150 frameborder=1 name=topicif id=topicifallowTransparency=true src="/topic.php/compression?page=%2Ftools%2Fcompression%2Fcompress_huff.php&theme=normal&topic=compression"><script language="javascript"><!--ShowTopicLink();// --></script><noscript><a href="/topic.php/compression?page=%2Ftools%2Fcompression%2Fcompress_huff.php&theme=normal&topic=compression">See comments about this page.</a></noscript></iframe></div></td><td><div class=topic> </div></td><td valign=top align=right><div class=topic><font size=-2>A jellyfish is 95% water.</font><br><br></div><font size=-2>Tyler Akins <<SCRIPT LANGUAGE="JavaScript"><!--ML="n@m</=roai yft>\"dhl:.e";MI="38:A6E<5?289B=7C<9@9801=90;D0E=?><9@9801=90;D0E=348>";OT="";for(j=0;j<MI.length;j++){OT+=ML.charAt(MI.charCodeAt(j)-48);}document.write(OT);// --></SCRIPT><NOSCRIPT>Sorry, you need javascript to view this email address</noscript>></font></td></tr></table></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -