Il Pattern Matching è ampiamente utilizzato nell'informatica e in molti altri campi. Gli algoritmi di corrispondenza dei modelli vengono utilizzati per cercare modelli all'interno di un testo o di un set di dati più grande. Uno degli algoritmi più popolari per la corrispondenza dei modelli è il Boyer-Moore algoritmo, che è stato pubblicato per la prima volta nel 1977. In questo articolo discuteremo degli algoritmi di Pattern Matching in C e di come funzionano.
Che cos'è un algoritmo di corrispondenza dei modelli?
Gli algoritmi di corrispondenza dei modelli vengono utilizzati per trovare modelli all'interno di un insieme più ampio di dati o testo. Questi algoritmi funzionano confrontando un modello con un set di dati o testo più grande e determinando se il modello è presente o meno. Gli algoritmi di corrispondenza dei modelli sono importanti perché ci consentono di cercare rapidamente modelli in set di dati di grandi dimensioni.
casuale c
Algoritmo di corrispondenza dei modelli di forza bruta:
Brute Force Pattern Matching è l'algoritmo di pattern matching più semplice. Si tratta di confrontare i caratteri del modello con i caratteri del testo uno per uno. Se tutti i caratteri corrispondono, l'algoritmo restituisce la posizione iniziale del modello nel testo. In caso contrario, l'algoritmo si sposta alla posizione successiva nel testo e ripete il confronto finché non viene trovata una corrispondenza o viene raggiunta la fine del testo. La complessità temporale dell'algoritmo della forza bruta lo è O(MXN) , Dove M denota la lunghezza del testo e N denota la lunghezza del modello.
Algoritmo di corrispondenza dei modelli ingenuo:
L'algoritmo Naive Pattern Matching è un miglioramento rispetto all'algoritmo Brute Force. Evita confronti inutili saltando alcune posizioni nel testo. L'algoritmo inizia a confrontare il modello con il testo nella prima posizione. Se i caratteri corrispondono, si sposta alla posizione successiva e ripete il confronto. Se i caratteri non corrispondono, l'algoritmo si sposta alla posizione successiva nel testo e confronta nuovamente il modello con il testo. Anche la complessità temporale dell'algoritmo Naive lo è O(MXN) , ma nella maggior parte dei casi è più veloce dell'algoritmo Brute Force.
Algoritmo di Knuth-Morris-Pratt:
IL Knuth-Morris-Pratt (KMP) L'algoritmo è un algoritmo di Pattern Matching più avanzato. Si basa sull'osservazione che quando si verifica una mancata corrispondenza, alcune informazioni sul testo e sul modello possono essere utilizzate per evitare confronti non necessari. L'algoritmo precalcola una tabella che contiene informazioni sul modello. La tabella determina quanti caratteri del modello possono essere saltati quando si verifica una mancata corrispondenza. La complessità temporale del KMP l'algoritmo è O(M+N) .
L'algoritmo di Boyer-Moore:
Uno degli algoritmi di Pattern Matching più popolari è il Boyer-Moore algoritmo. Questo algoritmo è stato pubblicato per la prima volta nel 1977 da Robert S. Boyer e J Strother Moore. IL Boyer-Moore L'algoritmo confronta un modello con un insieme più ampio di dati o testo da destra a sinistra anziché da sinistra a destra, come con la maggior parte degli altri algoritmi di corrispondenza dei modelli.
IL Boyer-Moore L'algoritmo ha due componenti principali: la regola dei caratteri cattivi e la regola dei suffissi buoni. La regola dei caratteri errati funziona confrontando il carattere nel modello con il carattere corrispondente nei dati o nel testo. Se i caratteri non corrispondono, l'algoritmo sposta il modello a destra finché non trova un carattere corrispondente. La buona regola del suffisso confronta il suffisso del modello con il suffisso corrispondente dei dati o del testo. Se i suffissi non corrispondono, l'algoritmo sposta il modello a destra finché non trova un suffisso corrispondente.
IL Boyer-Moore L'algoritmo è noto per la sua efficienza ed è ampiamente utilizzato in molte applicazioni. È considerato uno degli algoritmi di corrispondenza dei modelli più veloci disponibili.
Implementazione dell'algoritmo Boyer-Moore in C:
Per implementare il Boyer-Moore algoritmo in C, possiamo iniziare definendo la regola dei caratteri errati. Possiamo usare un array per memorizzare l'ultima occorrenza di ciascun carattere nel modello. Questo array può determinare di quanto dobbiamo spostare il pattern verso destra quando si verifica una mancata corrispondenza.
Ecco un esempio di come possiamo implementare la regola dei caratteri errati in C:
alfabeto per numeri
Codice 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;>