W3Schools 線上編輯器 - W3Schools 教學

Python

Java

class Node:
    def __init__(self, char=None, freq=0):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

nodes = []

def calculate_frequencies(word):
    frequencies = {}
    for char in word:
        if char not in frequencies:
            freq = word.count(char)
            frequencies[char] = freq
            nodes.append(Node(char, freq))

def build_huffman_tree():
    while len(nodes) > 1:
        nodes.sort(key=lambda x: x.freq)
        left = nodes.pop(0)
        right = nodes.pop(0)
        
        merged = Node(freq=left.freq + right.freq)
        merged.left = left
        merged.right = right
        
        nodes.append(merged)

return nodes[0]

def generate_huffman_codes(node, current_code, codes):
    if node is None:
        return

if node.char is not None:
        codes[node.char] = current_code

generate_huffman_codes(node.left, current_code + '0', codes)
    generate_huffman_codes(node.right, current_code + '1', codes)

def huffman_encoding(word):
    global nodes
    nodes = []
    calculate_frequencies(word)
    root = build_huffman_tree()
    codes = {}
    generate_huffman_codes(root, '', codes)
    return codes

def huffman_decoding(encoded_word, codes):
    current_code = ''
    decoded_chars = []

code_to_char = {v: k for k, v in codes.items()}

for bit in encoded_word:
        current_code += bit
        if current_code in code_to_char:
            decoded_chars.append(code_to_char[current_code])
            current_code = ''

return ''.join(decoded_chars)

word = "lossless"
codes = huffman_encoding(word)
encoded_word = ''.join(codes[char] for char in word)
decoded_word = huffman_decoding(encoded_word, codes)

print("Initial word:", word)
print("Huffman code:", encoded_word)
print("Conversion table:", codes)
print("Decoded word:", decoded_word)

#Python

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    char charValue;
    int freq;
    struct Node* left;
    struct Node* right;
} Node;

Node* nodes[256];
int nodeCount = 0;

void calculateFrequencies(const char* word) {
    int frequencies[256] = {0};
    int n = strlen(word);

for (int i = 0; i < n; i++) {
        frequencies[(unsigned char)word[i]]++;
    }

for (int i = 0; i < n; i++) {
        if (frequencies[(unsigned char)word[i]] > 0) {
            nodes[nodeCount] = (Node*)malloc(sizeof(Node));
            nodes[nodeCount]->charValue = word[i];
            nodes[nodeCount]->freq = frequencies[(unsigned char)word[i]];
            nodes[nodeCount]->left = NULL;
            nodes[nodeCount]->right = NULL;
            frequencies[(unsigned char)word[i]] = 0;  // Prevent duplicates
            nodeCount++;
        }
    }
}

void insertionSort(Node* arr[], int n) {
    for (int i = 1; i < n; i++) {
        Node* key = arr[i];
        int j = i - 1;

while (j >= 0 && arr[j]->freq > key->freq) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Node* buildHuffmanTree() {
    while (nodeCount > 1) {
        insertionSort(nodes, nodeCount);

Node* left = nodes[0];
        Node* right = nodes[1];

Node* merged = (Node*)malloc(sizeof(Node));
        merged->charValue = '\0';
        merged->freq = left->freq + right->freq;
        merged->left = left;
        merged->right = right;

// Remove the first two elements and add the merged node
        for (int i = 2; i < nodeCount; i++) {
            nodes[i - 2] = nodes[i];
        }
        nodeCount -= 2;

nodes[nodeCount++] = merged;
    }

return nodes[0];
}

void generateHuffmanCodes(Node* node, char* currentCode, int depth, char codes[256][256]) {
    if (node == NULL) {
        return;
    }

if (node->charValue != '\0') {
        strncpy(codes[(unsigned char)node->charValue], currentCode, depth);
        codes[(unsigned char)node->charValue][depth] = '\0';
    }

if (node->left) {
        currentCode[depth] = '0';
        generateHuffmanCodes(node->left, currentCode, depth + 1, codes);
    }

if (node->right) {
        currentCode[depth] = '1';
        generateHuffmanCodes(node->right, currentCode, depth + 1, codes);
    }
}

void huffmanEncoding(const char* word, char codes[256][256]) {
    nodeCount = 0;
    calculateFrequencies(word);
    Node* root = buildHuffmanTree();

char currentCode[256];
    generateHuffmanCodes(root, currentCode, 0, codes);
}

char* huffmanDecoding(const char* encodedWord, char codes[256][256]) {
    static char decodedWord[256];
    int decodedWordIndex = 0;
    int n = strlen(encodedWord);
    char currentCode[256];
    int currentCodeIndex = 0;

for (int i = 0; i < n; i++) {
        currentCode[currentCodeIndex++] = encodedWord[i];
        currentCode[currentCodeIndex] = '\0';

for (int j = 0; j < 256; j++) {
            if (strcmp(currentCode, codes[j]) == 0) {
                decodedWord[decodedWordIndex++] = j;
                currentCodeIndex = 0;
                break;
            }
        }
    }

decodedWord[decodedWordIndex] = '\0';
    return decodedWord;
}

int main() {
    const char* word = "lossless";
    char codes[256][256] = {0};

huffmanEncoding(word, codes);

char encodedWord[1024] = "";
    for (int i = 0; word[i] != '\0'; i++) {
        strcat(encodedWord, codes[(unsigned char)word[i]]);
    }

printf("Word: %s\n", word);
    printf("Huffman code: %s\n", encodedWord);
    printf("Conversion table:\n");
    for (int i = 0; i < 256; i++) {
        if (codes[i][0] != '\0') {
            printf("%c: %s\n", i, codes[i]);
        }
    }

char* decodedWord = huffmanDecoding(encodedWord, codes);
    printf("Decoded word: %s\n", decodedWord);

return 0;
}

//C

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Node {
    char charValue;
    int freq;
    Node left;
    Node right;

Node(char charValue, int freq) {
        this.charValue = charValue;
        this.freq = freq;
        this.left = null;
        this.right = null;
    }

Node(int freq) {
        this.charValue = '\0';
        this.freq = freq;
        this.left = null;
        this.right = null;
    }
}

public class Main {
    static List<Node> nodes = new ArrayList<>();

public static void calculateFrequencies(String word) {
        Map<Character, Integer> frequencies = new HashMap<>();
        for (char charValue : word.toCharArray()) {
            if (!frequencies.containsKey(charValue)) {
                // Count the frequency of the character
                int freq = 0;
                for (char ch : word.toCharArray()) {
                    if (ch == charValue) {
                        freq++;
                    }
                }
                frequencies.put(charValue, freq);
                nodes.add(new Node(charValue, freq));
            }
        }
    }

public static Node buildHuffmanTree() {
        while (nodes.size() > 1) {
            nodes.sort((a, b) -> a.freq - b.freq); // Stable sorting by frequency
            Node left = nodes.remove(0);
            Node right = nodes.remove(0);

Node merged = new Node(left.freq + right.freq);
            merged.left = left;
            merged.right = right;

nodes.add(merged);
        }
        return nodes.get(0);
    }

public static void generateHuffmanCodes(Node node, String currentCode, Map<Character, String> codes) {
        if (node == null) {
            return;
        }

if (node.charValue != '\0') {
            codes.put(node.charValue, currentCode);
        }

generateHuffmanCodes(node.left, currentCode + '0', codes);
        generateHuffmanCodes(node.right, currentCode + '1', codes);
    }

public static Map<Character, String> huffmanEncoding(String word) {
        nodes.clear();
        calculateFrequencies(word);
        Node root = buildHuffmanTree();
        Map<Character, String> codes = new HashMap<>();
        generateHuffmanCodes(root, "", codes);
        return codes;
    }

public static String huffmanDecoding(String encodedWord, Map<Character, String> codes) {
        StringBuilder currentCode = new StringBuilder();
        StringBuilder decodedChars = new StringBuilder();

Map<String, Character> codeToChar = new HashMap<>();
        for (Map.Entry<Character, String> entry : codes.entrySet()) {
            codeToChar.put(entry.getValue(), entry.getKey());
        }

for (char bit : encodedWord.toCharArray()) {
            currentCode.append(bit);
            if (codeToChar.containsKey(currentCode.toString())) {
                decodedChars.append(codeToChar.get(currentCode.toString()));
                currentCode.setLength(0); // Clear the current code
            }
        }

return decodedChars.toString();
    }

public static void main(String[] args) {
        String word = "lossless";
        Map<Character, String> codes = huffmanEncoding(word);
        StringBuilder encodedWord = new StringBuilder();
        for (char charValue : word.toCharArray()) {
            encodedWord.append(codes.get(charValue));
        }
        String decodedWord = huffmanDecoding(encodedWord.toString(), codes);

System.out.println("Initial word: " + word);
        System.out.println("Huffman code: " + encodedWord);
        System.out.println("Conversion table: " + codes);
        System.out.println("Decoded word: " + decodedWord);
    }
}

//Java