Luận văn 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

Luận văn 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 1 - LỜI CẢM ƠN Em xin gửi lời cảm ơn chân thành nhất đến PGS.TS Đặng Văn Đức, người đã tận tình hướng dẫn, giúp đỡ em trong suốt thời gian thực hiện luận văn này. Con cảm ơn Cha, Mẹ và gia đình, những người đã dạy dỗ, khuyến khích, động viên con trong những lúc khó khăn, tạo mọi điều kiện cho chúng con nghiên cứu học tập. Em cảm ơn các thầy, cô trong Viện Công Nghệ Thông Tin Hà Nội cùng các thầy cô trong Khoa Công nghệ thông 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ựng 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ính tổng, tính trung bình, phép chiếu…) Lưu trữ Các văn bản ngôn ngữ tự nhiên. Các phần tử dữ liệu ở dạng bảng. Các sự kiện rõ ràng và các kiến thức tổng quát. Xử lý Các câu truy vấn không chính xác. Các câu truy vấn có cấu trúc. Các câu truy vấn không giới hạn. 2.1.5 Các hệ tìm kiếm văn bản thường được sử dụng hiện nay GoogleDesktop: Google desktop search giúp cho chúng ta có thể tìm kiếm một cách dễ dàng trong máy tính của mình giống như việc tìm kiếm trên web của google. Google Desktop là một ứng dụng cung cấp cho chúng ta tìm kiếm một văn bản với từ khóa đầy đủ trong mail, các file, âm nhạc, ảnh, chat, Gmail, và các trang web nằm trong máy mình. Bằng việc làm cho có thể tìm kiếm được trên máy tính của mình, Desktop đặt những thông tin của người dùng vào trong tầm kiểm soát và rất linh hoạt trong việc tổ chức file mail và bookmark. Google Desktop không chỉ giúp chúng ta tìm kiếm trong máy mà còn có thể giúp chúng ta lấy thông tin trên m ạng và chúng được bố trí trong gadgets và sidebar. Chúng ta có thể đặt Google Gadgets ở bất cứ chỗ nào trong máy tính , nó sẽ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 35 - hiển thị thông tin về mail, thời tiết, ảnh, tin tức và nhiều thứ khác. Sidebar là vertical bar nằm trên máy có tác dụng tổ chức lại các Gadgets. DTSearch: DTSearch là một hệ tìm kiếm thực hiện theo mô hình boolean. Nó lập chỉ mục khá nhanh và có nhiều lựa chọn thích hợp cho người sử dụng. Ngoài việc cung cấp giao diện tìm kiếm trực tiếp và lập chỉ mục thì DTSearch còn cung cấp thư viện dll dùng cho lập trình viên. Thư viện dll này có khả năng lập chỉ mục, thực hiện tìm kiếm theo mô hình boolean. Có thể nói DTSearch là điển hình tìm kiếm văn bản theo mô hình boolean khá tốt hiện nay. Hệ tìm kiếm văn bản Lucene: Hệ tìm kiếm văn bản Lucene là hệ tìm kiếm mã nguồn mở . Hệ thống được phát triển cả trên nền .Net và cả trên ngôn ngữ Java. Hệ thống hiện cũng được khá nhiều lập trình viên phát triển 2.2 Một số kỹ thuật tìm kiếm văn bản theo nội dung 2.2.1 Chỉ mục tự động văn bản và mô hình tìm kiếm Bool 2.2.1.1. Mô hình tìm kiếm Bool cơ sở Mục tiêu của hệ thống IR là tìm kiếm các mục thích hợp trong CSDL tài liệu để đáp ứng các câu truy vấn người sử dụng. Phần lớn các hệ thống IR thương mại hiện nay có thể phân lớp như hệ thống IR Bool hay hệ thống tìm kiếm theo mẫu văn bản (text-pattern). Các câu truy vấn trong tìm kiếm mẫu văn bản là các xâu hay biểu thức thông thường. Trong khi tìm kiếm, mọi tài liệu được tìm kiếm và cái nào chứa xâu truy vấn thì được lấy ra. Các hệ thống “mẫu văn bản” là hình thức chung nhất cho việc tìm kiếm trong CSDL hay tập hợp tài liệu nhỏ. Một thí dụ quen thuộc của tìm kiếm mẫu văn bản là họ công cụ grep trong môi trường Unix. Mô hình truy vấn Bool trên cơ sở lý thuyết tập hợp và đại số bool: Tài liệu là tập các thuật ngữ và truy vấn là biểu thức bool trên các thuật ngữ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 36 - Trong hệ thống tìm kiếm Bool, tài liệu được chỉ mục bởi tập các từ khóa. Các câu truy vấn được biểu diễn bởi tập từ khóa kết nối với tập phép toán Bool (để thể hiện quan hệ giữa các thuật ngữ). Ba loại toán tử hay được sử dụng là OR, AND và NOT. Quy tắc tìm kiếm của nó như sau: • Toán tử OR: Xem xét hai thuật ngữ đồng nghĩa. Thí dụ, cho trước câu truy vấn (term1 OR term2) thì hiện diện của một trong hai thuật ngữ trong tài liệu đủ để đáp ứng tìm kiếm tài liệu này. • Toán tử AND: Tổ hợp các thuật ngữ (hay từ khóa) vào một câu truy vấn. Vậy, truy vấn (term1 AND term2) chỉ ra cả hai thuật ngữ phải hiện diện trong tài liệu để cho kết quả là tìm thấy. • Toán tử NOT: Là hạn chế hay thuật ngữ hẹp, thông thường nó được sử dụng với toán tử AND. Câu truy vấn (term1 AND NOT term2) dẫn tới tìm kiếm tài liệu có term1 nhưng không có term2. Mô hình tìm kiếm Boolean khá đơn giản. Câu truy vấn đưa vào phải ở dạng biểu thức Boolean. Nghĩa là phải thỏa mãn hai tiêu chí: • Ngữ nghĩa rõ ràng; • Hình thức ngắn gọn. Do các từ hoặc xuất hiện hoặc là không xuất hiện, nên trọng số wij Є {0,1} Giả sử đưa vào một câu truy vấn dạng biểu thức Boolean như sau: t1 and t2. Sau khi tìm kiếm ta xác định được các tài liệu liên quan đến t1 là { d1, d3, d5} và các tài liệu liên quan đến t2 là {d3, d5, d7}. Như vậy với phép and, các tài liệu thỏa yêu cầu của người dùng là {d3, d5}. Phương pháp này có một số khuyết điểm như sau: • Các tài liệu trả về không được sắp xếp (ranking); • Câu truy vấn tìm kiếm đòi hỏi phải đúng định dạng của biểu thức Boolean gây khó khăn cho người dùng; • Kết quả trả về có thể là quá ít hoặc quá nhiều tài liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 37 - 2.2.1.2 Tìm kiếm Bool mở rộng Mô hình tìm kiếm Boolean không hỗ trợ việc sắp xếp kết quả trả về bởi vì các tài liệu hoặc thỏa hoặc không thỏa yêu cầu Boolean. Tất cả các tài liệu thỏa mãn đều được trả về, nhưng không có sự ước lượng nào được tính toán cho sự liên quan của chúng đối với câu truy vấn. Mô hình tìm kiếm Boolean mở rộng ra đời nhằm hỗ trợ việc sắp xếp (ranking) kết quả trả về dựa trên ý tưởng cơ bản là đánh trọng số cho mỗi từ trong câu truy vấn và trong tài liệu. Giả sử một câu truy vấn yêu cầu (t1 OR t2) và một tài liệu D có chứa t1 với trọng số w1 và t2 với trọng số w2. Nếu w1 và w2 đều bằng 1 thì tài liệu nào có chứa cả hai từ này sẽ có thứ tự sắp xếp cao nhất. Tài liệu nào không chứa một trong hai từ này sẽ có thứ tự sắp xếp thấp nhất. Ý tưởng đơn giản là tính khoảng cách Eclide từ điểm (w1, w2) tới gốc: SC(Q,Di) = 2 2 1 2(w ) (w )+ Với trọng số 0.3 và 0.4, SC(Q,Di) = ( ) ( )23 4.03.0 + = 0.500 SC cao nhất nếu w1 và w2 đều bằng 1. Khi đó: SC(Q,Di) = 2 = 1.414 Để đưa SC vào khoảng [0,1], SC được tính như sau: SC(Q t1v t2, di) = ( ) ( ) 2 2 2 2 1 ww + Công thức này giả sử là câu truy vấn chỉ có toán tử OR. Đối với toán tử AND, thay vì tính khoảng cách tới gốc, ta sẽ tính khoảng cách đến điểm (1,1). Câu truy vấn nào càng gần đến điểm (1,1) thì nó càng thoả yêu cầu của toán tử AND: SC(Q t1^t2, di) = ( ) ( ) 2 11 1 2 2 2 1 ww −+−− Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 38 - Mở rộng trong việc thêm vào trọng số của câu truy vấn: Nếu câu truy vấn có trọng số là q1 và q2 thì độ tương quan sẽ được tính như sau: SC(Qq1vq2, di) = 2 2 2 1 2 2 2 2 2 1 2 1 qq wqwq + + SC(Qq1^q2, di) =         + −+− − 2 2 2 1 2 2 2 2 2 1 2 1 )1()1(1 qq wqwq Mở rộng cho số từ tuỳ ý: Để tính khoảng cách Euclide trong không gian đa chiều sử dụng tham số p. Tham số p chỉ sự biến đổi tầm quan trọng của trọng số trong việc đánh giá độ thích hợp. Độ tương quan SC tổng quát như sau: SC(D, Qqivqj ) = p p j p i p j p j p i p i qq wqwq 1         + + SC(D, Qqi^qj) = p p j p i p j p j p i p i qq wqwq 1 )1()1( 1         + −+− − Nếu p →∞ : chuyển về hệ thống Boolean thông thường (không có trọng số). Nếu p = 1 : chuyển về hệ thống không gian vector. Thêm toán tử tự động: Các chiến lược tìm kiếm không đòi hỏi người dùng nhận biết các toán tử phức tạp. Trọng số có thể được gán tự động và tài liệu được sắp xếp bằng cách chèn toán tử OR vào giữa các từ. Bất kỳ tài liệu nào có chứa ít nhất một từ trong câu truy vấn sẽ được sắp thứ tự với một số điểm lớn hơn 0. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 39 - 2.2.1.3 Các bước để xây dựng hệ thống tìm kiếm thông tin – IR Tìm kiếm thông tin (Information retrieval) 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 trích các chỉ mục từ chính nội dung của tài liệu (free text). Trong đồ án này tôi 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 được biểu diễn bằng tập các chỉ mục. a. Lập chỉ mục cho tài liệu Từ nội dung của các tài liệu riêng rẽ trong tập tài liệu hệ thống tìm kiếm thông tin có nhiệm vụ tách nội dung đó thành các từ riêng biệt và tổng hợp chúng thành một danh sách các từ riêng biệt có trong tập tài liệu. Sau khi có được tập các từ đã được trích, ta sẽ chọn các từ để làm từ chỉ mục. Tuy nhiên, không phải từ nào cũng được chọn làm từ chỉ mục. Các từ có khả năng đại diện cho tài liệu sẽ được chọn, các từ này được gọi là key word, do đó trước khi lập chỉ mục sẽ là giai đoạn tiền xử lý đối với các từ trích được để chọn ra các key word thích hợp. Ta sẽ loại bỏ danh sách các từ ít có khả năng đại diện cho nội dung văn bản dựa vào danh sách gọi là từ dừng (stop list). Đối với tiếng Anh hay tiếng Việt đều có danh sách stop list. b. Tìm kiếm Người dùng nhập câu truy vấn và yêu cầu tìm kiếm, câu truy vấn mà người dùng nhập vào cũng sẽ được xử lý, nghĩa là ta sẽ tách từ cho câu truy vấn. Phương Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 40 - pháp tách từ cho câu truy vấn cũng nên là phương pháp tách từ cho các tài liệu thu thập được để đảm bảo sự tương thích. Sau đó, hệ thống sẽ tìm kiếm trong tập tin chỉ mục để xác định các tài liệu liên quan đến câu truy vấn của người dùng. c. Sắp xếp các tài liệu trả về (Ranking) Các tài liệu sau khi đã xác định là liên quan đến câu truy vấn của người dùng sẽ được sắp xếp lại, bởi vì trong các tài liệu đó có những tài liệu liên quan đến câu truy vấn nhiều hơn. Hệ thống sẽ dựa vào một số phương pháp để xác định tài liệu nào liên quan nhiều nhất, sắp xếp lại (ranking) và trả về cho người dùng theo thứ tự ưu tiên. 2.2.1.4 Lập chỉ mục tài liệu Một trong các vấn đề cơ bản trong thiết kế hệ thống IR là quyết định sử dụng loại cấu trúc tệp nào để lưu trữ CSDL tài liệu. Cấu trúc tệp sử dụng trong các hệ thống IR bao gồm các tệp phẳng, tệp mục lục (inverted), tệp chữ ký và các tệp khác như cây PAT và đồ thị. Với quan điểm tệp phẳng, một hay nhiều tài liệu lưu trữ trong tệp, thông thường trong mã ASCII hay EBCDIC, không có chỉ mục tài liệu. Tìm kiếm tệp phẳng thông qua tìm kiếm mẫu. Trong UNIX, khi lưu trữ tập các tài liệu người ta lưu trữ mỗi tài liệu trong một tệp, trong danh mục. Các tệp này có thể tìm kiếm nhờ các công cụ tìm kiếm theo mẫu như “grep”, “awk”. Tiếp cận này không hiệu quả vì mỗi lần truy vấn thì toàn bộ tập các tài liệu phải được duyệt để tìm ra mẫu văn bản. Các tệp chữ ký (signature files): chứa các chữ ký (mẫu bit) đại diện cho tài liệu. Có nhiều cách để sinh chữ ký tài liệu. Câu truy vấn được đại diện bởi chữ ký mà nó sẽ được so sánh với chữ ký tài liệu trong khi tìm kiếm. Cách sử dụng chung nhất là tệp mục lục (inverted). Vì thời gian có hạn nên trong khuôn khổ luận văn tác giả chỉ đề cập đến cách sử dụng tệp mục lục (inverted). Nội dung như sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 41 - a. Khái quát về hệ thống lập chỉ mục Trong các hệ thống tìm kiếm thông tin văn bản ( Text Information Retrieval System), tiến trình quan trọng nhất là tiến trình phân tích nội dung văn bản để xác định tập chỉ mục biểu diễn tốt nhất nội dung của văn bản (tiến trình lập chỉ mục - indexing). Để có thể phân tích và rút trích được các chỉ mục (index term / term) tốt người ta thường ứng dụng các kết quả của lĩnh vực xử lý ngôn ngữ tự nhiên vào tiến trình này. Chỉ mục có thể là từ (word) hay là một cấu trúc phức tạp hơn như cụm danh từ (noun phrase), khái niệm (concept)... Vấn đề xác định chỉ mục cho văn bản tiếng Việt phức tạp hơn đối với ngôn ngữ châu Âu do việc xác định giới hạn của một từ (word segmentation) trong tiếng Việt không đơn giản là chỉ dựa vào các khoảng trắng giữa chúng. Hơn nữa ngữ pháp tiếng Việt vẫn còn nhiều vấn đề tranh luận giữa các nhà ngôn ngữ học nên cũng còn nhiều khó khăn trong việc tự động hóa việc phân tích tiếng Việt. Tạo chỉ mục cho tài liệu là một cách để tăng tốc độ tìm kiếm thông tin. Tuy nhiên, việc lập chỉ mục có một nhược điểm lớn, đó là khi thêm một tài liệu mới, phải cập nhật lại tập tin chỉ mục. Nhưng đối với hệ thống tìm kiếm thông tin, chỉ cần cập nhật lại tập tin chỉ mục vào một khoảng thời gian định kỳ. Do đó, chỉ mục là một công cụ rất có giá trị. Lập chỉ mục bao gồm các công việc sau: • Xác định các từ có khả năng đại diện cho nội dung của tài liệu; • Đánh trọng số cho các từ này, trọng số phản ánh tầm quan trọng của từ trong một tài liệu. b. Cấu trúc tệp mục lục Trong tệp mục lục, chỉ mục được xây dựng cho mỗi thuật ngữ để lưu trữ chỉ danh (ID) tài liệu cho toàn bộ tài liệu chứa thuật ngữ này. Đầu vào tệp mục lục thông thường chứa thuật ngữ (từ khoá) và một số ID tài liệu. Mỗi thuật ngữ và các Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 42 - ID tài liệu (mà có chứa thuật ngữ) được tổ chức thành một hàng. Thí dụ tệp mục lục như sau: Term1: Doc1, Doc3 Term2: Doc1, Doc2 Term3: Doc2, Doc3, Doc4 Term4: Doc1, Doc2, Doc3, Doc4 trong đó, Termi (i = 1,2,3,4) là số ID thuật ngữ i, Doci (i = 1, 2, 3, 4) là số ID của tài liệu i(Doci). Dòng 1 có nghĩa rằng Doc1 và Doc3 chứa Term1, các dòng khác có ý nghĩa tương tự. Việc tìm kiếm sẽ được thực hiện nhanh chóng trong các tệp mục lục. Chỉ các hàng chứa thuật ngữ tìm kiếm mới được tìm kiếm, không cần tìm mọi tài liệu trong CSDL. Tệp chỉ mục có định dạng như trên người ta gọi là Tệp chỉ mục đảo. * Phân biệt giữa tập tin nghịch đảo và tập tin trực tiếp Tập tin trực tiếp (direct file) là tập tin mà chính các mục thông tin đã cung cấp thứ tự chính của tập tin. Ngược lại, tập tin nghịch đảo (inverted file) được sắp xếp theo chủ đề, mỗi chủ đề lại bao gồm một tập các mục thông tin. Giả sử có một tập các tài liệu (Doci), mỗi tài liệu chứa danh sách các từ (termj). Nếu một từ xuất hiện trong một tài liệu, ghi số 1. Ngược lại, ghi 0. Khi đó, tập tin trực tiếp và tập tin nghịch đảo sẽ lưu trữ như Bảng 2.2 và Bảng 2.3. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 43 - Bảng 2.2: Cách tập tin nghịch đảo lưu trữ Doc Term D1 D2 D3 T1 0 1 1 T2 1 1 1 T3 0 0 1 T4 0 1 0 Bảng 2.3 Cách tập tin trực tiếp lưu trữ Term Doc T1 T2 T3 T4 D1 0 1 0 1 D2 1 1 0 1 D3 1 1 1 0 * Tại sao sử dụng tập tin nghịch đảo để lập chỉ mục? Trong hệ thống tìm kiếm thông tin, tập tin nghịch đảo có ý nghĩa rất lớn, giúp việc truy cập đến các mục thông tin được nhanh chóng. Giả sử khi người dùng nhập một câu truy vấn, hệ thống sẽ tách thành 2 từ là “Term1” và “Term2”. Dựa vào tập tin nghịch đảo, ta dễ dàng xác định được các tài liệu có liên quan đến 2 từ này để trả về cho người tìm kiếm. Tuy nhiên, khó khăn chính của tập tin nghịch đảo là khi thêm một tài liệu mới, tất cả các từ có liên quan đến tài liệu này đều phải được cập nhật lại. Ví dụ khi thêm tài liệu 4 có chứa 2 từ “Term3” và “Term4” vào tập tin nghịch đảo: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 44 - Bảng 2.4: Thêm một tài liệu mới vào tập tin nghịch đảo Doc Term D1 D2 D3 D4 T1 0 1 1 0 T2 1 1 0 0 T3 0 0 1 1 T4 0 1 0 1 Rõ ràng việc này tốn một chi phí lớn nếu tập ti n nghịch đảo rất lớn. Trong thực tế, tập tin nghịch đảo tài liệu có thể chứa hàng trăm ngàn từ. Tuy nhiên, trong các hệ thống tìm kiếm thông tin, người ta chỉ cập nhật lại tập tin tại một khoảng thời gian định kỳ. Vì vậy, tập tin nghịch đảo vẫn được sử dụng để lập chỉ mục. * Quy tắc tìm kiếm bằng mô hình Bool trên tệp mục lục Truy vấn AND: Thí dụ (Termi AND Termj). Sinh danh sách trộn hàng i với hàng j trong tệp mục lục và mọi tài liệu đều chứa Termi và Termj sẽ là kết quả tìm kiếm ở đầu ra. Thí dụ truy vấn (Term1 AND Term3) cho kết quả là Doc3. Truy vấn OR: Thí dụ (Termi OR Term j). Sinh danh sách trộn cho hàng i và j, Mọi mục trong danh sách trộn là đầu ra kết quả. Thí dụ truy vấn (Term1 OR Term2) sẽ cho kết quả là Doc1, Doc2 và Doc3. Truy vấn NOT: Thí dụ (Termi AND NOT Termj) sẽ cho kết quả là các mục xuất hiện trong hàng i nhưng không trong hàng j. Truy vấn (Term4 AND NOT Term1) cho kết quả là Doc2, Doc4. Truy vấn (Term1 AND NOT Term4) sẽ cho đầu ra là rỗng. * Mở rộng thao tác tệp mục lục Cho đến thời điểm hiện tại ta đã bỏ qua hai yếu tố quan trọng khi chỉ mục và tìm kiếm tài liệu, đó là vị trí của các thuật ngữ và ý nghĩa các thuật ngữ (trọng số thuật ngữ) trong tài liệu. Trong các truy vấn AND, mọi tài liệu chứa cả hai thuật Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 45 - ngữ được tìm thấy, không quan tâm đến vị trí của chúng trong tài liệu. Các thuật ngữ có tầm quan trọng như nhau, không quan tâm đến tần số xuất hiện trong tài liệu. Để nâng cao hiệu quả truy vấn, hai yếu tố này cần được xem xét. Các quan hệ đặc tả giữa hai hay nhiều thuật ngữ được tăng cường bằng cách bổ sung các tham số “tính gần kề” vào đặc tả truy vấn. Khi tham số gần kề được bổ sung, chủ điểm được xác định cụ thể hơn, tính phù hợp của mục truy vấn được sẽ cao hơn. Hai tham số thuộc nhóm này có thể là đặc tả “ within sentence” và “adjacency”: • (Termi within sentence Termj) có nghĩa rằng thuật ngữ i và thuật ngữ j cùng xuất hiện trong câu của tài liệu vừa tìm ra. • (Termi adjacency Termj) có nghĩa các thuật ngữ i và j xuất hiện liền kề trong các tài liệu tìm ra. Để hỗ trợ loại truy vấn này, thông tin vị trí thuật ngữ phải gộp vào tệp mục lục. Cấu trúc tổng quát của file này sẽ như sau: Termi: Record no., Paragraph no., Sentence no., Word no. Thí dụ, nếu tệp mục lục có các đầu vào sau: information: R99, 10, 8, 3; R15, 15, 3, 6; R166, 2, 3, 1 retrieval: R77, 9, 7, 2; R99, 10, 8, 4; R166, 10, 2, 5 thì kết quả truy vấn (information within sentence retrieval) là R99. Trong thí dụ trên, các thuật ngữ “information” và “retrieval” xuất hiện trong cùng câu R99 của tài liệu. Mặt khác, dù R166 đều chứa cả hai thuật ngữ này nhưng lại ở vị trí khác nhau của tài liệu, do vậy truy vấn không cho lại kết quả (không phải là “information retrieval”). Có thể hai thuật ngữ này được sử dụng trong các ngữ cảnh khác nhau. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 46 - c. Phương pháp lập chỉ mục * Xác định các từ chỉ mục Cho một tập gồm có n tài liệu. Với mỗi tài liệu, tính tần số của mỗi từ riêng biệt trong tài liệu đó. Gọi FREQik: là tần số xuất hiện của từ k trong tài liệu i. Xác định tần số của từ k trong tập tài liệu, ký hiệu là TOTFREQk bằng cách tính tổng tần số xuất hiện của k trong tất cả n tài liệu: TOTFREQk = ∑ − n i ikFREQ 1 Sắp xếp các từ giảm dần dựa vào tần số xuất hiện của nó trong tập tài liệu. Xác định giá trị ngưỡng cao và loại bỏ tất cả các từ có tần số xuất hiện lớn hơn giá trị này. Tương tự, loại bỏ các từ có tần số thấp. Nghĩa là, xác định ngưỡng thấp và loại bỏ tất cả các từ có tần số xuất hiện nhỏ hơn giá trị này. Điều này sẽ loại bỏ các từ ít xuất hiện trong tập tài liệu, nên sự có mặt của các từ này cũng không ảnh hưởng đến việc thực hiện truy vấn. Loại bỏ các từ không có giá trị. Các từ này gọi là các từ dừng (StopWords) Các từ có tần số xuất hiện trung bình còn lại sẽ được sử dụng làm từ chỉ mục. Hình 2.5 Các từ được sắp theo thứ tự Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 47 - * Các phương pháp tính trọng số của từ Trọng số của một từ phản ánh tầm quan trọng của từ đó trong tài liệu. Ý tưởng chính là một từ xuất hiện thường xuyên trong tất cả các tài liệu thì ít quan trọng hơn là từ chỉ xuất hiện tập trung trong một số tài liệu. Tính tần số tài liệu nghịch đảo: Việc sắp xếp kết quả cho lại theo thứ tự là rất quan trọng vì những mục đầu tiên là có ích nhất cho người sử dụng. Họ chỉ cần quan sát vài mục đầu tiên thay cho duyệt toàn bộ kết quả. Việc gán các thuật ngữ chỉ mục cho tài liệu và câu truy vấn là để phân biệt các tài liệu mà người sử dụng quan tâm với các tài liệu khác. Trong một tài liệu cụ thể, thuật ngữ nào xuất hiện thường xuyên hơn thì nó quan trọng hơn, nên nó có trọng số lớn hơn. Trong ngữ cảnh tập hợp toàn bộ tài liệu, nếu thuật ngữ xuất hiện hầu hết trong các tài liệu thì nó không phải là lựa chọn tốt làm thuật ngữ chỉ mục vì nó không giúp phân biệt các tài liệu người sử dụng quan tâm với tài liệu khác. Do vậy, thuật ngữ được chỉ mục tốt là thuật ngữ xuất hiện thường xuyên trong vài tài liệu nhưng không xuất hiện trong các tài liệu khác. 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 hợp, dfj là 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)] Trên cơ sở công thức Wij = tfij * log (N/dfj), nếu thuật ngữ xuất hiện trong toàn bộ tài liệu (dfj = N) thì trọng số của thuật ngữ bằng 0 (thuật ngữ không thể sử dụng làm thuật ngữ chỉ mục). Mặt khác, nếu thuật ngữ xuất hiện thường xuyên chỉ trong vài tài liệu, trọng số của thuật ngữ sẽ rất cao (thuật ngữ này làm thuật ngữ chỉ mục tốt). Ví dụ có 5 tài liệu D1 đến D5, và 1 thuật ngữ “CAR”. Hình 2.6 dưới đây minh hoạ cho mối quan hệ giữa 5 tài liệu và thuật ngữ “CAR” và chỉ có 3 tài liệu có Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 48 - chứa thuật ngữ “CAR”. Truy vấn hệ thống cho thuật ngữ này cho giá trị IDF=log(N/dfi)=log(5/3)=0.2218. 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” Khi đó ta có bảng trọng số Wij tính theo công thức tf.idf: tfi Wij=tfi*IDFi Term D1 D2 D3 D1 D2 D3 CAR 1 4 5 0.2218 0.8872 1.109 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 49 - d. Lập chỉ mục tự động cho tài liệu tiếng Anh Một quá trình đơn giản để lập chỉ mục cho tài liệu có thể được mô tả như sau: Trước hết, xác định tất cả các từ tạo thành tài liệu. Trong tiếng Anh, chỉ đơn giản là tách từ dựa vào khoảng trắng. Loại bỏ các từ có tần số xuất hiện cao. Những từ này chiếm khoảng 40-50% các từ, như đã đề cập trước đây, chúng có độ phân biệt kém do đó không thể sử dụng để đại diện cho nội dung của tài liệu. Trong tiếng Anh, các từ này có khoảng 250 từ, do đó, để đơn giản có thể lưu chúng vào từ điển, gọi là stop list. Trích dẫn các từ dừng của tiếng Anh như trong Bảng 2.5. Bảng 2.5: Danh sách từ dừng của tiếng Anh A ALTHOUGH ANYONE ABOUT ALWAYS ANYTHING ACROSS AMONG ANYWHERE AFTER AMONGST ARE AFTERWARDS AN AROUND AGAIN AND AS AGAINST ANOTHER AT ALL ANY BE ALSO ANYHOW BECOME Sau khi loại bỏ các từ có trong stop list, xác định các từ chỉ mục “tốt”. Trước hết cần loại bỏ các hậu tố để đưa về từ gốc, ví dụ các từ như: analysis, analyzing, analyzer, analyzed, analysing có thể chuyển về từ gốc là “analy.” Từ gốc sẽ có tần số xuất hiện cao hơn so với các dạng thông thường của nó. Nếu sử dụng từ gốc làm chỉ mục, ta có thể thu được nhiều tài liệu có liên quan hơn là sử dụng từ ban đầu của nó. Đối với tiếng Anh, việc loại bỏ hậu tố có thể được thực hiện dễ dàng bằng cách sử dụng danh sách các hậu tố có sẵn (Suffix List). Sau khi có được danh sách các từ gốc, sử dụng phương pháp dựa vào tần số (frequency – based) để xác định tầm quan trọng của các từ gốc này. Chúng ta có thể sử dụng một trong các phương pháp đã được đề cập ở trên như: tần số tài liệu nghịch đảo (inverse document frequency), độ tín hiệu (SIGNALk), độ phân biệt từ (DISVALUEk). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 50 - Trong hệ thống chỉ mục có trọng số, trọng số của một từ được sử dụng để xác định tầm quan trọng của từ đó. Mỗi tài liệu được biễu diễn là một vector: Di = (di1, di2, …, dit) trong đó dij là trọng số của từ j trong tài liệu Di. Giả sử có 1033 tài liệu nói về y học. Quá trình lập chỉ mục đơn giản được thực hiện như sau (trong đó chỉ loại bỏ hậu tố tận cùng là s): Hình 2.7 Quá trình chọn từ làm chỉ mục Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 51 - e. Lập chỉ mục cho tài liệu tiếng Việt Lập chỉ mục cho tài liệu tiếng Việt cũng tương tự như cho tiếng Anh. Tuy nhiên có vài điểm khác biệt sau: • Giai đoạn tách từ trong tiếng Anh chỉ đơn giản dựa vào khoảng trắng, còn tiếng Việt là ngôn ngữ đơn lập, một từ có thể có nhiều tiếng. Giả sử sau giai đoạn tách từ, ta sẽ thu được một danh sách các từ riêng biệt. • Đối với tiếng Việt, không phải qua giai đoạn loại bỏ hậu tố. • Nói chung, lập chỉ mục cho tài liệu tiếng Việt gồm các bước sau: o Xác định các từ riêng biệt trong tài liệu; o Loại bỏ các từ có tần số cao. (Trong tiếng Việt, cũng như tiếng Anh, ta có một danh sách Stop List chứa những từ không thể là nội dung của văn bản như: và, với, những, gì, sao, nào, …); o Loại bỏ các từ có trọng số thấp. • Các từ thu được sẽ được chọn làm các từ chỉ mục. 2.2.2 Mô hình tìm kiếm không gian vector 2.2.2.1 Mô hình tìm kiếm không gian vector cơ sở Khái niệm mô hình tìm kiếm Bool đơn giản và được sử dụng trong hầu hết các hệ thống thương mại. Tuy nhiên tương đối khó hình thành các câu truy vấn Bool và kết quả truy vấn rất nhậy cảm với công thức truy vấn. Trọng số thuật ngữ truy vấn thường không được sử dụng vì các câu truy vấn thường rất ngắn. Để tránh vấn đề này, các mô hình tìm kiếm khác như không gian vector, thống kê và trên cơ sở cụm (cluster) được sử dụng để thay thế. Mô hình không gian vector giả sử rằng tồn tại tập cố định các thuật ngữ chỉ mục để đại diện tài liệu và câu truy vấn. Tài liệu Di và câu truy vấn Q j được biểu diễn như hai vector: Di = [Ti1, Ti2,..., Tik, ... , TiN] Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 52 - Qj = [Qj1, Qj2,..., Qjk, ... , QjN] trong đó, Tik là trọng số của thuật ngữ k trong tài liệu i, Qjk là trọng số của thuật ngữ k trong truy vấn j, và N là tổng số thuật ngữ sử dụng trong các tài liệu và truy vấn. Các trọng số thuật ngữ Tik và Qjk có thể là nhị phân (1 hoặc 0) họăc sử dụng phương pháp đánh trọng số tf.idf hoặc các phương pháp khác. 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 và các tài liệu. Độ 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 biểu diễn như dưới đây: ∑∑ ∑ == ==== 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 xếp hạng theo thứ tự tính tương đồng giảm dần sẽ được cho lại. Thí dụ, có 4 tài liệu và truy vấn được đại diện bởi các vector sau: D1 = [0.2, 0.1, 0.4, 0.5] D2 = [0.5, 0.6, 0.3, 0] D3 = [0.4, 0.5, 0.8, 0.3] D4 = [0.1, 0, 0.7, 0.8] Q = [0.5, 0.5, 0, 0] thì tính tương đồng giữa câu truy vấn và từng tài liệu như sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 53 - S(D1, Q) = 0.31 S(D2, Q) = 0.931 S(D3, Q) = 0.66 S(D4, Q) = 0.07 Hệ thống sẽ cho lại danh sách tài liệu theo thứ tự D2, D3, D1 và D4. Hạn chế chính của mô hình không gian vector là nó coi các thuật ngữ không có quan hệ với nhau và nó chỉ làm việc tốt với tài liệu và câu truy vấn ngắn. Nếu M là tổng số tài liệu, cần O(M) thời gian so sánh trong trường hợp tồi nhất. Nếu có N thuật ngữ, cần O(N) thời gian so sánh. Vậy tổng số thời gian đòi hỏi tính toán sẽ là O(N x M). Thông thường N x M là một số rất lớn, do vậy, người ta phải phát triển các kỹ thuật khác để tìm kiếm thuật ngữ trong tập tài liệu. 2.2.2.2. Kỹ thuật phản hồi phù hợp (Relevance Feedback Technique) Các kỹ thuật áp dụng thông tin phản hồi phù hợp của người sử dụng được phát triển để nâng cao hiệu năng hệ thống. Phản hồi phù hợp lấy quyết định của người sử dụng về tính thích hợp của tài liệu và sử dụng chúng để điều chỉnh câu truy vấn hay chỉ mục tài liệu. a. Điều chỉnh câu truy vấn Điều chỉnh câu truy vấn trên cơ sở phản hồi thích hợp của người sử dụng sẽ sử dụng quy tắc sau: • Các thuật ngữ xuất hiện trong tài liệu nhận ra trước đây là thích hợp thì được bổ sung vào câu truy vấn gốc, hay làm tăng trọng số của thuật ngữ. • Các thuật ngữ xuất hiện trong các tài liệu nhận ra trước đây không thích hợp thì hủy khỏi câu truy vấn hay làm giảm trọng số của thuật ngữ. Câu truy vấn mới được thay thế lần nữa để tìm kiếm tài liệu. Các quy tắc trên đây được diễn giải như sau: ∑∑ ∈∈ + −+= lNonD i lD iii ii DDQQ ReRe )()1( βα Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 54 - trong đó, Q(i+1) là truy vấn mới, Q (i) là truy vấn hiện hành, D i là tập hợp các tài liệu tìm kiếm được từ câu truy vấn Q(i), α và β là các trọng số, tổng thứ nhất được thực hiện với tất cả tài liệu phù hợp trong D(i), và tổng thứ hai thực hiện trên tài liệu không phù hợp D(i). Thực nghiệm cho thấy rằng hiệu năng sẽ được nâng cao nhờ sử dụng kỹ thuật này. Tóm lại, nguyên tắc của tiệm cận trên là tìm ra các tài liệu tương đồng với tài liệu đã kết luận là phù hợp với câu truy vấn. Các tài liệu thích hợp với câu truy vấn phải tương tự với nhau. b. Điều chỉnh tài liệu Trong điều chỉnh câu truy vấn trên cơ sở phản hồi phù hợp (relevance) của người sử dụng, các câu truy vấn được điều chỉnh nhờ các thuật ngữ trong tài liệu phù hợp. Người sử dụng khác không có lợi từ điều chỉnh này. Trong điều chỉnh tài liệu trên cơ sở phản hồi phù hợp của người sử dụng, các thuật ngữ chỉ mục tài liệu được điều chỉnh bằng các thuật ngữ truy vấn để sự thay đổi này tác động đến người sử dụng. Sử dụng các qui tắc trên cơ sở phản hồi phù hợp của người sử dụng như sau đây để điều chỉnh tài liệu: • Thuật ngữ trong truy vấn, nhưng không trong các tài liệu mà người sử dụng kết luận là phù hợp, sẽ được bổ sung vào danh sách chỉ mục tài liệu với trọng số khởi đầu. • Các trọng số của thuật ngữ chỉ mục trong câu truy vấn và trong các tài liệu phù hợp đều được tăng lên với giá trị nhất định. • Các trọng số của các thuật ngữ chỉ mục ngoài câu truy vấn nhưng trong tài liệu liên quan được giảm đi một giá trị nhất định. Khi các truy vấn tiếp theo sau tương tự các truy vấn sử dụng để hiệu chỉnh tài liệu được đưa ra thì hiệu năng được tăng cường. Tuy nhiên tiệm cận này có thể làm giảm hiệu năng nếu các truy vấn tiếp theo khác xa với cái được sử dụng để điều chỉnh tài liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 55 - 2.2.3. Thước đo hiệu năng Giả sử trong tập tài liệu khi chúng ta tìm kiếm với câu truy vấn Q chúng ta có kết quả như sau: Pert: Tập con tài liệu đúng với câu truy vấn Q trong thực tế Retr: Tập con tài liệu mà hệ thống tìm ra Hình 2.8. Mô hình thước đo hiệu năng Để đánh giá hiệu năng của hệ tìm kiếm thông tin dựa vào 2 tiêu chuẩn sau: +Khả năng tìm thấy (Recall): [ ]1,0 P RP ∈ ∩ +Độ chính xác (Precision): [ ]1,0 R RP ∈ ∩ Cả hai tiêu chuẩn đều có giá trị trong khoảng [0,1]. Khi Recall có giá trị càng sát 1 thì khả năng tìm thấy tài liệu càng cao. Khi recall=1 thì khả năng tìm thấy hết tài liệu liên quan. Đối với Precision cũng tương tự Recall, khi Precision càng tiến sát 1 thì độ chính xác càng cao Khi Recall = Precision = 1 thì hệ thống cho kết quả tuyệt đối Để so sánh hiệu năng của hệ thống này với hệ thống khác cùng chức năng chúng ta có thể dựa vào đồ thị sau: Tập hợp tài liệu Các tài liệu phù hợp (đối với người sử dụng) Các tài liệu tìm thấy (của hệ thống) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 56 - Hình 2.9. Đồ thị so sánh hiệu năng Theo tính chất của 2 tiêu chuẩn Recall và Precision thì đồ thị của hệ thống nào càng xa gốc thì đạt hiệu năng càng cao. 2.3 Ví dụ Giả sử cho câu truy vấn “gold silver truck” và 3 tài liệu: 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" Các kết quả tính trọng số được tổng kết trong bảng 2.5: Tần số tfi Trọng số wij=tfi*IDFi Terms Q D1 D2 D3 dfi D/dfi IDFi Q D1 D2 D3 A 0 1 1 1 3 3/3=1 0 0 0 0 0 arrived 0 0 1 1 2 3/2=1.5 0.1761 0 0 0.1761 0.1761 damaged 0 1 0 0 1 3/1=3 0.4771 0 0.4771 0 0 delivery 0 0 1 0 1 3/1=3 0.4771 0 0 0.4771 0 Fire 0 1 0 0 1 3/1=3 0.4771 0 0.4771 0 0 Gold 1 1 0 1 2 3/2=1.5 0.1761 0.1761 0.1761 0 0.1761 In 0 1 1 1 3 3/3=1 0 0 0 0 0 Of 0 1 1 1 3 3/3=1 0 0 0 0 0 silver 1 0 2 0 1 3/1=3 0.4771 0.4771 0 0.9542 0 shipment 0 1 0 1 2 3/2=1.5 0.1761 0 0.1761 0 0.1761 truck 1 0 1 1 2 3/2=1.5 0.1761 0.1761 0 0.1761 0.1761 Các cột trong bảng kết quả thể hiện: (0,0) Độ chính xác Khả năng tìm thấy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 57 - • Cột 1 đến cột 5: Danh mục các thuật ngữ được xây dựng từ các tài liệu và tính tần số tfi cho câu truy vấn trong mỗi tài liệu Dj. • Cột 6 đến cột 8: Là tần số tài liệu di của từng tài liệu. Từ đó tính IDFi = log(D/dfi) và D = 3. • Cột 9 đế cột 12: Là trọng số thuật ngữ được xác định bằng cách lấy tích tfi * IDFi. Các cột này có thể được xem như là một ma trận thưa, trong đó hầu hết các mục bằng 0. Tính độ tương đồng: Để tính độ tương đồng, trước tiên tính tất cả các chiều dài vector cho mỗi tài liệu và câu truy vấn: ∴ ∑= i 2 ji,WiD 7192.05173.01761.01761.04771.04771.0 22221 ==+++=D 0955.12001.11761.09541.04771.01761.0 22222 ==+++=D 3522.01240.01761.01761.01761.01761.0 22223 ==+++=D 5382.02896.01761.04771.01761.0W 222 i 2 jQ, ==++== ∑Q Tiếp theo tính tất cả các tích điểm (bỏ qua các tích 0): ∴Q•Di=∑ i ji,jQ, WW Q•D1 = 0.1761*0.1761=0.0310 Q•D2 = 0.4771*0.9542*0.1761*0.1761=0.4862 Q•D3 = 0.1761*0.1761*0.1761*0.1761=0.0620 => Các giá trị tương đồng: ∴CosθDi = S(Q,Di) = ∑∑ ∑ i ji j jQ i jijQ WW WW 2 , 2 , ,, Cos 0801.0 7192.0*5382.0 0310.0 * 1 1 1 == • = DQ DQ Dθ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 58 - Cos 8246.0 0955.1*5382.0 4862.0 * 2 2 2 == • = DQ DQ Dθ Cos 3271.0 3522.0*5382.0 0620.0 * 3 3 3 == • = DQ DQ Dθ Cuối cùng sắp xếp thứ tự cho các tài liệu theo thứ tự giảm dần theo giá trị tương đồng: Rank 1: Doc2 = 0.8246 Rank 2: Doc 3= 0.3271 Rank 3: Doc 1= 0.0801 2.4 Kết luận Với lượng thông tin khổng lồ như hiện nay thì lựa chọn các kỹ thuật tìm kiếm thông tin sao cho vừa nhanh chóng, vừa chính xác là một điều hết sức cần thiết. Trong chương này của luận văn, tác giả đã trình bày hai kỹ thuật đơn giản, dễ hiểu nhất trong số các kỹ thuật tìm kiếm thông tin đã được nghiên cứu và phát triển. Tuy nhiên, hai kỹ thuật này chưa thực sự hiệu quả do vậy cần phải có những kỹ thuật tốt hơn, hiệu quả hơn nhằm đáp ứng nhu cầu truy vấn của người sử dụng. 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 nâng cao tìm kiếm văn bản. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 59 - CHƯƠNG 3: MỘT SỐ KỸ THUẬT NÂNG CAO HIỆU NĂNG TÌM KIẾM VĂN BẢN 3.1 Giới thiệu Trong chương 2 đã giới thiệu cách tìm kiếm các vector đặc trưng cho tài liệu văn bản. Các vector đặc trưng thông thường là đa chiều. Thí dụ, trong mô hình không gian vector, tổng số chiều đặc trưng hay vector tài liệu bằng tổng số mục (items), thường hàng trăm hay hàng ngàn, được sử dụng trong tập hợp tài liệu. Tổng số chiều phụ thuộc vào phương pháp lựa chọn. Trong khi tìm kiếm , câu truy vấn cũng được biểu diễn bởi vector đa chiều. Tìm kiếm trên cơ sở mức độ tương đồng hay khoảng cách giữa vector truy vấn và vector đặc trưng của các đối tượng lưu trữ. Khi tổng số đối tượng lưu trữ hoặc/và tổng số chiều của vector đặc trưng lớn, chúng sẽ chậm khi tìm kiếm tuyến tính mọi vector đặc trưng lưu trữ để tìm ra cái thỏa mãn tiêu trí truy vấn. Do vậy, đòi hỏi có các kỹ thuật và cấu trúc dữ liệu để tổ chức các vector đặc trưng và quản lý tiến trình tìm kiếm sao cho các vector đặc trưng liên quan đến truy vấn được định vị nhanh. Mục tiêu chính của các kỹ thuật để nâng cao hiệu năng tìm kiếm tương tự là chia không gian đặc trưng đa chiều thành nhiều vùng nhỏ sao cho việc tìm kiếm chỉ được thực hiện trong một hay trong một vài vùng nhỏ. Các kỹ thuật và cấu trúc dữ liệu khác nhau thì khác nhau về cách phân chia và lựa chọn vùng nhỏ cho mỗi truy vấn. Có ba loại truy vấn thường được sử dụng: truy vấn điểm, truy vấn dải (range) và truy vấn k láng giềng gần nhất. Trong truy vấn điểm : Câu truy vấn của người sử dụng được biểu diễn bởi vector, các đối tượng có vector đặc trưng đối sánh chính xác với vector truy vấn thì được xem như kết quả ở đầu ra. Trong truy vấn dải: Câu truy vấn được biểu diễn bởi vector đặc trưng và dải khoảng cách. Mọi đối tượng mà khoảng cách từ chúng đến vector truy vấn nhỏ hơn hay bằng dải khoảng cách cho trước thì là kết quả. Tồn tại rất nhiều thước đo Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - 60 - khoảng cách khác nhau, trong đó chuẩn L1 và L2 (khoảng cách Euclid) là hay được sử dụng nhất. Loại khác của truy vấn dải được đặc tả bởi dải giá trị cho mỗi chiều của vector đặc trưng. Trong truy vấn k láng giềng gần nhất , câu truy vấn của người sử dụng được đặc tả bởi một vector và một số nguyên k. Hệ thống sẽ tìm ra k đối tượng mà nó thỏa mãn điều kiện là những khoảng cách từ chúng đến vector truy vấn là nhỏ nhất. Cần có kỹ thuật và cấu trúc dữ liệu hữu hiệu để hỗ trợ cả ba loại truy vấn nói trên. Có thể tối ưu các cấu trúc dữ liệu cho một loại truy vấn nhất định nếu biết rằng chỉ một loại truy vấn đó hay được sử dụng cho loại ứng dụng cụ thể. 3.2 Một số kỹ thuật nâng cao hiệu năng tìm kiếm đa phương tiện Thông thường có thể giảm không gian tìm kiếm bằng tiến trình lọc trên cơ sở các tiêu chí nào đó. Có một số tiêu chí và tiến trình lọc phụ thuộc vào ứng dụng hay đặc trưng cụ thể. Các tiêu chí khác không phụ thuộc vào ứng dụng mà có thể được sử dụng cho nhiều tiến trình tìm kiếm. Ý tưởng cơ sở của chúng được trình bày như sau đây. Các tiến trình lọc, thí dụ việc lọc trên cơ sở thuộc tính, được thực hiện rất hiệu quả để chọn các mục thỏa mãn tiêu chí nào đó. Việc tìm kiếm trên cơ sở đặc trưng phức tạp (biểu diễn bởi các vector đa chiều) sau đó chỉ được thực hiện trên các mục đã được chọn lựa. Vì tổng số các mục lựa chọn là rất nhỏ so với tổng số mục trong CSDL, cho nên tiến trình tìm kiếm sẽ nhanh. Có các phương pháp