Task_30 - master - Skob.m.a/WorkSpace

Task_30
107 строк4 KB
Skob.m.a
create Task_30
22 дек 2024, 16:06
22 дек 2024, 16:06c3a7b72
import java.util.PriorityQueue;
import java.util.HashMap;
import java.util.Map;

class HuffmanNode implements Comparable<HuffmanNode> {
    char character;
    int frequency;
    HuffmanNode left;
    HuffmanNode right;

    public HuffmanNode(char character, int frequency) {
        this.character = character;
        this.frequency = frequency;
    }

    @Override
    public int compareTo(HuffmanNode other) {
        return this.frequency - other.frequency;
    }
}

public class HuffmanCoding {
    private Map<Character, String> huffmanCode = new HashMap<>();

    private HuffmanNode buildHuffmanTree(char[] characters, int[] frequencies) {
        PriorityQueue<HuffmanNode> priorityQueue = new PriorityQueue<>();

        for (int i = 0; i < characters.length; i++) {
            priorityQueue.add(new HuffmanNode(characters[i], frequencies[i]));
        }

        while (priorityQueue.size() > 1) {
            HuffmanNode left = priorityQueue.poll();
            HuffmanNode right = priorityQueue.poll();
            HuffmanNode combined = new HuffmanNode('\0', left.frequency + right.frequency);
            combined.left = left;
            combined.right = right;
            priorityQueue.add(combined);
        }

        return priorityQueue.poll(); // Корень дерева
    }

    private void generateHuffmanCodes(HuffmanNode root, String code) {
        if (root == null) return;

        if (root.left == null && root.right == null) {
            huffmanCode.put(root.character, code);
        }

        generateHuffmanCodes(root.left, code + "0");
        generateHuffmanCodes(root.right, code + "1");
    }

    public String encode(String text) {
        Map<Character, Integer> frequencyMap = new HashMap<>();
        for (char c : text.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }

        char[] characters = new char[frequencyMap.size()];
        int[] frequencies = new int[frequencyMap.size()];
        int index = 0;
        for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
            characters[index] = entry.getKey();
            frequencies[index] = entry.getValue();
            index++;
        }

        HuffmanNode root = buildHuffmanTree(characters, frequencies);
        generateHuffmanCodes(root, "");

        StringBuilder encodedString = new StringBuilder();
        for (char c : text.toCharArray()) {
            encodedString.append(huffmanCode.get(c));
        }

        return encodedString.toString();
    }

    public String decode(String encodedText) {
        StringBuilder decodedString = new StringBuilder();
        HuffmanNode currentNode = buildHuffmanTree(huffmanCode.keySet().toArray(new char[0]), huffmanCode.values().stream().mapToInt(Integer::parseInt).toArray());

        for (char bit : encodedText.toCharArray()) {
            currentNode = (bit == '0') ? currentNode.left : currentNode.right;

            if (currentNode.left == null && currentNode.right == null) {
                decodedString.append(currentNode.character);
                currentNode = buildHuffmanTree(huffmanCode.keySet().toArray(new char[0]), huffmanCode.values().stream().mapToInt(Integer::parseInt).toArray());
            }
        }

        return decodedString.toString();
    }

    public static void main(String[] args) {
        HuffmanCoding huffmanCoding = new HuffmanCoding();
        
        String text = "hello huffman";
        String encoded = huffmanCoding.encode(text);
        System.out.println("Encoded: " + encoded);

        String decoded = huffmanCoding.decode(encoded);
        System.out.println("Decoded: " + decoded);
    }
}