סיפורי אופטימיזציה: קוד קל-משקל

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

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

התשובה הנאיבית היא להחזיק טבלה של צמדים: בטור אחד מחרוזת שמייצגת את הנקודות והקווים (למשל "-.-") ובטור השני התו המתאים ("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 קווים ונקודות. ההתמודדות איתם מצריכה גישה טיפה פחות אלגנטית, ולכן נעצור כאן 🙂

להרשמה
הודע לי על
11 Comments
מהכי חדשה
מהכי ישנה לפי הצבעות
Inline Feedbacks
הראה את כל התגובות

תודה על הפוסט, אהבתי את הגישה. בדיוק כשהתחלתי לחשוב על ייצוג "מרומז" של עץ, עידו העיר שזה שקול. דרך אגב, מימוש כ – TRIE (http://en.wikipedia.org/wiki/Trie) יכול היה להיות מגניב עם יכולת prediction. יש לי רעיון שמעלה קצת עת כמות החישוב אבל מצמצם את המקום למשהו שנע בין 17 ל – 18 בתים (למעשה 9 אינטג'רים). הוא עוד ראשוני ולא לגמרי מעובד, מה עוד שאין לי כרגע מתחת ליד ארדואינו עובד לבדוק אם זה עובד עד הסוף, אבל לדעתי הוא ישים. נתחיל מזה שיש אריתמטיקת תווים בארדואינו, כלומר: 'a' = 65 'b' = 66 וכו'. מאחר ואנחנו מדברים (כשעוסקים רק באותיות)… לקרוא עוד »

למה שלא תקח כל בייט ותחלק אותו לשתי קבוצות?
חמישה ביטים ראשונים עבור הייצוג הבינארי של הקוד, ושלושת הביטים באחרונים עבור כמות הסימנים, ככה יש לך אפשרות לשמור כל תו בבייט אחד בלי צורך "לזכור" מה כמות הסימנים, זה יהיה טוב עד 6/7 סימנים לתו.

ערך התו באסקי יהיה המיקום שלו במערך הבייטים. שיטה כזו יעילה בעיקר להמרה הפוכה- מטקסט למורס כיוון שלהפך רק החיפוש אחרי התו הנכון יקח הרבה פעולות

אני מסכים עם חגי שיש קצת בעיה עם קוד שאף אחד חוץ ממך לא יכול לקרוא אבל מצד שני החיסכון אכן משמעותי. יכול להיות שאפשר במקרה הזה להשתמש במערך מערכים (לא 2D אלא [] []) שמגדירים כל אחד בנפרד באורך המתאים.
אפשרות יותר יעילה לדעתי היא מיון על בסיס עץ בינארי שלדעתי יותר יעיל מבחינת המקום ואולי אפילו הפעולות https://www.google.co.il/search?q=morse+code+binary+tree&sa=X&espv=210&es_sm=93&tbm=isch&tbo=u&source=univ&ei=44aEUqdCg9i0Bo6EAQ&ved=0CCsQsAQ&biw=1024&bih=509#imgdii=_

בסדר, נכנעתי…

אלגנטי בהרבה לכתוב קוד שבני אנוש יכולו להבין, בלי לקשר בהערה לפוסט שלך..
לפחות היית מפצל את הstring שלך ל2d array של chars, עם אינדקס אחד לאורך והשני לערך. זה אפילו אותו משקל, לא?