ב-Online
 
 
 
 
 
 
 
 
קידוד הקסם של הופמן 

קידוד הקסם של הופמן

 
 
עידו גנדל

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

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

איך לכווץ טקסט

כפי שאתם בוודאי זוכרים, כל תו טקסט נשמר במחשב, לרוב, בבייט יחיד (8 ביטים). כיום, הודות לקודים כמו Unicode, מצב זה הולך ומשתנה – אך לצורך הנוחות נתמקד במקרה הפשוט. בייט יכול לשמור כל אחד מ-256 תווים שונים. אבל לכמה תווים אנחנו באמת זקוקים? קחו טקסט כלשהו בעברית: יש בו את 22 האותיות בתוספת 5 סופיות, עשר ספרות ועוד כמה סימני פיסוק ותווים מיוחדים. גם אם נתאמץ מאד לא נצליח, לרוב, למצוא יותר מ-64 תווים. כדי לשמור תו אחד מתוך 64 מספיקים 6 ביטים, כלומר ששניים מתוך שמונת הביטים שבייט ה"רגיל" מיותרים. כבר חסכנו 25%. אבל אולי אפשר לחסוך יותר?

כאן באה לעזרתנו עובדה נוספת – בטקסטים רגילים וארוכים מספיק, האותיות השונות מופיעות בשכיחות שונה. אותיות אהו"י נפוצות מאד בעברית, ואילו אותיות כמו ט' או צ' נדירות יחסית. להמחשה, נניח שיש לנו חנות עם דלפק שירות ומחסן צר וארוך, שמוכרת 22 מוצרים. חלק מהמוצרים פופולריים הרבה יותר מאחרים, אז הגיוני לאחסן אותם בחלק הקרוב של המחסן, כדי לחסוך התרוצצות. אם מישהו בא ומבקש פריט נדיר, המוכר אמנם יצטרך לרוץ עד לסוף המחסן, אבל בממוצע הוא עדיין יעבוד פחות קשה. "קידוד הופמן" (Huffman Coding), שהומצא על ידי הדוקטורנט דיוויד הופמן מ–MIT בשנת 1952, הוא אלגוריתם דחיסה מהיר ויעיל ש"מסדר את המחסן" בצורה נכונה עבור טקסטים, ומביא לכיווץ משמעותי.
 
 

קוד הופמן

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

ברד ירד בדרום ספרד

(18 תווים, כולל רווחים) ונספור כמה פעמים מופיע כל תו:
ב: 2
ר: 4
ד: 4
_: 3
י, ו, ם, ס, פ: 1

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

כדי להגיע לאות מסוימת בעץ שנוצר, מתחילים בצומת העליון ועוברים ימינה או שמאלה לפי הצורך, תוך צבירה של 0 ו-1 לאורך הנתיב. למשל, כדי להגיע לאות י', צריך ללכת שמאלה (1), ימינה (0), שמאלה (1) ושוב ימינה (0). כלומר הקוד של י' הוא 1010. הקוד של ד' הנפוצה, לעומת זאת, קצר הרבה יותר: ימינה ואז שמאלה, כלומר 01.
 
לסיום, נתרגם את המחרוזת כולה לקודי הופמן המתאימים:
 
 
המחרוזת החדשה היא בת 53 תווים, אך אלה הם רק אפסים ואחדים, ואפשר להמיר אותם לביטים – ואז המחרוזת הזאת תתפוס 7 בייטים בסך הכל, לעומת 18 במחרוזת המקורית. כמובן שצריך לאחסן איפשהו גם את המבנה של העץ עצמו, כך שבסופו של דבר הקוד אולי לא יהיה חסכוני עבור המחרוזת הספציפית הזאת. אבל כשעוברים לטקסטים ארוכים יותר, הכיווץ יכול להיות משמעותי מאד – עד כדי כך שווריאציות של קוד הופמן משמשות אפילו כיום בשיטות כיווץ נפוצות כמו jpeg, MP3 ועוד.
 

כיווץ הקסם

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

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

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

כל הזכויות שמורות 2011 © נענע 10 בע"מ
 
 
 
 
כל הזכויות שמורות © Nana10 בע"מ
Video powered by