Algoritmy pre reťazce

Knuth-Morris-Prathov algoritmus

Popis
Tento algoritmus vychádza z myšlienky, že je zbytočné vracať sa pri neúspešnom porovnaní v reťazci späť a porovnávať znova znaky, ktoré už porovnané boli. Aby sme sa nemuseli vracať späť, vytvoríme si pred začatím vyhľadávania tabuľku, v ktorej budeme mať pre každú pozíciu vo vzore napísané číslo, ktoré nám bude určovať, koľký prvok vzoru máme porovnávať s aktuálnym znakom v reťazci, ak bolo porovnanie na tejto pozícii neúspešné a my sa nechceme vrátiť v reťazci späť k pozícii začatia porovnávania (presnejšie k nasledujúcej pozícii od pozície začatia porovnávania).

Vstupy algoritmu
Vstupom je ako v predošlom algoritme ukazovateľ na vzor a reťazec a počty znakov, ktoré vzor a reťazec obsahujú. Spomínanú tabuľku si algoritmus vytvára sám a preto ju nemusíme považovať za vstup.

Princíp činnosti
Algoritmus najprv vytvorí tabuľku, v ktorej bude mať zapísané, s ktorým znakom vzoru má porovnať aktuálny znak reťazca pri neúspešnom porovnaní. Táto hodnota sa môže líšiť pre každý znak vzoru. Znamená to, že pri nájdení nezhody nemusí prechádzať už porovnané prvky, ale číslo z tabuľky mu dá informáciu o tom, s ktorým znakom vzoru má tento aktuálny znak reťazca porovnať pred ďalším posunom v reťazci tak, aby zbytočne nemrhal časom a porovnaniami, ktoré vlastne už vykonal. KMP algoritmus podobne ako sekvenčný algoritmus prechádza reťazec od začiatku ku koncu, ale v prípade nezhody pokračuje v porovnaní aktuálneho znaku so znakom vzoru zadaným v tabuľke alebo prejde na znak nasledujúci. Algoritmus porovnáva vzor a reťazec pokiaľ počet zostávajúcich znakov v reťazci je väčší alebo rovný ako potrebný počet úspešných porovnaní pre nájdenie zhody so vzorom.

Príklad tabuľky pre slovo abracadabra
 a  b  r  a  c  a  d  a  b  r  a
 0  1  1  0  2  0  2  0  1  1  0  5

0 – značí, že sa pri nezhode na tejto pozícii môžeme presunúť
na nasledujúci znak reťazca a porovnávať vzor od začiatku
1,2 – značí, že aktuálny znak reťazca, ktorý sa nezhodoval so znakom
vo vzore porovnáme opäť s 1. alebo 2. znakom vo vzore (pri indexovaní od 0 s 0. a 1. znakom)
5 – ak by sme pri nájdení zhody chceli pokračovať ďalej vo vyhľadávaní,
porovnáme aktuálny znak v reťazci s 5. znakom vo vzore (pri indexovaní od 0 so 4. znakom)

Výstupy algoritmu
Výstupom je opäť pozícia začiatku zhodnej sekvencie v reťazci so vzorom. Táto je vypočítaná ako akt_poz – pocet_prvkov_vzoru + 1. Ak už algoritmus vie určiť, že sa daný vzor v reťazci nenachádza, výstupom je index, ktorý nemôže patriť do vstupného reťazca, teda napr. –1.

Vývojový diagram

Implementácia

 
//Knuth-Morris-Prattov algoritmus vyhladavania zadaneho vzoru "vzor" s poctom znakov "dlzka_v"
//v retazci "retazec" s poctom znakov "dlzka_r"
//funkcia vracia index prveho znaku najdeneho vzoru v retazci 
//(v pripade neuspechu vyhladavania vracia -1)
int najdi_KMP(char* vzor, int dlzka_v, char* retazec, int dlzka_r){
	if (dlzka_v > MAX_DLZKA_VZORU) return -2;
	int postupnost[MAX_DLZKA_VZORU+1];
	pre(vzor, dlzka_v, &postupnost[0]);

	int i=0;
	int j=0;
	while (j < dlzka_r) {
		if (vzor[i] == retazec[j]) {
			if (i == dlzka_v-1) {
				return (j-dlzka_v+1);
				//i=postupnost[i];
			}
			else {i++; j++;}
		}
		else if (postupnost[i] == -1) {i=0; j++;}
		else i=postupnost[i];
	}
	return -1;
}

Vizualizácie

Časová zložitosť
Časová zložitosť algoritmu sa skladá z dvoch časových zložitostí. Je to čas potrebný na vytvorenie tabuľky a samotný čas prehľadávania reťazca. Podľa [8] je čas potrebný na vytvorenie tabuľky rádovo m a čas potrebný na samotné vyhľadávania je rádovo n. Celková časová zložitosť môže byť pre vyhľadávania, kde je reťazec podstatne väčší ako vzor zjednodušená na rádovo n.

Porovnanie s predchádzajúcimi algoritmami
V sekvenčnom algoritme bola časová zložitosť závislá od súčinu dĺžky vzoru a reťazca. Pre tento algoritmus vidíme, že časová zložitosť závisí už iba od ich súčtu. Tento algoritmus teda pre veľké reťazce a vzory prináša vysokú časovú úsporu. Daňou za to je vytvorenie tabuľky, ktorá obsahuje m+1 prvkov.