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

קוד מורס ענייין אותי מאז ומתמיד (הנה טור שכתבתי עליו לפני חמש שנים וקצת), ולאחרונה התפנה לי קצת זמן כדי ללמוד אותו כמו שצריך. אז קניתי מפתח מורס – הידית שבסרטון, חדשה תוצרת סין – והתחלתי לכתוב תוכנה ללוח תואם הלאונרדו שלי כדי שאוכל להשתמש במפתח כמו במקלדת. פרט לזיהוי של הנקודות, הקווים והרווחים, התוכנה הזו צריכה לדעת גם לתרגם את הצירופים שלהם לאותיות המתאימות שיישלחו למחשב, וכאן העסק מתחיל להיות מאתגר. באיזו צורה כדאי לאחסן ולאתר את המידע?

התשובה הנאיבית היא להחזיק טבלה של צמדים: בטור אחד מחרוזת שמייצגת את הנקודות והקווים (למשל "-.-") ובטור השני התו המתאים ("K"). אם נתעלם לצורך העניין מספרות ומסימני פיסוק, יש לנו את 26 האותיות של הא"ב הלועזי, ואם אינני טועה לכל אחד מהם מחרוזת באורך ממוצע של כ-3.154 תווים. כלומר, הטבלה הזו תתפוס מינימום 82 בייטים בזיכרון, וזה עוד לפני שדיברנו על ריווח לצורך גישה קלה יותר, ועל איך בכלל מחפשים בה בצורה יעילה.

לצירופים של קוד מורס אין שום קשר לבסיס הבינארי, כך שאי אפשר להמיר אותם ישירות לייצוג מספרי נוח. גם אם ננסה, למשל, להפוך כל נקודה ל-0 וכל קו ל-1, ניתקל בבעיה: האם בייט שערכו 1 הוא האות T (קו יחיד), A (נקודה וקו, כלומר אפס-אחד), U (שתי נקודות וקו) או V (שלוש נקודות וקו)?

פריצת הדרך הגיעה כשחשבתי לשמור בצד, בנוסף לייצוג הבינארי של הקווים והנקודות, גם את אורך הצירוף. הא"ב בקוד מורס כולל את כל הווריאציות האפשריות על ביט יחיד (נקודה ל-E, קו ל-T), על שני ביטים (I,A,N,M) ועל שלושה ביטים, ו-12 מתוך ה-16 האפשריות לארבעה ביטים. כתבתי מחרוזת אחת ארוכה עם כל אותיות הא"ב, ממוינים קודם כל לפי אורך הצירוף שלהם במורס, מהקטן לגדול, ובתוך זה ממוינים לפי הייצוג הבינארי של אותו צירוף, גם כן מהקטן לגדול. את ארבעת הייצוגים החסרים לארבעה ביטים סימנתי בעזרת תו שאינו קיים במורס: קו תחתון. הנה המחרוזת כפי שהיא מוגדרת בתוכנה שלי:

const char MORSE_LOOKUP_1_4[31] = 
           "ETIANMSURWDKGOHVF_L_PJBXCYZQ__";

מה זה נותן? ובכן, אם הקטע של בסיס 2 חקוק לכם במוח, אתם כבר מבינים שיש 2 תווים עם "ביט" יחיד, 4 תווים עם 2 ביטים, 8 עם 3 ו-16 (כולל ה"חסרים") עם 4. זאת אומרת שכל קבוצת תווים כזו מתחילה במיקום 2-בחזקת-N פחות 2 במחרוזת (כאשר N הוא מספר הביטים של חברי הקבוצה). לדוגמה, התווים שהצירוף שלהם הוא באורך 3 ביטים יתחילו בתו מספר שש (זיכרו שמחרוזות בשפת C מתחילות באינדקס 0). בתוך קבוצת התווים הזו, הייצוג הבינארי של הצירוף ייתן לנו את המיקום המדויק. אגב, הגדרת המחרוזת היא בת 31 תווים ולא 30 כי צריך את התו הנוסף לסיום תקני של המחרוזת ("0\").

זה לא מסובך כמו שזה נשמע. נניח שאני מקבל את הצירוף "-..-". אני ממיר אותו לייצוג הבינארי "1001" וזוכר שיש בו 4 ביטים. לפי החישוב למעלה, הקבוצה הרלוונטית במחרוזת מתחילה ב-2-בחזקת-4 מינוס 2, שזה 14, ולתוצאה הזו צריך להוסיף את הערך 1001 בינארי, שזה 9 עשרוני, סה"כ 23. סיפרו ותראו שהתו הזה הוא "X". תשובה נכונה!

את כל זה אפשר לתאר בשורת קוד אחת קטנה. היא נמצאת בתוך פונקציה, שמקבלת את המשתנה len (מספר הביטים בצירוף), ואת m (הערך שלו):

return MORSE_LOOKUP_1_4[(1 << len) - 2 + m];

אם יש פתרון יותר חסכוני וזריז מזה, אשמח לראות אותו!

לרוע המזל, קוד מורס כולל גם סימנים נוספים, עם צירופים בני 5 ו-6 קווים ונקודות. ההתמודדות איתם מצריכה גישה טיפה פחות אלגנטית, ולכן נעצור כאן 🙂