Pattern Matching je široce používán v informatice a mnoha dalších oborech. Algoritmy porovnávání vzorů se používají k vyhledávání vzorů v rámci většího textu nebo souboru dat. Jedním z nejpopulárnějších algoritmů pro porovnávání vzorů je Boyer-Moore algorithm, který byl poprvé publikován v roce 1977. V tomto článku se budeme zabývat algoritmy Pattern Matching v C a jak fungují.
Co je to algoritmus porovnávání vzorů?
Algoritmy porovnávání vzorů se používají k nalezení vzorů ve větší sadě dat nebo textu. Tyto algoritmy fungují tak, že porovnávají vzor s větší sadou dat nebo textem a určují, zda vzor je či není přítomen. Algoritmy porovnávání vzorů jsou důležité, protože nám umožňují rychle vyhledávat vzory ve velkých souborech dat.
c++ rozdělený řetězec
Algoritmus porovnávání vzorů hrubou silou:
Hrubá síla Pattern Matching je nejjednodušší algoritmus Pattern Matching. Zahrnuje porovnávání znaků vzoru se znaky textu jeden po druhém. Pokud se všechny znaky shodují, algoritmus vrátí počáteční pozici vzoru v textu. Pokud ne, algoritmus se přesune na další pozici v textu a opakuje porovnání, dokud není nalezena shoda nebo není dosaženo konce textu. Časová složitost algoritmu hrubé síly je O(MXN) , kde M označuje délku textu a N označuje délku vzoru.
Naivní algoritmus porovnávání vzorů:
Algoritmus Naive Pattern Matching je vylepšením algoritmu Brute Force. Vyhýbá se zbytečným srovnáváním přeskakováním některých pozic v textu. Algoritmus začne porovnávat vzor s textem na první pozici. Pokud se znaky shodují, přesune se na další pozici a zopakuje srovnání. Pokud se znaky neshodují, algoritmus se přesune na další pozici v textu a znovu porovná vzor s textem. Časová složitost naivního algoritmu je také O(MXN) , ale ve většině případů je rychlejší než algoritmus Brute Force.
Algoritmus Knuth-Morris-Pratt:
The Knuth-Morris-Pratt (KMP) Algorithm je pokročilejší algoritmus Pattern Matching. Vychází z pozorování, že když dojde k neshodě, lze použít některé informace o textu a vzoru, aby se předešlo zbytečným srovnáváním. Algoritmus předpočítá tabulku, která obsahuje informace o vzoru. Tabulka určuje, kolik znaků vzoru lze přeskočit, když dojde k neshodě. Časová složitost KMP algoritmus je O(M+N) .
Algoritmus Boyer-Moore:
Jedním z nejpopulárnějších algoritmů porovnávání vzorů je Boyer-Moore algoritmus. Tento algoritmus byl poprvé publikován v roce 1977 Robertem S. Boyerem a J Strotherem Moorem. The Boyer-Moore Algoritmus porovnává vzor s větší sadou dat nebo textu zprava doleva místo zleva doprava, jako u většiny ostatních algoritmů pro porovnávání vzorů.
The Boyer-Moore Algoritmus má dvě hlavní složky: pravidlo špatného charakteru a pravidlo dobré přípony. Pravidlo špatného znaku funguje tak, že porovnává znak ve vzoru s odpovídajícím znakem v datech nebo textu. Pokud se znaky neshodují, algoritmus posune vzor doprava, dokud nenajde znak, který se shoduje. Pravidlo dobré přípony porovnává příponu vzoru s odpovídající příponou dat nebo textu. Pokud se přípony neshodují, algoritmus posune vzor doprava, dokud nenajde odpovídající příponu.
The Boyer-Moore Algoritmus je známý svou účinností a je široce používán v mnoha aplikacích. Je považován za jeden z nejrychlejších dostupných algoritmů pro porovnávání vzorů.
Implementace Boyer-Moorova algoritmu v C:
K implementaci Boyer-Moore algoritmu v C, můžeme začít definováním pravidla špatné postavy. Můžeme použít pole k uložení posledního výskytu každého znaku ve vzoru. Toto pole může určit, jak daleko musíme posunout vzor doprava, když dojde k neshodě.
Zde je příklad toho, jak můžeme implementovat pravidlo špatné postavy v C:
10 1 milionu
C kód:
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;>