למה חיפוש מעורפל הוא חיפוש טוב

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

חיפוש גרוע כסטנדרט

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

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

שגיאות בחיפוש

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

כדי לשפר את החיפוש נצטרך לזנוח את המאפיין העיקרי של החיפוש הפשוט, שהוא בדיקה האם קלט החיפוש מוכל בטקסט של התוכן. במקום ההשוואה הפשוטה הזאת נרצה לבדוק עד כמה הקלט של המשתמש דומה לתוכן שיש לנו במערכת ונחזיר את התוצאות הדומות ביותר, גם אם הן אינן זהות בדיוק. למשל, נניח שאנו מנהלים סופרמרקט מקוון, במערכת קיימים המוצרים ״אבטיח״, ״פלפל״ ו״פלפל ירוק חריף״, והמשתמש חיפש ״פלפלים״. נרצה שתוצאת החיפוש תהיה כי המוצר הדומה ביותר הוא ״פלפל״, אחריו ״פלפל ירוק חריף״ ובמקום האחרון ״אבטיח״. שיטה זו נקראת approximate string matching או fuzzy search. האלגוריתם ישווה בין מחרוזת החיפוש למחרוזת של כל אחד מהנתונים, ייתן לכל אחד מהם ״ציון״ שיחווה עד כמה הנתון דומה לחיפוש ואז ימיין את הנתונים לפי רמת הדמיון הזו. איזו פונקציה נגדיר כדי לקבוע מה הציון הזה? נציג כמה מהשיטות הרבות שקיימות ונראה איך משתמשים בהן בפועל.

מרחק לוינשטיין

אחת הפונקציות הידועות והקלות להבנה היא מרחק לוינשטיין. הפונקציה מגדירה מרחק בין שתי מחרוזות על ידי מספר פעולות העריכה שצריכים לבצע כדי להגיע ממחרוזת אחת לשניה, כאשר פעולת עריכה היא הוספה של תו, מחיקה של תו או החלפה של תו. למשל, המרחק בין המילה ״שלום״ למילה ״חלום״ הוא 1, משום שכדי לעבור מהמילה הראשונה לשניה אנו צריכים לבצע פעולת עריכה אחת – להחליף ״ש״ ב-״ח״. המרחק בין המילה ״שלום״ למילה ״שלו״ גם הוא 1, משום שגם כאן כדי לעבור מהמחרוזת הראשונה לשניה צריכים לבצע פעולת עריכה אחת – להוריד את ״ם״. המרחק בין המילה ״עציץ״ למילה ״חצי״ הוא 2, משום שצריכים לבצע שתי פעולות – להוריד את ״ץ״ ולהחליף את ״ע״ ב-״ח״. פונקציה כזו נקראת פונקציית עריכה ובאנגלית edit distance function משום שהפונקציה מודדת את מספר פעולות העריכה הנדרשות על מנת לעבור מטקסט אחד לטקסט השני.

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

מרחק לוינשטיין מנורמל

הבעיה העיקרית עם מרחק לוינשטיין הוא שהוא לא מביא בחשבון את אורך המחרוזות. בדוגמה של חיפוש הפלפלים נראה כי המונח הדומה ביותר ל״פלפלים״ הוא ״פלפל״ (במרחק 2), אחריו ״אבטיח״ (במרחק 5) ובמקום האחרון ״פלפל ירוק חריף״ (במרחק 9), וזאת למרות שהיינו רוצים ש״פלפל ירוק חריף״ יהיה קרוב יותר מאשר ״אבטיח״. נתגבר על הבעיה הזאת אם נשתמש במרחק לווינשטיין מנורמל: נחלק את מרחק לוינשטיין באורך המחרוזת הארוכה מבין שני המונחים אותם אנחנו משווים. בצורה זו נקבל מספר בין 0 ל-1 שיהווה חיווי של מידת הקרבה, כאשר 0 הוא הקרוב ביותר ו-1 הוא הרחוק ביותר. בשיטה הזאת המרחק בין ״פלפלים״ ל״אבטיח״ הוא 0.83 והוא אכן גדול יותר מהמרחק בין ״פלפלים״ ל״פלפל ירוק חריף״ שהוא 0.64. השיטה הזאת מביאה לידי ביטוי את העובדה שבמרחק לווינשטיין הרגיל ל״פלפל ירוק חריף״ יש מחיר גבוה בעיקר בגלל האורך שלו, למרות הדמיון ל״פלפלים״ בתחילת המחרוזת, ואילו המרחק הגבוה של ״אבטיח״ נובע מכך שהוא שונה לחלוטין מ״פלפלים״.

פונקציית מרחק

הפיסקה הבאה היא מעט מתמטית ואפשר לעבור לפסקה הבאה בלי לאבד את רצף הקריאה. פונקציה המקבלת שני פרמטרים מוגדרת כפונקצית מרחק אם היא מקיימת שלושה תנאים: א. המרחק של אובייקט מעצמו הוא 0. ב. הפונקציה סימטרית – המרחק מ-A ל-B שווה למרחק מ-B ל-A. ג. הפונקציה מקיימת את אי שוויון המשולש. דהיינו, אם אנחנו רוצים להגיע מ-A ל-B דרך נקודה אחרת C, לא נעבור דרך קצרה יותר מאשר אם נעבור ישירות מ-A ל-B. קל לראות שפונקציית לווינשטיין מקיימת את שלושת התנאים ולכן היא מוגדרת כפונקציית מרחק. לעומת זאת, נשים לב שמרחק לווינשטיין המנורמל אינו מקיים את התנאי השלישי ולכן היא אינה פונקציית מרחק. למשל, המרחק מ-״אב״ ל-״בג״ הוא 1 (2 שינויים חלקי האורך המקסימלי 2), אבל נוכל לעשות את המעבר במחיר נמוך יותר אם נעבור מ-״אב״ ל-״בג״ דרך ״אבג״: מ-״אב״ ל-״אבג״ במחיר ⅓ (שינוי אחד חלקי האורך המקסימלי 3), ומ-״אבג״ ל-״בג״ גם כן במחיר ⅓ על פי אותו חישוב, ובסך הכל ⅔ עבור שני הקטעים במקום המחיר המקורי של 1. אינטואיטיבית, אנחנו רוצים שהפונקציה שאנחנו משתמשים בה תהיה מטריקת מרחק כדי להימנע מאנומליות כאלו שעלולות לשבש את החיפוש. למרות זאת, מרחק לווינשטיין מנורמל נותן תוצאות טובות יותר, כך שיש כאן טרייד-אוף בין איכות התוצאות לבין התפשרות על הגדרות מתמטיות.

מימוש

איך מממשים את מרחק לווינשטיין בין שתי מחרוזות? ב-JavaScript בצד לקוח נוכל להשתמש בספרייה js-levenshtein או בצד שרת בפייתון בספרייה python-Levenshtein או בג׳אווה בספרייה LevenshteinDistance. אפשר גם להשתמש ישירות בתוך מסד הנתונים בפונקציה levenshtein ל-postgres או לממש בעצמנו את הפונקציה בכל מסד נתונים בו נשתמש.

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

סורנסן – דייס

אלגוריתם נוסף הוא Sørensen–Dice coefficient המבוסס על מספר רצפי התווים הדומים בשתי המחרוזות. למשל, אם נרצה להעריך עד כמה המילה ״החציל״ דומה למילה ״חצילים״ נחלק כל מילה לרצפים של שתי אותיות עוקבות. את ״החציל״ נפצל לקבוצה של 4 רצפים {״הח״, ״חצ״, ״צי״, ״יל״} ואת ״חצילים״ לקבוצה של 5 רצפים {״חצ״, ״צי״, ״יל״, ״לי״, ״ים״}. כשנתעלם מרצפים כפולים נמצא ששלושה רצפים (״חצ״, ״צי״, ״יל״) נמצאים בשתי המחרוזות. נוסחת הקירבה בודקת כמה רצפים משותפים יש יחסית למספר הרצפים הכללי. כאן אפשר לראות ויזואליזציה של האלגוריתם. שיטה זו מתאימה לחיפושים הקשורים במילים אנושיות, משום שבדרך כלל מילים בעלות משמעות קרובה משמרות חלקים זהים. נשים לב שהפונקציה מודדת דמיון, כך ש-1 מסמל זהות מושלמת ו- 0 מסמל אי דמיון מוחלט. כדי להשוות את התוצאה לפונקציית מרחק, כמו מרחק לוינשטיין המנורמל, נשתמש בערך המשלים ל-1. כך למשל המרחק בין ״חצילים״ ל״החציל״ בשיטה זו הוא 0.33 לעומת 0.5 לפי מרחק לוינשטיין המנורמל.

אחד החסרונות של האלגוריתם Sørensen–Dice הוא שציון הקירבה לא נותן משקל לסדר האותיות במילה. בדרך כלל למילים בעלות משמעות קרובה יש תחיליות משותפות, למשל ״לימון״ ו״לימונים״. חסרון נוסף הוא שציון הקרבה לא מתייחס לסדר המילים במשפט. למשל, היינו רוצים להבין שהביטויים ״פלפל ובצל ירוק״ ו״פלפל ירוק ובצל״ יהיו רחוקים יותר ממה שניתן לראות מרצף זוגות האותיות גרידא.

Trigram

אלגוריתם שעונה על בעיית חשיבות הסדר בין המילים הוא n-grams, כאשר n מייצג מספר קטן כלשהו. הערך המקובל ל-n הוא 3 ואז האלגוריתם נקרא trigram. גם אלגוריתם זה יוצר מכל מחרוזת קבוצה של רצפים (באורך של n, או 3 במקרה הפרטי של trigram), אלא שבנוסף לרצפים הרגילים נוספים לקבוצה רצפים המבטאים אילו רצפים מהווים תחילת מילה ומה הסדר בין המילים. באלגוריתם זה למשל, המרחק בין ״החציל״ ל״חצילים״ אכן עומד בציפיות שלנו להיות קטן והוא 0.15 (לעומת 0.33 ב-Sørensen–Dice ו-0.5 במרחק לוינשטיין). המרחק בין ״פלפל ירוק ובצל״ ל״פלפל ובצל ירוק״ מקבל בצדק ערך גבוה של 0.6 (לעומת 0.09 ב-Sørensen–Dice ו-0.57 במרחק לוינשטיין המנורמל). כך הוא מצליח גם במקרים בהם לוינשטיין או Sørensen–Dice נכשלים. מקובל להשתמש בכלל האצבע לפיו דמיון של עד 0.3 מסמל ששני המונחים זהים. האלגוריתם עצמו די מורכב להסבר וחורג מגבולות הפוסט. ההרצה שלו, לעומת זאת, מאוד פשוטה וקלה. הנה דוגמת קוד ב-python שמשווה בין שני מילים. קיים גם מימוש ב-PostgreSQL לאלגוריתם זה.

שיפורים נוספים

חשוב לציין שבכל השיטות שציינו קיימים חסרונות. למשל, במקרים בהם יש פחות קשר בין משמעות המילים לרצפי האותיות. למשל, שני דגמי המעבדים ״i7-920״ ו-״i5-750״ יקבלו ציון נמוך למרות שאנו רואים דמיון רב במבנה שלהם, ושני דגמי המצלמות ״Sony A7II״ ו-״Sony A7III״ יקבלו ציון של מרחק נמוך מאוד, ובאלגוריתמים שציינו הם יקבלו ציון של זהות כמעט מוחלטת, למרות שהמחרוזות אינן זהות והן מתארות מוצרים שונים למדי.

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

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