ויקיפדיה

קוד האפמן – הבדלי גרסאות

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
אין תקציר עריכה
שורה 1:
[[קובץ:Huffman tree 2.svg|שמאל|ממוזער|450px|עץ הופמןהאפמן שנוצר על פי התדירויות במשפט "this is an example of a huffman tree"]]
'''קוד הופמןהאפמן''' הוא שיטה ל[[קידוד תווים|קידוד סימנים]], כגון תווי טקסט, ללא [[דחיסה_מאבדת_נתונים|אובדן נתונים]].
הקוד שייך למשפחה שימושית של קודים המכונה [[קוד תחיליות|קודי תחיליות]] (ראה למטה), ובמשפחה זו הוא הקוד המספק [[דחיסת נתונים]] מרבית, כלומר מאחסן את הסימנים במספר מזערי של [[סיבית|סיביות]]. השיטה מתבססת על אורך משתנה לסימנים, כך שסימן נפוץ יוצג באמצעות מספר קטן של סיביות. לרוב ניתן לחסוך באמצעות שיטה זו בין 20% ל-90% משטח האחסון. קוד הופמןהאפמן הוא גרסה כללית יותר של עקרון קידוד הנקרא "[[קידוד אנטרופיה]]".
 
==גילוי הקוד==
שורה 14:
 
===תיאור הקוד===
קוד הופמןהאפמן הוא [[קוד תחיליות]], כלומר כל מחרוזת ביטים שמייצגת אות אינה תחילית של מחרוזת המייצגת אות אחרת. קוד כזה מבטיח אפשרות יחידה לפיענוח, ויתירה מזאת, הפיענוח מהיר, שכן מספיק לעבור על המסמך המקודד פעם אחת מההתחלה ועד הסוף תוך שמירת מעט מידע.
 
קוד מסוג זה ניתן לייצג על ידי [[עץ בינארי]], כאשר עלי העץ מייצגים את האותיות המקודדות, וצמתי העץ מסומנים ב-0 או 1. כאשר רוצים לפענח רצף ביטים כלשהו, הולכים על העץ על פי הביטים שנקלטים עד אשר מגיעים לעלה. האות המאוחסנת בעלה היא האות המפוענחת.
שורה 21:
 
===תיאור הבעיה===
הבעיה העיקרית שאותה פתר הופמןהאפמן אינה תיאור הקוד עצמו, אלא מציאת [[אלגוריתם]] יעיל שמבטיח בנייה של קוד כזה בהינתן מסמך כלשהו. מרגע שקיים קוד כנדרש, קידוד ופענוח ניתנים לביצוע במעבר אחד על הטקסט, ולכן הבעיה הגדולה היא מציאת הקוד. מכיוון שאופטימליות הקוד מתבססת על מספר המופעים של כל אות בטקסט, לא קיים קוד אחד שנותן קידוד אופטימלי לכל טקסט, ולכן נדרשת הפעלה של האלגוריתם וגילויובניית הקוד המתאים עבור טקסט ספציפי.
 
מבחינה פורמלית, הקלט לבעיה הוא אוסף אותיות, <math>\ a_1,a_2,\dots,a_n</math>, ומספר הפעמים שכל אות מופיעה בטקסט: <math>\ c_1,c_2,\dots,c_n</math>.
שורה 30:
 
===תיאור האלגוריתם===
האלגוריתם של הופמןהאפמן הוא דוגמה ל[[אלגוריתם חמדן]]. הוא מבצע בכל שלב את הפעולה שנראית, נקודתית, כפעולה המשתלמת ביותר, ומתבסס על כך שפתרון אופטימלי עבור <math>\ n-1</math> אותיות יכול להפוך לפתרון אופטימלי עבור <math>\ n</math> אותיות.
 
הרעיון באלגוריתם הוא כזה: נבנה את העץ הבינארי של הקוד "מלמטה למעלה". ראשית, נמצא את שתי האותיות שמספר המופעים שלהם '''מינימלי''', וניצור צומת חדש, כך ששתי האותיות הללו יהיו בניו. כעת נתייחס לצומת החדש בתור אות חדשה, שמספר המופעים שלה הוא סכום מספרי המופעים של שתי האותיות שהן בניה. כך קיבלנו צמצום של הבעיה מבעיה ב-<math>\ n</math> אותיות לבעיה ב-<math>\ n-1</math> אותיות. נחזור על התהליך עד שנישאר עם צומת אחד בלבד - ראש העץ.
שורה 47:
 
==אופטימליות הקוד==
ניתן להוכיח כי קוד הופמןהאפמן מחזיר תמיד קידוד אופטימלי, מבין כל צפני הקידומתהתחיליות. באופן כללי יותר, קוד הופמןהאפמן נותן אורך ממוצע מינימלי של צופן בהשוואה לכל צפני החד-פענח (Uniquely Decodable). יש להיזהר בשימוש במילה "אופטימלי", שכן קיימים קידודים יעילים יותר במצבים מסוימים. האופטימליות של קוד הופמןהאפמן פירושה שהוא הקוד היעיל ביותר שבו מייצגים כל אות על ידי רצף קבוע של ביטים, כך שלכל אות בטקסט מותאם רצף שכזה.
 
הוכחת אופטימליות הקוד אינה מסובכת, ומתבססת על כך שבהינתן קוד אופטימלי כלשהו, ניתן לבנות ממנו קוד אופטימלי חדש על ידי כך שמעבירים את שתי האותיות בעלות מספר המופעים הנמוך ביותר למקום הנמוך ביותר בעץ הקוד. מכיוון שפעולה זו יכולה רק לשפר את עלות הקוד הכוללת, הקוד נותר אופטימלי. כך ניתן באינדוקציה לבנות קוד הופמןהאפמן מתוך כל קוד אופטימלי.
 
==קישורים חיצוניים==
אוחזר מתוך "https://he.wikipedia.org/wiki/קוד_האפמן"