Huffman coding: Difference between revisions
Added a new Javascript code for Huffman encoding based on a translation of the 'c' code on this page.
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
BlackHorse (talk | contribs) (Added a new Javascript code for Huffman encoding based on a translation of the 'c' code on this page.) |
||
Line 3,532:
this is an example for huffman encoding
is decoded string same as original? true</pre>
{{trans|C}}
<syntaxhighlight lang = "javascript">
class node{
constructor(freq, char, left, right){
this.left = left;
this.right = right;
this.freq = freq;
this.c = char;
}
};
nodes = [];
code = {};
function new_node(left, right){
return new node(left.freq + right.freq, -1, left, right);;
};
function qinsert(node){
nodes.push(node);
nodes.sort(compareFunction);
};
function qremove(){
return nodes.pop();
};
function compareFunction(a, b){
return b.freq - a.freq;
};
function build_code(node, codeString, length){
if (node.c != -1){
code[node.c] = codeString;
return;
};
/* Left Branch */
leftCodeString = codeString + "0";
build_code(node.left, leftCodeString, length + 1);
/* Right Branch */
rightCodeString = codeString + "1";
build_code(node.right, rightCodeString, length + 1);
};
function init(string){
var i;
var freq = [];
var codeString = "";
for (var i = 0; i < string.length; i++){
if (isNaN(freq[string.charCodeAt(i)])){
freq[string.charCodeAt(i)] = 1;
} else {
freq[string.charCodeAt(i)] ++;
};
};
for (var i = 0; i < freq.length; i++){
if (freq[i] > 0){
qinsert(new node(freq[i], i, null, null));
};
};
while (nodes.length > 1){
qinsert(new_node(qremove(), qremove()));
};
build_code(nodes[0], codeString, 0);
};
function encode(string){
output = "";
for (var i = 0; i < string.length; i ++){
output += code[string.charCodeAt(i)];
};
return output;
};
function decode(input){
output = "";
node = nodes[0];
for (var i = 0; i < input.length; i++){
if (input[i] == "0"){
node = node.left;
} else {
node = node.right;
};
if (node.c != -1){
output += String.fromCharCode(node.c);
node = nodes[0];
};
};
return output
};
string = "this is an example of huffman encoding";
console.log("initial string: " + string);
init(string);
for (var i = 0; i < Object.keys(code).length; i++){
if (isNaN(code[Object.keys(code)[i]])){
} else {
console.log("'" + String.fromCharCode(Object.keys(code)[i]) + "'" + ": " + code[Object.keys(code)[i]]);
};
};
huffman = encode(string);
console.log("encoded: " + huffman + "\n");
output = decode(huffman);
console.log("decoded: " + output);
</syntaxhighlight>
<pre style='width: full; overflow: scroll'>
initial string: this is an example of huffman encoding
' ': 111
'a': 1011
'c': 00101
'd': 00100
'e': 1010
'f': 1101
'g': 00111
'h': 0101
'i': 1100
'l': 00110
'm': 0100
'n': 100
'o': 0111
'p': 00001
's': 0110
't': 00000
'u': 00011
'x': 00010
encoded: 000000101110001101111100011011110111001111010000101011010000001001101010111011111011110101000111101110101001011100111101010000101011100100110010000111
decoded: this is an example of huffman encoding
</pre>
=={{header|Julia}}==
| |||