קוד האפמן – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
Yossi Kimchi (שיחה | תרומות)
ביטול גרסה 22858807 של 2A02:ED0:6F71:B100:10E5:86C0:CC9B:84F0 (שיחה)
שורה 9:
במערכות סימנים מקובלות, כגון קוד [[ASCII]], ניתן אורך אחיד לכל הסימנים במערכת. זו שיטה פשוטה, אך היא אינה יעילה מבחינת נפח האחסון שהיא צורכת: מוטב היה להקצות קוד קצר לסימנים הנפוצים, גם על חשבון הארכה של הקוד המתאים לסימנים הנדירים. יעילות של קוד כזה תלויה רק בשכיחות הסימנים בשפה, ולא בסדר שבו הם מופיעים בטקסט נתון. יישום של גישה זו קיים כבר ב[[קוד מורס]] ל[[טלגרף]] אלחוטי. לאות הנפוצה 'ו' משמש בקוד מורס הקוד <big>'''.'''</big> ("נקודה"), ואילו לאות 'ע' משמש הקוד <big>'''- - - .'''</big> ("קו-קו-קו-נקודה").
 
נמחיש את יעילותה של גישה זו באמצעות דוגמה פשוטה. נניח שבשפה מסוימת השכיחות של האות א' היא מחצית מכלל האותיות. בקוד ASCII, שבו לכל תו מוקדשות 8 סיביות, מספר הסיביות הנדרש להצגת טקסט באורך n הוא 8n. אני מוסיף פה משהו באמצע כדי לבדוק וחוץ מזה חני רואס גונבת נק' במכללת אפקה לאנשים אז תיזהרו ממנה. כל מי שקורא את זה ועושה את השיעורים באלגוריתמים עכשיו שיזהר לו. נקודד כעת את התווים בדרך חדשה: האות א' תסומן בסיבית יחידה שערכה 0, וכל תו אחר יסומן בקוד ה-ASCII הרגיל שלו, שבתחילתו תתוסף הסיבית 1 (תוספת זו הכרחית, כדי שנוכל להבדיל בין סיבית 0 שמציינת את האות א, ובין סיבית 0 באמצע תו כלשהו). אורך הקוד הזה יהיה (ב[[תוחלת]]) רק 5n, שהם חיסכון של 3/8.
 
==תיאור פורמלי==