The Huffman algorithm is a lossless data compression algorithm used to compress data and reduce the amount of storage space required for data. It is widely used for text and image compression.
The algorithm works by assigning variable-length codes to characters in a string based on their frequency of occurrence. The characters that occur more frequently are assigned shorter codes, while characters that occur less frequently are assigned longer codes. The resulting variable-length codes are then used to compress the original string.
The Huffman algorithm in JavaScript is implemented as follows:
- Building the frequency table
function buildFrequencyTable(string) {
let frequencyTable = {};
for (let char of string) {
frequencyTable[char] = frequencyTable[char] + 1 || 1;
}
return frequencyTable;
}
This section of the code creates a frequency table for the given string. It creates an empty object frequencyTable and then loops through each character of the input string. For each character, it checks if it exists in the frequencyTable object and increases its frequency by 1. If it doesn’t exist, it adds the character to the frequencyTable with a frequency of 1. The frequency table is returned at the end.
- Building the Huffman Tree
class Node {
constructor(char, frequency) {
this.char = char;
this.frequency = frequency;
this.left = null;
this.right = null;
}
}
function buildHuffmanTree(frequencyTable) {
let nodes = [];
for (let char in frequencyTable) {
nodes.push(new Node(char, frequencyTable[char]));
}
while (nodes.length > 1) {
nodes.sort((a, b) => a.frequency - b.frequency);
let left = nodes.shift();
let right = nodes.shift();
let parent = new Node(null, left.frequency + right.frequency);
parent.left = left;
parent.right = right;
nodes.push(parent);
}
return nodes[0];
}
This section of the code builds the Huffman tree. It starts by creating a Node class that represents each node in the tree. Each node has a character, frequency, and left and right children. The buildHuffmanTree function takes the frequency table as input and creates an array of Node objects, one for each character in the frequency table. It then uses a while loop to build the Huffman tree by sorting the nodes based on frequency, combining the two nodes with the lowest frequency into a single parent node, and repeating until there is only one node left in the array. This final node is the root of the Huffman tree and is returned at the end.
- Encoding the string
function encode(root, string, encoding = '') {
if (!root) return;
if (!root.left && !root.right) {
console.log(`${root.char}: ${encoding}`);
return;
}
encode(root.left, string, encoding + '0');
encode(root.right, string, encoding + '1');
}
This section of the code encodes the input string using the Huffman tree. It starts at the root of the tree and uses a recursive function to traverse the tree. If a node doesn’t have any children, it is a leaf node and represents a character. The function logs the character and its encoding (the path from the root to the node) to the console. If the node has children, the function recursively calls itself on the left and right children, appending a 0 or 1 to the encoding depending on which child it is visiting.
- Decoding the string
function decode(root, encoded) {
let current = root;
let decoded = '';
for (let bit of encoded) {
if (bit === '0') {
current = current.left;
} else {
current = current.right;
}
if (!current.left && !current.right) {
decoded += current.char;
current = root;
}
}
return decoded;
}This section of the code decodes an encoded string using the Huffman tree. It starts at the root of the tree and uses a for loop to iterate through each bit of the encoded string. For each bit, it checks if it is a 0 or a 1 and moves to the corresponding left or right child in the tree. If it reaches a leaf node (a node without any children), it adds the character represented by that node to the decoded string and returns to the root of the tree. The final decoded string is returned at the end.
And finally, the complete code of the Huffman algorithm in JavaScript. To use the code, you would call the encode function with the root of the Huffman tree and the string you want to encode, and the decode function with the root of the Huffman tree and the encoded string you want to decode.
function buildFrequencyTable(string) {
let frequencyTable = {};
for (let char of string) {
frequencyTable[char] = frequencyTable[char] + 1 || 1;
}
return frequencyTable;
}
class Node {
constructor(char, frequency) {
this.char = char;
this.frequency = frequency;
this.left = null;
this.right = null;
}
}
function buildHuffmanTree(frequencyTable) {
let nodes = [];
for (let char in frequencyTable) {
nodes.push(new Node(char, frequencyTable[char]));
}
while (nodes.length > 1) {
nodes.sort((a, b) => a.frequency - b.frequency);
let left = nodes.shift();
let right = nodes.shift();
let parent = new Node(null, left.frequency + right.frequency);
parent.left = left;
parent.right = right;
nodes.push(parent);
}
return nodes[0];
}
function encode(root, string, encoding = '') {
if (!root) return;
if (!root.left && !root.right) {
console.log(`${root.char}: ${encoding}`);
return;
}
encode(root.left, string, encoding + '0');
encode(root.right, string, encoding + '1');
}
function decode(root, encoded) {
let current = root;
let decoded = '';
for (let bit of encoded) {
if (bit === '0') {
current = current.left;
} else {
current = current.right;
}
if (!current.left && !current.right) {
decoded += current.char;
current = root;
}
}
return decoded;
}
There are other algorithms that are similar to the Huffman algorithm, including the Arithmetic coding, LZW (Lempel-Ziv-Welch) and Run-length encoding algorithms. These algorithms also aim to reduce the amount of storage space required for data, but they use different methods to achieve this goal.
No Comments
Leave a comment Cancel