Comment implémenter l'algorithme de codage de Huffman en utilisant Java

Comment implémenter l'algorithme de codage de Huffman en Java

L'algorithme de codage de Huffman est une méthode efficace de compression des données, qui réduit l'espace de stockage et la transmission en utilisant des encodages plus courts pour un temps de caractères plus fréquent. Cet article explique comment utiliser Java pour implémenter l'algorithme de codage de Huffman et donne des exemples de code spécifiques.

1. Construction de l'arbre de Huffman

Tout d'abord, nous devons construire un arbre de Huffman. Un arbre de Huffman est un arbre binaire spécial dans lequel chaque nœud feuille correspond à un caractère, et chaque nœud non-feuille de l'arbre a deux nœuds enfants. Les étapes pour construire un arbre de Huffman sont les suivantes :

1.1 Créer une classe de nœuds

Tout d'abord, nous devons créer une classe de nœuds pour représenter les nœuds de l'arbre de Huffman. La classe de nœuds contient trois attributs : caractère, fréquence et nœuds enfants gauche et droit.

class Node {
    char data;
    int frequency;
    Node left;
    Node right;

    // 构造函数
    public Node(char data, int frequency){
        this.data = data;
        this.frequency = frequency;
        left = null;
        right = null;
    }
}

1.2 Construire un arbre de Huffman

Les étapes pour construire un arbre de Huffman sont les suivantes :

• Créez une liste de nœuds et insérez chaque caractère dans la liste en tant que nœud distinct.
• Triez la liste des nœuds de petite à grande fréquence.
• Supprimez les deux nœuds avec la plus petite fréquence de la liste des nœuds, créez un nouveau nœud comme nœud parent et insérez ce nouveau nœud dans la liste.
• Répétez les étapes ci-dessus jusqu'à ce qu'il ne reste qu'un seul nœud dans la liste, le nœud racine.

class HuffmanTree {
    public static Node buildHuffmanTree(HashMap<Character, Integer> frequencies) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.frequency));
        
        // 将每个字符作为一个单独的节点插入到优先队列中
        for (Map.Entry<Character, Integer> entry : frequencies.entrySet()) {
            pq.offer(new Node(entry.getKey(), entry.getValue()));
        }
        
        // 构建哈夫曼树
        while (pq.size() > 1) {
            Node leftChild = pq.poll();
            Node rightChild = pq.poll();
            Node parent = new Node('', leftChild.frequency + rightChild.frequency);
            parent.left = leftChild;
            parent.right = rightChild;
            pq.offer(parent);
        }
        
        return pq.peek();
    }
}

2. Génération du codage de Huffman

Ensuite, nous devons générer le codage de caractères basé sur l'arbre de Huffman. La règle de codage est qu'à partir du nœud racine, si vous allez dans le sous-arbre de gauche, le code est 0, si vous allez dans le sous-arbre de droite, le code est 1. Pour chaque caractère, nous pouvons générer l'encodage en parcourant récursivement l'arbre de Huffman.

class HuffmanEncoding {
    public static String getHuffmanCode(Node root, char target) {
        StringBuilder code = new StringBuilder();
        generateHuffmanCode(root, target, code);
        return code.toString();
    }

    private static void generateHuffmanCode(Node node, char target, StringBuilder code) {
        if (node == null) {
            return;
        }
        
        if (node.data == target) {
            return;
        }
        
        // 往左子树走
        code.append('0');
        generateHuffmanCode(node.left, target, code);
        
        if (code.charAt(code.length() - 1) != '1') {
            code.deleteCharAt(code.length() - 1);
            // 往右子树走
            code.append('1');
            generateHuffmanCode(node.right, target, code);
        }
        
        if (code.charAt(code.length() - 1) != '1') {
            code.deleteCharAt(code.length() - 1);
        }
    }
}

3. Compression et décompression du codage Huffman

Avec le codage Huffman, nous pouvons compresser et décompresser des données.

3.1 Données compressées

Convertissez les données à compresser en un tableau de caractères, parcourez chaque caractère et utilisez le codage de Huffman pour générer une chaîne codée compressée.

class HuffmanCompression {
    public static String compressData(String data, HashMap<Character, String> huffmanCodes) {
        StringBuilder compressedData = new StringBuilder();
        char[] characters = data.toCharArray();

        for (char c : characters) {
            compressedData.append(huffmanCodes.get(c));
        }

        return compressedData.toString();
    }
}

3.2 Données décompressées

Pour la chaîne codée compressée, nous devons décoder selon l'arbre de Huffman, c'est-à-dire parcourir la chaîne codée à partir du nœud racine. Si 0 est rencontré, accédez au sous-arbre de gauche. en rencontrant 1, allez dans le sous-arbre de droite jusqu'à ce que vous trouviez le nœud feuille, c'est-à-dire que vous trouviez le caractère d'origine.

class HuffmanDecompression {
    public static String decompressData(String compressedData, Node root) {
        StringBuilder decompressedData = new StringBuilder();
        Node currentNode = root;
        
        for (char bit : compressedData.toCharArray()) {
            if (bit == '0') {
                currentNode = currentNode.left;
            } else if (bit == '1') {
                currentNode = currentNode.right;
            }
            
            if (currentNode.left == null && currentNode.right == null) {
                decompressedData.append(currentNode.data);
                currentNode = root;
            }
        }
        
        return decompressedData.toString();
    }
}

En utilisant le code ci-dessus, nous pouvons implémenter l'algorithme de codage de Huffman. L'utilisation du codage Huffman peut compresser les données dans une certaine mesure et réduire l'espace de stockage et le temps de transmission.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!