Algorytmy na tekstach – Python

Błędy językowe, literówki i inne pomyłki w tekście zwykle biorą się z niewiedzy lub nieuwagi piszącego, ale czasem mogą mieć poważne konsekwencje – dlatego programy komputerowe oferują narzędzia do automatycznego przetwarzania tekstu: wyszukiwanie, podkreślanie powtórzeń, zamianę fraz. W tym materiale nauczysz się, jak komputer zapisuje tekst oraz jak napisać własne algorytmy porównywania i wyszukiwania tekstu w Pythonie.

Materiał na 3 godziny lekcyjne (klasa 3 LO):

Cele lekcji – po zrealizowaniu materiału uczeń:

Godzina 1. Jak komputer zapisuje tekst

1.1. Znaki jako liczby

Komputer nie „widzi” liter ani emoji – wszystko, co wyświetla się na ekranie, jest w pamięci zapisane jako liczby. Każdy znak (litera, cyfra, znak interpunkcyjny, symbol, emoji) ma przypisany swój kod liczbowy, czyli pozycję w ogromnej, uporządkowanej tablicy zwanej tablicą Unicode. W 2020 roku liczba zakodowanych w niej znaków przekraczała 280 000 – są tam litery wszystkich alfabetów świata, symbole matematyczne i muzyczne, a także setki emoji.

Podstawowe znaki, które można wprowadzić bezpośrednio z klawiatury (litery alfabetu łacińskiego, cyfry, znaki interpunkcyjne i symbole typu @, ^), znajdują się w początkowej części tablicy Unicode, na pozycjach od 0 do 127. Ten fragment nazywa się tablicą ASCII (ang. American Standard Code for Information Interchange) i pochodzi jeszcze z lat 60. XX wieku, gdy opracowywano go na potrzeby telekomunikacji.

0123456789
3_spacja!"#$%&'()
4_*+,-./0123
6_@ABCDEFGHI
9_`abcdefghi

Fragment tablicy ASCII. Numer znaku odczytujemy jak liczbę w systemie szesnastkowym: wiersz to cyfra dziesiątek, kolumna to cyfra jedności. Np. znak @ ma kod 64 (w tabeli: wiersz „6_”, kolumna 4), a spacja ma kod 32.

Ciekawostka: pary wielkich i małych liter („A” i „a” itd.) znajdują się w tych samych kolumnach tablicy i są oddalone o dokładnie 32 – dzięki temu łatwo przejść z kodu małej litery do kodu wielkiej litery (i odwrotnie), po prostu dodając lub odejmując 32.

1.2. Typ danych str w Pythonie

W Pythonie teksty przetwarza się za pomocą typu danych str (od ang. string). Napis przechowywany jest jako ciąg znaków, do których mamy dostęp poprzez indeksy – liczone od 0. Pierwszy znak napisu tekst to tekst[0], a ostatni – tekst[-1] (indeksy ujemne liczone są od końca).

Do konwersji między znakiem a jego kodem liczbowym służą dwie funkcje wbudowane:

Przydatna jest też funkcja len(napis), która zwraca liczbę znaków napisu.

Przykład: program „Znaki” – wypisywanie fragmentu tablicy ASCII

for i in range(32, 127):
    znak = chr(i)
    print(znak, end=" ")
    if i % 16 == 15:
        print()  # nowa linia co 16 znaków

Wyjaśnienie: pętla for przechodzi po kolejnych kodach od 32 do 126. Funkcja chr(i) zamienia kod na znak, który wypisujemy z odstępem (end=" "). Warunek i % 16 == 15 co 16 znaków przechodzi do nowej linii, żeby wynik był czytelny.

Przykład: program „Znaki2” – od znaku do znaku (funkcja ord)

znak = " "
kod = ord(znak)
kod2 = ord("~")

while kod <= kod2:
    print(znak, end=" ")
    if kod % 16 == 15:
        print()
    kod = kod + 1
    znak = chr(kod)

Wyjaśnienie: zamiast z góry znać zakres liczbowy (32–126), tym razem podajemy zakres jako pierwszy i ostatni znak (spacja i ~) i obliczamy ich kody funkcją ord. Pętla while działa dopóki nie dojdziemy do drugiego znaku.

Ćwiczenie 1.1

Ćwiczenie 1.2

Godzina 2. Algorytmy porównywania tekstów

2.1. Dostęp do znaków i metody klasy str

Klasa str udostępnia gotowe metody ułatwiające pracę z tekstem, np.:

2.2. Poprawność adresu e‑mail

Dla uproszczenia przyjmujemy, że poprawny adres e‑mail to napis, w którym:

  1. występuje dokładnie jeden znak @, który jest co najmniej trzecim znakiem napisu,
  2. po znaku @ występuje kropka ., będąca trzecim lub czwartym znakiem od końca napisu i nie występująca bezpośrednio po @.

Przykłady poprawnych adresów: [email protected], [email protected]. Niepoprawne: [email protected] (za krótka nazwa użytkownika), nk@[email protected] (dwa znaki @), n.@pl (brak @), [email protected] (kropka zaraz po @).

Przykład: funkcja CzyPoprawnyAdres (metody find i rfind)

def CzyPoprawnyAdres(adres):
    dl = len(adres)

    i = adres.find("@")           # etap 1: pierwsze wystąpienie @
    if i < 2 or i == -1:
        return False

    j = adres.rfind("@")          # etap 2: ostatnie wystąpienie @
    if i != j:                    # jeśli i != j, są co najmniej dwa @
        return False

    k = adres.rfind(".")          # etap 3: ostatnia kropka
    if k == -1:
        return False
    if not (k == dl - 3 or k == dl - 4):
        return False

    if k - i <= 1:                # etap 4: kropka tuż po @?
        return False

    return True

if __name__ == "__main__":
    adres_1 = input("Podaj adres e-mail: ")
    print("Poprawny" if CzyPoprawnyAdres(adres_1) else "Niepoprawny")

Wyjaśnienie kolejnych etapów:

2.3. Porównanie dwóch adresów (symulacja rejestracji)

Wiele serwisów internetowych przy zakładaniu konta prosi o dwukrotne podanie adresu e‑mail, żeby wykryć literówkę.

def CzyPoprawnyAdres(adres):
    dl = len(adres)
    i = adres.find("@")
    if i < 2 or i == -1:
        return False
    j = adres.rfind("@")
    if i != j:
        return False
    k = adres.rfind(".")
    if k == -1 or not (k == dl - 3 or k == dl - 4):
        return False
    if k - i <= 1:
        return False
    return True

adres_1 = input("Podaj adres e-mail: ")
adres_2 = input("Powtórz adres e-mail: ")

if adres_1 == adres_2:
    print("Hasło do serwisu wysłaliśmy na adres " + adres_1 if CzyPoprawnyAdres(adres_1) else "Adres ma niepoprawną strukturę.")
else:
    print("Podane adresy e-mail są różne!")

2.4. Usuwanie powtórzeń z listy zakupów

Kolejne zadanie: mamy listę słów wpisywanych alfabetycznie, jedno pod drugim, zakończoną trzema gwiazdkami (***). Chcemy usunąć zbędne, sąsiadujące powtórzenia (skoro lista jest posortowana, powtórzenia tego samego produktu zawsze sąsiadują ze sobą).

Sposób rozwiązania: dopóki na wejściu pojawiają się nowe wyrazy, porównujemy ostatnio wczytany wyraz z poprzednim i w razie potrzeby pomijamy powtórzenie, a nieusunięte wyrazy dołączamy do listy wynikowej.

N = 20
wynik = []

i = 1
nowy = input()
wynik.append(nowy)

stary = nowy
nowy = input()

while nowy != "***" and i < N:
    if nowy != stary:
        i = i + 1
        wynik.append(nowy)
    stary = nowy
    nowy = input()

for j in wynik:
    print(j)

Wyjaśnienie: zmienna wynik to pusta lista, do której metodą append dopisujemy kolejne, nowe słowa. Zmienna i liczy elementy na liście (zabezpieczenie przed przekroczeniem N). W pętli while sprawdzamy, czy ostatnio wczytany napis różni się od poprzedniego – jeśli tak, dopisujemy go do wynik.

Ćwiczenie 2.1

Ćwiczenie 2.2

Godzina 3. Wyszukiwanie wzorca w tekście

3.1. Na czym polega wyszukiwanie wzorca

Wyszukiwanie wzorca w tekście (ang. pattern matching) polega na znalezieniu miejsca, w którym w danym tekście występuje wskazany łańcuch znaków (wzorzec) – o ile w ogóle występuje. To dokładnie to, co robimy „na oko”, szukając ukrytych wyrazów w wykreślance, albo to, co w tle robi wyszukiwarka w edytorze tekstu czy w przeglądarce (Ctrl+F).

3.2. Algorytm naiwny

Najprostszy (tzw. naiwny) algorytm wyszukiwania wzorca przesuwa wzorzec wzdłuż tekstu o jeden znak i za każdym razem porównuje go znak po znaku z odpowiednim fragmentem tekstu.

Oznaczmy długość tekstu literą n, a długość wzorca literą m. Lista kroków algorytmu:

  1. Wczytaj tekst i wzorzec.
  2. Dla każdej liczby poz z zakresu od 0 do n − m wykonuj kroki 3–4.
  3. Wybierz fragment tekstu długości m, zaczynający się na pozycji poz, i porównaj go ze wzorcem znak po znaku.
  4. Jeśli fragment i wzorzec są identyczne, zwróć poz jako odpowiedź i zakończ algorytm.
  5. Jeśli żadne dopasowanie nie zostało znalezione, zwróć wartość -1.
Sprawdzamy pozycje tylko do n − m, ponieważ dalej nie zmieściłby się już cały wzorzec – to ostatnie miejsce, w którym w ogóle może wystąpić dopasowanie.

Przykład: program „Szukaj wzorca”

TEKST = "ALA ALBO ADA"

def Porownaj(wzorzec):
    n = len(TEKST)
    m = len(wzorzec)
    for poz in range(0, n - m + 1):
        j = 0
        while j < m and TEKST[poz + j] == wzorzec[j]:
            j = j + 1
        if j == m:
            return poz
    return -1

print("Tekst:", TEKST)
print("Podaj wzorzec:", end=" ")
wzorzec = input()

print("Pozycja:", Porownaj(wzorzec))

Wyjaśnienie: zewnętrzna pętla for (linie z poz) przesuwa punkt startu porównania po kolejnych znakach tekstu. Wewnętrzna pętla while porównuje kolejne znaki wzorca z fragmentem tekstu – działa dopóki znaki się zgadzają (TEKST[poz+j] == wzorzec[j]) i nie doszliśmy do końca wzorca. Jeśli licznik j osiągnął długość wzorca m, oznacza to pełne dopasowanie – zwracamy poz, czyli liczbę znaków tekstu poprzedzających wzorzec.

Przykładowo, dla tekstu ALA ALBO ADA i wzorca ALBO, algorytm zwróci wartość 4 (bo cztery znaki: A, L, A, spacja, poprzedzają dopasowanie).

Uwaga: naiwny algorytm sprawdza po kolei wszystkie możliwe pozycje – to tzw. metoda siłowa (ang. brute-force). Dla krótkich tekstów działa bardzo dobrze, ale dla bardzo długich tekstów (np. całej książki) bywa powolny. Dlatego w praktyce Python udostępnia gotową, dużo szybszą metodę napis.find(wzorzec), która realizuje to samo zadanie – w kolejnych latach nauki poznasz bardziej zaawansowane algorytmy dopasowywania wzorca.

Ćwiczenie 3.1

Ćwiczenie 3.2

Podsumowanie