Giáo trình Cấu trúc dữ liệu và giải thuật - Phần 2: Các cấu trúc dữ liệu - Chương 12: Bảng và truy xuất thông tin
Chöông 12 – Baûng vaø truy xuaát thoâng tin
Chöông 12 – BAÛNG VAØ TRUY XUAÁT THOÂNG TIN
Chöông naøy tieáp tuïc nghieân cöùu veà caùch tìm kieám truy xuaát thoâng tin ñaõ ñeà
caäp ôû chöông 7, nhöng taäp trung vaøo caùc baûng thay vì caùc danh saùch. Chuùng ta
baét ñaàu töø caùc baûng hình chöõ nhaät thoâng thöôøng, sau ñoù laø caùc daïng baûng khaùc vaø
cuoái cuøng laø baûng baêm.
12.1. Daãn nhaäp: phaù vôõ raøo caûn lgn
Trong chöông 7 chuùng ta ñaõ thaáy raèng, baèng caùch so saùnh khoùa, trung bình
vieäc tìm kieám trong n phaàn töû khoâng theå coù ít hôn lg n laàn so saùnh. Nhöng keát
quaû naøy chæ noùi ñeán vieäc tìm kieám baèng caùch so saùnh caùc khoùa. Baèng moät vaøi
phöông phaùp khaùc, chuùng ta coù theå toå chöùc caùc döõ lieäu sao cho vò trí cuûa moät phaàn
töû coù theå ñöôïc xaùc ñònh nhanh hôn.
Thaät vaäy, chuùng ta thöôøng laøm theá. Neáu chuùng ta coù 500 phaàn töû khaùc nhau coù
caùc khoùa töø 0 ñeán 499, thì chuùng ta seõ khoâng bao giôø nghó ñeán vieäc tìm kieám tuaàn
töï hoaëc tìm kieám nhò phaân ñeå xaùc ñònh vò trí moät phaàn töû. Ñôn giaûn chuùng ta chæ
löu caùc phaàn töû naøy trong moät maûng kích thöôùc laø 500, vaø söû duïng chæ soá n ñeå xaùc
ñònh phaàn töû coù khoùa laø n baèng caùch tra cöùu bình thöôøng ñoái vôùi moät baûng.
Vieäc tra cöùu trong baûng cuõng nhö vieäc tìm kieám coù chung moät muïc ñích, ñoù laø
truy xuaát thoâng tin. Chuùng ta baét ñaàu töø moät khoùa vaø mong muoán tìm moät phaàn
töû chöùa khoùa naøy
Trong chöông naøy chuùng ta tìm hieåu caùch hieän thöïc vaø truy xuaát caùc baûng
trong vuøng nhôù lieân tuïc, baét ñaàu töø caùc baûng hình chöõ nhaät thoâng thöôøng, sau ñoù
ñeán caùc baûng coù moät soá vò trí haïn cheá nhö caùc baûng tam giaùc, baûng loài loõm. Sau
ñoù chuùng ta chuyeån sang caùc vaán ñeà mang tính toång quaùt hôn, vôùi muïc ñích tìm
hieåu caùch söû duïng caùc maûng truy xuaát vaø caùc baûng baêm ñeå truy xuaát thoâng tin.
Chuùng ta seõ thaáy raèng, tuyø theo hình daïng cuûa baûng, chuùng ta caàn coù moät soá
böôùc ñeå truy xuaát moät phaàn töû, tuy vaäy, thôøi gian caàn thieát vaãn laø 0(1) - coù nghóa
laø, thôøi gian coù giôùi haïn laø moät haèng soá vaø ñoäc laäp vôùi kích thöôùc cuûa baûng- vaø do
ñoù vieäc tra cöùu baûng coù theå ñaït hieäu quaû hôn nhieàu so vôùi baát kyø phöông phaùp tìm
kieám naøo.
Caùc phaàn töû cuûa caùc baûng maø chuùng ta xem xeùt ñöôïc ñaùnh chæ soá baèng moät
maûng caùc soá nguyeân, töông töï caùch ñaùnh chæ soá cuûa maûng. Chuùng ta seõ hieän thöïc
caùc baûng ñöôïc ñònh nghóa tröøu töôïng baèng caùc maûng. Ñeå phaân bieät giöõa khaùi nieäm
tröøu töôïng vaø caùc hieän thöïc cuûa noù, chuùng ta coù moät quy öôùc sau:
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
305
Chöông 12 – Baûng vaø truy xuaát thoâng tin
Chæ soá xaùc ñònh moät phaàn töû cuûa moät baûng ñònh nghóa tröøu töôïng ñöôïc bao bôûi
caëp daáu ngoaëc ñôn, coøn chæ soá cuûa moät phaàn töû trong maûng ñöôïc bao bôûi caëp daáu
ngoaëc vuoâng.
Ví duï, T(1,2,3) laø phaàn töû cuûa baûng T ñöôïc ñaùnh chæ soá bôûi daõy soá 1, 2, 3, vaø
A[1][2][3] töông öùng phaàn töû vôùi chæ soá trong maûng A cuûa C++.
12.2. Caùc baûng chöõ nhaät
Do taàm quan troïng cuûa caùc baûng chöõ nhaät, haàu heát caùc ngoân ngöõ laäp trình caáp
cao ñeàu cung caáp maûng hai chieàu ñeå chöùa vaø truy xuaát chuùng, vaø noùi chung ngöôøi
laäp trình khoâng caàn phaûi baän taâm ñeán caùch hieän thöïc chi tieát cuûa noù. Tuy nhieân,
boä nhôù maùy tính thöôøng coù toå chöùc cô baûn laø moät maûng lieân tuïc (nhö moät maûng
tuyeán tính coù phaàn töû naøy naèm keá phaàn töû kia), ñoái vôùi moãi truy xuaát ñeán baûng
chöõ nhaät, maùy caàn phaûi coù moät soá tính toaùn ñeå chuyeån ñoåi moät vò trí trong hình
chöõ nhaät sang moät vò trí trong maûng tuyeán tính. Chuùng ta haõy xem xeùt ñieàu naøy
moät caùch chi tieát hôn.
12.2.1.Thöù töï öu tieân haøng vaø thöù töï öu tieân coät
Caùch töï nhieân ñeå ñoïc moät baûng chöõ nhaät laø ñoïc caùc phaàn töû ôû haøng thöù nhaát
tröôùc, töø traùi sang phaûi, sau ñoù ñeán caùc phaàn töû haøng thöù hai, vaø cöù theá tieáp tuïc
cho ñeán khi haøng cuoái ñaõ ñöôïc ñoïc xong. Ñaây cuõng laø thöù töï maø ña soá caùc trình
bieân dòch löu tröõ baûng chöõ nhaät, vaø ñöôïc goïi laø thöù töï öu tieân haøng (row-major
ordering). Chaúng haïn, moät baûng tröøu töôïng coù haøng ñöôïc ñaùnh soá laø töø 1 ñeán 2,
vaø coät ñöôïc ñaùnh soá töø 5 ñeán 7, thì thöù töï cuûa caùc phaàn töû theo thöù töï öu tieân
haøng nhö sau:
(1,5)
(1,6)
(1,7)
(2,5)
(2,6)
(2,7)
Ñaây cuõng laø thöù töï ñöôïc duøng trong C++ vaø haàu heát caùc ngoân ngöõ laäp trình caáp
cao ñeå löu tröõ caùc phaàn töû cuûa moät maûng hai chieàu. FORTRAN chuaån laïi söû duïng
thöù töï öu tieân coät, trong ñoù caùc phaàn töû cuûa coät thöù nhaát ñöôïc löu tröôùc, roài ñeán
coät thöù hai,v.v...Ví duï thöù töï öu tieân coät nhö sau:
(1,5)
(2,5)
(1,6)
(2,6)
(1,7)
(2,7)
Hình 12.1 minh hoïa caùc thöù töï öu tieân cho moät baûng coù 3 haøng vaø 4 coät.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
306
Chöông 12 – Baûng vaø truy xuaát thoâng tin
Hình 12.1 – Bieåu dieãn noái tieáp cho maûng chöõ nhaät
12.2.2.Ñaùnh chæ soá cho baûng chöõ nhaät
Moät caùch toång quaùt, trình bieân dòch coù theå baét ñaàu töø chæ soá (i,j) ñeå tính vò trí
trong moät maûng noái tieáp maø moät phaàn töû töông öùng trong baûng ñöôïc löu tröõ.
Chuùng ta seõ ñöa ra coâng thöùc tính toaùn sau ñaây. Ñeå ñôn giaûn chuùng ta chæ söû
duïng thöù töï öu tieân haøng cuøng vôùi giaû thieát laø haøng ñöôïc ñaùnh soá töø 0 ñeán m-1, vaø
coät töø 0 ñeán n-1. Tröôøng hôïp caùc haøng vaø caùc coät ñöôïc ñaùnh soá khoâng phaûi töø 0
ñöôïc xem nhö baøi taäp. Soá phaàn töû cuûa baûng seõ laø mn, vaø ñoù cuõng laø soá phaàn töû
trong hieän thöïc lieân tuïc trong maûng. Chuùng ta ñaùnh soá caùc phaàn töû trong maûng töø
0 ñeán mn –1. Ñeå coù coâng thöùc tính vò trí cuûa phaàn töû (i,j) trong maûng, tröôùc heát
chuùng ta quan saùt moät vaøi tröôøng hôïp ñaëc bieät. Phaàn töû (0,0) naèm taïi vò trí 0, caùc
phaàn töû thuoäc haøng ñaàu tieân trong baûng raát deã tìm thaáy: (0,j) naèm taïi vò trí j.
Phaàn töû ñaàu cuûa haøng thöù hai (1,0) naèm ngay sau phaàn töû (0,n-1), ñoù laø vò trí n.
Tieáp theo, chuùng ta thaáy phaàn töû (1,j) naèm taïi vò trí n+j. Caùc phaàn töû cuûa haøng keá
tieáp cuõng seõ naèm sau soá phaàn töû cuûa hai haøng tröôùc ñoù (2n phaàn töû). Do ñoù phaàn
töû (2,j) naèm taïi vò trí 2n+j. Moät caùch toång quaùt, caùc phaàn töû thuoäc haøng i coù n i
phaàn töû phía tröôùc, neân coâng thöùc chung laø:
Phaàn töû (i,j) trong baûng chöõ nhaät naèm taïi vò trí n i + j trong maûng noái tieáp.
Coâng thöùc naøy cho bieát vò trí trong maûng noái tieáp maø moät phaàn töû trong baûng
chöõ nhaät ñöôïc löu tröõ, vaø ñöôïc goïi laø haøm chæ soá (index function).
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
307
Chöông 12 – Baûng vaø truy xuaát thoâng tin
12.2.3.Bieán theå: maûng truy xuaát
Vieäc tính toaùn cho caùc haøm chæ soá cuûa caùc baûng chöõ nhaät thaät ra khoâng khoù
laém, caùc trình bieân dòch cuûa haàu heát caùc ngoân ngöõ caáp cao seõ dòch haøm naøy sang
ngoân ngöõ maùy thaønh moät soá böôùc tính toaùn caàn thieát. Tuy nhieân, treân caùc maùy
tính nhoû, pheùp nhaân thöôøng thöïc hieän raát chaäm, moät phöông phaùp khaùc coù theå
ñöôïc söû duïng ñeå traùnh pheùp nhaân.
Phöông phaùp naøy löu moät maûng phuï trôï chöùa moät phaàn cuûa baûng nhaân vôùi
thöøa soá laø n:
0,
n,
2n,
3n,
...,
(m-1)n.
Löu yù raèng maûng naøy nhoû hôn baûng chöõ nhaät raát nhieàu, neân noù coù theå ñöôïc
löu thöôøng tröïc trong boä nhôù. Caùc phaàn töû cuûa noù chæ phaûi tính moät laàn (vaø
chuùng coù theå ñöôïc tính chæ baèng pheùp coäng). Khi gaëp moät yeâu caàu tham chieáu
ñeán baûng chöõ nhaät, trình bieân dòch coù theå tìm vò trí cuûa phaàn töû (i,j) baèng caùch
laáy phaàn töû thöù i trong maûng phuï trôï coäng theâm j ñeå ñeán vò trí caàn coù.
Maûng phuï trôï naøy cung caáp cho chuùng ta moät ví duï ñaàu tieân veà moät maûng
truy xuaát (access maûng) (Hình 12.2). Noùi chung, moät maûng truy xuaát laø moät
maûng phuï trôï ñöôïc söû duïng ñeå tìm moät döõ lieäu ñöôïc löu tröõ ñaâu ñoù. Maûng truy
xuaát coù khi coøn ñöôïc goïi laø vector truy xuaát (access vector).
Hình 12.2 – Maûng truy xuaát cho baûng chöõ nhaät
12.3. Caùc baûng vôùi nhieàu hình daïng khaùc nhau
Thoâng tin thöôøng löu trong moät baûng chöõ nhaät coù theå khoâng caàn ñeán moïi vò trí
trong hình chöõ nhaät ñoù. Neáu chuùng ta ñònh nghóa ma traän laø moät baûng chöõ nhaät
goàm caùc con soá, thì thöôøng laø moät vaøi vò trí trong ma traän ñoù mang trò 0. Moät vaøi
ví duï nhö theá ñöôïc minh hoïa trong hình 12.3. Ngay caû khi caùc phaàn töû trong moät
baûng khoâng phaûi laø nhöõng con soá, caùc vò trí ñöôïc söû duïng thöïc söï cuõng coù theå
khoâng phaûi laø taát caû hình chöõ nhaät, vaø nhö vaäy coù theå coù caùch hieän thöïc khaùc hay
hôn thay vì söû duïng moät baûng chöõ nhaät vôùi nhieàu choã troáng. Trong phaàn naøy,
chuùng ta tìm hieåu caùc caùch hieän thöïc caùc baûng vôùi nhieàu hình daïng khaùc nhau,
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
308
Chöông 12 – Baûng vaø truy xuaát thoâng tin
nhöõng caùch naøy seõ khoâng ñoøi hoûi vuøng nhôù cho nhöõng phaàn töû vaéng maët nhö
trong baûng chöõ nhaät.
12.3.1.Caùc baûng tam giaùc
Chuùng ta haõy xem xeùt caùch bieåu dieãn baûng tam giaùc döôùi nhö trong hình veõ
12.3. Moät baûng nhö vaäy chæ caàn caùc chæ soá (i,j) vôùi i≥j. Chuùng ta coù theå hieän thöïc
moät baûng tam giaùc trong moät maûng lieân tuïc baèng caùch tröôït moãi haøng ra sau
haøng naèm ngay treân noù, nhö caùch bieåu dieãn ôû hình 12.4.
Hình 12.3 – Caùc baûng vôùi nhieàu daïng khaùc nhau.
Ñeå xaây döïng haøm chæ soá moâ taû caùch aùnh xaï naøy, chuùng ta cuõng giaû söû raèng caùc
haøng vaø caùc coät ñeàu ñöôïc ñaùnh soá baét ñaàu töø 0. Ñeå tìm vò trí cuûa phaàn töû (i,j)
trong maûng lieân tuïc chuùng ta caàn tìm vò trí baét ñaàu cuûa haøng i, sau ñoù ñeå tìm coät j
chuùng ta chæ vieäc coäng theâm j vaøo ñieåm baét ñaàu cuûa haøng i. Neáu caùc phaàn töû cuûa
maûng lieân tuïc cuõng ñöôïc ñaùnh soá baét ñaàu töø 0, thì chæ soá cuûa ñieåm baét ñaàu cuûa
haøng thöù i cuõng chính laø soá phaàn töû naèm ôû caùc haøng treân haøng i. Roõ raøng laø treân
haøng thöù 0 coù 0 phaàn töû, vaø chæ coù moät phaàn töû cuûa haøng 0 laø xuaát hieän tröôùc
haøng 1. Ñoái vôùi haøng 2, coù 1 + 2 = 3 phaàn töû ñi tröôùc, vaø trong tröôøng hôïp toång
quaùt chuùng ta thaáy soá phaàn töû coù tröôùc haøng i chính xaùc laø:
1
1 + 2 + . . . + i =
i(i + 1).
2
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
309
Chöông 12 – Baûng vaø truy xuaát thoâng tin
1
2
Vaäy phaàn töû (i,j) trong baûng tam giaùc töông öùng phaàn töû
maûng lieân tuïc.
i(i + 1) + j cuûa
Hình 12.4 – Hieän thöïc lieân tuïc cuûa baûng tam giaùc.
Cuõng nhö chuùng ta ñaõ laøm cho caùc baûng chöõ nhaät, chuùng ta cuõng traùnh moïi
pheùp nhaân vaø chia baèng caùch taïo moät maûng truy xuaát chöùa caùc phaàn töû töông öùng
vôùi caùc chæ soá cuûa caùc haøng trong baûng tam giaùc. Vò trí i trong maûng truy xuaát
1
mang trò
i (i + 1). Maûng truy xuaát ñöôïc tính toaùn chæ moät laàn khi baét ñaàu
2
chöông trình, vaø ñöôïc söû duïng laëp laïi cho moãi truy xuaát ñeán baûng tam giaùc. Chuù yù
raèng ngay caû vieäc tính toaùn ban ñaàu cuõng khoâng caàn ñeán pheùp nhaân hoaëc chia maø
chí coù pheùp coäng theo thöù töï sau maø thoâi:
0,
1,
1+2, (1 + 2) + 3, . . .
12.3.2.Caùc baûng loài loõm
Hình 12.5 – Maûng truy xuaát cho baûng loài loõm.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
310
Chöông 12 – Baûng vaø truy xuaát thoâng tin
Trong caû hai ví duï ñaõ ñeà caäp tröôùc chuùng ta ñaõ xem xeùt moät baûng ñöôïc taïo töø
caùc haøng cuûa noù. Trong caùc baûng chöõ nhaät thoâng thöôøng, taát caû caùc haøng ñeàu coù
cuøng chieàu daøi; trong baûng tam giaùc, chieàu daøi moãi haøng coù theå ñöôïc tính döïa vaøo
moät coâng thöùc ñôn giaûn. Baây giôø chuùng ta haõy xem xeùt ñeán tröôøng hôïp cuûa caùc
baûng loài loõm töïa nhö hình 12.5, khoâng coù moät moái quan heä coù theå ñoaùn tröôùc naøo
giöõa vò trí cuûa moät haøng vaø chieàu daøi cuûa noù.
Moät ñieàu hieån nhieân ñöôïc nhìn thaáy töø sô ñoà raèng, tuy chuùng ta khoâng theå xaây
döïng moät haøm thöù töï naøo ñeå aùnh xaï moät baûng loài loõm sang vuøng nhôù lieân tuïc,
nhöng vieäc söû duïng moät maûng truy xuaát cuõng deã daøng nhö caùc ví duï tröôùc, vaø caùc
phaàn töû cuûa baûng loài loõm coù theå ñöôïc truy xuaát moät caùch nhanh choùng. Ñeå taïo
maûng truy xuaát, chuùng ta phaûi xaây döïng baûng loài loõm theo thöù töï voán coù cuûa noù,
baét ñaàu töø haøng ñaàu tieân. Phaàn töû 0 cuûa maûng truy xuaát, cuõng nhö tröôùc kia, laø
baét ñaàu cuûa maûng lieân tuïc. Sau khi moãi haøng cuûa baûng loài loõm ñöôïc xaây döïng
xong, chæ soá cuûa vò trí ñaàu tieân chöa ñöôïc söû duïng tôùi cuûa vuøng nhôù lieân tuïc chính
laø trò cuûa phaàn töû keá tieáp trong maûng truy xuaát vaø ñöôïc söû duïng ñeå baét ñaàu xaây
döïng haøng keá cuûa baûng loài loõm.
12.3.3. Caùc baûng chuyeån ñoåi
Tieáp theo, chuùng ta haõy xem xeùt moät ví duï minh hoïa vieäc söû duïng nhieàu maûng
truy xuaát ñeå tham chieáu cuøng luùc ñeán moät baûng caùc phaàn töû qua moät vaøi khoùa
khaùc nhau.
Chuùng ta xem xeùt nhieäm vuï cuûa moät coâng ty ñieän thoaïi trong vieäc truy xuaát
ñeán caùc phaàn töû veà caùc khaùch haøng cuûa hoï. Ñeå in danh muïc ñieän thoaïi, caùc phaàn
töû caàn saép thöù töï teân khaùch haøng theo alphabet. Tuy nhieân, ñeå xöû lyù caùc cuoäc goïi
ñöôøng daøi, caùc phaàn töû laïi caàn coù thöù töï theo soá ñieän thoaïi. Ngoaøi ra, ñeå tieán
haønh baûo trì ñònh kyø, danh saùch caùc khaùch haøng saép thöù töï theo ñòa chæ seõ coù ích
cho caùc nhaân vieân baûo trì. Nhö vaäy, coâng ty ñieän thoaïi caàn phaûi löu caû ba, hoaëc
nhieàu hôn, danh saùch caùc khaùch haøng theo caùc thöù töï khaùc nhau. Baèng caùch naøy,
khoâng nhöõng toán keùm nhieàu vuøng löu tröõ maø coøn coù khaû naêng thoâng tin bò sai
leäch do khoâng ñöôïc caäp nhaät ñoàng thôøi.
Chuùng ta coù theå traùnh ñöôïc vieäc phaûi löu nhieàu laàn cuøng moät taäp caùc phaàn töû
baèng caùch söû duïng caùc maûng truy xuaát, vaø chuùng ta coù theå tìm caùc phaàn töû theo
baát kyø moät khoùa naøo moät caùch nhanh choùng chaúng khaùc gì chuùng ñaõ ñöôïc saép thöù
töï theo khoùa ñoù. Chuùng ta seõ taïo moät maûng truy xuaát cho teân caùc khaùch haøng.
Phaàn töû ñaàu tieân cuûa maûng naøy chöùa vò trí cuûa khaùch haøng ñöùng ñaàu danh saùch
theo alphabet. Phaàn töû thöù hai chöùa vò trí khaùch haøng thöù hai, vaø cöù theá. Trong
maûng truy xuaát thöù hai, phaàn töû ñaàu tieân chöùa vò trí cuûa khaùch haøng coù soá ñieän
thoaïi nhoû nhaát. Töông töï, maûng truy xuaát thöù ba coù caùc phaàn töû chöùa vò trí cuûa
caùc khaùch haøng theo thöù töï ñòa chæ cuûa hoï. (Hình 12.6)
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
311
Chöông 12 – Baûng vaø truy xuaát thoâng tin
Hình 12.6 – Maûng truy xuaát cho nhieàu khoùa: baûng chuyeån ñoåi
Chuùng ta löu yù raèng trong phöông phaùp naøy caùc thaønh phaàn döõ lieäu ñöôïc xem
nhö laø khoùa ñeàu ñöôïc xöû lyù cuøng moät caùch. Khoâng coù lyù do gì buoäc caùc phaàn töû
phaûi coù thöù töï vaät lyù öu tieân theo khoùa naøy maø khoâng theo khoùa khaùc. Caùc phaàn
töû coù theå ñöôïc löu tröõ theo moät thöù töï tuøy yù, coù theå noùi ñoù laø thöù töï maø chuùng
ñöôïc nhaäp vaøo heä thoáng. Cuõng khoâng coù söï khaùc nhau giöõa vieäc caùc phaàn töû ñöôïc
löu trong moät danh saùch lieân tuïc laø maûng (maø caùc phaàn töû cuûa caùc maûng truy xuaát
chöùa caùc chæ soá cuûa maûng naøy) hay caùc phaàn töû ñang thuoäc moät danh saùch lieân keát
(caùc phaàn töû cuûa caùc maûng truy xuaát chöùa caùc ñòa chæ ñeán töøng phaàn töû rieâng).
Trong moïi tröôøng hôïp, chính caùc maûng truy xuaát ñöôïc söû duïng ñeå truy xuaát thoâng
tin, vaø, cuõng gioáng nhö caùc maûng lieân tuïc thoâng thöôøng, chuùng coù theå ñöôïc söû
duïng trong vieäc tra cöùu caùc baûng, hoaëc tìm kieám nhò phaân, hoaëc vôùi baát kyø muïc
ñích naøo khaùc thích hôïp vôùi caùch hieän thöïc lieân tuïc.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
312
Chöông 12 – Baûng vaø truy xuaát thoâng tin
Hình 12.7 – Ví duï veà baûng tam giaùc ñoái xöùng qua 0.
12.4. Baûng: Moät kieåu döõ lieäu tröøu töôïng môùi
Töø ñaàu chöông naøy chuùng ta ñaõ bieát ñeán moät soá haøm chæ soá ñöôïc duøng ñeå tìm
kieám caùc phaàn töû trong caùc baûng, sau ñoù chuùng ta cuõng ñaõ gaëp caùc maûng truy xuaát
laø caùc maûng ñöôïc duøng vôùi cuøng moät muïc ñích nhö caùc haøm chæ soá. Coù moät söï
gioáng nhau raát lôùn giöõa caùc haøm vôùi vieäc tra cöùu baûng: vôùi moät haøm, chuùng ta baét
ñaàu baèng moät thoâng soá ñeå tính moät giaù trò töông öùng; vôùi moät baûng, chuùng ta baét
ñaàu baèng moät chæ soá ñeå truy xuaát moät giaù trò döõ lieäu töông öùng ñöôïc löu trong
baûng. Chuùng ta haõy söû duïng söï töông töï naøy ñeå xaây döïng moät ñònh nghóa hình
thöùc cho thuaät ngöõ baûng.
12.4.1.Caùc haøm
Trong toaùn hoïc, moät haøm ñöôïc ñònh nghóa döïa treân hai taäp hôïp vaø söï töông
öùng töø caùc phaàn töû cuûa taäp thöù nhaát ñeán caùc phaàn töû cuûa taäp thöù hai. Neáu f laø moät
haøm töø taäp A sang taäp B, thì f gaùn cho moãi phaàn töû cuûa A moät phaàn töû duy nhaát
cuûa B. Taäp A ñöôïc goïi laø domain cuûa f, coøn taäp B ñöôïc goïi laø codomain cuûa f. Taäp
con cuûa B chæ chöùa caùc phaàn töû laø caùc trò cuûa f ñöôïc goïi laø range cuûa f. Ñònh nghóa
naøy ñöôïc minh hoïa trong hình 12.8.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
313
Chöông 12 – Baûng vaø truy xuaát thoâng tin
Hình 12.8 – Domain, codomain vaø range cuûa moät haøm
Vieäc truy xuaát baûng baét ñaàu baèng moät chæ soá vaø baûng ñöôïc söû duïng ñeå tra cöùu
moät trò töông öùng. Ñoái vôùi moät baûng chuùng ta goïi domain laø taäp chæ soá (index set),
vaø codomain laø kieåu cô sôû (base type) hoaëc kieåu trò (value type). Laáy ví duï, chuùng
ta coù moät khai baùo maûng nhö sau:
double array[n];
thì taäp chæ soá laø taäp caùc soá nguyeân töø 0 ñeán n-1, vaø kieåu cô sôû laø taäp taát caû caùc soá
thöïc. Laáy ví duï thöù hai, chuùng ta haõy xeùt moät baûng tam giaùc coù m haøng, moãi phaàn
töû coù kieåu item. Kieåu cô sôû seõ laø kieåu itemvaø taäp chæ soá laø taäp caùc caëp soá nguyeân
{(i,j) | 0 ≤ j ≤ i < m}
12.4.2.Moät kieåu döõ lieäu tröøu töôïng
Chuùng ta ñang ñi ñeán moät ñònh nghóa cho baûng nhö moät kieåu döõ lieäu tröøu
töôïng môùi, ñoàng thôøi trong caùc chöông tröôùc chuùng ta ñaõ bieát raèng ñeå hoaøn taát
moät ñònh nghóa cho moät caáu truùc döõ lieäu, chuùng ta caàn phaûi ñaëc taû caùc taùc vuï ñi
keøm.
Ñònh nghóa: Moät baûng vôùi taäp chæ soá I vaø kieåu cô sôû T laø moät haøm töø I ñeán T keøm
caùc taùc vuï sau:
1. Access (truy xuaát baûng): Xaùc ñònh trò cuûa haøm theo baát kyø moät chæ soá trong I.
2. Assignment (ghi baûng): Söûa ñoåi haøm baèng caùch thay ñoåi trò cuûa noù taïi moät chæ
soá naøo ñoù trong I thaønh moät trò môùi ñöôïc chæ ra trong pheùp gaùn.
Hai taùc vuï naøy laø taát caû nhöõng gì ñöôïc cung caáp bôûi caùc maûng trong C++ hoaëc
moät vaøi ngoân ngöõ khaùc, nhöng ñoù khoâng phaûi laø lyù do ñeå coù theå ngaên caûn chuùng
ta theâm moät soá taùc vuï khaùc cho moät baûng tröøu töôïng. Neáu so saùnh vôùi ñònh nghóa
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
314
Chöông 12 – Baûng vaø truy xuaát thoâng tin
cuûa moät danh saùch (list), chuùng ta ñaõ coù caùc taùc vuï nhö theâm phaàn töû, xoùa phaàn töû
cuõng nhö truy xuaát hoaëc caäp nhaät laïi. Vaäy chuùng ta coù theå laøm töông töï ñoái vôùi
baûng.
Caùc taùc vuï boå sung cho baûng:
1. Creation (Taïo): Taïo moät haøm töø I vaøo T.
2. Clearing (Doïn deïp): Loaïi boû moïi phaàn töû trong taäp chæ soá I, domain seõ laø moät
taäp roãng.
3. Insertion (Theâm): Theâm moät phaàn töû x vaøo taäp chæ soá I vaø xaùc ñònh moät trò
töông öùng cuûa haøm taïi x.
4. Deletion (Xoùa): Loaïi boû moät phaàn töû x trong taäp chæ soá I vaø haïn cheá chæ cho
haøm xaùc ñònh treân taäp chæ soá coøn laïi.
12.4.3.Hieän thöïc
Ñònh nghóa treân chæ môùi laø ñònh nghóa cuûa moät kieåu döõ lieäu tröøu töôïng maø
chöa noùi gì ñeán caùch hieän thöïc. Noù cuõng khoâng heà nhaéc ñeán caùc haøm chæ soá hay
caùc maûng truy xuaát. Chuùng ta haõy xem hình minh hoïa trong hình 12.9. Phaàn treân
cuûa hình naøy cho chuùng ta thaáy moät söï tröøu töôïng trong ñònh nghóa, truy xuaát
baûng ñôn giaûn chæ laø moät aùnh xaï töø moät taäp chæ soá sang moät kieåu cô sôû. Phaàn döôùi
cuûa hình laø yù töôûng toång quaùt cuûa phaàn hieän thöïc. Moät haøm chæ soá hoaëc moät maûng
truy xuaát nhaän thoâng soá töø moät taäp chæ soá theo moät daïng ñaõ ñöôïc ñaëc taû naøo ñoù.
Chaúng haïn (i,j) trong baûng 2 chieàu hoaëc (i,j,k) trong baûng 3 chieàu vôùi i, j, k ñaõ coù
mieàn xaùc ñònh ñaõ ñònh. Keát quaû cuûa haøm chæ soá hoaëc maûng truy xuaát seõ laø moät
trong caùc trò trong mieàn caùc chæ soá, chaúng haïn taäp con cuûa taäp caùc soá nguyeân.
Mieàn trò naøy coù theå ñöôïc söû duïng tröïc tieáp nhö chæ soá cho maûng vaø ñöôïc cung caáp
bôûi ngoân ngöõ laäp trình.
Ñeán ñaây xem nhö chuùng ta ñaõ giôùi thieäu xong moät kieåu caáu truùc döõ lieäu môùi,
ñoù laø baûng. Tuøy töøng muïc ñích cuûa caùc öùng duïng, baûng coù theå coù nhieàu phieân baûn
khaùc nhau. Phaàn ñònh nghóa chi tieát hôn cho caùc phieân baûn naøy cuõng nhö caùc
caùch hieän thöïc cuûa chuùng ñöôïc xem nhö baøi taäp. Phaàn tieáp theo ñaây trình baøy söï
gioáng vaø khaùc nhau giöõa danh saùch vaø baûng. Sau ñoù chuùng ta seõ tieáp tuïc laøm quen
vôùi moät caáu truùc döõ lieäu khaù ñaëc bieät vaø raát phoå bieán, ñoù laø baûng baêm. Caáu truùc
döõ lieäu baûng baêm cuõng xuaát phaùt töø yù töôûng söû duïng baûng nhö phaàn naøy ñaõ giôùi
thieäu.
12.4.4.So saùnh giöõa danh saùch vaø baûng
Chuùng ta haõy so saùnh hai kieåu döõ lieäu tröøu töôïng danh saùch vaø baûng. Neàn
taûng toaùn hoïc cô baûn cuûa danh saùch laø moät chuoãi noái tieáp caùc phaàn töû, coøn ñoái
vôùi baûng, ñoù laø taäp hôïp vaø haøm. Chuoãi noái tieáp coù moät traät töï ngaàm trong ñoù, ñoù
laø phaàn töû ñaàu tieân, phaàn töû thöù hai, v.v..., coøn taäp hôïp vaø haøm khoâng coù thöù töï.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
315
Chöông 12 – Baûng vaø truy xuaát thoâng tin
Vieäc truy xuaát thoâng tin trong moät danh saùch thöôøng lieân quan ñeán vieäc tìm
kieám, nhöng vieäc truy xuaát thoâng tin trong baûng ñoøi hoûi nhöõng phöông phaùp
khaùc, ñoù laø caùc phöông phaùp coù theå ñi thaúng ñeán phaàn töû mong muoán. Thôøi gian
caàn thieát ñeå tìm kieám trong danh saùch noùi chung phuï thuoäc vaøo n laø soá phaàn töû
trong danh saùch vaø ít nhaát laø baèng lg n, nhöng thôøi gian ñeå truy xuaát baûng
thöôøng khoâng phuï thuoäc vaøo soá phaàn töû trong baûng, vaø thöôøng laø O(1). Vì lyù do
naøy, trong nhieàu öùng duïng, vieäc truy xuaát baûng thöïc söï nhanh hôn vieäc tìm kieám
trong moät danh saùch.
Hình 12.9 – Hieän thöïc cuûa baûng
Maët khaùc, duyeät laø moät taùc vuï töï nhieân ñoái vôùi moät danh saùch, nhöng
ñoái vôùi baûng thì khoâng. Vieäc di chuyeån xuyeân suoát moät danh saùch ñeå thöïc hieän
moät taùc vuï naøo ñoù leân töøng phaàn töû cuûa noù noùi chung laø deã daøng. Ñieàu naøy ñoái vôùi
baûng khoâng deã daøng chuùt naøo, ñaëc bieät trong tröôøng hôïp coù yeâu caàu tröôùc veà moät
traät töï naøo ñoù cuûa caùc phaàn töû ñöôïc duyeät.
Cuoái cuøng, chuùng ta caàn laøm roõ söï khaùc nhau giöõa baûng vaø maûng. Noùi chung,
chuùng ta duøng töø baûng nhö laø chuùng ta ñaõ ñònh nghóa trong phaàn vöøa roài vaø giôùi
haïn töø maûng chæ vôùi nghóa nhö laø moät phöông tieän duøng ñeå laäp trình cuûa C++ vaø
phaàn lôùn caùc ngoân ngöõ caáp cao, caùc maûng naøy thöôøng ñöôïc söû duïng ñeå hieän thöïc
caû hai: baûng vaø danh saùch lieân tuïc.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
316
Chöông 12 – Baûng vaø truy xuaát thoâng tin
12.5. Baûng baêm
Khi giôùi thieäu toång quaùt veà baûng cuõng nhö caùch söû duïng haøm chæ soá vaø maûng
truy xuaát, chuùng ta caàn nhaän ra moät ñieàu raèng, thoâng soá cho haøm chæ soá hoaëc
maûng truy xuaát phaàn naøo phaûn aùnh vò trí, hay noùi roõ hôn, ñoù laø traät töï cuûa phaàn
töû caàn truy xuaát trong baûng. Chaúng haïn traät töï theo chæ soá haøng vaø coät trong
baûng (i,j), hay tröôøng hôïp danh saùch caùc khaùch haøng söû duïng ñieän thoaïi: teân cuûa
caùc khaùch haøng coù thöù töï theo alphabet. Baûng baêm maø chuùng ta seõ nghieân cöùu
tieáp theo mang moät ñaëc ñieåm hoaøn toaøn khaùc. Vieäc truy xuaát baûng baét ñaàu töø giaù
trò cuûa khoùa trong phaàn töû döõ lieäu, vaø thoâng thöôøng khoùa naøy khoâng lieân quan
ñeán traät töï trong haøng hoaëc coät cuûa baûng ñeå coù theå söû duïng moät haøm chæ soá ñôn
giaûn cho ra vò trí cuûa noù trong baûng nhö ôû phaàn treân ñaõ giôùi thieäu.
12.5.1.Caùc baûng thöa
12.5.1.1. Caùc haøm chæ soá
Ñieàu chuùng ta coù theå laøm laø xaây döïng söï töông öùng moät – moät giöõa caùc khoùa
vaø caùc chæ soá maø chuùng ta söû duïng ñeå truy xuaát baûng. So vôùi caùc phaàn tröôùc, haøm
chæ soá maø chuùng ta xaây döïng ôû ñaây seõ phöùc taïp hôn, vì coù khi chuùng ta caàn ñeán söï
bieán ñoåi cuûa caùc khoùa, chaúng haïn töø caùc chöõ caùi sang caùc soá nguyeân. Theo nguyeân
taéc, ñieàu naøy luoân coù theå laøm ñöôïc.
Khoù khaên thöïc söï chæ laø khi soá caùc khoùa coù theå coù vöôït ra ngoaøi khoâng gian
cuûa baûng. Laáy ví duï, neáu caùc khoùa laø caùc töø coù 8 kyù töï, thì coù theå coù ñeán 268 ≈ 2 x
1011 khoùa khaùc nhau, vaø ñaây cuõng laø con soá lôùn hôn raát nhieàu dung löôïng cho
pheùp cuûa moät boä nhôù toác ñoä cao. Tuy nhieân trong thöïc teá, chæ coù moät soá khoâng lôùn
caùc khoùa naøy laø thöïc söï xuaát hieän. Ñieàu ñoù coù nghóa laø baûng chöùa seõ raát thöa thôùt.
Chuùng ta coù theå xem baûng ñöôïc ñaùnh chæ soá baèng moät taäp raát lôùn, nhöng chæ coù
moät soá töông ñoái ít vò trí laø thöïc söï coù phaàn töû.
12.5.1.2. Khaùi nieäm baêm
Nhaèm traùnh moät baûng quaù thöa thôùt coù nhieàu vò trí khoâng bao giôø ñöôïc duøng
ñeán, chuùng ta laøm quen vôùi khaùi nieäm bamê . YÙ töôûng cuûa baûng baêm (hình 12.10) laø
cho pheùp aùnh xaï moät taäp caùc khoùa khaùc nhau vaøo caùc vò trí trong moät maûng vôùi
kích thöôùc cho pheùp. Goïi kích thöôùc maûng naøy laø hash_size, moãi khoùa seõ ñöôïc
aùnh xaï vaøo moät chæ soá trong khoaûng [0, hash_size-1]. Aùnh xaï naøy ñöôïc goïi laø
haøm baêm (hash function). Moät caùch lyù töôûng, haøm naøy caàn coù caùch tính ñôn giaûn
vaø phaân boå caùc khoùa sao cho hai khoùa khaùc nhau luoân vaøo hai vò trí khaùc nhau.
Nhöng do kích thöôùc maûng laø giôùi haïn vaø mieàn trò cuûa caùc khoùa laø raát lôùn, ñieàu
naøy laø khoâng theå ñöôïc. Chuùng ta chæ coù theå hy voïng raèng moät haøm baêm toát thì seõ
phaân boå ñöôïc caùc khoùa vaøo caùc chæ soá moät caùch khaù ñoàng ñeàu vaø traùnh ñöôïc hieän
töôïng gom tuï.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
317
Chöông 12 – Baûng vaø truy xuaát thoâng tin
Haøm baêm noùi chung luoân aùnh xaï moät vaøi khoùa khaùc nhau vaøo cuøng moät chæ soá.
Neáu phaàn töû caàn tìm ñang naèm taïi chæ soá ñöôïc aùnh xaï ñeán, vaán ñeà cuûa chuùng ta
xem nhö ñaõ ñöôïc giaûi quyeát; ngöôïc laïi, chuùng ta caàn söû duïng moät phöông phaùp
naøo ñoù ñeå giaûi quyeát ñuïng ñoä. Vieäc ñuïng ñoä (collision) xaûy ra khi hai phaàn töû caàn
ñöôïc chöùa trong cuøng moät vò trí cuûa baûng.
Treân ñaây laø yù töôûng cô baûn cuûa vieäc söû duïng baûng baêm. Coù ba vaán ñeà chuùng ta
caàn xem xeùt khi söû duïng phöông phaùp baêm:
• Tìm haøm baêm toát.
• Xaùc ñònh phöông phaùp giaûi quyeát ñuïng ñoä.
• Xaùc ñònh kích thöôùc baûng baêm.
Hình 12.10 – Baûng baêm
12.5.2.Löïa choïn haøm baêm
Hai tieâu chí cô baûn ñeå choïn löïa moät haøm baêm laø:
• Haøm baêm caàn ñöôïc tính toaùn deã daøng vaø nhanh choùng.
• Vieäc phaân phoái caùc khoùa coù theå xuaát hieän raûi ñeàu treân baûng baêm.
Neáu chuùng ta bieát tröôùc chính xaùc nhöõng khoùa naøo seõ xuaát hieän, thì chuùng ta
coù theå xaây döïng moät haøm baêm thaät hieäu quaû, nhöng noùi chung chuùng ta thöôøng
khoâng bieát tröôùc ñieàu naøy.
Chuùng ta caàn löu yù raèng moät haøm baêm khoâng heà coù tính ngaãu nhieân. Khi tính
nhieàu laàn cho cuøng moät khoùa, moät haøm baêm phaûi cho cuøng moät trò, coù nhö vaäy thì
khoùa môùi coù theå ñöôïc truy xuaát sau khi ñöôïc löu tröõ.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
318
Chöông 12 – Baûng vaø truy xuaát thoâng tin
12.5.2.1. Chia laáy phaàn dö (modular arithmetic)
Tröôùc heát chuùng ta haõy xem xeùt moät tröôøng hôïp thaät ñôn giaûn. Neáu caùc khoùa
laø caùc soá nguyeân, haøm baêm ñôn giaûn vaø phoå bieán ñöôïc duøng laø pheùp chia cho
hash_size ñeå laáy phaàn dö, vì nhö vaäy chuùng ta seõ coù caùc chæ soá thuoäc [0,
hash_size -1]. Tuy nhieân cuõng caàn löu yù nhöõng tröôøng hôïp caùc khoùa taäp trung
vaøo moät soá giaù trò ñaëc bieät naøo ñoù. Chaúng haïn neáu hash_size = 10, maø phaàn lôùn
caùc khoùa laïi coù con soá ôû haøng ñôn vò laø 0. Söï phaân taùn caùc khoùa phuï thuoäc nhieàu
vaøo pheùp chia laáy phaàn dö, ñoù chính laø kích thöôùc cuûa baûng baêm. Neáu kích thöôùc
ñoù laø moät boäi soá cuûa caùc soá nguyeân nhoû nhö 2 hoaëc 10, thì raát nhieàu khoùa seõ cho
cuøng chæ soá nhö nhau, trong khi ñoù coù moät soá chæ soá raát ít ñöôïc söû duïng ñeán. Caùch
choïn pheùp chia laáy phaàn dö toát nhaát thöôøng laø chia cho moät soá nguyeân toá (nhöng
khoâng phaûi laø luoân luoân), keát quaû seõ raûi ñeàu caùc khoùa trong baûng baêm hôn. Nhö
vaäy, thay vì choïn baûng baêm kích thöôùc 1000, chuùng ta neân choïn kích thöôùc 997
hoaëc 1009; caùch choïn 210 = 1024laø moät caùch choïn raát dôû.
Thoâng thöôøng, caùc khoùa laø caùc chuoãi kyù töï. Moät caùch töï nhieân, ngöôøi ta thöôøng
laáy moät soá nguyeân baèng vôùi toång cuûa caùc maõ ASCII cuûa caùc kyù töï trong khoùa laøm
ñaïi dieän cho noù. Haøm baêm vôùi caùch vieát cuûa C chuaån sau ñaây thaät ñôn giaûn vaø
tính cuõng raát nhanh:
index Hash(const char *Key, int hash_size)
{
unsigned int HashVal = 0;
while (*Key != ‘\0’)
{
HashVal += *Key;
Key++;
}
return HashVal % hash_size;
}
Tuy nhieân, neáu hash_sizelôùn, haøm seõ khoâng phaân boå caùc khoùa toát. Laáy ví duï
vôùi hash_size =10007 (moät soá nguyeân toá). Giaû söû caùc khoùa coù chieàu daøi 8 kyù töï
hoaëc ít hôn. Moãi kyù töï coù maõ ASCII <=127. Giaù trò cuûa haøm baêm chæ coù theå töø 0
ñeán 127 x 8 = 1016.
Moät caûi tieán khaùc cuûa haøm baêm nhö sau: vôùi giaû thieát raèng caùc khoùa ñeàu coù ít
nhaát 3 kyù töï, soá 27 ñöôïc duøng vì ñoù laø soá kyù töï trong baûng chöõ caùi tieáng Anh
(tính caû khoaûng traéng).
index Hash(const char *Key, int hash_size)
{
return (Key[0] + 27*Key[1] + 27*27*Key[2]) %hash_size;
}
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
319
Chöông 12 – Baûng vaø truy xuaát thoâng tin
Haøm naøy chæ quan taâm 3 kyù töï ñaàu cuûa caùc khoùa, nhöng neáu chuùng laø ngaãu
nhieân vaø hash_size laø 10007 nhö treân, thì söï phaân boå khaù ñoàng ñeàu. Ñieàu khoâng
may ôû ñaây laø caùc töø trong tieáng Anh khoâng phaûi laø moät söï gheùp caùc kyù töï moät
caùch ngaãu nhieân. Maëc duø coù ñeán 263 = 17576 khaû naêng gheùp 3 kyù töï, thöïc teá
trong töø ñieån cho thaáy chæ coù 2851 khaû naêng xaûy ra. Ngay caû khi khoâng coù söï
ñuïng ñoä xaûy ra giöõa töøng caëp trong caùc khaû naêng naøy, thì cuõng chæ coù 28% vò trí
trong baûng laø ñöôïc söû duïng.
Theâm moät caûi tieán khaùc nhö sau ñaây:
index Hash(const char *Key, int hash_size)
{
unsigned int HashVal = 0;
while (*Key != ‘\0’)
{
HashVal = (HashVal << 5 ) + *Key);
Key++;
}
return HashVal % hash_size;
}
Haøm naøy quan taâm ñeán moïi kyù töï trong khoùa vaø noùi chung coù theå phaân boå caùc
khoùa ñoàng ñeàu trong moät baûng kích thöôùc töông ñoái lôùn. Trò cuûa haøm ñöôïc tính
Key[KeySize-i-1].32i. Ñaây laø ña thöùc vôùi heä soá laø 32 vaø söû duïng
KeySize-1
∑
i=0
coâng thöùc Horner. Ví duï, ñeå tính hk = k1 +27k2 +272k3, ngöôøi ta tính
hk = ((k3)*27 +k2)*27 +k1. Vieäc duøng soá 32 thay soá 27 laø vì vôùi 32 thì khoâng
caàn laøm pheùp nhaân maø chæ ñôn giaûn laø pheùp dòch chuyeån bit (32 = 25), vaø thöïc
teá laø duøng pheùp XOR.
Haøm treân ñaây chöa phaûi laø haøm toát nhaát khi xeùt ñeán tieâu chí phaân boå ñoàng
ñeàu, nhöng noù cho pheùp vieäc tính toaùn ñöôïc thöïc hieän raát nhanh choùng. Neáu khoùa
quaù daøi thì noù cuõng loä nhöôïc ñieåm laø phaûi tính quaù laâu. Hôn nöõa quaù trình dòch
bit seõ laøm maát ñi taùc duïng cuûa caùc kyù töï ñaõ ñöôïc xeùt tröôùc. Thöïc teá khaéc phuïc
ñieàu naøy baèng caùch khoâng söû duïng taát caû caùc kyù töï coù trong khoùa.
12.5.2.2. Caét xeùn (truncation)
Phöông phaùp caét xeùn boû qua moät phaàn cuûa khoùa, phaàn coøn laïi ñöôïc xem nhö
chæ soá (caùc döõ lieäu khoâng phaûi soá thì laáy theo baûng maõ cuûa chuùng). Ví duï, neáu
khoùa laø moät soá nguyeân 8 kyù soá vaø baûng baêm coù 1000 vò trí, thì vieäc laáy töø vò trí
thöù nhaát, thöù hai vaø thöù naêm keå töø phaûi sang seõ laø haøm baêm. Coù nghóa laø khoùa
21296876 coù chæ soá laø 976. Caét xeùn laø moät phöông phaùp cöïc nhanh, nhöng noù
thöôøng khoâng phaân phoái caùc khoùa ñeàu khaép baûng baêm.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
320
Chöông 12 – Baûng vaø truy xuaát thoâng tin
12.5.2.3. Xaùo troän (folding)
YÙ töôûng xaùo troän (folding) döôùi ñaây giuùp cho caùc boä phaän cuûa khoùa ñeàu coù theå
tham gia vaøo vieäc xaùc ñònh keát quaû cuoái cuøng cuûa haøm baêm. Töø baêm ôû ñaây coù
nghóa laø keát quaû sinh ra coù phaàn gioáng vôùi khoùa ban ñaàu. Ngoaøi ra, söï xaùo troän
cho pheùp chuùng ta hy voïng raèng moïi khuoân maãu hoaëc söï laëp laïi coù theå xuaát hieän
trong caùc khoùa (haäu quaû cuûa tính thieáu ngaãu nhieân cuûa döõ lieäu trong thöïc teá) seõ bò
trieät tieâu. Coù nhö vaäy thì caùc keát quaû môùi ñöôïc phaân phoái theo cuøng moät quy luaät
nhö nhau maø khoâng coù söï truøng laëp cuûa töøng nhoùm keát quaû vaø chuùng ta traùnh
ñöôïc hieän töôïng gom tuï. ÔÛ ñaây chuùng ta thaáy raèng thuaät ngöõ “baêm” mang tính moâ
taû roõ nhaát. Tuy nhieân trong moät soá taøi lieäu khaùc ngöôøi ta duøng caùc caùc töø mang
tính kyõ thuaät hôn nhö “boä nhôù phaân taùn” (scatter-storage) hoaëc “pheùp bieán ñoåi
khoùa” (key-transformation).
Phöông phaùp xaùo troän chia khoùa laøm nhieàu phaàn vaø keát noái caùc phaàn naøy laïi
theo moät caùch thích hôïp (thöôøng söû duïng pheùp coäng hoaëc pheùp nhaân). Laáy ví duï,
moät soá nguyeân 8 kyù soá coù theå ñöôïc chia laøm 3 nhoùm goàm 3, 3, vaø 2 kyù soá, caùc
nhoùm naøy ñöôïc coäng laïi vôùi nhau, sau ñoù coù theå ñöôïc caét xeùn bôùt neáu caàn thieát ñeå
cho ra caùc chæ soá phuø hôïp kích thöôùc baûng baêm. Khoùa 21296876 seõ ñöôïc baêm
thaønh 212 + 968 + 76 = 1256, caét ngaén coøn 256. Do moïi döõ lieäu trong khoùa ñeàu coù
aûnh höôûng ñeán keát quaû haøm baêm neân phöông phaùp naøy laøm cho caùc khoùa raûi ñeàu
treân baûng baêm hôn laø phöông phaùp caét xeùn neâu treân.
Toùm laïi, chuùng ta ñaõ xem xeùt moät soá phöông phaùp maø chuùng ta coù theå keát hôïp
laïi theo nhieàu caùch khaùc nhau ñeå xaây döïng haøm baêm. Laáy phaàn dö thöôøng laø moät
caùch toát ñeå keát thuùc vieäc tính toaùn cuûa moät haøm baêm, do noù vöøa coù theå ñaït ñöôïc
söï raûi ñeàu caùc khoùa trong baûng baêm vöøa baûo ñaûm keát quaû nhaän ñöôïc luoân naèm
trong mieàn caùc chæ soá cho pheùp.
12.5.3.Phaùc thaûo giaûi thuaät cho caùc thao taùc döõ lieäu trong baûng baêm
Tröôùc heát, chuùng ta caàn khai baùo moät maûng ñeå chöùa baûng baêm. Sau ñoù, caùc vò
trí trong maûng caàn ñöôïc khôûi taïo laø troáng. Giaù trò khôûi taïo phuï thuoäc vaøo öùng
duïng, thoâng thöôøng chuùng ta cho caùc vò trí troáng naøy chöùa moät giaù trò ñaëc bieät
naøo ñoù. Chaúng haïn, vôùi caùc khoùa laø caùc chöõ caùi, moät trò chöùa toaøn kyù töï troáng coù
theå bieåu dieãn moät vò trí troáng.
Ñeå theâm moät phaàn töû vaøo baûng baêm, caàn tính haøm baêm cho khoùa cuûa noù. Neáu
vò trí tìm thaáy coøn troáng, phaàn töû seõ ñöôïc theâm vaøo; neáu ñaõ coù phaàn töû taïi vò trí
naøy vaø khoùa cuûa noù truøng vôùi khoùa cuûa phaàn töû caàn theâm thì vieäc theâm seõ khoâng
ñöôïc thöïc hieän; tröôøng hôïp cuoái cuøng, neáu taïi vò trí tìm thaáy ñaõ coù moät phaàn töû
nhöng cuûa moät khoùa khaùc, chuùng ta seõ aùp duïng moät phöông phaùp giaûi quyeát ñuïng
ñoä naøo ñoù ñeå tìm ñeán moät vò trí khaùc cho vieäc theâm phaàn töû môùi cuûa chuùng ta.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
321
Chöông 12 – Baûng vaø truy xuaát thoâng tin
Vieäc truy xuaát moät phaàn töû vôùi khoùa cho tröôùc ñöôïc laøm töông töï. Tröôùc tieân,
haøm baêm ñöôïc tính cho khoùa cho tröôùc. Neáu phaàn töû caàn tìm ñang naèm taïi vò trí
ñöôïc chæ bôûi haøm baêm, thì vieäc truy xuaát seõ ñöôïc thöïc hieän thaønh coâng; ngöôïc laïi,
trong khi maø vò trí ñang xeùt khoâng troáng vaø moïi vò trí chöa ñöôïc xeùt ñeán, caàn
tieán haønh caùc böôùc töông töï nhö caùc böôùc ñaõ ñöôïc söû duïng khi giaûi quyeát ñuïng ñoä
trong quaù trình theâm vaøo. Neáu trong khi tìm kieám gaëp moät vò trí troáng, hoaëc khi
moïi vò trí ñaõ ñöôïc xeùt ñeán, thì coù theå keát luaän vieäc tìm kieám thaát baïi: khoâng coù
phaàn töû vôùi khoùa caàn tìm trong baûng baêm.
12.5.4.Ví duï trong C++
Nhö moät ví duï ñôn giaûn, chuùng ta seõ vieát moät haøm baêm trong C++ ñeå chuyeån
ñoåi moät khoùa goàm 8kyù töï chöõ caùi sang moät soá nguyeân trong mieàn
0 . . hash_size – 1.
Chuùng ta coù moät lôùp Key vôùi caùc phöông thöùc nhö sau:
class Key: public String{
public:
char key_letter(int position) const;
void make_blank();
// Caùc constructor vaø caùc phöông thöùc khaùc.
};
Ñeå giaûm coâng söùc laäp trình khi hieän thöïc lôùp, chuùng ta choïn caùch thöøa keá caùc
phöông thöùc cuûa lôùp String trong chöông 5. Chuùng ta seõ ñôõ phaûi vieát laïi caùc taùc
vuï so saùnh. Phöông thöùc key_letter(int position) traû veà kyù töï taïi vò trí
positiontrong khoùa, hoaëc traû veà khoaûng traéng neáu khoùa coù chieàu daøi nhoû hôn n.
Phöông thöùc make_blanktaïo moät khoùa troáng.
int hash(const Key &target)
/*
post: Haøm baêm treân target traû veà trò trong mieàn 0 .. hash_size-1.
uses: Caùc phöông thöùc cuûa lôùp Key.
*/
{
int value = 0;
for (int position = 0; position < 8; position++)
value = 4 * value + target.key_letter(position);
return value % hash_size;
}
Haøm baêm treân ñôn giaûn chæ coäng doàn cacù maõ cuûa moãi kyù töï trong khoùa sau khi
ñaõ nhaân vôùi 4. Chuùng ta khoâng theå lyù giaûi ñöôïc raèng phöông phaùp naøy laø toát hôn
(hoaëc xaáu hôn) moät vaøi phöông phaùp khaùc. Chuùng ta cuõng coù theå laáy maõ cuûa kyù töï
tröø ñi moät soá naøo ñoù, roài nhaân töøng caëp vôùi nhau, hoaëc boû qua moät vaøi kyù töï naøo
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
322
Chöông 12 – Baûng vaø truy xuaát thoâng tin
ñoù. Ñoâi khi moät öùng duïng seõ cho thaáy moät haøm baêm naøy laø toát hôn moät haøm baêm
khaùc, ñoâi khi caàn phaûi coù söï khaûo saùt baèng thöïc nghieäm môùi chæ ra ñöôïc haøm naøo
laø toát hôn.
12.5.5.Giaûi quyeát ñuïng ñoä baèng phöông phaùp ñòa chæ môû
Coù hai nhoùm phöông phaùp giaûi quyeát ñuïng ñoä: nhoùm phöông phaùp ñòa chæ môû
vaø nhoùm phöông phaùp noái keát. Nhoùm phöông phaùp ñòa chæ môû chæ söû duïng caùc
maûng caáp phaùt tónh. Nhoùm phöông phaùp noái keát coù söû duïng nhöõng vuøng nhôù caáp
phaùt ñoäng ñöôïc quaûn lyù bôûi caùc con troû noái keát.
Döôùi ñaây laø caùc phöông phaùp duøng ñòa chæ môû.
12.5.5.1. Thöû tuyeán tính
Phöông phaùp ñôn giaûn nhaát ñeå giaûi quyeát ñuïng ñoä laø baét ñaàu töø vò trí traû veà töø
haøm baêm coù xaûy ra ñuïng ñoä, vieäc tìm kieám seõ tieáp tuïc moät caùch tuaàn töï ôû caùc vò
trí keá trong baûng cho ñeán khi gaëp khoùa mong muoán hoaëc moät vò trí troáng. Phöông
phaùp naøy ñöôïc goïi laø phöông phaùp thöû tuyeán tính (linear probing). Baûng ñöôïc xem
nhö moät maûng voøng, khi vieäc tìm kieám ñaït ñeán vò trí cuoái cuûa baûng thì seõ quay veà
vò trí ñaàu cuûa baûng.
Hieän töôïng gom tuï
Nhöôïc ñieåm chính cuûa phöông phaùp thöû tuyeán tính laø khi coù khoaûng moät nöûa
soá vò trí trong baûng ñaõ chöùa döõ lieäu, khuynh höôùng gom tuï seõ xuaát hieän; nghóa laø,
caùc phaàn töû seõ naèm trong caùc chuoãi lieân tuïc caùc vò trí, giöõa caùc chuoãi naøy laø nhöõng
loã hoång. Vieäc tìm kieám tuaàn töï moät vò trí troáng trong baûng seõ ngaøy caøng laâu hôn.
Chuùng ta haõy xem ví duï ôû hình 12.11. Giaû söû maûng coù n vò trí thì xaùc suaát maø
haøm baêm choïn moät vò trí naøo ñoù laø 1/n. Ban ñaàu vieäc phaân phoái ñöôïc thöïc hieän
khaù ñeàu trong baûng (phaàn treân cuûa hình). Giaû söû caàn theâm döõ lieäu môùi maø haøm
baêm traû veà vò trí b thì döõ lieäu ñöôïc theâm vaøo taïi ñaây, nhöng neáu haøm baêm traû veà
vò trí a maø vò trí naøy ñaõ coù döõ lieäu, vieäc theâm vaøo seõ ñöôïc thöïc hieän taïi b. Nhö
vaäy xaùc suaát ñeå vò trí b nhaän döõ lieäu laø 2/n. Taïi böôùc tieáp theo, khi döõ lieäu caàn
theâm vaøo moät trong caùc vò trí a, b, c, hoacë d thì choã troáng thöïc söï ñeå theâm vaøo chæ
laø d, nhö vaäy xaùc suaát döõ lieäu theâm vaøo d laø 4/n. Sau ñoù, xaùc suaát döõ lieäu theâm
vaøo vò trí e laïi laø 5/n. Vaø cöù nhö theá, khi döõ lieäu caøng ñöôïc theâm vaøo nhieàu thì
chuoãi lieân tuïc caùc vò trí ñaõ coù döõ lieäu baét ñaàu töø a ngaøy caøng daøi ra. Nhö vaäy caùch
thöïc hieän cuûa baûng baêm baét ñaàu suy thoaùi daàn tôùi söï tìm kieám tuaàn töï.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
323
Chöông 12 – Baûng vaø truy xuaát thoâng tin
Hình 12.11 – Hieän töôïng gom tuï trong baûng baêm.
Hieän töôïng gom tuï chính laø nguyeân nhaân cuûa tính thieáu oån ñònh. Neáu moät soá
ít caùc khoùa ngaãu nhieân naèm keá nhau, thì sau ñoù caùc khoùa khaùc boãng trôû neân keát
dính vôùi chuùng, coù nghóa laø vò trí chöùa chuùng phuï thuoäc laãn nhau, vaø söï phaân phoái
daàn daàn trôû neân thieáu caân baèng.
12.5.5.2. Haøm gia taêng
Ñeå traùnh hieän töôïng gom tuï, chuùng ta phaûi söû duïng phöông phaùp phöùc taïp hôn
ñeå choïn ra chuoãi caùc vò trí caàn xem xeùt ñeán ñeå theâm moät döõ lieäu môùi naøo ñoù khi
coù xaûy ra ñuïng ñoä. Coù nhieàu caùch ñeå thöïc hieän. YÙ töôûng chung laø söû duïng moät
hoaëc moät vaøi haøm gia taêng ñeå xaùc ñònh khoaûng caùch töø vò trí vöøa ñuïng
ñoä ñeán moät vò trí môùi. Caàn löu yù raèng keát quaû cuûa haøm gia taêng khoâng ñöôïc
pheùp traû veà trò 0.
Haøm gia taêng coù theå phuï thuoäc vaøo khoùa, hoaëc vaøo soá laàn ñaõ thöû, sao cho coù
theå traùnh ñöôïc hieän töôïng gom tuï.
Tröôøng hôïp thöù nhaát, khi haøm gia taêng phuï thuoäc vaøo khoùa, chuùng ta coù
khaùi nieäm baêm laïi. Ñoù laø caùch söû duïng moät haøm baêm thöù hai. Keát quaû cuûa haøm
baêm naøy laø soá vò trí caàn di chuyeån keå töø vò trí ñaõ bò ñuïng ñoä tröôùc ñoù. Neáu vò trí
naøy laïi ñuïng ñoä, chuùng ta laïi duøng moät haøm baêm khaùc nöõa ñeå tìm ñeán vò trí thöù
ba, vaø cöù theá. Cuõng coù khi töø keát quaû tính cuûa haøm baêm thöù hai ngöôøi ta duøng
luoân soá naøy ñeå di chuyeån giöõa hai laàn thöû keá tieáp.
Trong tröôøng hôïp thöù hai, haøm gia taêng phuï thuoäc vaøo soá laàn ñaõ thöû, coù
theå keå ra ñaây phöông phaùp thöû baäc hai.
Thöû baäc hai
Neáu coù söï ñuïng ñoä taïi ñòa chæ baêm ñöôïc h, phöông phaùp thöû baäc hai (quadratic
probing) thöû caùc vò trí keá tieáp laø h+1, h+4, h+9, ... trong baûng, coù nghóa laø caùc
vò trí h + i2, vôùi i laø laàn thöû. Noùi caùch khaùc, haøm gia taêng laø i2.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
324
Tải về để xem bản đầy đủ
34 trang
23920
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật - Phần 2: Các cấu trúc dữ liệu - Chương 12: Bảng và truy xuất thông tin", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_cau_truc_du_lieu_va_giai_thuat_phan_2_cac_cau_tru.pdf
