Prefix Code - Huffman Code

קודי-הפמן שימושיים מאוד וטכניקה אפיקטיבית לדחיסת מידע , שחוסכת 90% − 20% בד"כ , תלוי במאפייני המידע שצריכים לדחוס . נסתכל על המידע כסדרה של אותיות , האלגוריתם החמדן $Huffman$ משתמש בטבלה של תדיריות עבור כל אות לבנות דרך אופטימלית לייצג את את האותיות כמחרוזת בינארית .

נגדיר קוד בינארי חוקי לא״ב $\mathrm{\Sigma }$ כפונקצייה $c:\mathrm{\Sigma }\to \{0,1{\}}^{+}$ כך שהתכונות הבאות מתקיימות

1. חח״ע $c(\sigma )=c({\sigma }^{\prime })\leftrightarrow \sigma ={\sigma }^{\prime }$
2. שרשור של ביטים יכול לייצר רק שרשור אחד של תווים מהא״ב.

דוגמה טובה לכך היא ASCII שבו כל תו משתמש ב 8 ביטים ולכן יש לכלהיותר $2^8$ תווים אפשריים ויש רק דרך אחת לקודד כל תו. באופן כללי, תמיד קיים קוד בינארי לא״ב כלשהו כך שאורך כל קידוד הוא $\lceil \log |\mathrm{\Sigma }|\rceil$ .

דוגמה לקוד שלא מקיים את התכונה השנייה היא $0001110001$ עבור הקידוד :

באופן הזה נקבל ש $aaadddaaad$ ו $aabcaab$ יקודדו לאותה מחרוזת בינארית.

prefix-free code

קוד תחילי עבור $\mathrm{\Sigma }$ א״ב הוא פונקצייה $c:\mathrm{\Sigma }\to \{0,1{\}}^{+}$ כך ש:

1. חח״ע
2. לכל שתי תווים שונים בא״ב יתקיים שהפעלת c על אחד מהם היא לא רישא של השני ולהיפך

בטבלה הראשונה c(d) הוא רישא של c(c) וכאן זה תרחיש שלא יתקיים.

prefix-free tree

נוכל להתייחס ל prefix-free code כעץ בינארי באופן הבא:

1. התווים הם עלים
2. הבן השמאלי משוייך ל 0 והימני ל 1
3. $c(\sigma )$ הוא שרשור של הביטים מהשורש לעלה.

למשל עבור הטבלה למעלה העץ ייראה כך

נסמן: $d_T(\sigma )$ את העומק של $\sigma$ ב עץ $T$ שמייצג קוד תחיליות $c$ . יתקיים:

(הסימון מייצג את מספר האיברים במחרוזת הבינארית)ֿ

optimal prefix-free code

נניח שיש לנו קובץ מאוד גדול ואנחנו רוצים לקודד את האותיות בקובץ על ידי שימוש ב prefix-free code שמביאה את ההגודל הקובץ המקודד למינימום.
נסמן את קבוצת האותיות בקובץ ב $\mathrm{\Sigma }$ ונסמן לכל $\sigma \in \mathrm{\Sigma }$ את $f_{\sigma }$ שזה מספר הפעמים שהתו מופיע בקובץ.
אם נשתמש בקוד תחילי $c$ עם עץ $T$ אז הגודל הכולל לקובץ אחרי קידוד יהיה :

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

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

נרצה להגיע למצב הבא

השאלה היא איך מגיעים למצב כזה?

כיוון אינטואיטיבי היה למיין את כל התווים לפי התדירות ולכל ${\alpha }_i$ שזה התו בדירוג ה $i$ להגדיר שקוד שלו יהיה $\underset{\text{i times}}{\underbrace{111\dots 1}}0$ ככה נבטיח שהתו עם הקידוד ה $i$ יהיה בעומק ה $i$ בעץ. עם זאת, זה לא פתרון אופטימלי למשל עבור הקידוד הנ״ל

העץ השמאלי הוא הרגיל והעץ הימני הוא האופטמילי וזה בניגוד לאינטואיצייה שתיארתי למעלה שהייתה נותנת עץ אחר.

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

למה
עץ קוד תחילי אופטימלי לא מכיל קודקוד פנימי עם ילד אחד, כלומר הוא עץ שלם
נניח בשלילה שלעץ תחילי אופטימלי $T$ ישנו קודקוד פנימי $k$ עם ילד אחד $x$. נזכיר רק שקודקוד פנימי לא משוייך לאף תו ולכן מחיקה שלו לא אמורה להשפיע על מספר התווים בקידוד אלא רק על אורך של קידוד כלשהו.
לפי אלגוריתם מחיקה מעץ בינארי , זאת מחיקה די פשוטה שכל מה שהיא עושה זה להקטין את עומק הילד , במקרה הזה $x$, ב1. נעשה זאת ונסתכל על אחד העלים ש $x$ הוא חלק מהמסלול שלו נסמנו $m$ ואת $T^{\prime }$ כעץ המתקבל מהפעולה הזאת

בסתירה לכך ש $T$ עץ קוד תחילי אופטימלי.

בניית Huffman code

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

HUFFMAN(E)
	n = |E|
	Q = E
	for i=1 to n-1
		do allocate a new node z
			z.left = x = GET-MIN(Q)
			z.right = y = GET-MIN(Q)
			f[z]= f[x]ִ+f[y]
			INSERT(Q,z)
	return GET-MIN(Q)

אם $x,y$ הם התווים עם התדירות הנמוכה ביותר נגדיר $z\notin \mathrm{\Sigma }$ כך שהוא יהיה אבא של $x,y$ בעץ עם תדירות : $f_z=f_x+f_y$ וכעת ממשיכים לעבוד על ה א״ב ${\mathrm{\Sigma }}^{\prime }=\mathrm{\Sigma }\cup \{z\}\text{/}\{y,x\}$ .
האלגוריתם בונה עץ חילי אופטימלי בשיטת bottom-up, כלומר קודם כל בונים את העלים ועולים למעלה לשורש.
מתחילים בא״ב בגודל $n$ וכל פעם ממזגים באופן שתיארנו למעלה וכך מקטינים את $n$ ב אחד כל פעם עד שמגיעים לשורש.
$Q$ זאת בעצם ערימת מינימום בינארית לפי יחס סדר על התדירויות כך שבכל איטרציה מבצעים את המיזוג המתואר למעלה ומכניסים את $z$ לערימה ובריקרוסיה הולכים ל א״ב בלי x,y אבל כם עם z . ככה מבצעים $n-1$ איטרציות עד שנשאר קודקוד אחד, השורש של העץ, הוא זה שחוזר גם בשורה האחרונה.

דוגמת הרצה עבור

זמן הריצה עבור $|\mathrm{\Sigma }|=n$ קבוצת האותיות: אתחול ערימה בינארית עם $n$ קודקודים הוא ב $O(n)$ והלולאה מבוצעת $n-1$ פעמים כאשר כל פעם שולפים את שתי המינימום ב $\log n$ וסך הכל זמן הריצה יהיה $O(n\log n)$.

הוכחת נכונות

תכונת הבחירה החמדנית

קודם כל נבין מהי הבחירה החמדנית שעשינו כאן, עבור א״ב $\mathrm{\Sigma }$ בגודל לפחות 2 ולכל אות $\sigma$ מוגדרת התדירות $f_{\sigma }$ , אזי עבור $x,y\in \mathrm{\Sigma }$ שתי האותיות עם התדירות הנמוכה ביותר קיים עץ קוד תחילי אופטימלי כאשר $x,y$ הם עלים אחים והם העמוקים ביותר בעץ.

הוכחה:
יהי עץ קוד תחילי אופטימלי $T$ עבור $\mathrm{\Sigma }$ והתדירויות הנכונות. ניקח את העלה העמוק ביותר בעץ נמסנו $a$ . כיוון ש $T$ אופטימלי, לאבא של $a$ יש ילד נוסף והבן הזה חייב להיות על גם הוא (אחרת $a$ הוא לא העמוק ביותר בעץ). נסמן את האח $b$ ונשים לב שהוא גם העלה הנמוך ביותר בעץ.
בעץ $T$ אנחנו יודעים ש $x,y$ הם עדיין עלים איפה שהוא בעץ ויתקיים

(זה עניין סמנטי בלבד כי אנחנו ל יודעים את המיקומים של $x,y$ בעץ אלא רק שהם יותר ״גבוהים״ מהעלים הנמוכים ביותר, כמו כן האפשרות שהם שווים לא נשללת בא״שׁ הזה).
כעת נתבונן בעץ שבו מחליפים את $x$ עם $a$ ואת $y$ עם $b$ (בלי הגבלת הכלליות) ונסמן את העץ החדש $T^{\prime }$

כלומר

ולכן

נשים לב שהגורמים היחידים שלא יצטצמטו הם ההחלפות שעשינו ולכן

נשים לב שכל הביטויים האלה גדולים מ 0 ולכן קיבלנו שההפרשת בין העלויות של העצים גדול מ 0 כלומר העלות של $T$ גבוהה או שווה מהעלות של $T^{\prime }$ אבל $T^{\prime }$ עץ אופטימלי ולכן היא לא יכולה להיות גבוהה יותר כלומר

כלומר גם $T$ הוא עץ אופטימלי.

תת המבנה האופטימלי

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

יהי $\mathrm{\Sigma }$ א״ב מגודל לפחות 2, כאשר לכל תו מוגדרת התדירות המתאימה לו. אם ניקח $x,y\in \mathrm{\Sigma }$ שתי התווים עם התדירות הנמוכה ביותר ונגדיר איתם $z\notin \mathrm{\Sigma }$ שיקיים
$f_z=f_x+f_y$ ונבנה עץ $T^{\prime }$ אופטימלי עבור ${\mathrm{\Sigma }}^{\prime }=E\cup \{z\}-\{x,y\}$ אזי : העץ $T$ המתקבל מ $T^{\prime }$ על ידי הוספת $x,y$ כבנים של $z$ הוא עץ קוד תחילי אופטימלי עבור $\mathrm{\Sigma }$ .

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

נשים לב ש $d_T(x)=d_{T^{}}(y)=d_{T^{\prime }}(z)+1$ וגם ${\mathrm{\forall }}_{\sigma \ne x,y\in \mathrm{\Sigma }}:d_T(\sigma )=d_{T^{\prime }}(\sigma )$ זאת בגלל שבכלל לא נגענו בהם. סך הכל נקבל

כלומר קיבלנו

כעת, ניקח $\bar{T}$ עץ תחילי אופטימלי עבור $\mathrm{\Sigma }$. ע״י למת הבחירה החמדנית, נניח בלי הגבלת הכלליות ש $x,y$ אחים ב $\bar{T}$ .
ניקח ${\bar{T}}^{\prime }$ עץ קוד תחילי המתקבל מ $\bar{T}$ על ידי החלפת $x,y$ וקודקוד האבא שלהם בעלה חדש $z$ .

מההגדרה יתקיים ש ${\bar{T}}^{\prime }$ עץ קוד תחילי עבור ${\mathrm{\Sigma }}^{\prime }$ . כמו כן, מההוכחה הקודמת ניתן לראות ש $COST(\bar{T})=COST({\bar{T}}^{\prime })+f_z$ .
סך הכל מכל העצים שבנינו יתקיים

אבל

זה נכון בגלל ש$T^{\prime }$ אופטימלי. כלומר קיבלנו שיוויון ולכן $T$ אופטימלי. מה שעשינו כאן בעצם זה השתמשנו בעץ תחילי אופטימלי שמקיים את תכונת הבחירה החמדנית והראנו שהעלות שלו שקולה לעץ שמתקבל מהבנייה הריקורסיבית שעשינו. כלומר הראנו שהצעד החמדני אכן מביא אותנו לפתרון אופטימלי באופן ריקורסיבי. השלב הראשון היה למצוא את הקשר בין העלויות, לאחר מכן הראנו שאם עושים את זה על עץ שמקיים את למת הבחירה החמדנית אז הוא עץ תחילי אופטימלי.