Huffman 압축 알고리즘은 데이터를 압축하는 방법 중 하나로, 데이터의 빈도 수에 기반하여 각 문자에 대한 가변 길이 코드를 생성합니다. 가장 빈번하게 나타나는 문자에는 짧은 코드가 할당되고, 드물게 나타나는 문자에는 긴 코드가 할당됩니다. 이 방법은 데이터를 효율적으로 압축하고, 원래 데이터로 재구성할 수 있는 능력을 제공합니다.
1. 필요한 자료구조 생성하기
Huffman 알고리즘을 구현하기 위해 먼저 필요한 자료구조를 생성해야 합니다. 다음은 Huffman Tree의 노드를 표현하는 클래스입니다.
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 o) {
return this.frequency - o.frequency;
}
}
2. 문자 빈도 수 계산하기
Huffman 알고리즘을 사용하기 위해서는 입력 데이터의 각 문자에 대한 빈도 수를 계산해야 합니다. 다음은 입력 문자열에서 각 문자의 빈도 수를 계산하는 메소드입니다.
public static Map<Character, Integer> calculateFrequencies(String input) {
Map<Character, Integer> frequencies = new HashMap<>();
for (char c : input.toCharArray()) {
frequencies.put(c, frequencies.getOrDefault(c, 0) + 1);
}
return frequencies;
}
3. Huffman Tree 생성하기
빈도 수가 계산된 후, Huffman Tree를 생성해야 합니다. 역시 메소드를 사용하여 간단하게 구현할 수 있습니다.
public static HuffmanNode buildHuffmanTree(Map<Character, Integer> frequencies) {
PriorityQueue<HuffmanNode> queue = new PriorityQueue<>();
for (Map.Entry<Character, Integer> entry : frequencies.entrySet()) {
HuffmanNode node = new HuffmanNode(entry.getKey(), entry.getValue());
queue.offer(node);
}
while (queue.size() > 1) {
HuffmanNode leftChild = queue.poll();
HuffmanNode rightChild = queue.poll();
HuffmanNode parent = new HuffmanNode('\0', leftChild.frequency + rightChild.frequency);
parent.left = leftChild;
parent.right = rightChild;
queue.offer(parent);
}
return queue.poll();
}
4. Huffman 코드 생성하기
Huffman Tree를 생성한 후, 각 문자에 대한 Huffman 코드를 생성해야 합니다. 다음은 Huffman Tree를 사용하여 문자에 대한 코드를 생성하는 메소드입니다.
public static Map<Character, String> generateHuffmanCodes(HuffmanNode root) {
Map<Character, String> huffmanCodes = new HashMap<>();
generateHuffmanCodesHelper(root, "", huffmanCodes);
return huffmanCodes;
}
private static void generateHuffmanCodesHelper(HuffmanNode node, String code, Map<Character, String> huffmanCodes) {
if (node == null) {
return;
}
if (node.left == null && node.right == null) { // leaf node
huffmanCodes.put(node.character, code);
return;
}
generateHuffmanCodesHelper(node.left, code + "0", huffmanCodes);
generateHuffmanCodesHelper(node.right, code + "1", huffmanCodes);
}
5. 데이터 압축하기
Huffman 코드를 사용하여 입력 데이터를 압축할 수 있습니다. 다음은 입력 데이터를 Huffman 코드로 압축하는 메소드입니다.
public static String compress(String input, Map<Character, String> huffmanCodes) {
StringBuilder compressedData = new StringBuilder();
for (char c : input.toCharArray()) {
compressedData.append(huffmanCodes.get(c));
}
return compressedData.toString();
}
6. 데이터 복원하기
압축된 데이터를 Huffman 코드를 사용하여 원래의 데이터로 복원할 수 있습니다. 다음은 압축된 데이터를 Huffman 코드로 복원하는 메소드입니다.
public static String decompress(String compressedData, HuffmanNode root) {
StringBuilder decompressedData = new StringBuilder();
HuffmanNode current = root;
for (char bit : compressedData.toCharArray()) {
if (bit == '0') {
current = current.left;
} else if (bit == '1') {
current = current.right;
}
if (current.left == null && current.right == null) { // leaf node
decompressedData.append(current.character);
current = root;
}
}
return decompressedData.toString();
}
7. 압축 예제
이제 위에서 구현한 메소드들을 사용하여 데이터를 압축 및 복원하는 예제를 보겠습니다.
public static void main(String[] args) {
String input = "hello world";
Map<Character, Integer> frequencies = calculateFrequencies(input);
HuffmanNode root = buildHuffmanTree(frequencies);
Map<Character, String> huffmanCodes = generateHuffmanCodes(root);
String compressedData = compress(input, huffmanCodes);
System.out.println("Compressed Data: " + compressedData);
String decompressedData = decompress(compressedData, root);
System.out.println("Decompressed Data: " + decompressedData);
}
위 예제를 실행하면 입력 데이터가 압축되고 복원된 결과를 확인할 수 있습니다.
Huffman 압축 알고리즘은 데이터를 효율적으로 압축하고, 빠르게 복원하는 간단하면서도 강력한 압축 알고리즘입니다. 암호화된 데이터를 전송하거나 저장해야 할 때 Huffman 알고리즘을 사용하여 데이터의 크기를 줄일 수 있습니다.