ב-Online
 
 
 
 
 
 
 
לפרק את הבייט 
היום בו nana הפכה למשמש 

היום בו nana הפכה למשמש

 
לפרק את הבייט |
 

רעיון מקורי באמת לפרויקט תכנות: תוכנה קטנה שתאתר את כל המילים שיש להן משמעות גם אם מקלידים אותן בטעות בשפה הלא-נכונה

 
 
 
 
 
 
 
 
 
 
 

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

 

יאאפ:.. טמקא

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

 
מקום שלישי בגוגל: הבלוג שהתפרסם בזכות שגיאת הקלדה (צילומסך: עידו גנדל)
 מקום שלישי בגוגל: הבלוג שהתפרסם בזכות שגיאת הקלדה (צילומסך: עידו גנדל) 
 
 

לפעמים, לגמרי במקרה כמובן, המחרוזת שמתקבלת כתוצאה מהקלדה בשפה הלא-נכונה היא בעלת משמעות בפני עצמה. כך למשל הקלדה של שם האתר nana בעברית נותנת "משמש", והקלדה של "גרוע" באנגלית נותנת "drug". חיפוש קצר בגוגל העלה, איך לא, מספר תוצאות משעשעות נוספות (תחת הכותרת "תקלדות qwerty בעלות משמעות"). בנקודה זו אמור להתעורר המתכנת החובב ולשאול: האם ניתן לכתוב תוכנה שתמצא את כל ההתאמות המקריות הללו?

 

שלב ראשון: המרה

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

 

שלב שני: מילונים

כך, ילדים, נראה מילון
 כך, ילדים, נראה מילון 
 צילום: GettyImages 
 

כצפוי, הרשת יכולה לעזור לנו מאד במציאת רשימות מילים מקיפות, שיחסכו את הצורך להקליד ידנית את מילון אוקספורד או אבן-שושן. רשימות אלה משמשות לרוב תוכנות לבדיקת איות, וחלק מהן מוצעות בחינם לכל דיכפין עם תנאי שימוש מתירניים. כך, למשל, חבילת ispell או SCOWL שניתן להוריד מכאן, או Moby Word Lists. בכולן תמצאו קבצי טקסט ענקיים בפורמט פשוט - מילה אחת בכל שורה.

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

 

שלב שלישי: מבנה הנתונים


 צילום: GettyImages 
 

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

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

כשלב ראשון, אפשר לצמצם את הרשימות ולהוציא מהן מילים שלא יכולות להופיע בשום אופן. לדוגמה, לעולם לא נמצא התאמה למילה שמסתיימת ב-ץ סופית, כי התו המקביל במקלדת האנגלית הוא "<". באותו אופן, לא תיתכנה התאמות למילים באנגלית שיש בהן I או O בהתחלה או באמצע, או את האות Q, או מילים בעברית שכוללות ת' או ף סופית (האות W דווקא קבילה, מכיוון שהגרש העברי יכול להופיע במילה אחרי ג', ז' או צ').

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

 
טבלת Hash בסיסית לשיפור מהירות הגישה והחיפוש המילים (איור: עידו גנדל)
 טבלת Hash בסיסית לשיפור מהירות הגישה והחיפוש המילים (איור: עידו גנדל) 
 

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

נ.ב. הקוד לתוכנת החישובים במספרים גדולים מהשבוע שעבר יופיע בתוך יום או יומיים באתר הבית שלי – עקבו אחר העדכונים בפייסבוק. htkkv chh!

 
 
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
 
תגובות
הוסף תגובה0 תגובות
הוספת תגובה
מאת
 
נושא
 
תוכן
 
 
 
 
תודה! תגובתך התקבלה.
התגובה תתפרסם בכפוף לתנאי האתר.
 
 
 
 
 

כל הזכויות שמורות 2011 © נענע 10 בע"מ
 
 
 
 
כל הזכויות שמורות © Nana10 בע"מ
Video powered by