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

איך מחשבים דוחסים טקסט  © Tom Scott.

איך מחשבים שומרים טקסט

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

הדחיסה

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

קידוד הופמן (Huffman Coding)

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

כך זה עובד:

• סופרים כמה פעמים כל תו מופיע בטקסט.

• בונים “עץ הופמן” שמחבר כל פעם את שני התווים הכי נדירים.

• מהעץ מתקבל קוד בינארי ייחודי לכל תו. אף קוד אינו התחלה של קוד אחר ולכן אין בלבול בפענוח.

• תווים נפוצים מקבלים קודים קצרים, נדירים מקבלים קודים ארוכים יותר.

לדוגמה, מילות השיר Wild Wild West של ויל סמית’ נדחסו מכ-30,000 ביטים לכ-20,000 ביטים. זה חיסכון של כ-30%. צריך לשמור את עץ הקידוד עצמו ולכן זה פחות משתלם לטקסטים קצרים. מצד שני, זה משתלם מאוד לטקסטים גדולים.

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

צפו בסרטון מערוץ היוטיוב של © Tom Scott.

תרגום לעברית: Ofek Zeevi

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

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

כדי להישאר מעודכנים בתכנים חדשים הצטרפו לדף הפייסבוק שלנו