מדריך | קצת על איך מנוע חיפוש בנוי - הרבה יותר פשוט ממה שחשבתם
-
זוהי כתבה שרציתי לכתוב כבר הרבה זמן היום קצת אין לי כח לתיכנות אז הנה הכתבה
המושג אינדקס
המושג אינדקס (Inverted Index)
מנוע חיפוש מיישם אינדקס פשוט למדי שמאפשר לענות על השאילתה "אילו ספרים מכילים את המילים הללו?" כמעט באופן מיידי.
במקום לעבור על כל ספר בצורה ליניארית – פעולה שעלולה לקחת זמן רב – הוא פשוט בודק באינדקס באילו ספרים כל מילה מופיעה, ומחזיר את התוצאה במהירות.
שיטת הניקוד
שיטת הניקוד
מנועי חיפוש קלאסיים מיישמים בדרך כלל אלגוריתם שנקרא Term Frequency (TF). הרעיון הוא שככל שמילה מופיעה יותר פעמים באותו מסמך, כך סביר יותר שהמסמך רלוונטי לחיפוש.
זוהי הנחה טובה מאוד עבור מסמכים רגילים, אך לדעתי היא פחות מתאימה לזירה התורנית, שבה לעיתים דווקא אזכור בודד במקום המדויק הוא החשוב ביותר.
בגוגל מיושם כמובן גם ניקוד לפי פרמטרים נוספים, כגון פופולריות, סמכות הדף, מוניטין ועוד. בזית מיושם ניקוד גם לפי פרמטרים ייעודיים לעולם התורני, כגון ספרי יסוד וכדומה.
כיצד התוצאות מחושבות
המנוע צריך למצוא במהירות את החיתוך בין רשימות המסמכים של המילים שבשאילתה – כלומר אילו מסמכים מכילים את כולן.
הרעיון המרכזי נקרא leap-frog ("קפיצת צפרדע"): במקום לעבור על שתי הרשימות במקביל איבר אחר איבר, לוקחים את הערך הנוכחי ברשימה האחת ו"דוהרים" קדימה ברשימה השנייה בקפיצות הולכות וגדלות עד שעוברים את הערך המבוקש, ואז מצמצמים בחיפוש בינארי על הטווח שנותר. שיטת הקפיצות האקספוננציאליות הזו נקראת Galloping Search. לאחר מכן מחליפים תפקידים בין הרשימות וחוזר חלילה. כך, כאשר רשימה אחת קצרה משמעותית מהשנייה, מדלגים על נתחים ענקיים של הרשימה הארוכה כמעט מבלי לגעת בהם.
איך זה עובד מאחורי הקלעים (פירוט טכני):
בפועל הרשימות (postings) שמורות בצורה דחוסה (Delta + VarInt – ראו בהמשך), כך שאין אליהן גישה אקראית: "התקדמות" ליעד מסוים מתבצעת על ידי פענוח הזרם קדימה. אסטרטגיית ה-Galloping וה-leap-frog עובדת גם כך – פשוט מפענחים קדימה עד שעוברים את הערך המבוקש.
כדי להוזיל את הקפיצות הגדולות קיימת אופטימיזציה בשם Skip List (מפורט בהמשך): נקודות עצירה דלילות הנשמרות מראש ומאפשרות לדלג מעל נתחים שלמים בלי לפענח אותם. זוהי אופטימיזציה שלא תמיד נדרשת – עבור רשימות קצרות הפענוח קדימה מהיר דיו.
Roaring Bitmaps
אבל כאשר רשימות ההופעות ארוכות מאוד, גם הדילוג בעזרת ה-Skip List מתחיל לאבד מיעילותו יחסית. במקרים כאלה משתמשים לעיתים ב-Roaring Bitmaps – שיטה שמייצגת את המסמכים כרצף של ביטים ומאפשרת לחשב חיתוכים במהירות גבוהה במיוחד.
איך Roaring Bitmaps עובדים (פירוט טכני):
כדי להבין כיצד הם עובדים, צריך להבין מהו Bit. ביט הוא יחידת המידע הקטנה ביותר במחשב, והוא יכול להכיל רק 0 או 1.
במקום לשמור רשימת מזהי מסמכים, ניתן להקצות ביט אחד לכל מסמך:
- 1 – המסמך מכיל את המילה.
- 0 – המסמך אינו מכיל את המילה.
לדוגמה:
מסמך: 1 2 3 4 5 6 7 8 ביטים: 1 0 1 0 0 1 1 0את החיתוך בין שתי מילים ניתן לחשב באמצעות פעולת AND על שני מערכי הביטים. מכיוון שהמעבד מבצע פעולות על עשרות ואף מאות ביטים במקביל, הוא למעשה משווה כמות גדולה של מסמכים בפעולה אחת, ולכן החישוב מהיר מאוד.
כדי שלא לבזבז זיכרון על מיליוני ביטים שערכם 0, Roaring Bitmaps דוחסים את המידע בצורה חכמה (חלוקה לבלוקים ממוענים) ועדיין מאפשרים לבצע את פעולות ה-AND במהירות גבוהה. מכיוון שהבלוקים ממוענים, יש כאן דווקא גישה אקראית אמיתית – ולכן דילוג בין בלוקים (block-jump) הוא מקום שבו טכניקה בסגנון Galloping כן ישימה ומועילה.
למרות זאת, ברוב מנועי החיפוש הדילוג הרגיל (Galloping, לרוב בעזרת Skip List) עדיין מהיר יותר ברוב החיפושים, משום שרוב רשימות ההופעות אינן גדולות מספיק כדי להצדיק את העלות והמורכבות של Roaring Bitmaps. לכן נהוג להשתמש בו כברירת מחדל, ולעבור ל-Roaring Bitmaps רק עבור רשימות ענק וצפופות במיוחד.
Skip Lists
Skip Lists (או Skip Pointers) הם אופטימיזציה של אסטרטגיית ה-Galloping, ולא תמיד נעשה בהם שימוש. הרעיון פשוט: מוסיפים לרשימה "נקודות קפיצה" מראש, כך שבמקום לפענח את הזרם הדחוס קדימה עד היעד, אפשר לדלג ישר לאזור הרלוונטי ולחסוך את הפענוח המיותר. עבור רשימות קצרות פענוח קדימה מהיר דיו, ולכן לא תמיד מוסיפים Skip List.
פרטי המימוש (טכני):
כל כמה ערכים נשמר מצביע (offset בקובץ) יחד עם הערך שאליו הוא מצביע. כך אפשר לאתר במהירות (למשל בחיפוש בינארי על נקודות הקפיצה) את הבלוק הרלוונטי, ולפענח החל ממנו בלבד – במקום להתקדם ולפענח איבר אחר איבר מתחילת הרשימה.
בספריות כמו Lucene זהו בדיוק המנגנון שמשמש להתקדמות (
advance) על פני postings מדוחסים על הדיסק, בדרך כלל במבנה רב-שכבתי (multi-level skip list). Galloping Search כן מופיע במנועי חיפוש, אך רק מעל מבנים עם גישה אקראית אמיתית (כגון מערכים מפוענחים בזיכרון או מבני DocIdSet) – לא מעל זרם הבתים הדחוס עצמו.דחיסת הנתונים
דחיסת הנתונים
מנוע החיפוש חייב לדחוס את הנתונים המספריים, אחרת האינדקס יתפח במהירות לממדים עצומים הן בשטח הדיסק והן בזיכרון.
שיטות הדחיסה (טכני):
אחת משיטות הדחיסה הנפוצות נקראת Delta + VarInt: במקום לשמור כל מספר במלואו, שומרים רק את ההפרש מהמספר הקודם. מכיוון שההפרשים בדרך כלל קטנים, ניתן לקודד אותם באמצעות VarInt, שתופס מעט מאוד בתים עבור מספרים קטנים. השיטה פשוטה, מהירה ויעילה מאוד.
ישנן גם שיטות מודרניות יותר הדוחסות את הנתונים בבלוקים, בדרך כלל של 128 ערכים. מעבר לדחיסה טובה יותר, הן מאפשרות לעיתים לדלג על בלוק שלם כאשר ברור שאין בו תוצאה רלוונטית.
מקטעים
מקטעים (Segments)
כשמסתכלים לראשונה על מבנה האינדקס, קל להיבהל מכך שהוא אינו קובץ אחד רציף אלא מורכב ממספר מקטעים (Segments) נפרדים. אבל אין בכך שום דבר מפחיד – זוהי תוצאה טבעית של הדרך היעילה לכתוב לדיסק.
הסיבה היא שכתיבה לדיסק פריט אחר פריט היא איטית מאוד. במקום זאת, המסמכים נצברים תחילה בזיכרון (buffer), וכאשר הוא מתמלא, כל התוכן נכתב לדיסק בבת אחת כמקטע חדש – פעולה הנקראת Flush. כתיבה מרוכזת (batch) של הרבה נתונים בבת אחת מהירה בהרבה מאלפי כתיבות קטנות ונפרדות, ולכן שלב ה-Flush הוא הכרחי לביצועים טובים.
כל מקטע הוא בפני עצמו אינדקס קטן ושלם, שאינו משתנה עוד לאחר שנכתב (immutable). בזמן חיפוש, המנוע פונה לכל המקטעים ומאחד את התוצאות. מכיוון שכל Flush יוצר מקטע נוסף, עם הזמן מצטברים מקטעים רבים – וריבוי מקטעים מאט את החיפוש.
LSM ומיזוג מקטעים
הפתרון הוא מיזוג (Merge): מדי פעם מאחדים כמה מקטעים קטנים למקטע אחד גדול יותר. בכתבי הקודש בחרתי בגישת מיזוג בסגנון LSM (Log-Structured Merge tree), שהיא בטוחה וחכמה במיוחד.
עיקר החוכמה של LSM הוא שהמיזוג מתרחש בדיוק בקצב הנכון – לא תכוף מדי (שיבזבז משאבים על כתיבה חוזרת של אותם נתונים) ולא נדיר מדי (שיותיר יותר מדי מקטעים ויאט את החיפוש) – בזכות ארגון המקטעים ברמות (levels).
כיצד מבנה הרמות עובד (טכני):
המקטעים מאורגנים בשכבות לפי גודלם. כל Flush יוצר מקטע קטן ברמה הנמוכה ביותר, וכאשר מצטברים ברמה מסוימת מספיק מקטעים בגודל דומה, הם מתמזגים יחד – והתוצאה, מקטע גדול יותר, "מקודמת" (bump) לרמה הבאה מעליה. וכך הלאה: הרמות הגבוהות מחזיקות מעט מקטעים גדולים, והרמות הנמוכות הרבה מקטעים קטנים.
התוצאה היא שמיזוגים קטנים ותכופים מתבצעים ברמות הנמוכות, ומיזוגים גדולים ויקרים מתבצעים לעיתים רחוקות בלבד ברמות הגבוהות – כך שקצב המיזוג מאוזן מאליו לפי כמות הנתונים שנצברה.
הבסיס לכל זה הוא ש-LSM היא שיטה של הוספה בלבד (append-only): לעולם לא עורכים מקטע קיים במקומו, אלא רק כותבים מקטעים חדשים. וזהו בדיוק הסוד למהירות – כתיבה רציפה של נתונים חדשים מהירה בהרבה מעדכון מפוזר של קובץ קיים, וגם בטוחה יותר: מכיוון שהמקטעים אינם משתנים, גם אם התהליך נקטע באמצע (קריסה או הפסקת חשמל), הנתונים הקיימים נשארים שלמים ואין סכנה לאיבוד מידע או להשחתת האינדקס.
החשיבות של נתונים ממוינים
תנאי הכרחי לכל המנגנון הזה הוא שהנתונים בכל מקטע יהיו ממוינים לפי מזהה המסמך. המיזוג עצמו אפשרי רק בזכות המיון: איחוד שני מקטעים ממוינים למקטע ממוין אחד הוא פעולה יעילה מאוד (בדומה למיזוג שתי רשימות ממוינות), הנעשית במעבר אחד בלבד. ללא מיון, המיזוג היה דורש מיון מחדש של כל הנתונים בכל פעם.
המיון חשוב לא פחות גם לחישוב תוצאות החיפוש: כל האלגוריתמים שתוארו למעלה (Skip List, leap-frog, חיתוך רשימות) מניחים שרשימות ההופעות ממוינות לפי מזהה. לכן כל מסמך חייב מזהה מספרי יציב שלפיו ממיינים.
במנועי חיפוש קלאסיים מקצים לכל פריט מזהה (id) פנימי משלהם. בכתבי הקודש בחרתי שלא ליצור מזהה חדש, אלא להשתמש במזהה השורה המובנה (line id) הקיים ממילא בקובץ
seforim.db– כך המזהה כבר קיים, יציב, ומקשר ישירות בין תוצאות החיפוש למקור בטקסט.חיפוש משודרג
חיפוש משודרג
רוב מנועי החיפוש תומכים גם בחיפוש תחיליות, סיומות, חיפוש מטושטש ועוד. לשם כך הם משתמשים בדרך כלל במבנה נתונים קומפקטי בשם FST (Finite State Transducer).
זהו מעין עץ שבו מילים בעלות תחילית משותפת חולקות את אותו נתיב, כך שנמנעות כפילויות ונחסך זיכרון רב. החיסרון הוא שבדרך כלל יש לטעון את מבנה הנתונים לזיכרון, דבר שדורש זמן אתחול וצריכת RAM נוספת.
בכתבי הקודש בחרתי להשתמש ב-SQLite, שמממש אינדקס מסוג B-Tree. גם כאן החיפוש לפי תחילית מהיר מאוד, אך אין צורך לטעון את כל מילון המילים מראש לזיכרון.
המעלה הגדולה של FST היא תמיכה טבעית בחיפוש מטושטש, בזכות המבנה שלו. ב-SQLite יכולת זו אינה מובנית.
החיסרון המשותף לשתי הגישות הוא חיפוש לפי סיומת או תת-מחרוזת: כאשר תחילת המילה אינה ידועה, אין לעץ נקודת התחלה יעילה.
N-Grams
הפתרון הקלאסי לבעיה זו הוא N-Grams. במקום לאנדקס רק מילים שלמות, מפרקים כל מילה למקטעים קצרים, למשל באורך 3 תווים, ומאנדקסים גם אותם.
לדוגמה:
ברכות ברכ רכו כותכך ניתן למצוא גם רצפים המופיעים באמצע המילה.
בכתבי הקודש לא הסתפקתי בטבלת N-Grams רגילה, אלא בניתי מבנה נתונים דחוס במיוחד שמייצג את כל ה-Grams בצורה קומפקטית.
בעיית הגזירים
בעיית הגזירים
רוב מנועי החיפוש יודעים לייצר גזירים (Snippets), אך הדבר בדרך כלל מחייב לשמור גם את תוכן המסמך בתוך האינדקס, מה שמגדיל אותו משמעותית ויוצר כפילות נתונים.
אפשר כמובן לבנות אינדקס "רזה" שאינו שומר את הטקסט, אך אז יש לחשב את הגזיר בזמן אמת, פעולה שאינה מהירה במיוחד.
חיסרון נוסף הוא שרוב מנועי החיפוש אינם מספקים גישה ישירה לרשימת המילים שהתאימו לשאילתה. לעיתים ניתן לקבל מידע זה, אך רק באמצעות שאילתה נוספת.
בכתבי הקודש, כבר בתחילת החיפוש נטענות כל המילים שהתאימו לשאילתה יחד עם מיקומן, ולכן ניתן לייצר גזירים במהירות, בגמישות ובדיוק רב.
Tokenization
שלב ה-Tokenization אחראי להחליט כיצד הטקסט יחולק למילים שהאינדקס ישמור.
במאגר של אוצריא קיימת מורכבות מיוחדת, משום שיש לטפל בראשי תיבות, סימנים, קיצורים וצורות כתיב שונות. לכן נדרש Tokenizer חכם שיודע לזהות נכון מהי מילה.
Token Stream
כדי לייצר גזירים נוסף שלב נוסף: בתוך החלוקה למילים נשמר גם המיקום המדויק של כל מילה במסמך. מידע זה נקרא Token Stream.
המידע הזה מאפשר לייצר גזירים מדויקים, להדגיש את המילים שנמצאו בתוצאות החיפוש, ולבצע זאת ללא צורך לסרוק מחדש את הטקסט כולו.
החישוב הזה מאפשר גם לסנן תוצאות לפי םרמטרים של מרחק בי מילים וכיו"ב
מנועי חיוש מודרניים שומרים את כל המידע הזה כבר בעת האינדוקס - אני בחרתי לא לעשות זאת עקב שיקולים של חסכון משמעותי בנפח דיסק.
לסיכום
לסיכום
בסופו של דבר, מנוע חיפוש קלאסי מורכב ממספר רעיונות פשוטים יחסית:
- Inverted Index – האינדקס ההפוך שממפה מילים למסמכים
- דחיסת נתונים – Delta + VarInt ודחיסה בבלוקים
- Galloping / Leap-frog – אסטרטגיית הדילוג האקספוננציאלי לחיתוך מהיר בין רשימות ממוינות
- Skip Lists – אופטימיזציה שמאיצה את הדילוג על רשימות דחוסות ארוכות (לא תמיד נדרשת)
- Roaring Bitmaps – חיתוך יעיל עבור רשימות ענק וצפופות, עם דילוג בסגנון Galloping בין בלוקים ממוענים
כל השאר הם בעיקר שיפורי ביצועים ותכונות נוספות.
@pcinfogmach
וואו!!
בערך שנה אני מחכה שתכתוב את זה...
עוד לא קראתי, אבל תודה רבה!! -
@pcinfogmach
וואו!!
בערך שנה אני מחכה שתכתוב את זה...
עוד לא קראתי, אבל תודה רבה!! -
@הבל-הבלים פיתחת מנוע חיפוש בלי להבין איך הוא עובד?
@המלאך
אני לא פיתחתי מנוע חיפוש.
וגם השיפורים שעשיתי - הרבה מהם בזכות התכתבויות עם @pcinfogmach .
וגם כשאני מבין ברמה מסוימת איך משהו עובד - הנגשה ברורה ממקצוען - זה תענוג. -
@המלאך
אני לא פיתחתי מנוע חיפוש.
וגם השיפורים שעשיתי - הרבה מהם בזכות התכתבויות עם @pcinfogmach .
וגם כשאני מבין ברמה מסוימת איך משהו עובד - הנגשה ברורה ממקצוען - זה תענוג. -
@הבל-הבלים ואז מתלונן כשמישהו נוגע לך במשהו.
@המלאך
לא אכפת לי שייגעו, אבל שיגידו לי מה עשו ולמה..
[אגב, זה כבר עבר לפלמוני שאין לי מושג איך הוא עושה הכול ביחד..] -
@המלאך
לא אכפת לי שייגעו, אבל שיגידו לי מה עשו ולמה..
[אגב, זה כבר עבר לפלמוני שאין לי מושג איך הוא עושה הכול ביחד..] -
לפלמוני שאין לי מושג איך הוא עושה הכול ביחד..]
-
@המלאך
לא אכפת לי שייגעו, אבל שיגידו לי מה עשו ולמה..
[אגב, זה כבר עבר לפלמוני שאין לי מושג איך הוא עושה הכול ביחד..] -
@המלאך
עד עכשיו ידעתי שיש אחד, מה שחדש לי זה שיש שנים. -
@הבל-הבלים לא, הוא "המלאך" בה"א הידיעה
-
@המלאך
אני לא פיתחתי מנוע חיפוש.
וגם השיפורים שעשיתי - הרבה מהם בזכות התכתבויות עם @pcinfogmach .
וגם כשאני מבין ברמה מסוימת איך משהו עובד - הנגשה ברורה ממקצוען - זה תענוג.@המלאך
אני לא פיתחתי מנוע חיפוש.
וגם השיפורים שעשיתי - הרבה מהם בזכות התכתבויות עם @pcinfogmach .
וגם כשאני מבין ברמה מסוימת איך משהו עובד - הנגשה ברורה ממקצוען - זה תענוג.הרוב פה לא רוולונטי אלא בתור תיאוריה בעלמא
בנוגע לאיך להשתמש במנועי חיפוש יש שפה שכדאי להכיר ומושגים ומונחים שהם משתמשים בהם.
רוב מה שכתבתי פה לא רלונטי כלל אם אתה משתמש במנוע חיפוש כמו lucene או טנטיביטי.
שלום! נראה שהשיחה הזו מעניינת אותך, אבל עדיין אין לך חשבון.
נמאס לכם לגלול בין אותם הפוסטים בכל ביקור? כשנרשמים לחשבון, תמיד תחזרו בדיוק למקום שבו הייתם קודם, ותוכלו לבחור לקבל התראות על תגובות חדשות (בין אם במייל, ובין אם בהתראת פוש). תוכלו גם לשמור סימניות ולפרגן ב-upvote לפוסטים כדי להביע הערכה לחברי קהילה אחרים.
בעזרת התרומה שלך, הפוסט הזה יכול להיות אפילו טוב יותר 💗
הרשמה התחברות