Hit enter after type your search item

קידוד האפמן

/
/
/
193 Views

המוטיבציה

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

האלגוריתם

האלגוריתם מורכב מקריאת הקובץ, בניית עץ, קידוד הקובץ ופענוח הקובץ.

קורא את הקובץ

ראשית, התוכנית מייצרת מערך של כל הערכים האפשריים בקובץ. בקובץ טקסט, אלו יהיו 128 תווי ASCII האפשריים. ב-JPG, זה יהיה הצבעים הזמינים השונים. כשהתוכנית קוראת את ה-fille, היא מגדילה את המיקום המתאים במערך. בסוף הקריאה בקובץ, המערך הוא ספירה של מספר הפעמים שכל ערך התרחש בקובץ. לדוגמה, לאחר קריאת הקובץ “איש בננה” המערך ייראה בערך כך:

מַעֲרָך[ ] = 1, [array[a] = 4, מערך[b] = 1, מערך[n] = 3, מערך[m] = 1, עם כל שאר הערכים 0

בונים עץ

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

התוכנית מתחילה לבנות את העץ על ידי יצירת עלה האפמן אחד עבור כל ערך במערך, מילוי הספירה עם הערך מהמערך והערך של האפמן עלה מאותו ערך במערך. אם נמשיך בדוגמה הקודמת של “איש הבננה”, נקבל 128 עלים, שלרובם יש ספירה של אפס. רק העלים המתאימים ל-SPACE, a, b, n ו-m אינם אפס.

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

צומת ההאפמן הזה הוא השורש של עץ ההאפמן שלנו.

קידוד הקובץ

התוכנית צריכה להשתמש ב-Huffman Tree כדי לקודד את הקובץ. כדי לעשות זאת, הוא צועד במורד העץ, לוקח שבילים שמאלה או ימינה כאשר הוא זמין. תוך כדי, הוא עוקב אחר הנתיב שנלקח עם 0 לשמאל ו-1 לימין. כאשר הוא מגיע לעלה, הוא שומר את הנתיב שנלקח כדי להגיע לעלה זה בתור הקידוד של הדמות באותו עלה. לכן, אם התוכנה עברה שמאלה, ימינה, ימינה, שמאלה, שמאלה כדי להגיע לתו ‘h’, הקידוד עבור h יהיה 01100. ברגע שיש לה את הקידוד עבור כל התווים, התוכנית מתחילה לכתוב לקובץ החדש . עליו לשמור תחילה את האפמן עץ, מכיוון שלכל קובץ יש עץ האפמן אחר. לאחר מכן, עבור כל תו בקובץ הישן, הוא מחפש אותו ברשימת הקידוד וכותב את הקידוד הזה לקובץ החדש.

פענוח הקובץ

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

הסבר

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

קידוד האפמן הוא חסר הפסד

מכיוון שהנתונים משוחזרים לחלוטין, ללא שגיאות, Huffman Coding נחשב ללא אובדן.

יישומים

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



Source by Daniel Obenshain

Leave a Comment

E-posta hesabınız yayımlanmayacak.

This div height required for enabling the sticky sidebar
Copyright at 2022. www.sitewebstats.com All Rights Reserved