Rozdział 8: Techniki analizy algorytmów

W poprzednich rozdziałach zbadaliśmy szeroką gamę podstawowych algorytmów i struktur danych, obejmujących takie tematy, jak sortowanie, wyszukiwanie, grafy, ciągi znaków i różne zastosowania. Chociaż wdrażanie i rozumienie tych algorytmów jest kluczowe, równie ważne jest analizowanie ich charakterystyki wydajnościowej, aby podejmować świadome decyzje przy wyborze algorytmów do konkretnych problemów. W tym rozdziale zagłębiamy się w techniki używane do analizowania i oceny algorytmów, koncentrując się na modelach matematycznych, badaniach empirycznych i wizualizacji algorytmów.

Modele matematyczne i analiza

Analiza matematyczna jest potężnym narzędziem do zrozumienia zachowania i wydajności algorytmów. Poprzez opracowywanie modeli matematycznych, które uchwytują istotne cechy algorytmu, możemy rozumować na temat jego efektywności i skalowalności. Te modele pozwalają nam przewidywać czas działania algorytmu, zużycie pamięci i inne metryki wydajności, umożliwiając porównywanie różnych algorytmów i wybór najbardziej odpowiedniego do danego zadania.

Notacja dużego O

Jedną z najczęściej używanych notacji do opisywania wydajności algorytmu jest notacja dużego O. Notacja dużego O dostarcza górnej granicy szybkości wzrostu funkcji, pozwalając nam scharakteryzować scenariusz najgorszego przypadku czasu działania algorytmu lub złożoności pamięci.

W notacji dużego O wyrażamy wydajność algorytmu jako funkcję rozmiaru wejścia, zazwyczaj oznaczaną jako n. Na przykład, rozważmy następującą prostą funkcję, która oblicza sumę pierwszych n dodatnich liczb całkowitych:

public static int sum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

Czas działania tej funkcji rośnie liniowo wraz z rozmiarem wejścia n. Możemy to wyrazić za pomocą notacji dużego O jako O(n), wskazując, że czas działania jest proporcjonalny do rozmiaru wejścia. Oznacza to, że wraz ze wzrostem rozmiaru wejścia, czas działania algorytmu będzie rósł liniowo.Poniżej znajduje się tłumaczenie pliku Markdown na język polski. Komentarze w kodzie zostały przetłumaczone, ale sam kod pozostał niezmieniony.

Wraz ze wzrostem rozmiaru danych wejściowych, czas działania algorytmu rośnie co najwyżej liniowo.

Notacja dużego O pozwala nam pominąć stałe współczynniki i niższego rzędu człony, skupiając się na dominującym członie, który określa szybkość wzrostu funkcji. Na przykład, rozważmy następującą funkcję:

public static int sumOfSquares(int n) {
    // Zainicjuj sumę do 0
    int sum = 0;
    // Iteruj od 1 do n
    for (int i = 1; i <= n; i++) {
        // Iteruj od 1 do i
        for (int j = 1; j <= i; j++) {
            // Dodaj j do sumy
            sum += j;
        }
    }
    // Zwróć sumę
    return sum;
}

Czas działania tej funkcji jest proporcjonalny do kwadratu N. Dokładniej, liczba wykonań instrukcji sum += j to 1 + 2 + ... + N ~ N^2/2.

Ogólnie, możemy wyrazić czas działania programu w zależności od rozmiaru danych wejściowych, używając notacji dużego O. Pozwala to nam pominąć współczynniki wiodące i niższego rzędu człony, skupiając się na ważnej części: rzędzie wzrostu czasu działania.

Algorytm Knuth-Morris-Pratt

Algorytm Knuth-Morris-Pratt (KMP) jest wydajnym algorytmem wyszukiwania podciągu, który wykorzystuje wstępnie obliczoną "funkcję niepowodzenia", aby uniknąć niepotrzebnych porównań.

Funkcja niepowodzenia informuje nas o długości 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 "przeskoczyć" w tekście, gdy znajdziemy niezgodność, zamiast cofać się.

Oto przykład algorytmu KMP:

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

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

Algorytm Boyer-Moore'a

Algorytm Boyer-Moore'a jest innym wydajnym algorytmem wyszukiwania podciągu, który działa poprzez wstępne przetwarzanie ciągu wzorca. W przeciwieństwie do KMP, który rozpoczyna porównania od początku wzorca, Boyer-Moore zaczyna od końca i pracuje wstecz.

Kluczową ideą za algorytmem Boyer-Moore'a jest użycie dwóch wstępnie obliczonych funkcji: "dobrego sufiksu"Oto tłumaczenie pliku Markdown na język polski, z zachowaniem oryginalnego kodu:

Funkcja "dobrego znaku" i funkcja "złego znaku". Te funkcje pozwalają nam przeskakiwać do przodu w tekście, gdy znajdziemy niezgodność, podobnie jak w algorytmie KMP.

Oto przykład algorytmu Boyera-Moore'a:

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

Boyer-Moore ma najlepszy przypadek działania w czasie O(n/m) i najgorszy przypadek działania w czasie O(n * m), ale w praktyce często jest to najszybszy algorytm wyszukiwania podciągu 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 w nawiasach.

Oto kilka przykładów wyrażeń regularnych i wzorców, które one pasują:

a.b pasuje do dowolnego ciągu trzech znaków, który zaczyna się od "a" i kończy na "b", takich jak "acb", "a5b" lub "a b".
a*b pasuje do dowolnego ciągu, który składa się z zera lub więcej znaków "a" następowanych przez pojedynczy znak "b", takich jak "b", "ab", "aab" lub "aaab".
a+b pasuje do dowolnego ciągu, który składa się z jednego lub więcej znaków "a" następowanych przez pojedynczy znak "b", takich jak "ab", "aab" lub "aaab", ale nie "b".
a?b pasuje albo do "ab", albo do "b".
^a pasuje do dowolnego ciągu, który zaczyna się od "a".Oto tłumaczenie pliku na język polski. Dla kodu, nie tłumacz kodu, tylko tłumacz komentarze.

ts z "a".

a$ pasuje do każdego ciągu, który kończy się na "a".
[aeiou] pasuje do każdego pojedynczego znaku 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 na dysku i czasu transmisji. Istnieją dwa główne rodzaje kompresji: bezstratna i stratna. Kompresja bezstratna pozwala na dokładne 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 kody o zmiennej długości do symboli na podstawie ich częstotliwości w danych wejściowych. Częstsze symbole otrzymują krótsze kody, a mniej częste symbole otrzymują dłuższe kody.

Algorytm działa poprzez budowanie drzewa binarnego, zwanego drzewem Huffmana, od dołu do góry. Każdy węzeł liściowy 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 doOto polski przekład pliku Markdown:

Odpowiadający węzeł liściowy, z lewą gałęzią reprezentującą "0" i prawą gałęzią reprezentującą "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" jest przypisane do kodu "00", "B" do "01", "C" do "10", "D" do "110", a "E" do "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 Lempel-Ziv-Welch (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 kod o stałej długości kodem o zmiennej długości. Im dłuższy ciąg, tym więcej miejsca oszczędza się, kodując go jako pojedynczą liczbę.

Oto krok po kroku, jak działa kompresja LZW:

Zainicjuj słownik, zawierający wszystkie pojedyncze znaki.
Znajdź najdłuższy ciąg W w słowniku, który pasuje do bieżącego wejścia.
Wyemituj indeks słownika dla W do wyjścia i usuń W z wejścia.
Dodaj W wraz z następnym symbolem wejścia 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, zawierający "A" i "B".
Najdłuższy pasujący ciąg to "A". Wyemituj jego indeks...Oto polski przekład pliku w formacie Markdown. Dla kodu, nie tłumacz kodu, tylko tłumacz komentarze.
Najdłuższe dopasowanie to "A". Wyemituj jego indeks (0) i usuń go z danych wejściowych. Słownik teraz zawiera "A", "B" i "AB".
Najdłuższe dopasowanie to "B". Wyemituj jego indeks (1) i usuń go z danych wejściowych. Słownik teraz zawiera "A", "B", "AB" i "BA".
Najdłuższe dopasowanie to "AB". Wyemituj jego indeks (2) i usuń go z danych wejściowych. Słownik teraz zawiera "A", "B", "AB", "BA" i "ABA".
Najdłuższe dopasowanie to "ABA". Wyemituj jego indeks (4) i usuń go z danych wejściowych. Słownik teraz zawiera "A", "B", "AB", "BA", "ABA" i "ABAB".
Najdłuższe dopasowanie to "BA". Wyemituj jego indeks (3). Dane wejściowe są 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 odwrotnym kierunku:

Zainicjuj słownik, aby zawierał wszystkie ciągi znaków jednoelementowe.
Odczytaj kod X z danych wejściowych.
Wyświetl ciąg znaków dla X ze słownika.
Jeśli istnieje poprzedni kod, dodaj poprzedni ciąg znaków połączony z pierwszym znakiem ciągu znaków 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 znaczne zużycie pamięci. Ponadto słownik jest resetowany po każdym bloku danych wejściowych, co może zmniejszyć współczynnik kompresji dla małych plików.

Pomimo tych ograniczeń, LZW pozostaje popularnym i skutecznym algorytmem kompresji, zwłaszcza w zastosowaniach, w których szybkość jest ważniejsza niż osiągnięcie najwyższych możliwych współczynników kompresji.

Wniosek

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. Algorytmy te 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ą opTutaj jest tłumaczenie na język polski:

Następnie zbadaliśmy drzewa, strukturę danych drzewopodobną do przechowywania i pobierania ciągów znaków. Drzewa 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 na opisywanie wzorców ciągów znaków. Omówiliśmy podstawową składnię wyrażeń regularnych i jak można je wykorzystać 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żda ma swoje mocne strony i zastosowania.

Zrozumienie tych algorytmów i struktur danych przetwarzania ciągów znaków jest kluczowe dla każdego, kto pracuje z danymi tekstowymi. Ponieważ ilość niezorganizowanych danych stale rośnie, umiejętność wydajnego manipulowania, wyszukiwania i kompresowania ciągów znaków będzie coraz bardziej wartościowa. Opanowując techniki omówione w tym rozdziale, będziesz dobrze przygotowany do radzenia sobie z szeroką gamą wyzwań związanych z przetwarzaniem ciągów znaków w swoich własnych projektach i aplikacjach.

Chapter 7 Context Chapter 9 Algorithm Design Paradigms Divide and Conquer