مقدمة
أعتقد أن الأصدقاء الذين تعلموا هياكل البيانات يجب أن يعرفوا هوفمان. اخترع هذا الله العظيم "شجرة ثنائية مثالية" الشهيرة. من أجل الاحتفال به ، نسميها "شجرة هوفمان". يمكن استخدام شجرة 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
من الواضح أن الشجرة الثالثة لديها أقصر مسار للوزن (لا تصدق ذلك ، يمكنك تجربتها. إذا تمكنت من العثور على واحدة أقصر ، فمن المحتمل أن تفوز بجائزة Turing). هذا ما نسميه "شجرة الثنائية الأمثل (شجرة هافمان)". طريقة البناء بسيطة للغاية. يمكنك تحديد العقدة ذات الوزن الأصغر ووضعها في أسفل الشجرة ، ووضع أصغر الاتصالات في عقدة جديدة. تجدر الإشارة إلى أن وزن العقدة الجديدة التي تم تشكيلها يجب أن يكون مساوياً لمجموع أوزان هاتين العقدتين. ثم ضع هذه العقدة الجديدة مرة أخرى في العقدة حيث نحتاج إلى تشكيل الشجرة لمواصلة الفرز. وبهذه الطريقة ، توجد جميع العقد مع المعلومات المخزنة في شجرة Hafman على العقد الورقية.
بعد الانتهاء من المفهوم ، قد أكون "غير واضح" قليلاً.
دعونا نقدم مثالاً لبناءه بوضوح.
هناك سلسلة: AAAAAAABBBBBAAAACCCCCCDDDDDFFF
في الخطوة الأولى ، نحسب أولاً عدد المرات التي يظهر فيها كل حرف ونطلق عليه وزن الحرف. 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. تعيين العقدة الأخيرة إلى عقدة الجذر.
كود جافا
تم الانتهاء من المبدأ ، والخطوة التالية هي تنفيذ الرمز.
أولاً ، هناك فئة عقدة لتخزين البيانات.
حزمة Huffman ؛/** * فئة العقدة * Author Yuxiu * */Node Class Public {Code Public String Code ؛ // Hafman ترميز Node Public Int Codesize ؛ // طول العقدة Huffman تشفير بيانات السلسلة العامة ؛ // Node Data Count ؛ العقدة العامة rchild ؛ NODE () {} العقدة العامة (بيانات السلسلة ، العدد int) {this.data = data ؛ this.count = count ؛ } العقدة العامة (عدد int ، العقدة lchild ، العقدة rchild) {this.count = count ؛ this.lchild = lchild ؛ this.rchild = rchild ؛ } العقدة العامة (بيانات السلسلة ، عدد int ، العقدة lchild ، العقدة rchild) {this.data = data ؛ this.count = count ؛ this.lchild = lchild ؛ this.rchild = rchild ؛ }}ثم هناك عملية التنفيذ.
حزمة huffman ؛ استيراد java.io.*؛ استيراد java.util.*؛ فئة عامة huffman {private string str ؛ // المستخدمة في الأصل لضغط NewsTr string string = "؛ نفس الحرف في نفس الموقف arraylist الخاص <Node> nodeList ؛ // قائمة الانتظار لتخزين العقد 15 16/ ** * بناء شجرة huffman * * param str */ public void 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 ؛ i <str.length () // أخرج علم الحرف = صحيح ؛ لـ (int j = 0 ؛ j <charlist.size () ؛ j ++) {if (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 ++) {string data = charlist.get (i) .charat (0)+"" ؛ // احصل على الحرف الأول من كل سلسلة في charlist int count = charlist.get (i) .Length () ؛ // طول السلسلة في القائمة هو عقدة العقدة المقابلة = عقدة جديدة (البيانات ، العد) ؛ // Create Node Object Nodelist.add (I ، Node) ؛ // انضم إلى قائمة انتظار العقدة} // 3. الفرز (nodeList) ؛ بينما (nodeList.size ()> 1) {// عندما يكون عدد العقد أكبر من واحد // 4. قم بإخراج العقدتين مع أصغر وزن وإنشاء عقدة الوالد الجديدة/ 5. قم بحذف العقدتين بأصغر وزن وتخزين العقدة الأصل في قائمة القائمة المترتبة = nodelist.remove (0) ؛ العقدة اليمنى = nodelist.remove (0) ؛ int parentweight = left.count + right.count ؛ // وزن العقدة الأصل يساوي مجموع أوزان عقدة الطفل الأصل = عقدة جديدة (الأصل ، اليسار ، يمين) ؛ nodelist.add (0 ، الوالد) ؛ // ضع العقدة الأصل في الموضع الأول} // 6. كرر الخطوتين الرابع والخامس ليكون الحلقة // 7. تعيين العقدة الأخيرة إلى جذر عقدة الجذر = nodeList.get (0) ؛ } / ** * ترتيب تصاعدي * * param nodeList * / public void sort (ArrayList <Node> nodeList) {for (int i = 0 ؛ i <nodelist.size () - 1 ؛ i ++) {for (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 + "") ؛ // in-order arversal if (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 (لخص
ما سبق هو كل شيء عن تنفيذ شجرة هوفمان بناءً على جافا. آمل أن يكون هذا المقال مفيدًا للجميع لتعلم كيفية استخدام Java. إذا كان لديك أي أسئلة ، فيرجى ترك رسالة لمناقشة.