Huffman 인코딩 알고리즘의 Java 구현 이해
Huffman 인코딩 처리는 문자와 문자에 대응하는 2진 인코딩 배합 문제로 인코딩과 디코딩으로 나뉘는데 그 목적은 문자에 대응하는 2진 데이터의 길이를 압축하는 것이다.우리는 문자가 저장되고 전송될 때 모두 2진법이라는 것을 알고 있다. (컴퓨터는 0/1만 인식한다.) 그러면 문자와 2진법 간의 맵핑 관계가 있다.문자는 문자 집합(Charset)에 속하고, 문자는 인코딩(encode)을 통해 2진법으로 저장하고 전송해야 하며, 표시할 때 디코딩(decode)이 문자를 되돌려야 하며, 문자 집합과 인코딩 방법은 일대다 관계(Unicode는 UTF-8, UTF-16 등으로 인코딩할 수 있다).문자 집합, 인코딩, 디코딩을 이해하면 하늘을 찌를 듯한 디코딩 문제도 해결된다.영문 자모 소문자 a를 예로 들면 ASCII 인코딩에서 10진법은 97, 2진법은 01100001이다.ASCII의 모든 문자는 8개의 Bit(1Byte)로 인코딩되며, 1000개의 문자가 전송된다면 8000개의 Bit를 전송해야 한다.문제는 영문에서 자모 e의 사용 빈도가 12.702%이고 z는 0.074%이며 전자는 후자의 100여 배이지만 같은 비트의 2진법을 사용한다는 것이다.더 잘 할 수 있는 방법은 가변 길이 인코딩이고 지도 원칙은 주파수가 높은 것은 비교적 짧은 비트 인코딩, 주파수가 낮은 것은 비교적 긴 비트 인코딩이다.Huffman 인코딩 알고리즘은 이런 문제를 처리하는 것이다.
Huffman 인코딩 Java 구현
Huffman 인코딩 알고리즘이 주로 사용하는 데이터 구조는 완전 두 갈래 트리(full binary tree)와 우선순위 대기열입니다.후자는 자바를 쓴다.util.PriorityQueue, 전자는 스스로 실현한다(모두 내부 클래스), 코드는 다음과 같다.
static class Tree {
private Node root;
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
}
static class Node implements Comparable<Node> {
private String chars = "";
private int frequence = 0;
private Node parent;
private Node leftNode;
private Node rightNode;
@Override
public int compareTo(Node n) {
return frequence - n.frequence;
}
public boolean isLeaf() {
return chars.length() == 1;
}
public boolean isRoot() {
return parent == null;
}
public boolean isLeftChild() {
return parent != null && this == parent.leftNode;
}
public int getFrequence() {
return frequence;
}
public void setFrequence(int frequence) {
this.frequence = frequence;
}
public String getChars() {
return chars;
}
public void setChars(String chars) {
this.chars = chars;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
}
기왕 주파수에 따라 인코딩표를 안배해야 한다면 우선 주파수의 통계 정보를 얻어야 한다.나는 이런 문제를 처리하는 방법을 실현했다.통계가 이미 있으면 맵
public static Map<Character, Integer> statistics(char[] charArray) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (char c : charArray) {
Character character = new Character(c);
if (map.containsKey(character)) {
map.put(character, map.get(character) + 1);
} else {
map.put(character, 1);
}
}
return map;
}
트리 구축은 Huffman 인코딩 알고리즘의 핵심 단계입니다.사상은 모든 문자를 완전한 두 갈래 나무의 잎사귀 노드에 걸어 놓는 것이다. 어떤 페이지가 아닌 노드의 왼쪽 노드는 오른쪽 노드보다 나타나지 않는다.알고리즘은 통계 정보를 Node로 바꾸어 하나의 우선순위 대기열에 저장하고 매번 대기열에서 두 개의 최소 주파수의 노드를 꺼내서 새로운 아버지 Node(비잎 노드)를 구축한다. 문자 내용이 방금 튀어나온 두 노드의 문자 내용의 합이고 주파수도 그것들의 합이다. 처음에 튀어나온 것은 왼쪽 노드이고 뒤에 하나는 오른쪽 노드로 하고 방금 구축한 아버지 노드를 대기열에 넣는다.이상의 동작을 N-1번 반복하면 N은 서로 다른 문자의 개수(매 대기열의 개수 감소1)입니다.상기 절차를 끝내고 대기열에 노드가 하나 남았으며 나무의 루트로 팝업됩니다.코드는 다음과 같습니다.
private static Tree buildTree(Map<Character, Integer> statistics,
List<Node> leafs) {
Character[] keys = statistics.keySet().toArray(new Character[0]);
PriorityQueue<Node> priorityQueue = new PriorityQueue<Node>();
for (Character character : keys) {
Node node = new Node();
node.chars = character.toString();
node.frequence = statistics.get(character);
priorityQueue.add(node);
leafs.add(node);
}
int size = priorityQueue.size();
for (int i = 1; i <= size - 1; i++) {
Node node1 = priorityQueue.poll();
Node node2 = priorityQueue.poll();
Node sumNode = new Node();
sumNode.chars = node1.chars + node2.chars;
sumNode.frequence = node1.frequence + node2.frequence;
sumNode.leftNode = node1;
sumNode.rightNode = node2;
node1.parent = sumNode;
node2.parent = sumNode;
priorityQueue.add(sumNode);
}
Tree tree = new Tree();
tree.root = priorityQueue.poll();
return tree;
}
문자에 대응하는 인코딩은 이 문자가 있는 잎사귀 노드에서 위로 검색하고, 이 문자 노드가 부모 노드의 왼쪽 노드인 경우, 인코딩하기 전에 0을 추가하고, 반대로 오른쪽 노드인 경우 루트 노드까지 1을 추가합니다.문자와 바이너리 코드 사이의mapping 관계를 가져오면 인코딩은 매우 간단합니다.코드는 다음과 같습니다.
public static String encode(String originalStr,
Map<Character, Integer> statistics) {
if (originalStr == null || originalStr.equals("")) {
return "";
}
char[] charArray = originalStr.toCharArray();
List<Node> leafNodes = new ArrayList<Node>();
buildTree(statistics, leafNodes);
Map<Character, String> encodInfo = buildEncodingInfo(leafNodes);
StringBuffer buffer = new StringBuffer();
for (char c : charArray) {
Character character = new Character(c);
buffer.append(encodInfo.get(character));
}
return buffer.toString();
}
private static Map<Character, String> buildEncodingInfo(List<Node> leafNodes) {
Map<Character, String> codewords = new HashMap<Character, String>();
for (Node leafNode : leafNodes) {
Character character = new Character(leafNode.getChars().charAt(0));
String codeword = "";
Node currentNode = leafNode;
do {
if (currentNode.isLeftChild()) {
codeword = "0" + codeword;
} else {
codeword = "1" + codeword;
}
currentNode = currentNode.parent;
} while (currentNode.parent != null);
codewords.put(character, codeword);
}
return codewords;
}
Huffman 인코딩 알고리즘은 어떤 2진 코드도 다른 코드의 접두사가 되지 않도록 보장할 수 있기 때문에 디코딩은 매우 간단하다. 2진 코드의 모든 부분을 순서대로 추출하고 나무 뿌리에서 아래로 검색한다. 1은 오른쪽, 0은 왼쪽, 잎 노드(명중)에 도착하면 뿌리 노드로 되돌아와 상기 동작을 반복한다.코드는 다음과 같습니다.
public static String decode(String binaryStr,
Map<Character, Integer> statistics) {
if (binaryStr == null || binaryStr.equals("")) {
return "";
}
char[] binaryCharArray = binaryStr.toCharArray();
LinkedList<Character> binaryList = new LinkedList<Character>();
int size = binaryCharArray.length;
for (int i = 0; i < size; i++) {
binaryList.addLast(new Character(binaryCharArray[i]));
}
List<Node> leafNodes = new ArrayList<Node>();
Tree tree = buildTree(statistics, leafNodes);
StringBuffer buffer = new StringBuffer();
while (binaryList.size() > 0) {
Node node = tree.root;
do {
Character c = binaryList.removeFirst();
if (c.charValue() == '0') {
node = node.leftNode;
} else {
node = node.rightNode;
}
} while (!node.isLeaf());
buffer.append(node.chars);
}
return buffer.toString();
}
다음은 Huffman 인코딩의 정확성(선인코딩, 후인코딩, 중국어 포함)과 Huffman 인코딩과 흔히 볼 수 있는 문자 인코딩의 2진 문자열 비교를 테스트합니다.코드는 다음과 같습니다.
public static void main(String[] args) {
String oriStr = "Huffman codes compress data very effectively: savings of 20% to 90% are typical, "
+ "depending on the characteristics of the data being compressed. ";
Map<Character, Integer> statistics = statistics(oriStr.toCharArray());
String encodedBinariStr = encode(oriStr, statistics);
String decodedStr = decode(encodedBinariStr, statistics);
System.out.println("Original sstring: " + oriStr);
System.out.println("Huffman encoed binary string: " + encodedBinariStr);
System.out.println("decoded string from binariy string: " + decodedStr);
System.out.println("binary string of UTF-8: "
+ getStringOfByte(oriStr, Charset.forName("UTF-8")));
System.out.println("binary string of UTF-16: "
+ getStringOfByte(oriStr, Charset.forName("UTF-16")));
System.out.println("binary string of US-ASCII: "
+ getStringOfByte(oriStr, Charset.forName("US-ASCII")));
System.out.println("binary string of GB2312: "
+ getStringOfByte(oriStr, Charset.forName("GB2312")));
}
public static String getStringOfByte(String str, Charset charset) {
if (str == null || str.equals("")) {
return "";
}
byte[] byteArray = str.getBytes(charset);
int size = byteArray.length;
StringBuffer buffer = new StringBuffer();
for (int i = 0; i < size; i++) {
byte temp = byteArray[i];
buffer.append(getStringOfByte(temp));
}
return buffer.toString();
}
public static String getStringOfByte(byte b) {
StringBuffer buffer = new StringBuffer();
for (int i = 7; i >= 0; i--) {
byte temp = (byte) ((b >> i) & 0x1);
buffer.append(String.valueOf(temp));
}
return buffer.toString();
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
당신은 자신의 파일 압축이 어떻게 작동하는지 물어본 적이 있습니까?탐욕 알고리즘 뒤의 수학왜냐하면 우리는 영상이나 사진에서 발생하는 일을 볼 수 있고 이해할 수 있기 때문이다. 80년대 초반의 마이크로 BBC(8위) 등 컴퓨터의 최대 저장 용량은 800kb에 불과했기 때문에 텍스트 무손상 기술이 생겨났다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
