Potrivirea modelelor este utilizată pe scară largă în informatică și în multe alte domenii. Algoritmii de potrivire a modelelor sunt utilizați pentru a căuta modele într-un text sau un set de date mai mare. Unul dintre cei mai populari algoritmi pentru potrivirea modelelor este Boyer-Moore algoritm, care a fost publicat pentru prima dată în 1977. În acest articol, vom discuta despre algoritmii de potrivire a modelelor în C și cum funcționează aceștia.
Ce este un algoritm de potrivire a modelelor?
Algoritmii de potrivire a modelelor sunt utilizați pentru a găsi modele într-un set mai mare de date sau text. Acești algoritmi funcționează prin compararea unui model cu un set de date sau text mai mare și determinând dacă modelul este prezent sau nu. Algoritmii de potrivire a modelelor sunt importanți deoarece ne permit să căutăm rapid modele în seturi mari de date.
altfel dacă bash
Algoritmul de potrivire a modelului de forță brută:
Potrivirea modelelor de forță brută este cel mai simplu algoritm de potrivire a modelelor. Presupune compararea caracterelor tiparului cu personajele textului unul câte unul. Dacă toate caracterele se potrivesc, algoritmul returnează poziția de pornire a modelului în text. Dacă nu, algoritmul trece la următoarea poziție din text și repetă comparația până când se găsește o potrivire sau se ajunge la sfârșitul textului. Complexitatea temporală a algoritmului de forță brută este O(MXN) , Unde M denotă lungimea textului și N denotă lungimea modelului.
Algoritmul naiv de potrivire a modelelor:
Algoritmul Naive Pattern Matching este o îmbunătățire față de algoritmul Brute Force. Evită comparațiile inutile, omitând unele poziții din text. Algoritmul începe să compare modelul cu textul din prima poziție. Dacă personajele se potrivesc, se trece la următoarea poziția și repetă comparația. Dacă caracterele nu se potrivesc, algoritmul trece la următoarea poziție din text și compară din nou modelul cu textul. Complexitatea temporală a algoritmului Naive este de asemenea O(MXN) , dar este mai rapid decât algoritmul Brute Force în majoritatea cazurilor.
Algoritmul Knuth-Morris-Pratt:
The Knuth-Morris-Pratt (KMP) algoritmul este un algoritm mai avansat de potrivire a modelelor. Se bazează pe observația că atunci când apare o nepotrivire, unele informații despre text și model pot fi folosite pentru a evita comparațiile inutile. Algoritmul precalculează un tabel care conține informații despre model. Tabelul determină câte caractere ale modelului pot fi sărite atunci când apare o nepotrivire. Complexitatea timpului a KMP algoritmul este O(M+N) .
Algoritmul Boyer-Moore:
Unul dintre cei mai populari algoritmi de potrivire a modelelor este Boyer-Moore algoritm. Acest algoritm a fost publicat pentru prima dată în 1977 de Robert S. Boyer și J Strother Moore. The Boyer-Moore algoritmul compară un model cu un set mai mare de date sau text de la dreapta la stânga în loc de la stânga la dreapta, ca în cazul majorității altor algoritmi de potrivire a modelelor.
The Boyer-Moore algoritmul are două componente principale: regula caracterului rău și regula sufixului bun. Regula caracterelor proaste funcționează prin compararea caracterului din model cu caracterul corespunzător din date sau text. Dacă caracterele nu se potrivesc, algoritmul mută modelul spre dreapta până când găsește un caracter care se potrivește. Regula sufixului bun compară sufixul modelului cu sufixul corespunzător datelor sau textului. Dacă sufixele nu se potrivesc, algoritmul mută modelul spre dreapta până când găsește un sufix care se potrivește.
The Boyer-Moore algoritmul este cunoscut pentru eficiența sa și este utilizat pe scară largă în multe aplicații. Este considerat unul dintre cei mai rapidi algoritmi de potrivire a modelelor disponibile.
Implementarea algoritmului Boyer-Moore în C:
Pentru a implementa Boyer-Moore algoritm în C, putem începe prin definirea regulii caracterului rău. Putem folosi o matrice pentru a stoca ultima apariție a fiecărui caracter din model. Această matrice poate determina cât de departe trebuie să mutăm modelul spre dreapta atunci când apare o nepotrivire.
Iată un exemplu despre cum putem implementa regula caracterului rău în C:
ekta kapoor actor
cod 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;>