קודי Huffman: דוגמאות, יישומים

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

היסטוריה של האלגוריתם

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

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

העיקרון של קידוד יעיל

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

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

הקוד של הופמן, לדוגמה

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

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

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

אלגוריתם לבניית עץ על פי הופמן

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

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

שיפור יעילות דחיסה

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

האצת תהליך הדחיסה

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

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

מסקנה

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

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