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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 14: Linia 14:
 
przeszukiwać, to niestety musimy sprawdzić wszystkie jego elementy.
 
przeszukiwać, to niestety musimy sprawdzić wszystkie jego elementy.
  
  '''function Szukaj(''x'', ''A''[1..''n''])
+
  1 '''function Szukaj(''x'', ''A''[1..''n''])
  '''begin'''
+
  2 '''begin'''
  '''for''' i:=1 '''to''' ''n'' '''do'''
+
'''for''' i:=1 '''to''' ''n'' '''do'''
    '''if''' A[i]=x '''return''' ''i'';
+
4    '''if''' A[i]=x '''return''' ''i'';
  '''return''' ''brak poszukiwanego elementu'';
+
'''return''' ''brak poszukiwanego elementu'';
  '''end'''
+
  6 '''end'''
  
 
Oczywiście w pesymistycznym przypadku (np. gdy zbiór nie zawiera poszukiwanego elementu)
 
Oczywiście w pesymistycznym przypadku (np. gdy zbiór nie zawiera poszukiwanego elementu)
Linia 36: Linia 36:
 
o połowę.
 
o połowę.
  
  '''function''' WyszukiwanieBinarne(''x'', ''A''[1..''n''])
+
1 '''function''' WyszukiwanieBinarne(''x'', ''A''[1..''n''])
  { zakładamy, że tablica A jest uporządkowana rosnąco }
+
2 { zakładamy, że tablica A jest uporządkowana rosnąco }
  '''begin'''
+
3 '''begin'''
   l:=1;r:=n;
+
4   l:=1;r:=n;
   '''while''' (l<=r) '''do''' '''begin'''
+
5   '''while''' (l<=r) '''do''' '''begin'''
     { niezmiennik: poszukiwany element może znajdować się w zakresie A[l..r] }
+
6     { niezmiennik: poszukiwany element może znajdować się w zakresie A[l..r] }
     m:=(l+r) '''div''' 2;
+
7     m:=(l+r) '''div''' 2;
     '''if''' (A[m]<x) '''then''' l:=m+1
+
8     '''if''' (A[m]<x) '''then''' l:=m+1
     '''else if''' (A[m]>x) '''then''' r:=m-1
+
9     '''else if''' (A[m]>x) '''then''' r:=m-1
    '''else''' '''return''' ''m''; { ponieważ A[m]=x }  
+
10    '''else''' '''return''' ''m''; { ponieważ A[m]=x }  
  '''end''';
+
11  '''end''';
  '''return''' brak poszukiwanego elementu;
+
12  '''return''' brak poszukiwanego elementu;
  '''end''';
+
  13 '''end''';
  
 
== Proste słowniki: drzewa poszukiwań binarnych ==
 
== Proste słowniki: drzewa poszukiwań binarnych ==
Linia 63: Linia 63:
 
Dodatkowe wymaganie dotyczące kluczy, umożliwia nam efektywne wyszukiwanie elementów w drzewie.
 
Dodatkowe wymaganie dotyczące kluczy, umożliwia nam efektywne wyszukiwanie elementów w drzewie.
  
  '''function''' Szukaj(węzeł, klucz)
+
'''function''' Szukaj(węzeł, klucz)
    '''if''' (węzeł=='''nil''')  
+
2    '''if''' (węzeł=='''nil''')  
        '''return''' BRAK ELEMENTU
+
3        '''return''' BRAK ELEMENTU
    '''if''' (węzeł.klucz=klucz) '''then'''
+
4    '''if''' (węzeł.klucz=klucz) '''then'''
        '''return''' ELEMENT ISTNIEJE
+
5        '''return''' ELEMENT ISTNIEJE
    ''' else if (klucz < węzeł.klucz) '''then'''
+
6    ''' else if (klucz < węzeł.klucz) '''then'''
        '''return''' Szukaj(węzeł.lewePoddrzewo, klucz)
+
7      '''return''' Szukaj(węzeł.lewePoddrzewo, klucz)
    ''' else if (klucz > węzeł.klucz) '''then'''
+
8    ''' else if (klucz > węzeł.klucz) '''then'''
        '''return''' Szukaj(węzeł.prawPoddrzewo, klucz)
+
9        '''return''' Szukaj(węzeł.prawPoddrzewo, klucz)
  '''end''';
+
10  '''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ąc 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)
    '''if''' (klucz < węzeł.klucz) '''then'''
+
2    '''if''' (klucz < węzeł.klucz) '''then'''
        '''if''' węzeł.lewePoddrzewo=nil '''then'''
+
3      '''if''' węzeł.lewePoddrzewo=nil '''then'''
            utwórz nowy węzeł z wartością ''klucz''
+
4        utwórz nowy węzeł z wartością ''klucz''
            wskaźnik do nowego węzła zapisujemy w węzeł.lewePoddrzewo
+
5        wskaźnik do nowego węzła zapisujemy w węzeł.lewePoddrzewo
        '''else'''
+
6      '''else'''
            Dodaj(węzeł.lewePoddrzewo, klucz)
+
7        Dodaj(węzeł.lewePoddrzewo, klucz)
    '''else if (klucz >= węzeł.klucz) '''then'''
+
8    '''else if (klucz >= węzeł.klucz) '''then'''
        '''if''' węzeł.prawePoddrzewo=nil '''then'''
+
9      '''if''' węzeł.prawePoddrzewo=nil '''then'''
            utwórz nowy węzeł z wartością ''klucz''
+
10      utwórz nowy węzeł z wartością ''klucz''
            wskaźnik do nowego węzła zapisujemy w węzeł.prawePoddrzewo
+
11      wskaźnik do nowego węzła zapisujemy w węzeł.prawePoddrzewo
        '''else'''
+
12    '''else'''
            Dodaj(węzeł.prawePoddrzewo, klucz)
+
13      Dodaj(węzeł.prawePoddrzewo, klucz)
  '''end''';
+
14 '''end''';
  
 
Możemy również usuwać wartości z drzewa, niestety ta operacja jest bardziej skomplikowana.
 
Możemy również usuwać wartości z drzewa, niestety ta operacja jest bardziej skomplikowana.
  
  '''procedure''' Usuń(węzeł, klucz)  
+
'''procedure''' Usuń(węzeł, klucz)  
    '''if''' (klucz < węzeł.klucz) '''then'''
+
2    '''if''' (klucz < węzeł.klucz) '''then'''
        Usuń(węzeł.lewePoddrzewo, klucz)
+
3      Usuń(węzeł.lewePoddrzewo, klucz)
    '''else if (klucz > węzeł.klucz) '''then'''
+
4    '''else if (klucz > węzeł.klucz) '''then'''
        Usuń(węzeł.prawePoddrzewo, klucz)     
+
5      Usuń(węzeł.prawePoddrzewo, klucz)     
    '''else''' '''begin''' { klucz = węzeł.klucz
+
6    '''else''' '''begin''' { klucz = węzeł.klucz
        '''if''' ''węzeł'' jest liściem, '''then'''
+
7      '''if''' ''węzeł'' jest liściem, '''then'''
          { usuń '''węzeł''' z drzewa }
+
8        { usuń '''węzeł''' z drzewa }
          UsunProstyPrzypadek(węzeł)
+
9        UsunProstyPrzypadek(węzeł)
        '''else'''
+
10    '''else'''
          '''if''' węzeł.lewePoddrzewo <> nil '''then'''
+
11      '''if''' węzeł.lewePoddrzewo <> nil '''then'''
            niech ''x'' oznacza skrajnie prawy węzeł w poddrzewie węzeł.lewePoddrzewo
+
12        niech ''x'' oznacza skrajnie prawy węzeł w poddrzewie węzeł.lewePoddrzewo
            wezel.klucz:=x.klucz;
+
13        wezel.klucz:=x.klucz;
            UsunProstyPrzypadek(x);
+
14        UsunProstyPrzypadek(x);
          '''else'''
+
15      '''else'''
            analogiczne postępowanie dla węzeł.prawPoddrzewo  
+
16        analogiczne postępowanie dla węzeł.prawPoddrzewo  
            (jednak poszukujemy węzła na skrajnie lewej ścieżce)
+
17        (jednak poszukujemy węzła na skrajnie lewej ścieżce)
    '''end'''
+
18 '''end'''
  
 
Procedura ''UsunProstyPrzypadek'' oznacza usuwanie z drzewa węzła, który
 
Procedura ''UsunProstyPrzypadek'' oznacza usuwanie z drzewa węzła, który
 
ma co najwyżej jednego syna.
 
ma co najwyżej jednego syna.
  
  '''procedure''' UsunProstyPrzypadek(węzeł)
+
1 '''procedure''' UsunProstyPrzypadek(węzeł)
    poddrzewo:=nil;
+
2 '''begin'''
    ojciec:=węzeł.ojciec;
+
3    poddrzewo:=nil;
    '''if''' (węzeł.lewePoddrzewo) '''then'''
+
4    ojciec:=węzeł.ojciec;
      poddrzewo:=węzeł.lewePoddrzewo;
+
5    '''if''' (węzeł.lewePoddrzewo) '''then'''
    '''else'''     
+
6      poddrzewo:=węzeł.lewePoddrzewo;
      poddrzewo:=węzeł.prawePoddrzewo;     
+
7    '''else'''     
 +
8      poddrzewo:=węzeł.prawePoddrzewo;     
 
      
 
      
    '''if''' (ojciec=nil) '''then'''
+
9    '''if''' (ojciec=nil) '''then'''
      korzen:=poddrzewo;
+
10    korzen:=poddrzewo;
    '''else''' '''if''' ojciec.lewePoddrzewo=węzeł '''then''' { węzeł jest lewym synem }
+
11  '''else''' '''if''' ojciec.lewePoddrzewo=węzeł '''then''' { węzeł jest lewym synem }
      ojciec.lewePoddrzewo:=poddrzewo;
+
12    ojciec.lewePoddrzewo:=poddrzewo;
    '''else''' { węzeł jest prawym synem }
+
13  '''else''' { węzeł jest prawym synem }
      ojciec.prawePoddrzewo:=poddrzewo;
+
14    ojciec.prawePoddrzewo:=poddrzewo;
  
 
Wszystkie podane operacje mają pesymistyczny koszt <math>O(h)</math> gdzie <math>h</math>  
 
Wszystkie podane operacje mają pesymistyczny koszt <math>O(h)</math> gdzie <math>h</math>  
Linia 185: Linia 186:
 
Początkowo tablica <math>A</math> wypełniona jest wartościami '''nil'''.
 
Początkowo tablica <math>A</math> wypełniona jest wartościami '''nil'''.
  
  '''procedure''' Inicjalizacja;
+
  1 '''procedure''' Inicjalizacja;
  '''begin'''
+
  2 '''begin'''
  '''for''' i:=0 '''to''' m-1 '''do''' A[i]:='''nil''';
+
'''for''' i:=0 '''to''' m-1 '''do''' A[i]:='''nil''';
  '''end''';
+
  4 '''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>
  
  '''procedure''' Dodaj(x);
+
  1 '''procedure''' Dodaj(x);
  '''begin'''
+
  2 '''begin'''
  dodaj element <math>x</math> na początek listy <math>A[h(x)]</math>
+
dodaj element <math>x</math> na początek listy <math>A[h(x)]</math>
  '''end''';
+
  4 '''end''';
  
 
Sprawdzenie, czy element <math>x</math> jest w zbiorze, 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);
+
  1 '''function''' Szukaj(x);
  '''begin'''
+
  2 '''begin'''
  l:=A[h(x)];
+
l:=A[h(x)];
  '''while''' (l!='''nil''') '''do''' '''begin'''
+
'''while''' (l!='''nil''') '''do''' '''begin'''
      '''if''' (l.wartość=x) '''then''' '''return''' element istnieje
+
5      '''if''' (l.wartość=x) '''then''' '''return''' element istnieje
      l:=l.nast;
+
6      l:=l.nast;
  '''end''';
+
'''end''';
  '''return''' brak elementu
+
'''return''' brak elementu
  '''end''';
+
  9 '''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);
+
1 '''procedure''' Usuń(x);
  '''begin'''
+
2 '''begin'''
  l:=A[h(x)];p:=nil;
+
l:=A[h(x)];p:=nil;
  '''while''' (l!='''nil''') '''do''' '''begin'''
+
'''while''' (l!='''nil''') '''do''' '''begin'''
      '''if''' (l.wartość=x) '''then''' '''begin'''
+
5    '''if''' (l.wartość=x) '''then''' '''begin'''
        { usuwamy element l z listy A[h(x)] }
+
6      { usuwamy element l z listy A[h(x)] }
        '''if''' p='''nil''' '''then''' A[h(x)]:=l.nast;
+
7      '''if''' p='''nil''' '''then''' A[h(x)]:=l.nast;
        '''else''' p.nast:=l.nast;
+
8      '''else''' p.nast:=l.nast;
        '''return''';
+
9      '''return''';
      '''end'''
+
10    '''end'''
      p:=l; l:=l.nast;
+
11    p:=l; l:=l.nast;
  '''end''';
+
12  '''end''';
  '''end''';
+
  13 '''end''';
  
 
=== Wybór funkcji haszujących ===
 
=== Wybór funkcji haszujących ===
Linia 259: Linia 260:
 
przez funkcję <math>H(x,k)</math>.
 
przez funkcję <math>H(x,k)</math>.
  
  '''function''' Szukaj(x);
+
  1 '''function''' Szukaj(x);
  '''begin'''
+
  2 '''begin'''
  k:=0;
+
k:=0;
  '''while''' (A[H(x,k)!='''nil''') '''do''' '''begin'''
+
'''while''' (A[H(x,k)!='''nil''') '''do''' '''begin'''
      '''if''' (A[H(x,k)].wartość=x) '''then''' '''return''' element istnieje
+
5      '''if''' (A[H(x,k)].wartość=x) '''then''' '''return''' element istnieje
      k:=k+1;
+
6      k:=k+1;
  '''end''';
+
'''end''';
  '''return''' brak elementu
+
'''return''' brak elementu
  '''end''';
+
  9 '''end''';
  
 
Wstawianie elementów możemy wykonać przez analogiczne modyfikacje; usuwanie jest zwykle znacznie trudniejsze.
 
Wstawianie elementów możemy wykonać przez analogiczne modyfikacje; usuwanie jest zwykle znacznie trudniejsze.
Linia 284: Linia 285:
 
na wartość 1.
 
na wartość 1.
  
  '''procedure''' Dodaj(x);
+
  1 '''procedure''' Dodaj(x);
  '''begin'''
+
  2 '''begin'''
  '''for''' i:=1 '''to''' k '''do''' A[<math>h_i(x)</math>]:=1;
+
'''for''' i:=1 '''to''' k '''do''' A[<math>h_i(x)</math>]:=1;
  '''end''';
+
  4 '''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>.
Linia 295: Linia 296:
 
to taka struktura będzie dobrze sprawować się w praktyce.
 
to taka struktura będzie dobrze sprawować się w praktyce.
  
  '''function''' Szukaj(x);
+
  1 '''function''' Szukaj(x);
  '''begin'''
+
  2 '''begin'''
  '''for''' i:=1 '''to''' k '''do'''  
+
'''for''' i:=1 '''to''' k '''do'''  
    '''if''' A[<math>h_i(x)</math>]=0 '''then''' '''return''' brak elementu
+
4    '''if''' A[<math>h_i(x)</math>]=0 '''then''' '''return''' brak elementu
  '''return''' element istnieje
+
'''return''' element istnieje
  '''end''';
+
  6 '''end''';
  
 
==Literatura==
 
==Literatura==

Wersja z 13:35, 26 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.

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

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.
Wyszukiwanie.1.png

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

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;

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

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 .

Dodanie elementu x sprowadza się do ustawienia wszystkich bitów dla 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 . 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[]=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