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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 26: Linia 26:
 
== Wyszukiwanie binarne ==
 
== Wyszukiwanie binarne ==
  
W niektórych przypadkach czas poszukiwania, możemy znacząco zmniejszyć.
+
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
 
Dzieje się tak na przykład, gdy przeszukiwany zbiór przechowujemy w rosnąco
 
uporządkowanej tablicy.
 
uporządkowanej tablicy.
W takim przypadku, wystarczy jedynie <math>O(\log n)</math> operacji, by  
+
W takim przypadku wystarczy jedynie <math>O(\log n)</math> operacji, by  
odnaleźć poszukiwany element, lub stwierdzić jego brak.
+
odnaleźć poszukiwany element lub stwierdzić jego brak.
  
 
Algorytm utrzymuje zakres <math>[l,\ldots,r]</math>, w którym może
 
Algorytm utrzymuje zakres <math>[l,\ldots,r]</math>, w którym może
znajdować się element, przy każdym porównaniu zakres zostaje zmniejszony  
+
znajdować się element; przy każdym porównaniu zakres zostaje zmniejszony  
 
o połowę.
 
o połowę.
  
 
  '''function''' WyszukiwanieBinarne(''x'', ''A''[1..''n''])
 
  '''function''' WyszukiwanieBinarne(''x'', ''A''[1..''n''])
  { zakładamy, że tablica A, jest uporządkowana rosnąco }
+
  { zakładamy, że tablica A jest uporządkowana rosnąco }
 
  '''begin'''
 
  '''begin'''
 
   l:=1;r:=n;
 
   l:=1;r:=n;
 
   '''while''' (l<=r) '''do''' '''begin'''
 
   '''while''' (l<=r) '''do''' '''begin'''
     { niezmiennik, poszukiwany element, może znajdować się w zakresie A[l..r] }
+
     { niezmiennik: poszukiwany element może znajdować się w zakresie A[l..r] }
 
     m:=(l+r) '''div''' 2;
 
     m:=(l+r) '''div''' 2;
 
     '''if''' (A[m]<x) '''then''' l:=m+1
 
     '''if''' (A[m]<x) '''then''' l:=m+1
Linia 56: Linia 56:
  
 
Dla dowolnego węzła ''x'':
 
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 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''.
+
* wszystkie klucze w lewym poddrzewie węzła ''x'' mają wartości większe lub równe niż klucz węzła ''x''.
  
 
<center>[[Grafika:wyszukiwanie.1.png]]</center>
 
<center>[[Grafika:wyszukiwanie.1.png]]</center>
Linia 74: Linia 74:
 
   '''end''';
 
   '''end''';
  
Wstawianie do drzewa jest bardzo zbliżone do wyszukiwania, musimy przejść po drzewie  
+
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ść.
+
(rozpoczynając w korzeniu), aby odnaleźć wolne miejsce, w którym możemy dodać nową wartość.
  
 
   '''procedure''' Dodaj(węzeł, klucz)
 
   '''procedure''' Dodaj(węzeł, klucz)
Linia 137: Linia 137:
 
== Adresowanie bezpośrednie ==
 
== Adresowanie bezpośrednie ==
  
W przypadku gdy zbiór który przechowujemy pochodzi z niewielkiego uniwersum
+
W przypadku gdy zbiór, który przechowujemy pochodzi z niewielkiego uniwersum
 
(na przykład elementy zbioru to liczby z zakresu <math>1,\ldots,n</math>),
 
(na przykład elementy zbioru to liczby z zakresu <math>1,\ldots,n</math>),
 
możemy wszystkie operacje słownikowe (dodaj, usuń, szukaj) wykonać
 
możemy wszystkie operacje słownikowe (dodaj, usuń, szukaj) wykonać
Linia 146: Linia 146:
 
Początkowo w każdej komórce tablicy wpisujemy wartość ''false''.
 
Początkowo w każdej komórce tablicy wpisujemy wartość ''false''.
  
* dodanie elementu <math>i</math> do zbioru, wymaga jedynie ustawienia wartości <math>i</math>-tej komórki na ''true'',
+
* dodanie elementu <math>i</math> do zbioru wymaga jedynie ustawienia wartości <math>i</math>-tej komórki na ''true'',
* analogicznie usunięcie elementu <math>i</math> do zbioru, wymaga ustawienia wartości <math>i</math>-tej komórki na ''false'',
+
* analogicznie, usunięcie elementu <math>i</math> do zbioru wymaga ustawienia wartości <math>i</math>-tej komórki na ''false'',
* sprawdzenie czy element <math>i</math> należy do zbioru wykonujemy przez sprawdzenie stanu <math>i</math>-tej komórki.
+
* sprawdzenie, czy element <math>i</math> należy do zbioru, wykonujemy przez sprawdzenie stanu <math>i</math>-tej komórki.
  
 
Wszystkie powyższe operacje możemy wykonać używając stałej liczby kroków.
 
Wszystkie powyższe operacje możemy wykonać używając stałej liczby kroków.
Linia 159: Linia 159:
 
zastosowaniach ta metoda sprawuje się doskonale.
 
zastosowaniach ta metoda sprawuje się doskonale.
  
W tym rozdziale będziemy zakładać, że elementy uniwersum <math>U</math>,
+
W tym rozdziale będziemy zakładać, że elementy uniwersum <math>U</math>
 
to dodatnie liczby całkowite.  
 
to dodatnie liczby całkowite.  
 
Dodatkowo zakładamy, że dysponujemy tablicą <math>A[0,\ldots,m-1]</math>.
 
Dodatkowo zakładamy, że dysponujemy tablicą <math>A[0,\ldots,m-1]</math>.
Linia 168: Linia 168:
  
 
<center>
 
<center>
<math>h : U \rightarrow 0,\ldots,m-1</math>
+
<math>h : U \rightarrow \{ 0,\ldots,m-1\}</math>
 
</center>
 
</center>
  
Funkcja ta dla każdego elementu uniwersum przypisuje  
+
Funkcja każdemu elementowi uniwersum przypisuje  
 
odpowiednie miejsce w tablicy <math>A</math>. Jeśli <math>|U|>m</math>, to
 
odpowiednie miejsce w tablicy <math>A</math>. Jeśli <math>|U|>m</math>, to
 
z oczywistych względów znajdą się takie pary różnych elementów <math>x,y\in U</math>,
 
z oczywistych względów znajdą się takie pary różnych elementów <math>x,y\in U</math>,
 
dla których <math>f(x)=f(y)</math>. W takim przypadku mówimy o istnieniu '''kolizji'''.
 
dla których <math>f(x)=f(y)</math>. W takim przypadku mówimy o istnieniu '''kolizji'''.
Właśnie ze względu na ryzyko wystąpienia kolizji, musimy nieznacznie zmodyfikować metodę
+
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),
 
adresowania bezpośredniego - zamiast przechowywać w tablicy wartość logiczną (prawda/fałsz),
 
musimy zapisywać wartość przechowywanego elementu.
 
musimy zapisywać wartość przechowywanego elementu.
Linia 190: Linia 190:
 
  '''end''';
 
  '''end''';
  
Dodanie elementu <math>x</math> do tablicy, wymaga odczytania jego adresu z funkcji haszującej,
+
Dodanie elementu <math>x</math> do tablicy wymaga odczytania jego adresu z funkcji haszującej,
 
a następnie dodania go na początek listy <math>A[h(x)]</math>
 
a następnie dodania go na początek listy <math>A[h(x)]</math>
  
Linia 198: Linia 198:
 
  '''end''';
 
  '''end''';
  
Sprawdzenie czy element <math>x</math> istnieje, wymaga w pesymistycznym przypadku sprawdzenia całej listy <math>A[h(x)]</math>
+
Sprawdzenie, czy element <math>x</math> jest w zbiorze, wymaga w pesymistycznym przypadku sprawdzenia całej listy <math>A[h(x)]</math>
  
 
  '''function''' Szukaj(x);
 
  '''function''' Szukaj(x);
Linia 210: Linia 210:
 
  '''end''';
 
  '''end''';
  
Usuwanie elementu z tablicy jest bardzo podobne do wyszukiwania, i również w pesymistycznym przypadku wymaga sprawdzenia całej listy.
+
Usuwanie elementu z tablicy jest bardzo podobne do wyszukiwania i również w pesymistycznym przypadku wymaga sprawdzenia całej listy.
  
 
  '''procedure''' Usuń(x);
 
  '''procedure''' Usuń(x);
Linia 229: Linia 229:
  
 
Od wyboru dobrej funkcji haszującej w dużej mierze zależy efektywność
 
Od wyboru dobrej funkcji haszującej w dużej mierze zależy efektywność
maszej struktury danych.  
+
naszej struktury danych.  
Niestety nie można podać ścisłej procedury wyboru takiej funkcji.
+
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 (<math>m</math> oznacza rozmiar tablicy):
+
Dla liczb całkowitych możemy przykładowo wybrać jedną z następujących funkcji (<math>m</math> oznacza rozmiar tablicy):
* <math>f(x)=(x\,\mod\, p)\ \mod\ m</math> (gdzie <math>p>m</math> jest liczbą pierwszą), lub
+
* <math>f(x)=(x\,\mod\, p)\ \mod\ m</math> (gdzie <math>p>m</math> jest liczbą pierwszą);
* <math>f(x)=(qx\,\mod\, p)\ \mod\ m</math> (gdzie <math>p,q</math> są liczbami pierwszymi).
+
* <math>f(x)=(qx\,\mod\, p)\ \mod\ m</math> (gdzie <math>p,q</math> są liczbami pierwszymi);
 
* <math>f_{a,b}(x)=((ax+b)\,\mod\, p)\ \mod\ m</math> (gdzie <math>p</math> jest liczbą pierwszą, <math>1\le a < p</math>, <math>0 \le b < p</math>).
 
* <math>f_{a,b}(x)=((ax+b)\,\mod\, p)\ \mod\ m</math> (gdzie <math>p</math> jest liczbą pierwszą, <math>1\le a < p</math>, <math>0 \le b < p</math>).
  
Linia 242: Linia 242:
 
=== Adresowanie otwarte ===
 
=== Adresowanie otwarte ===
  
Adresowanie otwarte, jest metodą pozwalającą uniknąć utrzymywania list elementów w tablicy haszującej.
+
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.
+
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.
+
Każda komórka tablicy zawiera teraz wartość NIL lub element zbioru.
  
Niech <math>m</math> ozncza rozmiar tablicy haszującej.
+
Niech <math>m</math> oznacza rozmiar tablicy haszującej.
Zdefiniujmy funkcję <math>H(x,k)</math>, która wyznacza listę pozycji
+
Zdefiniujmy funkcję <math>H(x,k)</math>, wyznaczającą listę pozycji
<math>H(x,0),\ldots,H(x,m-1)</math> w których może znajdować się element <math>x</math>.
+
<math>H(x,0),\ldots,H(x,m-1)</math>, na których może znajdować się element <math>x</math>.
  
Mając daną funkcję <math>h(x)</math> możemy zdefiniować <math>H(x,k)</math>, jako:
+
Mając daną funkcję <math>h(x)</math>, możemy zdefiniować <math>H(x,k)</math>, jako:
* <math>H(x,k)=(h(x)+k)\ \mod\ m</math> --- adresowanie liniowe,
+
* <math>H(x,k)=(h(x)+k)\ \mod\ m</math> --- adresowanie liniowe;
* <math>H(x,k)=(h(x)+a_1\cdot k+a_2\cdot k^2)\ \mod\ m</math> --- adresowanie kwadratowe,
+
* <math>H(x,k)=(h(x)+a_1\cdot k+a_2\cdot k^2)\ \mod\ m</math> --- adresowanie kwadratowe;
* <math>H(x,k)=(h(x)+h_2(x)\cdot k)\ \mod\ m</math> --- podwójne haszowanie, przy czym <math>h_2(x)</math> jest funkcją haszującą, która przyjmuje wartości z zakresu <math>1,\ldots,m-1</math>
+
* <math>H(x,k)=(h(x)+h_2(x)\cdot k)\ \mod\ m</math> --- podwójne haszowanie, przy czym <math>h_2(x)</math> jest funkcją haszującą, która przyjmuje wartości z zakresu <math>1,\ldots,m-1</math>.
  
 
Wyszukiwanie elementów możemy wykonać nieznacznie modyfikując poprzednie rozwiązanie
 
Wyszukiwanie elementów możemy wykonać nieznacznie modyfikując poprzednie rozwiązanie
Linia 269: Linia 269:
 
  '''end''';
 
  '''end''';
  
Wstawianie i usuwanie elementów możemy wykonać przez analogiczne modyfikacje.
+
Wstawianie elementów możemy wykonać przez analogiczne modyfikacje; usuwanie jest zwykle znacznie trudniejsze.
  
 
=== Filtry Bloom'a ===
 
=== Filtry Bloom'a ===
Linia 279: Linia 279:
  
 
Nasza struktura to bitowa tablica o rozmiarze ''m'', początkowo tablica jest wypełniona zerami.  
 
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>
 
Dodanie elementu ''x'' sprowadza się do ustawienia wszystkich bitów <math>A[h_i(x)]</math> dla <math>i=1,\ldots,k</math>
Linia 289: Linia 289:
 
  '''end''';
 
  '''end''';
  
Analogicznie sprawdzenie czy element ''x'' należy do zbioru, wymaga sprawdzenia bitów <math>A[h_i(x)]</math> dla <math>i=1,\ldots,k</math>.
+
Analogicznie, sprawdzenie, czy element ''x'' należy do zbioru, wymaga sprawdzenia bitów <math>A[h_i(x)]</math> dla <math>i=1,\ldots,k</math>.
 
Jeśli wszystkie mają wartość 1, to uznajemy, że element należy do zbioru.  
 
Jeśli wszystkie mają wartość 1, to uznajemy, że element należy do zbioru.  
 
Oczywiście powoduje to pewien odsetek błędnych odpowiedzi.  
 
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,  
+
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.
 
to taka struktura będzie dobrze sprawować się w praktyce.
  

Wersja z 12:50, 25 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 .

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 operacji, by odnaleźć poszukiwany element lub stwierdzić jego brak.

Algorytm utrzymuje zakres , 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.
Wyszukiwanie.1.png

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ąc 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 gdzie oznacza wysokość drzewa. Niestety w najgorszym przypadku drzewo może mieć bardzo dużą wysokość -- nawet (np. dla ciągu operacji Dodaj ).

Adresowanie bezpośrednie

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

Dla uniwersum 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ą .

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ą:

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 , 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.

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

Dodanie elementu do tablicy wymaga odczytania jego adresu z funkcji haszującej, a następnie dodania go na początek listy

procedure Dodaj(x);
begin
  dodaj element  na początek listy 
end;

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

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ść 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):

  • (gdzie jest liczbą pierwszą);
  • (gdzie są liczbami pierwszymi);
  • (gdzie jest liczbą pierwszą, , ).

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 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 , na których może znajdować się element .

Mając daną funkcję , możemy zdefiniować , jako:

  • --- adresowanie liniowe;
  • --- adresowanie kwadratowe;
  • --- podwójne haszowanie, przy czym jest funkcją haszującą, która przyjmuje wartości z zakresu .

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ę .

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 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 .

Dodanie elementu x sprowadza się do ustawienia wszystkich bitów dla na wartość 1.

procedure Dodaj(x);
begin
  for i:=1 to k do A[]:=1;
end;

Analogicznie, sprawdzenie, czy element x należy do zbioru, wymaga sprawdzenia bitów dla . 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[]=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