Przeszukiwanie liniowe,
binarne,
haszowanie
Cel ćwiczenia
Celem ćwiczenia jest zapoznanie się z podstawowymi problemami dotyczącymi algorytmów przeszukiwań.
1
Przeszukiwanie liniowe
Przeszukiwanie liniowe jest jedną z najprostrzych metod wyszukiwania. Polega ona na przeglą-
daniu tablicy element po elemencie i porównywaniu za każdym razem wartości danego elementu z poszukiwanym kluczem. Poszukiwanie zostaje zakończone jeżeli zostanie znaleziony poszukiwany klucz lub osiągnie się koniec tablicy.
Przeszukiwanie liniowe ze względu na sposób działania nadaje się do wyszukiwania w tablic uporządkowanych jak i nieuporządkowanych.
2
Wyszukiwanie binarne
Wyszukiwanie binarne można zastosować, kiedy przeszukiwana tablica jest uporządkowana. Zamiast zaczynać od pierwszego elementu i przeglądać tablicę aż do znalezienia klucza lub dotarcia do jej końca, zaczyna się do środkowego elementu tablicy i porównuje się z szukanym kluczem.
Jeżeli jest mu równy, to przeszukiwanie zostaje zakończone. Jeżeli jest on większy niż klucz, to odrzuca się dolną połowę tablicy i ogranicza się poszukiwanie do elementów powyżej środ-ka. Jeżeli natomiast środkowy element jest mniejszy od klucza, to odrzuca się górną połowę i kontynuuje się poszukiwanie jedynie w dolnej części tablicy.
Przykład:
Znaleźć wartość 65 w uporządkowanej tablicy liczb całkowitych
1
2
3
4
5
6
7
8
9
2
10
15
22
43
47
50
65
80
Ponieważ wartość 43 jest mniejsza od 65 to odrzucana jest początkowa część tablicy 5
6
7
8
9
43
47
50
65
80
Ponieważ wartość 50 jest mniejsza od 65 to odrzucana jest początkowa część tablicy.
7
8
9
50
65
80
Ponieważ 65 = 65, więc poszukiwana wartość została znaleziona i mieści się w 8 elemencie
tablicy.
3
Transformacja kluczowa
Transformacja kluczowa należy do działu algorytmów przeszukiwań. Jest ona stosowana tam,
gdzie maksymalna ilość elementów należącej do pewnej dziedziny (w sensie matematycznym) R
jest z góry znana (Emax), natomiast wszystkich możliwych elementów tej dziedziny mogłoby być potencjalnie bardzo dużo (C). Tak dużo, że o ile przydział pamięci na tablicę o rozmiarze (Emax) jest praktycznie możliwa, o tyle przydział tablicy dla wszystkich potencjalnych C elementów dziedziny R byłby fizycznie niewykonalny.
Idea transformacji kluczowej polega na próbie odnalezienia takiej funkcji H, która otrzymując w parametrze pewien zbiór danych, podałaby nam indeks w tablicy T . Inaczej rzecz ujmując: transformacja kluczowa polega na odwzorowaniu dane −→ adres komórki w pamięci.
Naturalną konsekwencją nowego sposobu zapamiętywania danych jest maksymalne uproszczenie
procesu poszukiwań. Poszukując elementu x charakteryzowanego przez pewien klucz ν możemy
się posłużyć funkcją H. Obliczenie H(ν) powinno zwrócić nam pewien adres pamięci, pod którym należy sparwdzić istnienie x.
Mamy tu do czynienia z zupełnym porzuceniem jakiegokolwiek procesu przeszukiwania zbioru
danych: znając funkcję H, automatycznie możemy określić położenie dowolnego elementu w
pamięci — wiemy również od razu, gdzie poprowadzić ewentualne poszukiwania.
Metoda ta ma dwa istotne ograniczenia:
• ograniczenie pamięci,
• trudności w odnalezieniu dobrej funkcji H.
3.1
Poszukiwanie funkcji H
Potencjalnych funkcji, które na podstawie wartości danego klucza ν zwrócą pewien adres adr, jest bardzo dużo. Parametry, które mają wpływ na stopień skomplikowania funkcji H to: długość tablicy, w której zamierzamy składować rekordy danych, oraz wartość klucza ν.
Funkcja ta powinna posiadać dwie własności:
• powinna być łatwo obliczalna,
• różnym wartościom klucza ν powinny odpowiadać odmienne adresy pamięci T , tak aby
nie powodować kolizji dostępu.
3.2
Znane funkcje H
W zaprezentowanych przykładach będziemy zakładać, że „klucze” są ciągami znaków, które
można łączyć ze sobą i dość dowolnie interpretować jako liczby całkowite.
Każdy znak alfabetu będziemy kodować w naszych przykładach przy pomocy pięciu bitów:
A=00001
B=00010
C=00011
D=00100
E=00101
F=00110
G=00111
H=01000
I=01001
J=01010
K=01011
L=01100
M=01101
N=01110
O=01111
P=10000
Q=10001
R=10010
S=10011
T=10100
U=10101
V=10110
W=10111
X=11000
Y=11001
Z=11010
Tablica 1. Kodowanie liter przy pomocy 5 bitów.
• Kodowanie jest wykonane w celu zmiany wartości klucza na liczbę; sam kod jest nieistotny, ważne jest, aby wynik był liczbą, którą można później stosować w obliczeniach.
• Naszym celem jest możliwie jak najbardziej losowe „rozsianie” rekordów po tablicy wiel-
kości M . Cały problem polega na tym, że nie jest możliwe uzyskanie losowego rozrzutu
elementów, dysponując danymi wejściowymi, które z założenia nie są losowe. Musimy za-
tem ową losowość w jakiś sposób zasymulować.
Istnieje grupa prostych funkcji arytmetycznych (modulo, mnożenie, dzielenie), które dość dobrze nadają się do tego celu.
3.2.1
Suma modulo 2
H(ν1 ν2 . . . νn) = ν1 ⊕ ν2 ⊕ · · · ⊕ νn
⊕ — suma modulo 2.
Przykład:
Dla Rmax = 37, H(KOT) = (010110111110100)2 daje to
(01011)2 ⊕ (01111)2 ⊕ (10100)2 = (10000)2 = (16)10
Zalety:
• funkcja H łatwa do obliczenia;
• suma modulo 2, w przeciwieństwie do iloczynu i sumy logicznej, nie powiększa (jak toczyni suma logiczna) lub pomniejsza (jak iloczyn) swoich argumentów.
Wady:
• permutacja tych samych liter daje w efekcie ten sam wynik — można temu zaradzić po-
przez systematyczne przesuwanie cykliczne reprezentacji bitowej: pierwszy znak o jeden
bit w prawo, drugi o dwa bity w prawo etc.
Przykład:
• bez przsuwania H(KTO) = (16)10, jednocześnie H(TOK) = (16)10.
• z przesuwaniem H(KTO) = (10101)2 ⊕ (00101)2 ⊕ (11101)2 = (01101)2 = (13)10
natomiast H(TOK) = (01010)2 ⊕ (11011)2 ⊕ (01101)2 = (11100)2 = (28)10
3.2.2
Dzielenie modulo Rmax
H(ν) = ν mod Rmax
mod — dzielenie modulo
Przykład:
dla Rmax = 37
H(KOT) = (010110111110100)2 mod (37)10 = (11764)10 = 35
Zalety:
• funkcja H łatwa do obliczenia
Wady:
• otrzymana wartość zależy bardziej od Rmax, niż od klucza. Gdy Rmax jest parzyste, wszystkie otrzymane indeksy danych o kluczach parzystych będą parzyste, ponadto dla pewnych
dzielników wiele danyc otrzyma te same indeksy. Można temu zaradzić poprzez wybór
Rmax jako liczby pierwszej, ale tu znowu często mamy do czynienia z akumulacją elemen-
tów w pewnym obszarze tablicy.
• w przypadku dużych liczb binarnych nie mieszczących się w reprezentacji wewnętrznej
komputera, obliczanie modul już nie jest możliwe przez zwykłe dzielenie arytmetyczne.
Mnożenie Emax
H(ν) = b((ν · Θ)%1) · Emaxc,
gdzie 0 < Θ < 1
b. . .c — pobranie części całkowitej
Powyższą formułę należy odczytać następująco: klucz jest mnożony przez pewną liczbę Θ z prze-działu (0, 1). Z wyniku bierzemy część ułamkową, mnożymy przez Emax i ze wszystkiego liczymy część całkowitą. Istnieją dwie wartości parametru Θ, które „rozrzucają” klucze w miarę równomiernie po tablicy:
1 √
1
3
1 √
Θ =
5 −
Θ =
−
5
2
2
2
2
Przykład
Dla Θ = 0.61800339887, Rmax = 30 i klucza ν = KNT = 1732, otrzymamy H(KNT) = 23.
3.3
Obsługa konfliktów
3.3.1
Listy
W przypadku stwierdzenia kolizji dwóch odmiennych rekordów, którym funkcja H przydzieli-
ła ten sam indeks w tablicy T sytuacji tej możemy zaradzić poprzez pewną zamianę w samej
filozofii transformacji kluczowej. Jeżeli w tablicy T zamiast rekordów będziemy zapamiętywać głowy list do elementów charakteryzujących się tym samym kluczem, wówczas problem zostanie rozwiązany. Jeżeli wstawiając element x do tablicy pod indeksem m, stwierdzimy, że jest już tam jakiś element, wystarczy doczepić x na koniec listy, której głowa jest zapamiętana w T [m].
Analogicznie działa poszukiwanie: szukany element x i H(x) zwraca nam pewien indeks m. W
przypadku, gdy T [m] zawiera N U LL, możemy być pewni, że szukanego elementu nie odnaleźli-
śmy - w odwrotnej sytuacji, aby się ostatecznie upewnić, wystarczy przeszukać listę T [m].
Opisany powyżej sposób jest zilustrowany na rys 3.1.
T
0
•
−→
G
1
•
−→
A
−→
F
2
•
−→
C
3
•
−→
B
−→
F
4
NULL
5
•
−→
D
6
NULL
Rysunek 3.1. Użycie list do obsługi konfliktów dostępu
Zaprezentowana idea transformacji kluczowej zawiera zachęcające obietnice porzucenia wszel-kich drzew, list i innych skomplikowanych w obsłudze struktur danych na rzecz zwykłego od-wzorowania dane ←→ adres. Podczas dokładniejszej analizy napotkaliśmy na mały problem i
powróciliśmy do starych dobrych list. Z tych właśnie przyczyn rozwiązanie to można uznać za nieco sztuczne, choć parametry ”czasowe” tej metody są bardzo korzystne.
3.3.2
Tablice
Idea tej metody polegałaby na podziale tablicy T na dwie części: strefę podstawową i strefę przepełnienia. Do strefy przepełnienia elementy trafiałyby w momencie braku miejsca w części podstawowej. Strefa ta wypełniana byłaby liniowo wraz z napływem nowych elementów „koli-zyjnych”. Efekt wypełnienia tablicy przedstawiony jest na rysunku 3.2.
0
1
2
3
4
5
6
7
8
9
G
A
C
B
D
Ei Fi
-
STREFA PODSTAWOWA
Rysunek 3.2. Podział tablicy do obsługi konfliktów dostępu
Rekord E i F został zapamiętany w momencie stwierdzenia przepełnienia. Sugeruje to, że gdzieś musi istnieć zmienna zapamiętująca ostatnią wolną pozycję strefy przepełnienia. W przypadku zapełnienia strefy przepełnienia nie jest oczywiste co należy zrobić. Z tego właśnie powodu użycie tej metody powinno być poprzedzone szczególnie starannym obliczeniem rozmiarów tablicy.
3.3.3
Próbowanie liniowe
Jak zauważyliśmy wcześniej, konflikty dostępu są w metodzie transformacji kluczowej nieuchron-ne. Nie istnieje bowiem idealna funkcja H, która rozmieściłaby równomiernie wszystkie Rmax elementów po całej tablicy T .
1)
0
1
2
3
4
5
6
7
A
C
B
D
G
2)
0
1
2
3
4
5
6
7
A
C
B
E
D
G
3)
0
1
2
3
4
5
6
7
A
C
B
E
D
F
G
4)
0
1
2
3
4
5
6
7
H
A
C
B
E
D
F
G
Rysunek 3.3. Obsługa konfliktów dostępu przy próbkowaniu liniowym:
1) bez konfliktu, 2) konflikt B z E, 3) konflikt A z F, 4) konflikt G z H
Idea próbkowania liniowego jest następująca: W momencie zapisu nowego rekordu do tablicy, w przypadku stwierdzenia konfliktu możemy spróbować zapisać element na pierwsze wolne kolejne miejsce. Metoda ta została przedstawiona na rysunku 3.3.
Ciekawe jest teoretyczne wyliczanie średniej ilości prób potrzebnej do odnalezienia danej x. W
przypadku poszukiwania zakończonego sukcesem średniej ilości prób wynosi około:
1
1
1
+
·
,
2
2
1 − α
gdzie α jest współczynnikiem zapełnienia T . Analogicznie wynik dla przeszukiwania zakończonego niepowodzeniem wynosi około:
1
1
1
+
·
.
2
2
(1 − α)2
Przykładowo dla tablicy zapełnionej w 2/3 swojej pojemności (α = 2/3) liczby te wyniosą
odpowiednio 2 i 5.
W praktyce należy unikać szczelnego zapełnienia tablicy T , gdyż powyższe liczby stają się bardzo duże. Powyższy wzór został wyprowadzony przy założeniu funkcji H, która rozsiewa równomiernie elementy po dużej tablicy T . Te zastrzeżenia są bardzo istotne ponieważ podane wyżej rezultaty mają charakter statystyczny.
3.3.4
Podwójne kluczowanie
W metodzie próbowania liniowego jesteśmy narażeni na liniowe grupowanie elementów, co zwiększa czas poszukiwania wolnego miejsca dla nowego elementu tablicy T . Jednocześnie ziwększa się czas przeszukiwania tablicy T . Na szczęśćie istnieje łatwy sposób uniknięcia liniowego gru-powania elementów tj. podwójne kluczowanie. W momencie napotkania kolizji następuje próba
”rozrzucenia” elementów przy pomocy drugiej, pomocniczej funkcji H.
Dobór funkcji H2 ma duży wpływ na jakość wstawiania i poszukiwania. Przede wszystkim funkcja H2 powinna być różna od H1 i musi być funkcją prostą, która nie spowolni procesu wstawiania i poszukiwania. Przykładem takiej prostej i jednocześnie skutecznej funkcji jest funkcja w postaci: H2(k) = 8 − (k mod 8).
Metoda podwójnego kluczowania jest interesująca ze względu na zysk w szybkości poszukiwania danych. Średnia ilość prób zakończona sukcesem wynosi około:
ln
1
1−α
,
α
gdzie α jest współczynnikiem zapełnienia tablicy T . Analogicznie wynik dla poszukiwania za-kończonego niepowodzeniem wynosi około:
1
.
1 − α
Zastosowanie transformacji kluczowej
Zastosowania transformacji kluczowej mogą być dość nieoczekiwane: dane nie muszą znajdować się w pamięci głównej; w przypadku programu baz danych można w łatwy sposób użyć H -
kodu do sprawnego odszukiwania danych. Konstruując duże kompilatory/linkery, możliwe jest wykorzystanie metod transformacji kluczowej do odszukiwania skomplikowanych modułów w
dużych plikach bibliotecznych.
4
Ćwiczenia do wykonania
1. Dla każdego typu przeszukiwania utworzyć schemat blokowy i jego implementację w języku Pascal. W przypadku algorytmu haszowania należy uwzględnić obsługę konfliktów dostępu.
2. Dokonać analizy zastosowań powyższych algorytmów.
Bibliografia
[1] Harel Dawid, Rzecz o istocie informatyki. Algorytmika. WNT 1992
[2] Adam Drozdek, Struktury danych w języku C. WNT 1996