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

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

הגדרה

נניח קבוצה מעוצמה סופית או אלף אפס של מילים ${\displaystyle L\subset \Sigma ^{*}}$ מעל א"ב כלשהו ${\displaystyle \Sigma }$. אי-שוויון קראפט אומר כי התנאי $${\displaystyle \sum _{\ell \in L}|\Sigma |^{-|\ell |}\leq 1}$$ הוא מספיק והכרחי לשיוך כל מילה ב-${\displaystyle L}$ לצומת עץ (אולי אינסופי) בעל דרגת יציאה ${\displaystyle |\Sigma |}$, כך ש:

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

דוגמה

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

עץ שיוך

במקרה זה, $${\displaystyle 3^{-2}+3^{-1}+3^{-2}+3^{-2}+3^{-2}=0.777777778<1,}$$ ולכן אי-שוויון קראפט מבטיח שיש שיוך מתאים. ואכן, השיוך בתרשים בצד שמאל הוא שיוך מתאים.

שיוך אפשרי

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

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

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

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

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

חשיבות

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

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

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

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

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

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

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