Pattern Matching tiek plaši izmantota datorzinātnēs un daudzās citās jomās. Pattern Matching algoritmi tiek izmantoti, lai meklētu modeļus lielākā teksta vai datu kopā. Viens no populārākajiem modeļu saskaņošanas algoritmiem ir Bojers-Mūrs algoritmu, kas pirmo reizi tika publicēts 1977. gadā. Šajā rakstā mēs apspriedīsim modeļu saskaņošanas algoritmus valodā C un to darbību.
Kas ir modeļu saskaņošanas algoritms?
Pattern Matching algoritmi tiek izmantoti, lai atrastu modeļus lielākā datu vai teksta kopā. Šie algoritmi darbojas, salīdzinot modeli ar lielāku datu kopu vai tekstu un nosakot, vai modelis ir vai nav. Pattern Matching algoritmi ir svarīgi, jo tie ļauj ātri meklēt modeļus lielās datu kopās.
java beigas
Brutālā spēka modeļa atbilstības algoritms:
Brute Force Pattern Matching ir vienkāršākais modeļu saskaņošanas algoritms. Tas ietver rakstzīmju salīdzināšanu ar teksta rakstzīmēm pa vienam. Ja visas rakstzīmes sakrīt, algoritms atgriež raksta sākuma pozīciju tekstā. Ja nē, algoritms pāriet uz nākamo teksta pozīciju un atkārto salīdzināšanu, līdz tiek atrasta atbilstība vai tiek sasniegts teksta beigas. Brutālā spēka algoritma laika sarežģītība ir O(MXN) , kur M apzīmē teksta garumu un N apzīmē raksta garumu.
Naivs modeļu saskaņošanas algoritms:
Naive Pattern Matching algoritms ir uzlabojums salīdzinājumā ar brutālā spēka algoritmu. Tas ļauj izvairīties no nevajadzīgiem salīdzinājumiem, izlaižot dažas pozīcijas tekstā. Algoritms sāk modeļa salīdzināšanu ar tekstu pirmajā pozīcijā. Ja rakstzīmes sakrīt, tas pāriet uz nākamo pozīciju un atkārto salīdzinājumu. Ja rakstzīmes nesakrīt, algoritms pāriet uz nākamo teksta pozīciju un vēlreiz salīdzina modeli ar tekstu. Naivā algoritma laika sarežģītība arī ir O(MXN) , taču vairumā gadījumu tas ir ātrāks par Brute Force algoritmu.
Knuta-Morisa-Prata algoritms:
The Knuts-Mors-Prats (KMP) algoritms ir uzlabots Pattern Matching algoritms. Tas ir balstīts uz novērojumu, ka, ja rodas neatbilstība, var izmantot kādu informāciju par tekstu un modeli, lai izvairītos no nevajadzīgiem salīdzinājumiem. Algoritms iepriekš aprēķina tabulu, kurā ir informācija par modeli. Tabula nosaka, cik rakstzīmes var izlaist, ja rodas neatbilstība. Laika sarežģītība KMP algoritms ir O(M+N) .
Boijera-Mūra algoritms:
Viens no populārākajiem modeļu saskaņošanas algoritmiem ir Bojers-Mūrs algoritms. Šo algoritmu 1977. gadā pirmo reizi publicēja Roberts S. Boiers un Dž. Stroters Mūrs. The Bojers-Mūrs algoritms salīdzina modeli ar lielāku datu vai teksta kopu no labās puses uz kreiso, nevis no kreisās puses uz labo, kā ar lielāko daļu citu paraugu saskaņošanas algoritmu.
The Bojers-Mūrs Algoritmam ir divas galvenās sastāvdaļas: slikta rakstzīmju noteikums un laba sufiksa noteikums. Slikto rakstzīmju noteikums darbojas, salīdzinot rakstzīmi rakstā ar atbilstošo rakstzīmi datos vai tekstā. Ja rakstzīmes nesakrīt, algoritms pārvieto modeli pa labi, līdz atrod atbilstošu rakstzīmi. Labā sufiksa noteikums salīdzina modeļa sufiksu ar atbilstošo datu vai teksta sufiksu. Ja sufiksi nesakrīt, algoritms pārvieto modeli pa labi, līdz atrod atbilstošu sufiksu.
The Bojers-Mūrs Algoritms ir pazīstams ar savu efektivitāti un tiek plaši izmantots daudzās lietojumprogrammās. Tas tiek uzskatīts par vienu no ātrākajiem pieejamajiem modeļu saskaņošanas algoritmiem.
Boyer-Moore algoritma ieviešana programmā C:
Lai īstenotu Bojers-Mūrs algoritmu C, mēs varam sākt, definējot slikto rakstzīmju noteikumu. Mēs varam izmantot masīvu, lai saglabātu katras rakstzīmes pēdējo reizi paraugā. Šis masīvs var noteikt, cik tālu mums ir jāpārvieto modelis pa labi, ja rodas neatbilstība.
Šeit ir piemērs tam, kā mēs varam ieviest slikto rakstzīmju noteikumu C:
izmēģiniet datu struktūru
C kods:
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;>