קוד הופמן

Poll without page-refresh

Article on other languages:

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

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

מבוא

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

נמחיש את יעילותה של גישה זו באמצעות דוגמה פשוטה. נניח שנתונה מחרוזת בת 200 תווים, שמחציתם האות א. בקוד ASCII, שבו לכל תו מוקדשות 8 סיביות, אורכה של מחרוזת זו הוא 1,600 סיביות. נקודד כעת את התווים בדרך חדשה: האות א תסומן בסיבית יחידה שערכה 0, וכל תו אחר יסומן בקוד ה-ASCII הרגיל שלו, שבתחילתו תתוסף הסיבית 1 (תוספת זו הכרחית, כדי שנוכל להבדיל בין סיבית 0 שמציינת את האות א, ובין סיבית 0 באמצע תו כלשהו). אורך המחרוזת בקוד זה הוא 1,000 סיביות בלבד, שהם 63% מאורך המחרוזת המקורית.

היסטוריה

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

תיאור פורמלי

תיאור הקוד

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

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

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

תיאור הבעיה

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

מבחינה פורמלית, הקלט לבעיה הוא אוסף אותיות, $\ a_1,a_2,\dots,a_n$ , ומספר הפעמים שכל אות מופיעה בטקסט: $\ c_1,c_2,\dots,c_n$ .

הפלט הצפוי הוא קוד, שהוא אוסף $\ h_1,h_2,\dots,h_n$ של מילים בינאריות. נסמן $\ |h_k|$ את אורכה של המילה ה- $\ k$ .

היעד הוא שהקוד שיוחזר יהיה כזה כך ש- $\ \sum_{k=1}^n c_k\cdot|h_k|$ יהיה מינימלי. הסכום הוא בדיוק מספר הביטים שנדרש לקידוד הטקסט כולו, שכן עבור כל אות, אנו מכפילים את מספר המופעים שלה בטקסט במספר הביטים שנדרשים כדי לייצג אותה.

תיאור האלגוריתם

האלגוריתם של הופמן הוא דוגמה לאלגוריתם חמדן. הוא מבצע בכל שלב את הפעולה שנראית, נקודתית, כפעולה המשתלמת ביותר, ומתבסס על כך שפתרון אופטימלי עבור $\ n-1$ אותיות יכול להפוך לפתרון אופטימלי עבור $\ n$ אותיות.

הרעיון באלגוריתם הוא כזה: נבנה את העץ הבינארי של הקוד "מלמטה למעלה". ראשית, נמצא את שתי האותיות שמספר המופעים שלהם מינימלי, וניצור צומת חדש, כך ששתי האותיות הללו יהיו בניו. כעת נתייחס לצומת החדש בתור אות חדשה, שמספר המופעים שלה הוא סכום מספרי המופעים של שתי האותיות שהן בניה. כך קיבלנו צמצום של הבעיה מבעיה ב- $\ n$ אותיות לבעיה ב- $\ n-1$ אותיות. נחזור על התהליך עד שנישאר עם צומת אחד בלבד - ראש העץ.

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

מבחינה פורמלית:

צור תור עדיפויות $\ Q$ שיכיל צמתים המייצגים את כל אותיות, ממויינות על פי מספר המופעים, מהקטן לגדול.
כל עוד בתור העדיפויות יש יותר מצומת אחד, בצע:
1. צור צומת חדש, $\ z$ .
2. הוצא מתור העדיפויות את שני האיברים העליונים, $\ x,y$ .
3. הפוך את $\ x,y$ לבנים הימני והשמאלי של $\ z$ .
4. קבע את מספר המופעים של $\ z$ להיות סכום מספרי המופעים של $\ x$ ו- $\ y$ .
5. הכנס את $\ z$ לתור העדיפויות.
הצומת הבודד שנותר בתור העדיפויות הוא שורש עץ הקוד המבוקש.

דוגמה לעץ הופמן

האותיות הבאות מופעות במחרוזת כמספר הפעמים המצוינים לייד כל אות:

a - 10
b - 15
c - 30
d - 16
e - 29

סך הכול אותיות- 100.
התרשים הבא מתאר את העץ במקרה הנ"ל:
בתרשים כל צומת מחולק לשניים, החלק השמאלי מציין את האות עצמה, והחלק הימני מציין את מספר הפעמים שהאות מופיעה.
במקום שבו החלק השמאלי אדום, זהו צומת שנוצר, והחלק הימני שלו מציין את סכום מספר ההופעות של שני בניו. הצמתים הללו מתווספים לרשימת האותיות.
לאחר שימוש באות מסוימת כבן של צומת חדש שנוצר, יש למחוק אותה מרשימת האותיות.
ענף שמאל תמיד יהיה אפס, וענף ימין תמיד יהיה אחד. כל אות תיוצג על ידי הענפים שדרכם צריך לעבור כדי להגיע אליה. לדוגמה: כדי להגיע לאות b יש ללכת פעמיים שמאלה ופעם אחת ימינה, ולכן האות b תיוצג כ-001.
בכחול מסומנות התוצאות הסופיות של כל אחת מהאותיות.

אופטימליות הקוד

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

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

קישורים חיצוניים

איתן, אנימציית פלש המתארת את פעולת האלגוריתם, www.eitan.ac.il

מקור: http://he.wikipedia.org/wiki/%D7%A7%D7%95%D7%93_%D7%94%D7%95%D7%A4%D7%9E%D7%9F

קטגוריות: קידוד נתונים | אלגוריתמים | דחיסת נתונים

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.

Giant Panda

Mercedes Car

This site monitored by SitePinger.net