האלגוריתם של הופמן משמש לדחיסה או קידוד של נתונים. בדרך כלל, כל תו בקובץ טקסט מאוחסן כשמונה סיביות (ספרות, או 0 או 1) המתמנות לאותו תו באמצעות קידוד בשם ASCII. קובץ המקודד בהפמן מפרק את המבנה הנוקשה של 8 סיביות כך שהדמויות הנפוצות ביותר נשמרות בכמה סיביות בלבד ('a' יכול להיות "10" או "1000" במקום ASCII, שהוא "01100001"). התווים הפחות נפוצים, אם כן, יתפסו לעתים קרובות הרבה יותר מ -8 סיביות ('z' עשוי להיות "00100011010"), אך מכיוון שהם מופיעים לעתים רחוקות כל כך, קידוד הופמן, בסך הכל, יוצר קובץ קטן בהרבה מהמקור.
צעדים
חלק 1 מתוך 2: קידוד
שלב 1. ספרו את התדירות של כל תו בקובץ שיש לקודד
כלול תו דמה לציון סוף הקובץ - זה יהיה חשוב בהמשך. לעת עתה, קראו לזה EOF (סוף הקובץ) וסמן אותו כבעל תדירות של 1.
לדוגמה, אם ברצונך לקודד קובץ טקסט שכתוב בו "ab ab cab", יהיה לך 'a' עם תדר 3, 'b' עם תדר 3 '' (רווח) עם תדר 2, 'c' בתדר 1 ו- EOF בתדירות 1
שלב 2. אחסן תווים כצמתים של עץ והכניס אותם לתור עדיפות
אתה תבנה עץ בינארי גדול עם כל תו כעלה, אז עליך לאחסן את התווים בפורמט כזה שהם יכולים להפוך לצמתים של העץ. מקם את הצמתים הללו בתור עדיפות עם תדירות כל תו כעדיפות הצומת שלו.
- עץ בינארי הוא פורמט נתונים שבו כל נתון הוא צומת שיכול להכיל עד הורה אחד ושני ילדים. לעתים קרובות הוא מצויר כעץ מסתעף, ומכאן שמו.
- תור הוא איסוף נתונים בשם המתאים בו הדבר הראשון שנכנס לתור הוא גם הדבר הראשון שיוצא (כמו המתנה בתור). בתור עדיפות הנתונים נשמרים לפי סדר העדיפויות שלהם, כך שהדבר הראשון שיצא הוא הדבר הדחוף ביותר, הדבר בעל עדיפות קטנה ביותר, ולא הדבר הראשון שנלקח.
- בדוגמה "ab ab cab", תור העדיפות שלך ייראה כך: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
שלב 3. התחל לבנות את העץ שלך
הסר (או הסר) את שני הדברים הדחופים ביותר מתור העדיפות. צור צומת עץ חדש שיהיה האב של שני הצמתים הללו, ושמור את הצומת הראשון כילד השמאלי שלו והשני כילד הימני שלו. עדיפות הצומת החדש צריכה להיות סכום סדרי העדיפויות של הילד שלו. לאחר מכן העניק לצומת החדש הזה תור בתור העדיפות.
תור העדיפות נראה כעת כך: {'': 2, צומת חדש: 2, 'a': 3, 'b': 3}
שלב 4. סיים את בניית העץ שלך:
חזור על השלב לעיל עד שיש רק צומת אחד בתור. שים לב שבנוסף לצמתים שיצרת לדמויות ולתדירות שלהם, אתה גם תתנתק, יהפוך לעצים ותעמיק מחדש צמתים, צמתים שהם כבר עצים בעצמם.
- כשתסיים, הצומת האחרון בתור יהיה השורש של עץ הקידוד, כאשר כל שאר הצמתים מסתעפים ממנו.
- התווים הנפוצים ביותר יהיו העלים הקרובים ביותר לחלק העליון של העץ, בעוד שהתווים הנמצאים בשימוש לעתים רחוקות ימוקמו בתחתית העץ, רחוק יותר מהשורש.
שלב 5. צור מפת קידוד. ללכת בין העץ כדי להגיע לכל דמות. בכל פעם שאתה מבקר בילד השמאלי של הצומת, זהו '0'. בכל פעם שאתה מבקר את הילד הנכון של הצומת, זה '1'. כאשר אתה מגיע לדמות, אחסן את הדמות עם רצף ה -0 ו -1 הנדרש כדי להגיע לשם. רצף זה הוא מה שהדמות תהיה מקודדת כמו בקובץ הדחוס. אחסן את הדמויות והרצפים שלהן במפה.
- לדוגמה, התחל מהשורש. בקר בילד השמאלי של השורש, ולאחר מכן בקר בילד השמאלי של הצומת ההוא. מכיוון שלצומת שאתה נמצא בה כעת אין ילדים, הגעת לדמות. זה ' '. מכיוון שהלכת פעמיים שמאלה כדי להגיע לכאן, הקידוד עבור '' הוא "00".
- עבור עץ זה המפה תיראה כך: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
שלב 6. בקובץ הפלט, כלול את מפת הקידוד ככותרת
זה יאפשר לפענח את הקובץ.
שלב 7. קידוד הקובץ
עבור כל תו בקובץ שיש לקודד, כתוב את הרצף הבינארי ששמרת במפה. לאחר שסיימת לקודד את הקובץ, הקפד להוסיף את ה- EOF עד הסוף.
- עבור הקובץ "ab ab cab", הקובץ המקודד ייראה כך: "1011001011000101011011".
- קבצים מאוחסנים כבייטים (8 סיביות או 8 ספרות בינאריות). מכיוון שאלגוריתם הקידמן הופמן אינו משתמש בפורמט 8 סיביות, לרוב לא יהיו לקבצים המקודדים אורכים שהם כפולים של 8. הספרות הנותרות ימולאו ב- 0s. במקרה זה יתווספו שני 0s בסוף הקובץ, שנראה כמו רווח אחר. זו עלולה להיות בעיה: כיצד ידע המפענח מתי להפסיק לקרוא? עם זאת, מכיוון שכללנו תו סוף הקובץ, המפענח יגיע לזה ואז יפסיק, תוך התעלמות מכל דבר אחר שהתווסף לאחר מכן.
חלק 2 מתוך 2: פענוח
שלב 1. קרא בקובץ המקודד של האפמן
ראשית, קרא את הכותרת, שאמורה להיות מפת הקידוד. השתמש בזה לבניית עץ פענוח באותו אופן שבו בנית את העץ בו השתמשת כדי לקודד את הקובץ. שני העצים צריכים להיות זהים.
שלב 2. קראו ספרה בינארית אחת בכל פעם
חצו את העץ בזמן שאתם קוראים: אם אתם קוראים ב- '0', עבור אל הילד השמאלי של הצומת שאתה נמצא בו, ואם אתה קורא ב- '1', עבור אל הילד הנכון. כאשר אתה מגיע לעלה (צומת ללא ילדים), הגעת לדמות. כתוב את הדמות בקובץ המפענח.
בגלל האופן שבו התווים מאוחסנים בעץ, לקודים לכל תו יש מאפיין קידומת, כך ששום קידוד בינארי של תו לא יכול להתרחש בתחילת הקידוד של תו אחר. הקידוד לכל דמות הוא ייחודי לחלוטין. זה הופך את הפענוח לקל בהרבה
שלב 3. חזור על הפעולה עד שתגיע ל- EOF
מזל טוב! פענחת את הקובץ.
