Algorytmy i struktury danych/Wyszukiwanie

Wyszukiwanie

W niniejszym wykładzie opiszemy podstawowe techniki dotyczące wyszukiwania. Zajmiemy się również prostymi strukturami słownikowymi, które oprócz wyszukiwania, umożliwiają dodawanie i usuwanie elementów.

Wyszukiwanie liniowe

Jeśli nie dysponujemy żadną dodatkową wiedzą na temat zbioru, który chcemy przeszukiwać, to niestety musimy sprawdzić wszystkie jego elementy.

1 function Szukaj(x, A[1..n])
2 begin
3   for i:=1 to n do
4     if A[i]=x return i;
5   return brak poszukiwanego elementu;
6 end

Oczywiście w pesymistycznym przypadku (np. gdy zbiór nie zawiera poszukiwanego elementu) koszt czasowy, to $O (n)$ .

Wyszukiwanie binarne

W niektórych przypadkach czas poszukiwania możemy znacząco zmniejszyć. Dzieje się tak na przykład, gdy przeszukiwany zbiór przechowujemy w rosnąco uporządkowanej tablicy. W takim przypadku wystarczy jedynie $O (\log n)$ operacji, by odnaleźć poszukiwany element lub stwierdzić jego brak.

Algorytm utrzymuje zakres $[l, \dots, r]$ , w którym może znajdować się element; przy każdym porównaniu zakres zostaje zmniejszony o połowę.

1  function WyszukiwanieBinarne(x, A[1..n])
2  { zakładamy, że tablica A jest uporządkowana rosnąco }
3  begin
4    l:=1;r:=n;
5    while (l<=r) do begin
6      { niezmiennik: poszukiwany element może znajdować się w zakresie A[l..r] }
7      m:=(l+r) div 2;
8      if (A[m]<x) then l:=m+1
9      else if (A[m]>x) then r:=m-1
10     else return m; { ponieważ A[m]=x } 
11   end;
12   return brak poszukiwanego elementu;
13 end;

Proste słowniki: drzewa poszukiwań binarnych

Podstawowe operacje słownika to wyszukiwanie, wstawianie i usuwanie klucza. Drzewa poszukiwań binarnych (bez dodatkowych specjanych wymagań) mogą być traktowane jako prosty słownik. Sa to zwykłe drzewa binarne, których klucze spełniają następujące własności:

Dla dowolnego węzła x:

wszystkie klucze w lewym poddrzewie węzła x mają wartości mniejsze niż klucz węzła x,
wszystkie klucze w lewym poddrzewie węzła x mają wartości większe lub równe niż klucz węzła x.

Dodatkowe wymaganie dotyczące kluczy, umożliwia nam efektywne wyszukiwanie elementów w drzewie.

1  function Szukaj(węzeł, klucz)
2     if (węzeł==nil) 
3        return BRAK ELEMENTU
4     if (węzeł.klucz=klucz) then
5        return ELEMENT ISTNIEJE
6      else if (klucz < węzeł.klucz) then
7       return Szukaj(węzeł.lewePoddrzewo, klucz)
8     else if (klucz > węzeł.klucz) then
9        return Szukaj(węzeł.prawPoddrzewo, klucz)
10  end;

Wstawianie do drzewa jest bardzo zbliżone do wyszukiwania: musimy przejść po drzewie (rozpoczynając w korzeniu), aby odnaleźć wolne miejsce, w którym możemy dodać nową wartość.

1  procedure Dodaj(węzeł, klucz)
2    if (klucz < węzeł.klucz) then
3      if węzeł.lewePoddrzewo=nil then
4        utwórz nowy węzeł z wartością klucz
5        wskaźnik do nowego węzła zapisujemy w węzeł.lewePoddrzewo
6      else
7        Dodaj(węzeł.lewePoddrzewo, klucz)
8    else if (klucz >= węzeł.klucz) then
9      if węzeł.prawePoddrzewo=nil then
10       utwórz nowy węzeł z wartością klucz
11       wskaźnik do nowego węzła zapisujemy w węzeł.prawePoddrzewo
12     else
13       Dodaj(węzeł.prawePoddrzewo, klucz)
14 end;

Możemy również usuwać wartości z drzewa, niestety ta operacja jest bardziej skomplikowana.

1  procedure Usuń(węzeł, klucz) 
2    if (klucz < węzeł.klucz) then
3      Usuń(węzeł.lewePoddrzewo, klucz)
4    else if (klucz > węzeł.klucz) then
5      Usuń(węzeł.prawePoddrzewo, klucz)    
6    else begin { klucz = węzeł.klucz
7      if węzeł jest liściem, then
8        { usuń węzeł z drzewa }
9        UsunProstyPrzypadek(węzeł)
10     else
11       if węzeł.lewePoddrzewo <> nil then
12         niech x oznacza skrajnie prawy węzeł w poddrzewie węzeł.lewePoddrzewo
13         wezel.klucz:=x.klucz;
14         UsunProstyPrzypadek(x);
15       else
16         analogiczne postępowanie dla węzeł.prawPoddrzewo 
17         (jednak poszukujemy węzła na skrajnie lewej ścieżce)
18 end

Procedura UsunProstyPrzypadek oznacza usuwanie z drzewa węzła, który ma co najwyżej jednego syna.

1 procedure UsunProstyPrzypadek(węzeł)
2 begin
3    poddrzewo:=nil;
4    ojciec:=węzeł.ojciec;
5    if (węzeł.lewePoddrzewo) then
6      poddrzewo:=węzeł.lewePoddrzewo;
7    else    
8      poddrzewo:=węzeł.prawePoddrzewo;    
   
9    if (ojciec=nil) then
10     korzen:=poddrzewo;
11   else if ojciec.lewePoddrzewo=węzeł then { węzeł jest lewym synem }
12     ojciec.lewePoddrzewo:=poddrzewo;
13   else { węzeł jest prawym synem }
14     ojciec.prawePoddrzewo:=poddrzewo;

Wszystkie podane operacje mają pesymistyczny koszt $O (h)$ gdzie $h$ oznacza wysokość drzewa. Niestety w najgorszym przypadku drzewo może mieć bardzo dużą wysokość -- nawet $O (n)$ (np. dla ciągu operacji Dodaj $(1, 2, 3, \dots)$ ).

Adresowanie bezpośrednie

W przypadku gdy zbiór, który przechowujemy pochodzi z niewielkiego uniwersum (na przykład elementy zbioru to liczby z zakresu $1, \dots, n$ ), możemy wszystkie operacje słownikowe (dodaj, usuń, szukaj) wykonać znacznie szybciej i prościej.

Dla uniwersum $1, \dots, n$ zbiór możemy reprezentować przez tablicę $n$ -elementową. Początkowo w każdej komórce tablicy wpisujemy wartość false.

dodanie elementu $i$ do zbioru wymaga jedynie ustawienia wartości $i$ -tej komórki na true,
analogicznie, usunięcie elementu $i$ do zbioru wymaga ustawienia wartości $i$ -tej komórki na false,
sprawdzenie, czy element $i$ należy do zbioru, wykonujemy przez sprawdzenie stanu $i$ -tej komórki.

Wszystkie powyższe operacje możemy wykonać używając stałej liczby kroków.

Haszowanie

Czy możemy wykorzystać adresowanie bezpośrednie do dowolnych zbiorów? Okazuje się, że tak. Co prawda w pesymistycznym przypadku koszt jednej operacji może wynosić nawet $O (n)$ , jednak w praktycznych zastosowaniach ta metoda sprawuje się doskonale.

W tym rozdziale będziemy zakładać, że elementy uniwersum $U$ to dodatnie liczby całkowite. Dodatkowo zakładamy, że dysponujemy tablicą $A [0, \dots, m - 1]$ .

Ponieważ elementami mogą być bardzo duże liczby całkowite, stąd nie możemy zastosować metody adresowania bezpośredniego. Jednak możemy wybrać funkcję haszującą:

$h : U \to {0, \dots, m - 1}$

Funkcja każdemu elementowi uniwersum przypisuje odpowiednie miejsce w tablicy $A$ . Jeśli $| U | > m$ , to z oczywistych względów znajdą się takie pary różnych elementów $x, y \in U$ , dla których $f (x) = f (y)$ . W takim przypadku mówimy o istnieniu kolizji. Właśnie ze względu na ryzyko wystąpienia kolizji musimy nieznacznie zmodyfikować metodę adresowania bezpośredniego - zamiast przechowywać w tablicy wartość logiczną (prawda/fałsz), musimy zapisywać wartość przechowywanego elementu.

Rozwiązywanie kolizji metodą łańcuchową

Jedną z metod rozwiązywania kolizji jest utrzymywanie w każdej komórce tablicy listy elementów do niej przypisanych. Początkowo tablica $A$ wypełniona jest wartościami nil.

1 procedure Inicjalizacja;
2 begin
3   for i:=0 to m-1 do A[i]:=nil;
4 end;

Dodanie elementu $x$ do tablicy wymaga odczytania jego adresu z funkcji haszującej, a następnie dodania go na początek listy $A [h (x)]$

1 procedure Dodaj(x);
2 begin
3   dodaj element  $x$  na początek listy  $A [h (x)]$ 
4 end;

Sprawdzenie, czy element $x$ jest w zbiorze, wymaga w pesymistycznym przypadku sprawdzenia całej listy $A [h (x)]$

1 function Szukaj(x);
2 begin
3   l:=A[h(x)];
4   while (l!=nil) do begin
5      if (l.wartość=x) then return element istnieje
6      l:=l.nast;
7   end;
8   return brak elementu
9 end;

Usuwanie elementu z tablicy jest bardzo podobne do wyszukiwania i również w pesymistycznym przypadku wymaga sprawdzenia całej listy.

1  procedure Usuń(x);
2  begin
3   l:=A[h(x)];p:=nil;
4   while (l!=nil) do begin
5     if (l.wartość=x) then begin
6       { usuwamy element l z listy A[h(x)] }
7       if p=nil then A[h(x)]:=l.nast;
8       else p.nast:=l.nast;
9       return;
10    end
11    p:=l; l:=l.nast;
12  end;
13 end;

Analiza metody łańcuchowej

Haszowanie to metoda, która bardzo dobrze sprawdza się w praktyce, zastanówmy się przez chwilę, czy dobre własności tej metody można udowodnić.

Niech:

m oznacza rozmiar tablicy,
n oznacza liczbę elementów, które przetrzymujemy w tablicy,
przez $α$ oznaczamy współczynnik zapełniania tablicy $\frac{n}{m}$

Załóżmy, że dysponujemy idealną funkcją haszującą, dla której przypisanie każda wartość $h (x)$ jest równie prawdopodobna, czyli $P ({h (x) = i}) = \frac{1}{m}$ .

Przy takim założeniu oczekiwana długość listy elementów $A [h (x)]$ ma długość $\frac{n}{m}$ (oczekiwana liczba sukcesów w n próbach Bernoulli'ego).

Stąd oczekiwana złożoność operacji Szukaj, Dodaj, Usuń wynosi:

T (n, m) = \frac{n}{m} + O (1)

Wybór funkcji haszujących

Od wyboru dobrej funkcji haszującej w dużej mierze zależy efektywność naszej struktury danych. Niestety, nie można podać ścisłej procedury wyboru takiej funkcji.

Dla liczb całkowitych możemy przykładowo wybrać jedną z następujących funkcji ( $m$ oznacza rozmiar tablicy):

$f (x) = (x mod p) mod m$ (gdzie $p > m$ jest liczbą pierwszą);
$f (x) = (q x mod p) mod m$ (gdzie $p, q$ są liczbami pierwszymi);
$f_{a, b} (x) = ((a x + b) mod p) mod m$ (gdzie $p$ jest liczbą pierwszą, $1 \leq a < p$ , $0 \leq b < p$ ).

Jeśli nie dysponujemy żadną dodatkową wiedzą na temat elementów które będzie zawierać tablica, to rozsądnym rozwiązanie jest wybór funkcji $f_{a, b}$ dla losowych wartości $a, b$ .

Adresowanie otwarte

Adresowanie otwarte jest metodą pozwalającą uniknąć utrzymywania list elementów w tablicy haszującej. Oczywiście wymaga to opracowania innej metody rozwiązywania konfliktów. Każda komórka tablicy zawiera teraz wartość NIL lub element zbioru.

Niech $m$ oznacza rozmiar tablicy haszującej. Zdefiniujmy funkcję $H (x, k)$ , wyznaczającą listę pozycji $H (x, 0), \dots, H (x, m - 1)$ , na których może znajdować się element $x$ .

Mając daną funkcję $h (x)$ , możemy zdefiniować $H (x, k)$ , jako:

$H (x, k) = (h (x) + k) mod m$ --- adresowanie liniowe;
$H (x, k) = (h (x) + a_{1} \cdot k + a_{2} \cdot k^{2}) mod m$ --- adresowanie kwadratowe;
$H (x, k) = (h (x) + h_{2} (x) \cdot k) mod m$ --- podwójne haszowanie, przy czym $h_{2} (x)$ jest funkcją haszującą, która przyjmuje wartości z zakresu $1, \dots, m - 1$ .

Wyszukiwanie elementów możemy wykonać nieznacznie modyfikując poprzednie rozwiązanie -- zamiast przeszukiwać listę elementów, musimy przeszukać ciąg pozycji zdefiniowany przez funkcję $H (x, k)$ .

1 function Szukaj(x);
2 begin
3   k:=0;
4   while (A[H(x,k)!=nil) do begin
5      if (A[H(x,k)].wartość=x) then return element istnieje
6      k:=k+1;
7   end;
8   return brak elementu
9 end;

Wstawianie elementów możemy wykonać przez analogiczne modyfikacje; usuwanie jest zwykle znacznie trudniejsze.

Filtry Bloom'a

Ciekawym połączeniem adresowania bezpośredniego z haszowaniem są filtry Bloom'a. Polegają one na rozlużnieniu założeń naszej struktury:

ograniczamy się do operacji Dodaj i Szukaj,
pozwalamy na nieprawidłowe odpowiedzi dla operacji Szukaj (jednak z małym prawdopodobieństwem).

Nasza struktura to bitowa tablica o rozmiarze m, początkowo tablica jest wypełniona zerami. Zakładamy również, że mamy do dyspozycji k funkcji haszujących $h_{i} (x) : U \to {0, \dots, m - 1}$ .

Dodanie elementu x sprowadza się do ustawienia wszystkich bitów $A [h_{i} (x)]$ dla $i = 1, \dots, k$ na wartość 1.

1 procedure Dodaj(x);
2 begin
3   for i:=1 to k do A[ $h_{i} (x)$ ]:=1;
4 end;

Analogicznie, sprawdzenie, czy element x należy do zbioru, wymaga sprawdzenia bitów $A [h_{i} (x)]$ dla $i = 1, \dots, k$ . Jeśli wszystkie mają wartość 1, to uznajemy, że element należy do zbioru. Oczywiście powoduje to pewien odsetek błędnych odpowiedzi. Jednak jeśli dobrze dobierzemy funkcje, a wypełnienie tablicy nie będzie zbyt duże, to taka struktura będzie dobrze sprawować się w praktyce.

1 function Szukaj(x);
2 begin
3   for i:=1 to k do 
4     if A[ $h_{i} (x)$ ]=0 then return brak elementu
5   return element istnieje
6 end;

Literatura

[CLRS] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, 'Wprowadzenie do algorytmów', WNT, Warszawa 2004.

powrót do strony przedmiotu

Algorytmy i struktury danych/Wyszukiwanie

Spis treści

Wyszukiwanie liniowe

Wyszukiwanie binarne

Proste słowniki: drzewa poszukiwań binarnych

Adresowanie bezpośrednie

Haszowanie

Rozwiązywanie kolizji metodą łańcuchową

Analiza metody łańcuchowej

Wybór funkcji haszujących

Adresowanie otwarte

Filtry Bloom'a

Literatura

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia