Ujemanje vzorcev se pogosto uporablja v računalništvu in na številnih drugih področjih. Algoritmi za ujemanje vzorcev se uporabljajo za iskanje vzorcev v večjem besedilu ali nizu podatkov. Eden najbolj priljubljenih algoritmov za ujemanje vzorcev je Boyer-Moore algoritem, ki je bil prvič objavljen leta 1977. V tem članku bomo razpravljali o algoritmih za ujemanje vzorcev v C in o tem, kako delujejo.
Kaj je algoritem za ujemanje vzorcev?
Algoritmi za ujemanje vzorcev se uporabljajo za iskanje vzorcev znotraj večjega niza podatkov ali besedila. Ti algoritmi delujejo tako, da primerjajo vzorec z večjim naborom podatkov ali besedilom in ugotovijo, ali je vzorec prisoten ali ne. Algoritmi za ujemanje vzorcev so pomembni, ker nam omogočajo hitro iskanje vzorcev v velikih nizih podatkov.
ovojnica besedila css
Algoritem za ujemanje vzorcev s surovo silo:
Brute Force Pattern Matching je najpreprostejši algoritem za ujemanje vzorcev. Vključuje primerjavo znakov vzorca z znaki besedila enega za drugim. Če se vsi znaki ujemajo, algoritem vrne začetni položaj vzorca v besedilu. Če ni, se algoritem premakne na naslednji položaj v besedilu in ponavlja primerjavo, dokler ne najde ujemanja ali dokler ni dosežen konec besedila. Časovna kompleksnost algoritma surove sile je O(MXN) , kje M označuje dolžino besedila in n označuje dolžino vzorca.
Naivni algoritem za ujemanje vzorcev:
Algoritem Naive Pattern Matching je izboljšava v primerjavi z algoritmom Brute Force. Izogne se nepotrebnim primerjavam s preskokom nekaterih mest v besedilu. Algoritem začne primerjati vzorec z besedilom na prvi poziciji. Če se znaka ujemata, se premakne na naslednji položaj in ponovi primerjavo. Če se znaka ne ujemata, se algoritem premakne na naslednje mesto v besedilu in ponovno primerja vzorec z besedilom. Tudi časovna kompleksnost naivnega algoritma je O(MXN) , vendar je v večini primerov hitrejši od algoritma Brute Force.
Knuth-Morris-Prattov algoritem:
The Knuth-Morris-Pratt (KMP) algoritem je naprednejši algoritem za ujemanje vzorcev. Temelji na ugotovitvi, da se lahko, ko pride do neujemanja, uporabi nekaj informacij o besedilu in vzorcu, da se izognemo nepotrebnim primerjavam. Algoritem vnaprej izračuna tabelo, ki vsebuje informacije o vzorcu. Tabela določa, koliko znakov vzorca je mogoče preskočiti, ko pride do neujemanja. Časovna zapletenost KMP algoritem je O(M+N) .
Boyer-Moorov algoritem:
Eden najbolj priljubljenih algoritmov za ujemanje vzorcev je Boyer-Moore algoritem. Ta algoritem sta leta 1977 prvič objavila Robert S. Boyer in J Strother Moore. The Boyer-Moore algoritem primerja vzorec z večjim naborom podatkov ali besedila od desne proti levi namesto od leve proti desni, kot pri večini drugih algoritmov za ujemanje vzorcev.
The Boyer-Moore algoritem ima dve glavni komponenti: pravilo slabih znakov in pravilo dobrih končnic. Pravilo slabega znaka deluje tako, da primerja znak v vzorcu z ustreznim znakom v podatkih ali besedilu. Če se znaka ne ujemata, algoritem premakne vzorec v desno, dokler ne najde znaka, ki se ujema. Pravilo dobre pripone primerja pripono vzorca z ustrezno pripono podatkov ali besedila. Če se priponi ne ujemata, algoritem premakne vzorec v desno, dokler ne najde ujemajoče se pripone.
The Boyer-Moore Algoritem je znan po svoji učinkovitosti in se pogosto uporablja v številnih aplikacijah. Velja za enega najhitrejših razpoložljivih algoritmov za ujemanje vzorcev.
Implementacija algoritma Boyer-Moore v C:
Za izvajanje Boyer-Moore algoritma v C, lahko začnemo z definiranjem pravila slabih znakov. Za shranjevanje zadnje pojavitve vsakega znaka v vzorcu lahko uporabimo matriko. Ta niz lahko določi, kako daleč moramo premakniti vzorec v desno, ko pride do neujemanja.
Tukaj je primer, kako lahko implementiramo pravilo slabih znakov v C:
nadaljnji podatkovni tipi
koda 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;>