Algorytm naiwny, przesuwane okno, zlozonosc obliczeniowa, implementacja w Pythonie
ð Podstawa programowa: I.2bWyszukiwanie wzorca (pattern matching) to jeden z najwazniejszych problemow algorytmicznych w informatyce. Polega na znalezieniu wystapien pewnego krotszego tekstu (wzorca) wewnatrz dluzszego tekstu. Stosowany jest w edytorach tekstu (Ctrl+F), wyszukiwarkach, analizie DNA, filtrach antyspamowych i wielu innych dziedzinach.
Dane wejsciowe:
Wynik: pozycje (indeksy) w tekscie T, na ktorych zaczyna sie wzorzec W.
Algorytm naiwny jest najprostszym podejsciem do wyszukiwania wzorca. Polega on na "przesuwaniu" wzorca po tekscie o jedna pozycje i za kazdym razem sprawdzaniu, czy wzorzec pasuje do biezacego fragmentu tekstu.
Przklad: szukamy wzorca "AB" w tekscie "AABABAB"
Tekst: A A B A B A B
Wzorzec: A B pozycja 0: A=A ok, A!=B - NIE
A B pozycja 1: A=A ok, B=B ok - TAK! (znaleziono na pozycji 1)
A B pozycja 2: B!=A - NIE
A B pozycja 3: A=A ok, B=B ok - TAK! (znaleziono na pozycji 3)
A B pozycja 4: B!=A - NIE
A B pozycja 5: A=A ok, B=B ok - TAK! (znaleziono na pozycji 5)def szukaj_naiwnie(tekst, wzorzec):
"""Wyszukiwanie wzorca metoda naiwna.
Zwraca liste pozycji, na ktorych zaczyna sie wzorzec."""
n = len(tekst)
m = len(wzorzec)
pozycje = []
for i in range(n - m + 1):
# Sprawdzamy, czy wzorzec pasuje na pozycji i
pasuje = True
for j in range(m):
if tekst[i + j] != wzorzec[j]:
pasuje = False
break
if pasuje:
pozycje.append(i)
return pozycje
# Test
tekst = "AABABAB"
wzorzec = "AB"
wynik = szukaj_naiwnie(tekst, wzorzec)
print(f"Wzorzec '{wzorzec}' znaleziony na pozycjach: {wynik}")
# Wzorzec 'AB' znaleziony na pozycjach: [1, 3, 5]Algorytm naiwny ma zlozonosc:
Dla wiekszosci praktycznych zastosowan algorytm naiwny jest wystarczajaco szybki. Istnieja jednak szybsze algorytmy (KMP, Boyer-Moore, Rabin-Karp), ktore poznasz w przyszlosci.
Prześledz recznie dzialanie algorytmu naiwnego dla tekstu "ABCABCABC" i wzorca "CAB". Zapisz kazdy krok porownania i wskazz pozycje, na ktorych znaleziono wzorzec.
Tekst: A B C A B C A B C
Wzorzec: C A B poz 0: A!=C - NIE
C A B poz 1: B!=C - NIE
C A B poz 2: C=C, A=A, B=B - TAK! (pozycja 2)
C A B poz 3: A!=C - NIE
C A B poz 4: B!=C - NIE
C A B poz 5: C=C, A=A, B=B - TAK! (pozycja 5)
C A B poz 6: A!=C - NIE
Wzorzec "CAB" znaleziony na pozycjach: [2, 5]Zmodyfikuj algorytm naiwny tak, aby zliczal laczna liczbe porownan znakow. Przetestuj dla tekstu "AAAAAAAAAB" i wzorca "AAAB". Ile porownan wykonano?
def szukaj_z_licznikiem(tekst, wzorzec):
n = len(tekst)
m = len(wzorzec)
pozycje = []
porownania = 0
for i in range(n - m + 1):
pasuje = True
for j in range(m):
porownania += 1
if tekst[i + j] != wzorzec[j]:
pasuje = False
break
if pasuje:
pozycje.append(i)
return pozycje, porownania
tekst = "AAAAAAAAAB"
wzorzec = "AAAB"
poz, por = szukaj_z_licznikiem(tekst, wzorzec)
print(f"Pozycje: {poz}")
print(f"Liczba porownan: {por}")
# Pozycje: [6]
# Liczba porownan: 28Zmodyfikuj algorytm naiwny tak, aby ignorewal roznice miedzy wielkimi i malymi literami. Przetestuj dla tekstu "Ala ma kota a Kot ma Ale" i wzorca "ala".
def szukaj_bez_wielkosci(tekst, wzorzec):
tekst_lower = tekst.lower()
wzorzec_lower = wzorzec.lower()
n = len(tekst_lower)
m = len(wzorzec_lower)
pozycje = []
for i in range(n - m + 1):
if tekst_lower[i:i+m] == wzorzec_lower:
pozycje.append(i)
return pozycje
tekst = "Ala ma kota a Kot ma Ale"
wzorzec = "ala"
wynik = szukaj_bez_wielkosci(tekst, wzorzec)
print(f"Znaleziono na pozycjach: {wynik}")
# Znaleziono na pozycjach: [0]
# (Uwaga: "Ale" to nie "ala" - inny koncowy znak)Napisz funkcje zamien_wzorzec(tekst, stary, nowy), ktora znajduje wszystkie wystapienia tekstu "stary" i zastepuje je tekstem "nowy" (bez uzycia wbudowanej metody replace).
def zamien_wzorzec(tekst, stary, nowy):
wynik = ""
n = len(tekst)
m = len(stary)
i = 0
while i < n:
# Sprawdzamy czy na pozycji i zaczyna sie stary wzorzec
if i <= n - m and tekst[i:i+m] == stary:
wynik += nowy
i += m # przeskakujemy caly stary wzorzec
else:
wynik += tekst[i]
i += 1
return wynik
# Test
tekst = "Ala ma kota i kota ma Ala"
print(zamien_wzorzec(tekst, "kota", "psa"))
# Ala ma psa i psa ma Ala