How to resolve the algorithm Huffman coding step by step in the Zig programming language

Published on 12 May 2024 09:40 PM
#Zig

How to resolve the algorithm Huffman coding step by step in the Zig programming language

Table of Contents

Problem Statement

Huffman encoding is a way to assign binary codes to symbols that reduces the overall number of bits used to encode a typical string of those symbols. For example, if you use letters as symbols and have details of the frequency of occurrence of those letters in typical strings, then you could just encode each letter with a fixed number of bits, such as in ASCII codes. You can do better than this by encoding more frequently occurring letters such as e and a, with smaller bit strings; and less frequently occurring letters such as q and x with longer bit strings. Any string of letters will be encoded as a string of bits that are no-longer of the same length per letter. To successfully decode such as string, the smaller codes assigned to letters such as 'e' cannot occur as a prefix in the larger codes such as that for 'x'. The Huffman coding scheme takes each symbol and its weight (or frequency of occurrence), and generates proper encodings for each symbol taking account of the weights of each symbol, so that higher weighted symbols have fewer bits in their encoding. (See the WP article for more information). A Huffman encoding can be computed by first creating a tree of nodes:

Traverse the constructed binary tree from root to leaves assigning and accumulating a '0' for one branch and a '1' for the other at each node. The accumulated zeros and ones at each leaf constitute a Huffman encoding for those symbols and weights:

Using the characters and their frequency from the string: create a program to generate a Huffman encoding for each character as a table.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Huffman coding step by step in the Zig programming language

Source code in the zig programming language

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);
        },
    }
}

You may also check:How to resolve the algorithm Sort a list of object identifiers step by step in the Java programming language
You may also check:How to resolve the algorithm Knight's tour step by step in the 360 Assembly programming language
You may also check:How to resolve the algorithm Parametric polymorphism step by step in the Visual Prolog programming language
You may also check:How to resolve the algorithm Hello world/Line printer step by step in the M2000 Interpreter programming language
You may also check:How to resolve the algorithm Increment a numerical string step by step in the MATLAB programming language