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

משמש, nana ומילון

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

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

 
 
 
 
 
 
 
 
 
 
פרסומת
 
בשבוע שעבר הצגנו אתגר תכנות לא חשוב אך משעשע: חיפוש מילים בשפה X שכאשר מקלידים אותן בטעות במקלדת שמכוונת לשפה Y מקבלים מילים בעלת משמעות ב-Y. התוכנה שכתבתי לצורך העניין, עם מילון עברי צנוע של כ-16,000 מילים, הצליחה למצוא במהירות כמות נאה של התאמות. רובן הגדול היה לראשי תיבות אנגליים נדירים שהשתרבבו למילון הלועזי, אך הנה ההתאמות הבולטות מבין השאר:

punch = פומבי, thus = איוד, neck = מקבל, aura = שורש, ago = שעם, axe = שסק, echo = קבים (כתיב חסר, למה לא), pure = פורק, pay = פשט, prey = פרקט, guns = עומד, shunt = דיומא, dusk = גודל, muse = צודק, mpg = צפע (גם פורמט סרטים נחשב!), bugs = נועד, babe = נשנק, beg = נקע.

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

יותר ויותר מהר

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

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

0 ו-1 זה לא הכל בחיים

החיפוש הבינארי יעיל מאד: כדי לאתר מילה נדרשות log(n) פעולות (בבסיס 2 כמובן), לדוגמה 8 פעולות עבור מילון של 256 מילים. הוא גם אינטואיטיבי מאד, כי הוא מבוסס על פעולת השוואה שהתוצאה שלה היא בינארית (גדול מ- או לא גדול מ-). עם זאת, ומשום מה אנשי מחשבים נוטים קצת לשכוח כאן את המתמטיקה הפשוטה, חלוקה ל-2 היא לא החלוקה האופטימלית האוניברסלית. למשל, כדי להגיע מ-100 ל-1 צריך שש חלוקות חוזרות ב-2, אבל רק שתי חלוקות חוזרות ב-10!

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

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

הפתרון כמעט מובן מאליו כעת: עץ לא בינארי!
 

עץ עשרים-וששי

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

לצורך ההדגמה נשתמש רק באותיות A עד D. אנו מתחילים בעץ ריק:
 
שורש של עץ לא בינארי לאחסון מילון (איורים: עידו גנדל)
 שורש של עץ לא בינארי לאחסון מילון (איורים: עידו גנדל) 
 
נוסיף לו את המילה הראשונה שלנו, AB. העיגול הירוק מסמל סיום מילה, אם כי העץ יכול בהחלט להמשיך משם גם הלאה:
 
העץ בתוספת המילה AD
 העץ בתוספת המילה AD 
 
והנה אותו עץ בתוספת המילים ABBA ו-DAD:
 
העץ בתוספת ABBA ו-DAD
 העץ בתוספת ABBA ו-DAD 
 
בניגוד לאחסון ברשימה או בעץ בינארי, כאן אין כפילות: שילוב הצמתים AB בהתחלה משמש את כל המילים שמתחילות ב-AB, בלי שיהיה צורך לאחסן את שתי האותיות הללו עבור כל מילה מחדש. ובניגוד לטבלת גיבוב שמכילה טבלאות גיבוב נוספות ומיותרות, כאן אין כמעט מחיר לענפים "מתים". החיפוש בעץ כזה הוא, כאמור, מהיר ביותר. האם יש לנו זוכה?

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

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