Pattern Matching er meget udbredt inden for datalogi og mange andre områder. Mønstertilpasningsalgoritmer bruges til at søge efter mønstre i en større tekst eller datasæt. En af de mest populære algoritmer til mønstermatchning er Boyer-Moore algoritme, som først blev offentliggjort i 1977. I denne artikel vil vi diskutere Pattern Matching-algoritmer i C, og hvordan de virker.
Hvad er en mønstertilpasningsalgoritme?
Mønstermatchende algoritmer bruges til at finde mønstre inden for et større sæt data eller tekst. Disse algoritmer fungerer ved at sammenligne et mønster med et større datasæt eller tekst og afgøre, om mønsteret er til stede eller ej. Mønstermatchningsalgoritmer er vigtige, fordi de giver os mulighed for hurtigt at søge efter mønstre i store datasæt.
statisk i c
Brute Force Pattern Matching Algoritme:
Brute Force Pattern Matching er den enkleste Pattern Matching Algorithm. Det går ud på at sammenligne mønstrets tegn med tekstens tegn én efter én. Hvis alle tegnene matcher, returnerer algoritmen startpositionen for mønsteret i teksten. Hvis ikke, flytter algoritmen til den næste position i teksten og gentager sammenligningen, indtil der er fundet et match, eller slutningen af teksten er nået. Tidskompleksiteten af Brute Force Algorithm er O(MXN) , hvor M angiver længden af teksten og N angiver længden af mønsteret.
Naiv mønstermatchningsalgoritme:
Naive Pattern Matching-algoritmen er en forbedring i forhold til Brute Force-algoritmen. Det undgår unødvendige sammenligninger ved at springe nogle positioner over i teksten. Algoritmen begynder at sammenligne mønsteret med teksten ved den første position. Hvis tegnene matcher, flytter den til den næste position og gentager sammenligningen. Hvis tegnene ikke stemmer overens, flytter algoritmen til næste position i teksten og sammenligner mønsteret med teksten igen. Tidskompleksiteten af den naive algoritme er også O(MXN) , men det er hurtigere end Brute Force-algoritmen i de fleste tilfælde.
Knuth-Morris-Pratt Algoritme:
Det Knuth-Morris-Pratt (KMP) algoritme er en mere avanceret Pattern Matching-algoritme. Det er baseret på den observation, at når der opstår en mismatch, kan nogle oplysninger om teksten og mønsteret bruges til at undgå unødvendige sammenligninger. Algoritmen forudberegner en tabel, der indeholder information om mønsteret. Tabellen bestemmer, hvor mange tegn i mønsteret, der kan springes over, når der opstår en uoverensstemmelse. Tidskompleksiteten af KMP algoritme er O(M+N) .
Boyer-Moore-algoritmen:
En af de mest populære Pattern Matching-algoritmer er Boyer-Moore algoritme. Denne algoritme blev første gang udgivet i 1977 af Robert S. Boyer og J Strother Moore. Det Boyer-Moore algoritme sammenligner et mønster med et større sæt data eller tekst fra højre mod venstre i stedet for venstre mod højre, som med de fleste andre mønstermatchende algoritmer.
Det Boyer-Moore Algoritmen har to hovedkomponenter: reglen om dårlige tegn og reglen om det gode suffiks. Reglen om dårlige tegn fungerer ved at sammenligne tegnet i mønsteret med det tilsvarende tegn i data eller tekst. Hvis tegnene ikke matcher, flytter algoritmen mønsteret til højre, indtil den finder et tegn, der matcher. Reglen for gode suffiks sammenligner mønsterets suffiks med det tilsvarende suffiks af data eller tekst. Hvis suffikserne ikke stemmer overens, flytter algoritmen mønsteret til højre, indtil den finder et matchende suffiks.
Det Boyer-Moore Algoritme er kendt for sin effektivitet og er meget udbredt i mange applikationer. Det betragtes som en af de hurtigste mønstertilpasningsalgoritmer til rådighed.
Implementering af Boyer-Moore-algoritmen i C:
At implementere Boyer-Moore algoritme i C, kan vi starte med at definere reglen om dårlig karakter. Vi kan bruge en matrix til at gemme den sidste forekomst af hvert tegn i mønsteret. Dette array kan bestemme, hvor langt vi skal flytte mønsteret til højre, når der opstår en uoverensstemmelse.
Her er et eksempel på, hvordan vi kan implementere reglen om dårlig karakter i C:
forskel på middag og aftensmad
C kode:
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;>