איך תיבת חיפוש מנחשת מה תרצו להקליד - מתחת לרשימת ההשלמות¶
מקלידים "פיצ" בתיבת חיפוש, ולפני שהספקתם לסיים את המילה, כבר מופיעה רשימה - "פיצה", "פיצוץ", "פיצול". זה קורה תוך מילישניות, על מאגרים שיכולים להכיל מיליוני מונחים אפשריים. איך מערכת מוצאת את כל המילים הרלוונטיות כל כך מהר, ולפי איזה סדר היא מחליטה מה להציג ראשון?
למה חיפוש רגיל לא מספיק מהיר בשביל זה¶
הפתרון הנאיבי הוא לעבור על כל המילים במאגר, ולבדוק לכל אחת אם היא מתחילה באותיות שהוקלדו עד כה. זה עובד, אבל ככל שהמאגר גדל, זה נהיה איטי - ולזה יש לצרף עוד בעיה, שהחיפוש הזה קורה מחדש בכל תו נוסף שמקלידים, לא פעם אחת בסוף. בשביל חוויית משתמש שמרגישה מיידית, צריך מבנה נתונים שנבנה מראש בדיוק בשביל השאלה "אילו מילים מתחילות בקידומת הזאת".
עץ הקידומות - Trie¶
מבנה הנתונים הקלאסי לבעיה הזאת נקרא Trie, עץ קידומות. הרעיון - במקום לשמור מילים כמחרוזות שלמות, בונים עץ שבו כל צומת מייצג אות בודדת, ומסלול מהשורש עד לצומת מסוים מייצג קידומת מסוימת. אם שתי מילים חולקות את אותן אותיות בהתחלה, למשל "פיצה" ו"פיצוץ", המסלול המשותף שלהן בעץ, "פיצ", מיוצג פעם אחת בלבד, ורק בנקודה שבה הן מתחילות להיבדל, "ה" מול "ו", העץ מתפצל לשני ענפים נפרדים.
כשמישהו מקליד "פיצ", האלגוריתם פשוט הולך בעץ מהשורש, אות אחר אות, לפי מה שהוקלד - פ, אחר כך י, אחר כך צ - ומגיע לצומת ספציפי אחד. משם, כל מה שצריך לעשות זה לאסוף את כל המילים ששלמות שנמצאות בתת-העץ שמתחת לצומת הזה, וזה בדיוק כל המילים שמתחילות ב"פיצ". שלב הירידה בעץ תלוי רק באורך הקידומת שהוקלדה, לא בכמות המילים הכוללת במאגר, וזו בדיוק הסיבה שהחיפוש הזה נשאר מהיר גם עם מיליוני מילים.
מה קורה כשמגיעים לצומת - איך אוספים את ההצעות¶
ברגע שמגיעים לצומת שמייצג את הקידומת המבוקשת, עדיין יכולות להיות שם עשרות או מאות מילים אפשריות שמתחילות באותה קידומת. תיבת חיפוש לא יכולה להציג את כולן - היא צריכה לבחור, בדרך כלל, בין שלוש לחמש הצעות בלבד. כאן נכנס שלב הדירוג.
דירוג ההצעות - למה מילה אחת מנצחת אחרת¶
הבחירה איזו הצעה תופיע ראשונה כמעט אף פעם לא אלפביתית. מנועי חיפוש שומרים לצד כל מילה בעץ ניקוד שמשקלל כמה גורמים - כמה פעמים חיפשו את המילה הזאת בעבר (פופולריות כללית), כמה פעמים המשתמש הספציפי הזה חיפש אותה (התאמה אישית), ולפעמים גם הקשר עדכני יותר כמו טרנדים. במקום לשמור רשימה שטוחה של כל המילים תחת קידומת, מערכות בפועל שומרות בכל צומת בעץ כבר את קבוצת ההצעות המובילות שמתחתיו, מעודכנת מראש, כדי לא לצטרך לחשב דירוג מחדש בכל הקלדה.
איפה עוד רואים את אותו רעיון¶
עץ קידומות לא ייחודי לתיבות חיפוש. הוא מופיע בבדיקות איות (spell check), בהשלמת פקודות בטרמינל, בניתוב IP ברשתות (איפה שהקידומת המדויקת ביותר קובעת את הניתוב, כמו שראינו בפוסט על נתבים), ובכל מקום אחר שבו השאלה החוזרת היא "מה מתחיל באותה קידומת". ברגע שמזהים את התבנית הזאת, מבינים שזה בדיוק אותו רעיון שחוזר שוב ושוב בהקשרים שונים לגמרי.
בקורס התכנות הבסיסי שלנו עוברים על מבני נתונים בסיסיים כמו עצים ורשימות, ובונים בהדרגה את ההבנה שמאפשרת לזהות מתי מבנה נתונים ספציפי הוא בדיוק הכלי הנכון לבעיה.
קורס התכנות הבסיסי שלנו בונה את ההבנה הזאת שלב אחר שלב.
יש לכם שאלה על מבני נתונים או מתי להשתמש באיזה? שאלו בדיסקורד.
לסיכום¶
תיבת חיפוש לא "מנחשת" באופן מסתורי מה תרצו להקליד - היא נשענת על עץ קידומות שבנוי מראש, שמאפשר לקפוץ ישר לכל המילים הרלוונטיות בלי לסרוק את כל המאגר, ועל דירוג פופולריות שקובע אילו הצעות מתוך כל האפשרויות באמת שוות הצגה. שילוב של מבנה נתונים חכם וסדר עדיפויות נכון הוא בדיוק מה שהופך את זה להרגיש מיידי.