דיון מכווץ בצורה שבה עצי סיומות עוזרים לכיווץ

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

נוסטלגיה.

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

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

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

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

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

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

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

אוהבים להביא את השפה האנגלית כדוגמה. כל מי שמעיף מבט בטקסט סטנדרטי באנגלית יראה חיש קל מספר תבניות פשוטות - למשל, אחרי q יבוא כמעט תמיד u, כך שאפשר פשוט לוותר על ה-u ולציין במפורש את המקרים שבהם הוא נעדר. יש גם סיומות שנוהגות לחזור לעתים קרובות - tion, למשל. אפשר להחליף את ארבעת התווים הללו בתו מוסכם מיוחד, וכן הלאה. עוד מקום שבו אפשר לחסוך הוא במספר הביטים שנדרשים כדי לייצג כל אות; הזכרתי את קוד ASCII בפוסט שעבר - בקוד זה, כל תו מיוצג באמצעות שמונה ביטים. האם לא ניתן “לחסוך”? להשתמש בביט אחד עבור האות הנפוצה e, בשניים עבור אותיות נפוצות כמו a ו-i, וכן הלאה, תוך שאנחנו “משלמים” בכך שתווים “נפוצים” כמו z ידרשו, למשל, שבעה עשר ביטים? התשובה היא שאפשר - הרעיון נחקר היטב ונמצאה תוצאה אופטימלית - במובן מסויים ומוגדר מאוד - שנקראת קוד הופמן וראויה לפוסט משל עצמה. אני אתמקד כאן בשיטות האופטימיזציה הקודמות, של “להחליף תבנית שמופיעה כמה פעמים במזהה פשוט יותר”.

ובכן, איך עושים את זה? שיטה אחת - לבנות טבלה שמכילה מחרוזות נפוצות כמו tion, בתוספת סימן מזהה מוסכם לכל אחת מהן, ואז לעבור על הטקסט ולהחליף כל מופע של המחרוזות הללו במזהה המוסכם. אם הן מופיעות הרבה פעמים, והמזהה והטבלה לוקחים מעט מקום, בוודאי שנצא ברווח כלשהו. אלא שהשיטה הזו היא נאיבית למדי - איך בדיוק מחליטים על המחרוזות שיהיו בטבלה מראש? ואם הטקסט שמכווצים נכתב בסגנון מסויים, או מאחסן מידע מסויים, שבו המחרוזות הללו מופיעות מעט מאוד, אם בכלל? בקיצור, לא הגיוני לבנות את הטבלה מראש; מה שצריך לעשות הוא לבנות אותה תוך כדי תהליך הכיווץ, על ידי שימוש בטקסט שמכווצים בעצמו. יתר על כן, אין צורך של ממש בטבלה חיצונית. הבה ונתבונן בדוגמה הבאה. נניח שאני מכווץ את המשפט “The Enemy of my Enemy is still my Enemy”. כיווץ אפשרי של המשפט הוא זה:

" The Enemy of my (3,5) is still (6,2) (3,5)"

הביטו רגע במחרוזת ה”מכווצת” ונסו לנחש מה עשיתי.

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

אם כן, מה עושים מבחינה פורמלית? התיאור אינו מסובך. ראשית, אם המחרוזת שלנו מסומנת ב-S, נוח לסמן תת מחרוזות שלה בתור \( S[i..j] \)- זוהי תת המחרוזת שמתחילה ב-i ומסתיימת ב-j, כולל התו שבמיקום j (יש שפות תכנות - למשל, רובי - שבהן כך אכן מסמנים תת מחרוזות).כעת, נניח שכיווצנו את כל המחרוזת עד למקום ה-i, ושאורך המחרוזת הכולל הוא n, כלומר נותר לכווץ את \( S[i..n] \). אנו מסתכלים על מה שכבר כיווצנו - \( S[1..i-1] \) ושואלים את עצמנו - האם בתוך החלק הזה נצליח למצוא תת מחרוזת שזהה לרישא של \( S[i..n] \), כלומר, האם אפשר להחליף את התווים הבאים שאנו רוצים לדחוס בקישור לתוך \( S[1..i-1] \)?

לצור ך כך מגדירים שני מספרים - \( s_i,l_i \), כאשר \( s_i \) מציין את המיקום בתוך \( S[1..i-1] \) שבו מתחילה מחרוזת שנמצאת כולה בתוך \( S[1..i-1] \), ומזדהה עם רישא של \( S[i..n] \). את האורך שלה מסמנים בתור \( l_i \).כעת, אפשר להחליף את כל \( l_i \) התווים הראשונים של \( S[i..n] \) בסימון \( (s_i,l_i) \).

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

הנה מה שקורה כאשר אני מכווץ את מחרוזת הדוגמה שלי, בהנחה שלא היו לי שגיאות בקוד שחישב את הכיווץ:

"The En(2,1)my(3,1)of(3,1)(7,3)(4,6)is(3,1)(23,1)t(22,1)l(28,1)(12,9)"

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

נשארת רק השאלה המהותית, שהיא קריטית כאשר רוצים לכתוב יישומי כיווץ מעשיים - איך אפשר לחשב את הזוג \( s_i,l_i \) לכל מיקום במחרוזת ביעילות? התשובה, כמובן (אחרת בשביל מה הפוסט הזה?) היא שעצי סיומות הם הכלי המושלם לכך בזכות יכולת החיפוש המהירה שהם מספקים, שהצגתי בפוסט הקודם. כדי למצוא את הרישא של \( S[i..n] \) פשוט מתחילים לטייל על העץ על פי התווים של הרישא (תוך שנזהרים לא לחרוג מהתחום \( S[1..i-1] \) - כאב ראש בפני עצמו) עד שכבר אין לאן להמשיך - כלומר, הגענו לקצה הרישא המשותפת.

כשהטיול מסתיים, נמצא את עצמנו בתוך צומת פנימי של העץ. כדי להבין מה זה אומר, צריך להיזכר מה כל צומת מייצג - רישא של סיפות של S (אולי כמה סיפות שונות שחולקות את אותה הרישא), כשהעלים מייצגים סיפות שלמות. זו הסיבה שבגללה לא נוכל אף פעם להגיע לעלה בטיול שלנו - אנחנו מחפשים תת מחרוזות של \( S[1..i-1] \), כלומר כאלו שאינן מגיעות לסוף המחרוזת. את \( l_i \) אנחנו יודעים בקלות - פשוט סופרים כמה אותיות מהרישא של \( S[i..n] \) ראינו במהלך הטיול. לעומת זאת, \( s_i \) הוא לכאורה טריקי יותר. איך יודעים, בהינתן צומת, מה המיקומים בתוך S שבהם מתחילות הסיפות שאת הרישא שלהן הצומת מייצג?

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

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

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