Pattern Matching yra plačiai naudojamas kompiuterių moksle ir daugelyje kitų sričių. Pattern Matching algoritmai naudojami ieškant šablonų didesniame tekste ar duomenų rinkinyje. Vienas iš populiariausių modelių derinimo algoritmų yra Boyeris-Moore'as Šiame straipsnyje aptarsime šablonų atitikimo algoritmus C ir kaip jie veikia.
Kas yra modelio atitikimo algoritmas?
Pattern Matching algoritmai naudojami didesnio duomenų ar teksto rinkinio šablonams rasti. Šie algoritmai veikia lygindami šabloną su didesniu duomenų rinkiniu arba tekstu ir nustatydami, ar modelis yra, ar ne. Pattern Matching algoritmai yra svarbūs, nes jie leidžia greitai ieškoti šablonų dideliuose duomenų rinkiniuose.
palyginama java
Brute Force modelio atitikimo algoritmas:
Brute Force Pattern Matching yra paprasčiausias modelio suderinimo algoritmas. Tai apima rašto simbolių palyginimą su teksto simboliais po vieną. Jei visi simboliai sutampa, algoritmas grąžina pradinę šablono padėtį tekste. Jei ne, algoritmas pereina į kitą teksto vietą ir kartoja palyginimą, kol randama atitiktis arba pasiekiama teksto pabaiga. Brute Force algoritmo laiko sudėtingumas yra O (MXN) , kur M žymi teksto ilgį ir N žymi rašto ilgį.
Naivus modelio atitikimo algoritmas:
Naive Pattern Matching algoritmas yra patobulinimas, palyginti su Brute Force algoritmu. Taip išvengiama nereikalingų palyginimų praleidžiant kai kurias teksto pozicijas. Algoritmas pradeda lyginti šabloną su tekstu pirmoje pozicijoje. Jei simboliai sutampa, jis pereina į kitą vietą ir kartoja palyginimą. Jei simboliai nesutampa, algoritmas pereina į kitą teksto vietą ir vėl lygina šabloną su tekstu. Naivo algoritmo laiko sudėtingumas taip pat yra O (MXN) , tačiau daugeliu atvejų jis yra greitesnis nei Brute Force algoritmas.
Knutho-Morris-Pratto algoritmas:
The Knuth-Morris-Pratt (KMP) algoritmas yra pažangesnis modelio atitikimo algoritmas. Jis pagrįstas pastebėjimu, kad kai įvyksta neatitikimas, tam tikra informacija apie tekstą ir šabloną gali būti naudojama siekiant išvengti nereikalingų palyginimų. Algoritmas iš anksto apskaičiuoja lentelę, kurioje yra informacijos apie šabloną. Lentelėje nustatoma, kiek rašto simbolių galima praleisti, kai atsiranda neatitikimas. Laiko sudėtingumas KMP algoritmas yra O (M+N) .
Boyer-Moore algoritmas:
Vienas iš populiariausių modelių atitikimo algoritmų yra Boyeris-Moore'as algoritmas. Šį algoritmą 1977 m. pirmą kartą paskelbė Robert S. Boyer ir J Strother Moore. The Boyeris-Moore'as algoritmas lygina šabloną su didesniu duomenų ar teksto rinkiniu iš dešinės į kairę, o ne iš kairės į dešinę, kaip ir dauguma kitų šablonų atitikimo algoritmų.
The Boyeris-Moore'as Algoritmą sudaro du pagrindiniai komponentai: blogo simbolio taisyklė ir geros priesagos taisyklė. Blogo simbolio taisyklė veikia lyginant rašto simbolį su atitinkamu duomenų ar teksto simboliu. Jei simboliai nesutampa, algoritmas perkelia šabloną į dešinę, kol randa atitinkantį simbolį. Geros galūnės taisyklė lygina modelio galūnę su atitinkama duomenų ar teksto priesaga. Jei priesagos nesutampa, algoritmas perkelia šabloną į dešinę, kol randa atitinkamą galūnę.
The Boyeris-Moore'as Algoritmas yra žinomas dėl savo efektyvumo ir yra plačiai naudojamas daugelyje programų. Jis laikomas vienu greičiausių modelių derinimo algoritmų.
Boyer-Moore algoritmo įgyvendinimas C:
Norėdami įgyvendinti Boyeris-Moore'as algoritmą C, galime pradėti apibrėždami blogo simbolio taisyklę. Mes galime naudoti masyvą, kad išsaugotume paskutinį kiekvieno simbolio pasireiškimą šablone. Šis masyvas gali nustatyti, kiek turime perkelti šabloną į dešinę, kai atsiranda neatitikimas.
Štai pavyzdys, kaip galime įgyvendinti blogo simbolio taisyklę C:
kiek nulių 1 mlrd
C kodas:
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;>