בתשובה לג'וד, 19/06/11 11:33
אינדוקס 573692
אפופידס • בתשובה לג'וד יום א', 19/6/2011, 21:32
אתייחס רק לנקודה ספציפית, אך המרכזית לעובדה שמנועי חיפוש מסוגלים לספק במהירות את רשימת המסמכים המכילים מילה או צירוף מילים שנשלחו אליהם ע"י משתמשים. הדברים מובאים כמובן בנוסח פשטני ולא תמיד מדוייק.

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

זהו גם עיקר סודה של השליפה המהירה ע"י מנוע חיפוש. עבור כל מילה בה נתקל מנוע האינדוקס בתוך דפי האינטרנט שהורדו אליו מבעוד מועד, הוא שומר בצד את רשימת המספרים שהוא העניק לכל עמוד שהורד אליו (נניח, לפי סדר ההורדה של העמוד):
….
sambusak: 1, 5, 103, 104, 105, 244, 296
samsung: 3, 200, 244, 245, 296, 301
….
עתה, בהינתן שאילתת חיפוש הכוללת את המילה sambusak, לא צריך מנוע החיפוש לנדוד ברחבי הרשת בחיפושיו, ואף לא לקרוא את הדפים שכבר הורדו ממנה. כל שנדרש ממנו עתה הוא לגלות היכן איכסן מנגנון האינדוקס את רשימת העמודים עבור המילה sambusak, פעולה אותה ניתן לבצע באופן מיידי (חפשי למשל hash table), ולהחזיר את הרשימה למשתמש. טוב, לא בדיוק, הרי למשתמש אין מה לעשות עם רשימת המיספורים הפנימיים של המערכת. אז במקום לחזור למשתמש, עובר לפני כן המנוע אל טבלה נוספת, בה נמצא במקום הראשון הקישור לדף מספר אחת, במקום שני הקישור אל דף מספר 2 שהורד מן הרשת וכן הלאה. הוא ניגש עם 20 המספרים הראשונים (נניח) שברשימה, ניגש אל 20 המקומות המתאימים בטבלת הקישורים, שולף מן הטבלה את 20 הקישורים המתאימים וחוזר עמם אל המשתמש.

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

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

-------------------------------------------------------------------------------------------------------------------------------------
‏1 ליתר דיוק, כאשר מדובר בספר, כולל האינדקס רק את המילים שעורך הספר חפץ ביקרן, אבל במנוע חיפוש מדובר בכמעט כולן.
‏2 ישנן שיטות החוסכות את רוב פעולת ההצלבה (skip list) כך שזה יכול להגיע גם למיקרושניות עבור מיליון מופעים
אינדוקס 573698
247 • בתשובה לאפופידס יום א', 19/6/2011, 22:38
רק הערה קטנה:

שאלתי פעם פרופסור (עוסק בנושא רלוונטי) בטכניון, והוא אמר לי שלגוגל יש מעבר לאינדקס גם "עותק" (בנוסף לאינדקס) של האינטרנט לשם הפעלת אלגוריתמי הפייג' ראנק.
אינדוקס 573699
אפופידס • בתשובה ל247 יום א', 19/6/2011, 23:10
כמובן. בד"כ למנוע חיפוש שאינו "טפילי" ישנו עותק של כל המסמכים אותם הוא אינדקס, ולו כדי להחזיר ברשימת התוצאות גם את השורה בה מופיעה מילת/שאילתת החיפוש, על מנת לסייע למשתמש להחליט על מה ללחוץ ולחסוך לו זמן. אני מניח שבגוגל משתמשים בעותק זה גם בשביל המטרה אותה ציינת.
אינדוקס 573703
אייל סתם • בתשובה לאפופידס יום ב', 20/6/2011, 0:24
מה שאני מתקשה להבין זה איך גוגל מוצאים ביטויים מדוייקים (כאלה בתוך גרשיים) ומהר? הם פשוט עוברים על כל הדפים שבהם נמצאות כל המילים בביטוי ומחפשים את הצירוף?
אינדוקס 573765
אפופידס • בתשובה לאייל סתם יום ב', 20/6/2011, 22:47
כאמור, בפועל שומרים באינדקס של כל מילה לא רק את ה-ID (מספר מזהה) של כל דף html בו היא מופיעה, אלא גם את מיקומיה בו. אם נחזור לדוגמא שנתתי, בפועל יראה מאגר האינדקסים קרוב יותר לזה:
sambusak: *1, 74, 90, *5, 2, 10, 100, *103, 11, 50, *104, 10, ....
samsung: *3, 2, 5, *103, 12, 58, *200, 89, 244....
כאשר כוכבית מציינת שמדובר במספר דף ואילו ללא כוכבית, הכוונה למספר המילה בדף (ראשונה, שניה, שלישית,...).
משום כך, אם חפצה נפשך בדפים הכוללים איזכורים של דגם החכמופון החדש "sambusak samsung", ירוץ המנוע במקביל לאורך שתי הרשימות (וכאמור, עבור רשימות המציינות מיליוני מסמכים בהם מופיעות שתי המילים זה לוקחת שברירי שניה), ויגלה שבדף מספר 103 המילה ה-‏11 היא sambusak בעוד שהמילה ה-‏12 באותו דף html היא samsung - בינגו!
אינדוקס 573773
ידידיה • בתשובה לאפופידס יום ג', 21/6/2011, 3:48
הגאון כבר מצליח למצוא sambusak samsung, אבל נכון לזמן כתיבת תגובה זו, עדיין לא את "sambusak samsung".
אינדוקס 573780
צפריר כהן  (אתר) • בתשובה לידידיה יום ג', 21/6/2011, 10:01
באותו עניין: ראו לדוגמה את ויקיפדיה:מזנון/ארכיון 250#נפלאות גוגל [ויקיפדיה]‏1 שם הצלחתי בינתיים בקרב נגד Google.

‏‏1 אין אפשרות ליצור <קישור> שמצביע לתוך ויקיפדיה העברית.
אינדוקס 573708
סתם מישהו • בתשובה לאפופידס יום ב', 20/6/2011, 5:11
תודה על ההסבר.
אינדוקס 573764
אפופידס • בתשובה לסתם מישהו יום ב', 20/6/2011, 22:31
(:
אינדוקס 573709
ג'וד • בתשובה לאפופידס יום ב', 20/6/2011, 6:54
תודה, זה מאד מעניין, עד אתמול, אחרי ששאלתי אותך, לא עלה בדעתי שגוגל מאנדקסת כל מילה ומילה. הם הראשונים שעשו את זה? אתה מתעסק בדטה בייסים? עשיתי פעם קורס על אורקל, זה היה קורס קשה ושכחתי הכל מאלף עד תו. אחד הדברים הכי מסובכים היה הגיבויים. גם גוגל צריכה לגבות כל הזמן.

מצאתי בלוג מעניין על גוגל. מסופר למשל שה crawler מאחסן 850 TB של מידע (TB אחד שווה 1024 ג'יגה בייט), זו מן הסתם הטבלה שאתה דיברת עליה, נכון? האינדקס שבנוי מכל המילים מסודרות לפי הסדר, עם פוינטר ל URL וגם ציון המקומות שהמילה מופיעה בתוך הטקסט.
זה גודלה של כל הרשת? נשמע קטן.
אז איך פיזית מחפשים במהירות בתוך אינדקס כל כך גדול? הוא יושב על דיסקים או בזכרון? אולי הוא מחולק לדיסקים שונים? כשאני שואלת משהו את גוגל, לאן מופנית השאלה, לכולם?
אתה לא חייב לענות, המוח מסתחרר ממחשבות על גוגל על הבוקר.

בבלוג הזה מסופר גם שגוגל בודקת ממשק חדש בלי כפתור I'M FEELING LUCKY. ברוך השם, מעולם לא לחצתי עליו שלא בטעות.
אינדוקס 573763
אפופידס • בתשובה לג'וד יום ב', 20/6/2011, 22:30
1. רעיון האינדוקס הממוכן קדם בהרבה לגוגל (ואף לאינטרנט). עליו התבסס כל מנוע חיפוש, עד כמה שידיעתי מגעת, ובפרט אלו של יאהו, אלטה-ויסטה ואחרים שקדמו לזה של גוגל.
2. אין לי נגיעה בדטה בייסים. פעם הייתה עוינות הדדית אבל היום אנחנו כבר מיודדים, אם כי עדיין בלי הקטע הפיסי.
3. אכן גם גוגל צריכה לשמור גיבויים, אם כי אולי זה קורה מאליו, מעצם העובדה שכל מידע שמשמש את מנוע החיפוש משוכפל להרבה מכונות, כדי לתמוך בריבוי משתמשים. כך, כאשר מכונה קורסת, וזה כידוע עניין של זמן עד שזה קורה, ממשיכות לפעול המכונות עם העותקים האחרים של חלק המידע שנעלם.
4. נראה לי שהמידע שמאכסן ה-crawler שהזכרת הוא הדפים בשלמותם, ולא הטבלה שהזכרתי. אגב, בפועל, המילים לאו דווקא מסודרות אלפא-בייתית, אלא באמצעות Hash_table [Wikipedia] (אם ההסבר שם לא מספיק אנסה לפשט את הרעיון המגניב הזה).
5. נדמה לי שאצל גוגל הוא יושב בזיכרון. זכרי שגישה לזיכרון היא עניין של עשר נאנו-שניות (כנראה). כמובן, כל המידע הזה מחולק לחלקים קטנים ומפוזר על מאות אלפי מכונות, כדי לזרז את העניינים, ונתבים היודעים לזהות במהירות אל איזו קבוצה להפנות שאילתא נתונה. אם אני זוכר נכון, כל שאילתא מופנית אל יותר מקבוצה אחת, וזו שחוזרת קודם לנתב - חוזרת אל עוד לקוח מרוצה.

לילה טוב!
אינדוקס 573784
אייל אלמוני • בתשובה לאפופידס יום ג', 21/6/2011, 11:45
לפני ימים אחדים חיפשתי שם מסוים בגוגל, שם של אישה שהיא פרופסור. לצערי אינני זוכר מהו, אבל כשרשמתי את השם המלא לבדו קיבלתי פחות ממאה תוצאות. כשרשמתי גם "פרופ"' (הכל במרכאות כמובן) קיבלתי אלפי תוצאות. תופעה כזו כבר קרתה לי מספר פעמים עם צירופים אחרים. אתה מבין איך זה יכול לקרות?
אינדוקס 573788
אפופידס • בתשובה לאייל אלמוני יום ג', 21/6/2011, 12:09
מוזר. אשמח לבחון דוגמא כזו.

זה מזכיר לי שכל פעם אני צריך להסביר מחדש למי שהגיון החיפוש הממוכן זר לו, שאם לא חזרו תוצאות או שהן מעטות מדי ולא מכילות את המבוקש, אזי הוספת דרישות, למשל מילת חיפוש נוספת על אלו שניתנו, לא "תעזור" למנוע. זאת בניגוד לאופן בו היינו נוהגים במקרה של חפשן אנושי (נניח ספרן לפני שלושים שנה, או מחפש אוצרות של שודדי ים). אצל אדם, הוספת פרטים על אלו שכבר ניתנו ולא הניבו דבר, יכולה רק לעזור. הסיבה היא כפולה: המנוע מחפש כבר בפעם הראשונה בכל המקומות ולכן הוספת פרטים יכולה רק לכווץ את רשימת התוצאות, ולא לכוון אותו למקומות חדשים. הסיבה השניה היא שהמנוע מחפש במדוייק את מה שנשאל, ואם אין אז אין. אילו אדם, אם תוסיף לו פרטים, לוקח בחשבון שחלק מהם עשוי להיות לא מדוייק (למשל תורכיה לעומת טורקיה או כתיב מלא לעומת חסר) ולכן אם אין תוצאות הוא יתעלם מהם או ימיר אותם לצורה אחרת שאותה הוא יחפש. לזה יש סייג, מאחר ומנגנוני החיפוש מסוגלים במידה מסויימת כבר היום לחפש באופן לא מדוייק, ע"י תיקון שגיאות כתיב, התחשבות בהטיות ובמילים דומות.
אינדוקס 573791
דורון הגלילי • בתשובה לאפופידס יום ג', 21/6/2011, 12:33
למה? המנוע לא מכיר פונקצית OR?
אינדוקס 573795
אפופידס • בתשובה לדורון הגלילי יום ג', 21/6/2011, 12:56
המנוע כן, המשתמש המבוגר הממוצע פחות.
אינדוקס 573797
אייל אלמוני • בתשובה לדורון הגלילי יום ג', 21/6/2011, 13:13
המנוע מכיר את הפונקציה, אבל הוא לא אמור להפעיל אותה כשרושמים את המלים לחיפוש במרכאות. כעת נכון שבחודשים האחרונים הוא משום מה עושה גם את מה שאינו אמור לעשות, אבל מקרים כאלה קרו לי גם לפני שנים אחדות - כאשר לא עשה זאת. יותר מזה, כשרשמתי עכשיו (בדוגמא זו) את השם יחד עם התואר, התוצאות הראשונות שהופיעו היו שונות מאלה הראשונות בלי התואר - לפחות בעמודים הראשונים לא היה שימוש ב''או''.
אגב, לא ברור לי גם למה הוחלט להתעלם מהמרכאות, ואם יש דרך אחרת לקבל רק את התוצאות של ''ו-''. מאוד מרגיז.
אינדוקס 573806
ג'וד • בתשובה לאייל אלמוני יום ג', 21/6/2011, 13:34
אם אינני טועה, הוא תמיד מסדר לך את התוצאות לפי מידת ההתאמה לשאלה שלך.
אני מוצאת שזה ידידותי מצדו כי השאלות שלי לא תמיד הכי חכמות.
אינדוקס 573811
אייל אלמוני • בתשובה לג'וד יום ג', 21/6/2011, 14:34
הוא אכן מסדר את התוצאות על פי מידת ההתאמה, אבל מה ההבדל (במובן הזה) בין מידת ההתאמה ל"XY" ול"פרופ' XY"?
אינדוקס 573813
האייל האלמוני • בתשובה לאייל אלמוני יום ג', 21/6/2011, 14:48
זה האלגוריתם של דירוג התוצאות... אני לא מכיר את זה של גוגל אבל מקובל לתת לכל מילה ''מיקום סמנטי'', ז''א המילה פרופ' קרובה סמנטית למילים שקשורות לאקדמיה ולכן מסמכים בהם הרבה יש הרבה מילים שקשורות לאקדמיה יופיעו קודם אם השאילתה מופיעה המילה פרופ'. את הקרבה הסמנטית בין מילים מוצאים (בד''כ, ואני מניח שגם בגוגל) לפי הקרבה בין המילים בטקסטים השונים.
אינדוקס 573828
אייל אלמוני • בתשובה להאייל האלמוני יום ג', 21/6/2011, 16:25
אז האם המחשב כבר יודע סמנטיקה?
אינדוקס 573831
האייל האלמוני • בתשובה לאייל אלמוני יום ג', 21/6/2011, 16:42
המהנדסים של גוגל יודעים.
אינדוקס 573819
רון בן-יעקב • בתשובה לאייל אלמוני יום ג', 21/6/2011, 15:32
בעניין "ו-" בגוגל, תנסה להשתמש ב + לפני המלים שחייבות להיות כלולות בתוצאות.
אינדוקס 573827
אייל אלמוני • בתשובה לרון בן-יעקב יום ג', 21/6/2011, 16:23
אבל אם אני רוצה גם את הסדר הספציפי?
אינדוקס 573833
רון בן-יעקב • בתשובה לאייל אלמוני יום ג', 21/6/2011, 17:03
אולי "word1 word2"+
אינדוקס 573799
אייל אלמוני • בתשובה לאפופידס יום ג', 21/6/2011, 13:17
את כל אלה אני יודע, כמובן - שהרי אחרת לא הייתי שואל את השאלה...:)
אינדוקס 573792
ג'וד • בתשובה לאייל אלמוני יום ג', 21/6/2011, 12:48
אני חושבת שזה כי גוגל כן עושה OR על מילות החיפוש.

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

עם תוסיף לחיפוש עוד מילה: ברטולד חרסה נציג
תקבל 1,150 תוצאות.

הוא פשוט מציג תחילה את אלה עם ה-AND ולכן נראה שהוא לא עושה OR.
או שהוא עושה OR כשיש מעט מאד תוצאות על ה AND.
אינדוקס 573794
ג'וד • בתשובה לג'וד יום ג', 21/6/2011, 12:55
בעצם זה לא מסביר את התופעה שלך.
אינדוקס 573798
אייל אלמוני • בתשובה לג'וד יום ג', 21/6/2011, 13:16
בדיוק. וגם: תגובה 573797
אינדוקס 573908
ירדן ניר-בוכבינדר  (אתר) • בתשובה לאייל אלמוני יום ה', 23/6/2011, 15:54
קצת טפשי, אבל ניסית בלי גרש בפרופ'? זה סימן פיסוק שנדמה לי שנדיר בשפות העולם בסוף מילה, ואולי יש לו משמעות מיוחדת עבור מנוע החיפוש.
אינדוקס 573909
אייל אלמוני • בתשובה לירדן ניר-בוכבינדר יום ה', 23/6/2011, 16:01
לא נראה לי שגרש משנה לו משהו.
אינדוקס 574425
האלמוני המזוהה • בתשובה לאפופידס שבת, 2/7/2011, 18:14
ואם כבר מדברים על אינדקסים לספרים, הנה‏1 אינדקס שכיחות ע"פ זמן של גוגל לכל הספרים שהם אינדקסו (כמה אחוזים מכלל הספרים שאי פעם נדפסו; מישהו כבר בטח כתב על זה כאן, אבל לא מצאתי איפה).
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות