איך לתרגל שאלות קידוד האפמן במבוא למדעי המחשב?

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

כמה שאלות קידוד האפמן יש במבוא למדעי המחשב?

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

מה חשוב לדעת על קידוד האפמן לקראת מבחן במבוא למדעי המחשב?

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

מבוא למדעי המחשב - קידוד האפמן

תכנות, רקורסיה, מערכים, מחרוזות, עצים בינאריים ורשימות מקושרות

סטטיסטיקות מבחנים

רמת קושי:

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

{a, b, c, d, e, f}

בלבד. אין לעשות שימוש בתווים נוספים בכל השאלה.

לאורך השאלה אנו נעשה שימוש בקידוד האפמן המתואר לפי העץ הבא: השורש מוביל לתת-עץ שמאלי וצומת

f

ימני. תת-העץ השמאלי מוביל לתת-עץ נוסף שמכיל את האיברים

a, b, c

(כש-

a

מקודד

0000

ו-

c

מקודד

001

), ולתת-עץ ימני שמכיל את

d

(מקודד עם

010

) ו-

e

(מקודד עם

011

). כלומר:

$h u f f (a) = 0000$
$h u f f (b) = 0001$
$h u f f (c) = 001$
$h u f f (d) = 010$
$h u f f (e) = 011$
$h u f f (f) = 1$

סעיף א (8 נק'). בסעיף זה אנו מתייחסים לקורפוס שממנו יכול להיווצר עץ ההאפמן המופיע מעלה.

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

2. נתון קורפוס כלשהו אשר יכול לייצר את העץ. נסמן ב-

w (x)

את כמות המופעים של תו

x

בקורפוס, עבור כל אחד מהתווים

f, e, d, c, b, a

בקורפוס (כאשר כל תו מופיע בקורפוס לפחות פעם אחת). עבור כל אחד מהתנאים הבאים, הקיפו האם הוא בהכרח מתקיים, או שלא ניתן לדעת:

$w (a) + w (b) \leq w (d)$
$w (d) + w (e) \geq w (c)$
$w (a) + w (b) + w (c) > w (f)$

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

a sc ii

לשמירת תווים בודדים באופן הבא: במקום לקודד תו בודד

x

ע"י

"0" + a sc ii (x)

, כאשר

a sc ii (x)

הוא קידוד

a sc ii

באמצעות 7 ביטים, אנו נקודד תו בודד

x

ע"י

"0" + h u f f (x)

, כאשר

h u f f (x)

הוא קידוד האפמן באמצעות העץ המתואר בתחילת השאלה.

בנוסף, בשונה מהכיתה, אנו נעשה שימוש ב-5 ביטים לתיאור מרחק החזרה, ו-3 ביטים לתיאור לאורך החזרה, כך שחזרה מתוארת ע"י 9 ביטים באופן הבא:

"1" + bin (ba c k) + bin (r e p)

(כאשר

bin

מחזיר את הייצוג הבינארי ללא הקידומת

0 b

). תיאור חזרה באורך 3 שמתחילה 5 תווים אחורה יהיה:

"100101011"

.

לבסוף, אנו נקודד חזרה רק אם סכום אורכי הקידודים של כל אחד מהתווים בנפרד (ע"י שרשור

"0"

וקידוד ההאפמן עבור כל תו) יהיה ארוך (ממש) מאורך קידוד החזרה (שהוא כאמור 9 ביטים).

סעיף ב (4 נק'). רשמו את הפענוח של הרצפים הבאים:

$"01001100010010100100011"$
$"0010000100111000111100"$

סעיף ג (6 נק').
1. רשמו מחרוזת באורך 3 תווים, אשר כמות הביטים הנדרשים לקידוד שלה ע"י תווים בודדים קטן יותר מכמות הביטים הנדרשים לתיאור חזרה (נזכיר כי בשאלה זו חזרה מקודדת ע"י 9 ביטים).
2. רשמו מחרוזת באורך 3 תווים, אשר כמות הביטים הנדרשים לקידוד שלה ע"י תווים בודדים גדול יותר מכמות הביטים הנדרשים לתיאור חזרה.
3. רשמו מה האורך המינימלי למחרוזת כך שכמות הביטים הנדרשים לקידוד שלה ע"י תווים בודדים בהכרח גדול מכמות הביטים הנדרשים לתיאור חזרה.

סעיף ד (4 נק'). רשמו מה יהיה אורך הקידוד של הרצפים הבאים:

$" d c d c f "$
$" c " \cdot 27$ (כלומר $c$ חוזר 27 פעמים)

סעיף ה (3 נק'). בוב הציע מימוש לפונקציה אשר בהינתן תת מחרוזת

s u b_s t r

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

T r u e

במידה שקידודה ע"י חזרה קצר יותר מקידודה ע"י תווים בודדים. במימוש המוצע יש טעות (גם כאשר הקלט תקין). להלן המימוש:

1. הציעו ערך

s u b_s t r

באורך שבין 3 ל-5 תווים עבורו הפונקציה מחזירה ערך לא נכון.
2. בצעו שינוי בשורה אחת אשר מתקן את הפונקציה. ציינו את מספר השורה ואת תוכן השורה המתוקנת.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2025 · סמסטר ב

★★★★★

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

נתון קורפוס עם שכיחויות

a_{1} < a_{2} < \dots < a_{n}

כאשר

n = 128

(כלומר יש

128

תווים שונים בקורפוס). כמו כן מתקיים

a_{n} < 2 a_{1}

. מריצים את האלגוריתם ליצור עץ האפמן מהקורפוס. נסמן ב-

l

את כמות הביטים בקידוד של התו

a_{1}

שתדירותו

a_{1}

, וב-

u

את כמות הביטים בקידוד של התו

a_{n}

שתדירותו

a_{n}

. מהו ההפרש בין

l

לבין

u

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2024 · סמסטר א

★★★★★

קידוד האפמןסיבוכיות זמן

בשאלה זו נעסוק באלגוריתמי דחיסה שונים.

סעיף א (6 נק'). הציגו את עץ האפמן שיתקבל מהקורפוס הבא:

cor p u s = 4 \cdot^{'} a^{'} + 5 \cdot^{'} b^{'} + 6 \cdot^{'} c^{'} + 7 \cdot^{'} d^{'} + 10 \cdot^{'} e^{'} + 15 \cdot^{'} f^{'}

השתמשו בקוד זה בכדי לקודד את הטקסט הבא:

t e x t = " f a d ee "

.

סעיף ב (10 נק'). נתון קורפוס מסוים

C

, מכיל את שש האותיות הנמוכות ביותר בשפה האנגלית:

c, t, a, o, i, n

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

W (e) > W (t) > W (a) > W (o) > W (i) > W (n)

כאשר

W (σ)

היא השכיחות של התו

σ

.

מיכל בנתה עץ וקידוד האפמן על סמך הקורפוס

C

והגיעה בשמחה רבה שבקידוד שייצרה האות

e

מקודדת ע"י המחרוזת

"0"

.

מיכל שלחה את שלוש ההודעות הבאות. ידוע שקידודן ע"י תווים שייצרה.

הודעה א: $011$
הודעה ב: $11101$
הודעה ג: $01011001$

סעיף ג (9 נק'). נתונה הפונקציה H_compress(corpus, text) הממימשת את קידוד האפמן שראינו בכיתה, הדוחסת ע"י האפמן על פי הקורפוס corpus ומחזירה את הקידוד בביטים של המחרוזת text.

נתונה גם הפונקציה LZ_compress(text) הממימשת את קידוד למפל-זיו שראינו בכיתה ומחזירה את הקידוד בביטים של

t e x t

(ניתן להניח שהמימושים משתמשים בפרמטרים שראינו בכיתה:

W = 2^{12} - 1

L = 2^{5} - 1

).

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

s

שעבורה הטענה לא נכונה.

1. לכל מחרוזת

s

, מתקיים: len(H_compress(LZ_compress(s), LZ_compress(s))) == len(LZ_compress(s))

2. לכל מחרוזת

s

, מתקיים: len(H_compress(s, s)) == len(H_compress(s, s[::‐1]))

3. לכל מחרוזת

s

, מתקיים: len(LZ_compress(H_compress(s, s))) == len(H_compress(s, s))

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2023 · סמסטר ב

★★★★★

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

נתון קורפוס text באורך

n

על

t \geq 2

תווים

{a_{1}, \dots, a_{t}}

, כאשר כל תו מופיע בקורפוס לפחות פעם אחת.

בנוסף, נתון עץ האפמן

H

שנוצר מהתדירות ההרגלית של האפמן על הקורפוס text.

עבור כל אחת מהאמירות הבאות (סעיפים א-ד), ציינו את ערכו של הפיסוק (סופים א-ד), כיצד אנו מתארים כל כתגובה פונקציה של

H

:

א. מספר העלים בעץ

H

.
ב. משקל השורש של העץ

H

.
ג. גובה העץ

H

.
ד. מספר הצמתים בעץ

H

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2020 · סמסטר א

★★★★★

קידוד האפמןעצים בינאריים

נתון קורפוס text באורך

n

על

t \geq 2

תווים

{a_{1}, \dots, a_{t}}

, ונתון עץ האפמן

H

.

ו. לכל קורפוס text ולכל עץ האפמן

H

שנוצר מהקורפוס, ישנם שתי רמות שונות שמשקלן שונה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2020 · סמסטר א

★★★★★

קידוד האפמןעצים בינאריים

נתון קורפוס text באורך

n

על

t \geq 2

תווים

{a_{1}, \dots, a_{t}}

, ונתון עץ האפמן

H

.

נגדיר את הרמה ה-

i

בעץ כקבוצת כל הצמתים במרחק בדיוק

i

מהשורש (כלומר הרמה ה-0 כוללת רק את בני בניו של השורש בלבד, הרמה ה-1 את בני בניו של השורש בלבד וכו'). שימו לב: יש רמות תשובות מהדירוות, ובפורט לא להשתמש בהן.

ה. לכל קורפוס text ולכל עץ האפמן

H

שנוצר מהקורפוס, לכל הרמות משקל זהה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2020 · סמסטר א

★★★★★

קידוד האפמןעצים בינאריים

עומר ואדם רוצים לשלוח ביניהם הודעות טקסט שמכילות אך ורק תווים מתוך 16 תווי ה-ASCII הראשונים. כלומר, קוד ה-ASCII של כל תו בהודעות שישלחו יהיה מספר שלם בין 0 ל-15 כולל.

הם יצרו גירסה חדשה של אלגוריתם הדחיסה "למפל-זיו". בגירסה החדשה תו בודד יקודד ע"י הביט "0" ולאחריו

r

ביטים שמייצגים את קוד ה-ASCII של התו (כלומר, בסה"כ

1 + r

ביטים). חזרה תקודד (כמו באלגוריתם המקורי) ע"י הביט "1" ולאחריו 12 ביטים להיסט אחורה (offset) ולאחריהם 5 ביטים לאורך החזרה (כלומר, בסה"כ

1 + 12 + 5 = 18

ביטים).

סעיף 1: מהו הערך הקטן ביותר האפשרי ל-

r

(מספר הביטים לייצוג כל קוד ASCII של תו שיכול להופיע בהודעה)?

r =

__________

סעיף 2: מהי כמות התווים המינימלית

s

, כך שחזרות באורך

s

ומעלה משתלם לייצג כחזרה ולא כרצף תווים בודדים (מבחינת כמות הביטים)?

s =

__________

נימוק קצר לתשובתכם.

שימו לב: בהמשך השאלה נניח כי משתמשים בגירסה החדשה של למפל-זיו שמוגבלת ל-16 תווים ושאכן לא מקודדים חזרות באורך קטן מ-

s

.

סעיף 3: נניח שהתווים a,b,c,d,e הינם בעלי קוד ASCII בין 0 ל-15 כולל ולכן יכולים להופיע בהודעות בין עומר לאדם.

עבור כל מחרוזת ציינו כיצד יראה ייצוג הביניים של מחרוזת זו בשיטת הדחיסה של עומר ואדם:

"abababab" ייצוג הביניים: __________
"abcabcdabc" ייצוג הביניים: __________
"abcdabcdeabcde" ייצוג הביניים: __________

סעיף 4: עומר הפעיל את האלגוריתם על מחרוזת text חוקית וקיבל מחרוזת של ביטים, נסמנה binary. אדם הציע שכעת נתייחס למחרוזת זו כאל מחרוזת בינארית של "0" ו-"1", ונפעיל עליה אלגוריתם האפמן, כאשר הקורפוס הינו "01"*25 (כלומר שכפול של "01" עשרים וחמש פעמים). לדעתו של אדם התוצאה תהיה מחרוזת קצרה יותר מהמחרוזת binary. עומר טוען שהפעלת האפמן עם הקורפוס הזה מיותרת ותייצר מחרוזת באותו אורך כמו binary. בתיה טענה ששניהם טועים -- המחרוזת לאחר דחיסת האפמן תהיה אפילו ארוכה יותר. מי מהם צודק? הסבירו.

הקיפו בעיגול: עומר צודק / אדם צודק / בתיה צודקת

נימוק: __________

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2019 · סמסטר א

★★★★★

קידודקידוד האפמן

נתון קורפוס שמכיל את התווים a,b,c,d,e. שכיחויות התווים בקורפוס הינן:

w_{a}, w_{b}, w_{c}, w_{d}, w_{e}

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

בכל תת-סעיף נתון מבנה של עץ ועליכם לסמן את התנאים על ערכי השכיחויות שבהכרח יגרמו לבניית עץ בעל מבנה כזה ע"י אלגוריתם האפמן (עד כדי הבדלים של שמאל ימין), או לסמן שאין תנאי כזה מבין האפשרויות.

עץ א: (עץ בצורת שרשרת -- כל צומת פנימי, ילד אחד הוא עלה והשני הוא תת-עץ)

אפשרויות:

a. $w_{a} > w_{b} > w_{c} > w_{d} > w_{e}$
b. $w_{a} = \frac{1}{2} w_{b} = \frac{1}{4} w_{c} = \frac{1}{8} w_{d} = \frac{1}{16} w_{e}$
c. $w_{a} = w_{b} = w_{c}, w_{d} > 3 w_{a}, w_{e} > 2 w_{d}$
d. $w_{a} = \frac{1}{2} w_{b} = \frac{1}{3} w_{c} = \frac{1}{4} w_{d} = \frac{1}{5} w_{e}$
e. אף אחד מהנ"ל לא מתאים עבור עץ זה

עץ ב: (עץ שבו שלושה עלים בעומק 2 ושני עלים בעומק 3)

אפשרויות:

a. $w_{a} = \frac{1}{2} w_{b} = \frac{1}{4} w_{c}, w_{d} = \frac{1}{16} w_{e}$
b. $w_{a} > w_{b} > 2 w_{c} > 4 w_{d} > 8 w_{e}$
c. $w_{a} = w_{b} = w_{c}, w_{d} = w_{e} > 10 w_{a}$
d. $w_{a} = w_{b} = w_{c}, w_{d} = w_{e} > 3 w_{a}$
e. אף אחד מהנ"ל לא מתאים עבור עץ זה

עץ ג: (עץ מאוזן -- שורש עם שני תת-עצים, אחד עם 2 עלים ואחד עם 3 עלים בצורת שרשרת)

אפשרויות:

a. $w_{a} = \frac{1}{2} w_{b} < \frac{1}{4} w_{c} = \frac{1}{4} w_{d} = \frac{1}{5} w_{e}$
b. $w_{a} = \frac{1}{10} w_{b} = \frac{1}{20} w_{c} = \frac{1}{25} w_{d} = \frac{1}{30} w_{e}$
c. $w_{a} > w_{b} > w_{c}, w_{d} < w_{e}$
d. $w_{a} = w_{b} = w_{c} < w_{d} = w_{e}$
e. אף אחד מהנ"ל לא מתאים עבור עץ זה

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2019 · סמסטר א

★★★★★

קידוד האפמן

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

תזכורת: 128 תווי ascii מיוצגים במחשב (ללא דחיסה) באמצעות 7 ביטים כל אחד. חזרה מיוצגת באלגוריתם למפל זיו באמצעות זוג m, k כאשר ל-m מוקצים 12 ביטים בדיוק ול-k מוקצים 5 ביטים בדיוק. אנחנו משתמשים בגירסא בה לא דוחסים חזרות שאורכן 2 או פחות (k>=2).

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

לכל אחת מהמחרוזות בסעיפים הבאים:
1. ציירו עץ האפמן אפשרי שמתקבל מהמחרוזת כאשר היא משמשת כ-corpus
2. כתבו ביטוי המציין את יחס הדחיסה של המחרוזת לפי דחיסת האפמן והסבירו כיצד הגעתם לתשובה
3. כתבו את ייצוג הבינויים בדחיסת למפל-זיו והסבירו כיצד הגעתם לתשובה
4. כתבו ביטוי המציין את יחס הדחיסה של המחרוזת לפי דחיסת למפל-זיו והסבירו כיצד הגעתם לתשובה

בכל אחד מסעיפים 2 ו-4 אין צורך לחשב מספר שהוא יחס הדחיסה. מספיק לרשום ביטוי אריתמטי (מכיל פעולות חיבור, כפל וכו') השווה ליחס הדחיסה.

א. המחרוזת s = "abc"*k עבור 1<k<10 שלם.

ב. המחרוזת s = "abcabcdabcdeabcde".

ג. המחרוזת s = ''.join(['a'*i+'b'*i+'c'*i for i in range(5)]).
(תזכורת: ''.join(['a','b','c']) -> 'abc')

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2018 · סמסטר ב

★★★★★

קידוד האפמןקידוד

השאלה עוסקת בדחיסת טקסט.

נתון א"ב

Σ = {a_{1}, a_{2}, \dots, a_{n}}

ומשקלים

W = {w_{1}, w_{2}, \dots, w_{n}}

כאשר המשקל של

a_{i}

הוא

w_{i}

. המשקלים מקיימים

w_{1} > w_{2} > \dots > w_{n}

. נגדיר את הקידוד הבא:

תו	קידוד
$a_{1}$	0
$a_{2}$	10
$a_{3}$	110
$a_{4}$	1110
...	...
$a_{n - 1}$	$n - 1 111 \dots 1 0$
$a_{n}$	$n - 1 111 \dots 1 1$

נקרא לקידוד כזה "קידוד מונוטוני".

א. עבור הא"ב

Σ = {a_{1}, a_{2}, a_{3}, a_{4}}

תנו דוגמה למשקלים

w_{1} > w_{2} > w_{3} > w_{4}

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

ב. עבור הא"ב

Σ = {a_{1}, a_{2}, a_{3}, a_{4}}

תנו דוגמה למשקלים

w_{1} > w_{2} > w_{3} > w_{4}

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2018 · סמסטר א

★★★★★

קידודקידוד האפמן

שאלות קידוד האפמן במבוא למדעי המחשב עם פתרונות

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