Huffman Code

[sivz]

Huffman Code

יש לי שאלה, אולי למישהו יש פתרון או הצעה לפתרון: קובץ Z מכיל איברים {A1,A2,....An} בהסתברויות שונות. נניח כי דחסו את קובץ Z בשיטת Static Huffman. א. הוכח כי קיום אינדקס i כך שהסתברותו של האיבר ה- Ai גדולה או שוה חצי היא תנאי מספיק לקיום מילת קוד באורך של סיבית אחת. ב. הוכח כי קיום אינדקס i כך שהסתברות האיבר ה- Ai גדולה או שווה שליש היא תנאי הכרחי לקיום מילת קוד באורך של סיבית אחת. תודה רבה

 

[Maha Vailo]

תשובה

אני לא ממש זוכר את השמות, אז אני מקווה ששיטת הפמן סטטית זו הכוונה לבניית העץ מראש ע"י ההסתברויות. עבור הסעיף הראשון תחשוב על הבנייה של עץ הפמן. כל פעם מחברים את שני הצמתים עם ההסתברות הכי קטנה. מאחר ויש אות שיש לה הסתברות שגדולה מחצי, אז קודם יחברו את כל שאר הצמתים (כי ההסתברות שלהם תמיד תהיה קטנה מחצי) וגם כל אלה יחד יגיעו למקסימום הסתברות חצי לכן, כאשר נוסיף את האות עם ההסתברות חצי או יותר לעץ הפמן זה יהיה לרמה הראשונה של העץ, כלומר נחבר את הצומת של האות ישר לשורש של העץ - כלומר האורך של המילת קוד שלה תהיה אחת. הסעיף השני לא נראה לי נכון, כי אם A בהסתברות 1/3 ויש עוד שלוש אותיות B C D בהסתברות 2/9 כל אחת אז קודם כל האלגוריתם יחבר שתי אותיות B C וייצור צומת של 4/9 ואז יחבר את A D וייצור צומת של 5/9 ויאז יחבר את שני הצמתים החדשים ובעצם כל אות תהיה עם אורך קוד 2.

 

[sivz]

תודה

קודם כל תודה... זכרת נכון את השיטה של הבנייה. סעיף ראשון נשמע לי הגיוני וגם כן ההסבר, זה גם מה שאני חשבתי. בקשר לסעיף השני, ההסבר שלך נשמע הגיוני, אבל זו שאלה מתוך בחינה ואני חושבת שצרך להיות לזה הסבר. בכל אופן, תודה רבה על העזרה

 

[vinney]

תנאי הכרחי זה לא בהכרח תנאי מספיק

ויקי נתנה דוגמא למה זה לא תנאי מספיק, אבל זה בהחלט תנאי הכרחי, וזה מה שנדרשת להוכיח

 

[Maha Vailo]

צודק

לא שמתי לב שרשום בחלק השני תנאי הכרחי אז כמובן אם לכל האותיות הסתברות קטנה ממש משליש, אז כדי שאות A תהיה עם אורך קוד של אחד זה אומר שבבניית עץ מוסיפים אותה אחרונה יחד עם צומת שההסתברות שלה גדולה ממש משני שליש. מאחר וצומת זו לא יכולה להיות אות (כי הנחתי שההסתברות של האותיות קטנה משליש) אז היא מורכבת משני צמתים שלפחות אחד מהם גדול ממש משליש. וזה לא הגיוני, כי אז בשלב הקודם של בניית העץ היו לוקחים את הצומת של A והצומת הקטנה יותר. אז ההסתברות שאות כלשהי תהיה גדולה שווה שליש זה תנאי הכרחי

 

[vinney]

אופס, למה חשבתי שאת ויקי../images/Emo13.gif

סליחה, הדיסלקציה