Bài giảng Cơ sở dữ liệu đa phương tiện - Đỗ Trung Tuấn
Hꢀc viꢁn Công nghꢁ Bưu chính Viꢂn thông
ðꢃ Trung Tuꢄn
Cơ sꢅ dꢆ liꢁu ña phương tiꢁn
Hà Nꢇi, 2010
1
Mꢀc lꢀc
Mꢀc lꢀc........................................................................................................................... 2
Giꢁi thiꢂu........................................................................................................................ 5
Chương I. Tꢃng quan vꢄ cơ sꢅ dꢆ liꢂu ña phương tiꢂn..................................................... 6
1.1 Mꢅ ñꢇu ......................................................................................................... 6
1.2 Khái niꢂm dꢆ liꢂu ña phương tiꢂn ................................................................. 6
1.1.1. Kiꢈu dꢆ liꢂu và ña phương tiꢂn.............................................................. 6
1.1.2. Cơ sꢅ dꢆ liꢂu và hꢂ quꢉn trꢊ cơ sꢅ dꢆ liꢂu .............................................. 7
1.1.3. Tìm kiꢋm thông tin tư liꢂu văn bꢉn ........................................................ 7
1.1.4. Tìm kiꢋm và chꢌ sꢍ hóa ña phương tiꢂn.................................................. 7
1.1.5. Trích ñꢎc trưng, thꢈ hiꢂn nꢏi dung và chꢌ sꢍ hóa .................................... 8
1.3. ðꢎc trưng cꢐa các ñꢍi tưꢑng ña phương tiꢂn ............................................... 8
1.3.1. Sꢒ gia tăng dꢆ liꢂu ña phương tiꢂn và các tính chꢓt cꢐa chúng............... 8
1.3.2. Hꢂ quꢉn trꢊ cơ sꢅ dꢆ liꢂu và vai trò quꢉn lí dꢆ liꢂu ña phương tiꢂn......... 9
1.3.3. Hꢂ thꢍng tìm kiꢋm thông tin ñꢍi vꢁi dꢆ liꢂu ña phương tiꢂn ................ 11
1.3.4. Tiꢋp cꢔn tích hꢑp ñꢈ tìm kiꢋm và chꢌ sꢍ hóa ña phương tiꢂn ................ 11
1.3.5. Tꢃng quan vꢄ hꢂ thꢍng tìm kiꢋm và chꢌ sꢍ hóa ña phương tiꢂn ............ 12
1.4. Cꢓu trúc lưu trꢆ cơ sꢅ dꢆ liꢂu ña phương tiꢂn............................................. 12
1.4.1. Giꢁi thiꢂu ............................................................................................ 13
1.4.2. Cây kꢕD............................................................................................... 13
1.4.3. Cây tꢖ phân......................................................................................... 18
1.4.4. Cây tꢖ phân MX.................................................................................. 21
1.4.5. Cây R.................................................................................................. 24
1.4.6. So sánh các cꢓu trúc dꢆ liꢂu ña phương tiꢂn......................................... 26
1.5. Ngôn ngꢆ thao tác dꢆ liꢂu ña phương tiꢂn.................................................. 27
1.5.1. Giao diꢂn ngưꢗi dùng.......................................................................... 27
1.5.2. Khꢉ năng cꢐa hꢂ thꢍng tìm kiꢋm và chꢌ sꢍ hóa và ꢖng dꢀng ................ 27
1.6. Kꢋt luꢔn..................................................................................................... 28
Chương 2. Tư liꢂu ña phương tiꢂn tương tác.................................................................. 29
2.1 Cơ sꢅ dꢆ liꢂu ña phương tiꢂn tương tác....................................................... 29
2.1.1. Giꢁi thiꢂu ............................................................................................ 29
2.1.2. Kiꢋn trúc cꢐa MIRS............................................................................. 29
2.1.3. Các mô hình dꢆ liꢂu ............................................................................ 31
2.1.4. Thiꢋt kꢋ giao diꢂn ngưꢗi dùng ............................................................. 35
2.2. Mô hình hoá tư liꢂu ña phương tiꢂn tương tác IMD.................................... 37
2.2.1. Mô hình hoá tương tác vꢁi các sꢒ kiꢂn ................................................ 38
2.2.2. Tꢃ hꢑp không gian, thꢗi gian và các nhân tꢍ........................................ 40
2.2.3. Dꢆ liꢂu văn bꢉn ................................................................................... 42
2.2.4. ðꢘ hꢙa vecto và hình ñꢏng .................................................................. 44
2.2.5. Âm thanh............................................................................................. 50
2.2.6. Hình ꢉnh sꢍ ......................................................................................... 57
2.2.7. Video sꢍ .............................................................................................. 64
2.3. Phân loꢚi.................................................................................................... 69
2
2.3.1. Mꢏt sꢍ chuꢛn....................................................................................... 70
2.3.2. Các ñꢎc tính và yêu cꢇu cꢐa dꢆ liꢂu và ꢖng dꢀng ña phương tiꢂn......... 71
2.4 Mô hình kꢊch bꢉn....................................................................................... 74
2.4.1. Kꢊch bꢉn trong IMD ............................................................................ 74
2.4.2. Kꢊch bꢉn ña phương tiꢂn...................................................................... 75
2.5. Tìm kiꢋm tư liꢂu ña phương tiꢂn tương tác................................................. 77
2.5.1. Tìm tư liꢂu ña phương tiꢂn tương tác dꢒa trên cꢓu trúc không gian, thꢗi
gian...................................................................................................................... 78
2.6. Kꢋt luꢔn..................................................................................................... 81
Chương 3. Thành tꢒu và xu hưꢁng ................................................................................ 82
3.1 Các thành tꢒu chính cꢐa công nghꢂ hꢂ quꢉn trꢊ cơ sꢅ dꢆ liꢂu ña phương tiꢂn
................................................................................................................................ 82
3.1.1. Mô hình hoá ........................................................................................ 82
3.1.2. Toàn vꢜn.............................................................................................. 82
3.1.3. Tìm theo nꢏi dung ............................................................................... 82
3.2 Các sꢉn phꢛm thương mꢚi và mꢝu nghiên cꢖu............................................ 86
3.2.1. Mꢏt sꢍ sꢉn phꢛm ................................................................................. 86
3.2.2. Quꢉn lý ña phương tiꢂn ....................................................................... 86
3.2.3. Các vai trò trong dꢒ án ña phương tiꢂn ................................................ 89
3.3. Hưꢁng phát triꢈn cꢐa cơ sꢅ dꢆ liꢂu ña phương tiꢂn..................................... 90
3.3.1. Mꢏt sꢍ hưꢁng hiꢂn tꢚi và khuynh hưꢁng.............................................. 90
3.3.2. An toàn dꢆ liꢂu ña phương tiꢂn............................................................ 91
3.3.3. Yêu cꢇu vꢄ tꢃ chꢖc dꢆ liꢂu ña phương tiꢂn .......................................... 93
3.4. Kꢋt luꢔn..................................................................................................... 95
Chương 4. Quꢉn trꢊ dꢆ liꢂu ña phương tiꢂn.................................................................... 96
4.1. Khái niꢂm vꢄ quꢉn trꢊ cơ sꢅ dꢆ liꢂu ña phương tiꢂn.................................... 96
4.1.1. Dꢚng dꢆ liꢂu ña phương tiꢂn................................................................ 96
4.1.2. Ngôn ngꢆ hꢞi dꢆ liꢂu ña phương tiꢂn................................................... 97
4.1.3. Vꢓn ñꢄ khác......................................................................................... 98
4.2. Kiꢋn trúc hꢂ quꢉn trꢊ cơ sꢅ dꢆ liꢂu ña phương tiꢂn ..................................... 98
4.2.1. Các kiꢋn trúc vꢄ tꢃ chꢖc nꢏi dung........................................................ 98
4.2.2. Nguyên tꢟc tꢒ quꢉn.............................................................................. 98
4.2.3. Nguyên tꢟc ñꢘng ñꢄu........................................................................... 98
4.2.4. Nguyên tꢟc tꢃ chꢖc hꢠn hꢑp ................................................................ 99
4.2.5. Mꢏt sꢍ nhꢔn xét................................................................................... 99
4.2.6. Tꢃ chꢖc cơ sꢅ dꢆ liꢂu dꢒa trên nguyên tꢟc thꢍng nhꢓt........................ 100
4.3. Các kꢡ thuꢔt mô hình hóa dꢆ liꢂu............................................................ 100
4.3.1. Mô hình quan hꢂ................................................................................ 100
4.3.2. Cơ sꢅ dꢆ liꢂu hưꢁng ñꢍi tưꢑng .......................................................... 101
4.3.3. Cơ sꢅ dꢆ liꢂu ña phương tiꢂn............................................................. 107
4.4 Các kĩ thuꢔt chꢌ sꢍ hoá và trꢢu tưꢑng hoá.................................................. 108
4.4.1. Giꢁi thiꢂu .......................................................................................... 108
4.4.2. Chꢌ sꢍ hoá cơ sꢅ dꢆ liꢂu ña phương tiꢂn ............................................ 109
4.4.3. Các chꢌ sꢍ hiꢈn hiꢂn........................................................................... 109
4.4.4. Trꢢu tưꢑng hoá video ........................................................................ 110
4.4.5. ðꢘ thꢊ chuyꢈn cꢉnh............................................................................ 112
3
4.5. Tìm thông tin ña phương tiꢂn dꢒa trên nꢏi dung....................................... 112
4.5.1. Giꢁi thiꢂu vꢄ tìm thông tin ña phương tiꢂn......................................... 112
4.5.2. Lꢙc thông tin..................................................................................... 113
4.5.3. Hꢞi dꢆ liꢂu ña phương tiꢂn ................................................................ 113
4.5.4. Tìm theo nꢏi dung, sꢣ dꢀng tꢢ khoá................................................... 114
4.6. Thí dꢀ vꢄ cơ sꢅ dꢆ liꢂu ña phương tiꢂn..................................................... 114
4.6.1. Mꢏt sꢍ hꢂ thꢍng................................................................................. 114
4.6.2. Tìm các ñꢍi tưꢑng dꢒa trên hình dꢚng................................................ 117
4.6.3. Thꢈ hiꢂn hình dꢚng............................................................................ 118
4.6.4. Viꢂc khꢁp các hình ............................................................................ 118
4.6.5. Các liên kꢋt video ña phương tiꢂn...................................................... 118
4.7. Các ꢖng dꢀng cꢐa ña phương tiꢂn ............................................................ 119
4.7.1. Các hình ꢉnh thô................................................................................ 120
4.7.2. Thꢈ hiꢂn ꢉnh ñã nén........................................................................... 122
4.7.3. Xꢣ lí ꢉnh thông qua viꢂc phân ñoꢚn ꢉnh ............................................ 124
4.7.4. Tìm kiꢋm dꢒa trên sꢒ tương tꢒ........................................................... 126
4.7.5. Tꢃng quát vꢄ cơ sꢅ dꢆ liꢂu ꢉnh .......................................................... 129
4.7.6. Thꢈ hiꢂn cơ sꢅ dꢆ liꢂu ꢉnh nhꢗ mô hình quan hꢂ ............................... 129
4.7.7. Thꢈ hiꢂn cơ sꢅ dꢆ liꢂu ꢉnh trên cây R................................................ 132
4.7.8. Kꢋt luꢔn vꢄ cơ sꢅ dꢆ liꢂu ꢉnh............................................................. 134
4.8. Nhꢔn xét vꢄ dꢆ liꢂu ña phương tiꢂn.......................................................... 134
4.8.1. ðꢉm bꢉo QoS trong hꢂ thꢍng truyꢄn thông, tꢚi máy chꢐ và máy khách
.......................................................................................................................... 134
4.8.2. Mꢏt sꢍ vꢓn ñꢄ khác............................................................................ 135
4.9. Kꢋt luꢔn................................................................................................... 137
Hưꢁng dꢝn sꢣ dꢀng tài liꢂu theo chương trình khung................................................... 138
Tài liꢂu tham khꢉo ...................................................................................................... 142
4
Giꢁi thiꢂu
Trong nhiꢄu năm, nghiên cꢖu và phát triꢈn ña phương tiꢂn là cꢇn thiꢋt trong ꢖng
dꢀng truyꢄn thông và ñꢈ thꢈ hiꢂn thông tin ña phương tiꢂn. Ngày càng nhiꢄu dꢆ liꢂu sꢍ
ña phương tiꢂn ñưꢑc thꢈ hiꢂn dưꢁi dꢚng hình ꢉnh, video, âm thanh… ñòi hꢞi các kĩ
thuꢔt lưu trꢆ, tìm kiꢋm hiꢂu quꢉ và mꢚnh. Ngưꢗi ta có thꢈ so sánh yêu cꢇu này vꢁi yêu
cꢇu thꢈ hiꢂn dꢆ liꢂu kí tꢒ dưꢁi dꢚng tính toán ñưꢑc ꢅ nhꢆng năm 70 cꢐa thꢋ kꢌ XX.
Do vꢔy phát triꢈn vꢄ quꢉn trꢊ dꢆ liꢂu ña phương tiꢂn là bình thưꢗng ñꢍi vꢁi các tꢃ
chꢖc. Trưꢁc hꢋt do nhu cꢇu thꢒc tꢋ, tiꢋp theo là công nghꢂ hiꢂn tꢚi không ñꢐ khꢉ năng
giꢉi quyꢋt vꢓn ñꢄ ñꢍi vꢁi dꢆ liꢂu ña phương tiꢂn. Mꢏt trong nhꢆng khó khăn là viꢂc chꢌ
sꢍ hóa và tìm kiꢋm dꢆ liꢂu ña phương tiꢂn.
Ngưꢗi ta thꢓy cꢇn biꢋt công nghꢂ hiꢂn tꢚi cꢐa quꢉn lí dꢆ liꢂu ña phương tiꢂn. ðꢇu
tiên là các ñꢎc tính cꢐa dꢆ liꢂu ña phương tiꢂn và các khía cꢚnh vꢄ thiꢋt kꢋ cho phép hꢂ
thꢍng cơ sꢅ dꢆ liꢂu ña phương tiꢂn ñáp ꢖng các yêu cꢇu vꢄ dꢆ liꢂu. ðꢍi vꢁi tꢢng loꢚi dꢆ
liꢂu ña phương tiꢂn, như văn bꢉn, hình ꢉnh, âm thanh và video, cꢇn có kĩ thuꢔt chꢌ sꢍ
hóa riêng, ꢖng vꢁi ñꢎc tính chính cꢐa dꢆ liꢂu thô. Công cꢀ tìm kiꢋm dꢆ liꢂu ña phương
tiꢂn cꢇn lꢏ ñưꢑc câu hꢞi ngưꢗi dùng, dꢒa trên mꢖc ñꢏ tương tꢒ cꢐa mꢝu và dꢆ liꢂu ñã
lưu trꢆ. Viꢂc tìm kiꢋm và chꢌ sꢍ hóa theo nꢏi dung dꢆ liꢂu ña phương tiꢂn là quan trꢙng
và khó khăn, do các khía cꢚnh rút tꢢ dꢆ liꢂu thô thưꢗng ñưꢑc thꢈ hiꢂn qua vecto nhiꢄu
chiꢄu, ñòi hꢞi nhiꢄu thꢗi gian xꢣ lí.
Các kĩ thuꢔt và các cꢓu trúc dꢆ liꢂu có vai trò liên quan ñꢋn hiꢂu quꢉ tìm kiꢋm dꢆ
liꢂu. Cơ sꢅ dꢆ liꢂu ña phương tiꢂn vꢁi truy cꢔp tꢢ xa, qua mꢚng máy tính, theo mô hình
khách/ chꢐ… sꢤ phꢉi xꢣ lí các tình huꢍng liên quan ñꢋn truyꢄn dꢆ liꢂu, mã hóa dꢆ liꢂu.
Vꢔy kiꢋn trúc máy tính, viꢂc lưu trꢆ ña phương tiꢂn, hꢂ thꢍng ñiꢄu hành, hꢚ tꢇng mꢚng
cꢇn ñưꢑc quan tâm.
Trong hꢂ quꢉn trꢊ cơ sꢅ dꢆ liꢂu truyꢄn thꢍng, hiꢂu năng liên quan ñꢋn tính hiꢂu quꢉ,
theo thꢗi gian trꢉ lꢗi câu hꢞi. Trong hꢂ thꢍng ña phương tiꢂn, hiꢂu quꢉ cũng quan trꢙng,
nhưng hiꢂu quꢉ ñꢍi vꢁi tìm kiꢋm, ñꢍi vꢁi ñꢍi tưꢑng ñã có và phát hiꢂn ñꢍi tưꢑng tiꢄm
ꢛn, là có ý nghĩa. Ngưꢗi ta ñꢄ cꢔp ñiꢄu này do viꢂc tìm kiꢋm ꢅ ñó theo so sánh tương tꢒ,
và các dꢆ liꢂu cũng không cho phép so sánh khꢁp. Do vꢔy ñꢏ ño hiꢂu quꢉ là cꢇn thiꢋt
ñꢍi vꢁi hꢂ quꢉn trꢊ cơ sꢅ dꢆ liꢂu ña phương tiꢂn. Mꢏt sꢍ khía cꢚnh khác, như an toàn dꢆ
liꢂu, chuꢛn… cũng ñáng ñưꢑc quan tâm.
5
Chương I. Tꢃng quan vꢄ cơ sꢅ dꢆ liꢂu ña phương tiꢂn
1.1 Mꢀ ñꢁu
Các nghiên cꢖu và phát triꢈn vꢄ ña phương tiꢂn nhꢥm vào truyꢄn thông và thꢈ hiꢂn
dꢆ liꢂu ña phương tiꢂn, xác ñꢊnh quyꢄn tác giꢉ. Hꢂ quꢉn trꢊ cơ sꢅ dꢆ liꢂu ña phương tiꢂn
giꢆ vai trò như hꢂ quꢉn trꢊ truyꢄn thꢍng, khác là dꢆ liꢂu phꢖc tꢚp và ña dꢚng. ðꢈ ñꢉm
bꢉo tính hiꢂu quꢉ truy cꢔp và tìm kiꢋm, hꢂ quꢉn trꢊ cꢇn có kĩ thuꢔt tìm kiꢋm và chꢌ sꢍ
hóa khác.
Vꢔy viꢂc chꢌ sꢍ hóa và tìm kiꢋm ña phương tiꢂn là mꢀc ñích chính, trưꢁc khi xem
xét các chꢖc năng cꢐa hꢂ quꢉn trꢊ. Phꢇn ñꢇu sꢤ thꢈ hiꢂn hꢂ thꢍng chꢌ sꢍ hóa và tìm kiꢋm
MIRS1 và mꢏt vài ꢖng dꢀng chung cꢐa nó.
Hình. Mꢇt sꢈ logo ña phương tiꢂn
1.2 Khái niꢂm dꢃ liꢂu ña phương tiꢂn
Cꢇn thiꢋt xác ñꢊnh tꢢ ñꢇu mꢏt sꢍ khái niꢂm, ñꢊnh nghĩa sꢣ dꢀng trong suꢍt quá trình
liên quan ñꢋn hꢂ thꢍng ña phương tiꢂn.
1.1.1. Kiꢀu dꢁ liꢂu và ña phương tiꢂn
ðꢀnh nghĩa: Phương tiꢁn2: phương tiꢁn nhꢂm ñꢃn các kiꢄu thông tin hay kiꢄu thꢄ
hiꢁn thông tin, như dꢅ liꢁu sꢆ, chꢅ, hình ꢇnh, âm thanh, video.
Có nhiꢄu cách xác ñꢊnh phương tiꢂn. Phân loꢚi thông thưꢗng dꢒa vào dꢚng vꢔt lí và
mꢍi quan hꢂ phương tiꢂn vꢁi thꢗi gian. ꢦ ñây xác ñꢊnh phương tiꢂn không ñꢄ cꢔp yꢋu tꢍ
thꢗi gian. Thꢗi gian cho phép xác ñꢊnh phương tiꢂn tĩnh vꢁi phương tiꢂn ñꢏng, tꢖc thꢗi
gian liên tꢀc.
ðꢀnh nghĩa: Phương tiꢁn tĩnh3: phương tiꢁn không có chiꢈu thꢉi gian, và nꢊi dung
và ý nghĩa cꢋa chúng không phꢌ thuꢊc vào thꢉi gian thꢄ hiꢁn.
Các phương tiꢂn tĩnh gꢘm dꢆ liꢂu sꢍ, chꢆ, ñꢏ hꢙa, hình tĩnh. Hình tĩnh ñưꢑc xem
là sꢉn phꢛm ñưꢑc vꢤ, quét hay chꢀp bꢥng máy chꢀp ꢉnh.
1 multimedia indexing and retrieval systems
2 media
3 static media
6
ðꢀnh nghĩa: Phương tiꢁn ñꢊng1: phương tiꢁn có các chiꢈu thꢉi gian, vꢍi ý nghĩa
và tính chính xác tùy theo tꢆc ñꢊ thꢄ hiꢁn.
Phương tiꢂn ñꢏng gꢘm hình ñꢏng, âm thanh và video. Các phương tiꢂn này có
khoꢉng ñơn vꢊ bên trong hay tꢍc ñꢏ. Chꢧng hꢚn video có 25 khung trong mꢏt giây. Viꢂc
thꢈ hiꢂn lꢚi cꢇn theo cách tꢃ chꢖc trưꢁc ñó. Do các phương tiꢂn này thꢈ hiꢂn lꢚi liên tꢀc
theo tꢍc ñꢏ cꢍ ñꢊnh, chúng ñưꢑc gꢙi là phương tiꢂn liên tꢀc. Ngưꢗi ta cũng gꢙi chúng là
phương tiꢂn ñꢧng thꢗi, tꢖc chiꢋm thꢗi gian như nhau, bꢅi quan hꢂ cꢍ ñꢊnh giꢆa các ñơn
vꢊ phương tiꢂn và thꢗi gian.
ða phương tiꢂn nhꢥm vào tꢔp các kiꢈu phương tiꢂn sꢣ dꢀng cùng nhau. Nó cũng
ngꢇm xác ñꢊnh có kiꢈu dꢆ liꢂu khác sꢍ, chꢆ. Do vꢔy thuꢔt ngꢆ “ña phương tiꢂn” cũng
nhꢥm chꢌ tính chꢓt như tính tꢢ.
ðꢀnh nghĩa: Dꢅ liꢁu ña phương tiꢁn2: dꢅ liꢁu hưꢍng ñꢃn thꢄ hiꢁn máy ñꢎc ñưꢏc
cꢋa các kiꢄu phương tiꢁn gꢊp.
Thông tin ña phương tiꢂn hưꢁng tꢁi thông tin ñưꢑc truyꢄn tꢉi nhꢗ các kiꢈu phương
tiꢂn gꢏp. ðôi khi ngưꢗi ta dùng lꢝn dꢆ liꢂu ña phương tiꢂn vꢁi thông tin ña phương tiꢂn.
Ngưꢗi ta cũng sꢣ dꢀng thuꢔt ngꢆ ña phương tiꢂn và phương tiꢂn ñꢈ chꢌ thꢒc thꢈ tꢒ trꢊ
trong MIRS, cho phép hꢞi, tìm kiꢋm và thꢈ hiꢂn. Thuꢔt ngꢆ “ñꢍi tưꢑng” không hoàn
toàn chính xác như trong tiꢋp cꢔn hưꢁng ñꢍi tưꢑng.
1.1.2. Cơ sꢃ dꢁ liꢂu và hꢂ quꢄn trꢅ cơ sꢃ dꢁ liꢂu
Trong tài liꢂu vꢄ cơ sꢅ dꢆ liꢂu, hꢂ thꢍng cơ sꢅ dꢆ liꢂu ñã phân biꢂt hꢂ quꢉn trꢊ cơ sꢅ
dꢆ liꢂu DBMS vꢁi cơ sꢅ dꢆ liꢂu DB3. Giꢆa nhꢆng vꢓn ñꢄ vꢄ ña phương tiꢂn này, ñôi
khi lꢝn lꢏn hai thuꢔt ngꢆ.
ðꢀnh nghĩa: Hꢁ quꢇn trꢀ cơ sꢐ dꢅ liꢁu4: phꢑn mꢈm cho phép mô tꢇ, lưu trꢅ và xꢒ
lí các dꢅ liꢁu mꢊt cách khoa hꢎc.
1.1.3. Tìm kiꢆm thông tin tư liꢂu văn bꢄn
Hꢂ thꢍng tìm kiꢋm thông tin tꢒ ñꢏng IR5 ñưꢑc phát triꢈn ñꢈ xꢣ lí khꢍi lưꢑng lꢁn các
tài liꢂu khoa hꢙc tꢢ 1940. Chꢖc năng chính cꢐa hꢂ thꢍng là lưu và quꢉn lí sꢍ lꢁn các tư
liꢂu văn bꢉn theo cách tìm kiꢋm nhanh tư liꢂu hiꢂn ra cho câu hꢞi ngưꢗi dùng.
ðꢀnh nghĩa: Hꢁ thꢆng tìm thông tin tꢓ ñꢊng (IR): hꢁ thꢆng là lưu và quꢇn lí sꢆ lꢍn
các tư liꢁu văn bꢇn theo cách tìm kiꢃm nhanh tư liꢁu hiꢁn ra ñꢆi vꢍi câu hꢔi ngưꢉi
dùng.
1.1.4. Tìm kiꢆm và chꢇ sꢈ hóa ña phương tiꢂn
Viꢂc tìm kiꢋm trong DBMS dꢒa trên cꢓu trúc dꢆ liꢂu cho phép so sánh khꢁp. IR
ñưꢑc xem là hꢂ thꢍng tìm kiꢋm theo văn bꢉn. Viꢂc tìm kiꢋm theo nꢏi dung dꢒa trên ñꢎc
trưng phương tiꢂn thꢒc tꢚi như màu sꢟc, hình dáng, thay vì ghi chú, diꢨn giꢉi văn bꢉn
cꢐa phương tiꢂn.
1 dynamic media
2 multimedia data
3 DBMS Database Management Systems, DB Database
4 DBMS
5 information retrieval
7
ðꢀnh nghĩa: Tìm kiꢃm theo theo nꢊi dung1: tìm kiꢃm dꢓa trên ñꢕc trưng thꢓc tꢖi
như màu sꢗc, hình dáng… cꢋa phương tiꢁn.
Tìm kiꢋm theo nꢏi dung thưꢗng dꢒa vào tính tương tꢒ, thay vì so sánh khꢁp giꢆa
câu hꢞi và tꢔp các mꢀc tin cꢐa cơ sꢅ dꢆ liꢂu. ꢦ hꢂ thꢍng ña phương tiꢂn, MIRS hưꢁng
ñꢋn tìm kiꢋm theo cꢉ (i) DBMS; (ii) IR; (iii) theo nꢏi dung.
1.1.5. Trích ñꢉc trưng, thꢀ hiꢂn nꢊi dung và chꢇ sꢈ hóa
ðꢀnh nghĩa: ðꢕc trưng là ñiꢄm nꢘi bꢙt, giúp phân biꢁt cá thꢄ ñã cho vꢍi các cá
thꢄ khác mà ta có thꢄ ñem ra so sánh.
Trong MIRS, trích ñꢎc trưng hay thꢈ hiꢂn nꢏi dung, tꢖc ñꢎc trưng chính và nꢏi
dung trong mꢀc tin, là viꢂc quan trꢙng. Quá trình trích ñꢎc trưng có thꢈ thꢒc hiꢂn tꢒ
ñꢏng hay bán tꢒ ñꢏng. Trong vài tư liꢂu vꢄ tìm theo nꢏi dung, thuꢔt ngꢆ “trích ñꢎc
trưng” cũng dùng cho viꢂc chꢌ sꢍ hóa.
Do vꢔy, khi sꢣ dꢀng “chꢌ sꢍ”, ngưꢗi ta nhꢥm ñꢋn cꢓu trúc dꢆ liꢂu hay tꢃ chꢖc các
ñꢎc trưng ñưꢑc rút ra ñꢈ tìm hiꢂu quꢉ.
1.3. ðꢄc trưng cꢅa các ñꢆi tưꢇng ña phương tiꢂn
ðꢄ cꢔp nhu cꢇu vꢄ hꢂ thꢍng chꢌ sꢍ hóa và tìm kiꢋm ña phương tiꢂn, ngưꢗi ta thꢓy
ba viꢂc sau ñây cho thꢓy MIRS có ý nghĩa:
1. Ngày càng nhiꢄu dꢆ liꢂu ña phương tiꢂn ñưꢑc thu thꢔp và lưu trꢆ;
2. Dꢆ liꢂu ña phương tiꢂn khác vꢁi dꢆ liꢂu truyꢄn thꢍng ꢅ tính chꢓt riêng, có yêu cꢇu
và ý nghĩa khác;
3. Cho dù các kĩ thuꢔt IR có thꢈ dùng ñꢈ tìm kiꢋm ña phương tiꢂn, nhưng mꢏt mình nó
không ñꢉm bꢉo tính hiꢂu quꢉ ñꢍi vꢁi xꢣ lí dꢆ liꢂu ña phương tiꢂn.
ðꢀnh nghĩa: ðꢆi tưꢏng là mꢊt vꢙt, khái niꢁm hay thꢓc thꢄ.
1.3.1. Sꢋ gia tăng dꢁ liꢂu ña phương tiꢂn và các tính chꢌt cꢍa chúng
Không thꢈ không ñꢍi mꢎt vꢁi thông tin ña phương tiꢂn. Ngưꢗi ta không thꢈ tránh
hꢋt các dꢆ liꢂu âm thanh và tranh, ꢉnh. Xu hưꢁng sꢣ dꢀng dꢆ liꢂu ña phương tiꢂn làm
tăng công nghꢂ lưu trꢆ sꢍ. Dꢨ dàng ñáp ꢖng nhu cꢇu ña phương tiꢂn nhꢞ, nhưng ñꢍi vꢁi
yêu cꢇu toàn diꢂn, ñòi hꢞi cꢉ hꢂ thꢍng tꢃ chꢖc dꢆ liꢂu, tìm kiꢋm nhanh.
Hình. Sꢉ dꢀng khái niꢂm ña phương tiꢂn: máy bay vưꢊt ngưꢋng âm thanh
Ngưꢗi ta không chꢌ chꢊu sꢖc ép vꢄ khꢍi lưꢑng dꢆ liꢂu, mà còn các kiꢈu dꢆ liꢂu ña
1 Contentꢕbased retrieval
8
dꢚng và các tính chꢓt khác vꢁi dꢆ liꢂu sꢍ, chꢆ truyꢄn thꢍng. Các tính chꢓt chính cꢐa dꢆ
liꢂu ña phương tiꢂn ñưꢑc liꢂt kê:
• Dꢆ liꢂu ña phương tiꢂn, ñꢎc biꢂt dꢆ liꢂu âm thanh, video là nhꢆng dꢆ liꢂu ñưꢑc nén
vꢁi tꢌ lꢂ cao, khoꢉng 1 Gb chꢌ chꢖc ñưꢑc khoꢉng 10 phút video;
• Dꢆ liꢂu âm thanh và video có chiꢄu thꢗi gian, ñòi hꢞi thꢈ hiꢂn theo tꢍc ñꢏ cꢍ ñꢊnh ñꢈ
ñꢚt hiꢂu quꢉ dꢒ ñꢊnh;
• Các dꢆ liꢂu âm thanh, hình ꢉnh và video sꢍ ñưꢑc thꢈ hiꢂn theo mꢏt loꢚt các mꢝu
riêng, do vꢔy khó tꢒ ñꢏng ghi nhꢔn nꢏi dung bꢅi không dꢨ xác ñꢊnh cꢓu trúc ngꢆ
nghĩa cꢐa chúng;
• Nhiꢄu ꢖng dꢀng ña phương tiꢂn cꢇn thꢈ hiꢂn ñꢘng thꢗi cꢐa nhiꢄu dꢚng phương tiꢂn
theo cách tương ꢖng vꢁi không gian và thꢗi gian;
• Ý nghĩa cꢐa dꢆ liꢂu ña phương tiꢂn thưꢗng mꢗ và chꢐ quan, không tiꢂn xác ñꢊnh rõ;
• Dꢆ liꢂu ña phương tiꢂn mang nhiꢄu thông tin, ñòi hꢞi nhiꢄu tham sꢍ thꢈ hiꢂn nꢏi
dung.
Hình. Hình ñꢇng tꢌo bꢅi các khung
1.3.2. Hꢂ quꢄn trꢅ cơ sꢃ dꢁ liꢂu và vai trò quꢄn lí dꢁ liꢂu ña phương tiꢂn
ðꢀnh nghĩa: Hꢁ quꢇn trꢀ cơ sꢐ dꢅ liꢁ, DBMS, là phꢑn mꢈm cho phép mô tꢇ, lưu
trꢅ và xꢒ lí dꢅ liꢁu mꢊt cách khoa hꢎc.
Các DBMS truyꢄn thꢍng phù hꢑp vꢁi dꢆ liꢂu có cꢓu trúc. Mô hình dꢆ liꢂu quan hꢂ
là mô hình thông dꢀng tꢢ 1980 ñꢋn nay. Dꢆ liꢂu theo mô hình quan hꢂ ñưꢑc tꢃ chꢖc
trong các bꢉng quan hꢂ, có thuꢏc tính và các n_bꢏ. Có ba lꢁp ngôn ngꢆ hꢞi dꢆ liꢂu,
nhưng ngôn ngꢆ ñꢚi sꢍ quan hꢂ mà ñꢚi diꢂn là SQL ñưꢑc sꢣ dꢀng nhiꢄu.
Thí dꢀ
create table STUDENT (
stu# integer,
name char (20),
address char (100) );
và câu bꢃ sung dꢆ liꢂu
insert into STUDENT values (10, "Lew, Tom", "2 Main St.,
Churchill, Australia");
Bꢍng. Dꢆ liꢂu thí dꢀ
9
Tìm kiꢋm dꢆ liꢂu
select name
from STUDENT
where stu# = 32
Thuꢏc tính trong DBMS là dꢆ liꢂu theo kiꢈu cꢍ ñꢊnh, chꢧng hꢚn sꢍ nguyên, chiꢋm
32 bit. ðꢈ trꢑ giúp các biꢋn ñꢏ dài thay ñꢃi, ngưꢗi ta ñưa ra khái niꢂm ñꢍi tưꢑng nhꢊ
phân lꢁn BLOB1.
ðꢀnh nghĩa: BLOB2: BLOB là xâu bit lꢍn có ñꢊ dài thay ñꢘi.
Thí dꢀ cꢇn lưu ꢉnh cꢐa sinh viên
create table STUDENT (
stu# integer,
name char (20),
address char (100)
picture BLOB);
BLOB chꢌ là xâu bit, nên DBMS quan hꢂ không biꢋt nꢏi dung hay ngꢆ nghĩa cꢐa
nó, mà chꢌ xem như khꢍi dꢆ liꢂu.
DBMS hưꢁng ñꢍi tưꢑng kꢋt hꢑp nhiꢄu khía cꢚnh cꢐa quꢉn trꢊ dꢆ liꢂu, như lưu trꢆ
và tìm kiꢋm, vꢁi tiꢋp cꢔn hưꢁng ñꢍi tưꢑng, vꢁi khía cꢚnh ñóng gói, thꢢa kꢋ, xác ñꢊnh
ñꢍi tưꢑng. Ngưꢗi ta cũng tꢒ hꢞi liꢂu tꢍt không nꢋu kꢋt hꢑp mô hình quan hꢂ vꢁi mô
hình hưꢁng ñꢍi tưꢑng, trong khi chưa có mô hình dꢆ liꢂu ña phương tiꢂn. Các ñꢍi tưꢑng
ña phương tiꢂn ñưꢑc nhꢔn thꢖc theo tiꢋp cꢔn hưꢁng ñꢍi tưꢑng sꢤ phù hꢑp và dꢨ thꢈ hiꢂn
lꢚi hơn. Hꢂ thꢍng quan hꢂ ñꢍi tưꢑng cho phép (i) xác ñꢊnh ñꢍi tưꢑng theo nghĩa hưꢁng
ñꢍi tưꢑng; (ii) sꢣ dꢀng chꢖc năng xꢣ lí dꢆ liꢂu quan hꢂ ñã có.
Thí dꢀ: xác ñꢊnh kiꢈu dꢆ liꢂu hình ꢉnh:
create type IMAGE (
private
size integer,
resolution integer,
content float[],
public
...
);
Và sꢣ dꢀng nó trong
create table STUDENT (
stu# integer,
name char (20),
1 binary large object
2 binary large object
10
address char (100)
picture IMAGE);
Khác nhau chính giꢆa BLOB và các ñꢍi tưꢑng là các ñꢍi tưꢑng ñưꢑc xác ñꢊnh phù
hꢑp, vꢁi thuꢏc tính và chꢊu các phép xꢣ lí trên thuꢏc tính, mà BLOB không thꢈ. Khái
niꢂm vꢄ BLOB và các ñꢍi tưꢑng cũng ñánh dꢓu mꢏt bưꢁc quꢉn lí dꢆ liꢂu ña phương
tiꢂn, nhưng BLOB chꢌ dùng ñꢈ lưu trꢆ dꢆ liꢂu, trong lúc các ñꢍi tưꢑng cꢇn nhiꢄu thuꢏc
tính ñꢈ thꢈ hiꢂn nꢏi dung dꢆ liꢂu. Các tính năng cꢇn phát triꢈn cho dꢆ liꢂu ña phương
tiꢂn là:
• Công cꢀ trích rút nꢏi dung và ñꢎc trưng ña phương tiꢂn, tꢒ ñꢏng hay bán tꢒ
ñꢏng, trong các dꢆ liꢂu ña phương tiꢂn;
• Cꢓu trúc chꢌ sꢍ ñꢈ quꢉn lí các vecto ñꢎc trưng ña phương tiꢂn;
• ðꢏ ño tính tương tꢒ, trong tìm kiꢋm thay cho so sánh khꢁp;
• Hꢂ thꢍng lưu trꢆ phân tán ñꢍi vꢁi dꢆ liꢂu lꢁn và hꢚ tꢇng truyꢄn thông ñꢍi vꢁi
yêu cꢇu thꢗi gian thꢒc;
• Giao diꢂn ngưꢗi dùng, thiꢋt kꢋ cho kiꢈu dꢆ liꢂu ña phương tiꢂn khác nhau và cho
phép thꢈ hiꢂn ña dꢚng.
1.3.3. Hꢂ thꢈng tìm kiꢆm thông tin ñꢈi vꢎi dꢁ liꢂu ña phương tiꢂn
ðꢀnh nghĩa: Công cꢌ tìm kiꢃm là mꢊt phꢑn mꢈm nhꢂm cho phép ngưꢉi dùng tìm
kiꢃm và ñꢎc các thông tin có trong phꢑn mꢈm ñó, trên mꢊt trang Web, hay trên
toàn bꢊ Internet.
Hꢂ thꢍng IR dùng cho dꢆ liꢂu văn bꢉn. Các kĩ thuꢔt sꢣ dꢀng trong IR quan trꢙng
nhꢗ (i) nhiꢄu tư liꢂu văn bꢉn trong tꢃ chꢖc; (ii) văn bꢉn có thꢈ minh hꢙa cho phương
tiꢂn khác, như âm thanh, hình ꢉnh, video. Ngưꢗi ta có thꢈ sꢣ dꢀng kĩ thuꢔt IR ñꢍi vꢁi dꢆ
liꢂu ña phương tiꢂn. Tuy nhiên chúng có vài hꢚn chꢋ:
• Minh hꢙa, ghi chú cho phương tiꢂn khác thưꢗng thꢒc hiꢂn thꢐ công, tꢍn thꢗi
gian;
• Minh hꢙa bꢥng văn bꢉn không thꢈ ñꢐ và chꢐ quan;
• Các kĩ thuꢔt IR chꢌ cho phép hꢞi theo văn bꢉn;
• Mꢏt vài ñꢎc trưng ña phương tiꢂn như bꢄ mꢎt ꢉnh, hình dáng ñꢍi tưꢑng là phꢖc
tꢚp, không dùng văn bꢉn mà mô tꢉ hꢋt.
1.3.4. Tiꢆp cꢏn tích hꢐp ñꢀ tìm kiꢆm và chꢇ sꢈ hóa ña phương tiꢂn
Dù hꢂ thꢍng tìm kiꢋm thông tin IR có ích trong khung cꢉnh xꢣ lí dꢆ liꢂu ña phương
tiꢂn, ñꢍi vꢁi dꢆ liꢂu có cꢓu trúc, ngưꢗi ta cꢇn kĩ thuꢔt mꢁi ñꢈ quꢉn lí các tính chꢓt riêng
cꢐa dꢆ liꢂu ña phương tiꢂn.
Ngoài các kĩ thuꢔt xꢣ lí dꢆ liꢂu cꢐa DBMS truyꢄn thꢍng ñꢍi vꢁi dꢆ liꢂu có cꢓu trúc,
viꢂc tích hꢑp thêm các kĩ thuꢔt cho dꢆ liꢂu hình ꢉnh, âm thanh, video sꢤ cho phép hꢂ
thꢍng tìm kiꢋm và chꢌ sꢍ hóa ña phương tiꢂn MIRS.
ðꢀnh nghĩa: Chꢚ sꢆ là hꢁ thꢆng dùng ñꢄ tìm kiꢃm thông tin nhanh và dꢛ hơn.
11
1.3.5. Tꢑng quan vꢒ hꢂ thꢈng tìm kiꢆm và chꢇ sꢈ hóa ña phương tiꢂn
Trong hꢂ thꢍng MIRS, mꢀc tin trong cơ sꢅ dꢆ liꢂu ñưꢑc tiꢄn xꢣ lí ñꢈ rút các ñꢎc
trưng và nꢏi dung ngꢆ nghĩa. Các mꢀc tin này ñưꢑc chꢌ sꢍ hóa nhꢥm tăng tꢍc tìm kiꢋm.
Các câu hꢞi ngưꢗi dùng ñưꢑc trích ñꢎc trưng, so sánh tương tꢒ vꢁi ñꢎc trưng ñã ñưꢑc
chꢌ sꢍ.
C©u hái
c¸c môc tin
Xö lÝ vꢀ trÝch ®Æc tr−ng
Xö lÝ vꢀ chØ sè hãa
§Æc tr−ng
c©u hái
c¸c môc tin ®−îc
chØ sè hãa
So s¸nh
t−¬ng tù
T×m c¸c môc tin t−¬ng tù
Hình. Mô hình tìm kiꢎm thông tin tꢃng quát
Còn mꢏt sꢍ vꢓn ñꢄ: (i) mꢀc tin có chꢖa kiꢈu phương tiꢂn ?; (ii) cách rút ñꢎc trưng tꢢ
các mꢀc tin phương tiꢂn; (iii) ñꢏ ño tương tꢒ, vꢁi khung nhìn ña dꢚng cꢐa ngưꢗi dùng;
(iv) ñánh giá hiꢂu quꢉ tìm kiꢋm.
ðꢀnh nghĩa: Thꢀ giác là khꢇ năng nhꢙn và diꢛn giꢇi thông tin tꢜ ánh sáng ñi vào
mꢗt. Viꢁc tri giác này còn ñưꢏc gꢎi là thꢀ lꢓc, sꢓ nhìn.
Hình. Giác quan cꢏa con ngưꢐi
1.4. Cꢈu trúc lưu trꢃ cơ sꢀ dꢃ liꢂu ña phương tiꢂn
Khi ñꢄ cꢔp vꢄ cꢓu trúc dꢆ liꢂu ña phương tiꢂn, mꢏt ñiꢈm cꢇn lưu ý trưꢁc tiên là dꢆ
liꢂu ña phương tiꢂn luôn mang khía cꢚnh (i) không gian và (ii) thꢗi gian. Không gian
ñꢍi vꢁi dꢆ liꢂu ña phương tiꢂn thưꢗng nhiꢄu chiꢄu.
ðꢀnh nghĩa: Cꢝu trúc dꢅ liꢁu là cách lưu trꢅ và tꢘ chꢞc dꢅ liꢁu cꢌ thꢄ trong máy
tính ñꢄ các dꢅ liꢁu ñưꢏc sꢒ dꢌng hiꢁu quꢇ.
Ngưꢗi ta quan tâm viꢂc nhꢔn thꢖc các dꢆ liꢂu ña phương tiꢂn, cách hình thꢖc hoá
chúng. Các khái niꢂm ña phương tiꢂn cꢇn ñưꢑc áp phương pháp hình thꢖc ñꢈ có thꢈ
phát triꢈn ꢖng dꢀng. Hꢇu hꢋt các dꢆ liꢂu n chiꢄu ñꢄu dùng cách thꢈ hiꢂn phân rã theo
cây thông tin.
12
ðꢈ hình thꢖc hoá, trꢢu tương hoá dꢆ liꢂu ña phương tiꢂn, ngưꢗi ta cꢇn ñꢋn các kĩ
thuꢔt như cây kꢕchiꢄu, cây tꢖ phân theo ñiꢈm, cây tꢖ phân, cây R. ðꢘng thꢗi còn phꢉi
quan tâm ñꢋn các phương pháp cài ñꢎt các kĩ thuꢔt này.
ðꢀnh nghĩa: Không gian, thꢉi gian: Không gian là mꢐ rꢊng ba chiꢈu, không giꢍi
hꢖn, trong ñó các ñꢆi tưꢏng và các sꢓ kiꢁn xꢇy ra và có vꢀ trí và hưꢍng tương ñꢆi.
Thꢉi gian là mꢊt phꢑn cꢋa hꢁ thꢆng ño, dùng cho các sꢓ kiꢁn tuꢑn tꢓ, ñꢄ so sánh
thꢉi lưꢏng cꢋa các sꢓ kiꢁn và khoꢇng thꢉi gian giꢅa chúng, và ñꢄ lưꢏng hóa tꢚ lꢁ
thay ñꢘi chuyꢄn ñꢊng cꢋa các ñꢆi tưꢏng.
1.4.1. Giꢎi thiꢂu
Dꢚng tꢃ chꢖc dꢆ liꢂu ñꢊa lí thông dꢀng như GIS, thꢈ hiꢂn ꢅ dꢚng bꢉn ñꢘ, tꢖc các
ñiꢈm. Mꢠi ñiꢈm không gian ñưꢑc thꢈ hiꢂn qua cꢓu trúc dꢆ liꢂu.
Dꢆ liꢂu ñꢊa lí ña dꢚng, có thꢈ thꢓy như ñiꢈm, ñưꢗng thꢧng, các ñưꢗng cong, các
hình, các bꢉn ñꢘ, các dꢆ liꢂu gꢟn vꢁi bꢉn ñꢘ theo các tꢇng ñꢊa lí khác nhau. Các thông
tin này thay ñꢃi theo thꢗi gian...
1.4.2. Cây kꢓD
Sꢣ dꢀng cây kꢕd ñꢈ lưu trꢆ các ñiꢈm cꢐa bꢉn ñꢘ.
ðꢀnh nghĩa: Cây là cꢝu trúc dꢅ liꢁu thông dꢌng, thꢄ hiꢁn cꢝu trúc dꢅ liꢁu phân
cꢝp vꢍi tꢙp các nút liên kꢃt nhau. Vꢈ toán hꢎc, cây là ñꢟ thꢀ không xoay vòng cꢋa
các nút; mꢠi nút có các nút con, và thuꢊc vꢈ mꢊt nút cha.
1.4.2.1. Cꢀu trúc nút
Nút cꢐa cây kꢕd có cꢓu trúc
Kiꢈu dꢆ liꢂu nút = record
INFO: kiꢈu thông tin;
XVAL: real;
YVA L: real;
LLINK: ↑ kiꢈu nút;
RLINK: ↑ kiꢈu nút;
End;
Các mꢍi nꢍi RLINK và LLINK cho phép trꢞ tꢁi các nút con phꢉi và trái cꢐa mꢏt
nút.
Giꢉ sꢣ T là trꢞ ñꢋn gꢍc cây kꢕd. Nꢋu N là nút cây thì ngưꢗi ta xác ñꢊnh thêm mꢖc1
cꢐa nút N: Mꢖc (N) = 0 nꢋu N là gꢍc cây; mꢖc (P) + 1 khi N là nút con cꢐa nút cha P.
ðꢀnh nghĩa: Cây 2ꢡd là cây nhꢀ phân thoꢇ mãn (i) Khi N là nút cây mꢞc chꢢn thì
nút cây con trái M có M.XVAL < N.XVAL và nút L bên phꢇi có L.XVAL
N.XVAL; (ii) Khi N là nút cây mꢞc lꢣ thì nút cây con trái M có M.YVAL <
N.YVAL và nút L bên phꢇi có L.YVAL N.YVAL.
≥
≥
1 level
13
XVAL = 10, YVAL = 20
N
N t¹i møc ch½n
M t¹i møc lÎ
M.YVAL = 12
L
M
XVAL = 8 < N.XVAL
XVAL = 12 >= N.XVAL
L2
M2
YVAL = 8 < M.YVAL
YVAL = 14 >= M.YVAL
Hình. Qui ñꢑnh các giá trꢑ X, Y cꢏa các nút con
1.4.2.2. Bꢁ sung và tìm kiꢂm trên cây 2ꢃd
Yêu cꢇu thêm nút N vào cây ñã có. Cây này có trꢞ T, ngꢇm hiꢈu con trꢞ trꢞ ñꢋn nút
T. Ngưꢗi ta thꢓy có các khꢉ năng:
1. Nꢋu N ≡ T thì hiꢈn nhiên ñã có nút N trên cây;
2. Ngưꢑc lꢚi, ngưꢗi ta sang trái nꢋu N.XVAL < T.XVAL, do nút T là nút chꢩn (0);
và sang phꢉi nꢋu N.XVAL không nhꢞ hơn;
3. Tꢚi nút vꢢa ñꢋn P, nꢋu P ≡ N thì ñã xong, ngưꢑc lꢚi do P là nút lꢪ, nên căn cꢖ
vào giá trꢊ YVAL ñꢈ quyꢋt ñꢊnh sang trái hay phꢉi. Nꢋu N.YVAl < p.YVAL.
ngưꢗi ta sang trái; ngưꢑc lꢚi sang phꢉi.
4. Tiꢋp tꢀc tꢢ bưꢁc 2, cho ñꢋn khi dꢢng hay ñꢋn nút là thì bꢃ sung nút N.
Viꢂc tìm kiꢋm nút N vꢁi giá trꢊ XVAL và YVAL ñưꢑc thꢒc hiꢂn như dò tìm ñꢈ bꢃ
sung nút mꢁi.
Thí dꢀ:
Ngưꢗi ta có bꢉn ñꢘ vꢁi các ñiꢈm Hà nꢏi (19, 45), Hꢉi phòng (40, 50), Hà tây (38,
38), Hà ñông (54, 40), và Hoà bình (4, 4). Nꢋu xuꢓt phát tꢢ Hà nꢏi, ngưꢗi ta xây dꢒng
ñưꢑc cây thông tin.
Dꢒa trên cây 2ꢕd ñã có, ngưꢗi ta có thꢈ tiꢋn hành (i) tìm kiꢋm; (ii) bꢃ sung nút mꢁi
theo cách trên.
Hꢀ néi
(19, 45)
Hoꢀ b×nh
H¶i phßng
(4, 4)
(40, 50)
Hꢀ t©y
(38, 38)
Hꢀ ®«ng
(54, 40)
Hình. Các nút trên cây 2ꢒd
1.4.2.3. Xoá nút trên cây 2ꢃd
Vꢓn ñꢄ ñꢎt ra là: giꢉ sꢣ cây cꢇn xoá nút có trꢞ T; nút cꢇn xoá có toꢚ ñꢏ (x, y).
14
1. Bưꢁc ñꢇu tiên cꢇn tìm ra nút (x, y), thoꢉ mãn N.XVAL = x và N.YVAl = y. Bưꢁc
này khꢧng ñꢊnh có nút N cꢇn xoá, ñưꢑc thꢒc hiꢂn theo cách ñã nêu trong mꢀc trưꢁc;
2. Nꢋu nút N là nút lá, ngưꢗi ta huꢫ nút N bꢥng cách thay ñꢃi con trꢞ cꢐa các nút cha
trꢞ ñꢋn nút con N. Các trꢞ cꢐa nút cha sꢤ là NIL;
3. Nꢋu N là nút trung gian, công viꢂc phꢖc tꢚp hơn.
P
R
N
N
R
P
Hình. Chꢓn nút R thay thꢎ N
i. Khi N.LLINK ≠ NIL, tꢖc N có cây con trái Tl, và N.RLINK ≠ NIL, tꢖc có
cây con phꢉi Tr: cꢇn tìm nút R trong Tl hay Tr ñꢈ thay thꢋ N, và R bꢊ xoá khꢞi
cây cây {Tl, Tr}. Do vꢔy ngưꢗi ta thꢒc hiꢂn ba bưꢁc nhꢞ sau:
•
•
Bưꢁc 1. Tìm nút R ñꢈ thay thꢋ {Tl, Tr};
Bưꢁc 2. Thay trưꢗng nꢍi LLINK, RLINK không rꢠng cꢐa N vào các
trưꢗng nói cꢐa R;
•
•
Bưꢁc 3. Xoá R ra khꢞi {Tl, Tr};
Quá trình này sꢤ kꢋt thúc do có Ti ∈ {Tl, Tr} vꢁi mꢖc cao hơn;
ii. Vꢓn ñꢄ ñꢎt ra là bưꢁc thꢖ nhꢓt tìm R thay thꢋ {Tl, Tr} cꢇn có quan hꢂ không
gian ñꢍi vꢁi tꢓt cꢉ các nút P trong {Tl, Tr}, mà N sinh ra, cho ñꢋn nút P này.
•
•
•
Nꢋu P thuꢏc góc tây nam cꢐa N thì P là tây nam cꢐa R;
Nꢋu P là tây bꢟc cꢐa N thì P là tây bꢟc cꢐa R;
ðiꢄu này có nghĩa R thay thꢃ có tính chꢓt
a. Mꢠi M trong Tl:M.XVAL < R.XVAL nꢋu N mꢖc chꢩn; M.YVAL <
R.YVAL nꢋu N mꢖc lꢪ;
N ®ang ë møc ch½n
N
R
C©y con tr¸i Tl
M
Hình. Vꢑ trí nút thay thꢎ R khi N tꢌi mꢔc chꢕn
b. Mꢠi M trong Tr thoꢉ mãn: M.XVAL ≥ R.XVAL nꢋu N mꢖc chꢩn;
ngưꢑc lꢚi khi N mꢖc lꢪ.
iii. Khi Tr ≠ NIL, xét trưꢗng hꢑp mꢖc chꢩn lꢪ cꢐa N:
15
•
•
Nꢋu N mꢖc chꢩn thì bꢓt kì nút nào trong Tr có giá trꢊ XVAL nhꢞ nhꢓt là
nút R thay thꢋ. Chꢧng hꢚn nút Hà nꢏi bꢊ loꢚi thì nút Hà tây thay thꢋ;
Nꢋu N mꢖc lꢪ, nút thay thꢋ trong Tr có YVAL bé nhꢓt.
iv.
v.
Nhìn chung ngưꢗi ta thꢒc hiꢂn “tìm nút thay thꢋ trong cây con trái chꢌ vꢁi
mꢏt vài ñiꢄu kiꢂn”.
•
•
Nꢋu N ꢅ mꢖc chꢩn, nút phù hꢑp trong Tl là nút có XVAL lꢁn nhꢓt;
Nꢋu N mꢖc lꢪ, ngưꢗi ta chꢙn nút có YVAL ñꢚt cꢒc ñꢚi;
Vꢓn ñꢄ ñꢎt ra khi trong Tl có nhiꢄu nút ñꢚt giá trꢊ cꢒc ñꢚi, tꢚi XVAL hay
YVAL, thì ñiꢄu (2) trong ñꢊnh nghĩa cây 2ꢕd sꢤ bꢊ vi phꢚm khi áp dꢀng ba
bưꢁc thꢒc hiꢂn trên. Do vꢔy khi cꢇn xoá nút N trung gian, nên tìm nút thay
thꢋ R trên cây con phꢉi, bꢅi vì viꢂc tác ñꢏng vào cây con trái hay gây mꢓt
bꢄn vꢆng cꢓu trúc cây;
vi.
Khi cây con phꢉi Tr = NIL, ngưꢗi ta chꢙn R thay thꢋ trong Tl vꢁi giá trꢊ x
nhꢞ nhꢓt trong Tl khi N là nút tꢚi mꢖc chꢩn, hay chꢙn R thay thꢋ có y nhꢞ
nhꢓt khi N mꢖc lꢪ; và trong ba bưꢁc thꢒc hiꢂn nhꢞ trên, thay
Bưꢁc 2. Thay tꢓt cꢉ trưꢗng không rꢠng cꢐa N bꢥng các trưꢗng cꢐa R. ðꢎt
N.RLINK = N.LLINK, N.LLINK = NIL;
N
N
NIL
NIL
Hình. Cꢖu trúc nút
1.4.2.4. Câu hꢄi vꢅ phꢆm vi trong cꢀu trúc cây 2ꢃd
Vꢓn ñꢄ là tìm các nút (x, y) trong phꢚm vi bán kính r tꢢ (x0, y0). Sꢤ có vòng tròn
bán kính r vꢁi tâm là ñiꢈm (x0, y0).
(x, y)
(19, 45)
Hình. Miꢄn cꢗn tìm khi có nút (19, 45)
Liên quan ñꢋn câu hꢞi này, ngưꢗi ta thꢓy mꢠi nút N có miꢄn RN vꢁi bán kinh r.
Vòng tròn tꢚo ra tꢢ (x0, y0) không giao vꢁi vòng tròn RN thì không xét cây con cꢐa N.
Khái niꢂm vꢄ miꢄn liên quan ñꢋn mꢏt nút, có 5 loꢚi:
1. Xét nút Hà nꢏi (19, 45), ngưꢗi ta tꢚo ñưꢑc miꢄn Hà nꢏi = {(x, y)};
2. Nút Hꢉi phòng cho biꢋt miꢄn Hꢉi phòng = {(x, y) | x ≥ 19};
16
3. Nút Hà tây cho biꢋt miꢄn Hꢉi tây = {(x, y) | x ≥ 19, y < 50};
4. Nút Hà ñông cho biꢋt miꢄn Hà ñông = {(x, y) | x ≥ 38, y < 50};
5. Nút Hoà bình cho biꢋt miꢄn Hoà bình = {(x, y) | x < 19}.
Trôc Y
(19, 45)
Trôc X
Hình. Xác ñꢑnh các biên
Nhìn chung mꢠi nút N có nhiꢄu nhꢓt 4 ràng buꢏc liên quan, gꢟn vꢁi viꢂc xác ñꢊnh
vùng:
1. Xác ñꢊnh biên dưꢁi vꢄ X, XLB1, có dꢚng x ≥ c1;
2. Xác ñꢊnh biên trên vꢄ X, XUB2, có dꢚng x< c2;
3. Xác ñꢊnh biên dưꢁi vꢄ Y, YLB3, có dꢚng y ≥ c3;
4. Xác ñꢊnh biên trên vꢄ Y, YUB4, có dꢚng y< c4.
5. Do vꢔy cꢇn mꢅ rꢏng kiꢈu dꢆ liꢂu vꢄ nút, vꢁi tên là kiꢈu nút dꢆ liꢂu mꢁi:
Kiꢈu nút mꢁi = record
INFO: kiꢈu thông tin;
XVAL, YVAL: real;
XLB, XUB, YLB, YUB: real ∪ {ꢕ∞, +∞};
LLINK, RLLINK: ↑ kiꢈu nút mꢁi;
End;
Viꢂc bꢃ sung các nút cꢇn thꢒc hiꢂn:
1. Gꢍc cây nhꢔn XLB: = ꢕ∞, YLB: = ꢕ∞ và XUB: = +∞, YUB: = +∞;
2. Nꢋu nút N có cha P và P tꢚi mꢖc chꢩn, thì các giá trꢊ phꢚm vi cꢐa N ñưꢑc xác ñꢊnh
theo P:
•
N.XLB = P.XLB nꢋu N là con trái cꢐa P; ngưꢑc lꢚi N là con phꢉi, N.XLB =
P.XVAL;
•
N.XUB = P.XVAL nꢋu N là con trái cꢐa P; ngưꢑc lꢚi N là con phꢉi, N.XLB =
P.XUB;
•
•
N.YLB = P. YLB;
N.YUB = P. YUB;
3. Nꢋu N có cha là P và mꢖc P là lꢪ, thì:
•
N.YLB = P.YLB nꢋu N là con trái cꢐa P; ngưꢑc lꢚi N là con phꢉi, N.YLB =
1 XLB lower bound on x
2 XUB upper bound on x
3 YLB lower bound on y
4 YUB upper bound on y
17
P.YVAL;
•
N.YUB = P.YVAL nꢋu N là con trái cꢐa P; ngưꢑc lꢚi N là con phꢉi, N.YLB =
P.YUB;
•
•
N.XLB = P. XLB;
N.XUB = P. XUB;
ðꢍi vꢁi viꢂc tìm kiꢋm vùng trên cây, ngưꢗi ta có nhꢔn xét:
•
•
Khi gꢍc T không giao, thì xét cây con trái, cây con phꢉi;
Vꢁi cây con không giao, có thꢈ loꢚi bꢞ trong quá trình tìm kiꢋm.
1.4.2.5. Cây kꢃd tꢁng quát
Cây kꢕd tꢃng quát có k ≥ 2. Cây 2ꢕd ñưꢑc dùng ñꢈ thꢈ hiꢂn các nút trong không
gian 2 chiꢄu. Cây kꢕd vꢁi k ≥ 2 ñưꢑc dùng cho không gian k chiꢄu, chꢧng hꢚn các ñiꢈm
(x, y, z) sꢣ dꢀng cây 3ꢕd. ðꢍi vꢁi cây tꢃng quát, không thꢈ sꢣ dꢀng XVAL, YVAL ñꢈ trꢞ
ñꢋn hai cây con, mà dùng vecto VAL k chiꢄu, ꢖng vꢁi bꢏ các con trꢞ trꢞ ñꢋn các cây
con.
ðꢀnh nghĩa: Cây T có cꢝu trúc nút cây kꢡd nꢃu ñꢆi vꢍi nút N trên cây T, thì:
• Nút N có mꢞc i. Mꢞc này ñưꢏc tính i = “mꢞc thꢓc sꢓ” mod k;
• nút M trên cây con trái cꢋa N, M.VAL [i] < N. VAL [i];
• nút P trên cây con phꢇi cꢋa N, P. VAL[i]
≥ N.VAL [i].
Các thuꢔt toán ñã sꢣ dꢀng cho cây 2ꢕd ñưꢑc phát triꢈn dùng cho cây kꢕd. Khi k = 1,
ngưꢗi ta làm viꢂc vꢁi cây nhꢊ phân quen thuꢏc.
1.4.3. Cây tꢔ phân
Cây tꢖ phân1, hay cây bꢍn phꢇn, ñưꢑc dùng ñꢈ thꢈ hiꢂn ñiꢈm không gian 2 chiꢄu.
Cây 2ꢕd cũng có tác dꢀng như vꢔy. Tuy nhiên ñiꢈm khác biꢂt là cây tꢖ phân chia miꢄn
thành 4 phꢇn, trong khi cây 2ꢕd cho phép tách miꢄn ra hai phꢇn.
Trôc Y
Trôc Y
(N.XVAL, N.YVAL)
Khi N t¹i møc lÎ
(N.XVAL, N.YVAL)
Khi N t¹i møc ch½n
Trôc X
Trôc X
Hình. Vai trò cꢏa trꢀc ngang và dꢓc khi chia các miꢄn
Bꢍn phꢇn ꢖng vꢁi bꢍn cây con trên cây tꢖ phân ñưꢑc gꢙi tên theo hưꢁng ñꢍi vꢁi
nút N: ñông bꢟc NE, tây bꢟc NW, tây nam SW, và ñông nam SE2.
Kiꢈu dꢆ liꢂu ñưꢑc mô tꢉ là:
Kiꢈu nút tꢖ phân = record
INFO: kiꢈu thông tin;
XVAL: real;
1 point quadtree
2 north east, north west, south west, south east
18
YVAL: real;
NW, SW, NE, SE: ↑ kiꢈu nút tꢖ phân;
End;
PhÇn t©y b¾c
NW
PhÇn ®«ng b¾c
NE
(N.XVAL, N.YVAL)
PhÇn ®«ng nam
SE
PhÇn t©y nam
SW
Hình. Bꢈn phꢗn so vꢁi mꢇt nút
1.4.3.1. Tìm kiꢂm thông tin và bꢁ sung nút trên cây tꢇ phân
Khi có các giá trꢊ ñiꢈm không gian, như trong thí dꢀ trưꢁc vꢁi bꢉn ñꢘ các ñiꢈm Hà
nꢏi (19, 45), Hꢉi phòng (40, 50), Hà tây (38, 38), Hà ñông (54, 40), và Hoà bình (4, 4),
ngưꢗi ta có thꢈ xây dꢒng ñưꢑc cây bꢥng cách phát triꢈn dꢇn các nút. Chꢧng hꢚn tꢢ nút
Hà nꢏi, ngưꢗi ta dùng 4 con trꢞ ñꢋn các nút khác, theo vꢊ trí tương ñꢍi so vꢁi nút Hà
nꢏi.
Nót thø ba
Nót thø hai
N
CÊu tróc mét nót trªn
c©y tø ph©n
Nót thø nhÊt
Hình. Nguyên tꢘc mô tꢍ nút cây tꢔ phân
Viꢂc xây dꢒng cây ñưꢑc tiꢋn hành theo:
1. Cây rꢠng, ngưꢗi ta xác ñꢊnh nút ñꢇu là Hà nꢏi, toꢚ ñꢏ (19, 45);
2. Chia ra 4 phꢇn không gian;
(40, 50)
Hꢀ néi
N
W
S
W
N
E
S
E
(19, 45)
H¶i phßng
N
W
S
W
N
E
S
E
Hình. Thêm nút Hà nꢇi và xác ñꢑnh ñưꢊc vꢑ trí tương ñꢈi cꢏa Hꢍi phòng so vꢁi Hà nꢇi
3. Bꢃ sung nút Hà tây. Do phꢇn này chưa có nút nào, con trꢞ tꢢ nút Hà nꢏi trꢞ
trꢒc tiꢋp ñꢋn nút Hà tây;
4. Vꢁi nút Hà ñông: do ñã có nút Hà tây tꢚi SE cꢐa nút Hà nꢏi, ngưꢗi ta nhꢔn
thꢓy chính nút Hà tây cho phép tách không gian ra 4 phꢇn, và nút Hà ñông là
NE cꢐa nút Hà tây;
19
5. Viꢂc bꢃ sung nút Hoà bình ñơn giꢉn.
Hꢀ néi
N
W
S
W
N
E
S
E
H¶i phßng
Hꢀ t©y
N
W
S
W
N
E
S
E
N
W
S
W
N
E
S
E
Hoꢀ b×nh
Hꢀ ®«ng
N
W
S
W
N
E
S
E
N
W
S
W
N
E
S
E
Hình. Các nút cây tꢔ phân
Nhìn chung, trong trưꢗng hꢑp xꢓu nhꢓt, n nút tꢚo nên ñꢏ cao nꢕ1 mꢖc. Lưu ý rꢥng
thꢗi gian tìm kiꢋm nút, bꢃ sung nút ñưꢑc biꢈu diꢨn tuyꢋn tính theo sꢍ nút n.
1.4.3.2. Xoá mꢈt nút trên cây tꢇ phân
Khi nút N cꢇn xoá là nút lá thì công viꢂc ñơn giꢉn. Nhưng khi N là nút trung gian,
viꢂc tìm nút thay thꢋ rꢓt phꢖc tꢚp, do:
•
Mꢠi nút gꢟn vꢁi miꢄn, vùng cꢐa bꢉn ñꢘ, có cách xác ñꢊnh khác cây 2ꢕd. Trong
cây 2ꢕd, ngưꢗi ta ñã dùng các ràng buꢏc x ≥ c1, x < c2, y ≥ c3, và y < c4;
•
Trong cây tꢖ phân, mô tꢉ kiꢈu dꢆ liꢂu là
Kiꢈu nút tꢖ phân = record
INFO: kiꢈu thông tin;
XVAL, YVAl: real;
XLB, YLB, XUB, YUB: real ∪ {ꢕ∞, +∞}
NW, SW, NE, SE: ↑ kiꢈu nút tꢖ phân;
End;
Viꢂc xoá nút cꢇn lưu ý ñꢋn viꢂc bꢃ sung nút. Viꢂc bꢃ sung mꢏt nút N vào cây có trꢞ
T ñưꢑc thꢒc hiꢂn:
1. Nꢋu N là gꢍc cây T, thì N.XLB = ꢕ∞, N.YLB = ꢕ∞, N.XUB = +∞, N.YUB
= +∞;
2. Nꢋu P là nút cha cꢐa con n, thì viꢂc gán giá trꢊ theo tham chiꢋu ñꢋn bꢉng
sau, tuỳ theo vꢊ trí tương ñꢍi cꢐa con N ñꢍi vꢁi P. Trong bꢉng ngưꢗi ta sꢣ
dꢀng kí hiꢂu ñꢏ rꢏng cꢐa hình bao w = P.XUB – P.XLB, và chiꢄu cao cꢐa
hình bao h = YUB – YLB.
Trưꢗng hꢑp
N.XLB
P.XLB
P.XLB
N.XUB
N.YLB
N.YUB
N là con tây bꢟc
N là con tây nam
P.XLB + w / 2 P.YLB + h / 2
P.XLB + w / 2 P.YLB
P.YUB
P.YLB + h / 2
P.YUB
N là con ñông bꢟc P.XLB + w / 2
N là con ñông nam P.XLB + w / 2
P.XUB
P.XUB
P.YLB + h / 2
P.YLB
P.YLB + h / 2
Hình. Bꢍng tra cꢔu giá trꢑ cꢙn trên/ dưꢁi cho các nút con
Trong quá trình tìm nút R thay thꢋ N trong sꢍ các cây con, ñꢈ xoá N, ngưꢗi ta nhꢔn
20
Tải về để xem bản đầy đủ
142 trang
22300
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cơ sở dữ liệu đa phương tiện - Đỗ Trung Tuấn", để 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:
- bai_giang_co_so_du_lieu_da_phuong_tien_do_trung_tuan.pdf
