Powtórzenie

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.

Spis treści

[schowaj]

· 1 Wyszukiwanie liniowe

· 2 Wyszukiwanie binarne

· 3 Proste słowniki: drzewa poszukiwań binarnych

· 4 Adresowanie bezpośrednie

· 5 Haszowanie

o 5.1 Rozwiązywanie kolizji metodą łańcuchową

o 5.2 Analiza metody łańcuchowej

o 5.3 Wybór funkcji haszujących

o 5.4 Adresowanie otwarte

o 5.5 Filtry Bloom'a

Wyszukiwanie liniowe

Jeśli nie dysponujemy żadną dodatkową wiedzą na temat zbioru, który chcemy przeszukiwać, 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 .

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,\ldots,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 prawym 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 <> nil 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 gdzie oznacza wysokość drzewa. Niestety w najgorszym przypadku drzewo może mieć bardzo dużą wysokość -- nawet (np. dla ciągu operacji Dodaj $(1,2,3,\ldots)$ ).

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,\ldots,n$ ), możemy wszystkie operacje słownikowe (dodaj, usuń, szukaj) wykonać znacznie szybciej i prościej.

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

· dodanie elementu do zbioru wymaga jedynie ustawienia wartości -tej komórki na true,

· analogicznie, usunięcie elementu do zbioru wymaga ustawienia wartości -tej komórki na false,

· sprawdzenie, czy element należy do zbioru, wykonujemy przez sprawdzenie stanu -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 , jednak w praktycznych zastosowaniach ta metoda sprawuje się doskonale.

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

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

$h : U \rightarrow \{ 0,\ldots,m-1\}$

Funkcja każdemu elementowi uniwersum przypisuje odpowiednie miejsce w tablicy . Jeśli , to z oczywistych względów znajdą się takie pary różnych elementów $x,y\in U$ , dla których . 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 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 do tablicy wymaga odczytania jego adresu z funkcji haszującej, a następnie dodania go na początek listy

1 procedure Dodaj(x);

2 begin

3 dodaj element na początek listy

4 end;

Sprawdzenie, czy element jest w zbiorze, wymaga w pesymistycznym przypadku sprawdzenia całej listy

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 $\alpha$ oznaczamy współczynnik zapełniania tablicy $\frac{n}{m}$

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

Przy takim założeniu oczekiwana długość listy elementów 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 ( oznacza rozmiar tablicy):

· $f(x)=(x\,\mod\, p)\ \mod\ m$ (gdzie jest liczbą pierwszą);

· $f(x)=(qx\,\mod\, p)\ \mod\ m$ (gdzie są liczbami pierwszymi);

· $f_{a,b}(x)=((ax+b)\,\mod\, p)\ \mod\ m$ (gdzie jest liczbą pierwszą, $1\le a < p$ , $0 \le b < p$ ).

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

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 oznacza rozmiar tablicy haszującej. Zdefiniujmy funkcję , wyznaczającą listę pozycji $H(x,0),\ldots,H(x,m-1)$ , na których może znajdować się element .

Mając daną funkcję , możemy zdefiniować , 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 jest funkcją haszującą, która przyjmuje wartości z zakresu $1,\ldots,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ę .

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 \rightarrow \{ 0,\ldots,m-1\}$ .

Dodanie elementu x sprowadza się do ustawienia wszystkich bitów dla $i=1,\ldots,k$ na wartość 1.

1 procedure Dodaj(x);

2 begin

3 for i:=1 to k do A[]:=1;

4 end;

Analogicznie, sprawdzenie, czy element x należy do zbioru, wymaga sprawdzenia bitów dla $i=1,\ldots,k$ . Jeśli wszystkie mają wartość 1, to uznajemy, że element należy do zbioru. Oczywiście powoduje to pewien odsetek błędnych odpowiedzi. Jeśli jednak 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[]=0 then return brak elementu

5 return element istnieje

6 end;

Powtórzenie

Dodaj komentarz