Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- 5 -
DANH MỤC CÁC TỪ TIẾNG ANH VÀ VIẾT TẮT
Từ gốc Giải nghĩa
Cluster-based Cơ sở cụm
CSDL Cơ sở dữ liệu
DBMS (Database Management System) Hệ quản trị cơ sở dữ liệu
MDBMS (Multimedia Database
Management System)
Hệ quản trị cơ sở dữ liệu đa phương tiện
Doc Tài liệu
Docs Nhiều tài liệu
DSS (Decision Support Systems) Hệ hỗ trợ ra quyết định
Exact match Đối sánh chính xác
IMS (Information Management System) Hệ quản lý thông tin
Index Chỉ mục
IR (Information Retrieval) Truy tìm thông tin
IRS (Information Retrieval System) Hệ truy tìm thông tin
LSI (Latent Semantic Indexing) Chỉ mục ngữ nghĩa tiềm ẩn
MultiMedia Truyền thông da phương tiện
Precision Độ chính xác
QAS (Question Anser System) Hệ trả lời câu hỏi
Query Truy vấn
Term Thuật ngữ (từ)
Ranking Sắp xếp
Record Bản ghi
Recall Khả năng tìm thấy
SC (Similarity Coeficient) Độ tương quan
SVD (Singular Value Decomposition) Kỹ thuật tách giá trị đơn
Text-partern Mẫu văn bản
The Term Discrimination Value Giá trị phân biệt từ
The Signal – Noise Ratio Độ nhiễu tín hiệu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- 6 -
DANH MỤC CÁC BẢNG
Bảng 2.2: Cách tập tin nghịch đảo lưu trữ 43
Bảng 2.3 Cách tập tin trực tiếp lưu trữ 43
Bảng 2.4: Thêm một tài liệu mới vào tập tin nghịch đảo 44
Bảng 2.5: Danh sách từ dừng của tiếng Anh 49
Bảng 3.1: Bảng khoảng cách của từng đối tượng trong CSDL đến từng vector so
sánh 62
DANH MỤC CÁC HÌNH, ĐỒ THỊ
Hình1.1. Kiến trúc bậc cao cho một MDBMS đáp ứng các yêu cầu cho dữ liệu
MULTIMEDI 10
Hình 1.2. Mô hình khả năng lưu trữ của các hệ thống Multimedia 13
Hình 2.1. Mô hình tổng quát tìm kiếm thông tin 28
Hình 2.3. Mô hình kiến trúc của hệ tìm kiếm thông tin 31
Hình 2.4. Cấu trúc hệ tìm kiếm thông tin tiêu biểu 31
Hình 2.5. Các từ được sắp theo thứ tự 46
Hình 2.6. Mô hình minh hoạ mối quan hệ giữa 5 tài liệu D1 đến D5 và thuật ngữ
“CAR” 48
Hình 2.7. Quá trình chọn từ làm chỉ mục 50
Hình 2.8. Mô hình thước đo hiệu năng 55
Hình 2.9. Đồ thị so sánh hiệu năng 56
Hình 3.1. Mô hình LSI 67
Hình 3.2. Mô hình tính toán và xếp thứ hạng cho các tài liệu 68
Hình 3.3. Minh hoạ kỹ thuật Chỉ số hoá ngữ nghĩa tiềm ẩn (LSI) 69
Hình 3.4. Mô hình minh hoạ tách giá trị đơn (SVD) 75
Hình 4.1. Giao diện màn hình lập chỉ mục 82
Hình 4.2. Giao diện màn hình cập nhập chỉ mục 83
Hình 4.3. Giao diện tìm kiếm theo mô hình vector 83
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- 7 -
MỞ ĐẦU
Cùng với sự phát triển nhanh chóng của công nghệ tin học thì khối lượng dữ
liệu đa phương tiện (Multimedia) được thu thập và lưu trữ dưới dạng số ngày càng
nhiều dẫn tới việc tìm kiếm dữ liệu đa phương tiện trở nên khó khăn vì vậy cần có
các hệ thống tìm kiếm thông tin (Information Retrieval) hỗ trợ người dùng tìm kiếm
một cách chính xác và nhanh chóng các thông tin mà họ cần trên kho tư liệu khổng
lồ này.
Hiện nay có một số hệ thống tìm kiếm như GoogleDesktop, DTSearch,
Lucene, tuy nhiên các hệ thống này sử dung các kỹ thuật tìm kiếm đơn giản nên
hiệu quả còn chưa cao. Vì vậy mục tiêu của luận văn này nhằm tìm hiểu một số kỹ
thuật nâng cao tìm kiếm thông tin, cụ thể ở đây là tìm kiếm văn bản theo nội dung
trong cơ sở dữ liệu đa phương tiện nhằm đáp ứng nhu cầu cấp thiết của thời đại
bùng nổ thông tin điện tử hiện nay.
Bố cục của luận văn gồm các phần sau:
+ CHƯƠNG 1: TỔNG QUAN VỀ HỆ QUẢN TRỊ CSDL ĐA PHƯƠNG TIỆN:
Phần này sẽ giới thiệu tổng quan về hệ quản trị CSDL đa phương tiện.
+ CHƯƠNG 2: MỘT SỐ KỸ THUẬT CHỈ MỤC VÀ TÌM KIẾM VĂN BẢN
- Trình bày các v ấn đề về hệ tìm kiếm thông tin.
- Trình bày kỹ thuật cơ sở chỉ mục văn bản trên cơ sở mô hình Bool và mô
hình vector.
+ CHƯƠNG 3: MỘT SỐ KỸ THUẬT NÂNG CAO HIỆU NĂNG TÌM KIẾM
VĂN
- Trình bày cơ sở lý thuyết về một số kỹ thuật chỉ mục nâng cao.
- Giới thiệu kỹ thuật chỉ mục nâng cao LSI.
+ CHƯƠNG 4: PHÁT TRIỂN CHƯƠNG TRÌNH THỬ NGHIỆM: Chương này
phát triển chương trình thử nghiệm áp dụng kỹ thuật chỉ mục và kỹ thuật tìm kiếm
văn bản theo nội dung trong cơ sở dữ
liệu đa phương tiện.
+ KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN: Trình bày các kết quả đạt được trong
luận văn và nêu phương hướng phát triển của đề tài trong tương lai.
+ TÀI LIỆU THAM KHẢO và PHỤ LỤC: Trình bày các thông tin liên quan đến
luận văn.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- 8 -
CHƯƠNG 1: TỔNG QUAN HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU ĐA
PHƯƠNG TIỆN (MDBMS)
Trung tâm của một hệ thống thông tin đa phương tiện (MULTIMEDIA)
chính là hệ quản trị CSDL MULTIMEDIA (MDBMS - Multimedia Database
Management System). Theo truyền thống, một CSDL bao gồm một bộ các dữ liệu
có liên quan về một thực thể cho trước hoặc một hệ quản trị CSDL (DBMS) là một
bộ các dữ liệu có liên quan đến nhau với một tập hợp các chương trình được dùng
để khai báo, tạo lập, lưu trữ, truy cập và truy vấn CSDL. Tương tự như vậy,
chúng ta có thể xem một CSDL MULTIMEDIA là một tập các loại dữ liệu
Multimedia như văn bản, hình ảnh, video, âm thanh, các đối tượng đồ hoạ…. Một
hệ quản trị CSDL MULTIMEDIA cung cấp hỗ trợ cho các loại dữ liệu
MULTIMEDIA trong việc tạo lập, lưu trữ, truy cập, truy vấn và kiểm soát.
Sự khác
nhau của các kiểu dữ liệu trong CSDL MULTIMEDIA có thể
đòi hỏi các phương thức đặc biệt để tối ưu hoá việc lưu trữ, truy cập, chỉ số
hoá và khai thác. MDBMS cần phải cung cấp các yêu cầu đặc biệt này bằng
cách cung cấp các cơ chế tóm tắt bậc cao để quản lý các kiểu dữ liệu khác nhau
cũng như các giao diện thích hợp để thể hiện chúng.
1.1 Mục đích của MDBMS
Một MDBMS cung cấp một môi trường thích hợp để sử dụng và quản lý
các thông tin CSDL MULTIMEDIA. Vì vậy, nó phải hỗ trợ các kiểu dữ liệu
MULTIMEDIA khác nhau bên cạnh việc phải cung cấp đầy đủ các chức năng của
một DBMS truyền thống như khai báo và tạo lập CSDL, khai thác dữ liệu, truy
cập và tổ chức dữ liệu, độc lập dữ liệu, tính riêng, toàn vẹn dữ liệu, kiểm soát
phiên bản. Các chức năng của MDBMS cơ bản tương tự như các chức năng của
DBMS, tuy nhiên, bản chất của thông tin MULTIMEDIA tạo ra các đòi hỏi
mới. Bằng cách sử dụng các chức năng tổng quát của DBMS chúng ta có thể
trình bày mục đích của MDBMS như sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- 9 -
• Sự thống nhất: bảo đảm rằng một dữ liệu không phải tạo lại khi các
chương trình khác nhau đòi hỏi dữ liệu đó.
• Độc lập dữ liệu: Đảm bảo sự tách rời giữa CSDL và các chức năng quản trị
từ các chương trình ứng dụng.
• Điều khiển nhất quán: đảm bảo sự toàn vẹn của CSDL MULTIMEDIA
thông qua các quy tắc được áp dụng trên các giao dịch đồng thời.
• Sự tồn tại: bảo đảm các đối tượng dữ liệu tồn tại qua các giao dịch khác
nhau cũng như các yêu cầu của chương trình.
• Tính riêng: ngăn chặn các truy cập và sửa chữa các dữ liệu được lưu trữ
một cách trái phép.
• Kiểm soát sự toàn vẹn: bảo đảm sự toàn vẹn của CSDL từ một giao dịch
này sang một giao dịch khác thông qua việc áp đặt các ràng buộc.
• Khả năng phục hồi: phải có các phương thức cần thiết để đảm bảo rằng kết
quả của các giao dịch thất bại không làm ảnh hưởng đến dữ liệu lưu trữ.
• Hỗ trợ truy vấn: bảo đảm các cơ chế truy vấn phù hợp với dữ liệu
MULTIMEDIA.
• Kiểm soát phiên bản: tổ chức và quản lý các phiên bản khác nhau của các
đối tượng lưu trữ có thể được yêu cầu bởi các ứng dụng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- 10 -
Hình1.1. Kiến trúc bậc cao cho một MDBMS đáp ứng các yêu cầu cho dữ liệu
MULTIMEDI
Đối với việc điều khiển nhất quán, một giao dịch là một chuỗi các hướng
dẫn được thực thi một cách hoàn toàn hoặc không hoàn toàn, đối với trường
hợp không hoàn toàn CSDL sẽ được khôi phục lại trạng thái trước đó, việc đưa
ra được một cơ chế tương ứng đảm bảo cho việc nhất quán là một vấn đề
khó khăn đối với CSDL MULTIMEDIA. Các CSDL quan hệ truyền thống sử
dụng một bản ghi hoặc một bảng duy nhất như là một đơn vị nhất quán. CSDL
MULTIMEDIA thường sử dụng một đối tượng đơn lẻ (hoặc đối tượng ghép) như
là một đơn vị logic của truy cập. Như vậy một đối tượng MULTIMEDIA đơn lẻ có
thể tạo thành đơn vị nhất quán.
Đối với vấn đề lưu trữ, một phương thức đơn giản là lưu trữ các tệp
MULTIMEDIA trong các tệp tương ứng của hệ điều hành. Tuy nhiên với đặc thù là
dung lượng lớn, các dữ liệu MULTIMEDIA là cho chi phí triển khai theo cách
thức này trở nên tốn kém. Hơn nữa, hệ thống cũng cần phải lưu trữ các metadata
MULTIMEDIA và có thể cả các đối tượng MULTIMEDIA tổng hợp. Vì vậy, hầu
hết các MDBMS phân loại thành 2 phần là cố định và tạm thời và chỉ lưu trữ
các dữ liệu cố định sau khi các giao dịch được cập nhật. Các dữ liệu tạm thời
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- 11 -
chỉ được dùng trong các chương trình hoặc các giao dịch khi chúng được thực thi
và được loại bỏ sau đó.
Thông thường, một câu hỏi sẽ lựa chọn một tập con của các đối tượng dữ
liệu dựa trên các mô tả của người dùng (thường là thông qua các ngôn ngữ truy
vấn) về truy nhập dữ liệu nào. Một câu hỏi thường có nhiều thuộc tính khác nhau,
có thể là dựa trên từ khoá hoặc hướng theo nội dung và thường là tác động lẫn
nhau. Vì vậy, các chức năng cho phản hồi có liên quan, công thức của câu hỏi,
các kết quả tương tự, và cơ chế thể hiện kết quả rõ ràng là rất quan trọng trong
MDBMS.
Khi các ứng dụng cần truy cập đến các trạng thái khác nhau của một đối
tượng thì vấn đề kiểm soát phiên bản
đối với đối tượng MULTIMEDIA khi
chúng được truy cập hoăc sửa chữa trở nên rất quan trọng. Một DBMS cung cấp
các khả năng truy cập như vậy thông qua các phiên bản của các đối tượng lưu trữ,
đối MDBMS khi mà phải lưu trữ một khối lượng dữ liệu khổng lồ thì vấn đề kiểm
soát phiên bản càng trở nên quan trọng. Mặt khác, việc quản lý phiên bản không
chỉ áp dụng cho một đối tượng riêng lẻ mà nó còn được áp dụng để quản lý các đối
tượng phức tạp tạo nên CSDL MULTIMEDIA.
Các tính chất đặc biệt của dữ liệu MULTIMEDIA cũng đòi hỏi phải có các
tính năng đặc biệt mới để hỗ trợ cho nó như kết hợp và phân rã các đối tượng,
quản trị dung lượng
khổng lồ dữ liệu MULTIMEDIA, lưu trữ và khai thác hiệu
quả, có khả năng làm việc được với các đối tượng dữ liệu tạm thời hoặc một phần
của chúng.
1.2 Các yêu cầu của một MDBMS
Để có được một MDBMS đáp ứng được các yêu cầu đã nêu ra ở trên,
chúng ta cần phải có được một số các yêu cầu cụ thể cho nó, các yêu cầu ở đây bao
gồm:
• Đầy đủ các khả năng của một DBMS truyền thống.
• Có khả năng lưu trữ lớn.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- 12 -
• Có khả năng khai thác dữ liệu thuận tiện.
• Có khả năng tích hợp, tổng hợp và thể hiện.
• Hỗ trợ truy vấn Multimedia.
• Có giao diện Multimedia và tương tác.
Bên cạnh các yêu cầu vừa nêu, để cho hệ thống hoạt động có thể hoạt động
tốt chúng ta cũng cần phải giải quyết các vấn đề sau:
• Hệ thống CSDL MULTIMEDIA sẽ được xây dựng như thế nào để có
thể bao gồm các lĩnh vực ứng dụng khác nhau.
• Xây dựng phần hạt nhân cho việc phân rã, lưu trữ và quản lý thông tin
ở mức độ nào? Các công nghệ, cấu trúc nền tảng được sắp xếp và sử dụng như thế
nào?
• Các kiến thức về tổng hợp dữ liệu đối với CSDL MULTIMEDIA, làm
thế nào để có thể phát triển được một ngôn ngữ truy vấn đáng tin cậy và có hiệu quả
để hỗ trợ cho vô số phương thức truy nhập và các kiểu đối tượng khác nhau. Làm
thế nào để ngôn ngữ truy vấn hỗ trợ được các đặc tính và hình thái khác nhau của dữ
liệu MULTIMEDIA.
• Xác định được hạ tầng thể hiện nào mà một hệ thống MULTIMEDIA
phải có để đạt được các yêu cầu và cách thức thể hiện khác nhau. Làm cách nào để
hỗ trợ việc đồng bộ hoá việc thể hiện các dữ liệu tạm thời cũng như các dữ liệu bộ
phận của các dữ liệu MULTIMEDIA khác nhau.
• Giả sử các kiểu media khác nhau có các yêu cầu cập nhật và sửa đổi
thông tin khác nhau thì hệ thống sẽ cập nhật các thành phần này như thế nào?
Như hình 1.1 chúng ta đã thấy kiến trúc bậc cao dành cho một MDBMS
đã chỉ ra được một số các yêu cầu cần phải đạt được. Kiến trúc này bao gồm hầu
hết các khối chức năng về quản lý đi kèm với DBMS truyền thống. Ngoài ra, nó
cũng bao gồm một số modul đặc biệt phục vụ cho việc quản trị dữ liệu
MULTIMEDIA như tích hợp các phương tiện và quản lý các đối tượng. Tuy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- 13 -
nhiên hầu hết các chức năng thêm vào DBMS truyền thống đều nằm ngoài phần
lõi của MDBMS bao gồm thể hiện, giao diện, và quản lý cấu hình.
1.2.1 Khả năng quản trị lưu trữ lớn
Hình 1.2. Mô hình khả năng lưu trữ của các hệ thống Multimedia
Các yêu cầu về khả năng lưu trữ của các hệ thống MULTIMEDIA có thể
được đặc trưng bởi khả năng lưu trữ lớn và cách thức tổ chức theo thứ bậc (dạng
kim tự tháp) của hệ thống lưu trữ. Việc lưu trữ theo thứ bậc đặt các đối
tượng dữ liệu MULTIMEDIA trong một hệ thống phân bậc bao gồm các thiết bị
khác nhau, có thể là trực tuyến (online), không trực tuyến (offline). Một cách tổng
quát, mức cao nhất của hệ thống sẽ cho ta hiệu suất cao nhất, khả năng lưu trữ nhỏ
nhất, chi phí cao nhất và sự cố định ít nhất. Các lớp cao trong hệ thống phân cấp
này có thể sử dụng để lưu trữ các đối tượng tóm tắt nhỏ hơn của
một dữ liệu
MULTIMEDIA hoàn chỉnh với mục đích cung cấp khả năng duyệt và xem trước
nhanh đối với nội dung của dữ liệu. Chi phí và hiệu suất (tính về mặt thời gian) sẽ
giảm dần nếu ta đi xuống các lớp phía dưới của hệ thống phân cấp, cùng với điều
này là sự tăng của khả năng lưu trữ và tính cố định. Thông thường trong hầu hết
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- 14 -
các hệ thống lưu trữ MULTIMEDIA, mức cao nhất của lưu trữ thường là RAM,
tiếp theo đó là đĩa từ, các thiết bị này cung cấp các dịch vụ trực tuyến (online
services). Các thiết bị lưu trữ quang học cung cấp mức lưu trữ tiếp theo, khái niệm
trực tuyến ở đây có thể hiểu là gần như, tiêu biểu cho các thiết bị lưu trữ kiểu này
là các jukebox (CD-DVD jukebox). Mức thấp nhất trong hệ thống lưu trữ phân cấp
có thể là các thiết bị như băng từ, đĩa quang hoặc các thiết bị tương tự, các thiết bị
này cung cấp khả năng lưu trữ offline và có thể không cần kết nối trức tiếp với máy
tính. Chúng cung cấp khả năng lưu trữ và tính cố
định cao hơn nhưng cũng có
hiệu suất kém nhất về thời gian truy nhập. Vì những lý do trên, một MDBMS
phải quản lý và tổ chức việc lưu trữ đối với bất kỳ mức nào của hệ thống phân cấp,
nó phải có cơ chế tự động để chuyển các đối tượng dữ liệu MULTIMEDIA từ
một mức này của hệ thống lưu trữ phân cấp sang mức khác, việc chuyển cấp này
phải dựa trên tần suất sử dụng của dữ liệu MULTIMEDIA. Trong trường hợp dữ
liệu MULTIMEDIA được lưu trữ ở các thiết bị offline thì MDBMS cũng phải có
được các thông tin trợ giúp cho việc dễ dàng xác định các thiết bị cụ thể có chứa các
thông tin cần truy xuất.
1.2.2 Hỗ trợ truy vấn và khai thác dữ liệu.
Truy vấn đối với dữ liệu MULTIMEDIA bao gồm các kiểu dữ liệu khác
nhau, các từ khoá, thuộc tính, nội dung vv…Do người dùng có thể có các cách suy
nghĩ khác nhau về dữ liệu MULTIMEDIA vì vậy kết quả thu được từ việc truy
vấn dữ liệu MULTIMEDIA có thể không hoàn toàn chính xác và có thể chỉ là các
kết quả tương tự hoặc là một phần của kết quả hơn là các kết quả chuẩn xác. Do
việc có thể kết quả là không chính xác nên chúng ta phải có khả năng phân hạng
các kết quả thu được sao cho chúng gần với yêu cầu truy vấn nhất, tương tự như
vậy chúng ta cũng phải có các phương thức để loại bỏ bớt những kết quả không
thoả mãn yêu cầu truy vấn. Vi
ệc làm này sẽ giảm thiểu các sai sót về mặt tính toán
trong quá trình tìm kiếm.
1.2.3 Tích hợp các phương tiện, tổng hợp và thể hiện
Giả sử tính đa dạng của các kiểu dữ liệu đã được hỗ trợ, một MDBMS cũng
Không có nhận xét nào:
Đăng nhận xét