אי-שוויון קראפט – הבדלי גרסאות

 

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

 

במקרה זה,

<center><math>3^{-2} + 3^{-1} + 3^{-2} + 3^{-2} + 3^{-2} = 0.777777778 < 1,</math></center>

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

 

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