Dopasowywanie wzorców jest szeroko stosowane w informatyce i wielu innych dziedzinach. Algorytmy dopasowywania wzorców służą do wyszukiwania wzorców w większym tekście lub zestawie danych. Jednym z najpopularniejszych algorytmów dopasowywania wzorców jest Boyera-Moore'a algorytm, który został po raz pierwszy opublikowany w 1977 roku. W tym artykule omówimy algorytmy Pattern Matching w C i ich działanie.
Co to jest algorytm dopasowywania wzorców?
Algorytmy dopasowywania wzorców służą do znajdowania wzorców w większym zestawie danych lub tekście. Algorytmy te działają poprzez porównanie wzorca z większym zbiorem danych lub tekstem i określenie, czy wzorzec występuje. Algorytmy dopasowywania wzorców są ważne, ponieważ pozwalają nam szybko wyszukiwać wzorce w dużych zbiorach danych.
dziedziczenie javy
Algorytm dopasowywania wzorców brutalnej siły:
Dopasowywanie wzorców Brute Force to najprostszy algorytm dopasowywania wzorców. Polega ona na porównywaniu kolejno znaków wzoru ze znakami tekstu. Jeżeli wszystkie znaki pasują, algorytm zwraca pozycję początkową wzorca w tekście. Jeśli nie, algorytm przechodzi do następnej pozycji w tekście i powtarza porównanie, aż do znalezienia dopasowania lub osiągnięcia końca tekstu. Złożoność czasowa algorytmu brutalnej siły wynosi O(MXN) , Gdzie M oznacza długość tekstu i N oznacza długość wzoru.
Naiwny algorytm dopasowywania wzorców:
Algorytm Naive Pattern Matching stanowi ulepszenie w stosunku do algorytmu Brute Force. Pozwala uniknąć niepotrzebnych porównań poprzez pominięcie niektórych pozycji w tekście. Algorytm rozpoczyna porównywanie wzorca z tekstem znajdującym się na pierwszej pozycji. Jeśli znaki pasują, przechodzi do następnej pozycji i powtarza porównanie. Jeżeli znaki nie pasują, algorytm przechodzi do kolejnej pozycji w tekście i ponownie porównuje wzór z tekstem. Złożoność czasowa algorytmu Naive jest również O(MXN) , ale w większości przypadków jest szybszy niż algorytm Brute Force.
Algorytm Knutha-Morrisa-Pratta:
The Knuth-Morris-Pratt (KMP) Algorytm jest bardziej zaawansowanym algorytmem dopasowywania wzorców. Opiera się na obserwacji, że w przypadku wystąpienia niezgodności można wykorzystać pewne informacje dotyczące tekstu i wzoru, aby uniknąć niepotrzebnych porównań. Algorytm wstępnie oblicza tabelę zawierającą informacje o wzorcu. Tabela określa, ile znaków wzorca można pominąć w przypadku wystąpienia niezgodności. Złożoność czasowa KMP algorytm jest O(M+N) .
Algorytm Boyera-Moore'a:
Jednym z najpopularniejszych algorytmów dopasowywania wzorców jest Boyera-Moore'a algorytm. Algorytm ten został po raz pierwszy opublikowany w 1977 roku przez Roberta S. Boyera i J Strothera Moore'a. The Boyera-Moore'a algorytm porównuje wzorzec z większym zestawem danych lub tekstu od prawej do lewej zamiast od lewej do prawej, jak w przypadku większości innych algorytmów dopasowywania wzorców.
The Boyera-Moore'a Algorytm składa się z dwóch głównych elementów: reguły złego znaku i reguły dobrego przyrostka. Zasada złego znaku działa poprzez porównanie znaku we wzorcu z odpowiadającym mu znakiem w danych lub tekście. Jeśli znaki nie pasują, algorytm przesuwa wzór w prawo, aż znajdzie pasujący znak. Zasada dobrego sufiksu porównuje sufiks wzorca z odpowiadającym mu sufiksem danych lub tekstu. Jeśli przyrostki nie pasują, algorytm przesuwa wzór w prawo, aż znajdzie pasujący przyrostek.
The Boyera-Moore'a Algorytm jest znany ze swojej wydajności i jest szeroko stosowany w wielu zastosowaniach. Jest uważany za jeden z najszybszych dostępnych algorytmów dopasowywania wzorców.
Implementacja algorytmu Boyera-Moore'a w C:
Aby wdrożyć Boyera-Moore'a algorytmu w C, możemy zacząć od zdefiniowania reguły złego znaku. Możemy użyć tablicy do przechowywania ostatniego wystąpienia każdego znaku we wzorcu. Tablica ta może określić, jak daleko musimy przesunąć wzór w prawo, gdy wystąpi niezgodność.
Oto przykład, jak możemy zaimplementować regułę złego znaku w C:
algorytm Bellforda
Kod 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;>