Usklađivanje uzoraka naširoko se koristi u informatici i mnogim drugim područjima. Algoritmi za podudaranje uzoraka koriste se za traženje uzoraka unutar većeg teksta ili skupa podataka. Jedan od najpopularnijih algoritama za podudaranje uzoraka je Boyer-Moore algoritam, koji je prvi put objavljen 1977. U ovom ćemo članku raspravljati o algoritmima usklađivanja uzorka u C-u i kako oni rade.
Što je algoritam podudaranja uzorka?
Algoritmi za podudaranje uzoraka koriste se za pronalaženje uzoraka unutar većeg skupa podataka ili teksta. Ovi algoritmi funkcioniraju uspoređujući uzorak s većim skupom podataka ili tekstom i utvrđujući je li uzorak prisutan ili ne. Algoritmi za podudaranje uzoraka važni su jer nam omogućuju brzo traženje uzoraka u velikim skupovima podataka.
inače ako bash
Algoritam za podudaranje uzorka grube sile:
Brute Force Pattern Matching najjednostavniji je algoritam Pattern Matching. Uključuje usporedbu znakova uzorka sa znakovima teksta jednog po jednog. Ako se svi znakovi podudaraju, algoritam vraća početnu poziciju uzorka u tekstu. Ako nije, algoritam se pomiče na sljedeću poziciju u tekstu i ponavlja usporedbu dok se ne pronađe podudaranje ili dok se ne dođe do kraja teksta. Vremenska složenost algoritma Brute Force je O(MXN) , gdje M označava duljinu teksta i N označava duljinu uzorka.
Naivni algoritam podudaranja uzorka:
Algoritam Naive Pattern Matching je poboljšanje u odnosu na algoritam Brute Force. Izbjegava nepotrebne usporedbe preskačući neka mjesta u tekstu. Algoritam počinje uspoređivati uzorak s tekstom na prvoj poziciji. Ako se znakovi podudaraju, pomiče se na sljedeću poziciju i ponavlja usporedbu. Ako se znakovi ne podudaraju, algoritam se pomiče na sljedeću poziciju u tekstu i ponovno uspoređuje uzorak s tekstom. Vremenska složenost Naivnog algoritma također je O(MXN) , ali je u većini slučajeva brži od algoritma Brute Force.
Knuth-Morris-Prattov algoritam:
The Knuth-Morris-Pratt (KMP) algoritam je napredniji algoritam usklađivanja uzorka. Temelji se na zapažanju da se, kada dođe do neslaganja, neke informacije o tekstu i uzorku mogu koristiti kako bi se izbjegle nepotrebne usporedbe. Algoritam unaprijed izračunava tablicu koja sadrži informacije o uzorku. Tablica određuje koliko se znakova uzorka može preskočiti kada dođe do neslaganja. Vremenska složenost KMP algoritam je O(M+N) .
Boyer-Mooreov algoritam:
Jedan od najpopularnijih algoritama za usklađivanje uzoraka je Boyer-Moore algoritam. Ovaj algoritam su prvi put objavili 1977. Robert S. Boyer i J Strother Moore. The Boyer-Moore algoritam uspoređuje uzorak s većim skupom podataka ili teksta s desna na lijevo umjesto slijeva na desno, kao kod većine drugih algoritama za podudaranje uzoraka.
The Boyer-Moore algoritam ima dvije glavne komponente: pravilo lošeg znaka i pravilo dobrog sufiksa. Pravilo lošeg znaka funkcionira tako da se znak u uzorku uspoređuje s odgovarajućim znakom u podacima ili tekstu. Ako se znakovi ne podudaraju, algoritam pomiče uzorak udesno dok ne pronađe znak koji odgovara. Pravilo dobrog sufiksa uspoređuje sufiks uzorka s odgovarajućim sufiksom podataka ili teksta. Ako se sufiksi ne podudaraju, algoritam pomiče uzorak udesno dok ne pronađe odgovarajući sufiks.
The Boyer-Moore Algoritam je poznat po svojoj učinkovitosti i naširoko se koristi u mnogim aplikacijama. Smatra se jednim od najbržih dostupnih algoritama za usklađivanje uzoraka.
Implementacija Boyer-Moore algoritma u C:
Za provedbu Boyer-Moore algoritma u C-u, možemo započeti definiranjem pravila lošeg znaka. Možemo koristiti niz za pohranjivanje posljednjeg pojavljivanja svakog znaka u uzorku. Ovaj niz može odrediti koliko daleko moramo pomaknuti uzorak udesno kada dođe do neusklađenosti.
Evo primjera kako možemo implementirati pravilo loših znakova u C:
nova linija u pythonu
C kod:
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;>