public class HuffmanNode {
    char data;
    int freq;
    HuffmanNode left;
    HuffmanNode right;

    public HuffmanNode(char data, int frequency) {
        this.data = data;
        this.freq = frequency;
        this.left = null;
        this.right = null;
    }

    public HuffmanNode(int freq, HuffmanNode left, HuffmanNode right) {
        this.data = '\0';
        this.freq = freq;
        this.left = left;
        this.right = right;
    }

    public boolean isLeaf() {
        return this.left == null && this.right == null;
    }
}

public class HuffmanCoding {
    private Map<Character, String> huffmanCodes;

    public List<Map.Entry<Character, String>> compress(String text) {
        Map<Character, Integer> frequencyMap = calculateFrequency(text);
        HuffmanNode root = buildHuffmanTree(frequencyMap);
        huffmanCodes = new HashMap<>();
        generateHuffmanCodes(root, "");
        return encodeText();
    }

    private Map<Character, Integer> calculateFrequency(String text) {
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char ch : text.toCharArray()) {
            freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
        }
        return freqMap;
    }

    private HuffmanNode buildHuffmanTree(Map<Character, Integer> frequencyMap) {
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.freq));

        for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
            pq.add(new HuffmanNode(entry.getKey(), entry.getValue()));
        }

        while (pq.size() > 1) {
            HuffmanNode left = pq.poll();
            HuffmanNode right = pq.poll();
            HuffmanNode merged = new HuffmanNode(left.freq + right.freq, left, right);
            pq.add(merged);
        }

        return pq.poll();
    }

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

        if (node.isLeaf()) {
            huffmanCodes.put(node.data, code);
            return;
        }

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

    private List<Map.Entry<Character, String>> encodeText() {
        List<Map.Entry<Character, String>> result = new ArrayList<>(huffmanCodes.entrySet());
        result.sort(Comparator.comparing(Map.Entry::getKey)); // 알파벳 순 정렬 (옵션)
        return result;
    }

}

public class Main {
    public static void main(String[] args) {
        HuffmanCoding huffman = new HuffmanCoding();
        String str = "Lorem ipsum dolor sit amet consectetur adipiscing elit. Consectetur adipiscing elit quisque faucibus ex sapien vitae. Ex sapien vitae pellentesque sem placerat in id. Placerat in id cursus mi pretium tellus duis. Pretium tellus duis convallis tempus leo eu aenean.";
        List<Entry<Character, String>> result = huffman.compress(str);
        for (Map.Entry<Character, String> entry : result) {
            System.out.printf("[ '%s', '%s' ]\n", entry.getKey(), entry.getValue());
        }
    }
}

========================================================================
[ ' ', '110' ]
[ '.', '100011' ]
[ 'C', '00111110' ]
[ 'E', '00111111' ]
[ 'L', '10001001' ]
[ 'P', '0010011' ]
[ 'a', '0101' ]
[ 'b', '0010010' ]
[ 'c', '11110' ]
[ 'd', '00101' ]
[ 'e', '011' ]
[ 'f', '10001000' ]
[ 'g', '0011110' ]
[ 'i', '000' ]
[ 'l', '0100' ]
[ 'm', '10000' ]
[ 'n', '11111' ]
[ 'o', '00110' ]
[ 'p', '10110' ]
[ 'q', '001000' ]
[ 'r', '10111' ]
[ 's', '1110' ]
[ 't', '1010' ]
[ 'u', '1001' ]
[ 'v', '001110' ]
[ 'x', '1000101' ]