״משחק המילים המתקפלות״

מתוך המאמר ״Foldable Words״ (פבר׳ 2021) של Brian Hayes, מתוך האתר Bit-player.

משחק המילים המתקפלות (או באנגלית: Foldable Words) הוא בעצם בעיה אלגוריתמית המתייחסת ליכולת ״לקפל״ מילה תקנית בשפה האנגלית בתוך משפט תקני אחר. ההגדרה למילה ״מתקפלת״ היא מילה אשר כל האותיות שלה מופיעות בגרסה המנורמלת של המשפט (״גרסה מנורמלת״: ללא אותיות גדולות או סימני פיסוק) באותו הסדר בו הן מופיעות במילה המקורית עצמה, אך לא בהכרח רצופות. באותו האופן, ניתן להתייחס ל-״משפט מתקפל״, כאשר כל מילה מתוך המשפט הינה מילה מתקפלת בפני עצמה מתוך המשפט המקורי והן מופיעות בדיוק באותו הסדר. להלן דוגמה למספר משפטים המתקפלים מתוך המשפט ״It’s a pleasure to serve you״:

          itsapleasuretoserveyou   ==>   I love you.

          itsapleasuretoserveyou   ==>   I please you.

          itsapleasuretoserveyou   ==>   I leave you.

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

כבר חשבתם על פתרון? בואו ונראה שניים מהם.

הפתרון ה׳נאיבי׳ נקרא ״FoldableString3״  והוא פועל בגישה של חיפוש המילים ״בכוח הזרוע״ (Brute Force) על הקלט עצמו. האלגוריתם מייצר את כל האפשרויות של רצפי האותיות עד אורך 3 מתוך הטקסט שהתקבל ובודק אם הרצף שנוצר הוא מילה תקנית בשפה. האלגוריתם עצמו מקבל את שני הפרמטרים הבסיסיים בלבד: משפט תקני באנגלית (text) ומאגר מילים (lexicon). היתרון הבולט של אלגוריתם זה הוא היכולת לספק תשובה מהימנה עבור מילים באורך 3. מצד שני, ניתן להבחין כי החיסרון הבולט של אלגוריתם זה, מעבר להיותו פרימיטיבי לחלוטין, הוא שהוא מוגבל לאורך מסוים של מילה, שכן להגריל את כל רצפי האותיות באנגלית עד אורך 15 היא פעולה מאוד יקרה ולא מתוחכמת. בנוסף, זמן הריצה של האלגוריתם אינו יעיל, הוא מושפע באופן ישיר מגודל הקלט וגדל באופן אקספוננציאלי, כלומר זמן הריצה הוא O(n^3).

פתרון נוסף, הינו אלגוריתם שנקרא ״RandomFoldableWords״ והוא פועל בגישה של חיפוש המילים באופן רנדומלי מתוך הטקסט הנתון. כלומר, האלגוריתם פועל באופן בו הוא רץ מספר מוגדר מראש של פעמים, כאשר בכל פעם מגריל רצף אותיות רנדומלי מתוך הטקסט ובודק אם המילה שהתקבלה היא מילה תקנית מתוך המאגר. האלגוריתם עצמו מקבל את שני הפרמטרים הבסיסיים: משפט תקני באנגלית (text) ומאגר מילים (lexicon) ובנוסף את אורך המילה הרנדומלית אותה הוא מייצר (k) ואת מספר הריצות שיבצע (reps). היתרון המרכזי של אלגוריתם זה הוא היכולת לקבוע מראש בכל הרצה את סדר הגודל של זמן הריצה, כלומר את כמות הריצות, ביחס לדיוק הדרוש. זמן הריצה הכולל של האלגוריתם מושפע אך ורק מכמות החזרות שנזין כקלט, מכיוון ש-״תהליך בניית המילה״ נעשה  על ידי הגרלת אינדקסים של אותיות ובגישה פשוטה לתווים במחרוזת. לאחר מכן, החיפוש בלקסיקון נעשה ב- O(1). בנוסף, אלגוריתם זו הוא יותר ממוקד ומודולרי, הוא יכול להתמקד באורך מסוים של מילים ולחקור אותן בלבד. מצד שני, החיסרון המשמעותי של אלגוריתם זה הוא שלא ניתן להגיע לתוצאה וודאית במאה אחוזים. מכיוון שהאלגוריתם מחייב להזין כקלט את כמות ההגרלות, נותרת באופן קבוע השאלה, איזה מילים לא הוגרלו שהפונקציה פספסה? 

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

 http://bit-player.org/2021/foldable-words

תודה מיוחדת לאלון לסמן וזיו שחם