Question

huffman

הוכיחו/הפריכו את הטענות הבאות המתייחסות לעצי האפמן:

  1. אם כל תו מופיע בקובץ בתדירות קטנה מ-13\frac{1}{3} אזי בהכרח בעץ האפמן לא תהיה מילת קוד באורך 1.
  2. אם קיים תו שתדירותו גדולה מ-25\frac{2}{5} אזי מילת הקוד המתאימה לו בעץ האפמן הינה בהכרח מאורך 1.
  3. האורך הממוצע של מילת קוד בעץ האפמן הינו Ω(logn)\Omega(\log n) כאשר nn הינו מספר התווים.
1

Answers

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

אז התדירות של bb קטנה מ-13\frac{1}{3} זאת של cc גדולה מ-23\frac{2}{3} נניח בלי הגבלת הכלליות שהתדירות של dd גדולה מ-13\frac{1}{3} וקיבלנו סתירה, כי החלפה של הצומת dd עם bb מקטינה את משקל העץ.

2. לא נכון, למשל עבור א"ב בגודל 3 עם תדירויות 120,920,1020\frac{1}{20}, \frac{9}{20}, \frac{10}{20} בהתאמה.

3. לא נכון, בעץ האפמן "שרוכי"

חצי מהצמתים בעומק גדול מ-n4\frac{n}{4} ולכן האורך הממוצע של מילת קוד הוא לפחות n8\frac{n}{8}.

2
Feedback