Javaを使用してハフマン符号化アルゴリズムを実装する方法

Java を使用してハフマン コーディング アルゴリズムを実装する方法

ハフマン コーディング アルゴリズムは、より高い頻度で文字を圧縮することにより、データ圧縮に効果的な方法です。短いエンコーディングを使用して、保存スペースと送信時間を削減します。この記事では、Java を使用してハフマン符号化アルゴリズムを実装する方法を紹介し、具体的なコード例を示します。

1. ハフマン ツリーの構築

まず、ハフマン ツリーを構築する必要があります。ハフマン ツリーは、各リーフ ノードが文字に対応し、ツリーの各非リーフ ノードが 2 つの子ノードを持つ特殊なバイナリ ツリーです。ハフマン ツリーを構築する手順は次のとおりです。

1.1 ノード クラスの作成

まず、ハフマン ツリーのノードを表すノード クラスを作成する必要があります。ノード クラスには、文字、頻度、左右の子ノードの 3 つの属性が含まれています。

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 ハフマン ツリーの構築

ハフマン ツリーを構築する手順は次のとおりです。

• ノード リストを作成し、各文字を個別の文字として扱います。ノードがリストに挿入されます。
• 頻度に従ってノード リストを小さいものから大きいものまで並べ替えます。
• ノード リストから頻度が最も小さい 2 つのノードを取り出し、その親ノードとして新しいノードを作成し、リストに追加します。
• リストに 1 つのノード (ルート ノード) だけが残るまで、上記の手順を繰り返します。

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. ハフマン エンコーディングの生成

次に、ハフマン ツリーに基づいて文字エンコーディングを生成する必要があります。コーディング規則は、ルート ノードから開始して、左側のサブツリーに移動するとコードは 0、右側のサブツリーに移動するとコードは 1 になります。文字ごとに、ハフマン ツリーを再帰的に走査することでエンコーディングを生成できます。

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. ハフマン符号化の圧縮と解凍

ハフマン符号化を使用すると、データを圧縮および解凍できます。

3.1 圧縮データ

圧縮対象のデータを文字配列に変換し、各文字を走査し、ハフマン コーディングを使用して圧縮エンコード文字列を生成します。

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 データの解凍

圧縮されたエンコードされた文字列の場合、ハフマン ツリーに従ってデコードする必要があります。つまり、ルート ノードから開始してエンコードされた文字列を走査する必要があります。 , 次に、左側のサブツリーに移動し、1 に遭遇したら、リーフ ノードが見つかるまで、つまり元の文字が見つかるまで、右側のサブツリーに移動します。

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

上記のコードを使用すると、ハフマン符号化アルゴリズムを実装できます。ハフマン符号化を使用すると、データをある程度まで圧縮し、保存スペースと送信時間を削減できます。

以上がJavaを使用してハフマン符号化アルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。