Technikum Klasa I 45 minut PP: I.2b | s. 342

Lekcja 7: Algorytmy na tekstach - porownywanie tekstow

Reprezentacja tekstow, kody ASCII, porownywanie leksykograficzne

📋 Podstawa programowa: I.2b
algorytmyporownanieporownywanie tekstowprezentacjestringznaki
00:00
Wprowadzenie
5 min
00:05
Teoria
18 min
00:23
Cwiczenia
17 min
00:40
Podsumowanie
5 min
📚

Teoria

▼

Jak komputer przechowuje tekst?

Komputer nie rozumie liter - przechowuje je jako liczby. Kazdy znak (litera, cyfra, symbol) ma przypisany numer w tablicy kodow, np. ASCII (American Standard Code for Information Interchange).

Tablica ASCII - najwazniejsze zakresy

Znak     | Kod ASCII | Uwagi
---------|-----------|------------------
'0'-'9'  | 48-57     | cyfry
'A'-'Z'  | 65-90     | duze litery
'a'-'z'  | 97-122    | male litery
' '      | 32        | spacja
'!'      | 33        | wykrzyknik

Przyklady:
'A' = 65    'a' = 97    (roznica: 32)
'B' = 66    'b' = 98
'Z' = 90    'z' = 122
'0' = 48    '9' = 57
Wazne: Duze litery maja MNIEJSZE kody niz male litery! Dlatego w porzadku ASCII: 'A' < 'Z' < 'a' < 'z'. Rowniez: cyfry < duze litery < male litery.

Tekst jako tablica znakow

Tekst (lancuch znakow, ang. string) to ciag znakow ponumerowanych od pozycji 0 (lub 1, zalezenie od konwencji).

Tekst: "INFORMATYKA"
Indeks: 0  1  2  3  4  5  6  7  8  9  10
Znak:   I  N  F  O  R  M  A  T  Y  K  A
Dlugosc: 11 znakow

Porownywanie tekstow - porzadek leksykograficzny

Porzadek leksykograficzny to porzadek slownikowy - porownujemy teksty znak po znaku od lewej strony:

ALGORYTM Porownaj(tekst1, tekst2):
  1. i = 0
  2. DOPOKI i < dlugosc(tekst1) ORAZ i < dlugosc(tekst2):
     a. JESLI tekst1[i] < tekst2[i]: ZWROC "tekst1 < tekst2"
     b. JESLI tekst1[i] > tekst2[i]: ZWROC "tekst1 > tekst2"
     c. i = i + 1
  3. JESLI dlugosc(tekst1) < dlugosc(tekst2): ZWROC "tekst1 < tekst2"
  4. JESLI dlugosc(tekst1) > dlugosc(tekst2): ZWROC "tekst1 > tekst2"
  5. ZWROC "tekst1 = tekst2"

Przyklady porownywania

Przyklad 1: "ALA" vs "ALE"
  Pozycja 0: 'A'(65) = 'A'(65) -> rowne, dalej
  Pozycja 1: 'L'(76) = 'L'(76) -> rowne, dalej
  Pozycja 2: 'A'(65) < 'E'(69) -> "ALA" < "ALE"

Przyklad 2: "DOM" vs "DOMEK"
  Pozycja 0: 'D' = 'D' -> dalej
  Pozycja 1: 'O' = 'O' -> dalej
  Pozycja 2: 'M' = 'M' -> dalej
  "DOM" sie skonczyl, a "DOMEK" jest dluzszy
  -> "DOM" < "DOMEK"

Przyklad 3: "abc" vs "ABC"
  Pozycja 0: 'a'(97) > 'A'(65) -> "abc" > "ABC"
  (Male litery maja wieksze kody ASCII!)

Zastosowania porownywania tekstow

  • Sortowanie listy nazwisk - ukladanie w porzadku alfabetycznym
  • Wyszukiwarki - porownywanie zapytan z indeksem
  • Bazy danych - sortowanie i filtrowanie rekordow tekstowych
  • Slowniki i encyklopedie - porzadek hasel
✏️

Zadania

▼
Latwe

Zadanie 1: Kody ASCII

Korzystajac z tablicy ASCII, zapisz kody nastepujacych znakow:

a) 'H', 'e', 'l', 'l', 'o'
b) Jaki tekst koduja liczby: 80, 121, 116, 104, 111, 110?
c) Jaka jest roznica miedzy kodem 'a' a 'A'? Jak zamienic mala litere na duza?

Pokaz rozwiazanie 
a) 'H'=72, 'e'=101, 'l'=108, 'l'=108, 'o'=111

b) 80='P', 121='y', 116='t', 104='h', 111='o', 110='n'
   Tekst: "Python"

c) 'a'=97, 'A'=65 -> roznica = 32
   Aby zamienic mala litere na duza:
   kod_duzej = kod_malej - 32
   Np. 'c'(99) - 32 = 67 = 'C'
Latwe

Zadanie 2: Porownaj leksykograficznie

Okresl, ktory tekst jest "mniejszy" (wczesniejszy w porzadku slownikowym). Uzasadnij:

a) "KOWALSKI" vs "KOWALSKA"
b) "JAN" vs "JANUSZ"
c) "programowanie" vs "program"
d) "Ala" vs "ala"

Pokaz rozwiazanie 
a) "KOWALSKI" vs "KOWALSKA"
   Pozycje 0-6: K,O,W,A,L,S,K - identyczne
   Pozycja 7: 'I'(73) vs 'A'(65) -> 'A' < 'I'
   "KOWALSKA" < "KOWALSKI"

b) "JAN" vs "JANUSZ"
   Pozycje 0-2: J,A,N - identyczne
   "JAN" krotszy -> "JAN" < "JANUSZ"

c) "programowanie" vs "program"
   Pozycje 0-6: p,r,o,g,r,a,m - identyczne
   "program" krotszy -> "program" < "programowanie"

d) "Ala" vs "ala"
   Pozycja 0: 'A'(65) vs 'a'(97) -> 'A' < 'a'
   "Ala" < "ala"
   (Duze litery sa "mniejsze" w ASCII!)
Srednie

Zadanie 3: Sortowanie tekstow

Uporzadkuj nastepujace listy w porzadku leksykograficznym (ASCII):

a) "Python", "Java", "C++", "JavaScript", "HTML"
b) "Nowak", "Kowalski", "Nowacki", "Kowal", "Nowakowski"

Pokaz rozwiazanie 
a) Porzadek ASCII (duze litery):
   "C++" < "HTML" < "Java" < "JavaScript" < "Python"
   ('+' ma kod 43, wiec C++ jest pierwsze;
    H(72) < J(74) < P(80))

b) Porzadek ASCII:
   "Kowal" < "Kowalski" < "Nowacki" < "Nowak" < "Nowakowski"
   (K(75) < N(78), wiec Kowal* przed Nowak*
    "Kowal" < "Kowalski" (krotszy prefiks)
    "Nowacki": pozycja 4 = 'c'(99)
    "Nowak": pozycja 4 = 'k'(107)
    'c' < 'k', wiec "Nowacki" < "Nowak"
    "Nowak" < "Nowakowski" (krotszy prefiks))
Trudne

Zadanie 4: Pseudokod - porownanie bez rozrozniania wielkosci liter

Napisz pseudokod algorytmu, ktory porownuje dwa teksty leksykograficznie, ale NIE rozroznia duzych i malych liter (np. "Ala" = "ala" = "ALA"). Wskazowka: zamien wszystkie litery na male przed porownaniem.

Pokaz rozwiazanie 
FUNKCJA NaMale(znak):
  JESLI kod(znak) >= 65 ORAZ kod(znak) <= 90:
    ZWROC char(kod(znak) + 32)
  ZWROC znak

ALGORYTM PorownajBezWielkosci(t1, t2):
  1. i = 0
  2. DOPOKI i < dlugosc(t1) ORAZ i < dlugosc(t2):
     a. z1 = NaMale(t1[i])
     b. z2 = NaMale(t2[i])
     c. JESLI z1 < z2: ZWROC "t1 < t2"
     d. JESLI z1 > z2: ZWROC "t1 > t2"
     e. i = i + 1
  3. JESLI dlugosc(t1) < dlugosc(t2): ZWROC "t1 < t2"
  4. JESLI dlugosc(t1) > dlugosc(t2): ZWROC "t1 > t2"
  5. ZWROC "t1 = t2"

Test: PorownajBezWielkosci("Ala", "ALA")
  i=0: NaMale('A')='a', NaMale('A')='a' -> rowne
  i=1: NaMale('l')='l', NaMale('L')='l' -> rowne
  i=2: NaMale('a')='a', NaMale('A')='a' -> rowne
  Dlugosci rowne -> "t1 = t2" (poprawnie!)
🎥

Materialy wideo

▼
Algorithms on texts - text comparison
Dziwne... u mnie działa - (ScratchSPWZ)
Algorithms on texts - searching for a pattern in text
Dziwne... u mnie działa - (ScratchSPWZ)
🎧

Podcasty

▼
✔️

Quiz - sprawdz sie!

▼
📜

Podstawa programowa

▼
← Lekcja 6: NWD - algorytm Euklidesa Lekcja 8: Wyszukiwanie wzorca w tekscie →