Algorytmy i struktury danych

wykład VII

„Tablice z haszowaniem, statystyki pozycyjne”

dr in . Andrzej Zalewski

www:

www.ia.pw.edu.pl/~azalews2

e-mail:

[e-mail]

konsultacje:

roda godz. 12:15 – 13:00.

(c) Andrzej Zalewski (IAiIS PW)

Plan wykładu

♦

Tablice z haszowaniem

♦

Statystyki pozycyjne

Tablice z mieszaniem

(haszowanie, pami

rozproszona)

(c) Andrzej Zalewski (IAiIS PW)

Haszowanie – pomysł i problem

♦

Zamiast porównywa wyszukiwany klucz, z kluczami w

tablicy /drzewie (itp.)/ znajdujemy pozycj w tablicy na

podstawie samej warto ci klucza, tzn.

– dana jest funkcja H(k): K –> I, gdzie:

• K – zbiór kluczy,
• I – zbiór indeksów

– zauwa my, e zwykle: |K| >> |I|

♦

szansa: wyszukiwanie/wstawianie/usuwanie w czasie

stałym (!)

– je li wyznaczenie H(k) nie jest „czasochłonne” obliczeniowo

♦

K – zwykle zbiór liczb naturalnych

(c) Andrzej Zalewski (IAiIS PW)

Haszowanie – pomysł c.d.

♦

Problem: kolizja

– prawdopodobie stwo, e H(k)=H(k’), dla k

≠ k’

/tzw. kolizja/ jest znacz ce

– paradoks dnia urodzin – prawd. braku kolizji

daty urodzin |I|=365, dla liczby ludzi |K|>= 23

jest wi ksze ni 50%!

(c) Andrzej Zalewski (IAiIS PW)

Funkcje haszuj ce – wymagane wła ciwo ci

♦

Równomierne rozrzucanie:

– dla losowo wybranego klucza ka da pozycja w indeksie

jest jednakowo prawdopodobna niezale nie od

odwzorowania innych kluczy

♦

„Całkowite wypełnianie” zbioru I

♦

W ogólno ci dobór funkcji haszuj cej zale y od

wła ciwo ci zbioru kluczy

– np. dla k

∈<0,1), H(k)= k m , gdzie, |I| = m, haszuje

równomiernie

♦

Typowo: |I| = N

(c) Andrzej Zalewski (IAiIS PW)

Haszowanie

♦

Dla kluczy nie całkowitoliczbowych –

przekształcamy klucz w liczb naturaln

– dla ci gów znaków: H(k) = (h

1

(c

1

) + h

2

(c

2

) +

...) mod m, h

1

, h

2

... – pewna funkcja mieszaj ca

– dla ci gów składaj cych si z kilku liczb

sklejamy poszczególne fragmenty klucza

korzystaj c z operacji mod w lub xor

– traktujemy tekst lub jego fragment jako liczb

w okre lonym systemie pozycyjnym – np. ab –

w systemie 24-kowym...

(c) Andrzej Zalewski (IAiIS PW)

Funkcje mieszaj ce – haszowanie modularne

♦

H(k) = k mod m /k – klucz

całkowitoliczbowy/

– problem dobór m:

• dobre m – liczba pierwsza,
• m parzyste – zły wybór – miesza po połowie

przestrzeni 0...m (k – parzyste => H(k) – parzyste, k

– nie parzyste => H(k) nieparzyste)

• m – 2

k

– obci cie klucza do k najmniej znacz cych

bitów klucza

(c) Andrzej Zalewski (IAiIS PW)

Haszowanie przez mno enie

♦

H(k) = m (k A mod 1)

• x mod 1 – ułamkowa cz

x

• A

∈(0,1),

♦

m – mało istotne – działa dla dowolnego m,

♦

(c) Andrzej Zalewski (IAiIS PW)

Haszowanie uniwersalne

♦

Rodzina uniwersalna funkcji haszuj cych

– rodzina R = { H: K->I} , e

• liczba ró nych funkcji H w R odwzorowuj cych

ró ne klucze k i l w ten sam indeks H(k)=H(l) jest

nie wi ksza ni |R|/m, m=|I|

♦

Haszowanie uniwersalne

– losujemy funkcj haszuj c z rodziny

uniwersalnych funkcji haszuj cych

(c) Andrzej Zalewski (IAiIS PW)

Rodzina uniwersalna funkcji haszuj cych

♦

niech p – liczba pierwsza wi ksza od

najwi kszego „haszowanego” klucza

♦

niech a

∈{0,1, … p – 1} , b∈{1, 2, …, p –

1}

♦

h

a,b

(k)= ((a*k+b) mod p) mod m, p>m

♦

ciekawe: m dowolna liczba, nie koniecznie

pierwsza (m – liczba indeksów w tablicy)

(c) Andrzej Zalewski (IAiIS PW)

Rodzina uniwersalna funkcji haszuj cych

♦

Rodzina funkcji H

a,b

(k) jest rodzin uniweraln

funkcji haszuj cych

♦

Wyja nienie (szkic dowodu):

– q=(a*k

1

+ b) mod p i r=(a*k

2

+ b) mod p s ró ne dla

k

1

<>k

2

/sprawdzi q – r/

– prawdopodobie stwo kolizji – to prawdopod., e q mod

m = r mod m (q i r kongruentne)

– dla danego q z pozostałych p – 1 liczba mo liwych

warto ci prawd., e q i r kongruentne wynosi: p/m - 1

<= (p -1)/m

– co daje prawdopodobie stwo kolizji wynosz ce 1/m.

– dla |R| funkcji haszuj cych dwa ró ne klucze w to samo

miejsce wynosi zatem |R|/m.

(c) Andrzej Zalewski (IAiIS PW)

Haszowanie –

rozwi zywanie kolizji

♦

metoda ła cuchowa

– tablica jest de facto tablic wska ników – normalnie

wskazuje co zero lub jeden element, w przypadku

kolizji dodajemy nast pne elementy

♦

adresowanie otwarte – stosujemy funkcj H(k, i),

gdzie i – numer próby wyszukania/wstawienia

– liniowe: próbkujemy kolejno: H(k), H(k) –1, H(k) – 2

itd. je li dotrzemy do pustego miejsca nie znalazłszy

wcze niej klucza – klucza nie ma w tablicy – mo emy

wstawi nowy klucz lub stwierdzi brak klucza

szukanego – H(k, i) = (H’(k) + i) mod m

– haszowanie kwadratowe H(k, i)=(H’(k)+c

1

i+c

2

i

2

) mod

m, i – numer próby, c

1

, c

2

– stałe całkowite;

(c) Andrzej Zalewski (IAiIS PW)

Haszowanie otwarte, podwójne

♦

Z podwójnym haszowaniem

– H(k, i) = (h

1

(k)+ i*h

2

(k)) mod m; i – numer

próby

– h

1

– modularna funkcja haszuj ca

– h

2

– dobrana tak, by przegl da cał tablic

• m = 2

n

, h

2

– daje tylko warto ci nieparzyste

• m – liczba pierwsza, , h

2

– liczby dodatnie, mniejsze

ni m – np. 1 + (k mod m’), np.. m’=m-1

(c) Andrzej Zalewski (IAiIS PW)

Haszowanie - efektywno

♦

W haszowaniu met. ła cuchow

– czas prop. 1 + n / m /wypełnienie tablicy/

♦

W adresowaniu otwartym:

– 1/(n/m) ln (1/(1-n/m)), n/m<1
– konkretnie: n/m=0,5 – rednia liczba porówna

< 1,385, n/m=0,9 – 2,559 /Cormen/

♦

Wniosek:

– haszowanie dla n/m<100% działa ca. w czasie

liniowym

(c) Andrzej Zalewski (IAiIS PW)

Haszowanie doskonałe

♦

Cel:

– zdefiniowa sposób wyszukiwania kluczy w czasie

stałym w statycznym zbiorze danych.

♦

Def. Haszowanie jest doskonałe, je li w

pesymistycznym przypadku wymaga stałej liczby

odwoła do tablicy

♦

Rozwi zanie:

– analog do rozwi zywania kolizji ła cuchowo:

• zamiast tworzy list elementów odwzorowywanych na dany

indeks i tworzymy dodatkowe tablice z haszowaniem,

starannie dobieraj c funkcje H

j

(c) Andrzej Zalewski (IAiIS PW)

Haszowanie doskonałe – konstrukcja rozwi zania

♦

I poziom – haszowanie modularne

♦

II poziom – n

j

– liczba kluczy k, dla których

H(k)=i;

– rozwi zanie:m

j

= n

i

2

, stos. f-cj H

p, mi

, p – l-ba pierwsza

wi ksza od ka dej warto ci klucza

• mo na pokaza , e wtedy prawd. kolizji jest mniejsze ni 0,5,

je li posługujemy si r.u.f.h. (prawd. kolizji mi dzy k i l - 1/n,

ró nych k, l jest newton(n

i

, 2))

– konkluzja: znalezienie funkcji haszuj cej bez kolizji

wymaga „kilku prób”

– ile powinno wynosi m (H(k)=k mod m) na pierwszym

poziomie haszowania

(c) Andrzej Zalewski (IAiIS PW)

Haszowanie doskonałe

♦

Co z pami ci ?

– okazuje si , e je li m=n, to wart. oczekiwana

sumy długo ci tablic drugiego poziomu nie jest

wi ksza ni 2n

– prawdopodobie stwo, e tablice 2 poziomu

zajm wi cej ni 4n<1/2

Statystyki pozycyjne –

problem wyboru

(c) Andrzej Zalewski (IAiIS PW)

Stat. pozycyjne – definicja zadania

♦

Dany jest n-elementowy zbiór. Znale i-ty

najmniejszy element

– Przykłady:

• min – 1’szy
• max – n’ty
• rodkowy – mediana element (n+1)/2 ‘y lub

(n+1)/2 ‘y

♦

Rozwi zanie intuicyjne:

– sortujemy zbiór, sprawdzenie statystyki

pozycyjnej (dowolnej!) w czasie stałym

(c) Andrzej Zalewski (IAiIS PW)

Rozwi zanie efektywne

♦

Modyfikujemy sort. szybkie

– proc. randomized-partition(A, p, r) mo na

nieco zmodyfikowa , tak by dzieliła tablic na

A[p…q-1], A[q+1…r], odp <= i > od el.

rozdziel i A[q] – element rozdzielaj cy.

♦

Tym samym mamy 3 przypadki:

– A[q] – jest szukan i-t statystyk
– i-ta statyst. jest w lewej podtablicy A[p…q-1]
– i-ta statyst. jest w prawej podtab. A[q+1…r]

(c) Andrzej Zalewski (IAiIS PW)

Algorytm

♦

rand-select(A, p, r, i)

– if p=r then return A[p] //znaleziono
– q=rand.-partition(A, p, r)
– k=q – p + 1
– if i=k then return A[q] //znaleziono
– if i<k then rand-select(A, p, q – 1, i) /lewa podt.
– else rand-select(A, q+1, r, i – k)

(c) Andrzej Zalewski (IAiIS PW)

Algorytm - wła ciwo ci

♦

Co ciekawe – redni czas działania –

liniowy!

– intuicja: badamy tylko 1 z dwóch 2 drzew

rekurencji

– mo emy jednak przeci rekurencj ju na

samym pocz tku:

• przyp. szukan statystyk element rozdzielaj cy

(c) Andrzej Zalewski (IAiIS PW)

Wybór w pesym. czasie liniowym

♦

Szkic pomysłu

– wyznaczamy median median dla n/5 -

sortuj c elementy w podtablicach

– wyznaczamy median median dla kolejnych

grup 5 elementowych /mediany tworz kolejn

tablic , któr sortujemy i wyzn. med./

– dzielimy tablic wzgl. mediany median x, k-

indeks el. rozdziel.

– szukamy rekurencyjnie w lewej lub prawej

podtablicy lub ko czymy rekur. i=k

Appendix do wyszukiwania

wzg. klucza

(c) Andrzej Zalewski (IAiIS PW)

Wyszukiwanie metod Fibbon.

♦

Liczby Fibbonaciego F

0

=0, F

1

=1, F

2

=1, F

k+1

= F

k

+ F

k-1

, czyli F

3

=2, F

4

=3, F

5

=5, F

6

=8

♦

Drzewo Fibbonaciego w tablicy:

– rz du k=0, 1 po prostu 0
– rz du k>=2 korzeniem jest element F

k

, lewym

poddrzewem drzewo rz du F

k-1

, prawym

poddrzewem drzewo rz du F

k-2

z elementami o

indeksach powi kszonych o F

K

(c) Andrzej Zalewski (IAiIS PW)

Drzewo Fibbonacciego

♦

k=6, F

6

=8

8

5

11

3

7

10

12

12

6

9

11

5

6

7

2

1

2

0

1

4

3

4

8

9

10

(c) Andrzej Zalewski (IAiIS PW)

Poruszanie si po drzewie Fibb.

♦

Niech i=F

k

, p=F

k-1

, q=F

k-2

(i – na pocz tku

wskazuje korze )

♦

Przej cie do lewego poddrzewa

– i = i – q (F

k

=F

k-1

+F

k-2

= > F

k-1

=F

k

– F

k-2

)

– (p,q) = (q, p – q) (F

k-2

, F

k-3

)

♦

Przej cie do prawego poddrzewa

– i = i + q (zgodnie z definicj drzewa)
– p = p – q /F

k-3

/, q = q – p /F

k-4

= F

k-2

– F

k-3

/

(c) Andrzej Zalewski (IAiIS PW)

Wskazówki do konstrukcji algorytmu

♦

Od tego miejsca ju bardzo prosto:

– zatrzymujemy si znalazłszy wła ciwy klucz
– przy próbie przej cia w lewo zatrzymujemy si ,

gdy q=0 (osi gn li my F

0

)

– przy próbie przej cia w prawo zatrzymujemy

si , gdy p=1

Koniec