הסבר | איתור מראי מקומות באמצעות חיפוש מטושטש
-
שלום לכולם,
ברצוני לשתף איתכם הדגמה קטנה של חיפוש מתקדם באמצעות אלגוריתם שנקרא "חיפוש מטושטש".
נניח שיש לנו מאגר תורני שיש בו הרבה מאד מקורות, והמשתמש רוצה להציג מקור מסויים על ידי הקלדת מראה המקום שלו, לדוגמה "רשי ברכות דף ב". יתכן שהטקסט המדוייק כפי שהוא מופיע במאגר שונה מעט לדוגמא "רש"י על מסכת ברכות ב.". ואנו רוצים שהמשתמש יקבל את התוצאה הקרובה ביותר לטקסט שהוא הקליד.
ישנן כמה דרכים ידניות לעשות זאת, כמו לנסות תמיד עם המילה "פרק" "עמוד" וכדומה ובלי המילה הזו, לחפש גם התאמה חלקית, ועוד רעיונות שונים ומשונים.
אך ניתן גם להשתמש באלגוריתם שנקרא חיפוש מטושטש שתפקידו למצוא את המחרוזת הדומה ביותר למחרוזת של המשתמש. לא ניכנס לפרטים אבל הרעיון הכללי הוא לחשב את מספר השינויים שצריך לעשות במחרוזת אחת כדי לקבל את השנייה, לדוגמה תחול -> חתול, צריך להחליף שתי אותיות סמוכות, חול -> חתול צריך להוסיף אות, חזתול -> חתול צריך להוריד אות, וכיוצא בזה לכל שינוי יש ניקוד מסויים, והניקוד הכללי קובע מהי המחרוזת הכי קרובה. הניקוד הזה מכונה מרחק לוינשטיין.
האתגר שעמד בפני הוא שהאלגוריתם הזה הוא די איטי, וסכום מראי המקומות האפשריים הוא גדול מאד, לדוגמה במקרה שלנו כ600 אלף דוגמאות, ולעבור על כל הדוגמאות אורך כ8-12 שניות (במחשב שלי).
הפתרון שמצאתי הוא לחלק את החיפוש לשניים: קודם כל לחפש רק ברשימת הספרים, שכוללת סה"כ כ8000 אפשרויות (ל5800 ספרים), ולאחר שמצאנו את הספרים הכי קרובים, לחפש רק בהם. הדבר מקצר מאד את משך החיפוש, על חשבון הדיוק. כך לחפש רק ב3 הספרים הכי קרובים לקח 0.4 שניות ולחפש ב10 הספרים הכי קרובים לקח כ2 שניות, אך דיוק החיפוש יורד.
תכל'ס אחרי כל כך הרבה דיבורים, הנה הקישור לנסות זאת בעצמכם. (ניתן לשנות את מספר הספרים לחיפוש, מ0 עד 20.) אשמח לפידבק והערות בונות. (גם הקוד נמצא שם)
@pcinfogmach ו @לא-מתייאש אני חושב שזה יעניין אתכם.
-
-
@pcinfogmach כתב בהסבר | איתור מראי מקומות באמצעות חיפוש מטושטש:
@sivan22
מרתק
כמדומני שמאוד ישפר את הקוד אם יינתן ניקוד גבוה יותר על פי חלוקה של מילים.כלומר
אם חיפשתי
רש באשת ב ד
התוצאה הייתה שמואל ב ב
בזמן שציפיתי שיהיה רש"י בראשית ב ד
וזה מה שהיה קורה אם ההתאמה הייתה לפי מיליםעדכנתי את הקוד, נתתי אפשרות לכמה אלגוריתמים שונים. אלגוריתם ברירת המחדל כרגע מחלק לפי מילים, אשמח לשמוע עוד פידבק:
-
-
-
![חיפוש גוגל בפורום](javascript:{bootbox.prompt({title:'<div style="text-align: center;"><img src="/assets/uploads/files/1625950269825-mt-google.png" width="400"></div>',placeholder:'כתוב מילים לחיפוש ב Google',buttons:{confirm:{label:'חיפוש'},cancel:{label:'ביטול'}},backdrop:true,callback:function(result){if(result!=null&&result!=''){var a=document.createElement('a');a.href='https://www.google.co.il/search?q=site:mitmachim.top '+encodeURIComponent(result.trim());a.target='_blank';a.click();}}})();};){kind=link}