Jak działają algorytmy
Chapter 4 Searching Algorithms

Rozdział 4: Algorytmy wyszukiwania

Wyszukiwanie to podstawowa operacja w informatyce, która polega na znalezieniu określonego elementu lub zbioru elementów w kolekcji danych. Wydajne algorytmy wyszukiwania i struktury danych są kluczowe dla wielu zastosowań, od baz danych i systemów plików po wyszukiwanie informacji i geometrię obliczeniową. W tym rozdziale zbadamy kilka ważnych algorytmów i struktur danych do wyszukiwania, w tym drzewa wyszukiwania binarnego, zrównoważone drzewa wyszukiwania i tablice haszujące. Omówimy również różne zastosowania wyszukiwania w realnych scenariuszach.

Tablice symboli i struktury danych

Tablica symboli to abstrakcyjny typ danych, który kojarzy klucze z wartościami, zapewniając operacje wstawiania par klucz-wartość, wyszukiwania wartości na podstawie klucza i usuwania par klucz-wartość. Tablice symboli są również znane jako słowniki lub tablice asocjacyjne w różnych językach programowania. Są to fundamentalne struktury danych używane w szerokim zakresie zastosowań, takich jak:

  • Kompilatory, gdzie tablice symboli są używane do przechowywania informacji o zmiennych, funkcjach i innych identyfikatorach.
  • Bazy danych, gdzie indeksy są budowane przy użyciu tablic symboli, aby umożliwić szybkie wyszukiwanie i pobieranie rekordów.
  • Routery sieciowe, które używają tablic symboli do przechowywania informacji o routingu w celu wydajnego przekazywania pakietów.

Istnieje kilka struktur danych, które można wykorzystać do implementacji tablic symboli, każda z nich ma swoje własne kompromisy w zakresie wydajności wyszukiwania, wstawiania i usuwania. W tej sekcji skupimy się na dwóch ważnych strukturach danych: drzewach wyszukiwania binarnego i tablicach haszujących.

Drzewa wyszukiwania binarnego (BST)

Drzewo wyszukiwania binarnego (BST) to hierarchiczna struktura danych, która przechowuje pary klucz-wartość w taki sposób, aby umożliwić wydajne operacje wyszukiwania, wstawiania i usuwania. Każdy węzeł w BST zawiera klucz, skojarzoną wartość oraz odwołania do lewego i prawego węzła potomnego. Klucz w każdym węźle jest większy niż wszystkie klucze w jego lewym poddrzewie i mniejszy niż wszystkie klucze w jego prawym poddrzewie.Oto tłumaczenie pliku Markdown na język polski. Komentarze w kodzie zostały przetłumaczone, ale sam kod pozostał niezmieniony.

e. Ta właściwość, znana jako invariant BST, pozwala na wydajne wyszukiwanie poprzez podejmowanie binarnych decyzji w każdym węźle.

Oto przykład prostego drzewa BST:

      4
    /   \
   2     6
  / \   / \
 1   3 5   7

Wyszukiwanie w drzewie BST polega na porównywaniu szukanego klucza z kluczem w bieżącym węźle i rekurencyjnym przeszukiwaniu lewego lub prawego poddrzewa w zależności od wyniku porównania. Jeśli szukany klucz zostanie znaleziony, zwracana jest skojarzona z nim wartość. Jeśli szukany klucz nie zostanie znaleziony po dotarciu do referencji null, wyszukiwanie kończy się niepowodzeniem.

Wstawianie do drzewa BST przebiega w podobny sposób jak wyszukiwanie. Porównujemy klucz nowego węzła z kluczami w drzewie BST i przemieszczamy się w dół drzewa, aż znajdziemy referencję null, gdzie dołączamy nowy węzeł jako liść. Usuwanie z drzewa BST jest nieco bardziej złożone, ponieważ wymaga obsługi trzech przypadków: usuwania węzła-liścia, usuwania węzła z jednym dzieckiem i usuwania węzła z dwoma dziećmi.

Średni czas złożoności dla wyszukiwania, wstawiania i usuwania w drzewie BST wynosi O(log n), gdzie n to liczba węzłów w drzewie. Jednak w najgorszym przypadku (np. gdy drzewo BST degeneruje się do listy jednokierunkowej), czas złożoności staje się O(n). Aby złagodzić ten problem, można używać samobalansujących się drzew BST, takich jak drzewa AVL lub drzewa czerwono-czarne, które utrzymują prawie zrównoważoną strukturę drzewa i gwarantują czas złożoności O(log n) w najgorszym przypadku dla wszystkich operacji.

Tablice haszujące

Tablica haszująca to struktura danych, która zapewnia szybkie średnie wyszukiwanie, wstawianie i usuwanie, wykorzystując funkcję haszującą do mapowania kluczy na indeksy w tablicy, zwanych kubełkami. Funkcja haszująca przyjmuje klucz jako dane wejściowe i zwraca całkowitoliczbowy indeks, który jest używany do zlokalizowania odpowiedniego kubełka w tablicy. Idealnie, funkcja haszująca powinna równomiernie rozkładać klucze między kubełkami, aby zminimalizować kolizje (tj. wiele kluczy mapowanych na ten sam kubełek).

Gdy wystąpi kolizja, istnieją dwa główne podejścia do jej rozwiązania:

  1. Łańcuchowanie rozdzielne: Każdy kubełek jest implementowany jakoOto polski przekład pliku Markdown:

Listy połączone, a wszystkie pary klucz-wartość, które hashują do tej samej kluczki, są przechowywane w liście połączonym tej kluczki.

  1. Adresowanie otwarte: Gdy wystąpi kolizja, tabela haszująca sonduje inne kluczki w z góry określonej sekwencji, aż znajdzie pustą kluczką. Powszechne techniki sondowania obejmują sondowanie liniowe, sondowanie kwadratowe i podwójne hashowanie.

Oto przykład tabeli haszującej z łańcuchowaniem:

+---+    +-------+
| 0 |--->| (1,A) |
+---+    +-------+
| 1 |--->| (5,B) |---->| (9,C) |
+---+    +-------+     +-------+
| 2 |
+---+
| 3 |--->| (7,D) |
+---+    +-------+
| 4 |
+---+

W tym przykładzie klucze 1, 5 i 9 wszystkie hashują do kluczki 1, więc są przechowywane w liście połączonym dołączonym do tej kluczki. Klucz 7 hashuje do kluczki 3 i jest jedyną parą klucz-wartość w tej kluczce.

Średni czas złożoności dla wyszukiwania, wstawiania i usuwania w dobrze zaprojektowanej tabeli haszującej wynosi O(1), co czyni ją jedną z najszybszych struktur danych dla tych operacji. Jednak najgorszy przypadek czasu złożoności może ulec pogorszeniu do O(n), jeśli funkcja haszująca jest źle wybrana lub występuje wiele kolizji. Aby utrzymać dobrą wydajność, kluczowe jest użycie wysokiej jakości funkcji haszującej i zmiana rozmiaru tabeli haszującej, gdy współczynnik obciążenia (tj. stosunek liczby par klucz-wartość do liczby kluczek) przekroczy określony próg, zwykle około 0,75.

Zrównoważone drzewa wyszukiwania

Chociaż drzewa wyszukiwania binarnego zapewniają wydajne wyszukiwanie, wstawianie i usuwanie w średnim przypadku, ich wydajność może znacznie się pogorszyć w najgorszym przypadku. Zrównoważone drzewa wyszukiwania to rodzina struktur danych, które utrzymują prawie zrównoważoną strukturę drzewa, zapewniając dobrą wydajność w najgorszym przypadku. W tej sekcji omawiamy dwa popularne zrównoważone drzewa wyszukiwania: drzewa AVL i drzewa czerwono-czarne.

Drzewa AVL

Drzewo AVL, nazwane od jego wynalazców Adelson-Velsky'ego i Landisa, jest samowyważającym się drzewem wyszukiwania binarnego, w którym wysokości lewego i prawego poddrzewa dowolnego węzła różnią się co najwyżej o jeden. Ta różnica wysokościPoniżej znajduje się tłumaczenie pliku Markdown na język polski. Komentarze w kodzie zostały przetłumaczone, ale sam kod pozostał niezmieniony.

Równowaga drzewa AVL jest określana jako współczynnik równowagi. Gdy operacja wstawiania lub usuwania narusza właściwość AVL (tj. współczynnik równowagi staje się większy niż 1 lub mniejszy niż -1), drzewo jest ponownie wyważane za pomocą jednej lub więcej rotacji.

Istnieją cztery typy rotacji używane do ponownego wyważania drzew AVL:

  1. Rotacja w lewo: Wykonywana, gdy współczynnik równowagi węzła jest większy niż 1, a współczynnik równowagi jego prawego dziecka jest nieujemny.

  2. Rotacja w prawo: Wykonywana, gdy współczynnik równowagi węzła jest mniejszy niż -1, a współczynnik równowagi jego lewego dziecka jest nieniepozytywny.

  3. Rotacja lewo-prawo: Wykonywana, gdy współczynnik równowagi węzła jest większy niż 1, a współczynnik równowagi jego prawego dziecka jest ujemny.

  4. Rotacja prawo-lewo: Wykonywana, gdy współczynnik równowagi węzła jest mniejszy niż -1, a współczynnik równowagi jego lewego dziecka jest dodatni.

Utrzymując właściwość AVL, drzewa AVL gwarantują najgorszy przypadek złożoności czasowej O(log n) dla operacji wyszukiwania, wstawiania i usuwania. Jednak stałe czynniki związane z operacjami na drzewach AVL są nieco wyższe w porównaniu do zwykłych drzew BST ze względu na narzut związany z utrzymywaniem współczynników równowagi i wykonywaniem rotacji.

Drzewa czerwono-czarne

Drzewo czerwono-czarne to inna samowyważająca się binarna drzewo poszukiwań, która utrzymuje prawie zrównoważoną strukturę. Każdy węzeł w drzewie czerwono-czarnym jest pomalowany na czerwono lub czarno, a drzewo spełnia następujące właściwości:

  1. Korzeń drzewa jest zawsze czarny.
  2. Wszystkie węzły liściowe (NIL) są czarne.
  3. Jeśli węzeł jest czerwony, oboje jego dzieci są czarne.
  4. Każda ścieżka od węzła do dowolnego jego potomnego węzła liściowego zawiera tę samą liczbę czarnych węzłów.

Te właściwości zapewniają, że najdłuższa ścieżka od korzenia do dowolnego liścia jest nie więcej niż dwa razy dłuższa niż najkrótsza ścieżka, gwarantując najgorszy przypadek złożoności czasowej O(log n) dla operacji wyszukiwania, wstawiania i usuwania.

Gdy operacja wstawiania lub usuwania naruszy dowolną z właściwości drzewa czerwono-czarnego, drzewo jest ponownie wyważane poprzez serię przełączeń kolorów i rotacji.Poniżej znajduje się tłumaczenie pliku Markdown na język polski. Komentarze w kodzie zostały przetłumaczone, ale sam kod pozostał niezmieniony.

Proces równoważenia w drzewach czerwono-czarnych jest generalnie bardziej wydajny niż w drzewach AVL, ponieważ wymaga średnio mniej rotacji. To sprawia, że drzewa czerwono-czarne są popularnym wyborem do implementacji zrównoważonych drzew wyszukiwania w praktyce, takich jak w Bibliotece Szablonów Standardowych C++ (STL) i Frameworku Kolekcji Java.

Zastosowania wyszukiwania

Algorytmy i struktury danych wyszukiwania mają liczne zastosowania w różnych dziedzinach. W tej sekcji omawiamy kilka przykładów, aby zilustrować znaczenie i wszechstronność wyszukiwania w realnych scenariuszach.

Bazy danych i systemy wyszukiwania informacji

Bazy danych i systemy wyszukiwania informacji w dużej mierze polegają na wydajnych technikach wyszukiwania, aby zapewnić szybki dostęp do danych. W bazach danych relacyjnych indeksy są budowane przy użyciu struktur danych, takich jak drzewa B lub tablice mieszające, aby umożliwić szybkie wyszukiwanie rekordów na podstawie określonych atrybutów. Te indeksy pozwalają bazom danych wydajnie wykonywać zapytania z warunkami na indeksowanych atrybutach, znacznie zmniejszając przestrzeń wyszukiwania i poprawiając wydajność zapytań.

W systemach wyszukiwania informacji, takich jak wyszukiwarki internetowe, używane są odwrócone indeksy do mapowania terminów na dokumenty je zawierające. Odwrócony indeks jest zasadniczo tabelą symboli, gdzie kluczami są terminy, a wartościami są listy identyfikatorów dokumentów. Gdy użytkownik wprowadza zapytanie, wyszukiwarka wyszukuje terminy zapytania w odwróconym indeksie i pobiera odpowiednie listy dokumentów, które są następnie łączone i rankingowane, aby uzyskać ostateczne wyniki wyszukiwania.

Projektowanie kompilatora

Kompilatory używają tabel symboli do śledzenia identyfikatorów (np. nazw zmiennych, nazw funkcji) i ich atrybutów (np. typu danych, zakresu) podczas procesu kompilacji. Gdy kompilator napotka identyfikator w kodzie źródłowym, wyszukuje go w tabeli symboli, aby określić jego znaczenie i właściwości. Wydajne wyszukiwanie jest kluczowe dla wydajności kompilatora, ponieważ typowy kompilator może mieć do przetworzenia miliony identyfikatorów w### Bioinformatyka i biologia obliczeniowa

W bioinformatyce i biologii obliczeniowej, algorytmy wyszukiwania odgrywają kluczową rolę w analizowaniu i rozumieniu danych biologicznych. Niektóre przykłady obejmują:

  • Dopasowanie sekwencji: Algorytmy takie jak BLAST (Basic Local Alignment Search Tool) i Smith-Waterman są używane do wyszukiwania podobieństw między sekwencjami DNA, RNA lub białek. Te algorytmy wykorzystują różne techniki wyszukiwania, aby efektywnie znaleźć najlepsze dopasowania między sekwencjami, pomagając badaczom zidentyfikować relacje ewolucyjne, podobieństwa funkcjonalne i potencjalne mutacje.

  • Montaż genomu: Algorytmy wyszukiwania są używane do lokalizowania nakładających się krótkich fragmentów DNA (odczytów) generowanych przez maszyny sekwencjonujące, umożliwiając rekonstrukcję oryginalnej sekwencji genomu. Wydajne wyszukiwanie jest niezbędne do obsługi ogromnych ilości danych generowanych w nowoczesnych projektach sekwencjonowania.

  • Znajdowanie genów i motywów: Badacze używają algorytmów wyszukiwania, aby zlokalizować określone wzorce lub motywy w sekwencjach DNA lub białek, takie jak miejsca wiązania czynników transkrypcyjnych, miejsca splicingowe lub zachowane domeny. Te wzorce mogą dostarczyć informacji na temat regulacji genów, funkcji białek i zachowania ewolucyjnego.

Cyberbezpieczeństwo i kryptografia

Algorytmy wyszukiwania są stosowane w różnych aspektach cyberbezpieczeństwa i kryptografii, w tym:

  • Wykrywanie włamań: Systemy wykrywania włamań do sieci często wykorzystują algorytmy wyszukiwania, takie jak Aho-Corasick lub Boyer-Moore, do efektywnego dopasowywania wzorców ruchu sieciowego do bazy danych znanych sygnatur ataków. Pozwala to na wykrywanie i zapobieganie zagrożeniom bezpieczeństwa w czasie rzeczywistym.

  • Łamanie haseł: Atakujący mogą używać algorytmów wyszukiwania do efektywnego przeszukiwania dużych słowników haseł lub generowania potencjalnych kombinacji haseł podczas próby złamania skrótów haseł. Techniki takie jak tabele tęczowe i kompromis między czasem a pamięcią polegają na wydajnym wyszukiwaniu, aby przyspieszyć odzyskiwanie haseł.Oto tłumaczenie na język polski:

  • Kryptoanalizy: W kryptografii, algorytmy wyszukiwania są używane do analizowania i potencjalnego wykorzystywania słabości w systemach kryptograficznych. Na przykład, algorytmy takie jak baby-step giant-step lub rho Pollarda są używane do rozwiązywania problemu logarytmu dyskretnego, który leży u podstaw bezpieczeństwa niektórych schematów kryptograficznych.

Wniosek

Algorytmy wyszukiwania i struktury danych są podstawowymi narzędziami w informatyce, z zastosowaniami obejmującymi szeroką gamę dziedzin. Od baz danych i wyszukiwania informacji po obliczenia naukowe, bioinformatykę i cyberbezpieczeństwo, zdolność do efektywnego wyszukiwania i lokalizowania danych jest kluczowa dla rozwiązywania złożonych problemów i wydobywania cennych informacji.

Poprzez zrozumienie zasad i technik stojących za algorytmami wyszukiwania, takich jak drzewa wyszukiwania binarnego, zrównoważone drzewa wyszukiwania i tablice mieszające, deweloperzy mogą podejmować świadome decyzje podczas projektowania i wdrażania systemów, które polegają na wydajnych możliwościach wyszukiwania. Wybór odpowiedniego algorytmu wyszukiwania i struktury danych zależy od czynników takich jak rozmiar i charakter danych, częstotliwość operacji wyszukiwania oraz specyficzne wymagania aplikacji.

Ponieważ ilość generowanych i przetwarzanych danych rośnie wykładniczo, znaczenie wydajnych algorytmów wyszukiwania będzie tylko rosło. Badacze i praktycy w różnych dziedzinach będą nadal polegać na tych podstawowych narzędziach, aby stawić czoła wyzwaniom stawianych przez big data i odkrywać nowe możliwości dla odkryć i innowacji.

Chapter 3 Sorting AlgorithmsChapter 5 Graphs