חיפוש שמות ומושגים לפי דמיון פונטי - WizSoft Search

אברהם מידן 13.01.2016 21:28
חיפוש שמות ומושגים לפי דמיון פונטי - WizSoft Search


הבעיה: משתמשים מחפשים פריט או לקוח מסוים, אבל לא יודעים את מספר הפריט (או הלקוח) ולא זוכרים במדויק את השם. הבעיה קיימת בכל עסק שמפעיל תוכנת ERP וכן בביקורים בחנויות וירטואליות (כאשר מחפשים פריט מסוים). כמו כן הבעיה קיימת באתרי חיפוש שח אנשים כגון מוזאון התפוצות יד ושם וכד'. כדי להתגבר על הבעיה הנ"ל פותחו אלגוריתמים למציאת שמות דומים. המשתמשים רושמים שם כפי שהם זוכרים אותו, והתוכנה מציגה שמות דומים מבחינה פונטית.



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

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

יש מקום לבחון את האלגוריתמים האלה לפי שלושה קריטריונים:
מהירות החיפוש – המשתמשים אינם מעוניינים להמתין לרשימת ההצעות כמות פספוסים (שמות שהמשתמשים היו רוצים לראות ברשימת ההצעות, אבל לא נשלפו ע"י האלגוריתם)
כמות אזעקות שווא (שמות שנמצאים ברשימת ההצעות אבל לא מתאימים לפריטים או הלקוחות שהמתמשים חיפשו).

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

 

Soundex

האלגוריתם פורסם לראשונה ב- 1918. נפוץ במחשבים משנות ה- 60 של המאה ה- 20. כל שם הופך למספר לפי השיטה הבאה (ציטוט מויקיפדיה). שמות דומים הם שמות בעלי אותו מספר.

1.   Retain the first letter of the name and drop all other occurrences of a, e, i, o, u, y, h, w.

2.   Replace consonants with digits as follows (after the first letter):

·         b, f, p, v → 1

·         c, g, j, k, q, s, x, z → 2

·         d, t → 3

·         l → 4

·         m, n → 5

·         r → 6

3.   If two or more letters with the same number are adjacent in the original name (before step 1), only retain the first letter; also two letters with the same number separated by 'h' or 'w' are coded as a single number, whereas such letters separated by a vowel are coded twice. This rule also applies to the first letter.

4.   If you have too few letters in your word that you can't assign three numbers, append with zeros until there are three numbers. If you have more than 3 letters, just retain the first 3 numbers.

 

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

 

מנוע החיפוש של WizSoft

מנוע החיפוש, WizSoft Search, מיועד לאתרי מסחר אלקטרוני או אתרים אחרים שבהם הנתונים (לגביהם עורכים את החיפושים) נמצאים ברשומות.

החיפוש מתבצע בדומה לחיפוש באתרים כמו Google ו- Alibaba. המשתמשים רושמים שאילתת חיפוש כלשהי. תוך כדי הקלדת שאילתת החיפוש התוכנה מציעה הצעות (autocomplete) ומתוך רשימת ההצעות המשתמשים בוחרים את הערך המתאים. 

בעת החיפוש, בעת הצגת ההצעות בשלב ה- autocomplete, החיפוש מתבסס על שלושת המרכיבים הבאים:

·         דמיון פונטי בין המילים שהוקלדו בשאילתת החיפוש לבין הנתונים באתר;

·         מחרוזות זהות (מתחיל ב-, מכיל) בין הנתונים הנ"ל;

·         שכיחות של המילים באתר.

כאשר שאילתת החיפוש כוללת יותר ממילה אחת, במסגרת ה- autocomplete התוכנה מציעה מילים מתאימות לפי סטטיסטיקה על צירופי מילים שכיחים באתר.

שתי מילים (או שמות) מוגדרים כדומים פונטית אם –

·         יש להן אותם עיצורים (באותו סדר), או

·         באחת המילים עיצור אחד חסר או הוחלף בעיצור אחר, או

·         שני עיצורים סמוכים החליפו מקום (שיכול אותיות).

 

בדיקת מנוע החיפוש לפי שלושת הקריטריונים הנ"ל:

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

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

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

 

מנוע החיפוש מתאים לאתרים בעברית ובאנגלית (או בשפות לטיניות אחרות)

 

כדי לבדוק את היכולות של מנוע החיפוש חיברנו אותו לאתרים של Wikipedia האנגלית (כ- 12 מליון ערכים) והעברית (כ- ... מליון ערכים).

סרטון המדגים חיפוש באתרים אלה לאחר המצגת


 

מצגת ההרצאה  



הוספת תגובה
  מגיב אנונימי
שם או כינוי:
חסימת סיסמה:
  זכור אותי תמיד במחשב זה

כותרת ראשית:
אבקש לקבל בדואר אלקטרוני כל תגובה לטוקבק שלי
אבקש לקבל בדואר אלקטרוני כל תגובה למאמר הזה