Algorytmy i struktury danych/Wyszukiwanie: Różnice pomiędzy wersjami

Wersja z 12:53, 18 wrz 2006

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.

function Szukaj(x, A[1..n])
begin
  for i:=1 to n do
    if A[i]=x return i;
  return brak poszukiwanego elementu;
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ę.

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

 function Szukaj(węzeł, klucz)
    if (węzeł==nil) 
       return BRAK ELEMENTU
    if (węzeł.klucz=klucz) then
       return ELEMENT ISTNIEJE
     else if (klucz < węzeł.klucz) then
       return Szukaj(węzeł.lewePoddrzewo, klucz)
    else if (klucz > węzeł.klucz) then
       return Szukaj(węzeł.prawPoddrzewo, klucz)
 end;

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

 procedure Dodaj(węzeł, klucz)
    if (klucz < węzeł.klucz) then
       if węzeł.lewePoddrzewo=nil then
           utwórz nowy węzeł z wartością klucz
           wskaźnik do nowego węzła zapisujemy w węzeł.lewePoddrzewo
       else
           Dodaj(węzeł.lewePoddrzewo, klucz)
    else if (klucz >= węzeł.klucz) then
       if węzeł.prawePoddrzewo=nil then
           utwórz nowy węzeł z wartością klucz
           wskaźnik do nowego węzła zapisujemy w węzeł.prawePoddrzewo
       else
           Dodaj(węzeł.prawePoddrzewo, klucz)
 end;

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

 procedure Usuń(węzeł, klucz) 
   if (klucz < węzeł.klucz) then
       Usuń(węzeł.lewePoddrzewo, klucz)
    else if (klucz > węzeł.klucz) then
       Usuń(węzeł.prawePoddrzewo, klucz)    
    else begin { klucz = węzeł.klucz
       if węzeł jest liściem, then
         { usuń węzeł z drzewa }
         UsunProstyPrzypadek(węzeł)
       else
         if węzeł.lewePoddrzewo <> nil then
           niech x oznacza skrajnie prawy węzeł w poddrzewie węzeł.lewePoddrzewo
           wezel.klucz:=x.klucz;
           UsunProstyPrzypadek(x);
         else
           analogiczne postępowanie dla węzeł.prawPoddrzewo 
           (jednak poszukujemy węzła na skrajnie lewej ścieżce)
    end

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

 procedure UsunProstyPrzypadek(węzeł)
   poddrzewo:=nil;
   ojciec:=węzeł.ojciec;
   if (węzeł.lewePoddrzewo) then
     poddrzewo:=węzeł.lewePoddrzewo;
   else    
     poddrzewo:=węzeł.prawePoddrzewo;    
   
   if (ojciec=nil) then
     korzen:=poddrzewo;
   else if ojciec.lewePoddrzewo=węzeł then { węzeł jest lewym synem }
     ojciec.lewePoddrzewo:=poddrzewo;
   else { węzeł jest prawym synem }
     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 ta dla każdego elementu 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.

procedure Inicjalizacja;
begin
  for i:=0 to m-1 do A[i]:=nil;
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)]$

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

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

function Szukaj(x);
begin
  l:=A[h(x)];
  while (l!=nil) do begin
     if (l.wartość=x) then return element istnieje
     l:=l.nast;
  end;
  return brak elementu
end;

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

procedure Usuń(x);
begin
  l:=A[h(x)];p:=nil;
  while (l!=nil) do begin
     if (l.wartość=x) then begin
        { usuwamy element l z listy A[h(x)] }
        if p=nil then A[h(x)]:=l.nast;
        else p.nast:=l.nast;
        return;
     end
     p:=l; l:=l.nast;
  end;
end;

Wybór funkcji haszujących

Od wyboru dobrej funkcji haszującej w dużej mierze zależy efektywność maszej 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ą), lub
$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. Używając tej metody, każda komórka tablicy zawiera wartość NIL lub element zbioru.

Niech $m$ ozncza rozmiar tablicy haszującej. Zdefiniujmy funkcję $H (x, k)$ , która wyznacza listę pozycji $H (x, 0), \dots, H (x, m - 1)$ w 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)$ .

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

Wstawianie i usuwanie elementów możemy wykonać przez analogiczne modyfikacje.

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.

procedure Dodaj(x);
begin
  for i:=1 to k do A[ $h_{i} (x)$ ]:=1;
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.

function Szukaj(x);
begin
  for i:=1 to k do 
    if A[ $h_{i} (x)$ ]=0 then return brak elementu
  return element istnieje
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

@@ Linia 279: / Linia 279: @@
 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 <math>h_i(x) : U \rightarrow : 0,\ldots,m-1</math>.
+Zakładamy, również, że mamy do dyspozycji ''k'' funkcji haszujących <math>h_i(x) : U \rightarrow  0,\ldots,m-1</math>.
 Dodanie elementu ''x'' sprowadza się do ustawienia wszystkich bitów <math>A[h_i(x)]</math> dla <math>i=1,\ldots,k</math>

Algorytmy i struktury danych/Wyszukiwanie: Różnice pomiędzy wersjami

Wersja z 12:53, 18 wrz 2006

Spis treści

Wyszukiwanie liniowe

Wyszukiwanie binarne

Proste słowniki: drzewa poszukiwań binarnych

Adresowanie bezpośrednie

Haszowanie

Rozwiązywanie kolizji metodą łańcuchową

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