Pattern Matching je široko používaný v informatike a mnohých ďalších oblastiach. Algoritmy zhody vzorov sa používajú na vyhľadávanie vzorov v rámci väčšieho textu alebo súboru údajov. Jeden z najpopulárnejších algoritmov na porovnávanie vzorov je Boyer-Moore algoritmu, ktorý bol prvýkrát publikovaný v roku 1977. V tomto článku sa budeme zaoberať algoritmami zhody vzorov v jazyku C a ako fungujú.
Čo je to algoritmus zhody vzorov?
Algoritmy zhody vzorov sa používajú na nájdenie vzorov vo väčšom súbore údajov alebo textu. Tieto algoritmy fungujú tak, že porovnávajú vzor s väčším súborom údajov alebo textom a určujú, či vzor existuje alebo nie. Algoritmy zhody vzorov sú dôležité, pretože nám umožňujú rýchlo vyhľadávať vzory vo veľkých súboroch údajov.
algoritmus mergesort
Algoritmus na porovnávanie vzorov hrubou silou:
Hrubá sila Pattern Matching je najjednoduchší algoritmus Pattern Matching. Zahŕňa porovnávanie znakov vzoru so znakmi textu jeden po druhom. Ak sa všetky znaky zhodujú, algoritmus vráti počiatočnú pozíciu vzoru v texte. Ak nie, algoritmus sa presunie na ďalšiu pozíciu v texte a zopakuje porovnanie, kým sa nenájde zhoda alebo sa nedosiahne koniec textu. Časová zložitosť algoritmu hrubej sily je O (MXN) , kde M označuje dĺžku textu a N označuje dĺžku vzoru.
Naivný algoritmus zhody vzorov:
Algoritmus Naive Pattern Matching je vylepšením algoritmu Brute Force. Vyhýba sa zbytočným porovnávaniam preskakovaním niektorých pozícií v texte. Algoritmus začne porovnávať vzor s textom na prvej pozícii. Ak sa znaky zhodujú, presunie sa na ďalšiu pozíciu a zopakuje porovnanie. Ak sa znaky nezhodujú, algoritmus sa presunie na ďalšiu pozíciu v texte a znova porovná vzor s textom. Časová zložitosť naivného algoritmu je tiež O (MXN) , ale vo väčšine prípadov je rýchlejší ako algoritmus Brute Force.
Algoritmus Knuth-Morris-Pratt:
The Knuth-Morris-Pratt (KMP) Algoritmus je pokročilejší algoritmus zhody vzorov. Vychádza z pozorovania, že keď sa vyskytne nesúlad, niektoré informácie o texte a vzore možno použiť, aby sa predišlo zbytočným porovnávaniam. Algoritmus vopred vypočíta tabuľku, ktorá obsahuje informácie o vzore. Tabuľka určuje, koľko znakov vzoru možno preskočiť, keď dôjde k nezhode. Časová zložitosť KMP algoritmus je O(M+N) .
Algoritmus Boyer-Moore:
Jedným z najpopulárnejších algoritmov na porovnávanie vzorov je Boyer-Moore algoritmu. Tento algoritmus prvýkrát publikovali v roku 1977 Robert S. Boyer a J Strother Moore. The Boyer-Moore Algoritmus porovnáva vzor s väčším súborom údajov alebo textu sprava doľava namiesto zľava doprava, ako pri väčšine iných algoritmov na porovnávanie vzorov.
The Boyer-Moore Algoritmus má dve hlavné zložky: pravidlo zlého charakteru a pravidlo dobrej prípony. Pravidlo zlého znaku funguje tak, že sa znak vo vzore porovnáva so zodpovedajúcim znakom v údajoch alebo texte. Ak sa znaky nezhodujú, algoritmus posunie vzor doprava, kým nenájde znak, ktorý sa zhoduje. Pravidlo dobrej prípony porovnáva príponu vzoru so zodpovedajúcou príponou údajov alebo textu. Ak sa prípony nezhodujú, algoritmus posunie vzor doprava, kým nenájde zhodnú príponu.
The Boyer-Moore Algoritmus je známy svojou účinnosťou a je široko používaný v mnohých aplikáciách. Považuje sa za jeden z najrýchlejších dostupných algoritmov na porovnávanie vzorov.
Implementácia Boyer-Mooreovho algoritmu v C:
Na implementáciu Boyer-Moore algoritmu v C, môžeme začať definovaním pravidla zlého charakteru. Na uloženie posledného výskytu každého znaku vo vzore môžeme použiť pole. Toto pole môže určiť, ako ďaleko musíme posunúť vzor doprava, keď dôjde k nesúladu.
Tu je príklad toho, ako môžeme implementovať pravidlo zlého charakteru v C:
mesto v USA
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;>