Java를 사용하여 허프만 코딩 알고리즘을 구현하는 방법

Java에서 허프만 코딩 알고리즘을 구현하는 방법

허프만 코딩 알고리즘은 데이터 압축에 효과적인 방법으로, 문자 시간이 더 자주 발생하도록 짧은 인코딩을 사용하여 저장 공간과 전송을 줄입니다. 이 기사에서는 Java를 사용하여 허프만 코딩 알고리즘을 구현하는 방법을 소개하고 구체적인 코드 예제를 제공합니다.

1. 허프만 트리 구축

먼저, 허프만 트리를 구축해야 합니다. 허프만 트리는 각 리프 노드가 문자에 해당하고 트리의 리프가 아닌 각 노드에 두 개의 자식 노드가 있는 특수 이진 트리입니다. 허프만 트리를 구축하는 단계는 다음과 같습니다.

1.1 노드 클래스 생성

먼저, 허프만 트리의 노드를 나타내는 노드 클래스를 생성해야 합니다. 노드 클래스에는 문자, 빈도, 왼쪽 및 오른쪽 하위 노드라는 세 가지 속성이 포함되어 있습니다.

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 허프만 트리 구성

허프만 트리를 구성하는 단계는 다음과 같습니다.

• 노드 목록을 만들고 각 문자를 별도의 노드로 목록에 삽입합니다.
• 노드 목록을 빈도별로 작은 것부터 큰 것까지 정렬하세요.
• 노드 목록에서 빈도가 가장 작은 두 개의 노드를 꺼내고 새 노드를 상위 노드로 만든 다음 이 새 노드를 목록에 삽입합니다.
• 목록에 하나의 노드, 즉 루트 노드만 남을 때까지 위 단계를 반복합니다.

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 압축 해제된 데이터

압축된 인코딩 문자열의 경우 허프만 트리에 따라 디코딩해야 합니다. 즉, 루트 노드부터 시작하여 인코딩된 문자열을 순회해야 합니다. If When. 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!