התאמת דפוסים נמצאת בשימוש נרחב במדעי המחשב ובתחומים רבים אחרים. אלגוריתמים של התאמת דפוסים משמשים לחיפוש תבניות בתוך טקסט או מערך נתונים גדול יותר. אחד האלגוריתמים הפופולריים ביותר להתאמת דפוסים הוא בויאר-מור אלגוריתם, אשר פורסם לראשונה בשנת 1977. במאמר זה, נדון באלגוריתמים של Pattern Matching ב-C וכיצד הם פועלים.
מהו אלגוריתם התאמת דפוסים?
אלגוריתמים של התאמת דפוסים משמשים כדי למצוא דפוסים בתוך קבוצה גדולה יותר של נתונים או טקסט. אלגוריתמים אלה פועלים על ידי השוואת דפוס עם מערך נתונים או טקסט גדול יותר וקביעה אם הדפוס קיים או לא. אלגוריתמים של התאמת דפוסים חשובים מכיוון שהם מאפשרים לנו לחפש דפוסים במערכות נתונים גדולות במהירות.
רבעון בעסקים
אלגוריתם התאמת דפוס כוח גס:
התאמת דפוסי כוח גס הוא האלגוריתם הפשוט ביותר של התאמת דפוסים. זה כרוך בהשוואה בין הדמויות של התבנית לדמויות הטקסט אחת אחת. אם כל התווים תואמים, האלגוריתם מחזיר את מיקום ההתחלה של התבנית בטקסט. אם לא, האלגוריתם עובר למיקום הבא בטקסט וחוזר על ההשוואה עד שנמצא התאמה או הגעה לסוף הטקסט. מורכבות הזמן של אלגוריתם הכוח הברוט היא O(MXN) , איפה M מציין את אורך הטקסט ו נ מציין את אורך התבנית.
אלגוריתם התאמת דפוסים נאיבי:
אלגוריתם התאמת דפוסים הנאיבי הוא שיפור לעומת האלגוריתם Brute Force. זה מונע השוואות מיותרות על ידי דילוג על כמה מיקומים בטקסט. האלגוריתם מתחיל להשוות את התבנית לטקסט במיקום הראשון. אם התווים תואמים, הוא עובר למיקום הבא וחוזר על ההשוואה. אם התווים אינם תואמים, האלגוריתם עובר למיקום הבא בטקסט ומשווה שוב את התבנית לטקסט. מורכבות הזמן של האלגוריתם הנאיבי היא גם O(MXN) , אבל הוא מהיר יותר מאלגוריתם Brute Force ברוב המקרים.
אלגוריתם קנוט-מוריס-פראט:
ה Knuth-Moris-Pratt (KMP) אלגוריתם הוא אלגוריתם התאמת תבניות מתקדם יותר. הוא מבוסס על התצפית שכאשר מתרחשת אי התאמה, ניתן להשתמש במידע מסוים על הטקסט והתבנית כדי למנוע השוואות מיותרות. האלגוריתם מחשב מראש טבלה המכילה מידע על התבנית. הטבלה קובעת כמה תווים של התבנית ניתן לדלג כאשר מתרחשת אי התאמה. מורכבות הזמן של KMP אלגוריתם הוא O(M+N) .
האלגוריתם של בויאר-מור:
אחד האלגוריתמים הפופולריים ביותר של התאמת דפוסים הוא בויאר-מור אַלגוֹרִיתְם. אלגוריתם זה פורסם לראשונה בשנת 1977 על ידי Robert S. Boyer ו-J Strother Moore. ה בויאר-מור אלגוריתם משווה דפוס עם קבוצה גדולה יותר של נתונים או טקסט מימין לשמאל במקום משמאל לימין, כמו ברוב האלגוריתמים האחרים של התאמת דפוסים.
ה בויאר-מור לאלגוריתם שני מרכיבים עיקריים: כלל התווים הרע וכלל הסיומת הטובה. כלל התווים הרע פועל על ידי השוואת התו בתבנית עם התו המקביל בנתונים או בטקסט. אם התווים אינם תואמים, האלגוריתם מזיז את התבנית ימינה עד שהוא מוצא תו תואם. כלל הסיומת הטובה משווה את הסיומת של התבנית עם הסיומת המתאימה של הנתונים או הטקסט. אם הסיומות אינן תואמות, האלגוריתם מזיז את התבנית ימינה עד שהוא מוצא סיומת תואמת.
ה בויאר-מור האלגוריתם ידוע ביעילותו ונמצא בשימוש נרחב ביישומים רבים. זה נחשב לאחד האלגוריתמים המהירים ביותר של התאמת דפוסים הזמינים.
יישום אלגוריתם Boyer-Moore ב-C:
כדי ליישם את בויאר-מור אלגוריתם ב-C, נוכל להתחיל בהגדרת כלל התווים הרע. אנו יכולים להשתמש במערך כדי לאחסן את המופע האחרון של כל תו בתבנית. מערך זה יכול לקבוע כמה רחוק עלינו להזיז את התבנית ימינה כאשר מתרחשת אי התאמה.
הנה דוגמה כיצד נוכל ליישם את כלל התווים הרע ב-C:
np.histogram
קוד C:
void bad_character_rule(char *pattern, int pattern_length, int *bad_char) { int i; for (i = 0; i <no_of_chars; i++) bad_char[i]="-1;" for (i="0;" i < pattern_length; bad_char[(int) pattern[i]]="i;" } pre> <p>In this example, we first initialize the array to -1 for all characters. We then iterate through the pattern and update the array with the last occurrence of each character in the pattern.</p> <p>Next, we can implement the good suffix rule. We can use an array to store the length of the longest suffix of the pattern that matches a suffix of the data or text. This array can be used to determine how far we need to move the pattern to the right.</p> <hr></no_of_chars;>