כיצד פועלת דחיסת נתונים ללא אובדן | מגזין קוונטה

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

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

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

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

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

פאנו פתר את החלק הזה של הבעיה. הוא הבין שהוא יכול להשתמש בקודים באורכים שונים מבלי להזדקק לרווחים יקרים, כל עוד הוא מעולם לא השתמש באותה דפוס של ספרות גם בתור קוד שלם וגם בתור התחלה של קוד אחר. לדוגמה, אם האות S הייתה כל כך נפוצה בהודעה מסוימת עד ש-Fano הקצה לה את הקוד הקצר ביותר 01, אז שום אות אחרת בהודעה הזו לא הייתה מקודדת עם כל דבר שמתחיל ב-01; קודים כמו 010, 011 או 0101 יהיו כולם אסורים. כתוצאה מכך, ניתן היה לקרוא את ההודעה המקודדת משמאל לימין, ללא כל אי בהירות. לדוגמה, כאשר האות S מוקצית 01, האות A מוקצית 000, האות M מוקצית 001, והאות L מוקצית 1, פתאום ניתן לתרגם את ההודעה 0100100011 מיד למילה "קטן" למרות ש-L מיוצג על ידי אחד ספרה, S בשתי ספרות, ושאר האותיות בשלוש כל אחת.

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

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

התוצאה הייתה דחיסה יעילה להפליא. אבל זה היה רק ​​הערכה; אסטרטגיית דחיסה טובה יותר הייתה צריכה להתקיים. אז פאנו אתגר את תלמידיו למצוא אותו.

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

שקול הודעה שבה גישת פאנו מדשדשת. ב"חדר בית ספר", O מופיע ארבע פעמים, ו-S/C/H/L/R/M כל אחד מופיע פעם אחת. גישת האיזון של פאנו מתחילה בהקצאת ה-O ואות אחת נוספת לענף השמאלי, כאשר חמשת השימושים הכוללים באותיות אלו מאזנים את חמש ההופעות של האותיות הנותרות. ההודעה המתקבלת דורשת 27 סיביות.

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

טבלת התדרים המעודכנת שלו מציעה לו אז ארבע אפשרויות: ה-O המופיע ארבע פעמים, צומת ה-RM המשולב החדש שבו נעשה שימוש פונקציונלי פעמיים, והאותיות הבודדות S, C, H ו-L. האפמן שוב בוחר את שתי האפשרויות הפחות נפוצות, תואמות (נגיד) H עם ל.

התרשים מתעדכן שוב: ל-O עדיין יש משקל של 4, ל-RM ול-HL יש כעת משקל של 2 לכל אחד, והאותיות S ו-C עומדות בפני עצמו. האפמן ממשיך משם, בכל שלב מקבץ את שתי האפשרויות הפחות תכופות ולאחר מכן מעדכן גם את העץ וגם את טבלת התדירות.

בסופו של דבר, "חדר בית ספר" הופך ל-11101111110000110110000101, ומגלח קצת את גישת פאנו מלמעלה למטה.

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

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

לא רע לפרויקט שמונע במקור על ידי רצונו של סטודנט לתואר שני לדלג על מבחן גמר.