คำนำ
ฉันคิดว่าเพื่อนที่เรียนรู้โครงสร้างข้อมูลต้องรู้จัก Huffman พระเจ้าผู้ยิ่งใหญ่คนนี้คิดค้น "ต้นไม้ไบนารีที่ดีที่สุด" ที่มีชื่อเสียง เพื่อที่จะระลึกถึงเขาเราเรียกมันว่า "Huffman Tree" ต้นไม้ Huffman สามารถใช้สำหรับการเข้ารหัส Huffman และความรู้ในการเข้ารหัสนั้นยอดเยี่ยมมากเช่นสำหรับการบีบอัดการเข้ารหัสลับ ฯลฯ ลองมาดูกันว่าต้นไม้ Huffman คืออะไรในปัจจุบัน
แนวคิด
แน่นอนหนึ่งในกิจวัตรประจำวันคือเราต้องเข้าใจแนวคิดพื้นฐานบางอย่าง
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)" วิธีการก่อสร้างนั้นง่ายมาก คุณเลือกโหนดด้วยน้ำหนักที่เล็กที่สุดและวางไว้ที่ด้านล่างของต้นไม้และวางการเชื่อมต่อที่เล็กที่สุดสองรายการลงในโหนดใหม่ ควรสังเกตว่าน้ำหนักของโหนดใหม่ที่เกิดขึ้นควรเท่ากับผลรวมของน้ำหนักของสองโหนดนี้ จากนั้นใส่โหนดใหม่นี้กลับเข้าไปในโหนดที่เราจำเป็นต้องสร้างต้นไม้เพื่อเรียงลำดับต่อไป ด้วยวิธีนี้โหนดทั้งหมดที่มีข้อมูลที่เก็บไว้ในต้นไม้ Hafman อยู่บนโหนดใบไม้
หลังจากเสร็จสิ้นแนวคิดฉันอาจจะ "ไม่ชัดเจน" นิดหน่อย
มายกตัวอย่างเพื่อสร้างให้ชัดเจน
มีสตริง: AAAAAAAABBBBAAAAACCCCCCCCCCCCCCCCCCCCCDDDDDDDFFF
ในขั้นตอนแรกเรานับจำนวนครั้งแรกที่ตัวละครแต่ละตัวปรากฏขึ้นและเรียกมันว่าน้ำหนักของตัวละคร A 15, B 5, C 8, D 6, F 3
ขั้นตอนที่สองคือการค้นหาตัวละครสองตัวที่มีน้ำหนักน้อยที่สุด B5 และ F3 และสร้างโหนด
จากนั้นลบ F3 และ B5 ตอนนี้ A15, C8, D6, FB8
ขั้นตอนที่ 3 ทำซ้ำขั้นตอนที่สองจนกว่าจะมีการสร้างโหนดเพียงหนึ่งโหนด
ตอนนี้เป็น DFB14, A15, C8
ในที่สุด
ตกลงต้นไม้ Huffman ของเราถูกสร้างขึ้น
ขั้นตอนในการสร้าง
ตามตรรกะข้างต้นเพื่อสรุปมันมีไม่กี่ขั้นตอน:
1. สถิติจำนวนอักขระและอักขระที่ปรากฏในสตริง
2. สร้างโหนดตามโครงสร้างของขั้นตอนแรก
3. เรียงลำดับโหนดน้ำหนักคำสั่งจากน้อยไปหามาก
4. นำโหนดสองโหนดออกมาด้วยน้ำหนักที่เล็กที่สุดและสร้างโหนดพาเรนต์ใหม่
5. ลบทั้งสองโหนดด้วยน้ำหนักที่เล็กที่สุดและเก็บโหนดพาเรนต์ไว้ในรายการ
6. ทำซ้ำขั้นตอนที่ 4 หรือ 5 จนกว่าจะมีโหนดเหลือ;
7. กำหนดโหนดสุดท้ายให้กับโหนดรูท
รหัส Java
หลักการเสร็จสิ้นและขั้นตอนต่อไปคือการใช้รหัส
ก่อนอื่นมีคลาสโหนดเพื่อจัดเก็บข้อมูล
แพ็คเกจ huffman;/** * คลาสโหนด * @author yuxiu * */โหนดคลาสสาธารณะ {รหัสสตริงสาธารณะ; // hafman การเข้ารหัสของโหนดรหัสสาธารณะรหัสสาธารณะ; // ความยาวของโหนด huffman เข้ารหัสข้อมูลสตริงสาธารณะ; // โหนดข้อมูล โหนดสาธารณะ rchild; โหนดสาธารณะ () {} โหนดสาธารณะ (ข้อมูลสตริง, จำนวน int) {this.data = data; this.count = นับ; } โหนดสาธารณะ (จำนวน int, โหนด lchild, โหนด rchild) {this.count = count; this.lchild = lchild; this.rchild = rchild; } โหนดสาธารณะ (ข้อมูลสตริง, จำนวน int, โหนด lchild, โหนด rchild) {this.data = data; this.count = นับ; this.lchild = lchild; this.rchild = rchild; -จากนั้นก็มีกระบวนการดำเนินการ
Package Huffman; Import Java.io.*; นำเข้า Java.util.*; คลาสสาธารณะ Huffman {สตริงส่วนตัว str; // ที่ใช้สำหรับการบีบอัดสตริงส่วนตัว newstr = ""; // สตริงที่เชื่อมต่อโดย Huffman การเข้ารหัสโหนดส่วนตัว อักขระที่แตกต่างกันเป็นอักขระเดียวกันในตำแหน่งเดียวกัน ArrayList ส่วนตัว <Node> Nodelist; // คิวสำหรับการจัดเก็บโหนด 15 16/ ** * สร้าง Huffman Tree * * @param str */ โมฆะสาธารณะ Creathfmtree (String str) {this.str = str; charlist = new ArrayList <String> (); Nodelist = new ArrayList <Node> (); // 1. สถิติจำนวนอักขระและอักขระที่ปรากฏในสตริง // ความคิดพื้นฐานคือการใส่สตริงที่ไม่ได้เรียงลำดับเช่น Ababccdebed ลงใน Charlist ซึ่งเป็น AA, BBB, CC, DD, EE // และความยาวของสตริงในรายการคือน้ำหนักที่สอดคล้องกันสำหรับ (int i = 0; // นำธงอักขระออก = true; สำหรับ (int j = 0; j <charlist.size (); j ++) {ถ้า (charlist.get (j) .charat (0) == ch) {// ถ้าพบอักขระเดียวกันกับสตริง s = charlist.get (j)+ch; charlist.set (j, s); ธง = เท็จ; หยุดพัก; }} if (Flag) {charlist.add (charlist.size (), ch + ""); }} // 2. สร้างโหนดตามโครงสร้างของขั้นตอนแรกสำหรับ (int i = 0; i <charlist.size (); i ++) {สตริง data = charlist.get (i) .charat (0)+""; // รับอักขระแรกของแต่ละสตริงใน charlist int count = charlist.get (i) .length (); // ความยาวของสตริงในรายการคือโหนดน้ำหนักที่สอดคล้องกัน Node = โหนดใหม่ (data, count); // สร้าง Node NodeList.add (i, Node); // เข้าร่วมกับคิวโหนด} // 3. เรียงลำดับ (nodelist); ในขณะที่ (nodelist.size ()> 1) {// เมื่อจำนวนโหนดมากกว่าหนึ่ง // 4 นำสองโหนดด้วยน้ำหนักที่เล็กที่สุดและสร้างโหนดพาเรนต์ใหม่ // 5 ลบทั้งสองโหนดด้วยน้ำหนักที่เล็กที่สุด โหนดขวา = nodelist.remove (0); int parentweight = ซ้าย count + ขวา. count; // น้ำหนักของโหนดพาเรนต์เท่ากับผลรวมของน้ำหนักของโหนดโหนดโหนด parent = โหนดใหม่ (parentweight, ซ้าย, ขวา); Nodelist.add (0, Parent); // วางโหนดพาเรนต์ที่ตำแหน่งแรก} // 6 ทำซ้ำขั้นตอนที่สี่และห้าเป็นขณะที่ลูป // 7 กำหนดโหนดสุดท้ายให้กับรูทรูทรูทรูท = nodelist.get (0); } / ** * คำสั่งซื้อจากน้อยไปมาก * * @param nodelist * / public void sort (arraylist <node> nodelist) {สำหรับ (int i = 0; i <nodelist.size () - 1; i ++) {สำหรับ (int j = i+1; j <nodelist.size (); j ++) 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) {ถ้า (node.lchild! = null) {output (node.lchild); } system.out.print (node.count + ""); // in-order traversal ถ้า (node.rchild! = null) {output (node.rchild); }} เอาต์พุตโมฆะสาธารณะ () {เอาต์พุต (รูท); }/** * วิธีหลัก * * @param args */โมฆะคงที่สาธารณะหลัก (สตริง [] args) {huffman huff = new huffman (); // สร้างวัตถุ Havalman huff.creathfmtree ("sdfassvvdfgsfdfsdfs");สรุป
ข้างต้นคือทั้งหมดที่เกี่ยวกับการใช้ต้นไม้ Huffman ตาม Java ฉันหวังว่าบทความนี้จะเป็นประโยชน์กับทุกคนในการเรียนรู้วิธีใช้ Java หากคุณมีคำถามใด ๆ โปรดฝากข้อความเพื่อพูดคุย