הצגת המקור של הדף "אי-שוויון קראפט"

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

==הגדרה==

נניח [[קבוצה סופית|קבוצה מעוצמה סופית]] או [[אלף אפס]] של מילים <math>L \subset \Sigma^*</math> מעל א"ב כלשהו <math>\Sigma</math>.
אי-שוויון קראפט אומר כי התנאי 
<math display="block">\sum_{\ell \in L}|\Sigma|^{-|\ell|} \leq 1</math>
הוא מספיק והכרחי לשיוך כל מילה ב-<math>L</math> לצומת עץ (אולי אינסופי) בעל דרגת יציאה <math>|\Sigma|</math>, כך ש:
# כל מילה משויכת לצומת יחיד בעומק השווה לאורך המילה.
# אין שתי מילים המשויכות לצומת וצאצא שלו.

===דוגמה===

נניח א"ב בעל שלוש אותיות, לדוגמה <math>\Sigma = 0, 1, 2</math>. נניח שיש לנו קבוצה בת חמש מילים מעל א"ב זה, שאורכיהן הם <math>\{2, 1, 2, 2, 2\}</math>. עלינו למצוא שיוך לעץ המוצג בצד שמאל כך שארבעה צמתים בגובה 2 ישויכו, צומת אחד בגובה 1 ישויך, ואף צומת משויך לא יהיה צאצא של צומת משויך אחר.  
[[File:KlomogorovTree 0.png|שמאל|ממוזער|עץ שיוך]]

במקרה זה,
<math display="block">3^{-2} + 3^{-1} + 3^{-2} + 3^{-2} + 3^{-2} = 0.777777778 < 1,</math>
ולכן אי-שוויון קראפט מבטיח שיש שיוך מתאים. ואכן, השיוך בתרשים בצד שמאל הוא שיוך מתאים.
[[File:KolmogorovTree 3.png|שמאל|ממוזער|שיוך אפשרי]]

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

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

נסמן כל צומת בעץ כ'''פנוי''', '''משויך''', או '''תפוס'''. 
# בתחילה, כל צומת יהיה פנוי.
# בכל פעם שצומת הופך להיות משויך, כל אחד מאבותיו (עד השורש) נהיה תפוס (ייתכן שחלקם כבר היו תפוסים).
# אם בצעד כלשהו צריך לשייך צומת ברמה <math>h</math>, נמצא את הצומת הפנוי השמאלי ביותר ברמה זו, ונשייך אותו.

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

==חשיבות==

כאשר מילים משויכות לעצים, אפשר לבנות [[קוד]] למילים. בהינתן מילה, נמצא את הצומת המתאים למילה, ונתאר את המילה בעזרת המסלול המוביל מראש העץ למילה. בתרשים הקודם, לדוגמה, המילים השייכות לצמתים יתוארו, משמאל לימין, על ידי המחרוזות:
# 00 (רד שמאלה פעמיים)
# 1 (רד ישר פעם אחת)
# 20 (רד ימינה ואז שמאלה)
# 21 (רד ימינה ואז ישר)
# 22 (רד ימינה פעמיים)

כאשר משתמשים בשיטה זו לקידוד רצף מילים, עולה הבעיה היכן מסתיים קידוד מילה אחת ומתחיל קידוד המילה הבאה. לדוגמה, נניח שקידוד רצף המילים הוא
201002:
# רצף הקידודים עשוי להיות 20,10,02,
# רצף הקידודים עשוי להיות 201, 00, 2
# וכו'

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

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

[[קטגוריה:תורת האינפורמציה]]
[[קטגוריה:תורת הקודים]]
[[קטגוריה:משפטים במדעי המחשב]]