คัดลอกรหัสรหัสดังต่อไปนี้:
// คลาสการใช้งานของการเข้ารหัส Huffman
HffmanCoding ระดับสาธารณะ {
private int charsAndWeight[][];// [][0] คืออักขระ [][1] เก็บน้ำหนัก (จำนวนครั้ง) ของอักขระ
int hfmcoding ส่วนตัว []; // ต้นไม้ Huffman ที่เก็บข้อมูล
int ส่วนตัว i = 0; // ตัวแปรลูป
สตริงส่วนตัว hcs[];
สาธารณะ HffmanCoding (int [] ตัวอักษร) {
// ตัวสร้าง TODO
charsAndWeight = int ใหม่ [chars.length] [2];
charsAndWeight = ตัวอักษร;
hfmcoding = new int[2 * chars.length - 1][4];//จัดสรรพื้นที่สำหรับแผนผัง Huffman
-
// การใช้งานแผนผัง Huffman
การเข้ารหัสเป็นโมฆะสาธารณะ () {
int n = charsAndWeight.length;
ถ้า(n==0)
กลับ;
int ม. = 2 * n - 1;
// เริ่มต้นต้นไม้ Huffman
สำหรับ (i = 0; i <n; i++) {
hfmcoding[i][0] = charsAndWeight[i][1];//เริ่มต้นน้ำหนักของต้นไม้ Huffman
hfmcoding[i][1] = 0;//เริ่มต้นโหนดรูทของทรี Huffman
hfmcoding[i][2] = 0;//เตรียมใช้งานลูกด้านซ้ายของแผนผัง Huffman
hfmcoding[i][3] = 0;//เตรียมใช้งานลูกที่ถูกต้องของแผนผัง Huffman
-
สำหรับ (i = n; i < m; i++) {
hfmcoding[i][0] = 0;//เริ่มต้นน้ำหนักของต้นไม้ Huffman
hfmcoding[i][1] = 0;//เริ่มต้นโหนดรูทของทรี Huffman
hfmcoding[i][2] = 0;//เตรียมใช้งานลูกด้านซ้ายของแผนผัง Huffman
hfmcoding[i][3] = 0;//เตรียมใช้งานลูกที่ถูกต้องของแผนผัง Huffman
-
//สร้างต้นไม้ฮัฟฟ์แมน
สำหรับ (i = n; i < m; i++) {
int s1[] = select(i); // ค้นหาโหนดที่มีน้ำหนักน้อยที่สุดโดยที่ parent เป็นศูนย์ในแผนผัง Huffman
hfmcoding[s1[0]][1] = i;// จ่ายเงินให้ผู้ปกครองตามมูลค่าขั้นต่ำของแผนผัง Huffman
hfmcoding[s1[1]][1] = ฉัน;
hfmcoding [i] [2] = s1 [0]; // ลูกซ้ายของโหนดใหม่
hfmcoding[i][3] = s1[1];//ลูกขวาของโหนดใหม่
hfmcoding[i][0] = hfmcoding[s1[0]][0] + hfmcoding[s1[1]][0];//น้ำหนักของโหนดใหม่คือผลรวมของน้ำหนักของลูกด้านซ้ายและขวา
-
-
//ค้นหาโหนดที่มีน้ำหนักน้อยที่สุดโดยที่พาเรนต์เป็นศูนย์
int ส่วนตัว [] เลือก (int w) {
// TODO ต้นขั้ววิธีการสร้างอัตโนมัติ
int s[] = { -1, -1 }, j = 0; // s1 คือหมายเลขลำดับของโหนดที่มีน้ำหนักน้อยที่สุดและมีพาเรนต์เป็นศูนย์ i คือตัวแปรลูป
int min1 = 32767, min2 = 32767;
สำหรับ (j = 0; j < w; j ++) {
if (hfmcoding[j][1] == 0) {// ค้นหาเฉพาะในโหนดที่ยังไม่ได้สร้างแผนผังไบนารี (โหนดที่ไม่มีพาเรนต์เป็นศูนย์)
ถ้า (hfmcoding[j][0] < min1) {
นาที2 = นาที1;
ส[1] = ส[0];
min1 = การเข้ารหัส hfm[j] [0];
ส[0] = เจ;
} อื่นถ้า (hfmcoding[j][0] < min2) {
min2 = การเข้ารหัส hfm[j] [0];
ส[1] = เจ;
-
-
-
กลับ;
-
public String[] CreateHCode() {// ค้นหาโค้ด Huffman ตามแผนผัง Huffman
int n = charsAndWeight.length;
ฉัน, ฉ, ค;
สตริง hcodeString = "";
hcs = สตริงใหม่ [n];
สำหรับ (i = 0; i < n; i++) {// ค้นหาโค้ด Huffman ตามแผนผัง Huffman
ค = ฉัน;
hcodeString = "";
f = hfmcoding[i][1]; // f คือโหนดรูทของแผนผัง Huffman
ในขณะที่ (f != 0) {//ตามลำดับจนถึงโหนดรูทของทรี
ถ้า (hfmcoding [f] [2] == c) {// ประมวลผลโหนดลูกด้านซ้าย
hcodeString += "0";
} อื่น {
hcodeString += "1";
-
ค = ฉ;
f = hfmcoding[f][1];
-
hcs[i] = สตริงใหม่ (StringBuffer ใหม่ (hcodeString).reverse());
-
ส่งคืน hcs;
-
การแสดงสตริงสาธารณะ (สตริง s) {// แสดงการเข้ารหัสสตริง
สตริง textString = "";
ถ่านค[];
อินท์เค = -1;
c = ถ่านใหม่ [s.length()];
c = s.toCharArray(); // แปลงสตริงเป็นอาร์เรย์อักขระ
สำหรับ (int i = 0; i < c.length; i++) {
เค = ค[ฉัน];
สำหรับ (int j = 0; j < charsAndWeight.length; j++)
ถ้า (k == ตัวอักษร AndWeight [j] [0])
textString += hcs[j];
-
กลับข้อความสตริง;
-
// การคอมไพล์การเข้ารหัสของ Huffman
reCoding สตริงสาธารณะ (สตริง s) {
String text = "";//เก็บอักขระที่ถอดรหัสแล้ว
int k = 0, m = hfmcoding.length - 1;//เริ่มการสืบค้นจากโหนดรูท
ถ่านค[];
c = ถ่านใหม่ [s.length()];
c = s.toCharArray();
เค = ม.;
สำหรับ (int i = 0; i < c.length; i++) {
ถ้า (c[i] == '0') {
k = hfmcoding[k][2];//ค่าของ k คือหมายเลขลำดับของลูกด้านซ้ายของโหนดรูท
if (hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0)// พิจารณาว่าเป็นโหนดปลายสุดหรือไม่ เงื่อนไข (ลูกทั้งซ้ายและขวาเป็นศูนย์)
-
ข้อความ += (อักขระ) charsAndWeight[k] [0];
เค = ม.;
-
-
ถ้า (c[i] == '1') {
k = hfmcoding[k][3];//ค่าของ k คือหมายเลขลำดับของลูกด้านขวาของโหนดรูท
if (hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0)// พิจารณาว่าเป็นโหนดปลายสุดหรือไม่ เงื่อนไข (ลูกทั้งซ้ายและขวาเป็นศูนย์)
-
ข้อความ += (อักขระ) charsAndWeight[k] [0];
เค = ม.;
-
-
-
ส่งกลับข้อความ;
-
-