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

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

- 1 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 2 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 3 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 4 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

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

DBMS (Database Management System) Hệ quản trị cơ sở dữ liệu MDBMS (Multimedia Database Management System) 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

Truyền thông da phương tiện MultiMedia

Độ chính xác Precision

QAS (Question Anser System) Hệ trả lời câu hỏi

Truy vấn Query

Thuật ngữ (từ) Term

Sắp xếp Ranking

Bản ghi Record

Khả năng tìm thấy Recall

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

- 5 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 6 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.

- 7 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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:

- 8 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

• 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.

- 9 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 10 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.

- 11 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

• 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

- 12 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 13 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 14 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 15 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 16 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 17 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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à

- 18 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.

- 19 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 20 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 21 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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ồ.

- 22 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 23 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.

- 24 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.

- 25 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.

- 26 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 27 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.

Phù hợp người sử dụng

Người sử dụng

Tài liệu

Truy cập

Thế giới thực

Phù hợp hệ thống

Hệ thống cụ thể

Các yêu cầu

CSDL tài liệu

Đối sánh

Mô hình tài liệu

Mô hình yêu cầu

Tri thức

Mô hình tìm kiếm thông tin

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)

- 28 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.

- 29 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Query

Tài liệu văn bản

Xử lý

Xử lý

Đại diện query

Đại diện tài liệu

Đố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ở

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.

- 30 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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:

Giao diện người sử dụng

Hình 2.3. Mô hình kiến trúc của hệ tìm kiếm thông tin

(1)

Văn bản

Các tính toán cho văn bản

NSD yêu cầu

(2)

Quản trị cơ sở dữ liệu

Tính toán cho câu truy vấn

Lập chỉ mục

NSD phản hồi

Tìm kiếm

Chỉ mục

Truy vấn

Tệp chỉ mục

Săp xếp

Tìm kiếm tài liệu

Tài liệu đã sắp xếp

Cơ sở dữ liệu văn bản

(3)

Hình 2.4 Cấu trúc hệ tìm kiếm thông tin tiêu biểu

- 31 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 32 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.

- 33 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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 tử Các sự kiện rõ ràng. dung tài trong các liệu. Các phần có kiểu dữ liệu đã được định nghĩa.

Lưu trữ tử tự Các văn bản ngôn ngữ nhiên. Các phần 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. Giống DBMS nhưng hỗ trợ thêm những thủ tục (Tính tính tổng, trung bình, phép chiếu…)

Xử lý

Các câu truy vấn không giới hạn. 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.

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ẽ

- 34 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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ữ.

- 35 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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 t 1 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.

- 36 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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à

2

2

+

(w ) 1

(w ) 2

tính khoảng cách Eclide từ điểm (w1, w2) tới gốc:

3

+

)

)2

( 3.0

( 4.0

SC(Q,Di) =

= 0.500 Với trọng số 0.3 và 0.4, SC(Q,Di) =

SC cao nhất nếu w1 và w2 đều bằng 1. Khi đó:

SC(Q,Di) = 2 = 1.414

2

)

( ) 2 w + 1

( w 2

Để đưa SC vào khoảng [0,1], SC được tính như sau:

2

SC(Q t1v t2, di) =

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

2

2

−

)

)

( 1

( −+ 1

w 2

w 1

−

1

càng gần đến điểm (1,1) thì nó càng thoả yêu cầu của toán tử AND:

2

SC(Q t1^t2, di) =

- 37 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Mở rộng trong việc thêm vào trọng số của câu truy vấn:

+

2 2 wq 1 1

2 2 wq 2 2

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:

+

q

2 q 1

2 2

2

2

−

+

−

1(

)

1(

)

q

2 q 1

w 1

2 2

w 2

−

1

SC(Qq1vq2, di) =

+

q

2 q 1

2 2

   

   

SC(Qq1^q2, di) =

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.

1 p

+

p j

Độ tương quan SC tổng quát như sau:

+

q

q

p p wq i i p i

p wq j p j

   

   

1 p

−

+

−

1(

1(

)

q

q

w

p i

p j

−

1

SC(D, Qqivqj ) =

+

p w i q

q

) p i

p j p j

   

   

SC(D, Qqi^qj) =

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.

- 38 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 39 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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:

- 40 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 41 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.

- 42 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Bảng 2.2: Cách tập tin nghịch đảo lưu trữ

Doc D1 D2 D3 Term

1 T1 0 1

1 T2 1 1

1 T3 0 0

0 T4 0 1

Bảng 2.3 Cách tập tin trực tiếp lưu trữ

Term T1 T2 T3 T4 Doc

1 D1 0 1 0

1 D2 1 1 0

0 D3 1 1 1

* 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:

- 43 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Bảng 2.4: Thêm một tài liệu mới vào tập tin nghịch đảo

Doc D1 D2 D3 D4 Term

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

- 44 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.

- 45 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

n

FREQ ik

tổng tần số xuất hiện của k trong tất cả n tài liệu:

i

− 1

TOTFREQk = ∑

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ự

- 46 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

* 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ó

- 47 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

D2 D1 D3 D1 D2 D3 Term

4 1 5 0.2218 0.8872 1.109 CAR

- 48 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.

A ABOUT ACROSS AFTER AFTERWARDS AGAIN AGAINST ALL ALSO

ALTHOUGH ALWAYS AMONG AMONGST AN AND ANOTHER ANY ANYHOW

ANYONE ANYTHING ANYWHERE ARE AROUND AS AT BE BECOME

Bảng 2.5: Danh sách từ dừng của tiếng Anh

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).

- 49 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 50 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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]

- 51 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

N

=

(

,

)

QDS i

j

. QT ik

jk

và câu truy vấn Qj được tính như sau:

∑

k

= 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

N

. QT ik

jk

cách cosin) và được biểu diễn như dưới đây:

∑

k

= 1

=

=

=

θ

(

,

)

cos

QDS i

j

N

N

|

|

. QD i j || QD i

j

.

Q

2 T ik

2 jk

∑

∑

k

k

= 1

= 1

Đâ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:

- 52 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

+ )1( i

)( i

i

i

=

+

−

Q

Q

đây được diễn giải như sau:

∑

∑

i

i

∈

∈

Re

α D

D l

β D

Non

D Re l

- 53 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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.

- 54 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

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) Tập hợp tài liệu

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:

∩ RP

∈

]1,0 [

P

+Khả năng tìm thấy (Recall):

∩ RP

∈

]1,0 [

R

+Độ chính xác (Precision):

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:

- 55 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Độ chính xác

Khả năng tìm thấy

(0,0)

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

Q

Q D1 D2 D3 dfi D/dfi

IDFi

D1

D2

D3

Terms

A

0

1

1

1

3

0

0

3/3=1

0

0

0

arrived

0

0

1

1

2

0.1761 0.1761

3/2=1.5 0.1761

0

0

damaged

0

1

0

0

1

0

3/1=3

0.4771

0.4771 0

0

delivery

0

0

1

0

1

0

0

3/1=3

0.4771

0.4771 0

Fire

0

1

0

0

1

0

3/1=3

0.4771

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

0

0

3/3=1

0

0

0

Of

0

1

1

1

3

0

0

3/3=1

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:

- 56 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

• 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:

2 ji,W

iD

∑=

i

+

+

+

=

=

.0

2 4771

.0

2 4771

.0

2 1761

.0

2 1761

.0

5173

.0

7192

=D 1

+

+

+

=

=

.0

2 1761

.0

2 4771

.0

2 9541

.0

2 1761

.1

2001

.1

0955

=D 2

+

+

+

=

=

.0

2 1761

.0

2 1761

.0

2 1761

.0

2 1761

.0

1240

.0

3522

=D 3

=

+

+

=

=

W

.0

2 1761

.0

2 4771

.0

2 1761

.0

2896

.0

5382

2 jQ,

= ∑Q

i

jQ, WW ji,

∴

i

Tiếp theo tính tất cả các tích điểm (bỏ qua các tích 0): ∴Q•Di= ∑

Q•D1 = 0.1761*0.1761=0.0310

Q•D2 = 0.4771*0.9542*0.1761*0.1761=0.4862

WW , jQ

, ji

Q•D3 = 0.1761*0.1761*0.1761*0.1761=0.0620

i

W

W

2 , jQ

2 , ji

=> Các giá trị tương đồng: ∑ ∴CosθDi = S(Q,Di) =

∑

∑

j

i

=

=

=

.0

0801

Dθ

1

.0 5382

0310 .0*

.0

7192

• DQ 1 * 1 DQ

Cos

- 57 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

=

=

=

.0

8246

Dθ

2

• DQ 2 DQ *

.0 5382

4862 .1*

.0

0955

2

=

=

=

.0

3271

Cos

Dθ

3

.0 5382

0620 .0*

.0

3522

• DQ 3 DQ * 3

Cos

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.

- 58 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

- 59 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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 lọc

sau:

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

Một số thuộc tính có cấu trúc, thí dụ như ngày tháng, được kết hợp với hầu

hết các đối tượng đa phương tiện. Nếu người sử dụng chỉ quan tâm đến các đối

tượng mà thỏa mãn một vài thuộc tính thì chúng ta sẽ sử dụng các thuộc tính này để

lựa chọn sơ bộ, sau đó thực hiện tìm kiếm trên cơ sở các đặc trưng phức tạp hơn từ

chúng.

Thí dụ, khi có sẵn phân lớp chủ đề thì người sử dụng chọn các chủ đề quan tâm và

việc tìm kiếm các đối tượng chỉ cần thực hiện trong chủ đề đó.

- 60 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Các tiệm cận trên đây thường được áp dụng, nó không bị giới hạn trên các đặc trưng

nào được sử dụng. Với vài đặc trưng cụ thể, có thể sử dụng một số thuộc tính đặc

biệt để giảm không gian tìm kiếm. Thí dụ, trong phương pháp chỉ mục và tìm kiếm

hình dạng ảnh trên cơ sở vùng, chúng ta sử dụng độ lệch (eccentricity) hình dạng

làm tiêu chí lọc – chỉ cần tìm kiếm các hình dạng trong dải lệch xác định trước.

3.2.2 Các phương pháp trên cơ sở tính không đều tam giác

Phần lớn thước đo khoảng cách đặc trưng, thí dụ khoảng cách Euclid, là

metrics. Metrics có tính chất gọi là tính không đều tam giác ( triangle inequality).

Berman và Shapiro đã sử dụng tính chất này để làm giảm số lần so sánh trực tiếp

đặc trưng trong CSDL. Tính không đều của tam giác phát biểu rằng khoảng cách

giữa hai đối tượng không nhỏ hơn hiệu khoảng cách của nó đến đối tượng khác (đối

tượng thứ ba). Về toán học, tính chất không đều của tam giác được viết như sau:

d(i,q) ≥ |d(i, k) - d(q, k)|

trong đó, d là khoảng cách, i, q và k là các đối tượng (k là đối tượng khóa).

Bất đẳng thức trên đúng với mọi k. Vậy khi sử dụng tập các đối tượng (k1,..., km)

≥

−

max

|

)

|)

),( qid

,( kid

,( kqd

≤≤ 1

mj

j

j

thay cho k làm các đối tượng so sánh thì ta có:

trong đó m là tổng số đối tượng so sánh.

Chúng ta áp dụng tính không đều tam giác vào tìm kiếm thông tin đa phương tiện

như sau:

• Chọn m vector đặc trưng (như đối tượng khóa) làm cơ sở so sánh. Thông

thường, m nhỏ hơn nhiều so với tổng số n các đối tượng (i1, ..., in) trong CSDL.

• Với mỗi đối tượng i trong CSDL và mỗi vector so sánh kj, chúng ta tính trước

giá trị d(i,kj) và lưu trữ chúng trong CSDL.

• Trong khi tìm kiếm , ta tính khoảng cách d(q, k j) giữa câu truy vấn q với mỗi

=

−

il )(

max

|

kid ,(

)

kqd ,(

|)

vector so sánh kj.

≤≤ 1

mj

j

j

cho mỗi đối tượng i trong CSDL. • Tìm

• Chỉ những đối tượng có l(i) nhỏ hơn ngưỡng T chọn trước thì được lựa chọn để

- 61 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

tính toán khoảng cách từ nó tới q, gọi là d(q,i). Chúng ta không cần tính toán

khoảng cách giữa q và các đối tượng khác trong CSDL vì chúng được đảm bảo

là lớn hơn ngưỡng T, nó được lựa chọn theo đặc trưng sử dụng và theo yêu cầu

của người sử dụng.

Chú ý rằng các đối tượng không được lựa chọn trên cơ sở l(i) thì có khoảng

cách tới q lớn hơn T. Tuy nhiên, không phải mọi đối tượng được lựa chọn đều có

khoảng cách tới q nhỏ hơn T. Thí dụ sau đây mô tả tiến trình này. Giả sử CSDL có

8 đối tượng ảnh được biểu diễn bởi các vector đặc trưng i1 đến i8. Hai vector so sánh

là k1 và k2. Khoảng cách của từng đối tượng trong CSDL đến vector so sánh được

tính toán trước như trong bảng 3.1:

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

l(i) Database d(i, k1) d(i, k2) |d(i, k1)- d(q, |d(i, k2)- d(q,

items k1)| k2)|

2 5 1 1 1 i1

4 9 1 5 5 i2

7 2 4 2 4 i3

9 3 6 1 6 i4

3 8 0 4 4 i5

2 9 1 5 5 i6

1 4 2 2 2 i7

4 10 1 6 6 i8

Giả sử ta muốn tìm các đối tượng ảnh trong CSDL mà khoảng cách của

chúng đến câu truy vấn q nhỏ hơn 3, và khoảng cách giữa q đến từng vector so sánh

là 3 và 4. Cột thứ tư của bảng trên cho biết giá trị |d(i, k 1)-d(q, k1)| và cột thứ năm

chỉ ra |d(i, k2)-d(q, k2)| cho mỗi đối tượng ảnh trong CSDL.

- 62 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Cột cuối cùng trong bảng là giá trị l(i). Từ các giá trị của cột này ta thấy chỉ

đối tượng i1 và i7 là có khoảng cách đến q nhỏ hơn 3, do vậy nó cần so sánh trực

tiếp với q. Thí dụ này chỉ cần tính toán trực tuyến 4 khoảng cách giữa các vector đa

chiều thay cho việc tính toán 8 khoảng cách nếu không sử dụng tiến trình lọc trên

cơ sở tính không đều tam giác.

Tiến trình lọc trên cơ sở tính không đều tam giác được sử dụng trong mọi kỹ

thuật tìm kiếm mà thước đo khoảng cách của chúng là metric.

3.2.3 Mô hình tìm kiếm trên cơ sở cụm (cluster-based)

Trong các mô hình tìm kiếm thông tin đã khảo sát trong Chương 2 cũng như

đầu Chương 3, các tài liệu tương tự có thể không gần kề trong hệ thống tệp. Với

loại tổ chức tệp này, rất khó cài đặt khả năng duyệt (browsing). Hiệu quả của tìm

kiếm sẽ thấp vì không thể tìm ra mọi mục phù hợp và phải tìm kiếm trên toàn bộ

không gian tài liệu. Để khắc phục nhược điểm này, ta thực hiện cụm (nhóm) các tài

liệu tương đồng vào các cụm (cluster).

3.2.3.1 Sinh cụm

Hai tiệm cận tổng quát khi sinh cụm là:

• Tiệm cận thứ nhất: Trên cơ sở tính tương tự mọi cặp (pairwise) tài liệu,

hãy nhóm các mục tương tự vào cụm chung. Trong tiệm cận trên cơ sở tính tương

tự từng cặp, mỗi tài liệu được đại diện như “vector tài liệu” trong mô hình không

gian vector. Sau đó mức độ tương đồng giữa cặp tài liệu được tính toán. Trong tiến

trình cụm, mỗi tài liệu được khởi đầu trong một lớp (class) và sau đó hai tài liệu

tương tự nhau nhất trên cơ sở tính tương tự của cặp được tổ hợp trong một cụm.

Tính tương đồng giữa cụm mới hình thành và các tài liệu kh ác được tính toán, sau

đó tài liệu tương đồng nhất (kể cả cụm) được tổ hợp vào cụm mới. Tiến trình tổ hợp

tiếp tục cho mọi tài liệu được nhóm vào cụm cao hơn. Đó là tiến trình cụm phân

cấp.

- 63 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Các phương pháp cụm phân cấp trên cơ sở tính tương đồng giữa các t ài liệu

là khá đắt khi thực hiện. Nhưng phương pháp này sinh ra tập duy nhất các cụm cho

mỗi tập tài liệu.

• Tiệm cận thứ hai: Sử dụng phương pháp Heuristic không đòi hỏi tính

toán tính tương tự cặp tài liệu.

Phương pháp này sinh ra nhanh các cụm thô và tươn g đối rẻ hơn phương

pháp trên. Tiến trình heuristic đơn giản nhất (tiến trình một bước) lấy các tài liệu sẽ

cụm theo thứ tự tùy ý. Lấy tài liệu thứ nhất để đặt vào cụm. Mỗi tài liệu tiếp theo sẽ

so sánh với các cụm trước đó, rồi đặt vào cụm tồn tại nếu đủ tính tương đồng với

cụm đó. Nếu tài liệu không đủ tính tương đồng với các cụm có sẵn thì để vào cụm

mới. Tiến trình này tiếp tục cho đến khi mọi tài liệu được cụm. Cấu trúc cụm được

sinh ra theo cách này phụ thuộc vào thứ tự trong đó tài liệu được xử lý.

3.2.3.2 Tìm kiếm trên cơ sở cụm

Khi các cụm (nhóm) được hình thành, tìm kiếm tài liệu sẽ hiệu quả. Mỗi cụm

có vector đại diện, thường là tâm của chúng. Tâm của cụm được tính bằng vector

trung bình của mọi tài liệu trong nhóm (trọng số của thuật ngữ tâm i được xác định

bằng trọng số trung bình của mọi thuật ngữ i trong mọi tài liệu).

Trong khi tìm kiếm tài liệu, các vector câu truy vấn được so sánh với tâm của

các cụm. Sau khi nhận ra cụm có tính tương đồng cao nhất với vector truy vấn, sẽ

có hai khả năng:

• Mọi tài liệu trong cụm được tìm ra. Điều này xảy ra khi các cụm đều nhỏ.

• Vector tìm kiếm được so sánh với từng vector tài liệu trong cụm và chỉ

tài liệu nào có tính tương đồng cao nhất thì được tìm ra làm kết quả.

3.2.4 Chỉ mục ngữ nghĩa tiềm ẩn (LSI) để tìm kiếm thông tin trên cơ sở không

gian vector

Một kỹ thuật khác được áp dụng để tìm kiếm thông tin đa phương tiện đó

là kỹ thuật chỉ mục ngữ nghĩa tiềm ẩn (Latent Semantic Indexing – LSI). Ý tưởng

- 64 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

cơ bản của kỹ thuật này là sử dụng một ma trận phân tích để xác định những

thành phần chính của vector không gian được xác định bởi tập tài liệu, và sau đó

chiếu vector lên không gian được mở rộng bởi những thành phần chính đó. Trong

kỹ thuật LSI, những thành phần chính được xem là thể hiện cho những khái niệm

quan trọng, trong khi những thành phần ít quan trọng hơn được xem là những

biến đổi trong cách sử dụng khác nhau của từ. Vì thế LSI nhấn mạnh khía cạnh

quan trọng của tfi.df và bỏ qua hiệu quả của cách sử dụng từ ngữ khác nhau. Sau

đó, các tài liệu được so sánh bằng cách sử dụng phép đo độ tương đồng bằng

hàm số cosin và kết quả sẽ được sắp xếp theo độ tương đồng để hiển thị.

LSI là một kỹ thuật khá hiệu quả trong tìm kiếm văn bản, nên tác giả luận văn

sẽ đi sâu nghiên cứu về kỹ thuật này và chi tiết sẽ được trình bày trong mục tiếp

theo của chương.

- 65 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

3.3 Kỹ thuật LSI

3.3.1 Giới thiệu LSI

Trong mô hình không gian vector, mỗi tài liệu được biểu diễn bởi một vector

trọng số thuật ngữ N chiều, mỗi thành phần của vector là trọng số của từng thuật

ngữ trong số N thuật ngữ của tài liệu. Nếu tập tài liệu có M tài liệu, thì tập tài liệu

này được biểu diễn bằng ma trận A kích thước MxN. Trong khi tìm kiếm, câu truy

vấn cũng được biểu diễn bằng vector trọng số thuật ngữ N chiều. Tính tương đồng

giữa truy vấn và từng tài liệu lưu trữ được tính bằng tích vô hướng hay hệ số cosin

giữa vector truy vấn và vector tài liệu.

Tiệm cận trực tiếp trên đây có hai yếu điểm sau đây:

• Yếu điểm thứ nhất: Tập hợp tài liệu (thí dụ thư viện) có thể chứa đến hàng triệu

tài liệu với nhiều ngàn khái niệm (M và N rất lớn). Vậy đòi hỏi tổng số bộ nhớ

rất lớn để lưu trữ. Thí dụ, nếu thư viện có 1 triệu tài liệu với 10 000 thuật ngữ

thì chúng ta cần đến 10GB bộ nhớ lưu trữ với mỗi phần tử chiếm 1 byte.

• Yếu điểm thứ hai: Ít nhất cần M phép nhân vector N chiều khi tìm kiếm nếu sử

dụng thước đo tương tự tích vô hướng và đòi hỏi nhiều hơn thế nếu sử dụng

thước đo tương tự hệ số cosin. Khi M và N lớn, thời gian đòi hỏi để tính toán sẽ

không đáp ứng với việc tìm kiếm trực tuyến.

Chỉ mục ngữ nghĩa tiềm ẩn (LSI - Latent Semantic Indexing) được Falotsos,

Foltz, Dumais và Bently phát triển để giải quyết một phần khó khăn trên. Ý tưởng

cơ bản của LSI là thực hiện nhóm các thuật ngữ tương đương để hình thành “khái

niệm” hay “chủ đề” và tài liệu sẽ được đại diện bởi các khái niệm hay chủ đề này.

Vì tổng số khái niệm sẽ nhỏ hơn nhiều so với tổng số thuật ngữ, do vậy đòi hỏi ít bộ

nhớ lưu trữ hơn và thời gian tính toán sẽ nhanh hơn.

- 66 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Mô hình LSI

Mô hình không gian Term – Doc Mô hình term – topic - doc

Hình 3.1. Mô hình LSI

Mô hình này minh hoạ một cách tiếp cận trực tiếp hơn mối liên quan giữa

các tài liệu và các thuật ngữ như trong truy tìm vector, trong đó tồn tại một lớp giữa

trong đó bao gồm cả lược đồ câu truy vấn và lược đồ tài liệu. Không gian của khái

niệm có thể có kích thước nhỏ hơn. Chẳng hạn, chúng ta có thể xác định rằng câu

truy vấn t3 trả lại kết quả là d2, d3,d4 trong tập các câu hỏi, dựa vào sự quan sát cho

thấy chúng có liên quan đến khái niệm C2, không yêu cầu tài liệu đó phải chứa term

t3. Câu hỏi đặt ra là làm thế nào để thu được không gian khái niệm?. Một cách khả

quan để có thể tìm thấy những miêu tả chính tắc của ngôn ngữ tự nhiên, nhưng đây

là một nhiệm vụ khó đạt được. Đ ể đơn giản hơn, chúng ta có thể sử dụng nhữ ng

thuộc tính toán học của ma trận term – doc, ví dụ, xác định những khái n iệm bằng

cách tính toán ma trận.

3.3.2 Phương pháp luận LSI

Chỉ mục ngữ nghĩa tiềm ẩn (LSI) là một kỹ thuật được thiết kế để giải quyết

vấn đề đồng nghĩa và các vấn đề đa nghĩa của từ ngữ. Kỹ thuật chỉ mục ngữ nghĩa

tiềm ẩn giả thiết rằng có một số cấu trúc tiềm ẩn trong các mẫu có các từ đồng thời

- 67 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

xuất hiện, thông qua các tập và các phép thử tài liệu để mô hình hóa những phần

phụ thuộc giữa các từ và tài liệu. LSI dùng kỹ thuật tách các giá trị đơn (SVD-

Singular Value Decomposition) để giảm bớt kích thước ma trận term - doc,

không gian r chiều xuống một không gian s chiều, s<

gọi là không gian khái niệm.

Tất cả các thuật ngữ M và các tài liệu N có thể được thể hiện dưới dạng các

vector trong không gian s chiều. Do vậy, các từ không còn độc lập nhau, và

những từ đồng nghĩa sẽ tương ứng cùng kích thước hoặc có cùng độ tương đồng

trong không gian này. Các tài liệu với những mẫu từ tương tự sẽ gần nhau dù

chúng không chia sẻ những từ chung, điều này cho thấy rằng kỹ thuật chỉ mục

ngữ nghĩa tiềm ẩn có thể phát hiện ra những mối quan hệ ngữ nghĩa học tiềm ẩn

giữa những tài liệu. Ví dụ, chỉ mục ngữ nghĩa tiềm ẩn sẽ thấy được “laptop” và

“portable” xuất hiện nhiều trong cùng ngữ cảnh và có vectơ tương tự.

Xét ma trận term – doc

- Gọi A là ma trận term-doc với M cột (Terms) và N hàng (Docs).

t

q

- Các phần tử của ma trận là trọng số w được tính từ lược đồ tf-idf. i,j

At

At • q

query•doc1

doc1

doc2

query•doc2

doc3

t

N

...

doc4

query•doc6

doc5 doc6

Hình 3.2. Mô hình tính toán và xếp thứ hạng cho các tài liệu

Hình 3.2 minh hoạ ma trận term –doc A có thể được dùng để tính toán thứ

hạng của các tài liệu đối với câu truy vấn q như thế nào.

- 68 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Kỹ thuật LSI sử dụng kỹ thuật SVD bằng cách trong ma trận S chỉ lựa chọn những giá trị đơn lớn nhất, giữ lại những cột tương ứng U và VT. Ma trận kết quả

- As = Us x Ss x Vs

T

được gọi là As và được cho bởi:

trong đó s, s < r là kích thước của không gian khái niệm.

- Tham số s cần phải:

o Đủ lớn để phù hợp với đặc trưng của dữ liệu;

N

N

s

M

o Đủ nhỏ để lọc ra những chi tiết không liên quan.

=

A

S sxs

U

VT sxN Document vectors

MxN

Mxs Term vectors

Hình 3.3. Minh hoạ kỹ thuật Chỉ số hoá ngữ nghĩa tiềm ẩn (LSI)

Trong trường hợp tìm kiếm tài liệu văn bản, hạng r của ma trận A bằng tổng

khái niệm. U được xem như ma trận tương tự tài liệu – khái niệm, V là ma trận

tương tự thuật ngữ - khái niệm. Thí dụ, u2,3 = 0.6 có nghĩa là khái niệm 3 có trọng

số 0.6 trong tài liệu 2 và v1,2 = 0.4 có nghĩa rằng độ tương đồng giữa thuật ngữ 1 và

khái niệm 2 là 0.4.

Trên cơ sở SVD, chúng ta lưu trữ các ma trận U, S và V thay cho A, làm

giảm đáng kể vùng nhớ cần lưu trữ. Thí dụ, giả sử M=1.000.000, N=10.000 và

r=500. Tổng số không gian lưu trữ đòi hỏi sẽ là

1.000.000x500+500x500+10.000x500=505.25 MB. Giá trị này nhỏ hơn nhiều so

với 10 GB để lưu trữ A.

- 69 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Trong khi tìm kiếm , độ tương đồng giữa tài liệu và câu truy vấn được tính

như sau: vector tìm kiếm q trong không gian thuật ngữ được chuyển sang vector qc trong không gian khái niệm bằng cách nhân nó với V T như sau:

qc = VT x q

Độ tương đồng giữa câu truy vấn với từng tài l iệu được tính bằng tích vô

hướng hay hệ số cosin giữa qc và mỗi hàng của U. Do vậy, với việc sử dụng LSI,

chúng ta sẽ làm việc với vector s chiều thay cho vector r chiều khi tính độ tương

đồng. Vì s nhỏ hơn r nhiều lần, cho nên tính toán sử dụng LSI sẽ nhanh hơn nhiều

lần so với phương pháp trực tiếp.

* Các bước sắp xếp tài liệu sử dụng kỹ thuật LSI:

Bước1: Đánh trọng số thuật ngữ và xây dựng ma trận term-doc A và ma trận truy

vấn Q;

Bước 2: Tách ma trận A thành tích của các ma trận và tìm các ma trận U, S, V,

trong đó:

A = USVT

Bước 3: Thực hiện giảm chiều ma trận bằng cách tạo một ma trận vuông Ss có

chiều là s x s từ ma trận S. Tương tự như vậy cho ma trận Vs có chiều là s x N và

ma trận Us có chiều là M x s tương ứng

Bước 4: Tìm các toạ độ vector tài liệu mới trong không gian giảm chiều này;

-1

Bước 5: Tìm các tọa độ véc tơ truy vấn mới trong không gian giảm chiều:

q=qTUsSs

Bước 6: Sắp xếp các tài liệu theo thứ tự giảm dần của giá trị tương đồng cosin giữa

câu truy vấn và tài liệu.

Công thức tính toán để tính các giá trị tương đồng cosin trong mô hình không

gian vector cơ sở. Thực chất là tính tích điểm giữa các toạ độ vector câu truy vấn và

tài liệu chia cho tích của độ dài vector truy vấn và vector tài liệu.

dq * dq

Cosθdi = S(q,d)=

- 70 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Ví dụ: cho 3 tài liệu sau:

d1: Shipment of gold damaged in a fire.

d2: Delivery of silver arrived in a silver truck.

d3: Shipment of gold arrived in a truck.

Sử dụng kỹ thuật LSI để sắp xếp các tài liệu này cho truy vấn “gold silver truck”.

Bước1: Đánh trọng số thuật ngữ và xây dựng ma trận term-doc A và ma trận truy

vấn:

1 0

1 1

1 1

0 0

1

0

0

0

0

1

0

0

1

0

0

0

=

=

A

q

1

0

1

1

1

1

1

0

1

1

1

0

1

0

1

0

0

2

0

1

0

1

1

1

                

                

                

                

Terms d1 d2 d3 q

a arrived damaged delivery fire gold in of shipment silver truck

Bước 2: Tách ma trận A thành tích của các ma trận và tìm các ma trận U, S, V,

trong đó:

A = USVT

- 71 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

−

−

.0

4201

0748

.0

0460

−

.0 −

.0

2995

.0

2001

4078

−

.0 −

.0

1206

2749

.0

4538

−

.0 −

−

.0

1576

.0

3046

.0

2006

−

−

.0

1206

.0

2749

.0

4538

=

=

−

S

.4 .0

0989 0000

.0 .2

0000 3616

.0 .0

0000 0000

U

.0

2626

.0

3794

1547

−

.0 −

.0

0000

.0

0000

.1

2737

.0

4201

.0

0748

.0

0460

    

    

−

−

.0

4201

0748

.0

0460

−

.0 −

.0

2626

.0

3794

1547

−

−

.0 −

.0

3151

.0

6093

.0

−

−

.0

2995

.0

2001

.0

4078

               4013  

                

−

−

−

−

−

=

=

−

−

−

TV

V

.0 .0

4945 6458

.0 6492 − 7194 .0

.0 .0

5780 2556

.0 .0

6458 7194

.0 5817 2469 .0

−

.0 4945 6492 .0 −

−

.0

5817

.0

2469

.0

7750

5780

.0

.0

2556

.0

7750

    

    

    

    

Bước 3: Thực hiện giảm chiều vector bằng cách giữ lại các cột đầu tiên của U và V

−

.0

4201

0748

−

.0 −

.0

2995

.0

−

.0

1206

2749

−

.0 −

.0

1576

.0

3046

−

.0

1206

.0

2749

.4

0989

.0

0000

=

≈

=

−

S

.0

2626

.0

3794

≈ sUU

sS

.0

0000

.2

3616

  

  

−

.0

4201

.0

0748

−

−

.0 .0

4201 2626

.0 0748 − 3794 .0

−

−

.0

3151

.0

−

−

.0

2995

.0

  2001              6093  2001 

                

−

.0

4945

6492

−

−

−

.0

4945

=

−

.0 −

=

.0

7194

.0

6458

V

T V ≈

≈ sVV

T s

−

6458 7194

.0 5817 2469 .0

.0

6492

.0 .0

  

  

−

.0

5817

.0

2469

    

    

và các cột và hàng đầu tiên của S.

- 72 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Bước 4: Tìm các toạ độ vector tài liệu mới trong không gian 2 chiều rút gọn này.

Các hàng của V giữ các giá trị vector đặc trưng. Đây là các tọa độ của các vectors

tài liệu riêng, vì vậy

d1(-0.4945, 0.6492)

d2(-0.6458, -0.7194)

d3(-0.5817, 0.2469)

-1

Bước 5: Tìm các tọa độ véc tơ truy vấn mới trong không gian 2 chiều rút gọn

q=qTUsSs

Lưu ý: Đây là các toạ độ mới của vector truy vấn trong không gian hai chiều. Chú ý

xem ma trận này và ma trận truy vấn q ban đầu đã cho ở Bước 1 khác nhau như thế

-1

nào.

−

.0

4201

0748

−

.0 −

.0

2995

.0

−

.0

1206

2749

−

.0 −

.0

1576

3046

−

.0 −

.0

1206

0

2749

.0

0000

1 0989

.4

−

0

0

0

0

1

0

0

0

1

]1

q=qTUsSs

.0

2626

.0

3794

.0

0000

−

.0

4201

.0

0748

    

    

1 3616

.2

−

.0

4201

.0

0748

−

.0

2626

3794

−

.0 −

.0

3151

.0

−

−

.0

2995

.0

  2001              6093  2001 

                

−

.0

2140

] 1821

.0

q= [ 0

q = [ −

Bước 6: Sắp xếp các tài liệu theo thứ tự giảm dần của giá trị tương đồng cosin giữa

câu truy vấn và tài liệu.

dq * dq

S(q,d)=

- 73 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

−+

− .0(

− .0)(

.0(

1821

6492 )

−=

0541

.0

.0)( 2

2

2140 2

4945 ) 2

−+

+

− .0(

2140 )

.0(

1821 )

− .0(

4945 )

.0(

6492 )

−+

− .0(

− .0)(

.0(

1821

7194

)

=

.0

9910

S(q,d1)=

2140 2

6458 ) 2

.0)( 2

2

−+

−+

− .0(

2140

)

.0(

1821 )

− .0(

6458 )

.0(

7194

)

−+

− .0(

2140

− .0)(

5817

)

.0(

1821

.0)(

2469 )

=

.0

4478

S(q,d2)=

2

2

2

2

−+

+

− .0(

2140 )

.0(

1821 )

− .0(

5817

)

.0(

2469 )

S(q,d3)=

Sắp xếp các tài liệu theo thứ tự giảm dần của giá trị tương đồng: d2>d3>d1

Chúng ta có thể thấy rằng tài liệu d 2 có giá trị tương đồng cao hơn d3 và d1. Vector

của nó gần với vector truy vấn hơn các vector khác.

* Kỹ thuật tách giá trị đơn (SVD):

Ý tưởng của kỹ thuật tách giá trị đơn (SVD) là tách các đặc trưng chủ yếu

của ma trận term-doc AT và xấp xỉ nó bởi các ma trận nhỏ hơn.

Định lý SVD được phát biểu như sau:

Ma trận bất kỳ A với kích thước MxN số thực có thể biểu diễn như sau: A = U * S * VT

- 74 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

trong đó, U là ma trận trực giao cột M * r với r là hạng (rank) của ma trận A, S là

ma trận đường chéo và V là ma trận trực giao cột N * r.

Ma trận trực giao cột U có nghĩa là UT * U = I, I là ma trận đồng nhất. Nếu S

không tăng (các phần tử được s ắp xếp theo thứ tự giảm dần) thì phân tách trên đây

là duy nhất. Như vậy, kỹ thuật SVD tách một ma trận thành tích của 3 ma trận. Việc tách có thể có độ phức tạp tính toán là O(n3), độ phức tạp này là đáng kể, nó tạo ra

r

r

r

Documents

VT

N

S

Terms

A

=

r x N

sự ước tính gần đúng.

U

r x r

M x r

MxN

Hình 3.4. Mô hình minh hoạ tách giá trị đơn (SVD)

* Các bước tính SVD đầy đủ cho một ma trận A: Bước 1: Tính hoán vị của A: AT và ATA. Bước 2: Xác định các giá trị đặc trưng của ATA và sắp xếp theo thứ tự giảm dần.

Bước 3: Xây dựng ma trận đường chéo S bằng cách đặt các giá trị đơn theo thứ tự giảm dần dọc theo đường chéo của nó. Tính nghịch đảo S-1.

Bước 4: Sử dụng thứ tự các giá trị đặc trưng ở bước 2 và tính các vector đặc trưng của ATA. Đặt các giá trị đặc trưng đó dọc theo cột của V và tính hoán vị VT. Bước 5: Tính U với U=AVS -1. Để hoàn thành việc chứng minh, tính SVD đầy đủ sử dụng công thức A=USVT .

- 75 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

4

=

A

0 −

3

  5 

Ví dụ: Tính SVD đầy đủ cho ma trận sau đây:

   Bước 1: Tính hoán vị của A: AT và ATA

−

4

4

4

=

=

=

AAT

TA

3 −

3 −

25 −

0

0

3

15

25

  

  

  

  

  5 

  5 

 0  − 5 

 15  

Ma trận hoán vị 

Bước 2: Xác định các giá trị đặc trưng của ATA và sắp xếp theo thứ tự giảm dần.

−

−

c

−

=

AAT

cl

Căn bậc hai lúc này để tính giá trị đơn của A

25 −

15 − c

15

25

  

  

| ATA – cl | = (25-c)(25-c) – (-15)(-15) = 0

phương trình đặc trưng c2 – 50c+400=0

Phương trình bậc 2 cho 2 giá trị

Theo thứ tự giảm dần, có | 40 | > | 10 |

40 =

.6

3245

10 =

.3

1622

Các giá trị đặc trưng c1 = 40; c2 = 10

Các giá trị đơn s1= > s2 =

.6

3245

0

.0

1581

0

=

=−

S

1S

0

.3

1622

0

.0

3162

  

  

  

  

Bước 3: Xây dựng ma trận đường chéo S bằng cách đặt các giá trị đơn theo thứ tự giảm dần dọc theo đường chéo của nó. Tính nghịch đảo S-1

Bước 4: Sử dụng thứ tự các giá trị đặc trưng từ bước 2 và tính các vector đặc trưng của ATA. Đặt các giá trị đặc trưng đó dọc theo cột của V và tính hoán vị VT

- 76 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

−

−

−

−

−

−

−

−

40

15

10

15

15

−

=

−

=

AAT

cl

AAT

cl

25 −

15 −

25 −

15 −

−

−

−

−

15

40

15

25

15

10

15

25

15

  

  

 = 

 = 

  

  

 15  15 

  

Với c1=40 Với c2=10

−

−

−

15

0

0

x 1

x 1

−

−

15 −

x

x

15

0

15

15

0

2

2

  

  

 15  15 

 15  

  

  

  

  

  

 = 

  

 = 

(ATA – cl) x1 = 0 (ATA – cl) x2 = 0

-15x1 + -15x2 = 0 -15x1 + -15x2 = 0

-15x1 + -15x2 = 0 15x1 + 15x2 = 0

Giải thích cho x2 cho bởi công thức Giải thích cho x2 cho bởi công thức

x 1

x 1

=

=

x

2

x 1

x

x

2

x 1 x 1

2

x 1 − x 1

  

  

  

 = 

  

  

  

 = 

khác: x2=x1 khác: x2=x1

=

+

=

=

+

=

L

x

L

x

2 x 1

2 2

x 21

2 x 1

2 2

x 21

.0

7071

=

=

=

=

x 1

x 1

−

.0 −

.0

.0

Lx / 1 − Lx / 1

Lx / 1 Lx / 1

  

  

  7071 

 7071  7071 

  

 = 

  

 = 

     

     

1 2 1 2

1 2 1 2

     

     

7071

.0

=

=

]

V

x

[ x 1

2

.0 −

.0

7071

.0

  

 7071  7071 

−

=

TV

.0 .0

7071 7071

  

 .0 7071  7071 .0 

Chia bởi chiều dài của nó,

4

7071

.0

.0

1581

0

− 1

=

=

U

AVS

0 −

3

.0

7071

.0

0

.0

3162

  

  .0 −  5  

 7071  7071 

  

  

Bước 5: Tính U với U=AVS-1. Để hoàn thành việc chứng minh, tính SVD đầy đủ sử dụng công thức A=USVT

- 77 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

4

1118

.0

2236

− 1

=

=

U

AVS

0 −

3

.0

1118

.0

2236

  

  .0 −  5  

  

.0

4472

8944

− 1

=

=

U

AVS

.0 −

.0

8944

.0

4472

  

  

−

.0

4472

8944

.6

3245

0

.0

7071

.0

=

=

SV TUA

.0 −

.0

8944

.0

4472

0

.3

1622

.0

7071

7071

.0

  

  

  

  

  

 7071  

−

.0

4472

8944

.4

4721

.4

=

=

SV TUA

.0 −

.0

8944

.0

4472

.2

2360

2360

.2

  

  

  

 4721  

.3

9998

0

4

=

=

SV TUA

−

.2

9999

.4

9997

3

0 − 52

  

 ≈ 

  

  

Tính trực giao của các ma trận V và U có được bằng cách xem xét các

vector đặc trưng của chúng. Điều này có thể được chứng minh bởi các tích điểm

giữa các vector cột. Tất cả các tích điểm đều được cho = 0. Ngoài ra, chúng ta có

thể vẽ và thấy được tất cả các trực giao.

- 78 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

CHƯƠNG 4: PHÁT TRIỂN CHƯƠNG TRÌNH THỬ NGHIỆM

4.1 Giới thiệu bài toán

Chương trình xây dựng nhằm giải quyết bài toán có đầu vào và đầu ra như sau:

Input: tập gồm rất nhiều dữ liệu văn bản được lưu trữ trong máy tính dưới dạng

không nén.

Output: Danh sách các tệp văn bản chứa từ hay cụm từ trong câu truy vấn.

Với đầu vào và đầu ra của bài toán như trên thì chương trình phải đáp ứng các

yêu cầu sau:

• Chương trình cho phép thu thập và tạo chỉ mục tài liệu;

• Cho phép cập nhật lại chỉ mục mỗi khi có tài liệu mới được đưa vào hệ

thống;

• Cho phép người dùng nhập vào câu truy vấn, sau đó thực hiện tìm kiếm các

tài liệu liên quan đến câu truy vấn;

• Sắp xếp các tài liệu theo thứ tự giảm dần về độ tương quan của tài liệu và

câu truy vấn, sau đó hiển thị kết quả cho người dùng.

4.2 Chức năng chương trình

Chương trình được xây dựng với các chức năng chính sau:

- Tập hợp tài liệu

- Tách từ từ các tài liệu

- Tính trọng số của các từ ứng với mỗi tài liệu

- Chọn lọc các từ có giá trị phân biệt cao làm chỉ mục

- Lập chỉ mục cho các từ tạo nên tài liệu

- Cập nhật lại chỉ mục khi thêm tài liệu mới

- Hiển thị kết quả tìm kiếm cho người dùng.

4.3 Quy trình phát triển ứng dụng

Để xây dựng một chương trình đáp ứng các chức năng trên, cần thực hiện

các bước sau đây:

- 79 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

4.3.1 Xây dựng ma trận Term – Doc

Xây dựng ma trận Term – Doc A có kích thước MxN (M thuật ngữ, N tài

liệu) bao gồm các tần số tfij của thuật ngữ i trong tài liệu j. Ma trận này là ma

trận chỉ chứa những thuật ngữ xuất hiện tập trung trong một số tài liệu.

4.3.2 Lập chỉ mục tài liệu

Mục tiêu của làm chỉ mục là tìm ra các thuật ngữ tốt nhất để đại diện tài liệu

sao cho các tài liệu được truy tìm chính xác trong tiến trình truy vấn. Tiến trình chỉ

mục tự động bao gồm các bước sau:

• Tách các từ từ các tài liệu;

• Nhận biết các từ đồng nghĩa. Mọi thuật ngữ có ý nghĩa tương tự sẽ thay thế bằng từ

chung;

• Tính trọng số các thuật ngữ trong tài liệu bằng công thức: Wij = tfij * log (N/dfj);

• Loại bỏ từ dừng;

• Tạo tệp mục lục trên cơ sở các thuật ngữ và trọng số của thuật ngữ nói trên.

4.3.3 Xây dựng ma trận trọng số

Ma trận trọng số được xây dựng bằng cách tính trọng số của các từ ứng với mỗi

tài liệu.

Trọng số của một thuật ngữ phản ánh tầm quan trọng của thuật ngữ đó trong tài

liệu. Khi gán trọng số thuật ngữ, cần phải quan tâm đến cả hai: tần số thuật ngữ (tfij)

và tần số tài liệu (dfj). Công thức chung để tính trọng số thuật ngữ là:

Wij = tfij * log (N/dfj)

trong đó, Wij là trọng số của thuật ngữ j trong tài liệu i, tfij là tần số của thuật ngữ j

trong tài liệu i, N là tổng số tài liệu trong tập tài liệu, dfj là tần số tài liệu chứa thuật

ngữ j. Trọng số trên đây tỷ lệ với tần số thuật ngữ và tỷ lệ nghịch với tần số tài liệu,

công thức này thường được gọi là tf.idf. [idf=log(N/dfi)].

- 80 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

4.3.4 Tìm kiếm theo mô hình vector

Việc tìm kiếm trong mô hình không gian vector được thực hiện dựa trên cơ

sở tính tương đồng giữa câu truy vấn Qj và các tài liệu Di. Độ tương đồng giữa tài

N

=

(

,

)

QDS i

j

. QT ik

jk

liệu Di và câu truy vấn Qj được tính như sau:

∑

k

= 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

N

. QT ik

jk

cách cosin) và được tính theo công thức:

∑

k

= 1

θ

=

=

=

(

,

)

cos

QDS i

j

N

N

|

|

. QD i j || QD i

j

.

Q

2 T ik

2 jk

∑

∑

k

k

= 1

= 1

Đây là hệ số cosine quen thuộc giữa vector Di và Qj. Khi tìm kiếm , danh

sách trả về được sắp xếp theo thứ tự giảm dần của độ tương đồng.

4.3.5 Phương pháp LSI

Bước1: Đánh trọng số thuật ngữ và xây dựng ma trận term-doc A và ma trận

truy vấn Q;

Bước 2: Tách ma trận A thành tích của các ma trận và tìm các ma trận U, S,

V, trong đó:

A = USVT

Bước 3: Thực hiện giảm chiều ma trận bằng cách tạo một ma trận vuông Ss

có chiều là s x s từ ma trận S. Tương tự như vậy cho ma trận Vs có chiều là s x N

và ma trận Us có chiều là M x s tương ứng

Bước 4: Tìm các toạ độ vector tài liệu mới trong không gian giảm chiều này;

-1

Bước 5: Tìm các tọa độ véc tơ truy vấn mới trong không gian giảm chiều:

q=qTUsSs

Bước 6: Sắp xếp các tài liệu theo thứ tự giảm dần của giá trị tương đồng

- 81 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

cosin giữa câu truy vấn và tài liệu.

Công thức tính toán để tính các giá trị tương đồng cosin trong mô hình không

gian vector cơ sở. Thực chất là tính tích điểm giữa các toạ độ vector câu truy vấn và

tài liệu chia cho tích của độ dài vector truy vấn và vector tài liệu.

dq * dq

Cosθdi = S(q,d)=

4.2 Cài đặt thử nghiệm

Chương trình được cài đặt trên nền C#.

Chương trình gồm 2 phần: phần lập chỉ mục và phần tìm kiếm. Phần tìm kiếm được

chia ra làm 2 modul: tìm kiếm theo mô hình vector và tìm kiếm theo kỹ thuật LSI.

4.2.1 Giao diện màn hình lập chỉ mục

Hình 4.1: Giao diện màn hình lập chỉ mục

- 82 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

4.2.2 Giao diện màn hình cập nhập chỉ mục

Hình 4.2: Giao diện màn hình cập nhập chỉ mục

4.2.2 Tìm kiếm tài liệu theo mô hình vector

Giao diện màn hình tìm kiếm theo mô hình vector và kết quả tìm kiếm:

Hình 4.3. Giao diện tìm kiếm theo mô hình vector

- 83 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN

1. KẾT LUẬN

Kỹ thuật tìm kiếm thông tin trong hệ thống cơ sở dữ liệu đa phương tiện đã

và đang là một vấn đề mang tính thời sự của Công nghệ thông tin. Bản luận văn này

đã đề cập được một số vấn đề mang tính chất cơ sở của CSDL đa phương tiện và

một số kỹ thuật tìm kiếm văn bản theo nội dung trong CSDL đa phương tiện như mô

hình Bool cơ sở, mô hình không gian vector, và một số kỹ thuật nâng cao tìm kiếm

như: lọc bằng phân lớp, phương pháp tính không đều tam giác, kỹ thuật phân cụm và

đặc biệt đi sâu vào tìm hiểu kỹ thuật chỉ mục ngữ nghĩa tiềm ẩn (LSI - Latent

Semantic Indexing). Bản luận văn cũng đã xây dựng chương trình thử nghiệm,

demo chức năng lập chỉ mục và một số kỹ thuật tìm kiếm văn bản đơn giản như

mô hình không gian vector. Đây cũng là cơ sở cho việc tiếp tục xây dựng và đánh

giá tính hiệu quả của các kỹ thuật nâng cao tìm kiếm sau này.

Do sự eo hẹp về thời gian cũng như hạn chế về tài liệu và trình độ lập trình

còn yếu kém nên bản luận văn chưa thể đi sâu vào việc xây dựng và cài đặt một

chương trình thử nghiệm áp dụng kỹ thuật nâng cao trong tìm kiếm văn bản theo nội

dung như mong muốn.

2. HƯỚNG PHÁT TRIỂN

Đây là một đề tài có tính thực tế cao. Với nhiệm vụ là nghiên cứu, luận văn

đã đáp ứng được một số yêu cầu cơ bản đặt ra.Tuy nhiên để áp dụng kỹ thuật nâng

cao tìm kiếm vào một chương trình ứng dụng cụ thể cho người sử dụng thì đòi hỏi

phải có thêm thời gian nghiên cứu không chỉ với các kỹ thuật tìm kiếm mà còn một

số kỹ thuật khác liên quan đến việc truy tìm sao cho đạt hiệu quả tốt nhất. Do đó

hướng phát triển của luận văn như sau:

 Thêm chức năng tự thu thập tài liệu định kì và tự động cập nhập chỉ

mục;

 Cài đặt chương trình tìm kiếm văn bản sử dụng kỹ thuật nâng cao;

- 84 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

 Phát triển ứng dụng có áp dụng kỹ thuật nâng cao tìm kiếm để cung

cấp một bộ máy tìm kiếm hiệu quả cho người sử dụng (cụ thể là áp

dụng vào hệ thống thư viện số).

- 85 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

TÀI LIỆU THAM KHẢO

Tiếng Việt

[1] Đặng Văn Đức (2004/2005), “Multimedia Database Management System”

Chương 1,Chương 4, Chương 9.

[2] Đặng Văn Đức (2007), “Nâng cao hiệu năng MMDMS (Multimedia Database

Management System)”, Bài 8.

Tiếng Anh

[1] Guojun Lu, “Multimedia Database Management Systems”, Artech House,

Boston, London, 1999.

[2] Subrahmanian V.S., “Principles of Multimedia Database Systems”, Morgan

[3] David Hand, Heikki Mannila, Padhraic Smyth, Principles of Data Mining, A

Bradford Book The MIT Press Cambridge, Massachusetts LondonEngland, 2001.

[4] Xu, Feilong, Latent Semantic Indexing.

Kaufmann Publishers, Inc., California, 1998.

[5] Witten I.H, Moffat A., Bell C.T., “Managing Gigabytes, Compressing and

Indexing Documents and Images”, Second Edition, Morrgan Kaufman Publishers,

1999.

[6] Theory of Information Retrieval, Florida State University LIS-5263 (Fall,

2003): “Vector Model Information Retrieval”, Written by Rich Ackerman,

September 25. 2003.

[7] Thomas K Lundauer,Peter W. Foltz,Darrel Laham, “Introduction to Latent

Semantic Analysis”.

[8] Karl Aberer(2003/4), EPFL-SSC, “Latent Semantic Indexing”, Tr 36-67. [9] Deerwater, Dumais, Furnas, Landauer, Harshman, “Latent Semantic Indexing” Website

[1] Từ điển bách khoa toàn thư: http://vi.wikipedia.org.

[2] Trang http://www.miislita.com

[3] Trang mã nguồn mở:

http://www.codeProject.com

http://www.SourceForge.com

- 86 - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn