Question

spring_15_b
huffman

נתונה טבלת שכיחויות של טקסט TT באורך 100, מעל א"ב בן 6 אותיות:

abcdef30181716109 \begin{array}{|l|l|l|l|l|l|} \hline a&b&c&d&e&f \\\hline 30&18&17&16&10&9 \\\hline \end{array}

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

ב. כמה ביטים נדרשים לקודד את הטקסט כאשר הוא מקודד בקוד הופמן?

ג. נתון העץ הבא:

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

ד. הוכיחו/הפריכו: אם בטקסט מסויים השכיחות של האות aa היא 12\frac{1}{2}, אז מספר הביטים שמקודדים את aa בקוד הופמן עבור הטקסט הוא 1.

3

Answers

א. נצטרך 3 ביטים עבור כל תו, כלומר 300 ביטים בסך הכל.

ב. נבנה עץ הופמן:

ונקבל

2(30+18)+3(17+16+10+9)=2522 \cdot (30 + 18) + 3 \cdot (17 + 16 + 10 + 9) = 252

ג.

ד. נכון. נשים לב שכל עוד לא מאחדים את כל שאר התווים, תמיד קיים צומת בעץ עם שכיחות קטנה משל 12\frac{1}{2}, ולכן בכל בנייה של עץ הופמן עבור טקסט כזה, העלה שמתאים לתו aa הוא בן ישיר של שורש העץ.

1
Feedback