허프만 인코딩 소개
Huffman 인코딩은 문자에 해당하는 이진 데이터 길이를 압축하기 위해 인코딩 및 디코딩으로 나뉘어 진 문자에 해당하는 문자 및 이진의 코딩 쌍 문제를 처리합니다. 우리는 문자가 저장되고 전송되면 바이너리 (컴퓨터는 0/1 만 알고 있음)이므로 문자와 이진 사이에 매핑 관계가 있음을 알고 있습니다. 문자는 문자 세트 (숯)에 속합니다. 인코딩을 통해 문자를 바이너리에 저장하고 전송해야합니다. 표시되면 캐릭터로 다시 디코딩해야합니다. 문자 세트 및 인코딩 방법은 일대일 관계입니다 (유니 코드는 UTF-8, UTF-16 등으로 인코딩 할 수 있습니다). 캐릭터 세트, 인코딩 및 디코딩을 이해 한 후 하늘 전체로 날아간 코드 문제를 쉽게 해결할 수 있습니다. ASCII 인코딩에서 영어 문자의 소문자 A를 예로 들어 보면 10 진수는 97이고 바이너리는 01100001입니다. ASCII의 각 문자는 8 비트 (1 베이트)로 인코딩됩니다. 전송할 문자가 1000 인 경우 8000 비트를 전송해야합니다. 문제는 영어로 문자 E를 사용하는 빈도는 12.702%이고 z는 0.074%라는 것입니다. 전자는 후자보다 100 배 이상이지만 동일한 숫자의 이진을 사용합니다. 더 잘 수행 할 수 있으며,이 방법은 가변 길이 인코딩입니다. 지침 원리는 더 높은 주파수를 단기간으로 인코딩하는 것입니다. 허프만 인코딩 알고리즘은 그러한 문제를 처리합니다.
Huffman 인코딩 Java 구현
Huffman 인코딩 알고리즘이 주로 사용하는 데이터 구조는 전체 이진 트리 및 우선 순위 대기열입니다. 후자는 java.util.priorityqueue를 사용하며 전자는 그 자체를 구현합니다 (모두 내부 클래스입니다). 코드는 다음과 같습니다.
정적 클래스 트리 {개인 노드 루트; public node getRoot () {return root; } public void setRoot (노드 루트) {this.root = root; }} 정적 클래스 노드는 <node> {private String chars = ""; 개인 int 주파수 = 0; 개인 노드 부모; 개인 노드 왼쪽 노드; 개인 노드 오른쪽 노드; @override public int compareto (node n) {반환 주파수 -N.Frequency; } 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 () {반환 주파수; } public void setfrequence (int 주파수) {this.frequency = 주파수; } public String getChars () {return chars; } public void setchars (String chars) {this.chars = chars; } public node getParent () {return parent; } public void setparent (노드 부모) {this.parent = parent; } public node getLeftNode () {return leftNode; } public void setleftNode (노드 왼쪽 노드) {this.leftNode = LeftNode; } public node getRightNode () {return rightNode; } public void setrightnode (노드 오른쪽 노드) {this.rightNode = 오른쪽 노드; }} 통계
인코딩 테이블은 주파수에 따라 배열되어야하므로 물론 주파수의 통계 정보를 얻어야합니다. 그러한 문제를 처리하는 방법을 구현했습니다. 이미 통계가 있으면 MAP <문자, Integer>로 변환하십시오. 받는 정보가 백분율 인 경우 100 또는 1000 또는 10000을 곱합니다. 항상 정수로 변환 할 수 있습니다. 예를 들어, 12.702%가 1000을 곱한 것은 12702이며 허프만 인코딩은 크기 문제에 대해서만 관심이 있습니다. 통계 방법은 다음과 같이 구현됩니다.
public static map <문자, 정수> 통계 (char [] chararray) {map <문자, 정수> map = new Hashmap <문자, integer> (); for (charc c : chararray) {문자 문자 = new 캐릭터 (c); if (map.containskey (문자)) {map.put (문자, map.get (문자) + 1); } else {map.put (문자, 1); }} 리턴 맵; } 나무를 짓기
트리를 만드는 것은 허프만 인코딩 알고리즘의 핵심 단계입니다. 아이디어는 완전히 바이너리 트리의 잎 노드에 모든 문자를 걸어 놓는 것이며, 비 페이지 하위 노드의 왼쪽 노드 주파수는 오른쪽 노드보다 더 많이 나타나지 않습니다. 알고리즘은 통계를 노드로 변환하여 우선 순위 대기열에 저장합니다. 최소 주파수가있는 두 개의 노드가 큐에서 팝업 될 때마다 새 상위 노드 (비 잎 노드)가 구성됩니다. 캐릭터 내용이 방금 튀어 나오는 두 노드의 합계와 주파수도 합계입니다. 첫 번째 팝업은 왼쪽 하위 노드로 사용되며 다음 팝업은 오른쪽 하위 노드로 사용되며 새로 구성된 부모 노드는 큐에 배치됩니다. 위의 동작을 반복하여 n-1 회 반복하십시오. n은 다른 문자의 수입니다 (큐의 숫자는 매번 1 씩 줄어 듭니다). 위의 단계를 종료하면 대기열에 노드가 남아 있고 트리의 루트 노드가 나타납니다. 코드는 다음과 같습니다.
개인 정적 트리 빌드 트리 (Map <문자, 정수> 통계, 목록 <노드> 잎) {문자 [] 키 = 통계 .keyset (). ToArray (새 문자 [0]); PriorityQueue <노드> PriorityQueue = 새로운 PriorityQueue <Node> (); for (문자 문자 : 키) {node node = new Node (); node.chars = arribute.toString (); node.frequency = statistics.get (문자); PriorityQueue.add (노드); 잎 (노드); } int size = priorityqueue.size (); for (int i = 1; i <= size -1; i ++) {node node1 = priorityqueue.poll (); 노드 노드 2 = priorityQueue.poll (); 노드 sumnode = new Node (); sumnode.chars = node1.chars + node2.chars; sumnode.frequency = node1.fraquence + node2.fraquence; sumnode.leftnode = node1; sumnode.rightnode = node2; node1.parent = sumnode; node2.parent = sumnode; priorityqueue.add (sumnode); } 트리 트리 = 새로운 트리 (); tree.root = PriorityQueue.poll (); 귀환 트리; } 코딩
캐릭터의 해당 인코딩은 캐릭터가있는 리프 노드에서 검색하는 것입니다. 문자 노드가 부모 노드의 왼쪽 노드 인 경우 인코딩 된 문자 앞에 0을 추가하십시오. 그렇지 않으면 오른쪽 노드 인 경우 루트 노드까지 1을 추가하십시오. 문자와 이진 코드 간의 매핑 관계가 얻어지면 인코딩은 매우 간단합니다. 코드는 다음과 같습니다.
public static string encode (String OriginalStr, Map <문자, 정수> 통계) {if (OriginalSt == NULL || OriginalStr.equals ( "")) {return ""; } char [] charArray = originalstr.tochararray (); List <Node> LeafNodes = New ArrayList <Node> (); BuildTree (통계, LeafNodes); map <문자, 문자열> encodinfo = buildEncodingInfo (LeafNodes); StringBuffer buffer = new StringBuffer (); for (char c : chararray) {문자 문자 = new 캐릭터 (c); buffer.append (encodinfo.get (문자)); } return buffer.toString (); } private static map <문자, 문자열> buildEncodingInfo (list <node> leafnodes) {map <문자, 문자열> codewords = new Hashmap <문자, 문자열> (); for (Node LeafNodes : LeafNodes) {문자 문자 = new ar 문자열 코드 워드 = ""; 노드 currentNode = LeafNode; do {if (currentNode.isleftChild ()) {CodeWord = "0" + CodeWord; } else {CodeWord = "1" + CodeWord; } currentNode = currentNode.parent; } while (currentNode.parent! = null); codewords.put (문자, 코드 워드); } 반환 코드 워드; } 디코딩
Huffman 인코딩 알고리즘은 모든 이진 코드가 다른 코드의 접두사가되지 않도록 할 수 있으므로 디코딩은 매우 간단합니다. 이진의 각 비트를 순서대로 꺼내 트리 뿌리에서 1에서 오른쪽으로, 0에서 왼쪽으로, 잎 노드 (HIT)에 도달하고 루트 노드로 돌아가서 위의 동작을 계속 반복하십시오. 코드는 다음과 같습니다.
public static string decode (String binarystr, map <문자, 정수> 통계) {if (binarystr == null || binarystr.equals ( "")) {return ""; } char [] binarychararray = binarystr.tochararray (); LinkedList <atirection> binaryList = New LinkedList <문자> (); int size = binarychararray.length; for (int i = 0; i <size; i ++) {binarylist.addlast (new 특성 (binarychararray [i]); } list <Node> LeafNodes = new ArrayList <Node> (); 트리 트리 = buildTree (통계, 잎도); StringBuffer buffer = new StringBuffer (); while (binaryList.size ()> 0) {노드 노드 = tree.Root; do {문자 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 Encoding의 정확성에 대한 다음 테스트 (중국어를 포함하여 먼저 인코딩 된 다음 해독) 및 Huffman 인코딩의 공통 문자 인코딩 이진 문자열과의 비교에 대한 다음 테스트. 코드는 다음과 같습니다.
public static void main (String [] args) {String oristr = "Huffman 코드는 데이터를 매우 효과적으로 압축합니다. 20% ~ 90%의 절약은 일반적으로" + "는 압축되는 데이터의 특성에 따라" + "입니다. 중국의 상승"; Map <문자, 정수> 통계 = 통계 (oristr.tochararray ()); String encodedBinarist = encode (oristr, 통계); 문자열 decodedstr = decode (encodedBinarist, 통계); System.out.println ( "원래 문자열 :" + oristr); System.out.println ( "Huffman Encoed Binary String :" + encodedBinarist); System.out.println ( "Binariy String에서 디코딩 된 문자열 :" + decodedstr); System.out.println ( "UTF-8의 이진 문자열 :" + getStringofbyte (orist, charset.forname ( "UTF-8"))); System.out.println ( "UTF-16의 이진 문자열 :" + getStringofbyte (oristr, charset.forname ( "UTF-16"))); System.out.println ( "US-ASCII의 이진 문자열 :" + getStringtringofbyte (orist, charset.forname ( "us-ASCII"))); System.out.println ( "GB2312의 이진 문자열 :" + getStringofByte (orist, charset.forname ( "gb2312"))); } public static string getStringtringofByte (String Str, charset charset) {if (str == null || str.equals ( "")) {return ""; } byte [] bytearray = str.getBytes (chars); 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 (바이트 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 (); }위는이 기사의 모든 내용입니다. 모든 사람의 학습에 도움이되기를 바랍니다. 모든 사람이 wulin.com을 더 지원하기를 바랍니다.