השוואת טקסט כאשר המילים אינם לפי הסדר בc#

pcinfogmach

בC# קיימת הפונקציה contains שבודקת האם מחרוזת טקסט מכיל בתוכו מחרוזת טקסט אחרת
אבל מה קורה אם המחרוזת השניה מבולגנת (כלומר המילים אינם לפי הסדר) ואתה רוצה לבדוק אם היא קיימת בתוך מחרוזת הראשונה (לדוגמא אם נחפש את "כי זרע יקרא לך ביצחק" בתוך חומש בראשית).
בניתי לזה קוד והייתי שמח לקבל משוב - תודה מראש

 public static bool StringContains(this string line, string[] searchPatternArray, int maxDistance)
 {
     maxDistance = maxDistance - searchPatternArray[searchPatternArray.Length - 1].Length;
     List<List<int>> wordIndexesList = new List<List<int>>();

     // Get indexes of each word in the line
     foreach (string word in searchPatternArray)
     {
         var indexes = AllIndexesOf(line, word).ToList();
         wordIndexesList.Add(indexes);
     }

     if (wordIndexesList.Any(list => list.Count == 0))
         return false;

     // Calculate if there is an occurrence of all words within the max distance
     return IsWithinMaxDistance(wordIndexesList, maxDistance);
 }

 static IEnumerable<int> AllIndexesOf(string str, string value)
 {
     if (string.IsNullOrEmpty(value))
         throw new ArgumentException("The string to find may not be empty", nameof(value));

     int index = 0;
     while (index < str.Length)
     {
         index = str.IndexOf(value, index);
         if (index == -1)
             break;
         yield return index;
         index += value.Length;
     }
 }

 static bool IsWithinMaxDistance(List<List<int>> wordIndexesList, int maxDistance)
 {
     // Check if all words occur within the maximum distance
     for (int i = 0; i < wordIndexesList[0].Count; i++)
     {
         int startIndex = wordIndexesList[0][i];
         if (IsWithinMaxDistanceForIndex(wordIndexesList, maxDistance, 1, startIndex))
         {
             return true;
         }
     }
     return false;
 }

 static bool IsWithinMaxDistanceForIndex(List<List<int>> wordIndexesList, int maxDistance, int wordIndex, int startIndex)
 {
     if (wordIndex >= wordIndexesList.Count)
         return true; // All words checked within max distance

     for (int j = 0; j < wordIndexesList[wordIndex].Count; j++)
     {
         int endIndex = wordIndexesList[wordIndex][j];
         int distance = Math.Abs(endIndex - startIndex);
         if (distance <= maxDistance)
         {
             if (IsWithinMaxDistanceForIndex(wordIndexesList, maxDistance, wordIndex + 1, endIndex))
             {
                 return true;
             }
         }
         else if (endIndex > startIndex)
         {
             // No need to check further as the indexes are sorted
             break;
         }
     }

     return false;
 }

dovid

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

יש בקוד כמה שיפורים אפשריים, למשל:

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

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

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

pcinfogmach

פוסט זה נמחק!

sivan22

אני הייתי משתמש בספרייה fuzzysharp. הפונקציה fuzz.token_sort_ratio תתן את הניקוד של דימיון בין מחרוזות שאינן באותו הסדר.

pcinfogmach

@sivan22

זה יותר איטי ממה שאני הצעתי
התוצאות לא משהו אא"כ בין מחרוזות באורך זהה

אולי אני לא פועל איתו נכון?

sivan22

באמת למחרוזות באורך שונה מתאים יותר partial_token_sort. כדאי לנסות את אפשרויות הניקוד השונות לפי הצורך הספציפי.

yossiz

@pcinfogmach מה שדוד העיר שאתה לא מגדיר את הפוקנציה בצורה טובה היא הערה מאוד חשובה, עד שקראתי את הקוד בעיון באמת לא ידעתי מה הפונקציה עושה, וזה באמת עושה משהו מוזר קצת (לענ"ד) ואם היית מגדיר את זה במילים אולי היית שם לב לזה (או אולי זה באמת מה שרצית)

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

עוד הערה לגבי המרחק. שורה זו:

maxDistance = maxDistance - searchPatternArray[searchPatternArray.Length - 1].Length

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

dovid

פוסט זה נמחק!

ELIKO

היי אני לא יודע איך לכתוב את הקוד לזה ב C#

לדעתי מה שצריך לעשות זה לקחת מילה אחת (יתכן וישנה עדיפות לפי שכיחות)
למצוא את כל המופעים שלה בקוד ולשמור אותם
אחכ לרוץ עם המילה הבאה רק במרחק האינקס שמצאנו + N תווים עם כל המיקומים האפשריים של המילה מהאינדקס שמצאנו (צריך לקחת בחשבון את אורך המילים שנשארו כדי לחשב את המיקומים האפשריים בין היתר לכן ישנה עדיפות בבחירת סדר המילים)
וכן הלאה
וכל פעם גורעים מהרשימה הראשונית את מה שלא מתאים בוודאות
וכשמסיימים לרוץ על כל המילים לוקחים רק את הרצפים שמתאימים מתוך האינדקס הראשוני

מקווה שהייתי ברור

תחומים - פורום חרדי מקצועי

השוואת טקסט כאשר המילים אינם לפי הסדר בc#