Wyszukiwanie wzorca w tekście
Materiały tej lekcji są na razie tylko do czytania na stronie. Kod przepisz albo skopiuj do swojego edytora.
Czego się nauczysz
Napisy to w Pythonie ciągi znaków, po których można chodzić pętlą jak po liczbach. Na tej lekcji policzysz litery w kodzie DNA i napiszesz algorytm, który znajduje wszystkie miejsca, gdzie w tekście występuje szukany wzorzec.
Po tej lekcji:
- użyjesz
len, indeksów,ini pętli po znakach napisu, - policzysz wystąpienia liter pętlą z licznikami i metodą
count, - napiszesz algorytm naiwny zwracający listę pozycji wzorca.
Napis to ciąg znaków
len(s)– długość napisu,s[0]– pierwszy znak (numeracja od 0),s[-1]– ostatni,in– czy fragment występuje w napisie,for znak in s:– pętla po kolejnych znakach.
s = "CAATAAAAA"
print(len(s), s[0], s[-1]) # 9 C A
print("TAA" in s) # True
print("GG" in s) # False
Kod DNA zapisuje się literami A, C, G, T. Biolodzy szukają w nim wzorców – to dokładnie problem wyszukiwania w tekście.
Zliczanie liter – dwa sposoby
Sposób 1: pętla i liczniki – przeglądasz napis znak po znaku i zwiększasz licznik odpowiedniej litery.
def ile_liter(s):
ile_a = ile_c = ile_g = ile_t = 0
for znak in s:
if znak == "A":
ile_a = ile_a + 1
elif znak == "C":
ile_c = ile_c + 1
elif znak == "G":
ile_g = ile_g + 1
else:
ile_t = ile_t + 1
return [ile_a, ile_c, ile_g, ile_t]
Sposób 2: metoda count – s.count("A") zwraca liczbę wystąpień. Wynik ten sam, kod krótszy. Dla "TCTAAAGATATCGGG" oba sposoby dają [5, 2, 4, 4].
Algorytm naiwny
Przesuwasz wzorzec po tekście: dla każdej pozycji i porównujesz fragment tekstu o długości wzorca z wzorcem. Gdy są równe – zapisujesz pozycję. Wycinek s[i:i+m] zwraca m znaków od pozycji i.
def wystapienia(tekst, wzorzec):
pozycje = []
m = len(wzorzec)
for i in range(len(tekst) - m + 1):
if tekst[i:i + m] == wzorzec:
pozycje.append(i)
return pozycje
wystapienia("ABRAKADABRA", "ABRA") # [0, 7]
Ostatnia sensowna pozycja to len(tekst) - len(wzorzec).
Nakładające się wystąpienia
wystapienia("AAAA", "AA") zwraca [0, 1, 2] – trzy wystąpienia, które na siebie zachodzą. Metoda "AAAA".count("AA") zwraca 2, bo liczy tylko rozłączne wystąpienia.
Metoda find: "ABRAKADABRA".find("KAD") zwraca 4 – pozycję pierwszego wystąpienia; gdy wzorca brak, zwraca −1.
Indeksy zaczynają się od 0, a wielkość liter ma znaczenie: „a” to nie „A”.range(len(tekst) - m + 1)– bez+ 1pominiesz wzorzec na samym końcu tekstu.
Spróbuj sam
Uruchom kod z lekcji na stronie. Zmień tekst i wzorzec w wywołaniu wystapienia, np. poszukaj „TA” w napisie z DNA. Sprawdź, co zwróci funkcja, gdy wzorca w tekście nie ma.
Na karcie pracy do tej lekcji: zadania sprawdzające 1–3 razem na lekcji i zadania domowe 1–5 samodzielnie.
Sprawdź się
- Użyję
len, indeksów,ini pętli po znakach napisu. - Policzę wystąpienia liter pętlą z licznikami i metodą
count. - Napiszę algorytm naiwny zwracający listę pozycji wzorca.
Na następnej lekcji: przetwarzanie napisów – wycinki, palindromy, szyfr przestawieniowy.
Notatki
Prezentacja
Kod
Otwórz kod, zmieniaj go i uruchamiaj na stronie – np. usuń # z linii oznaczonej jako błąd i zobacz, co się stanie. „Przywróć” wraca do wersji z lekcji.