Przeczytaj

Algorytm KMP – implementacja w języku Python

Przykład 1

W materiale omawiającym algorytm Knutha‑Morrisa‑PrattaPAWg1Xbykmateriale omawiającym algorytm Knutha‑Morrisa‑Pratta możemy znaleźć zapisany za pomocą pseudokodu algorytm oraz dokładną analizę jego działania. W tym e‑materiale stworzymy implementację tego algorytmu. Najpierw napiszemy funkcję, której zadaniem będzie zbudowanie tablicy częściowych dopasowań. Tablicy tej potrzebujemy, aby efektywnie przeprowadzać próby dopasowań wzorca w tekście:

def budowa_tablicy_KMP(wzorzec):
	rozmiar_tablicy = len(wzorzec) + 1
	tablica = [0] * rozmiar_tablicy							# deklarujemy tablicę o 1 większą od wzorca, wypełnioną 0
	poz = tablica[0] = -1									# na pierwszej pozycji ustawiamy wartownika

	for i in range(1, rozmiar_tablicy):						# iterujemy po wszystkich prefiksach wzorca,
		
		while poz > -1 and wzorzec[poz] != wzorzec[i - 1]:	# dopóki możemy znaleźć dłuższy prefikso-sufiks
			poz = tablica[poz]
		poz += 1

		if i == rozmiar_tablicy - 1 or wzorzec[i] != wzorzec[poz]:
			tablica[i] = poz								# zapisujemy szerokość znalezionego prefikso-sufiksu, jeżeli element, 
															# który występuje po znalezionym prefikso-sufiksie jest taki sam,
															# jak po obecnym prefiksie
		else:
			tablica[i] = tablica[poz]						# zapisujemy w tablicy tę samą wartość, która jest zapisana przy elemencie
															# na pozycji równej szerokości prefikso-sufiksu
	return tablica

Następnie zdefiniujmy funkcję, która, używając tablicy, będzie realizowała wyszukiwanie wzorca w tekście. Korzysta ona z wyżej zdefiniowanej funkcji do budowania tablicy częściowych dopasowań. W kodzie użyjemy funkcji enumerateenumerate()enumerate w celu iterowania po znakach w tekście:

def szukaj_algorytmem_KMP(tekst, wzorzec):
	
	tablica_T = budowa_tablicy_KMP(wzorzec)						# budujemy tablicę częściowych dopasowań
	dop = 0														# indeks końca obecnie dopasowanej części wzorca
	wynikowy_indeks = -1
	for indeks, znak_S in enumerate(tekst):			
		while dop > -1 and wzorzec[dop] != znak_S:				# jeżeli znaleźliśmy niedopasowanie, to cofamy się po indeksach
			dop = tablica_T[dop]								# w tablica_T aż do napotkania wartownika (-1)
		dop += 1												# lub znalezienia znaku odpowiadającego znak_S
		
		if dop == len(wzorzec):									# jeżeli indeks dopasowania wzorca == długość wzorca,
			wynikowy_indeks = indeks - len(wzorzec) + 1			# to znaleźliśmy dopasowanie
			break
	return wynikowy_indeks

Pełna wersja programu wraz z kilkoma przykładami wykonań funkcji:

Linia 1. def budowa podkreślnik tablicy podkreślnik KMP otwórz nawias okrągły wzorzec zamknij nawias okrągły dwukropek. Linia 2. rozmiar podkreślnik tablicy znak równości len otwórz nawias okrągły wzorzec zamknij nawias okrągły plus 1. Linia 3. tablica znak równości otwórz nawias kwadratowy 0 zamknij nawias kwadratowy asterysk rozmiar podkreślnik tablicy. Linia 4. poz znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości minus 1. Linia 6. for i in range otwórz nawias okrągły 1 przecinek rozmiar podkreślnik tablicy zamknij nawias okrągły dwukropek. Linia 7. while poz zamknij nawias ostrokątny minus 1 and wzorzec otwórz nawias kwadratowy poz zamknij nawias kwadratowy wykrzyknik znak równości wzorzec otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy dwukropek. Linia 8. poz znak równości tablica otwórz nawias kwadratowy poz zamknij nawias kwadratowy. Linia 9. poz plus znak równości 1. Linia 11. if i znak równości znak równości rozmiar podkreślnik tablicy minus 1 or wzorzec otwórz nawias kwadratowy i zamknij nawias kwadratowy wykrzyknik znak równości wzorzec otwórz nawias kwadratowy poz zamknij nawias kwadratowy dwukropek. Linia 12. tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości poz. Linia 13. else dwukropek. Linia 14. tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości tablica otwórz nawias kwadratowy poz zamknij nawias kwadratowy. Linia 16. return tablica. Linia 19. def szukaj podkreślnik algorytmem podkreślnik KMP otwórz nawias okrągły tekst przecinek wzorzec zamknij nawias okrągły dwukropek. Linia 21. tablica podkreślnik T znak równości budowa podkreślnik tablicy podkreślnik KMP otwórz nawias okrągły wzorzec zamknij nawias okrągły. Linia 22. dop znak równości 0. Linia 23. wynikowy podkreślnik indeks znak równości minus 1. Linia 24. for indeks przecinek znak podkreślnik S in enumerate otwórz nawias okrągły tekst zamknij nawias okrągły dwukropek. Linia 25. while dop zamknij nawias ostrokątny minus 1 and wzorzec otwórz nawias kwadratowy dop zamknij nawias kwadratowy wykrzyknik znak równości znak podkreślnik S dwukropek. Linia 26. dop znak równości tablica podkreślnik T otwórz nawias kwadratowy dop zamknij nawias kwadratowy. Linia 27. dop plus znak równości 1. Linia 28. if dop znak równości znak równości len otwórz nawias okrągły wzorzec zamknij nawias okrągły dwukropek. Linia 29. wynikowy podkreślnik indeks znak równości indeks minus len otwórz nawias okrągły wzorzec zamknij nawias okrągły plus 1. Linia 30. break. Linia 31. return wynikowy podkreślnik indeks. Linia 34. kratka Działanie funkcji budującej tablicę dla przykładowych wzorców. Linia 35. print otwórz nawias okrągły budowa podkreślnik tablicy podkreślnik KMP otwórz nawias okrągły cudzysłów ADCDADC cudzysłów zamknij nawias okrągły zamknij nawias okrągły. Linia 36. kratka otwórz nawias kwadratowy minus 1 przecinek 0 przecinek 0 przecinek 0 przecinek minus 1 przecinek 0 przecinek 0 przecinek 3 zamknij nawias kwadratowy. Linia 38. print otwórz nawias okrągły budowa podkreślnik tablicy podkreślnik KMP otwórz nawias okrągły cudzysłów AAAAAAAAA cudzysłów zamknij nawias okrągły zamknij nawias okrągły. Linia 39. kratka otwórz nawias kwadratowy minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek minus 1 przecinek 8 zamknij nawias kwadratowy. Linia 41. print otwórz nawias okrągły budowa podkreślnik tablicy podkreślnik KMP otwórz nawias okrągły cudzysłów ASDGORKASDF cudzysłów zamknij nawias okrągły zamknij nawias okrągły. Linia 42. kratka otwórz nawias kwadratowy minus 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek minus 1 przecinek 0 przecinek 0 przecinek 3 przecinek 0 zamknij nawias kwadratowy. Linia 44. print otwórz nawias okrągły budowa podkreślnik tablicy podkreślnik KMP otwórz nawias okrągły cudzysłów ASDFORKASDFO cudzysłów zamknij nawias okrągły zamknij nawias okrągły. Linia 45. kratka otwórz nawias kwadratowy minus 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek minus 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 5 zamknij nawias kwadratowy. Linia 47. kratka Szukanie dopasowań wzorca w tekście. Linia 48. szukany podkreślnik W znak równości cudzysłów ADCDADC cudzysłów. Linia 49. lancuch podkreślnik S znak równości cudzysłów ADC ADCDAD ADCDADCDADCE cudzysłów. Linia 50. print otwórz nawias okrągły szukaj podkreślnik algorytmem podkreślnik KMP otwórz nawias okrągły lancuch podkreślnik S przecinek szukany podkreślnik W zamknij nawias okrągły zamknij nawias okrągły. Linia 51. kratka 11. Linia 53. kratka przykład sprawdzenia za pomocą wbudowanej metody find. Linia 54. print otwórz nawias okrągły lancuch podkreślnik S kropka find otwórz nawias okrągły szukany podkreślnik W zamknij nawias okrągły zamknij nawias okrągły. Linia 55. kratka 11.

def budowa_tablicy_KMP(wzorzec):
	rozmiar_tablicy = len(wzorzec) + 1
	tablica = [0] * rozmiar_tablicy
	poz = tablica[0] = -1

	for i in range(1, rozmiar_tablicy):
		while poz > -1 and wzorzec[poz] != wzorzec[i - 1]:
			poz = tablica[poz]
		poz += 1

		if i == rozmiar_tablicy - 1 or wzorzec[i] != wzorzec[poz]:
			tablica[i] = poz
		else:
			tablica[i] = tablica[poz]

	return tablica


def szukaj_algorytmem_KMP(tekst, wzorzec):
	
	tablica_T = budowa_tablicy_KMP(wzorzec)
	dop = 0
	wynikowy_indeks = -1
	for indeks, znak_S in enumerate(tekst):			
		while dop > -1 and wzorzec[dop] != znak_S:
			dop = tablica_T[dop]
		dop += 1
		if dop == len(wzorzec):
			wynikowy_indeks = indeks - len(wzorzec) + 1
			break
	return wynikowy_indeks


# Działanie funkcji budującej tablicę dla przykładowych wzorców
print(budowa_tablicy_KMP("ADCDADC"))
# [-1, 0, 0, 0, -1, 0, 0, 3]

print(budowa_tablicy_KMP("AAAAAAAAA"))
# [-1, -1, -1, -1, -1, -1, -1, -1, -1, 8]

print(budowa_tablicy_KMP("ASDGORKASDF"))
# [-1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 3, 0]

print(budowa_tablicy_KMP("ASDFORKASDFO"))
# [-1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 5]

# Szukanie dopasowań wzorca w tekście
szukany_W = "ADCDADC"
lancuch_S = "ADC ADCDAD ADCDADCDADCE"
print(szukaj_algorytmem_KMP(lancuch_S, szukany_W))
# 11

# przykład sprawdzenia za pomocą wbudowanej metody find
print(lancuch_S.find(szukany_W))
# 11

Dla zainteresowanych

Metoda find() w języku Python realizuje wyszukiwanie tekstu za pomocą zmodyfikowanego algorytmu Boyer‑Moor‑Horspoolalgorytm Boyer‑Moore‑HorsepoolBoyer‑Moor‑Horspool – więcej informacji na ten temat można znaleźć w kodzie źródłowym CPython.

Słownik

enumerate()

funkcja w języku Python służąca do generowania indeksu i wartości odpowiadającej temu indeksowi w liście

metoda naiwna

określana również jako brute force; sprawdza wszystkie możliwe dopasowania wzorca w tekście

algorytm Boyer‑Moore‑Horsepool

jest to ulepszenie algorytmu Boyera‑Moore'a; podobnie jak algorytm KMP analizuje wzorzec w celu znalezienia maksymalnego skoku w analizie tekstu po nieudanym dopasowaniu; porównanie wzorca z fragmentem tekstu odbywa się od końca wzorca; średnia złożoność czasowa tego algorytmu to $O = (\frac{d ł u g o ś ć w z o r c a}{a l f a b e t})$ i w praktyce jest on znacznie szybszy od rozwiązania naiwnego

Wprowadzenie

Symulacja interaktywna

Algorytm KMP – implementacja w języku Python

Słownik