Last active
September 2, 2025 00:39
-
-
Save AbeEstrada/030e6ce2c6dedb28502b4ada28c0a1a9 to your computer and use it in GitHub Desktop.
Exercise: Tree Huffman Decoding
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function analyzeFrequencies(str) { | |
| const frequencies = {}; | |
| for (const char of str) { | |
| frequencies[char] = (frequencies[char] || 0) + 1; | |
| } | |
| return frequencies; | |
| } | |
| // Factory function for leaf node | |
| function createLeaf(char, frequency) { | |
| return { | |
| data: { char, frequency }, | |
| left: null, | |
| right: null, | |
| isLeaf: true | |
| }; | |
| } | |
| // Factory function for internal node | |
| function createInternal(left, right) { | |
| const frequency = (left.data?.frequency || 0) + (right.data?.frequency || 0); | |
| return { | |
| data: { frequency }, | |
| left, | |
| right, | |
| isLeaf: false | |
| }; | |
| } | |
| // Build Huffman tree using min-heap (sorted array) | |
| function constructHuffmanTree(frequencies) { | |
| // Create leaf nodes | |
| let nodes = Object.entries(frequencies) | |
| .map(([char, freq]) => createLeaf(char, freq)); | |
| // Sort by frequency (min heap simulation) | |
| while (nodes.length > 1) { | |
| nodes.sort((a, b) => b.data.frequency - a.data.frequency); // Descending for pop() | |
| const right = nodes.pop(); | |
| const left = nodes.pop(); | |
| const parent = createInternal(left, right); | |
| nodes.push(parent); | |
| } | |
| return { root: nodes[0] || null }; // Return tree like object | |
| } | |
| function huffmanTree(str) { | |
| const frequencies = analyzeFrequencies(str); | |
| return constructHuffmanTree(frequencies); | |
| } | |
| function buildEncodingMap(root) { | |
| const map = {}; | |
| function traverse(node, path) { | |
| if (!node) return; | |
| if (node.isLeaf) { | |
| map[node.data.char] = path; | |
| return; | |
| } | |
| traverse(node.left, path + '0'); | |
| traverse(node.right, path + '1'); | |
| } | |
| traverse(root, ''); | |
| return map; | |
| } | |
| function huffmanEncode(str, huffmanTree) { | |
| if (!huffmanTree.root) return ''; | |
| const encodingMap = buildEncodingMap(huffmanTree.root); | |
| return str.split('').map(char => encodingMap[char] || '').join(''); | |
| } | |
| function huffmanDecode(bits, huffmanTree) { | |
| if (!huffmanTree.root) return ''; | |
| let result = ''; | |
| let current = huffmanTree.root; | |
| for (const bit of bits) { | |
| current = bit === '0' ? current.left : current.right; | |
| if (!current) { | |
| throw new Error('Invalid bit stream: traversal went off tree'); | |
| } | |
| if (current.isLeaf) { | |
| result += current.data.char; | |
| current = huffmanTree.root; // Reset | |
| } | |
| } | |
| return result; | |
| } | |
| function processData(input) { | |
| const tree = huffmanTree(input); | |
| const encoded = huffmanEncode(input, tree); | |
| const decoded = huffmanDecode(encoded, tree); | |
| console.log(decoded); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment