אתגר - אלגוריתם סופר מהיר להסרת מחרוזות כפולות

[Rרחמים]

בהינתן מערך עם N מחרוזות,
על האלגוריתם ליצור מערך חדש שתהיינה בו רק מחרוזות ייחודיות,
מה הן מחרוזות ייחודיות? כל מחרוזת שלא קיימת בתוך מחרוזת אחרת במערך.
כלומר אם יש כמה מחרוזות זהות יש להשאיר רק אחת מהן, אבל לא רק זאת, אלא גם מחרוזת קצרה שנמצאת בתוך מחרוזת ארוכה - יש להשאיר רק את הארוכה.

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

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

 

[אלעזר 1]

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

 

[שלמה וייס]

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

נכון.

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

בפייתון למשל, זה יראה כך:

def no_duplicate(arr):                     
    arr.sort(key=len)                     
    result = arr.copy()                   
    for i, word in enumerate(arr):         
        for rest in arr[i+1:]:             
            if word in rest:               
                result.remove(word)       
                break                     
    return result

 

[Rרחמים]

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

 

[אלעזר 1]

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

 

[שלמה וייס]

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

למה שיחסוך?

תכלס על כל איבר ברשימה, הוא עלול לעבור על כל הרשימה.

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

 

[אלעזר 1]

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

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

 

[esther3]

--

 

[Rרחמים]

לא עדיף למיין את המערך ופשוט בלולאה אחת לבדוק על כל מחרוזת אם הוא מכיל את המחרוזת הבאה?

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

אאא
בבב
גגג אאא

 

[שלמה וייס]

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

תשתמש בתנאי על count יותר מ1.

זה נכון שאפשר להשתמש בre בשביל זה, אבל לדעתי זה מיותר.

 

[אפר]

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

אאא
בבב
גגג אאא

והלאה

 

[Rרחמים]

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

לא רק שזה לא יחסוך זה יאריך פי כמה, מכמה סיבות:
1. החיפוש יהיה מול כל המחרוזות, ולא רק מול השוות או הארוכות יותר, וכך מאבדים את האופטמיזציה שהצעת לעיל
2. חיפוש מחרוזת באורך N בתוך מחרוזת באורך N+X מחייב X+1 בדיקות התאמה ולא יותר. אבל אם מחברים את כל המחרוזות יחד למחרוזת ארוכה יהיו הרבה יותר בדיקות, מאשר לבדוק כל פעם מול מחרוזת אחת קצרה.
3. אי אפשר לחבר את כל המחרוזות למחרוזת אחת, כי זה עובר את הכמות המקסימלית של תווים שמחרוזת יכולה להכיל, מדובר במערך של מיליוני איברים שכל איבר הוא מחרוזת שיכולה להיות של אלפי תווים.

 

[אפר]

נכון.

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

בפייתון למשל, זה יראה כך:

def no_duplicate(arr):                    
    arr.sort(key=len)                    
    result = arr.copy()                  
    for i, word in enumerate(arr):        
        for rest in arr[i+1:]:            
            if word in rest:              
                result.remove(word)      
                break                    
    return result

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

 

[שלמה וייס]

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

ואיך הדבר יועיל?

 

[אדרת]

מנסה

למיין לפי האורך, ולהתחיל מהארוך ביותר
ואז להשוות את הבא בתור
אם זה נמצא למחוק, אם לא לצרף למחרוזת הקודמת
ואז את השלישי להשוות למחרוזת המצורפת
וכן הלאה

כך יוצא שכל מחרוזת צריכה השוואה רק פעם אחת מול המחרוזת שכבר כוללת את כל המחרוזת שמעליה

 

[אפר]

ואיך הדבר יועיל?

שאז מחרוזת זהות יצמדו וימנע הצורך לבדוק באותו אורך מלבד הבא בתור
ובאורכים גדולים כן ידרש לבדוק את כל המחרוזות לדוג'

• אאא
• בבב
• בבב
• גגג
• דגכי
• יעיכ
• מאאא

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

ואולי קודם להריץ כל מחרוזת מול הבאה באותו הגודל וכך דבר ראשון לצמצם את הגודל הכללי של המערך ורק אז לחזור לריצה על מחרוזות גדולות יותר

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

 

[אפר]

מנסה

למיין לפי האורך, ולהתחיל מהארוך ביותר
ואז להשוות את הבא בתור
אם זה נמצא למחוק, אם לא לצרף למחרוזת הקודמת
ואז את השלישי להשוות למחרוזת המצורפת
וכן הלאה

כך יוצא שכל מחרוזת צריכה השוואה רק פעם אחת מול המחרוזת שכבר כוללת את כל המחרוזת שמעליה

לא פותר את בעיית האורך
(וכן יצריך הפרדה בתו יחודי)

 

[ירושל]

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

1. ממיינים לפי האורך ומתחילים מהמחרוזת הארוכה ביותר. נקבל - ירושלים, חלום, שלום, מספר, ספר, ים, לו.
2. מאתחלים מילון של אינדקסים או מצביעים לפי ה-א' ב' (א' = [], ב' = []...)
3. מפרקים כל מחרוזת ומכניסים את האינדקס של כל תתי המחרוזות מהארוכה לקצרה, בלי כפילויות.
נקבל - י' = [ירושלים], ר' = [רושלים] ו' = [ושלים] ש' = [שלים] ל' = [לים] י' = [ים]
4. מריצים את אותו תהליך על כל אחת מהמחרוזות הבאות, ובודקים חפיפה. שומרים על תתי המערכים ממוינים (מיון הכנסה) כדי לקצר את זמן החיפוש בתוך כל תתי המחרוזות באותה אות במילון. אם מצאנו התאמה, עוצרים את המשך הפרוק.
5. כל מילה שעברה פרוק, ולו חלקי, נשמור את האינדקס שלה במערך נוסף, נקרא לו פלט.
אם נמשיך עם הדוגמא - המילה הבאה (התוספות החדשום מודגשות):
חלום:
נקבל ח' = [חלום], י' = [ים, ירושלים], ר' = [רושלים] ו' = [ום , ושלים] ש' = [שלים] ל' = [לום,לים]
פלט = [ירושלים, חלום]
שלום:
נקבל ח' = [חלום], י' = [ים, ירושלים], ר' = [רושלים] ו' = [ום , ושלים] ש' = [שלום, שלים] ל' = [לום,לים]
אבל כשנשווה את הפרוק הבא - 'לום' - נגלה שהוא כבר קיים ולכן אין צורך להמשיך.
פלט = [ירושלים, חלום, שלום]
מספר:
ח' = [חלום], י' = [ים, ירושלים], ר' = [רושלים] ו' = [ום , ושלים] ש' = [שלום, שלים] ל' = [לום,לים] מ' = [מספר], ס' = [ספר], פ' = [פר]
פלט = [ירושלים, חלום, שלום, מספר]
ספר: מצאנו התאמה (מלאה) ולכם אין צורך להמשיך. לא התבצע פרוק ולכן לא מוסיפים את המחרוזת לפלט.
ים, לו - כנ"ל.
פלט סופי: [ירושלים, חלום, שלום, מספר]

 

[שלמה וייס]

שאז מחרוזת זהות יצמדו וימנע הצורך לבדוק באותו אורך מלבד הבא בתור
ובאורכים גדולים כן ידרש לבדוק את כל המחרוזות לדוג'

• אאא
• בבב
• בבב
• גגג
• דגכי
• יעיכ
• מאאא

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

ואולי קודם להריץ כל מחרוזת מול הבאה באותו הגודל וכך דבר ראשון לצמצם את הגודל הכללי של המערך ורק אז לחזור לריצה על מחרוזות גדולות יותר

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

איך החיפוש ידלג למחרוזת הגדולה יותר?

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

 

[אפר]

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

1. ממיינים לפי האורך ומתחילים מהמחרוזת הארוכה ביותר. נקבל - ירושלים, חלום, שלום, מספר, ספר, ים, לו.
2. מאתחלים מילון של אינדקסים או מצביעים לפי ה-א' ב' (א' = [], ב' = []...)
3. מפרקים כל מחרוזת ומכניסים את האינדקס של כל תתי המחרוזות מהארוכה לקצרה, בלי כפילויות.
נקבל - י' = [ירושלים], ר' = [רושלים] ו' = [ושלים] ש' = [שלים] ל' = [לים] י' = [ים]
4. מריצים את אותו תהליך על כל אחת מהמחרוזות הבאות, ובודקים חפיפה. שומרים על תתי המערכים ממוינים (מיון הכנסה) כדי לקצר את זמן החיפוש בתוך כל תתי המחרוזות באותה אות במילון. אם מצאנו התאמה, עוצרים את המשך הפרוק.
5. כל מילה שעברה פרוק, ולו חלקי, נשמור את האינדקס שלה במערך נוסף, נקרא לו פלט.
אם נמשיך עם הדוגמא - המילה הבאה (התוספות החדשום מודגשות):
חלום:
נקבל ח' = [חלום], י' = [ים, ירושלים], ר' = [רושלים] ו' = [ום , ושלים] ש' = [שלים] ל' = [לום,לים]
פלט = [ירושלים, חלום]
שלום:
נקבל ח' = [חלום], י' = [ים, ירושלים], ר' = [רושלים] ו' = [ום , ושלים] ש' = [שלום, שלים] ל' = [לום,לים]
אבל כשנשווה את הפרוק הבא - 'לום' - נגלה שהוא כבר קיים ולכן אין צורך להמשיך.
פלט = [ירושלים, חלום, שלום]
מספר:
ח' = [חלום], י' = [ים, ירושלים], ר' = [רושלים] ו' = [ום , ושלים] ש' = [שלום, שלים] ל' = [לום,לים] מ' = [מספר], ס' = [ספר], פ' = [פר]
פלט = [ירושלים, חלום, שלום, מספר]
ספר: מצאנו התאמה (מלאה) ולכם אין צורך להמשיך. לא התבצע פרוק ולכן לא מוסיפים את המחרוזת לפלט.
ים, לו - כנ"ל.
פלט סופי: [ירושלים, חלום, שלום, מספר]

לא נראה לי מעשי מדובר על מערך עם מחרוזות ארוכות לפי הנכתב