Rozdział 6: Ciągi znaków w algorytmach

Ciągi znaków są podstawowym typem danych w informatyce, reprezentującym sekwencje znaków. Badanie algorytmów i struktur danych do przetwarzania ciągów znaków jest kluczową częścią każdego programu studiów informatycznych. W tym rozdziale zbadamy kilka ważnych algorytmów przetwarzania ciągów znaków, w tym sortowanie ciągów znaków, drzewa tries, wyszukiwanie podciągów, wyrażenia regularne i kompresję danych. Te algorytmy mają liczne praktyczne zastosowania, od edycji tekstu i wyszukiwania dokumentów po bioinformatykę i przetwarzanie języka naturalnego.

Sortowanie ciągów znaków

Sortowanie jest podstawową operacją w informatyce, a sortowanie ciągów znaków jest powszechnym zadaniem w wielu zastosowaniach. Chociaż ogólne algorytmy sortowania, takie jak szybkie sortowanie i scalanie, mogą być używane do sortowania ciągów znaków, istnieją bardziej wydajne algorytmy, które wykorzystują specjalne właściwości ciągów znaków.

Zliczanie indeksowane kluczem

Zliczanie indeksowane kluczem to prosty i wydajny algorytm do sortowania ciągów znaków, które składają się z małego zbioru różnych znaków. Podstawowa idea polega na zliczeniu liczby wystąpień każdego znaku, a następnie użyciu tych zliczań do określenia pozycji każdego ciągu znaków w posortowanej kolejności.

Oto przykład zliczania indeksowanego kluczem w działaniu:

Wejście:  ["dab", "cab", "fad", "bad", "dad", "ebb", "ace"]
Wyjście: ["ace", "bad", "cab", "dab", "dad", "ebb", "fad"]

Algorytm działa w następujący sposób:

Zlicz częstotliwość występowania każdego znaku w ciągach znaków.
Oblicz indeks początkowy dla każdego znaku w posortowanej tablicy.
Skopiuj ciągi znaków do posortowanej tablicy, używając zliczań do określenia pozycji.

Zliczanie indeksowane kluczem działa w czasie O(n + R), gdzie n to całkowita liczba znaków w ciągach, a R to rozmiar alfabetu (liczba różnych znaków). Czyni to bardzo wydajnym algorytmem do sortowania ciągów znaków z małym rozmiarem alfabetu.

Sortowanie LSD radix

Sortowanie radix od najmniej znaczącego cyfry (LSD) to rozszerzenieOto tłumaczenie na język polski:

Liczenie, które może sortować ciągi znaków o równej długości nad dużym alfabetem. Podstawowa idea polega na sortowaniu ciągów znaków znak po znaku, począwszy od ostatniego znaku i przesuwając się w kierunku pierwszego.

Oto przykład sortowania LSD radix:

Wejście:  ["4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845", "4JZY524", "1ICK750", "3CIO720", "1OHV845", "1OHV845", "2RLA629", "2RLA629", "3ATW723"]
Wyjście: ["1ICK750", "1ICK750", "1OHV845", "1OHV845", "1OHV845", "2IYE230", "2RLA629", "2RLA629", "3ATW723", "3CIO720", "3CIO720", "4JZY524", "4PGC938"]

Algorytm działa w następujący sposób:

Sortuj ciągi znaków według ostatniego znaku, używając sortowania indeksowanego kluczem.
Powtórz krok 1 dla każdego znaku, przesuwając się w kierunku pierwszego.

Sortowanie LSD radix działa w czasie O(w * n), gdzie w to długość ciągów znaków, a n to liczba ciągów. Czyni to wydajnym wyborem do sortowania ciągów stałej długości.

Sortowanie MSD Radix

Sortowanie MSD radix (ang. Most-significant-digit-first) to rekurencyjny wariant sortowania radix, który może obsługiwać ciągi znaków o różnej długości. Podobnie jak quicksort, sortowanie MSD radix dzieli tablicę na podzastawy, które mogą być sortowane niezależnie.

Oto przykład sortowania MSD radix:

Wejście:  ["she", "sells", "seashells", "by", "the", "sea", "shore", "the", "shells", "she", "sells", "are", "surely", "seashells"]
Wyjście: ["are", "by", "sea", "seashells", "seashells", "sells", "sells", "she", "she", "shells", "shore", "surely", "the", "the"]

Algorytm działa w następujący sposób:

Podziel tablicę na podzastawy na podstawie pierwszego znaku każdego ciągu.
Rekurencyjnie sortuj każdą podzastawa.

Sortowanie MSD radix ma najgorszy przypadek czasu działania O(n * w), ale w praktyce często jest szybsze niż sortowanie LSD radix dla ciągów o różnej długości.

Drzewa trie

Drzewo trie (wymawiane "try") to struktury danych drzewopodobne do przechowywania ciągów znaków, które umożliwiają wydajne dopasowywanie prefiksów i wyszukiwanie ciągów znaków. Każdy węzeł w drzewie trie reprezentuje znak, a ścieżka od korzenia do węzła reprezentuje prefiks ciągu znaków.Oto tłumaczenie pliku Markdown na język polski. Dla kodu, nie tłumacz kodu, tylko komentarze.

Oto przykład trie przechowującego ciągi znaków "sea", "sells", "she", "shells" i "shore":

     (root)
    /  |  \
   s   h   o
  / \     / \
 e   h   r   t
 |   |   |   |
 a   e   e   h
     |       |
     l       e
     |       |
     l       r
     |
     s

Trie obsługuje następujące operacje:

Wstawianie ciągu znaków do trie.
Wyszukiwanie ciągu znaków w trie.
Usuwanie ciągu znaków z trie.
Znajdowanie wszystkich ciągów znaków z danym prefiksem.

Złożoność czasowa tych operacji wynosi O(w), gdzie w jest długością ciągu znaków, który jest wstawiany, wyszukiwany lub usuwany. Czyni to trie bardzo wydajną strukturą danych do zadań związanych z ciągami znaków.

Wyszukiwanie podciągów

Wyszukiwanie podciągów to problem polegający na znalezieniu wszystkich wystąpień wzorca ciągu znaków w większym ciągu tekstowym. Jest to podstawowy problem w przetwarzaniu ciągów znaków, z zastosowaniami w edycji tekstu, bioinformatyce i wielu innych dziedzinach.

Wyszukiwanie metodą siłową

Najprostsze podejście do wyszukiwania podciągów to algorytm siłowy, który sprawdza każdą możliwą pozycję w tekście pod kątem dopasowania do wzorca.

Oto przykład wyszukiwania metodą siłową:

Tekst:    "abacadabrabracabracadabrabrabracad"
Wzorzec: "abracadabra"
Wynik:   [13]

Algorytm siłowy ma najgorszy przypadek złożoności czasowej O(n * m), gdzie n to długość tekstu, a m to długość wzorca. Chociaż jest prosty w implementacji, może być nieefektywny dla dużych tekstów i wzorców.

Algorytm Knuth-Morris-Pratta

Algorytm Knuth-Morris-Pratta (KMP) to wydajny algorytm wyszukiwania podciągów, który używa wstępnie obliczonej "funkcji niepowodzenia", aby uniknąć niepotrzebnych porównań.

Funkcja niepowodzenia mówi nam długość najdłuższego właściwego prefiksu wzorca, który jest również sufiksem podciągu wzorca, który już dopasowaliśmy. Pozwala to nam "przeskakiwać" w tekście, gdy znajdziemy niezgodność, zamiast cofać się.

Oto przykład algorytmu KMP:

Tekst:    "abacadabrabrProszę o tłumaczenie tego pliku Markdown na język polski. Dla kodu, nie tłumacz kodu, tylko tłumacz komentarze.

Oto plik:

acabracadabrabracad"
Wzorzec: "abracadabra"
Wynik: [13]

Algorytm KMP ma czas działania O(n + m), co czyni go znacznie bardziej wydajnym niż podejście siłowe dla dużych tekstów i wzorców.

Algorytm Boyera-Moore'a

Algorytm Boyera-Moore'a to kolejny wydajny algorytm wyszukiwania podciągów, który działa poprzez przetwarzanie wstępne ciągu wzorca. W przeciwieństwie do KMP, który rozpoczyna porównania od początku wzorca, Boyera-Moore zaczyna od końca i pracuje wstecz.

Kluczową ideą za Boyerem-Moore'em jest wykorzystanie dwóch wstępnie obliczonych funkcji: funkcji "dobrego sufiksu" i funkcji "złego znaku". Te funkcje pozwalają nam przeskakiwać do przodu w tekście, gdy znajdziemy niezgodność, podobnie jak w KMP.

Oto przykład algorytmu Boyera-Moore'a:

Tekst:   "abacadabrabracabracadabrabrabracad"
Wzorzec: "abracadabra"
Wynik:   [13]

Boyera-Moore ma najlepszy czas działania O(n/m) i najgorszy czas działania O(n * m), ale w praktyce często jest to najszybszy algorytm wyszukiwania podciągów dla dużych alfabetów.

Wyrażenia regularne

Wyrażenia regularne to potężne narzędzie do opisywania wzorców w ciągach znaków. Zapewniają one zwięzłą i elastyczną notację do dopasowywania, wyszukiwania i manipulowania tekstem.

Wyrażenie regularne to ciąg znaków, który definiuje wzorzec wyszukiwania. Najprostszą formą wyrażenia regularnego jest dosłowny ciąg znaków, taki jak "hello", który dokładnie pasuje do ciągu "hello". Jednak wyrażenia regularne zawierają również specjalne znaki i konstrukcje, które umożliwiają bardziej złożone wzorce:

. (kropka) pasuje do dowolnego pojedynczego znaku.
* (gwiazdka) pasuje do zera lub więcej wystąpień poprzedzającego znaku lub grupy.
+ (plus) pasuje do jednego lub więcej wystąpień poprzedzającego znaku lub grupy.
? (znak zapytania) pasuje do zera lub jednego wystąpienia poprzedzającego znaku lub grupy.
^ (daszek) pasuje do początku linii.
$ (dolar) pasuje do końca linii.
[] (nawiasy kwadratowe) definiują klasę znaków, pasującą do dowolnego pojedynczego znaku.Oto polski przekład pliku Markdown:

Oto przykłady wyrażeń regularnych i wzorców, które one dopasowują:

a.b dopasowuje dowolny ciąg trzech znaków, który zaczyna się od "a" i kończy na "b", taki jak "acb", "a5b" lub "a b".
a*b dopasowuje dowolny ciąg, który składa się z zera lub więcej znaków "a" następowanych przez pojedynczy znak "b", taki jak "b", "ab", "aab" lub "aaab".
a+b dopasowuje dowolny ciąg, który składa się z jednego lub więcej znaków "a" następowanych przez pojedynczy znak "b", taki jak "ab", "aab" lub "aaab", ale nie "b".
a?b dopasowuje albo "ab", albo "b".
^a dopasowuje dowolny ciąg, który zaczyna się od "a".
a$ dopasowuje dowolny ciąg, który kończy się na "a".
[aeiou] dopasowuje dowolny pojedynczy znak samogłoski.

Wyrażenia regularne są obsługiwane przez wiele języków programowania i narzędzi, w tym Java, Python oraz narzędzia Uniksowe, takie jak grep i sed. Są one szeroko stosowane w zadaniach, takich jak walidacja danych, przetwarzanie tekstu i analiza logów.

Kompresja danych

Kompresja danych to proces kodowania informacji przy użyciu mniejszej liczby bitów niż oryginalna reprezentacja. Jest to przydatne do zmniejszenia wymagań dotyczących miejsca do przechowywania i czasu transmisji. Istnieją dwa główne rodzaje kompresji: bezstratna i stratna. Kompresja bezstratna pozwala na idealne odtworzenie oryginalnych danych z danych skompresowanych, podczas gdy kompresja stratna pozwala na pewną utratę informacji w zamian za większe współczynniki kompresji.

Kodowanie długości serii

Kodowanie długości serii (RLE) to prosta technika kompresji bezstratnej, która zastępuje powtarzające się sekwencje identycznych symboli (serie) pojedynczym wystąpieniem symbolu i licznikiem określającym liczbę powtórzeń.

Oto przykład RLE:

Wejście:  "AAAABBBCCCDDDEEE"
Wyjście: "4A3B3C3D3E"

RLE jest skuteczne dla danych z wieloma długimi seriami, takimi jak proste obrazy graficzne. Jednak może faktycznie zwiększyć rozmiar danych, jeśli występuje mało lub brak serii.

Kodowanie Huffmana

Kodowanie Huffmana to algorytm kompresji bezstratnej, który przypisuje zmiennej długości kody do symboli na podstawie ich częstotliwości występowania.Oto tłumaczenie na język polski:

Kodowanie Huffmana

Kodowanie Huffmana to algorytm kompresji bezstratnej, który wykorzystuje częstotliwość występowania symboli w danych wejściowych. Częstsze symbole są przypisywane krótszym kodom, a rzadsze symbole - dłuższym kodom.

Algorytm działa poprzez budowanie drzewa binarnego, zwanego drzewem Huffmana, od dołu do góry. Każdy liść reprezentuje symbol i jego częstotliwość, a każdy węzeł wewnętrzny reprezentuje sumę częstotliwości jego dzieci. Drzewo jest konstruowane przez wielokrotne łączenie dwóch węzłów o najniższych częstotliwościach, aż pozostanie tylko jeden węzeł.

Po zbudowaniu drzewa, kod dla każdego symbolu jest określany przez ścieżkę od korzenia do odpowiedniego liścia, gdzie lewa gałąź reprezentuje "0", a prawa gałąź reprezentuje "1".

Oto przykład kodowania Huffmana:

Wejście:  "AAAABBBCCCDDDEEE"
Wyjście: "000010011001011100101"

Drzewo Huffmana:
      (15)
     /    \
   (7)    (8)
   / \    / \
 (4) (3) (3) (5)
 /\  /\  /\  /\
A B  C D E

W tym przykładzie, "A" ma kod "00", "B" ma kod "01", "C" ma kod "10", "D" ma kod "110", a "E" ma kod "111". Skompresowane wyjście uzyskuje się przez zastąpienie każdego symbolu w wejściu jego odpowiednim kodem.

Kodowanie Huffmana jest optymalnym kodem prefiksowym, co oznacza, że żaden kod nie jest prefiksem innego kodu. Umożliwia to jednoznaczne dekodowanie skompresowanych danych. Kodowanie Huffmana jest szeroko stosowane w różnych formatach plików i narzędziach kompresji, takich jak JPEG, MP3 i ZIP.

Kompresja LZW

Kompresja Lempel-Ziv-Welch (LZW) to algorytm kompresji oparty na słowniku, który buduje słownik (lub książkę kodową) ciągów znaków podczas kompresji danych wejściowych. LZW jest szeroko stosowany w narzędziach kompresji plików i był używany w formacie obrazów GIF.

Kluczową ideą LZW jest zastępowanie ciągów znaków pojedynczymi kodami. Czyta on ciąg wejściowy znak po znaku i koduje go w zwartą reprezentację, zastępując każdy stałodługościowy kod zmienno długościowym kodem. Im dłuższy ciąg, tym więcej miejsca oszczędza się, kodując go jako pojedynczą liczbę.

Oto przykładOto tłumaczenie na język polski:

Krok po kroku opis działania kompresji LZW:

Zainicjuj słownik, aby zawierał wszystkie pojedyncze znaki.
Znajdź najdłuższy ciąg W w słowniku, który pasuje do bieżącego wejścia.
Wyślij indeks słownika dla W do wyjścia i usuń W z wejścia.
Dodaj W wraz z następnym symbolem na wejściu do słownika.
Przejdź do kroku 2.

Rozważmy przykład. Załóżmy, że chcemy skompresować ciąg "ABABABABA" przy użyciu LZW.

Zainicjuj słownik, aby zawierał "A" i "B".
Najdłuższy pasujący ciąg to "A". Wyślij jego indeks (0) i usuń go z wejścia. Słownik teraz zawiera "A", "B" i "AB".
Najdłuższy pasujący ciąg to "B". Wyślij jego indeks (1) i usuń go z wejścia. Słownik teraz zawiera "A", "B", "AB" i "BA".
Najdłuższy pasujący ciąg to "AB". Wyślij jego indeks (2) i usuń go z wejścia. Słownik teraz zawiera "A", "B", "AB", "BA" i "ABA".
Najdłuższy pasujący ciąg to "ABA". Wyślij jego indeks (4) i usuń go z wejścia. Słownik teraz zawiera "A", "B", "AB", "BA", "ABA" i "ABAB".
Najdłuższy pasujący ciąg to "BA". Wyślij jego indeks (3). Wejście jest teraz puste.

Skompresowana reprezentacja "ABABABABA" to zatem sekwencja indeksów [1], która wymaga mniej bitów do reprezentacji niż oryginalna reprezentacja ASCII.

Dekompresja działa podobnie, ale w odwrotnej kolejności:

Zainicjuj słownik, aby zawierał wszystkie pojedyncze znaki.
Odczytaj kod X z wejścia.
Wyślij ciąg dla X ze słownika.
Jeśli poprzedni kod istnieje, dodaj poprzedni ciąg połączony z pierwszym znakiem ciągu dla X do słownika.
Przejdź do kroku 2.

Kompresja LZW jest prosta i szybka, co czyni ją dobrym wyborem dla wielu zastosowań. Jednak ma ona również pewne ograniczenia. Rozmiar słownika może znacznie wzrosnąć, co powoduje duże zużycie pamięci. Ponadto słownik jest resetowany po każdym bloku wejścia, co może zmniejszyć współczynnik kompresji dla małych plików.

Pomimo tych ograniczeń...Poniżej znajduje się tłumaczenie pliku Markdown na język polski. Komentarze w kodzie zostały przetłumaczone, ale sam kod pozostał niezmieniony.

Podsumowanie

W tym rozdziale zbadaliśmy kilka ważnych algorytmów przetwarzania ciągów znaków, w tym sortowanie ciągów znaków, drzewa tries, wyszukiwanie podciągów, wyrażenia regularne i kompresję danych. Te algorytmy stanowią podstawę wielu rzeczywistych aplikacji i są niezbędnymi narzędziami dla każdego programisty pracującego z danymi tekstowymi.

Rozpoczęliśmy od omówienia sortowania ciągów znaków, które są zoptymalizowanymi algorytmami sortowania wykorzystującymi specjalne właściwości ciągów znaków. Liczenie kluczy, sortowanie LSD radix i sortowanie MSD radix zapewniają wydajne metody sortowania ciągów znaków na podstawie ich poszczególnych znaków.

Następnie zbadaliśmy drzewa tries, strukturę danych drzewopodobną do przechowywania i pobierania ciągów znaków. Drzewa tries umożliwiają szybkie dopasowywanie prefiksów i są powszechnie używane w aplikacjach, takich jak autouzupełnianie i tablice routingu IP.

Algorytmy wyszukiwania podciągów, takie jak algorytmy Knutha-Morrisa-Pratta i Boyera-Moore'a, pozwalają nam wydajnie wyszukiwać wzorce w większych ciągach znaków. Te algorytmy mają liczne zastosowania w edycji tekstu, biologii obliczeniowej i wyszukiwaniu informacji.

Wyrażenia regularne zapewniają potężny i elastyczny sposób opisywania wzorców ciągów znaków. Omówiliśmy podstawową składnię wyrażeń regularnych i sposób, w jaki mogą być one używane do dopasowywania wzorców i manipulowania ciągami znaków w różnych językach programowania i narzędziach.

Wreszcie, zbadaliśmy algorytmy kompresji danych, które zmniejszają rozmiar danych poprzez wykorzystywanie redundancji i wzorców w danych wejściowych. Omówiliśmy kodowanie długości serii, kodowanie Huffmana i kompresję Lempel-Ziv-Welch, z których każdy ma swoje własne mocne strony i zastosowania.

Zrozumienie tych algorytmów przetwarzania ciągów znaków i struktur danych jest kluczowe dla każdego, kto pracuje z danymi tekstowymi. Ponieważ ilość niezorganizowanych danych stale rośnie, umiejętność wydajnego manipulowania, wyszukiwania i kompresowania danych tekstowych staje się coraz ważniejsza.Here is the Polish translation of the provided text, with the code comments translated:

Ciśnienie na łańcuchy tekstowe będzie tylko rosło. Opanowując techniki omówione w tym rozdziale, będziesz dobrze przygotowany do radzenia sobie z szerokim zakresem wyzwań związanych z przetwarzaniem łańcuchów tekstowych w swoich własnych projektach i aplikacjach.

# Funkcja do odwracania łańcucha tekstowego
def reverse_string(s):
    return s[::-1]
 
# Funkcja do sprawdzania, czy łańcuch jest palindromem
def is_palindrome(s):
    return s == reverse_string(s)
 
# Przykład użycia funkcji
original_string = "racecar"
print(reverse_string(original_string))  # Wynik: "racecar"
print(is_palindrome(original_string))  # Wynik: True

Chapter 5 Graphs Chapter 7 Context