Huffman coding: Difference between revisions
Content added Content deleted
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: | Line 3,532: | ||
this is an example for huffman encoding |
this is an example for huffman encoding |
||
is decoded string same as original? true</pre> |
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}}== |
=={{header|Julia}}== |