אי-שוויון קראפט

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

הגדרה

נניח קבוצה סופית או אינסופית אך בת מניה של מילים $L \subset \Sigma^*$ מעל א"ב כלשהו $\Sigma$. אי-שוויון קראפט אומר כי התנאי

$\sum_{\ell \in L}|\Sigma|^{-|\ell|} \leq 1$

הוא מספיק והכרחי לשיוך כל מילה ב-$L$ לצומת עץ (אולי אינסופי) בעל דרגת יציאה $|\Sigma|$, כך ש:

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

דוגמה

נניח א"ב בעל שלוש אותיות, לדוגמה $\Sigma = 0, 1, 2$. נניח שיש לנו קבוצה בת חמש מילים מעל א"ב זה, שאורכיהן הם $\{2, 1, 2, 2, 2\}$. עלינו למצוא שיוך לעץ המוצג בצד שמאל כך שארבעה צמתים בגובה 2 ישויכו, צומת אחד בגובה 1 ישוייך, ואף צומת משוייך לא יהיה צאצא של צומת משוייך אחר.

עץ שיוך

במקרה זה,

$3^{-2} + 3^{-1} + 3^{-2} + 3^{-2} + 3^{-2} = 0.777777778 < 1,$

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

שיוך אפשרי

אלגוריתם מקוון

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

נסמן כל צומת בעץ כפנוי, משוייך, או תפוס.

1. בתחילה, כל צומת יהיה פנוי.
2. בכל פעם שצומת הופך להיות משוייך, כל אחד מאבותיו (עד השורש) נהיה תפוס (ייתכן שחלקם כבר היו תפוסים).
3. אם בצעד כלשהו צריך לשייך צומת ברמה $h$, נמצא את הצומת הפנוי השמאלי ביותר ברמה זו, ונשייך אותו.

המשפט לעיל אומר שאי-שוויון קראפט מתקיים אמ"ם אין צעד שבו אי אפשר למצוא צומת פנוי.

חשיבות

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

1. 00 (רד שמאלה פעמיים)
2. 1 (רד ישר פעם אחת)
3. 20 (רד ימינה ואז שמאלה)
4. 21 (רד ימינה ואז ישר)
5. 22 (רד ימינה פעמיים)

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

1. רצף הקידודים עשוי להיות 20,10,02,
2. רצף הקידודים עשוי להיות 201, 00, 2
3. וכו'

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

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

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