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