Huffman coding: Difference between revisions
m
→{{header|Wren}}: Minor tidy
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
m (→{{header|Wren}}: Minor tidy) |
||
| (3 intermediate revisions by 2 users not shown) | |||
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}}==
Line 7,381 ⟶ 7,522:
{{libheader|Wren-queue}}
Note that the results differ from Java because the PriorityQueue implementation is not the same.
<syntaxhighlight lang="
class HuffmanTree {
Line 7,476 ⟶ 7,617:
x 1 11110
h 2 11111
</pre>
=={{header|Zig}}==
{{trans|Rust}}
<syntaxhighlight lang="zig">
const std = @import("std");
const Node = struct {
frequency: usize,
kind: union(enum) {
internal: struct {
left: *Node,
right: *Node,
},
leaf: u8,
},
fn initLeaf(frequency: usize, ch: u8) Node {
return .{
.frequency = frequency,
.kind = .{ .leaf = ch },
};
}
fn initInternal(
allocator: std.mem.Allocator,
left_child: Node,
right_child: Node,
) !Node {
const left = try allocator.create(Node);
const right = try allocator.create(Node);
left.* = left_child;
right.* = right_child;
return .{
.frequency = left_child.frequency + right_child.frequency,
.kind = .{ .internal = .{ .left = left, .right = right } },
};
}
fn deinit(self: Node, allocator: std.mem.Allocator) void {
switch (self.kind) {
.internal => |inner| {
inner.left.deinit(allocator);
inner.right.deinit(allocator);
allocator.destroy(inner.left);
allocator.destroy(inner.right);
},
.leaf => {},
}
}
fn compare(context: void, a: Node, b: Node) std.math.Order {
_ = context;
return std.math.order(a.frequency, b.frequency);
}
};
pub fn main() !void {
const text = "this is an example for huffman encoding";
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer std.debug.assert(gpa.deinit() == .ok);
const allocator = gpa.allocator();
var frequencies = std.AutoHashMap(u8, usize).init(allocator);
defer frequencies.deinit();
for (text) |ch| {
const gop = try frequencies.getOrPut(ch);
if (gop.found_existing) {
gop.value_ptr.* += 1;
} else {
gop.value_ptr.* = 1;
}
}
var prioritized_frequencies =
std.PriorityQueue(Node, void, Node.compare).init(allocator, {});
defer prioritized_frequencies.deinit();
var freq_it = frequencies.iterator();
while (freq_it.next()) |counted_char| {
try prioritized_frequencies.add(Node.initLeaf(
counted_char.value_ptr.*,
counted_char.key_ptr.*,
));
}
while (prioritized_frequencies.len > 1) {
try prioritized_frequencies.add(try Node.initInternal(
allocator,
prioritized_frequencies.remove(),
prioritized_frequencies.remove(),
));
}
const root = prioritized_frequencies.items[0];
defer root.deinit(allocator);
var codes = std.AutoArrayHashMap(u8, []const u8).init(allocator);
defer codes.deinit();
var arena = std.heap.ArenaAllocator.init(allocator);
defer arena.deinit();
try generateCodes(arena.allocator(), &root, &.{}, &codes);
const stdout = std.io.getStdOut().writer();
var code_it = codes.iterator();
while (code_it.next()) |item| {
try stdout.print("{c}: {s}\n", .{
item.key_ptr.*,
item.value_ptr.*,
});
}
}
fn generateCodes(
arena: std.mem.Allocator,
node: *const Node,
prefix: []const u8,
out_codes: *std.AutoArrayHashMap(u8, []const u8),
) !void {
switch (node.kind) {
.internal => |inner| {
const left_prefix = try arena.alloc(u8, prefix.len + 1);
std.mem.copy(u8, left_prefix, prefix);
left_prefix[prefix.len] = '0';
try generateCodes(arena, inner.left, left_prefix, out_codes);
const right_prefix = try arena.alloc(u8, prefix.len + 1);
std.mem.copy(u8, right_prefix, prefix);
right_prefix[prefix.len] = '1';
try generateCodes(arena, inner.right, right_prefix, out_codes);
},
.leaf => |ch| {
try out_codes.put(ch, prefix);
},
}
}
</syntaxhighlight>
{{out}}
<pre>
n: 000
m: 0010
d: 00110
t: 00111
o: 0100
h: 0101
x: 01100
r: 01101
c: 01110
u: 01111
s: 1000
g: 10010
p: 100110
l: 100111
a: 1010
i: 1011
: 110
e: 1110
f: 1111
</pre>
| |||