Podstawy przetwarzania tekstów
1. Wprowadzenie do przetwarzania tekstów
Przetwarzanie tekstów (string processing) to fundamentalny obszar programowania, który obejmuje manipulację, analizę i wyszukiwanie wzorców w tekście.
Zastosowania praktyczne:
- Wyszukiwarki – Google, Bing (indeksowanie i wyszukiwanie)
- Edytory tekstu – Find & Replace, sprawdzanie pisowni
- Bioinformatyka – analiza sekwencji DNA
- Kompresja danych – ZIP, GZIP
- Bezpieczeństwo – wykrywanie wirusów, filtrowanie spamu
- Natural Language Processing – chatboty, tłumaczenia
2. Podstawowe operacje na stringach w Pythonie
2.1. Tworzenie i konkatenacja:
2.2. Indeksowanie i slicing:
2.3. Długość i sprawdzanie zawartości:
3. Metody stringów
3.1. Zmiana wielkości liter:
3.2. Usuwanie białych znaków:
3.3. Wyszukiwanie i zastępowanie:
3.4. Podział i łączenie:
4. Sprawdzanie typu zawartości
5. Formatowanie stringów
5.1. format() metoda:
5.2. f-stringi (Python 3.6+):
6. Złożoność operacji na stringach
6.1. Podstawowe operacje:
| Operacja | Złożoność | Uwagi |
|---|---|---|
| len(s) | O(1) | Długość przechowywana |
| s[i] | O(1) | Dostęp po indeksie |
| s in t | O(n*m) | Wyszukiwanie podstringa |
| s + t | O(n+m) | Konkatenacja |
| s * k | O(k*n) | Powtarzanie |
| s.find(t) | O(n*m) | Najgorszy przypadek |
| s.replace(old, new) | O(n*m) | Zależy od liczby wystąpień |
Uwaga: Stringi w Pythonie są niemutowalne (immutable)!
6.2. Konkatenacja w pętli:
7. Kodowanie znaków
7.1. ASCII i Unicode:
7.2. Kodowanie UTF-8:
8. Porównywanie stringów
8.1. Porównanie leksykograficzne:
8.2. Porównanie znaku po znaku:
9. Wyrażenia regularne (wprowadzenie)
10. Iterowanie po stringach
10.1. Proste iterowanie:
10.2. Iterowanie wstecz:
11. Stringi jako listy znaków
12. Praktyczne przykłady
12.1. Zliczanie znaków:
12.2. Usuwanie duplikatów (zachowując kolejność):
12.3. Sprawdzanie, czy string jest unikalny:
12.4. Odwracanie słów w zdaniu:
12.5. Kompresja stringów:
13. StringBuilder pattern (dla wydajności)
14. Podsumowanie
Podstawy przetwarzania tekstów:
- Stringi w Pythonie są niemutowalne (immutable)
- Indeksowanie: s[i], slicing: s[start:stop:step]
- Konkatenacja: +, *, join()
- Metody: upper(), lower(), strip(), split(), replace()
Złożoność:
| Operacja | Złożoność | Uwagi |
|---|---|---|
| Dostęp s[i] | O(1) | Szybki dostęp |
| Konkatenacja s+t | O(n+m) | Tworzy nowy string |
| s in t | O(n*m) | Wyszukiwanie podstringa |
| s.split() | O(n) | Podział na słowa |
| "".join(list) | O(n) | Efektywne łączenie ✅ |
Kluczowe operacje:
Dobre praktyki:
✅ Używaj "".join(list) zamiast + w pętli
✅ Używaj f-stringów dla formatowania
✅ Pamiętaj, że stringi są niemutowalne
✅ Dla dużych operacji tekstowych rozważ io.StringIO
Częste błędy:
❌ Konkatenacja w pętli s += char → O(n²)
❌ Zapominanie o immutability stringów
❌ Nie uwzględnianie case-sensitivity
Zastosowania:
- Parsowanie i walidacja danych
- Formatowanie outputu
- Wyszukiwanie wzorców (regex)
- Analiza tekstu (NLP)
- Kompresja i kodowanie
Co dalej warto poznać:
- Palindromy – wykrywanie i optymalizacje
- Anagramy – wykrywanie i grupowanie
- Wyszukiwanie wzorców – algorytmy KMP, Rabin-Karp, Boyer-Moore
- Wyrażenia regularne – zaawansowane wzorce
- Kompresja – algorytmy Huffman, LZ77
- Natural Language Processing – tokenizacja, stemming