머리말
데이터 구조를 배운 친구들은 허프만을 알아야한다고 생각합니다. 이 위대한 신은 유명한 "최적의 이진 나무"를 발명했습니다. 그를 기념하기 위해 우리는 그것을 "허프만 트리"라고 부릅니다. 허프만 트리는 허프만 인코딩에 사용될 수 있으며 압축, 암호화 등과 같이 인코딩에 대한 지식이 매우 훌륭합니다. 오늘날 허프만 트리가 무엇인지 살펴 보겠습니다.
개념
물론 일상 중 하나는 몇 가지 기본 개념을 이해해야한다는 것입니다.
1. 경로 길이 : 트리의 한 노드에서 다른 노드로 두 노드를 형성하는 경로. 경로의 가지 수를 경로 길이라고합니다.
2. 트리 경로 길이 : 트리 루트에서 각 노드까지의 경로 길이의 합. 우리가 완전한 이진 트리라고 부르는 것은 이런 종류의 가장 짧은 경로 길이입니다.
3. 트리의 가중 경로 길이 : 가중 값이 트리의 각 잎 노드에 할당되면 트리의 가중 경로 길이는 루트 노드에서 모든 잎 노드까지의 경로 길이의 제품의 합의 합과 잎 노드의 무게와 같습니다.
그렇다면 트리가 최적의 이진 트리인지 어떻게 결정합니까? 다음 나무를 살펴 보겠습니다.
그들의 전력 길이는 다음과 같습니다.
WPL1 : 7*2+5*2+2*2+4*2 = 36
WPL2 : 7*3+5*3+2*1+4*2 = 46
WPL3 : 7*1+5*2+2*3+4*3 = 35
세 번째 나무는 가장 짧은 무게 경로를 가지고 있음 이 분명합니다 (믿지 말고 시도해 볼 수 있습니다. 더 짧은 것을 찾을 수 있다면 튜링 상을 수상 할 수 있습니다). 이것이 우리가 "최적 바이너리 트리 (Hafman Tree)"라고 부르는 것입니다. 건축 방법은 매우 간단합니다. 무게가 가장 작은 노드를 선택하고 트리 바닥에 놓고 두 개의 작은 연결을 새 노드에 넣습니다. 형성된 새 노드의 가중치는이 두 노드의 가중치의 합과 같아야한다는 점에 유의해야합니다. 그런 다음이 새 노드를 다시 정렬하기 위해 트리를 형성 해야하는 노드에 다시 넣으십시오. 이러한 방식으로 Hafman 트리에 저장된 정보가있는 모든 노드는 리프 노드에 있습니다.
개념을 마친 후에는 약간 "불분명"할 수 있습니다.
명확하게 구축 할 모범을 보여 봅시다.
문자열이 있습니다
첫 번째 단계에서, 우리는 먼저 각 캐릭터가 나타나는 횟수를 계산하고 그것을 캐릭터의 무게라고 부릅니다. A 15, B 5, C 8, D 6, F 3.
두 번째 단계는 가장 작은 무게 인 B5와 F3의 두 문자를 찾아 노드를 구축하는 것입니다.
그런 다음 F3 및 B5, 이제 A15, C8, D6, FB8을 제거하십시오.
3 단계, 하나의 노드 만 남을 때까지 두 번째 단계를 반복하십시오.
이제 DFB14, A15, C8입니다.
마침내,
좋아, 그래서 우리의 허프만 나무가 만들어졌습니다.
구축 단계
위의 논리에 따르면, 요약하려면 몇 가지 단계가 있습니다.
1. 통계 문자열에 나타나는 문자 및 문자 수;
2. 첫 번째 단계의 구조에 따라 노드를 만듭니다.
3. 노드 가중치 오름차순 순서를 정렬하십시오.
4. 무게가 가장 작은 두 노드를 꺼내 새로운 상위 노드를 생성하십시오.
5. 두 노드를 가장 작은 무게로 삭제하고 부모 노드를 목록에 저장하십시오.
6. 왼쪽 노드가있을 때까지 4 단계 또는 5 단계를 반복하십시오.
7. 마지막 노드를 루트 노드에 할당합니다.
자바 코드
원칙은 완료되었으며 다음 단계는 코드를 구현하는 것입니다.
먼저 데이터를 저장할 노드 클래스가 있습니다.
패키지 huffman;/** * 노드 클래스 * @author yuxiu * */public class node {public String code; // 노드 공개 int 코드를 인코딩; // 노드의 길이 공개 문자열 데이터 인코딩; // 노드 데이터 공개 int count; // 노드 웨이트 퍼블릭 노드 lchild; 공개 노드 rchild; public node () {} public node (문자열 data, int count) {this.data = data; this.count = count; } public node (int count, 노드 lchild, 노드 rchild) {this.count = count; this.lchild = lchild; this.rchild = rchild; } public node (문자열 데이터, int count, node lchild, node rchild) {this.data = data; this.count = count; this.lchild = lchild; this.rchild = rchild; }}그런 다음 구현 프로세스가 있습니다.
package huffman;import java.io.*;import java.util.*;public class Huffman { private String str;// Originally used for compression private String newStr = "";// The string connected by Huffman encoding private Node root;// The root node of the Huffman binary tree private boolean flag;// Whether the latest characters already exist private ArrayList<String> charList;// The queue for storing different characters 동일한 위치에있는 동일한 문자 개인 Arraylist <Node> nodelist; // 노드 저장을위한 대기열 15 16/ ** * Huffman Tree를 빌드 * @param str */ public void creathfmtree (String str) {this.str = str; charlist = new arraylist <string> (); nodelist = new arraylist <node> (); // 1. 통계 문자열에 나타나는 문자 수와 문자의 수는 // 기본 아이디어는 charlist에 aa, bbb, cc, dd, ee //와 같은 변하지 않은 문자열을 넣는 것입니다. 목록의 문자열의 길이는 (int i = 0; i <str.length (); i ++) {char charat (i); // 문자 깃발을 꺼냅니다. 플래그 = true; for (int j = 0; Charlist.Set (J, S); flag = false; 부서지다; }} if (flag) {charlist.add (charlist.size (), ch + ""); }} // 2. (int i = 0; i <charlist.size (); i ++) {string data = charlist.get (i) .charat (0)+""; // Charlist int count = charlist.get (i) .length ()에서 각 문자열의 첫 번째 문자를 얻습니다. // 목록의 문자열의 길이는 해당 무게 노드 노드 = 새 노드 (data, count)입니다. // 노드 객체 nodelist.add (i, node) 만들기; // 노드 큐에 가입} // 3. sort (nodelist); while (nodelist.size ()> 1) {// 노드의 수가 1보다 큰 경우 // 4. 가장 작은 무게로 두 노드를 꺼내 새로운 상위 노드를 생성 // 5. 가장 작은 무게로 두 노드를 삭제하고 목록 노드 왼쪽 = nodelist.remove (0); 노드 오른쪽 = nodelist.remove (0); int parentweight = left.count + right.count; // 상위 노드의 무게는 자식 노드의 가중치의 합과 같습니다. nodelist.add (0, 부모); // 부모 노드를 첫 번째 위치에 놓습니다} // 6. 네 번째 및 다섯 번째 단계를 while 루프로 반복하십시오. // 7. 마지막 노드를 루트 노드 루트에 할당 = nodelist.get (0); } / ** * 오름차순 순서 * * @param nodelist * / public void sort (arraylist <node> nodelist) {for (int i = 0; i <nodelist.size () -1; i ++) {(int j = i+1; j <nodelist.size (); j ++) {node temp; if (nodelist.get (i) .count> nodelist.get (j) .count) {temp = nodelist.get (i); nodelist.set (i, nodelist.get (j)); nodelist.set (j, temp); }}}} / ** * Traversal * * @param node * node * / public void output (node node) {if (node.lchild! = null) {output (node.lchild); } system.out.print (node.count + ""); // (node.rchild! = null) {output (node.rchild); }} public void output () {output (root); }/** * 메인 메소드 * * @param args */public static void main (string [] args) {Huffman Huff = new Huffman (); // Havalman 객체 Huff.creathfmtree ( "sdfassvvvdfgsfdfsdfs"); // 트리 구성})요약
위의 것은 Java를 기반으로 Huffman Tree를 구현하는 것입니다. 이 기사가 모든 사람이 Java 사용 방법을 배우는 데 도움이되기를 바랍니다. 궁금한 점이 있으면 메시지를 남겨 두십시오.