בחיפוש בגוגל אנחנו מקבלים כמובנת מאליה את העובדה שכאשר אנו עושים שגיאת כתיב גוגל מתקן לנו אותה, ומחזיר לנו לא רק תוצאות התואמות במדויק את מה שחיפשנו אלא גם תוצאות המתאימות במקורב. למשל, אם נחפש בגוגל את המילה השגויה ״ירשאלי״, בגוגל יעשו בשבילנו שני דברים: ראשית, הם יבינו שאירעה לנו טעות בהקלדה והתכוונו לחפש ״ישראלי״. שנית, התוצאות לא יכללו רק את התוצאות המתאימות בדיוק לחיפוש המתוקן אלא גם תוצאות הקרובות לחיפוש הזה. למשל, התוצאה הראשונה תואמת לחיפוש ״ישראלים״.
חיפוש גרוע כסטנדרט
ככל שבגוגל הדבר מובן מאליו, מתסכל מאוד לגלות שזה אינו הסטנדרט, אפילו באתרים גדולים. למשל, כאשר נחפש באמזון אוזניות באיות השגוי "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 או לממש בעצמנו את הפונקציה בכל מסד נתונים בו נשתמש.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 הוא שציון הקירבה לא נותן משקל לסדר האותיות במילה. בדרך כלל למילים בעלות משמעות קרובה יש תחיליות משותפות, למשל ״לימון״ ו״לימונים״. חסרון נוסף הוא שציון הקרבה לא מתייחס לסדר המילים במשפט. למשל, היינו רוצים להבין שהביטויים ״פלפל ובצל ירוק״ ו״פלפל ירוק ובצל״ יהיו רחוקים יותר ממה שניתן לראות מרצף זוגות האותיות גרידא.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 לאלגוריתם זה.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from ngram import NGram | |
print(NGram.compare('החציל', 'חצילים')) | |
# 0.15384615384615385 | |
print(NGram.compare('פלפל ובצל ירוק', 'פלפל ירוק ובצל')) | |
# 0.6 |
שיפורים נוספים
חשוב לציין שבכל השיטות שציינו קיימים חסרונות. למשל, במקרים בהם יש פחות קשר בין משמעות המילים לרצפי האותיות. למשל, שני דגמי המעבדים ״i7-920״ ו-״i5-750״ יקבלו ציון נמוך למרות שאנו רואים דמיון רב במבנה שלהם, ושני דגמי המצלמות ״Sony A7II״ ו-״Sony A7III״ יקבלו ציון של מרחק נמוך מאוד, ובאלגוריתמים שציינו הם יקבלו ציון של זהות כמעט מוחלטת, למרות שהמחרוזות אינן זהות והן מתארות מוצרים שונים למדי.
כמו כן, בכל השיטות הללו מחרוזות החיפוש והמטרה מושוות בלי לעבד את המשמעות של המילים. למשל, כאשר חישבנו את הקירבה של ״לימון״ ו״לימונים״ לא השתמשנו בשום אלגוריתם המכיר את כללי הדקדוק העברי ויודע כי המילה ״לימונים״ היא צורת הרבים של המילה ״לימון״.
החיפוש של גוגל לוקח את זה בחשבון ולכן יהיה נאיבי להניח ששימוש באחד האלגוריתמים שתיארנו יביא אותנו לרמת היעילות של גוגל. אך עדיין, עבודה מועטה יחסית תשפר מאוד את החיפוש הפשוט ואת חוויית החיפוש של המשתמשים שלנו.
מאמר מעולה, בהחלט אשתמש בזה בפרויקטים שלי.
מעניין מאוד
הכותרת: נ נח נחמ נחמן מאומן…
1. אינה פונקציית מרחקת מרחק – השתכפל שם בטעות ה"ת מרחק".
2. כך הוא מצליח גם במקרים לוינשטיין – נשמטה המילה "בהם".
3. החלק הכי מתמטי בפסקה ה"מפחידה" זה ה"קל לראות" 😂
4. מאמר מעולה, כרגיל. אתם שומרים על האיכות, ומצליחים לכתוב מדויק ועדיין גם ברור ומובן. שאפו!
תודה רבה! תוקן.
מרתק. תודה.
יישר כח! כתוב יפה מאוד.
מרתק, והגיע בדיוק בזמן בשבילי.
האם elastic search / solr תומכים בכל האלגוריתמים האלה?
elastic תומכים באלגוריתם Damerau-Levenshtein שהיא הרחבה של מרחקלוינשטיין שמאפשרת גם שיכול של שני תוויםשונים. כלומר המרחק בין ab ל-ba הוא 1.
https://www.elastic.co/blog/found-fuzzy-search
מאד מעניין
מעניין מאד
איך גוגל גורמת למילים שכותבים באנגלית שיופיעו כעברית?
גוגל עושים עוד הרבה מאוד דברים בשביל לשפר את החיפוש. פה הצגנו ממש על קצה המזלג.
אחלה מאמר
אני משתמש בספריה הזו ל fuzzy-search ב js
https://github.com/krisk/fuse
כל הכבוד, מוצג מעולה
האם ישנם גם חסרונות לחיפושים המעורפלים? ומדוע אכן אין מיישמים זאת גם באתרים מושקעים מאוד?
אין אורחות לחינם. המחיר הוא שעה עבודה. בכמויות גדולות של נתונים תהיה האטה קלה בחיפוש.
למה אחרים לא עושים את זה? השאלה הזו נכונה לעוד הרבה מאוד פיצ'רים קלים למימוש שחסרים באתרים מכובדים.
הבעיה העיקרית בשימוש בfuzzy search הוא בייקור החיפוש עצמו מסדר גודל קבוע, במידה וקיים אינדקס על הטקסט, לסדר גודל של n (מספר המילים).
כדי לענות על השאלה איזה מילים הכי מתאימות לאינפוט של היוזר, יש צורך לסרוק את כל הסט של המילים הקיימות, זו פעולה מאוד יקרה בזמן אמת. לעומת זאת מציאת המילים המתאימות בדיוק לאינפוט, זו פעולה של זמן קבוע אם משתמשים בHM או בradix.
נכון ש-O(N) זה סדר גודל יותר מאשר O(logn) אבל בפועל לרוב אנחנו יכוים לשלם את זה בלי הרבה בעיות.
אתם יוצרים משהו אמיתי!! כעת הרעיון מיושם באתר נוסף. כל הכבוד!!
מעולה ומועיל.
כדאי לתת גם משקל לאותיות "ו" ו"י" שהם כתיב מלא וחסר, ולא אמורים להוריד משמעותית את "הציון" של המרחק בין המילים, כמו כן אותיות שקרובות במקלדת צריכות ציון גבוה יותר בהתאמה.
מאמר מועיל ויפה!
תודה
פוסט מאלף. אין ספק שגוגל מגדיל לעשות ומקדים את כולם (החיפוש בחלונות 10 לא מתקן אפילו הקלדה שגויה בעברית במקום אנגלית ולהיפך). עם זאת, הייתי מעדיף אופציה לדרוש ממנוע החיפוש לשנמך עצמו – כשזה נחוץ לי – לחיפוש בוליאני מדוייק לגמרי. זאת מפני שכמשתמש מתקדם לעתים חשוב לי להגיע דווקא לתוצאות שיש בהן שגיאת כתיב ספציפית, או כתיב לא סטנדרטי, או שם מקום נידח בשפה זרה ששונה באות ממילה נפוצה, או מוזרות אחרת, וגוגל מתעלם מרצוני כליל ומציף אותי בתוצאות שהוא חושב שיותר הגיוני שאשמח בהן. במלים אחרות, הוא מכוון למכנה המשותף הנפוץ ולא לחריגים.
והמצב חמור עוד יותר במתרגם של גוגל, שניכר שמרוב AI ו-ML הוא מתרגם למה שהוא רואה כסביר סטטיסטית שהכותב חשב ולא למה שכתוב – אם אני כותב "I measured one inch" הוא מחזיר "מדדתי סנטימטר אחד"…
תודה רבה!
ככל הידוע לי, ניתן לחפש בגוגל חיפוש מדויק על ידי הקפת החיפוש במרכאות. זה עובד גם ברמת המילה הבודדת.
בנוגע לתרגום החופשי של גוגל, זה מזכיר לי את הבדיחה המתארת את המצב ההפוך. המשורר הצהיר ״אלך אחרייך אלף מייל״ והמתרגם תרגם ״אלך אחרייך אלף שש מאות ותשעה קילומטר ושלוש מאות ארבעים וארבעה מטר״.
"ג. הפונקציה מקיימת את אי שוויון המשולש. דהיינו, אם אנחנו רוצים להגיע מ-A ל-B דרך נקודה אחרת C, לא נעבור דרך קצרה יותר מאשר אם נעבור ישירות מ-A ל-B."
צריך להוסיף שנק' C לא נמצאת על הקו AB.
(פיסקה מתמטית צריכה לדייק בצורה מתמטית…)
מאמר מצויין! תודה רבה.
מעולה!!
מאמר מעניין מאוד
תודה
מרתק וכתוב היטב!
עכשיו חסר לי החלק הבא של להבין איך בונים מבנה נתונים שיאפשר למצוא במהירות את הביטוי הקרוב ביותר מבין אינסוף אפשרויות