|
[[קובץ:Huffman tree 2.svg|שמאל|ממוזער|450px|עץ האפמן שנוצר על פי התדירויות במשפט "this is an example of a huffman tree"]]
'''קוד האפמן''' הוא שיטה ל[[קידוד תווים|קידוד סימנים]], כגון תווי טקסט, ללא [[דחיסה_מאבדת_נתונים|אובדן נתונים]].
הקוד שייך למשפחה שימושית של קודים המכונה [[קוד תחיליות|קודי תחיליות]] (ראו למטה), ובמשפחה זו הוא הקוד המספק [[דחיסת נתונים]] מרבית, כלומר מאחסן את הסימנים במספר מזערי של [[סיבית|סיביות]], על פי הקריטריון המפורט למטהבהמשך. השיטה מתבססת על הקצאת אורך משתנה לסימנים על פי שכיחותם, כך שסימן נפוץ יוצג באמצעות מספר קטן של סיביות. לרוב ניתן לחסוך באמצעות שיטה זו בין 20% ל-90% משטח האחסון. קוד האפמן הוא גרסה כללית יותר של עקרון קידוד הנקרא "[[קידוד אנטרופיה]]".
==גילוי הקוד==
בשנת [[1951]], במסגרת לימודיו לדוקטורט ב־[[MIT]], למד [[דייוויד האפמן]] למד קורס ב[[תורת האינפורמציה]] שהייתה אז בחיתוליה. המרצה בקורס [[רוברט פאנו]] הציע לתלמידים לבחור בין עבודה מסכמת ובין מבחן מסכם. העבודה שהציע פאנו הייתה בנושא מציאת הקוד הבינארי היעיל ביותר - בעיה שהייתה פתוחה באותו הזמן; הקוד הטוב ביותר שהיה ידוע נקרא [[קוד שאנון-פאנו]]. האפמן, שלא הצליח להוכיח שאף אחד מהקודים הקיימים הוא יעיל ביותר, עמד להיכנע ולהתחיל ללמוד לבחינה המסכמת, כאשר עלה במוחו הרעיון להשתמש בעצים בינאריים ממויינים על פי תדירות האותיות, כשבנייתם היא מהעלים כלפי מעלה. במהרה הוכיח כי שיטתו היא היעילה ביותר. האפמן עקף את המגבלה המרכזית בקוד שאנון-פאנו על ידי כך שבנה את העץ מלמטה למעלה, ולא ההפך.
==רקע==
במערכות סימנים מקובלות, כגון קוד [[ASCII]], ניתן אורך אחיד לכל הסימנים במערכת. זו שיטה פשוטה, אך היא אינה יעילה מבחינת נפח האחסון שהיא צורכת: ישמוטב סימניםהיה נדיריםלהקצות קוד קצר לסימנים הנפוצים, להםגם יכולנועל לתתחשבון הארכה של הקוד המתאים לסימנים הנדירים. יעילות של קוד ארוךכזה יותרתלויה רק בשכיחות הסימנים בשפה, ולעומתםולא להעדיףבסדר קודשבו קצרהם לסימניםמופיעים הנפוציםבטקסט נתון. יישום של גישה זו קיים כבר ב[[קוד מורס]] ל[[טלגרף]] אלחוטי. לאות הנפוצה 'ו' משמש בקוד מורס הקוד <big>'''.'''</big> ("נקודה"), ואילו לאות 'ע' משמש הקוד <big>'''- - - .'''</big> ("קו-קו-קו-נקודה").
נמחיש את יעילותה של גישה זו באמצעות דוגמה פשוטה. נניח שנתונהשבשפה מחרוזתמסויימת בתהשכיחות 200 תווים, שמחציתםשל האות א' היא מחצית מכלל האותיות. בקוד ASCII, שבו לכל תו מוקדשות 8 סיביות, אורכהמספר שלהסיביות מחרוזתהנדרש זולהצגת טקסט באורך n הוא 1,600 סיביות8n. נקודד כעת את התווים בדרך חדשה: האות א' תסומן בסיבית יחידה שערכה 0, וכל תו אחר יסומן בקוד ה-ASCII הרגיל שלו, שבתחילתו תתוסף הסיבית 1 (תוספת זו הכרחית, כדי שנוכל להבדיל בין סיבית 0 שמציינת את האות א, ובין סיבית 0 באמצע תו כלשהו). אורך המחרוזתהקוד בקודהזה זהיהיה הוא(ב[[תוחלת]]) 1,000רק סיביות בלבד5n, שהם 63%חסכון מאורךשל המחרוזת המקורית3/8.
==תיאור פורמלי==
===תיאור הקוד===
קוד האפמן הוא [[קוד תחיליות]], כלומר כל מחרוזת ביטים שמייצגת אות לעולם אינה מהווה תחילית של מחרוזת המייצגת אות אחרת. קוד כזה מבטיח אפשרות יחידה לפיענוח, ויתירה מזאת, הפיענוח מהיר, שכן מספיק לעבור על המסמךהרצף המקודד פעם אחת מההתחלה ועד הסוף תוך שמירת מעט מידע.
קוד מסוג זה ניתן לייצג על ידי [[עץ בינארי]], כאשר עלי העץ מייצגים את האותיות המקודדות, וצמתי העץ מסומנים ב-0 או 1. כאשר רוצים לפענח רצף ביטים כלשהו, הולכים על העץ על פי הביטים שנקלטים עד אשר מגיעים לעלה. האות המאוחסנת בעלה היא האות המפוענחת.
===תיאור הבעיה===
הבעיהבהנתן העיקריתשכיחות שאותההתווים פתרבשפה, האפמןהבעיה אינההאלגוריתמית תיאורהיא הקודבניה עצמו,מהירה אלאשל מציאת [[אלגוריתם]]קוד יעיל, שמבטיחהממיר בנייהאת שלהתווים קודלרצפים כזהקצרים בהינתןשל קבוצתסיביות. תוויםלאחר כלשהי.שהקוד מרגענבנה, שקייםאפשר קוד כנדרש,לבצע קידוד ופענוח ניתנים לביצוע במעבר אחד על התווים, ולכן הבעיה הגדולההמשמעותית היחידה היא מציאתבמציאת הקוד. מכיווןהיעילות שאופטימליותשל הקודקוד מתבססתתלויה עלכאמור מספרבמספר המופעים של כל תו בקבוצת התוויםבשפה, ולכן לא קיים קוד אחדאחיד שנותן קידוד אופטימלי לכל קבוצת תווים: אם שכיחות התווים שונה, ולכןיש נדרשתלהפעיל הפעלה שלאת האלגוריתם ובנייתולבנות את הקוד המתאים עבור הקבוצהמחדש.
מבחינה פורמלית, הקלט לבעיה הוא אוסף תווים, <math>\ a_1,a_2,\dots,a_n</math>, ומספר הפעמים שכל תו מופיע בקבוצת התווים: <math>\ c_1,c_2,\dots,c_n</math>.
הפלט הצפוי הוא '''קוד''', שהוא אוסף <math>\ h_1,h_2,\dots,h_n</math> של מילים בינאריות. נסמן ב-<math>\ |h_k|</math> את אורכה של המילה ה-<math>\ k</math>.
היעד הוא שהקוד שיוחזר יהיה כזה כך ש- <math>\ \sum_{k=1}^n c_k\cdot|h_k|</math> יהיה מינימלי. הסכום הוא בדיוק מספר הביטים שנדרש לקידוד קבוצת התווים כולה, שכן עבור כל תו, אנו מכפילים את מספר המופעים שלה בקבוצה במספר הביטים שנדרשים כדי לייצג אותה.
|
