Hệ quản trị cơ sở dữ liệu đa phương tiện (MDBMS)

g tin – ĐH Thái Nguyên đã dìu dắt, giảng dạy em, giúp em có những kiến thức quý báu trong những năm học qua. Cảm ơn các bạn đã tận tình động viên đóng góp ý kiến cho luận văn của tôi. Mặc dù đã cố gắng hết sức cùng với sự tận tâm của thầy giáo hướng dẫn song do trình độ còn hạn chế, nội dung đề tài còn mới mẻ nên Luận văn khó tránh khỏi những thiếu sót. Em rất mong nhận được sự thông cảm và góp ý của thầy cô và các bạn. Thái Nguyên, tháng 11/2008 Học viên Phạm Thị Ngọc Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 2 - MỤC LỤC MỤC LỤC .............................................................................................................. 2 DANH MỤC CÁC TỪ TIẾNG ANH VÀ VIẾT TẮT ............................................. 5 DANH MỤC CÁC BẢNG ....................................................................................... 6 DANH MỤC CÁC HÌNH, ĐỒ THỊ ........................................................................ 6 MỞ ĐẦU ................................................................................................................. 7 CHƯƠNG 1: TỔNG QUAN HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU ĐA PHƯƠNG TIỆN (MDBMS) ..................................................................................................... 8 1.1 Mục đích của MDBMS .................................................................................. 8 1.2 Các yêu cầu của một MDBMS ......................................................................11 1.2.1 Khả năng quản trị lưu trữ lớn ..............................................................13 1.2.2 Hỗ trợ truy vấn và khai thác dữ liệu......................................................14 1.2.3 Tích hợp các phương tiện, tổng hợp và thể hiện ....................................14 1.2.4 Giao diện và tương tác. ........................................................................15 1.2.5 Hiệu suất. .............................................................................................15 1.3 Các vấn đề của MDBMS ...............................................................................16 1.3.1 Mô hình hoá dữ liệu MULTIMEDIA ......................................................16 1.3.2 Lưu trữ đối tượng MULTIMEDIA .........................................................17 1.3.3 Tích hợp Multimedia, thể hiện và chất lượng của dịch vụ (QoS) ............19 1.3.4 Chỉ số hoá Multimedia ..........................................................................20 1.3.5 Hỗ trợ truy vấn Multimedia, khai thác và duyệt qua. ............................21 1.3.6 Quản trị CSDL Multimedia phân tán ....................................................22 1.3.7 Sự hỗ trợ của hệ thống ..........................................................................23 1.4 Kết luận ........................................................................................................23 CHƯƠNG 2: MỘT SỐ KỸ THUẬT CHỈ MỤC VÀ TÌM KIẾM VĂN BẢN THEO NỘI DUNG ............................................................................................................25 2.1 Giới thiệu hệ tìm kiếm thông tin ....................................................................25 2.1.1 Kỹ thuật tìm kiếm thông tin ....................................................................25 2.1.2 Một số vấn đề trong tìm kiếm thông tin ..................................................26 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 3 - 2.1.3 Hệ thống tìm kiếm thông tin – IR ..........................................................27 2.1.4 Sự khác biệt giữa các hệ thống IR và các hệ thống thông tin khác .........32 2.1.5 Các hệ tìm kiếm văn bản thường được sử dụng hiện nay ........................34 2.2 Một số kỹ thuật tìm kiếm văn bản theo nội dung ..........................................35 2.2.1 Chỉ mục tự động văn bản và mô hình tìm kiếm Bool ..............................35 2.2.1.1. Mô hình tìm kiếm Bool cơ sở ..........................................................35 2.2.1.2 Tìm kiếm Bool mở rộng ...................................................................37 2.2.1.3 Các bước để xây dựng hệ thống tìm kiếm thông tin – IR..................39 2.2.1.4 Lập chỉ mục tài liệu ........................................................................40 2.2.2 Mô hình tìm kiếm không gian vector ......................................................51 2.2.2.1 Mô hình tìm kiếm không gian vector cơ sở ......................................51 2.2.2.2. Kỹ thuật phản hồi phù hợp (Relevance Feedback Technique) .......53 2.2.3. Thước đo hiệu năng ..............................................................................55 2.3 Ví dụ ..............................................................................................................56 2.4 Kết luận .........................................................................................................58 CHƯƠNG 3: MỘT SỐ KỸ THUẬT NÂNG CAO HIỆU NĂNG TÌM KIẾM VĂN BẢN .......................................................................................................................59 3.1 Giới thiệu .......................................................................................................59 3.2 Một số kỹ thuật nâng cao hiệu năng tìm kiếm đa phương tiện ........................60 3.2.1 Lọc bằng phân lớp, thuộc tính có cấu trúc và các từ khóa .....................60 3.2.2 Các phương pháp trên cơ sở tính không đều tam giác............................61 3.2.3 Mô hình tìm kiếm trên cơ sở cụm (cluster-based) ...................................63 3.2.3.1 Sinh cụm .........................................................................................63 3.2.3.2 Tìm kiếm trên cơ sở cụm .................................................................64 3.2.4 Chỉ mục ngữ nghĩa tiềm ẩn (LSI) để tìm kiếm thông tin trên cơ sở không gian vector ........................................................................................................64 3.3 Kỹ thuật LSI ..................................................................................................66 3.3.1 Giới thiệu LSI ........................................................................................66 3.3.2 Phương pháp luận LSI ...........................................................................67 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 4 - CHƯƠNG 4: PHÁT TRIỂN CHƯƠNG TRÌNH THỬ NGHIỆM ........................79 4.1 Giới thiệu bài toán .........................................................................................79 4.2 Chức năng chương trình .................................................................................79 4.3 Quy trình phát triển ứng dụng ........................................................................79 4.3.1 Xây dựng ma trận Term – Doc ...............................................................80 4.3.2 Lập chỉ mục tài liệu ..............................................................................80 4.3.3 Xây dựng ma trận trọng số ....................................................................80 4.3.4 Tìm kiếm theo mô hình vector ................................................................81 4.3.5 Phương pháp LSI ...................................................................................81 4.2 Cài đặt thử nghiệm .........................................................................................82 4.2.1 Giao diện màn hình lập chỉ mục ............................................................82 4.2.2 Giao diện màn hình cập nhập chỉ mục ...................................................83 4.2.2 Tìm kiếm tài liệu theo mô hình vector ....................................................83 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ..............................................................84 TÀI LIỆU THAM KHẢO ......................................................................................86 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 15 - phải cung cấp khả năng để tích hợp các loại dữ liệu này để tạo nên các kiểu dữ liệu MULTIMEDIA mới và thể hiện các dữ liệu này khi có yêu cầu trong một khung thời gian yêu cầu. Độ phức tạp của việc tích hợp, tổng hợp và thể hiện bị tăng thêm bởi các đặc tính cơ bản của dữ liệu MULTIMEDIA như tính liên tục (tạm thời) của dữ liệu MULTIMEDIA đặc biệt là với các kiểu dữ liệu như video, hoạt hình hoặc âm thanh. Hơn nữa, một vài ứng dụng cụ thể như các hệ thống thông tin địa lý có thể đòi hỏi MDBMS cung cấp các thông tin bộ phận (về một vùng, miền nào đó). Tất cả các yếu tố này kết hợp với nhau làm cho việc tổng hợp và thể hiện MULTIMEDIA trở thành một quy trình phức tạp mà MDBMS phải cung cấp để đáp ứng các yêu cầu mà người dùng đòi hỏi. Các vấn đề về tích hợp có thể được cải thiện trong một số trường hợp, đặc biệt là khi các hệ thống CSDL MULTIMEDIA được xây dựng nhằm phục vụ cho các cộng đồng người dùng xác định trước. Trong các trường hợp đặc biệt này, MDBMS có thể hỗ trợ một số tính năng mà các ứng dụng khác không cần đến. 1.2.4 Giao diện và tương tác. Sự khác nhau về bản chất của các dữ liệu MULTIMEDIA đòi hỏi phải có các giao diện khác nhau để tương tác với dữ liệu. Thông thường, mỗi loại dữ liệu có các phương thức truy nhập và thể hiện riêng của mình, ví dụ như dữ liệu video và âm thanh sẽ đòi hỏi các giao diện người dùng khác nhau để thể hiện và truy vấn. Đối với một vài ứng dụng Multimedia, đặc biệt là sự có mặt của các loại dữ liệu có tính liên tục người dùng thường đòi hỏi phải có các khả năng tương tác với dữ liệu ( chẳng hạn như đối với dữ liệu VCR thì người dùng thường mong muốn có chức năng như tua lên (fast forward) hoặc tua ngược lại (reverse)). Khi mà một hệ thống Multimedia cung cấp các dịch vụ như vậy thì nó phải được liên kết vào CSDL đặc biệt là việc khai thác các đối tượng, tổng hợp và đồng bộ chúng. 1.2.5 Hiệu suất. Hiệu suất là một vấn đề quan trọng cần được xem xét đối với một MDBMS. Các hệ thống CSDL MULTIMEDIA tạo ra hiệu suất dựa trên sự tối ưu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 16 - hoá việc truy nhập tới các media, lưu trữ, chỉ số hoá, khai thác và truy vấn . Sự có tham gia của nhiều kiểu dữ liệu khác nhau trong CSDL MULTIMEDIA có thể đòi hỏi một số phương thức đặc biệt để tối ưu hoá việc truy cập, lưu trữ, chỉ số hoá và khai thác. Các yêu cầu này bao gồm hiệu quả, tính ổn định, đảm bảo và đồng bộ việc trao đổi dữ liệu, chất lượng của dịch vụ (QoS). 1.3 Các vấn đề của MDBMS Để đáp ứng được các yêu cầu đã nêu ra ở phần trên, MDBMS cần phải xác định được một số vấn đề quan trọng bao gồm: • Mô hình hoá dữ liệu Multimedia. • Lưu trữ đối tượng Multimedia. • Tích hợp, trình diễn, chất lượng dịch vụ Multimedia. • Chỉ số hoá, khai thác và duyệt. • Hỗ trợ truy vấn Multimedia. • Quản trị dữ liệu Multimedia phân tán. • Hỗ trợ của hệ thống. 1.3.1 Mô hình hoá dữ liệu MULTIMEDIA Mô hình dữ liệu là đơn vị trung tâm của một hệ thống CSDL MULTIMEDIA. Một mô hình dữ liệu cần phải tách rời người dùng ra khỏi chi tiết của việc quản lý các thiết bị lưu trữ và cấu trúc lưu trữ. Điều này đòi hỏi phải phát triển các mô hình dữ liệu tương ứng để tổ chức các kiểu dữ liệu khác nhau tường gặp trong các hệ thống CSDL MULTIMEDIA. Các mô hình dữ liệu MULTIMEDIA (cũng giống như các mô hình dữ liệu truyền thống khác) nắm bắt các đặc tính cố định cũng như động của nội dung CSDL và vì vậy nó cung cấp các khuôn mẫu cơ bản cho việc phát triển các công cụ cần thiết để sử dụng dữ liệu MULTIMEDIA. Các thuộc tính cố định có thể bao gồm các đối tượng tạo nên dữ liệu MULTIMEDIA, mối liên hệ giữa các đối tượng, thuộc tính của các đối tượng…Các đặc tính động bao gồm sự tương tác Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 17 - giữa các đối tượng, sự hoạt động trên đối tượng, các tương tác của người dùng. Tuy nhiên, do các tính chất đặc biệt của mình, dữ liệu MULTIMEDIA đòi hỏi phải có các quan tâm mới khi chọn lựa mô hình dữ liệu. Ví dụ, một vài kiểu dữ liệu MULTIMEDIA (chẳng hạn video) hoặc một nhóm các kiểu (video và hình ảnh) có thể đòi hỏi các mô hình dữ liệu đăc biệt để cải thiện hiệu quả và tính mềm dẻo. Hơn nữa, do tầm quan trọng của việc tương tác trong các hệ thống MULTIMEDIA nên việc nó được hỗ trợ bỏi các mô hình dữ liệu trở nên quan trọng. Rât nhiều các mô hình dữ liệu khác nhau như là mạng lưới, liên hệ, ngữ nghĩa, và hướng đối tượng đang tồn tại và một vài số trong chúng đã được xem xét để thiết lập CSDL MULTIMEDIA. Có hai cách tiếp cận cơ bản trong việc mô hình hoá dữ liệu MULTIMEDIA là: • Phương pháp thứ nhất: xây dựn._.g một mô hình dữ liệu MULTIMEDIA trên nền tảng của mô hình dữ liệu của một CSDL truyền thống (thường là CSDL quan hệ hoặc CSDL hướng đối tượng) bằng cách sử dụng các giao diện tương ứng đối với dữ liệu MULTIMEDIA. Các vấn đề nẩy sinh với cách tiếp cận này là các cấu trúc bên dưới (của CSDL truyền thống) không được thiết kế dành cho dữ liệu MULTIMEDIA, hơn nữa sự khác biệt cơ bản các yêu cầu của một CSDL truyền thống đối với CSDL MULTIMEDIA khiến cho giao diện trở thành nơi nghẽn cổ chai trong toàn bộ hệ thống. Các vấn đề này dẫn tới cách tiếp cận thứ hai. • Phương pháp thứ hai: phát triển các mô hình dữ liệu thực thụ dành cho dữ liệu MULTIMEDIA từ đầu chứ không xây dựng trên cơ sở của các CSDL truyền thống, tuy nhiên mọi người đều nhất trí rằng các nỗ lực như vậy đều phải dựa trên kỹ thuật hướng đối tượng. 1.3.2 Lưu trữ đối tượng MULTIMEDIA Lưu trữ vật lý các dữ liệu Multimedia đòi hỏi các phương thức để chuyển đổi, quản lý, trao đổi và phân phối một số lượng dữ liệu khổng lồ, các hệ thống Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 18 - Multimedia thông thường sử dụng phương thức phân cấp đối với các thiết bị lưu trữ. Các thiết bị lưu trữ online có tốc độ cao như RAM, HDD lưu trữ các dữ liệu đang được xử lý trong khi đó các thiết bị lưu trữ offline (có tốc độ chậm) dùng để lưu trữ các dữ liệu có tính chất dài hạn, cố định. Khi đó, hiệu suất sẽ phụ thuộc vào khả năng của cơ chế chuyển đổi các dữ liệu Multimedia tương ứng với mức tối ưu hoá trong hệ thống lưu trữ phân cấp. Các cơ chế nén dữ liệu kết hợp với các cơ chế chuyển đổi dữ liệu giúp phần làm giảm các yêu cầu khổng lồ về mặt lưu trữ, phương thức cơ bản được sử dụng ở đây là chuyển đổi dữ liệu Multimedia sang một số vùng chuyển đổi để loại bỏ sự dư thừa của dữ liệu gốc, các quá trình giải nén sẽ làm nhiệm vụ chuyển đổi ngược các dữ liệu này về dạng gốc của nó. Quá trình này sẽ dẫn đến việc mất mát dữ liệu, tuy nhiên việc mất mát này đươc hầu hết các ứng dụng Multimedia cho phép. Phụ thuộc vào mức độ của hạt nhân mà một đối tượng Multimedia có thể thể hiện toàn bộ hoặc một phần đoạn video, một frame, một hình ảnh riêng lẻ thậm chí cả từng đối tượng cá thể trong một ảnh hoặc một đoạn video. Vấn đề chính đặt ra ở đây là khả năng lưu trữ có hạn, băng thông hạn chế của hệ thống lưu trữ các kênh truyền thông, tỷ lệ sẵn sàng của các loại dữ liệu Multimedia. Tỷ lệ sẵn sàng của dữ liệu chỉ ra số lượng dữ liệu tối thiểu cần thiết đối với mỗi đơn vị thời gian cần đáp ứng đối với các đòi hỏi về yêu cầu chất lượng trong quá trình thể hiện các đối tượng Multimedia. Đứng từ quan điểm này, các yêu cầu về lưu trữ của dữ liệu Multimedia được giải quyết bằng cách phân chia dữ liệu thành các đối tượng Multimedia nhỏ hơn để có thể lưu trữ trong các đơn vị lưu trữ nhỏ hơn. Với việc sắp xếp lưu trữ phân cấp, các đối tượng Multimedia có thể được lưu trữ ở các mức độ khác nhau, khi mà tỷ lệ sử dụng các đối tượng d ữ liệu Multimedia thay đổi các đối tượng này cần phải được phân phối lại có thể là được lưu trữ trên các thiết bị khác, tại các mức khác nhau của hệ thống lưu trữ. Vấn đề cần giải quyết lúc này chỉ là tìm ra giải pháp tối ưu cho việc phân rã, phân phối và Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 19 - tái phân phối các đối tượng Multimedia. 1.3.3 Tích hợp Multimedia, thể hiện và chất lượng của dịch vụ (QoS) Khác với các dữ liệu truyền thống, dữ liệu Multimedia đòi hỏi các ràng buộc về sự thể hiện điều này bắt nguồn từ đặc tính liên tục của một số kiểu dữ liệu Multimedia mà chúng đòi hỏi thể hiện một số lượng nhất định dữ liệu trong một khoảng thời gian nhất định mà kết quả đem lai cho người dùng vẫn phải đảm bảo được đặc trưng của các kiểu dữ liệu đó. Khi mà dữ liệu Multimedia được bố trí phân tán và truyền đi trên mạng thì các vấn đề về thể hiện càng trở nên cấp thiết hơn, chúng ta đã bắt gặp điều này trong trường hợp băng thông hạn chế. Các dữ liệu liên tục được định nghĩa là phục thuộc vào thời gian, vì vậy thời gian trở thành một yếu tố quan trọng trong việc phân phát và thể hiện chúng. Vì vậy trong MDBMS, thời gian hồi đáp đối với một câu hỏi thường được đánh giá bởi cả tính chính xác và chất lượng đối với các kết quả khai thác. Đứng từ quan điểm của người dùng, chất lượng, mức độ chấp nhận được về hiệu suất của các loại dịch vụ khác nhau được cung cấp bởi hệ thống Multimedia và có thể ảnh hưởng đến kết quả của việc thể hiện Multimedia. Vì vậy, để hỗ trợ cho việc thể hiện Multimedia trong điều kiện người dùng có thể xác định các mức độ QoS khác nhau đối với các dịch vụ khác nhau, MDBMS cần phải hỗ trợ các mức QoS và một dịch vụ quản lý QoS, chúng thông thường được thực hiện bằng cách cung cấp một ánh xạ tương ứng từ QoS của người dùng sang QoS của hệ thống và ngược lại. Khi thể hiện các loại dữ liệu Multimedia khác nhau chẳng hạn video và âm thanh cùng vớ i nhau các vấn đề về tích hợp và đồng bộ các loại phương tiện trở nên hết sức quan trọng. MDBMS cần phải cung cấp một cơ chế để đảm bảo sự đồng bộ trong việc thể hiện cũng như đáp ứng được các yêu cầu khác như tỷ lệ sẵn sàng của dữ liệu và QoS. Trong một vài trường hợp, MDBMS có thể phải dựa vào một cơ chế quản lý đồng bộ hoá để đảm bảo được sự đồng bộ với một kiểu dữ liệu cho trước hoặc giữa các kiểu dữ liệu khác nhau. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 20 - 1.3.4 Chỉ số hoá Multimedia Cũng như trong các CSDL truyền thống, các dữ liệu Multimedia có thể được khai thác thông qua các định danh, các thuộc tính, các từ khoá và sự liên kết giữa chúng. Các từ khoá là phương thức chiếm ưu thế trong việc sử dụng để chỉ số hoá dữ liệu Multimedia. Con người thường chọn các từ khoá từ một tập các từ vựng nhất định, điều này tạo ra một số khó khăn khi áp dụng đối với dữ liệu Multimedia vì chúng thường được làm một cách thủ công và rất tốn thời gian và các kết quả thường là chủ quan và rất hạn chế phụ thuộc vào từ vựng. Một phương thức khác được sử dụng dựa trên việc truy cập nội dung, nó xem xét đến nội dung thực sự của dữ liệu Multimedia hoặc xuất phát từ ngữ cảnh của thông tin. Trong thời gian gần đây, việc nghiên cứu chỉ số hoá dựa trên nội dung đã được tiến hành hết sức mạnh mẽ với mục đích là chỉ số hoá dữ liệu Multimedia dựa trên các đặc trưng xác định thu được trực tiếp từ dữ liệu. Các đặc trưng khác nhau như mầu sắc, hình dạng, kết cấu bề mặt, các chuỗi đặc trưng và các đặc trưng khác đã được dùng để chỉ số hoá các ảnh. Để thu được các đặc trưng này đòi hỏi phải phân tích tự động dữ liệu Multimedia, các phương thức chính được sử dụng đối với dữ liệu ảnh và dữ liệu video là xử lý ảnh, đoán nhận ảnh và phân tích chuỗi video. Đối với dữ liệu video, chuỗi video trước tiên được phân tách thành các chuỗi hợp thành, sau đó các đặc trưng tóm tắt (thường là các frame khoá) sẽ được lựa chọn để đặc trưng cho mỗi chuỗi. Việc chỉ số hoá tiếp theo đối với dữ liệu video cũng dựa trên các frame khoá cũng giống như đối với dữ liệu ảnh Đối với dữ liệu âm thanh, việc chỉ số hoá dựa trên nội dung có thể có sự tham gia của việc phân tích tín hiệu, tự động nhận biết lời nói cùng với việc chỉ số hoá dựa trên từ khoá. Mặt khác, việc chỉ số hoá có thể dựa trên các thông tin khác phụ thuộc vào kiểu của dữ liệu âm thanh, ví dụ một vài nhà phát triển đã sử dụng các đặc trưng về nhịp điệu, hợp âm và giai điệu cho việc chỉ số hoá dựa trên nội dung đối với dữ liệu âm thanh. Tương tự như vậy, việc tìm kiếm và khai thác dữ liệu âm thanh dựa trên nội dung đã được đề xuất dựa trên các đặc Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 21 - tính của dữ liệu âm thanh như đã được chỉ ra qua các đăc trưng về âm học và giác quan.. Việc chỉ số hoá dựa trên nội dung cũng gợi ra một vài vấn đề cần quan tâm. Trước hết, cũng với một dữ liệu Multimedia nhưng mỗi người có thể hiểu theo một cách khác nhau. Thứ hai, người dùng thường cần các thông tin thay đổi khác nhau, vì vậy một đặc trưng duy nhất có thể là không đủ để chỉ số hoá hoàn toàn một kiểu dữ liệu Multimedia cho trước. Một vấn đề khác cần phải xem xét là vấn đề hiệu quả, việc chỉ số hoá phải nhanh và các chỉ số này phải được lưu trữ một cách hiệu quả để phục vụ cho việc truy cập dễ dàng khi mà số lượng các dữ liệu Multimedia được lưu trữ là rất lớn. Bởi vì đặc tính vốn có của dữ liệu Multimedia là rất khác nhau nên việc chỉ số hoá không thể tiến hành một cách hoàn toàn tự động, đơn cử như máy tính có thể phân tích dễ dàng một bức ảnh có chứa các tác phẩm nghệ thuật, nhưng nó gần như không thể tự động xác định được ý nghĩa của tác phẩm đó, điều đó chỉ có con người làm được. 1.3.5 Hỗ trợ truy vấn Multimedia, khai thác và duyệt qua. Các câu hỏi của người dùng thường được xử lý sử dụng các chỉ số có sẵn, tuy nhiên khác với CSDL truyền thống tính chính xác trong tìm kiếm đối với dữ liệu Multimedia không phải là chính xác tuyệt đối. Thông thường khi so sánh hai dữ liệu Multimedia thì kết quả thu được thường là gần đúng hoặc tương tự, giả sử trong trường hợp các dữ liệu này có cùng dữ liệu đầu vào thì kết quả thu được từ một câu hỏi có thể sinh ra rất nhiều giá trị. Đã có rất nhiều các nghiên cứu đi sâu vào việc tìm ra một phương thức thích hợp trợ giúp cho người dùng có được một khả năng hiệu quả để khai thác các dữ liệu Multimedia, chẳng hạn thông qua việc cung cấp các giao diện thích hợp để người dùng có thể duyệt một cách thuận lợi các kết quả có được từ quá trình tìm kiếm. Việc hỗ trợ duyệt một cách trực tiếp cho phép người sử dụng có thể khai thác bất kỳ thông tin nào có khả năng liên quan đến kết quả hiện thời bằng cách lựa chọn các mục dữ liệu tương ứng cần quan tâm sâu hơn. Truy vấn bằng ví dụ (Query-by-Example) là một phương thức chính được Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 22 - sử dụng để nhập các câu hỏi đối với CSDL Multimedia, đặc biệt là đối với dữ liệu ảnh. Ở đây người dùng đưa ra các yêu cầu bằng cách sử dụng một mẫu có sẵn (ví dụ như một ảnh tương tự), vì vậy giao diện được sử dụng để nhập câu hỏi vào hệ thống trở thành một vấn đề cần phải quan tâm. Do tính chất đa dạng của các kiểu dữ liệu Multimedia nên mỗi kiểu dữ liệu Multimedia có thể phải có các giao diện truy vấn khác nhau, vấn đề cần được xem xét ở đây là làm thế nào để tích hợp được các giao diện khác nhau vào một hệ thống tích hợp CSDL Multimedia. Một vấn đề khác cũng cần phải giải quyết là việc bao gồm truy vấn các dữ liệu không gian hoặc truy vấn các dự liệu tạm thời đòi hỏi phải có các thông tin không gian hoặc tạm thời. 1.3.6 Quản trị CSDL Multimedia phân tán MDBMS phân tán có thể được hiểu là một bộ các MDBMS độc lập (các MDBMS này có thể rất khác nhau) nằm tại các vị trí khác nhau mà có thể giao tiếp hoặc trao đổi dữ liệu Multimedia với nhau thông qua mạng. Các hệ thống Multimedia thường được phân tán với quan niệm một sự tương tác Multimedia đơn lẻ thường liên quan đến việc dữ liệu thu được từ các nguồn thông tin phân tán khác nhau. Điều này thường thấy trong các môi trường Multimedia cộng tác khi mà các người dùng có thể từ các địa điểm vật lý khác nhau thao tác và là người tạo ra cùng một tài liệu Multimedia. Ngoài ra, các vấ n đề về lưu trữ và phát sinh dữ liệu bắt buộc các nhà thiết kế hệ thống Multimedia phải bố trí dữ liệu Multimedia ở các địa điểm khác nhau. Để hỗ trợ cho việc truy vấn trong môi trường phân tán và cộng tác này , một MDBMS phân tán phải xác định được các vấn đề tổng quát của CSDL phân tán như xử lý truy vấn phân tán và song song, quản trị các giao dịch phân tán , sự trong suốt dữ liệu, an toàn dữ liệu.. Ngoài ra các vấn đề về hệ thống mạng như băng thông hoặc độ trễ cũng là các vấn đề quan trọng cần phải lưu tâm nhất là khi chúng có xu hướng bất lợi đối với việc hỗ trợ QoS. Không giống như DBMS truyền thống, việc tái tạo dữ liệu thường không được khuyến khích trong MDBMS phân tán do số lượng dữ liệu khổng lồ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 23 - Mô hình tính toán Khách-Chủ (client-server), trong đó các dịch vụ ứng dụng của máy chủ phục vụ cho nhiều ứng dụng khách khác nhau (các dịch vụ của server và các ứng dụng client có thể nằm ở các máy khác nhau) đã được chứng minh là thích hợp nhất cho các các hệ thống Multimedia trong cả trường hợp tổng quát cũng như đối với MDBMS phân tán. 1.3.7 Sự hỗ trợ của hệ thống Các ứng dụng Multimedia và các hệ thống CSDL Multimedia phân tán đặt ra các yêu cầu mới đối với tất cả các khía cạnh của hệ thống máy tính, từ các yêu cầu về hệ điều hành, hệ thống mạng cũng như các yêu cầu về phần cứng. Hầu hết các hệ điều hành hiện tại chưa hỗ trợ các xử lý mang tính thời gian thực. Một vài dữ liệu Multimedia chẳng hạn như các dữ liệu có tính liên tục có thể đòi hỏi các tính năng phân phát và thể hiện thời gian thực mặc dù các yêu cầu về thời gian thực này có thể không nghiêm ngặt như đối với các yêu cầu về thời gian thực thường bắt gặp đối với phần cứng. Vì vậy, các hệ thống CSDL Multimedia không thể cung cấp đầy đủ các tính năng cần thiết theo yêu cầu trừ khi các hỗ trợ thời gian thực cho các thiết bị Multimedia trở thành một phần không thể thiếu của hệ điều hành. Các đặc tính khác của Multimedia chẳng hạn như số lượng lớn dữ liệu cần phải lưu trữ có thể đòi hỏi một số ràng buộc đặc biệt đi với hệ thống về mặt quản lý bộ nhớ, hiệu suất của CPU. Các vấn đề khác cũng cần phải xem xét đến ở đây bao gồm việc quản lý cơ chế vào/ra (I/O) của phần cứng nhằm mục đích hỗ trợ cho các kiểu khác nhau có mặt trong CSDL Multimedia, hệ thống mạng viễn thông cũng phải đảm bảo cho việc truyền tải dữ liệu cho các môi trường Multimedia phân tán đáp ứng các đòi hỏi nghiêm ngặt của QoS đố i với các ứng dụng cụ thể. 1.4 Kết luận CSDL multimedia và các vấn để khác có liên quan đến nó như việc tổ chức, khai thác nội dung thông tin vv.. đã và đang là những vấn đề mang tính thời sự của Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 24 - CNTT. Trong chương này của bản luận văn đã đề cập được một số vấn đề mang tính chất cơ sở của cơ sở dữ liệu đa phương tiện như cách thức và mô hình lưu trữ dữ liệu, cách thức chỉ số hoá cũng như các yêu cầu và các vấn đề cần được giải quyết đối với một hệ thống quản trị cơ sở dữ liệu đa phương tiện (MDBMS). Tuy nhiên, với mục đích và yêu cầu của chủ đề nghiên cứu là trình bày các vấn đề liên quan đến việc tìm kiếm dữ liệu văn bản theo nội dung trong c ơ sở dữ liệu đa phương tiện nên trong chương tiếp theo của luận văn này sẽ trình bày một số kỹ thuật chỉ mục và tìm kiếm tài liệu văn bản. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 25 - CHƯƠNG 2: MỘT SỐ KỸ THUẬT CHỈ MỤC VÀ TÌM KIẾM VĂN BẢN THEO NỘI DUNG 2.1 Giới thiệu hệ tìm kiếm thông tin 2.1.1 Kỹ thuật tìm kiếm thông tin Kỹ thuật truy vấn tài liệu văn bản được gọi chung là kỹ thuật tìm kiếm thông tin (IR – Information Retrieval). Kỹ thuật IR trong hệ thống đa phương tiện rất quan trọng vì hai lý do chính sau đây: • Đang tồn tại số lượng lớn tài liệu văn bản trong các thư viện. Mà văn bản là tài nguyên rất quan trọng đối với các cơ quan tổ chức. Do đó cần có IR đủ tốt để sử dụng có hiệu quả các thông tin lưu trữ trong các tài liệu. • Văn bản được sử dụng để mô tả các media khác như video, audio, ảnh để có thể sử dụng các kỹ thuật IR qui ước vào việc truy vấn các thông tin đa phương tiện. Hai nhiệm vụ chính của thiết kế hệ thống IR nhằm giải quyết vấn đề sau: • Trình diễn và truy vấn tài liệu như thế nào? • So sánh tính tương đồng giữa các tài liệu và biểu diễn truy vấn ra sao? Các mô hình truy vấn sẽ xác định hai khía cạnh này. Có bốn mô hình truy vấn hay được sử dụng, đó là: • Đối sánh chính xác (exact match), • Không gian vector, • Xác suất • Trên cơ sở cụm (cluster-based). Trong kỹ thuật đối sánh chính xác (hoàn toàn), mô hình Boolean hay được sử dụng nhất. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 26 - Mặc dù các mô hình truy vấn khác nhau, sử dụng sự trình diễn và chỉ mục tài liệu khác nhau, nhưng nói chung tiến trình chỉ mục được sử dụng trong chúng là tương tự nhau. Để nâng cao hiệu năng truy vấn, việc xử lý ngôn ngữ tự nhiên và các kỹ thuật trí tuệ nhân tạo được áp dụng. Vì tính nhập nhằng và tồn tại nhiều biến thể của ngôn ngữ tự nhiên, cho nên hầu như không thể truy vấn mọi tài liệu ( items) liên quan hay loại đi mọi tài liệu không liên quan. Do vậy, thước đo hiệu năng IR là rất quan trọng. Các kỹ thuật IR rất phổ biến vì nó được sử dụng trong các môtơ tìm kiếm của WWW. 2.1.2 Một số vấn đề trong tìm kiếm thông tin Kể từ những năm 40, các vấn đề trong việc lưu trữ thông tin và tìm kiếm thông tin đã thu hút sự chú ý rất lớn. Với một lượng thông tin khổng lồ thì việc tìm kiếm chính xác và nhanh chóng càng trở nên khó khăn hơn. Với sự ra đời của máy tính, rất nhiều ý tưởng lớn được đưa ra nhằm cung cấp một hệ thống tìm kiếm thông minh và chính xác. Tuy nhiên, vấn đề tìm kiếm sao cho hiệu quả vẫn chưa được giải quyết. Về nguyên tắc, việc lưu trữ thông tin và tìm kiếm thông tin thì đơn giản. Giả sử có một kho chứa các tài liệu và một người muốn tìm các tài liệu liên quan đến yêu cầu của mình. Người đó có thể đọc tất cả các tài liệu trong kho, giữ lại các tài liệu liên quan và bỏ đi các tài liệu không liên quan. Rõ ràng giải pháp này không thực tế bởi vì tốn rất nhiều thời gian. Với sự ra đời của máy vi tính tốc độ cao, máy tính có thể “đọc” thay cho con người để trích ra các tài liệu có liên quan trong toàn bộ tập dữ liệu. Tuy nhiên vấn đề lúc này là làm sao để xác định được tài liệu nào liên quan đến yêu cầu của người sử dụng. Do đó, mục tiêu của một hệ thống tìm kiếm thông tin tự động là truy tìm được tất cả các tài liệu có liên quan đến yêu cầu của người sử dụng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 27 - 2.1.3 Hệ thống tìm kiếm thông tin – IRS Các hệ thống tự động tìm kiếm thông tin (IR - Information Retrieval) đã được phát triển để quản lý khối lượng lớn tài liệu từ những năm 40 của thế kỷ XX. Chức năng chính của hệ thống IR là lưu trữ và quản trị khối lượng văn bản lớn theo cách sao cho dễ dàng truy vấn ( query) tài liệu mà người sử dụng quan tâm. Chú ý rằng đồng nghĩa với IR là text IR dù rằng ý nghĩa đầy đủ của khái niệm IR là đề cập đến tìm kiếm bất kỳ loại thông tin nào. Sau đây là định nghĩa về hệ thống tìm kiếm thông tin của một số tác giả: Salton (1989): “Hệ thống tìm kiếm thông tin xử lý các tập tin lưu trữ và những yêu cầu về thông tin, xác định và tìm từ các tập tin những thông tin phù hợp với những yêu cầu về thông tin. Việc tìm kiếm những thông tin đặc thù phụ thuộc vào sự tương tự giữa các thông tin được lưu trữ và các yêu cầu, được đánh giá bằng cách so sánh các giá trị của các thuộc tính đối với thông tin được lưu trữ và các yêu cầu về thông tin.” Kowalski (1997) : “Hệ thống tìm kiếm thông tin là một hệ thống có khả năng lưu trữ, tìm kiếm và duy trì thông tin. Thông tin trong những trường hợp này c ó thể bao gồm văn bản, hình ảnh, âm thanh, video và những đối tượng đa phương tiện khác.” Tìm kiếm thông tin là lĩnh vực nghiên cứu nhằm tìm ra các giải pháp giúp người sử dụng có thể tìm thấy các thông tin mình cần trong một khối lượng lớn dữ liệu. Nhiệm vụ của một hệ thống tìm kiếm thông tin tương tự như nhiệm vụ tổ chức phân loại tài liệu và phục vụ việc tra cứu của một thư viện. Một hệ thống tìm kiếm thông tin có hai chức năng chính: lập chỉ mục (indexing) và tra cứu (interrogation). Lập chỉ mục là giai đoạn phân tích tài liệu (document) để xác định các chỉ mục (term/index term) biểu diễn nội dung của tài liệu. Việc lập chỉ mục có thể dựa vào một cấu trúc phân lớp có sẵn (control vocabulary) như cách làm của các nhân viên thư viện, phân loại tài liệu theo một bộ phân loại cho trước. Các chỉ mục trong cách làm này là tồn tại trước và độc lập với tài liệu. Cách thứ hai để lập chỉ mục là rút Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 28 - trích các chỉ mục từ chính nội dung của tài liệu (free text). Trong luận văn này tác giả chỉ đề cập đến cách thứ hai này. Cuối giai đoạn lập chỉ mục nội dung của các tài liệu có trong kho tài liệu (corpus) được biểu diễn bằng tập các chỉ mục. Mô hình tổng quát tìm kiếm thông tin: Hình 2.1 Mô hình tổng quát tìm kiếm thông tin Mô hình 2.1 gồm 4 thành phần: • Mô hình yêu cầu: Sử dụng để biểu diễn yêu cầu của người sử dụng. • Mô hình tài liệu: Biểu diễn trừu tượng tài liệu thực và nội dung của chúng. • Hàm ánh xạ (đối sánh) : Xác định sự phù hợp của hệ thống đối với yêu cầu. • Tri thức: Biểu diễn các tri thức để mô tả ngữ nghĩa thuộc lĩnh vực tài liệu. Biểu diễn hình thức: D – Biểu diễn các tài liệu Docs Q – Biểu diễn câu truy vấn Query (yêu cầu) Truy cập Mô hình tìm kiếm thông tin Phù hợp người sử dụng Người sử dụng Phù hợp hệ thống Tài liệu Mô hình yêu cầu Mô hình tài liệu Đối sánh Tri thức Các yêu cầu CSDL tài liệu Hệ thống cụ thể Thế giới thực Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 29 - F- Khung mô hình hóa của D, Q và quan hệ giữa chúng R(q, di) – Hàm đối sánh hay xếp hạng Quy trình của hệ thống tìm kiếm thông tin như sau: + Người sử dụng muốn xem tài liệu liên quan đến một chủ đề nào đó. + Người sử dụng cung cấp mô tả về tài liệu muốn xem dưới dạng câu truy vấn. + Từ câu truy vấn này hệ thống lọc ra những cụm từ và chỉ mục của tài liệu đã được xử lý trước đó. + Những tài liệu nào liên quan cao nhất với mô tả sẽ được trả về cho người sử dụng. Mục đích của IR là hiển thị một tập thông tin thỏa mãn nhu cầu của người sử dụng. Chúng ta định nghĩa thông tin yêu cầu là câu truy vấn (Query), thông tin tìm được là tài liệu (Document). Mục đích của hệ thống IR là tự động tìm kiếm các tài liệu bằng cách kiểm tra độ tương quan giữa câu truy vấn và đặc trưng của tài liệu. Kết quả thành công khi kết quả trả về của hệ thống phù hợp với yêu cầu của câu truy vấn. Hệ thống IR gồm các bản ghi không có cấu trúc. Chúng không chứa các thuộc tính cố định. Nó chỉ đơn thuần là tài liệu văn bản. Các tài liệu này có thể chỉ mục bằng các từ khóa, bộ mô tả tài liệu, hay các thuật ngữ (term) chỉ mục. Mỗi thuật ngữ chỉ mục được sử dụng để mô tả nội dung văn bản chỉ theo một khía cạnh nào đó, không đầy đủ và không rõ ràng cho toàn bộ nội dung văn bản. Nhiều thuật ngữ chỉ mục được gắn theo tài liệu hay văn bản cụ thể. Bởi vì các thao tác truy vấn văn bản phụ thuộc trực tiếp vào nội dung đại diện, sử dụng để mô tả các bản ghi lưu trữ, do vậy cần phải có nhiều cố gắng để tập trung vào phân tích nội dung của các tài liệu lưu trữ và vấn đề sinh từ khóa, chỉ mục. Ở đây, sẽ không thực tế nếu coi trọng truy vấn trên cơ sở đối sánh chính xác giữa câu truy vấn và các thuật ngữ tài liệu để tìm ra tài liệu kết quả. Thay vì, truy vấn các mục liên quan với đủ mức độ tương đồng giữa tập thuật ngữ gắn theo câu truy vấn và tài liệu, được sinh ra bởi phương pháp xấp xỉ hay đối sánh từng phần. Hơn nữa cùng thuật ngữ có thể có nhiều ý nghĩa khác nhau. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 30 - Tóm lại, các tài liệu kết quả truy vấn trong DBMS là hoàn toàn liên quan đến câu truy vấn và có ích với người sử dụng. Nhưng trong hệ thống IR, các tài liệu được xem như liên quan đến câu truy vấn nhưng có thể không liên quan và không có ích với người sử dụng. Hình 2.2 chỉ ra tiến trình truy vấn tài liệu cơ sở. Phía phải hình 2.2 chỉ ra rằng các tài liệu được xử lý off-line để có đại diện (mô tả). Các đại diện này được lưu trữ cùng với các tài liệu. Phía trái hình 2.2 chỉ ra quá trình truy vấn. Người sử dụng đưa ra câu truy vấn và được xử lý on-line để có đại diện của mình. Sau đó đối sánh đại diện truy vấn với đại diện tài liệu. Các tài liệu được xem như tương đồng sẽ được trình diễn cho người sử dụng. Họ đánh giá tài liệu cho lại và quyết định tài liệu nào thực sự tương đồng với thông tin họ cần. Một hệ thống IR tốt cần phải cho phép người sử dụng cung cấp phản hồi thích hợp cho hệ thống. Hệ thống sử dụng thông tin này để điều chỉnh truy vấn, đại diện truy vấn, hoặc/và đại diện tài liệu. Tìm kiếm khác tiếp theo được thực hiện trên cơ sở câu truy vấn đại diện tài liệu đã hiệu chỉnh. Nếu cần, tiến trình phản hồi tìm kiếm được thực hiện lặp vài lần. Chú ý rằng, không phải tất cả các hệ thống IR đều có tiến trình phản hồi thích hợp. Query Tài liệu văn bản Đại diện query Đại diện tài liệu Xử lý Xử lý Đối sánh (tính toán độ tương đồng) Tài liệu truy vấn Đánh giá mức độ thích hợp và phản hồi Hình 2.2 Tiến trình truy vấn tài liệu cơ sở Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 31 - Các mô hình IR khác nhau sử dụng các phương pháp khác nhau trong đại diện truy vấn và đại diện tài liệu, đối sánh tương đồng hoặc/và phản hồi thích hợp. Kiến trúc của hệ tìm kiếm thông tin: Hình 2.3. Mô hình kiến trúc của hệ tìm kiếm thông tin Hình 2.4 Cấu trúc hệ tìm kiếm thông tin tiêu biểu Giao diện người sử dụng Các tính toán cho văn bản Tính toán cho câu truy vấn Lập chỉ mục Quản trị cơ sở dữ liệu Tệp chỉ mục Tìm kiếm NSD yêu cầu NSD phản hồi Truy vấn Tài liệu đã sắp xếp Cơ sở dữ liệu văn bản Chỉ mục Tìm kiếm tài liệu Văn bản Săp xếp (1) (2) (3) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 32 - Hệ thống tìm kiếm thông tin gồm có 3 bộ phận chính: bộ phận phân tích văn bản, bộ phận lập chỉ mục, bộ phận so khớp và sắp xếp các tài liệu trả về. (1) Bộ phận phân tích văn bản: bộ phận này có nhiệm vụ phân tích các văn bản thu thập được thành các từ riêng biệt. Tương tự, khi người dùng nhập câu truy vấn thì câu truy vấn cũng được phân tích thành các từ riêng biệt. (2) Bộ phận lập chỉ mục: các từ trích được từ các văn bản thu thập được sẽ được bộ phận này lựa chọn để làm các từ chỉ mục. Các từ chỉ mục phải là các từ thể hiện được nội dung của văn bản. Hai bộ phận phân tích văn bản và lập chỉ mục thường đi liền với nhau và thường chỉ gọi là bộ phận lập chỉ mục (3) Bộ phận so khớp và sắp xếp các tài liệu trả về: Các từ trích được từ câu truy vấn và các từ chỉ mục của văn bản sẽ được so khớp với nhau để tìm ra các tài liệu liên quan đến câu truy vấn. Mỗi tài liệu có một độ tương quan với câu truy vấn. Các tài liệu này sẽ được sắp xếp theo độ tương quan giảm dần và trả về cho người sử dụng. 2.1.4 Sự khác biệt giữa các hệ thống IR và các hệ thống thông tin khác Hệ thống tìm kiếm thông tin cũng tương tự như nhiều hệ thống xử lý thông tin khác. Hiện nay các hệ thống thông tin quan trọng nhất là: hệ quản trị cơ sở dữ liệu (DBMS), hệ quản lý thông tin (MIS), hệ hỗ trợ ra quyết định (DSS), hệ trả lời câu hỏi (QAS) và hệ tìm kiếm thông tin (IR). Việc hiểu biết sự khác nhau giữa hai hệ thống tìm kiếm văn bản (IR) và các hệ thống thông tin khác giúp ta hiểu rõ các kỹ thuật tìm kiếm văn bản. Hệ quản trị cơ sở dữ liệu: Bất cứ hệ thống thông tin tự động nào cũng dựa trên một tập các mục được lưu trữ (gọi là cơ sở dữ liệu) cần thiết cho việc truy cập. Do đó hệ quản trị cơ sở dữ liệu đơn giản là một hệ thống được thiết kế nhằm thao tác và duy trì điều khiển cơ sở dữ liệu. DBMS tổ chức lưu trữ các dữ liệu của mình dưới dạng các bảng. Mỗi một cơ sở dữ liệu được lưu trữ thành nhiều bảng khác nhau. Mỗi một cột trong bảng là một Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 33 - thuộc tính, và mỗi một dòng là một bộ dữ liệu cụ thể. Trong mỗi một bảng có một thuộc tính duy nhất đại diện cho bảng, nó không được trùng lặp và ta gọi đó là khoá chính. Các bảng có mối liên hệ với nhau thông qua các khoá ngoại. Hệ quản tri cơ sở dữ liệu có một tập các lệnh để hỗ trợ cho người sử dụng truy vấn đến dữ liệu của mình. Vì vậy muốn truy vấn đến cơ sở dữ liệu trong hệ quản trị cơ sở dữ liệu ta phải học hết các tập lệnh này. Nhưng ngược lại nó sẽ cung cấp cho ta các dữ liệu đầy đủ và hoàn toàn chính xác. Hiện nay hệ quản trị cơ sở dữ liệu được sử dụng rộng rãi trên thế giới. Một số hệ quản trị cơ sở dữ liệu thông dụng: Access, SQL Server, Oracle. Hệ quản lý thông tin (IMS): Hệ quản lý thông tin là hệ quản trị cơ sở dữ liệu nhưng có thêm nhiều chức năng về việc quản lý. Những chức năng quản lý này phụ thuộc vào giá trị của nhiều kiểu dữ liệu khác nhau. Nói chung bất kỳ hệ thống nào có mục đích đặc biệt phục vụ cho việc quản lý thì ta gọi nó là hệ quản lý thông tin. Hệ hỗ trợ ra quyết định (DSS) Hệ hỗ trợ ra quyết định sẽ dựa vào các tập luật được học, từ những luật đã học rút ra những luật mới, sau khi gặp một vấn đề nó sẽ căn cứ vào vào tập các luật để đưa ra những quyết định thay cho con người. Hệ thống này đang được áp dụng nhiều cho công việc nhận dạng và chuẩn đoán bệnh. Hệ trả lời câu hỏi (QAS): Hệ trả lời câu hỏi cung cấp việc truy cập đến các thông tin bằng ngôn ngữ tự nhiên. Việc lưu trữ cơ sở dữ liệu thường bao gồm một số lượng lớn các vấn đề liên quan đến các lĩnh vực riêng biệt và các kiến thức tổng quát. Câu hỏi của người dùng có thể ở dạng ngôn ngữ tự nhiên. Công việc của hệ trả lời câu hỏi là phân tích câu truy vấn của người dùng, so sánh với các tri thức được lưu trữ, và tập hợp các vấn đề có liên quan lại để đưa ra câu trả lời thích hợp. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 34 - Tuy nhiên, hệ trả lời câu hỏi chỉ đang thử nghiệm. Việc xác định ý nghĩa của ngôn ngữ tự nhiên dường như vẫn là chướng ngại lớn để có thể sử dụng rộng rãi hệ thống này. Bảng 2.1: So sánh IRS với các hệ thống thông tin khác: IRS DBMS QAS IMS Tìm kiếm Nội dung trong các tài liệu. Các phần tử có kiểu dữ liệu đã được định nghĩa. Các sự kiện rõ ràng. Giống DBMS nhưng hỗ trợ thêm những thủ tục (Tín._.g đều tam giác được sử dụng trong mọi kỹ thuật tìm kiếm mà thước đo khoảng cách của chúng là metric. 3.2.3 Mô hình tìm kiếm trên cơ sở cụm (cluster-based) Trong các mô hình tìm kiếm thông tin đã khảo sát trong Chương 2 cũng như đầu Chương 3, các tài liệu tương tự có thể không gần kề trong hệ thống tệp. Với loại tổ chức tệp này, rất khó cài đặt khả năng duyệt (browsing). Hiệu quả của tìm kiếm sẽ thấp vì không thể tìm ra mọi mục phù hợp và phải tìm kiếm trên toàn bộ không gian tài liệu. Để khắc phục nhược điểm này, ta thực hiện cụm (nhóm) các tài liệu tương đồng vào các cụm (cluster). 3.2.3.1 Sinh cụm Hai tiệm cận tổng quát khi sinh cụm là: • Tiệm cận thứ nhất: Trên cơ sở tính tương tự mọi cặp (pairwise) tài liệu, hãy nhóm các mục tương tự vào cụm chung. Trong tiệm cận trên cơ sở tính tương tự từng cặp, mỗi tài liệu được đại diện như “vector tài liệu” trong mô hình không gian vector. Sau đó mức độ tương đồng giữa cặp tài liệu được tính toán. Trong tiến trình cụm, mỗi tài liệu được khởi đầu trong một lớp (class) và sau đó hai tài liệu tương tự nhau nhất trên cơ sở tính tương tự của cặp được tổ hợp trong một cụm. Tính tương đồng giữa cụm mới hình thành và các tài liệu khác được tính toán, sau đó tài liệu tương đồng nhất (kể cả cụm) được tổ hợp vào cụm mới. Tiến trình tổ hợp tiếp tục cho mọi tài liệu được nhóm vào cụm cao hơn. Đó là tiến trình cụm phân cấp. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 64 - Các phương pháp cụm phân cấp trên cơ sở tính tương đồng giữa các t ài liệu là khá đắt khi thực hiện. Nhưng phương pháp này sinh ra tập duy nhất các cụm cho mỗi tập tài liệu. • Tiệm cận thứ hai: Sử dụng phương pháp Heuristic không đòi hỏi tính toán tính tương tự cặp tài liệu. Phương pháp này sinh ra nhanh các cụm thô và tươn g đối rẻ hơn phương pháp trên. Tiến trình heuristic đơn giản nhất (tiến trình một bước) lấy các tài liệu sẽ cụm theo thứ tự tùy ý. Lấy tài liệu thứ nhất để đặt vào cụm. Mỗi tài liệu tiếp theo sẽ so sánh với các cụm trước đó, rồi đặt vào cụm tồn tại nếu đủ tính tương đồng với cụm đó. Nếu tài liệu không đủ tính tương đồng với các cụm có sẵn thì để vào cụm mới. Tiến trình này tiếp tục cho đến khi mọi tài liệu được cụm. Cấu trúc cụm được sinh ra theo cách này phụ thuộc vào thứ tự trong đó tài liệu được xử lý. 3.2.3.2 Tìm kiếm trên cơ sở cụm Khi các cụm (nhóm) được hình thành, tìm kiếm tài liệu sẽ hiệu quả. Mỗi cụm có vector đại diện, thường là tâm của chúng. Tâm của cụm được tính bằng vector trung bình của mọi tài liệu trong nhóm (trọng số của thuật ngữ tâm i được xác định bằng trọng số trung bình của mọi thuật ngữ i trong mọi tài liệu). Trong khi tìm kiếm tài liệu, các vector câu truy vấn được so sánh với tâm của các cụm. Sau khi nhận ra cụm có tính tương đồng cao nhất với vector truy vấn, sẽ có hai khả năng: • Mọi tài liệu trong cụm được tìm ra. Điều này xảy ra khi các cụm đều nhỏ. • Vector tìm kiếm được so sánh với từng vector tài liệu trong cụm và chỉ tài liệu nào có tính tương đồng cao nhất thì được tìm ra làm kết quả. 3.2.4 Chỉ mục ngữ nghĩa tiềm ẩn (LSI) để tìm kiếm thông tin trên cơ sở không gian vector Một kỹ thuật khác được áp dụng để tìm kiếm thông tin đa phương tiện đó là kỹ thuật chỉ mục ngữ nghĩa tiềm ẩn (Latent Semantic Indexing – LSI). Ý tưởng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 65 - cơ bản của kỹ thuật này là sử dụng một ma trận phân tích để xác định những thành phần chính của vector không gian được xác định bởi tập tài liệu, và sau đó chiếu vector lên không gian được mở rộng bởi những thành phần chính đó. Trong kỹ thuật LSI, những thành phần chính được xem là thể hiện cho những khái niệm quan trọng, trong khi những thành phần ít quan trọng hơn được xem là những biến đổi trong cách sử dụng khác nhau của từ. Vì thế LSI nhấn mạnh khía cạnh quan trọng của tfi.df và bỏ qua hiệu quả của cách sử dụng từ ngữ khác nhau. Sau đó, các tài liệu được so sánh bằng cách sử dụng phép đo độ tương đồng bằng hàm số cosin và kết quả sẽ được sắp xếp theo độ tương đồng để hiển thị. LSI là một kỹ thuật khá hiệu quả trong tìm kiếm văn bản, nên tác giả luận văn sẽ đi sâu nghiên cứu về kỹ thuật này và chi tiết sẽ được trình bày trong mục tiếp theo của chương. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 66 - 3.3 Kỹ thuật LSI 3.3.1 Giới thiệu LSI Trong mô hình không gian vector, mỗi tài liệu được biểu diễn bởi một vector trọng số thuật ngữ N chiều, mỗi thành phần của vector là trọng số của từng thuật ngữ trong số N thuật ngữ của tài liệu. Nếu tập tài liệu có M tài liệu, thì tập tài liệu này được biểu diễn bằng ma trận A kích thước MxN. Trong khi tìm kiếm, câu truy vấn cũng được biểu diễn bằng vector trọng số thuật ngữ N chiều. Tính tương đồng giữa truy vấn và từng tài liệu lưu trữ được tính bằng tích vô hướng hay hệ số cosin giữa vector truy vấn và vector tài liệu. Tiệm cận trực tiếp trên đây có hai yếu điểm sau đây: • Yếu điểm thứ nhất: Tập hợp tài liệu (thí dụ thư viện) có thể chứa đến hàng triệu tài liệu với nhiều ngàn khái niệm (M và N rất lớn). Vậy đòi hỏi tổng số bộ nhớ rất lớn để lưu trữ. Thí dụ, nếu thư viện có 1 triệu tài liệu với 10 000 thuật ngữ thì chúng ta cần đến 10GB bộ nhớ lưu trữ với mỗi phần tử chiếm 1 byte. • Yếu điểm thứ hai: Ít nhất cần M phép nhân vector N chiều khi tìm kiếm nếu sử dụng thước đo tương tự tích vô hướng và đòi hỏi nhiều hơn thế nếu sử dụng thước đo tương tự hệ số cosin. Khi M và N lớn, thời gian đòi hỏi để tính toán sẽ không đáp ứng với việc tìm kiếm trực tuyến. Chỉ mục ngữ nghĩa tiềm ẩn (LSI - Latent Semantic Indexing) được Falotsos, Foltz, Dumais và Bently phát triển để giải quyết một phần khó khăn trên. Ý tưởng cơ bản của LSI là thực hiện nhóm các thuật ngữ tương đương để hình thành “khái niệm” hay “chủ đề” và tài liệu sẽ được đại diện bởi các khái niệm hay chủ đề này. Vì tổng số khái niệm sẽ nhỏ hơn nhiều so với tổng số thuật ngữ, do vậy đòi hỏi ít bộ nhớ lưu trữ hơn và thời gian tính toán sẽ nhanh hơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 67 - Mô hình LSI Mô hình không gian Term – Doc Mô hình term – topic - doc Hình 3.1. Mô hình LSI Mô hình này minh hoạ một cách tiếp cận trực tiếp hơn mối liên quan giữa các tài liệu và các thuật ngữ như trong truy tìm vector, trong đó tồn tại một lớp giữa trong đó bao gồm cả lược đồ câu truy vấn và lược đồ tài liệu. Không gian của khái niệm có thể có kích thước nhỏ hơn. Chẳng hạn, chúng ta có thể xác định rằng câu truy vấn t3 trả lại kết quả là d2, d3,d4 trong tập các câu hỏi, dựa vào sự quan sát cho thấy chúng có liên quan đến khái niệm C2, không yêu cầu tài liệu đó phải chứa term t3. Câu hỏi đặt ra là làm thế nào để thu được không gian khái niệm?. Một cách khả quan để có thể tìm thấy những miêu tả chính tắc của ngôn ngữ tự nhiên, nhưng đây là một nhiệm vụ khó đạt được. Để đơn giản hơn, chúng ta có thể sử dụng những thuộc tính toán học của ma trận term – doc, ví dụ, xác định những khái n iệm bằng cách tính toán ma trận. 3.3.2 Phương pháp luận LSI Chỉ mục ngữ nghĩa tiềm ẩn (LSI) là một kỹ thuật được thiết kế để giải quyết vấn đề đồng nghĩa và các vấn đề đa nghĩa của từ ngữ. Kỹ thuật chỉ mục ngữ nghĩa tiềm ẩn giả thiết rằng có một số cấu trúc tiềm ẩn trong các mẫu có các từ đồng thời Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 68 - xuất hiện, thông qua các tập và các phép thử tài liệu để mô hình hóa những phần phụ thuộc giữa các từ và tài liệu. LSI dùng kỹ thuật tách các giá trị đơn (SVD- Singular Value Decomposition) để giảm bớt kích thước ma trận term - doc, không gian r chiều xuống một không gian s chiều, s<<r, không gian mới này được gọi là không gian khái niệm. Tất cả các thuật ngữ M và các tài liệu N có thể được thể hiện dưới dạng các vector trong không gian s chiều. Do vậy, các từ không còn độc lập nhau, và những từ đồng nghĩa sẽ tương ứng cùng kích thước hoặc có cùng độ tương đồng trong không gian này. Các tài liệu với những mẫu từ tương tự sẽ gần nhau dù chúng không chia sẻ những từ chung, điều này cho thấy rằng kỹ thuật chỉ mục ngữ nghĩa tiềm ẩn có thể phát hiện ra những mối quan hệ ngữ nghĩa học tiềm ẩn giữa những tài liệu. Ví dụ, chỉ mục ngữ nghĩa tiềm ẩn sẽ thấy được “laptop” và “portable” xuất hiện nhiều trong cùng ngữ cảnh và có vectơ tương tự. Xét ma trận term – doc - Gọi A là ma trận term-doc với M cột (Terms) và N hàng (Docs). - Các phần tử của ma trận là trọng số w i,j được tính từ lược đồ tf-idf. Hình 3.2. Mô hình tính toán và xếp thứ hạng cho các tài liệu Hình 3.2 minh hoạ ma trận term –doc A có thể được dùng để tính toán thứ hạng của các tài liệu đối với câu truy vấn q như thế nào. At • q query•doc1 query•doc2 ... query•doc6 At t q doc1 doc2 doc3 doc4 doc5 doc6 N t Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 69 - Kỹ thuật LSI sử dụng kỹ thuật SVD bằng cách trong ma trận S chỉ lựa chọn những giá trị đơn lớn nhất, giữ lại những cột tương ứng U và VT. Ma trận kết quả được gọi là As và được cho bởi: - As = Us x Ss x VsT trong đó s, s < r là kích thước của không gian khái niệm. - Tham số s cần phải: o Đủ lớn để phù hợp với đặc trưng của dữ liệu; o Đủ nhỏ để lọc ra những chi tiết không liên quan. Hình 3.3. Minh hoạ kỹ thuật Chỉ số hoá ngữ nghĩa tiềm ẩn (LSI) Trong trường hợp tìm kiếm tài liệu văn bản, hạng r của ma trận A bằng tổng khái niệm. U được xem như ma trận tương tự tài liệu – khái niệm, V là ma trận tương tự thuật ngữ - khái niệm. Thí dụ, u2,3 = 0.6 có nghĩa là khái niệm 3 có trọng số 0.6 trong tài liệu 2 và v1,2 = 0.4 có nghĩa rằng độ tương đồng giữa thuật ngữ 1 và khái niệm 2 là 0.4. Trên cơ sở SVD, chúng ta lưu trữ các ma trận U, S và V thay cho A, làm giảm đáng kể vùng nhớ cần lưu trữ. Thí dụ, giả sử M=1.000.000, N=10.000 và r=500. Tổng số không gian lưu trữ đòi hỏi sẽ là 1.000.000x500+500x500+10.000x500=505.25 MB. Giá trị này nhỏ hơn nhiều so với 10 GB để lưu trữ A. N M = MxN Mxs sxN sxs A U S VT Document vectors Term vectors N s Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 70 - Trong khi tìm kiếm , độ tương đồng giữa tài liệu và câu truy vấn được tính như sau: vector tìm kiếm q trong không gian thuật ngữ được chuyển sang vector qc trong không gian khái niệm bằng cách nhân nó với VT như sau: qc = VT x q Độ tương đồng giữa câu truy vấn với từng tài l iệu được tính bằng tích vô hướng hay hệ số cosin giữa qc và mỗi hàng của U. Do vậy, với việc sử dụng LSI, chúng ta sẽ làm việc với vector s chiều thay cho vector r chiều khi tính độ tương đồng. Vì s nhỏ hơn r nhiều lần, cho nên tính toán sử dụng LSI sẽ nhanh hơn nhiều lần so với phương pháp trực tiếp. * Các bước sắp xếp tài liệu sử dụng kỹ thuật LSI: Bước1: Đánh trọng số thuật ngữ và xây dựng ma trận term-doc A và ma trận truy vấn Q; Bước 2: Tách ma trận A thành tích của các ma trận và tìm các ma trận U, S, V, trong đó: A = USVT Bước 3: Thực hiện giảm chiều ma trận bằng cách tạo một ma trận vuông Ss có chiều là s x s từ ma trận S. Tương tự như vậy cho ma trận Vs có chiều là s x N và ma trận Us có chiều là M x s tương ứng Bước 4: Tìm các toạ độ vector tài liệu mới trong không gian giảm chiều này; Bước 5: Tìm các tọa độ véc tơ truy vấn mới trong không gian giảm chiều: q=qTUsSs-1 Bước 6: Sắp xếp các tài liệu theo thứ tự giảm dần của giá trị tương đồng cosin giữa câu truy vấn và tài liệu. Công thức tính toán để tính các giá trị tương đồng cosin trong mô hình không gian vector cơ sở. Thực chất là tính tích điểm giữa các toạ độ vector câu truy vấn và tài liệu chia cho tích của độ dài vector truy vấn và vector tài liệu. Cosθdi = S(q,d)= dq dq * Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 71 - Ví dụ: cho 3 tài liệu sau: d1: Shipment of gold damaged in a fire. d2: Delivery of silver arrived in a silver truck. d3: Shipment of gold arrived in a truck. Sử dụng kỹ thuật LSI để sắp xếp các tài liệu này cho truy vấn “gold silver truck”. Bước1: Đánh trọng số thuật ngữ và xây dựng ma trận term-doc A và ma trận truy vấn: Terms a arrived damaged delivery fire gold in of shipment silver truck d1 d2 d3                                   = 110 020 101 111 111 101 001 010 001 110 111 A q                                   = 1 1 0 0 0 1 0 0 0 0 0 q Bước 2: Tách ma trận A thành tích của các ma trận và tìm các ma trận U, S, V, trong đó: A = USVT Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 72 -                                   −− −−− −− −− −− − −− −−− −− −− −− = 4078.02001.02995.0 4013.06093.03151.0 1547.03794.02626.0 0460.00748.04201.0 0460.00748.04201.0 1547.03794.02626.0 4538.02749.01206.0 2006.03046.01576.0 4538.02749.01206.0 4078.02001.02995.0 0460.00748.04201.0 U           = 2737.10000.00000.0 0000.03616.20000.0 0000.00000.00989.4 S           − −−− −− = 7750.02469.05817.0 2556.07194.06458.0 5780.06492.04945.0 V           −− − −−− = 7750.02556.05780.0 2469.07194.06492.0 5817.06458.04945.0 TV Bước 3: Thực hiện giảm chiều vector bằng cách giữ lại các cột đầu tiên của U và V và các cột và hàng đầu tiên của S.                                   −− −− −− − − − − −− − −− − =≈ 2001.02995.0 6093.03151.0 3794.02626.0 0748.04201.0 0748.04201.0 3794.02626.0 2749.01206.0 3046.01576.0 2749.01206.0 2001.02995.0 0748.04201.0 sUU       =≈ 3616.20000.0 0000.00989.4 sSS           − −− − =≈ 2469.05817.0 7194.06458.0 6492.04945.0 sVV       − −−− =≈ 2469.07194.06492.0 5817.06458.04945.0T s T VV Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 73 - Bước 4: Tìm các toạ độ vector tài liệu mới trong không gian 2 chiều rút gọn này. Các hàng của V giữ các giá trị vector đặc trưng. Đây là các tọa độ của các vectors tài liệu riêng, vì vậy d1(-0.4945, 0.6492) d2(-0.6458, -0.7194) d3(-0.5817, 0.2469) Bước 5: Tìm các tọa độ véc tơ truy vấn mới trong không gian 2 chiều rút gọn q=qTUsSs-1 Lưu ý: Đây là các toạ độ mới của vector truy vấn trong không gian hai chiều. Chú ý xem ma trận này và ma trận truy vấn q ban đầu đã cho ở Bước 1 khác nhau như thế nào. q=qTUsSs-1 q= [ ]11000100000                                   −− −− − − − − −− −− − −− − 2001.02995.0 6093.03151.0 3794.02626.0 0748.04201.0 0748.04201.0 3794.02626.0 274901206.0 3046.01576.0 2749.01206.0 2001.02995.0 0748.04201.0           3616.2 10000.0 0000.0 0989.4 1 q = [ ]1821.02140.0 −− Bước 6: Sắp xếp các tài liệu theo thứ tự giảm dần của giá trị tương đồng cosin giữa câu truy vấn và tài liệu. S(q,d)= dq dq * Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 74 - S(q,d1)= 0541.0 )6492.0()4945.0()1821.0()2140.0( )6492.0)(1821.0()4945.0)(2140.0( 2222 −= +−−+− −+−− S(q,d2)= 9910.0 )7194.0()6458.0()1821.0()2140.0( )7194.0)(1821.0()6458.0)(2140.0( 2222 = −+−−+− −+−− S(q,d3)= 4478.0 )2469.0()5817.0()1821.0()2140.0( )2469.0)(1821.0()5817.0)(2140.0( 2222 = +−−+− −+−− Sắp xếp các tài liệu theo thứ tự giảm dần của giá trị tương đồng: d2>d3>d1 Chúng ta có thể thấy rằng tài liệu d 2 có giá trị tương đồng cao hơn d3 và d1. Vector của nó gần với vector truy vấn hơn các vector khác. * Kỹ thuật tách giá trị đơn (SVD): Ý tưởng của kỹ thuật tách giá trị đơn (SVD) là tách các đặc trưng chủ yếu của ma trận term-doc AT và xấp xỉ nó bởi các ma trận nhỏ hơn. Định lý SVD được phát biểu như sau: Ma trận bất kỳ A với kích thước MxN số thực có thể biểu diễn như sau: A = U * S * VT Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 75 - trong đó, U là ma trận trực giao cột M * r với r là hạng (rank) của ma trận A, S là ma trận đường chéo và V là ma trận trực giao cột N * r. Ma trận trực giao cột U có nghĩa là UT * U = I, I là ma trận đồng nhất. Nếu S không tăng (các phần tử được s ắp xếp theo thứ tự giảm dần) thì phân tách trên đây là duy nhất. Như vậy, kỹ thuật SVD tách một ma trận thành tích của 3 ma trận. Việc tách có thể có độ phức tạp tính toán là O(n3), độ phức tạp này là đáng kể, nó tạo ra sự ước tính gần đúng. Hình 3.4. Mô hình minh hoạ tách giá trị đơn (SVD) * Các bước tính SVD đầy đủ cho một ma trận A: Bước 1: Tính hoán vị của A: AT và ATA. Bước 2: Xác định các giá trị đặc trưng của ATA và sắp xếp theo thứ tự giảm dần. Bước 3: Xây dựng ma trận đường chéo S bằng cách đặt các giá trị đơn theo thứ tự giảm dần dọc theo đường chéo của nó. Tính nghịch đảo S-1. Bước 4: Sử dụng thứ tự các giá trị đặc trưng ở bước 2 và tính các vector đặc trưng của ATA. Đặt các giá trị đặc trưng đó dọc theo cột của V và tính hoán vị VT. Bước 5: Tính U với U=AVS -1. Để hoàn thành việc chứng minh, tính SVD đầy đủ sử dụng công thức A=USVT . Documents Terms = MxN M x r r x N r x r A U S V T N r r r Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 76 - Ví dụ: Tính SVD đầy đủ cho ma trận sau đây:       − = 53 04 A Bước 1: Tính hoán vị của A: AT và ATA Ma trận hoán vị       − = 50 34TA        − = 50 34 AAT       −53 04       − − = 2515 1525 Bước 2: Xác định các giá trị đặc trưng của ATA và sắp xếp theo thứ tự giảm dần. Căn bậc hai lúc này để tính giá trị đơn của A       −− −− =− c c clAAT 2515 1525 | ATA – cl | = (25-c)(25-c) – (-15)(-15) = 0 phương trình đặc trưng c2 – 50c+400=0 Phương trình bậc 2 cho 2 giá trị Theo thứ tự giảm dần, có | 40 | > | 10 | Các giá trị đặc trưng c1 = 40; c2 = 10 Các giá trị đơn s1= 3245.640 = > s2 = 1622.310 = Bước 3: Xây dựng ma trận đường chéo S bằng cách đặt các giá trị đơn theo thứ tự giảm dần dọc theo đường chéo của nó. Tính nghịch đảo S-1       = 1622.30 03245.6 S       =− 3162.00 01581.01S Bước 4: Sử dụng thứ tự các giá trị đặc trưng từ bước 2 và tính các vector đặc trưng của ATA. Đặt các giá trị đặc trưng đó dọc theo cột của V và tính hoán vị VT Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 77 - Với c1=40 Với c2=10       −− −− =      −− −− =− 1515 1515 402515 154025 clAAT       −− −− =      −− −− =− 1515 1515 102515 151025 clAAT (ATA – cl) x1 = 0 (ATA – cl) x2 = 0       =            −− −− 0 0 1515 1515 2 1 x x       =            − − 0 0 1515 1515 2 1 x x -15x1 + -15x2 = 0 -15x1 + -15x2 = 0 -15x1 + -15x2 = 0 15x1 + 15x2 = 0 Giải thích cho x2 cho bởi công thức Giải thích cho x2 cho bởi công thức khác: x2=x1 khác: x2=x1       − =      = 1 1 2 1 1 x x x x x       =      = 1 1 2 1 2 x x x x x Chia bởi chiều dài của nó, 21 2 2 2 1 xxxL =+= 212221 xxxL =+=       − =             −=     − = 7071.0 7071.0 2 1 2 1 / / 1 1 1 Lx Lx x       =             =      = 7071.0 7071.0 2 1 2 1 / / 1 1 1 Lx Lx x [ ]       − == 7071.07071.0 7071.07071.0 21 xxV       − = 7071.07071.0 7071.07071.0TV Bước 5: Tính U với U=AVS-1. Để hoàn thành việc chứng minh, tính SVD đầy đủ sử dụng công thức A=USVT             −     − == − 3162.00 01581.0 7071.07071.0 7071.07071.0 53 041AVSU Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 78 -       −     − == − 2236.01118.0 2236.01118.0 53 041AVSU       − == − 4472.08944.0 8944.04472.01AVSU       −             − == 7071.07071.0 7071.07071.0 1622.30 03245.6 4472.08944.0 8944.04472.0 SVTUA       −       − == 2360.22360.2 4721.44721.4 4472.08944.0 8944.04472.0 SVTUA       − ≈      − == 523 04 9997.49999.2 09998.3 SVTUA Tính trực giao của các ma trận V và U có được bằng cách xem xét các vector đặc trưng của chúng. Điều này có thể được chứng minh bởi các tích điểm giữa các vector cột. Tất cả các tích điểm đều được cho = 0. Ngoài ra, chúng ta có thể vẽ và thấy được tất cả các trực giao. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 79 - CHƯƠNG 4: PHÁT TRIỂN CHƯƠNG TRÌNH THỬ NGHIỆM 4.1 Giới thiệu bài toán Chương trình xây dựng nhằm giải quyết bài toán có đầu vào và đầu ra như sau: Input: tập gồm rất nhiều dữ liệu văn bản được lưu trữ trong máy tính dưới dạng không nén. Output: Danh sách các tệp văn bản chứa từ hay cụm từ trong câu truy vấn. Với đầu vào và đầu ra của bài toán như trên thì chương trình phải đáp ứng các yêu cầu sau: • Chương trình cho phép thu thập và tạo chỉ mục tài liệu; • Cho phép cập nhật lại chỉ mục mỗi khi có tài liệu mới được đưa vào hệ thống; • Cho phép người dùng nhập vào câu truy vấn, sau đó thực hiện tìm kiếm các tài liệu liên quan đến câu truy vấn; • Sắp xếp các tài liệu theo thứ tự giảm dần về độ tương quan của tài liệu và câu truy vấn, sau đó hiển thị kết quả cho người dùng. 4.2 Chức năng chương trình Chương trình được xây dựng với các chức năng chính sau: - Tập hợp tài liệu - Tách từ từ các tài liệu - Tính trọng số của các từ ứng với mỗi tài liệu - Chọn lọc các từ có giá trị phân biệt cao làm chỉ mục - Lập chỉ mục cho các từ tạo nên tài liệu - Cập nhật lại chỉ mục khi thêm tài liệu mới - Hiển thị kết quả tìm kiếm cho người dùng. 4.3 Quy trình phát triển ứng dụng Để xây dựng một chương trình đáp ứng các chức năng trên, cần thực hiện các bước sau đây: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 80 - 4.3.1 Xây dựng ma trận Term – Doc Xây dựng ma trận Term – Doc A có kích thước MxN (M thuật ngữ, N tài liệu) bao gồm các tần số tfij của thuật ngữ i trong tài liệu j. Ma trận này là ma trận chỉ chứa những thuật ngữ xuất hiện tập trung trong một số tài liệu. 4.3.2 Lập chỉ mục tài liệu Mục tiêu của làm chỉ mục là tìm ra các thuật ngữ tốt nhất để đại diện tài liệu sao cho các tài liệu được truy tìm chính xác trong tiến trình truy vấn. Tiến trình chỉ mục tự động bao gồm các bước sau: • Tách các từ từ các tài liệu; • Loại bỏ từ dừng; • Nhận biết các từ đồng nghĩa. Mọi thuật ngữ có ý nghĩa tương tự sẽ thay thế bằng từ chung; • Tính trọng số các thuật ngữ trong tài liệu bằng công thức: Wij = tfij * log (N/dfj); • Tạo tệp mục lục trên cơ sở các thuật ngữ và trọng số của thuật ngữ nói trên. 4.3.3 Xây dựng ma trận trọng số Ma trận trọng số được xây dựng bằng cách tính trọng số của các từ ứng với mỗi tài liệu. Trọng số của một thuật ngữ phản ánh tầm quan trọng của thuật ngữ đó trong tài liệu. Khi gán trọng số thuật ngữ, cần phải quan tâm đến cả hai: tần số thuật ngữ (tfij) và tần số tài liệu (dfj). Công thức chung để tính trọng số thuật ngữ là: Wij = tfij * log (N/dfj) trong đó, Wij là trọng số của thuật ngữ j trong tài liệu i, tfij là tần số của thuật ngữ j trong tài liệu i, N là tổng số tài liệu trong tập tài liệu, dfj là tần số tài liệu chứa thuật ngữ j. Trọng số trên đây tỷ lệ với tần số thuật ngữ và tỷ lệ nghịch với tần số tài liệu, công thức này thường được gọi là tf.idf. [idf=log(N/dfi)]. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 81 - 4.3.4 Tìm kiếm theo mô hình vector Việc tìm kiếm trong mô hình không gian vector được thực hiện dựa trên cơ sở tính tương đồng giữa câu truy vấn Qj và các tài liệu Di. Độ tương đồng giữa tài liệu Di và câu truy vấn Qj được tính như sau: ∑ = = N k jkikji QTQDS 1 .),( Để bù vào độ chênh lệch giữa kích thước tài liệu và kích thước câu truy vấn, tính tương đồng nói trên có thể chuẩn hóa với θ là góc của hai vector (gọi là khoảng cách cosin) và được tính theo công thức: ∑∑ ∑ == ==== N k jk N k ik N k jkik ji ji ji QT QT QD QD QDS 1 2 1 2 1 . . |||| . cos),( θ Đây là hệ số cosine quen thuộc giữa vector Di và Qj. Khi tìm kiếm , danh sách trả về được sắp xếp theo thứ tự giảm dần của độ tương đồng. 4.3.5 Phương pháp LSI Bước1: Đánh trọng số thuật ngữ và xây dựng ma trận term-doc A và ma trận truy vấn Q; Bước 2: Tách ma trận A thành tích của các ma trận và tìm các ma trận U, S, V, trong đó: A = USVT Bước 3: Thực hiện giảm chiều ma trận bằng cách tạo một ma trận vuông Ss có chiều là s x s từ ma trận S. Tương tự như vậy cho ma trận Vs có chiều là s x N và ma trận Us có chiều là M x s tương ứng Bước 4: Tìm các toạ độ vector tài liệu mới trong không gian giảm chiều này; Bước 5: Tìm các tọa độ véc tơ truy vấn mới trong không gian giảm chiều: q=qTUsSs-1 Bước 6: Sắp xếp các tài liệu theo thứ tự giảm dần của giá trị tương đồng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 82 - cosin giữa câu truy vấn và tài liệu. Công thức tính toán để tính các giá trị tương đồng cosin trong mô hình không gian vector cơ sở. Thực chất là tính tích điểm giữa các toạ độ vector câu truy vấn và tài liệu chia cho tích của độ dài vector truy vấn và vector tài liệu. Cosθdi = S(q,d)= dq dq * 4.2 Cài đặt thử nghiệm Chương trình được cài đặt trên nền C#. Chương trình gồm 2 phần: phần lập chỉ mục và phần tìm kiếm. Phần tìm kiếm được chia ra làm 2 modul: tìm kiếm theo mô hình vector và tìm kiếm theo kỹ thuật LSI. 4.2.1 Giao diện màn hình lập chỉ mục Hình 4.1: Giao diện màn hình lập chỉ mục Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 83 - 4.2.2 Giao diện màn hình cập nhập chỉ mục Hình 4.2: Giao diện màn hình cập nhập chỉ mục 4.2.2 Tìm kiếm tài liệu theo mô hình vector Giao diện màn hình tìm kiếm theo mô hình vector và kết quả tìm kiếm: Hình 4.3. Giao diện tìm kiếm theo mô hình vector Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 84 - KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 1. KẾT LUẬN Kỹ thuật tìm kiếm thông tin trong hệ thống cơ sở dữ liệu đa phương tiện đã và đang là một vấn đề mang tính thời sự của Công nghệ thông tin. Bản luận văn này đã đề cập được một số vấn đề mang tính chất cơ sở của CSDL đa phương tiện và một số kỹ thuật tìm kiếm văn bản theo nội dung trong CSDL đa phương tiện như mô hình Bool cơ sở, mô hình không gian vector, và một số kỹ thuật nâng cao tìm kiếm như: lọc bằng phân lớp, phương pháp tính không đều tam giác, kỹ thuật phân cụm và đặc biệt đi sâu vào tìm hiểu kỹ thuật chỉ mục ngữ nghĩa tiềm ẩn (LSI - Latent Semantic Indexing). Bản luận văn cũng đã xây dựng chương trình thử nghiệm, demo chức năng lập chỉ mục và một số kỹ thuật tìm kiếm văn bản đơn giản như mô hình không gian vector. Đây cũng là cơ sở cho việc tiếp tục xây dựng và đánh giá tính hiệu quả của các kỹ thuật nâng cao tìm kiếm sau này. Do sự eo hẹp về thời gian cũng như hạn chế về tài liệu và trình độ lập trình còn yếu kém nên bản luận văn chưa thể đi sâu vào việc xây dựng và cài đặt một chương trình thử nghiệm áp dụng kỹ thuật nâng cao trong tìm kiếm văn bản theo nội dung như mong muốn. 2. HƯỚNG PHÁT TRIỂN Đây là một đề tài có tính thực tế cao. Với nhiệm vụ là nghiên cứu, luận văn đã đáp ứng được một số yêu cầu cơ bản đặt ra.Tuy nhiên để áp dụng kỹ thuật nâng cao tìm kiếm vào một chương trình ứng dụng cụ thể cho người sử dụng thì đòi hỏi phải có thêm thời gian nghiên cứu không chỉ với các kỹ thuật tìm kiếm mà còn một số kỹ thuật khác liên quan đến việc truy tìm sao cho đạt hiệu quả tốt nhất. Do đó hướng phát triển của luận văn như sau:  Thêm chức năng tự thu thập tài liệu định kì và tự động cập nhập chỉ mục;  Cài đặt chương trình tìm kiếm văn bản sử dụng kỹ thuật nâng cao; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 85 -  Phát triển ứng dụng có áp dụng kỹ thuật nâng cao tìm kiếm để cung cấp một bộ máy tìm kiếm hiệu quả cho người sử dụng (cụ thể là áp dụng vào hệ thống thư viện số). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 86 - TÀI LIỆU THAM KHẢO Tiếng Việt [1] Đặng Văn Đức (2004/2005), “Multimedia Database Management System” Chương 1,Chương 4, Chương 9. [2] Đặng Văn Đức (2007), “Nâng cao hiệu năng MMDMS (Multimedia Database Management System)”, Bài 8. Tiếng Anh [1] Guojun Lu, “Multimedia Database Management Systems”, Artech House, Boston, London, 1999. [2] Subrahmanian V.S., “Principles of Multimedia Database Systems”, Morgan Kaufmann Publishers, Inc., California, 1998. [3] David Hand, Heikki Mannila, Padhraic Smyth, Principles of Data Mining, A Bradford Book The MIT Press Cambridge, Massachusetts LondonEngland, 2001. [4] Xu, Feilong, Latent Semantic Indexing. [5] Witten I.H, Moffat A., Bell C.T., “Managing Gigabytes, Compressing and Indexing Documents and Images”, Second Edition, Morrgan Kaufman Publishers, 1999. [6] Theory of Information Retrieval, Florida State University LIS-5263 (Fall, 2003): “Vector Model Information Retrieval”, Written by Rich Ackerman, September 25. 2003. [7] Thomas K Lundauer,Peter W. Foltz,Darrel Laham, “Introduction to Latent Semantic Analysis”. [8] Karl Aberer(2003/4), EPFL-SSC, “Latent Semantic Indexing”, Tr 36-67. [9] Deerwater, Dumais, Furnas, Landauer, Harshman, “Latent Semantic Indexing” Website [1] Từ điển bách khoa toàn thư: [2] Trang [3] Trang mã nguồn mở: ._.