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

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

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

ככל שבגוגל הדבר מובן מאליו, מתסכל מאוד לגלות שזה אינו הסטנדרט, אפילו באתרים גדולים. למשל, כאשר נחפש באמזון אוזניות באיות השגוי "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 או לממש בעצמנו את הפונקציה בכל מסד נתונים בו נשתמש.


const levenshtein = require("js-levenshtein")
const normalizedLevenshtein = (a, b) => levenshtein(a, b) / Math.max(a.length, b.length)
console.log(normalizedLevenshtein("headphones", "headph0nes"))
// 0.1
console.log(normalizedLevenshtein("לימון", "לימונים"))
// 0.42857142857142855

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

סורנסן – דייס

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

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


const { compareTwoStrings: sørensenDice } = require("string-similarity")
console.log(1 sørensenDice("חצילים", "החציל"))
// 0.33333333333333337
console.log(1 sørensenDice("פלפל ירוק ובצל", "פלפל ובצל ירוק"))
// 0.09090909090909094

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 לאלגוריתם זה.


from ngram import NGram
print(NGram.compare('החציל', 'חצילים'))
# 0.15384615384615385
print(NGram.compare('פלפל ובצל ירוק', 'פלפל ירוק ובצל'))
# 0.6

view raw

03_ngram.py

hosted with ❤ by GitHub

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

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

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

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

28 תגובות בנושא “למה חיפוש מעורפל הוא חיפוש טוב

הוסיפו את שלכם

  1. 1. אינה פונקציית מרחקת מרחק – השתכפל שם בטעות ה"ת מרחק".
    2. כך הוא מצליח גם במקרים לוינשטיין – נשמטה המילה "בהם".
    3. החלק הכי מתמטי בפסקה ה"מפחידה" זה ה"קל לראות" 😂
    4. מאמר מעולה, כרגיל. אתם שומרים על האיכות, ומצליחים לכתוב מדויק ועדיין גם ברור ומובן. שאפו!

  2. מרתק, והגיע בדיוק בזמן בשבילי.
    האם elastic search / solr תומכים בכל האלגוריתמים האלה?

  3. מעניין מאד
    איך גוגל גורמת למילים שכותבים באנגלית שיופיעו כעברית?

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

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

      1. הבעיה העיקרית בשימוש בfuzzy search הוא בייקור החיפוש עצמו מסדר גודל קבוע, במידה וקיים אינדקס על הטקסט, לסדר גודל של n (מספר המילים).
        כדי לענות על השאלה איזה מילים הכי מתאימות לאינפוט של היוזר, יש צורך לסרוק את כל הסט של המילים הקיימות, זו פעולה מאוד יקרה בזמן אמת. לעומת זאת מציאת המילים המתאימות בדיוק לאינפוט, זו פעולה של זמן קבוע אם משתמשים בHM או בradix.

  5. אתם יוצרים משהו אמיתי!! כעת הרעיון מיושם באתר נוסף. כל הכבוד!!

  6. מעולה ומועיל.
    כדאי לתת גם משקל לאותיות "ו" ו"י" שהם כתיב מלא וחסר, ולא אמורים להוריד משמעותית את "הציון" של המרחק בין המילים, כמו כן אותיות שקרובות במקלדת צריכות ציון גבוה יותר בהתאמה.

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

    והמצב חמור עוד יותר במתרגם של גוגל, שניכר שמרוב AI ו-ML הוא מתרגם למה שהוא רואה כסביר סטטיסטית שהכותב חשב ולא למה שכתוב – אם אני כותב "I measured one inch" הוא מחזיר "מדדתי סנטימטר אחד"…

    1. תודה רבה!

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

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

  8. "ג. הפונקציה מקיימת את אי שוויון המשולש. דהיינו, אם אנחנו רוצים להגיע מ-A ל-B דרך נקודה אחרת C, לא נעבור דרך קצרה יותר מאשר אם נעבור ישירות מ-A ל-B."
    צריך להוסיף שנק' C לא נמצאת על הקו AB.
    (פיסקה מתמטית צריכה לדייק בצורה מתמטית…)

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

נשמח לשמוע מה אתם חושבים על המאמר

ערכת עיצוב: Baskerville 2 של Anders Noren.

למעלה ↑

רוצים להיות מפתחים טובים יותר?
הכניסו את כתובת המייל שלכם כדי לקבל הודעות על פוסטים חדשים ולהישאר מעודכנים.

נרשמת בהצלח. בתודה, הגמל.

שגיאה בלתי צפויה, אנא נסה שוב.

camelCase will use the information you provide on this form to be in touch with you and to provide updates and marketing.