2
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ THU TRANG KỸ THUẬT TÌM KIẾM VĂN BẢN TRÊN CƠ SỞ NỘI DUNG
TRONG CƠ SỞ DỮ LIỆU ĐA PHƯƠNG TIỆN

Ngành: Công nghệ Thông tin
Chuyên ngành: Hệ thống Thông tin
Mã số: 60 48 05
LUẬN VĂN THẠC SỸ
1.1.3 Mô hình dữ liệu đa phương tiện 13
1.2 Trích chọn đặc trưng, chỉ mục và đo tính tương tự [1] 14
1.2.1 Trích chọn đặc trưng 15
1.2.2 Chỉ số hóa cấu trúc 16
1.2.3 Đo tính tương tự 17
1.3 Hệ thống truy tìm thông tin (IR-Information retrieval) [1] [3] [4] [9] [13] 17
1.3.1 Khái quát 17
1.3.2 Vấn đề truy tìm tài liệu văn bản (Text retrieval) 18
1.3.3 Phân biệt các hệ thống IR và DBMS (DataBase Manager System) 20
1.4 xếp hạng tài liệu (Ranking) [1] [8] 21
CHƢƠNG 2- MỘT SỐ KỸ THUẬT TÌM KIẾM 25
2.1 Các truy vấn Boolean và chỉ mục tài liệu [1] [5] [11] 25
2.1.1 Truy vấn Boolean 25
2.1.2 Cấu trúc tệp 26
2.1.3 Các từ dừng và từ gốc 27
2.1.4 Chỉ số hoá và bổ sung 28
2.1.5 Kỹ thuật nén chỉ số (index compression) 29
2.1.6 Chỉ mục tự động 31
2.2 Thước đo hiệu năng [1] [5] [8] 33
2.3 Mô hình truy tìm không gian vectơ [1] [11] 36
2.4 Mô hình truy tìm theo xác suất [1] [6] 37
2.5 Mô hình truy tìm trên cơ sở cụm [1] [6] 38
2.6 Kỹ thuật phản hồi phù hợp [1] [11] 39
2.7 Mô hình LSI (Latent semantic indexing) [1] [5] [6] [7] [8] [9] 40
2.7.1 Ý tưởng cơ bản của LSI 40 4
2.7.2 Một số khái niệm cơ bản 42
2.7.3 Kỹ thuật SVD (singular value decomposition) 43

5
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

Ký hiệu viết tắt
Tiếng Anh
Tiếng Việt
CSDL
DataBase
Cơ sở dữ liệu
DBMS
DataBase Manager System
Hệ quản trị Cơ sở dữ liệu
IDF
Inverse Document Frequency
Tần số xuất hiện tài liệu
IR
Information retrieval
Truy tìm thông tin
LSI
Latent Semantic Indexing
Chỉ số hóa ngữ nghĩa ẩn
MIRS
Multimedia Information Retrieval
System
Hệ thống truy tìm thông tin đa
phương tiện
SVD


6
DANH MỤC CÁC BẢNG

Bảng 1.1 Ma trận tài liệu - thuật ngữ 23
Bảng 1.2 Ma trận kết quả tài liệu - thuật ngữ TF-IDF 24
Bảng 1.3 Kết quả khoảng cách từ truy vấn Q với các tài liệu 24
Bảng 2.1 Kết quả recall và precision 35
Bảng 2.2 Số lần xuất hiện của thuật ngữ trong mỗi tài liệu 44
7
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ

Hinh 1.1 Mô hình dữ liệu đa phương tiện 14
Hình 1.2 Hệ thống IR tiêu biểu 19
Hình 1.3 Tiến trình truy vấn tài liệu 21
Hình 2.1 Sơ đồ duy trì các chỉ số trong tập hợp động 29
Hình 2.2 Mô tả recall 33
Hình 2.3 Mô tả Precision 34
Hình 2.4 Đồ thị so sánh hiệu năng 35
Hình 2.5 Sử dụng các khái niệm cho truy vấn 41
Hình 2.6 Biểu đồ 2-D của 12 thuật ngữ và 9 tài liệu từ tập mẫu 45
Hình 2.7 Sơ đồ SVD của một ma trận hình chữ nhật thuật ngữ- tài liệu 46
Hình 2.8 Sơ đồ của SVD được giảm lược của một ma trận thuật ngữ-tài liệu 47
Hình 2.9 Đồ thị Recall – Precision của thuật toán LSI 53
Hình 3.1 Sơ đồ chức năng 55
Hình 3.2 Chức năng thêm tài liệu 56
Hình 3.3 Chức năng xóa tài liệu 56

Ngày nay, sự phát triển nhanh chóng của lĩnh vực thông tin và Internet đã tạo ra
một khối lượng thông tin vô cùng lớn với sự phong phú, đa dạng và phức tạp của loại
hình thông tin như: văn bản, hình ảnh, video, siêu văn bản, đa phương tiện… Tương
ứng với khối lượng dữ liệu khổng lồ đó, người ta quan tâm nhiều đến cơ sở dữ liệu đa
phương tiện (Mutimedia Database) trong khoa học công nghệ và trong thực tiễn. Với
hệ thống cơ sở dữ liệu đa phương tiện, bao gồm dữ liệu dạng hình ảnh, video, audio và
văn bản (text) đang có xu thế thâm nhập vào rất nhiều lĩnh vực và đang dần trở thành
hệ cơ sở dữ liệu được quan tâm từ người sử dụng và các chuyên gia trong vấn đề lưu
trữ, xử lý và ứng dụng.
Cho đến nay, vấn đề tìm kiếm thông tin đa phương tiện vẫn được các chuyên
gia nghiên cứu, trong việc truy tìm thông tin phù hợp với yêu cầu của một truy vấn đưa
ra từ người sử dụng. Người sử dụng có xu hướng tìm kiếm chủ yếu trong hệ cơ sở dữ
liệu đa phương tiện, ví dụ như tìm kiếm một loạt hình ảnh cổ vật liên quan đến nền văn
hoá cổ Việt Nam, tìm kiếm dữ liệu âm thanh có bản text kèm theo, tìm kiếm video bài
giảng cho học sinh ôn thi đại học Để thực hiện được việc tìm kiếm đó trong cơ sở dữ
liệu đa phương tiện thì những người làm khoa học đã nghiên cứu ra các công cụ, 9
phương pháp, kỹ thuật tìm kiếm sao cho thuận tiện, chính xác và nhanh chóng đem lại
được thông tin phù hợp với yêu cầu của người sử dụng.
Văn bản là một trong số các dạng của dữ liệu đa phương tiện, nó được quan tâm
từ hàng nghìn năm trước trong việc tổ chức sắp xếp và lưu trữ, điển hình như bảng nội
dung của một cuốn sách. Ngày nay, sự lớn mạnh của thông tin với phần lớn là dạng
văn bản, hơn nữa nó xuất phát từ nhu cầu thực tế sử dụng của con người. Tài liệu văn
bản chiếm đa số trong mọi cơ quan tổ chức, đặc biệt là trong thư viện và còn được sử
dụng để mô tả các dạng khác của dữ liệu đa phương tiện như video, audio, hình ảnh.
Số lượng tài liệu văn bản ngày càng lớn và có vai trò vô cùng quan trọng, vì thế việc
việc lưu trữ, xử lý và truy tìm thủ công trước đây không thể hoặc khó có thể thực hiện
được. Cùng với sự ra đời và phát triển của máy tính, các công cụ xử lý cũng ngày càng

liệu trả lời. Đánh giá chất lượng IR còn phụ thuộc vào thước đo hiệu năng thực hiện
của kỹ thuật đó dựa vào các tham số chủ yếu là độ chính xác (precison) và số tài liệu
được gọi lại (recall).
Trên cơ sở đó, cấu trúc luận văn gồm phần mở đầu, kết luận, tài liệu tham khảo
và phần nội dung gồm ba chương và được trình bày theo thứ tự sau:
Chương 1. Giới thiệu tổng quan về cơ sở dữ liệu đa phương tiện, xếp hạng tài
liệu và các yếu tố cơ bản phục vụ cho việc tìm kiếm thông tin. Khái quát về một hệ
thống truy tìm thông tin (IR) tiêu biểu và cụ thể là truy tìm tài liệu văn bản.
Chương 2. Đề cập đến vấn đề chỉ mục tài liệu và thước đo hiệu năng. Nghiên
cứu một số mô hình tìm kiếm như: Boolean, không gian vectơ, phân cụm, dựa trên xác
suất, phản hồi phù hợp và LSI.
Chương 3. Cài đặt thực nghiệm mô hình LSI.
Nội dung luận văn đi từ tổng quan về cơ sở dữ liệu đa phương tiện, hệ thống
tìm kiếm đa phương tiện đến kỹ thuật chỉ mục, xử lý tài liệu, trích lọc thông tin đến chi
tiết vấn đề tìm kiếm trên tài liệu văn bản. Đặc biệt, nghiên cứu các mô hình tìm kiếm
và đi sâu nghiên cứu mô hình LSI- tìm kiếm văn bản trên cơ sở nội dung. 11
CHƢƠNG 1 - TỔNG QUAN

1.1 Khái quát về cơ sở dữ liệu (CSDL) đa phƣơng tiện [1] [10] [12]
1.1.1 Giới thiệu
Trên thế giới tồn tại một lượng rất lớn dữ liệu số, các dữ liệu từ tivi, internet,
qua phương tiện truyền thông hay có được từ nhiều phương tiện khác nhau như máy
quay (video) kỹ thuật số Các dòng dữ liệu số càng ngày càng tăng, các loại dữ liệu
đa phương tiện kết hợp của dữ liệu hình ảnh, âm thanh, văn bản…
Hiện nay, chúng ta đều biết internet đang được phát triển như thế nào, rõ ràng
trong quá trình tương tác và trao đổi thông tin, người sử dụng có xu hướng chủ yếu xử
lý trên kiểu dữ liệu đa phương tiện và chúng ta thấy được sự phát triển của kiểu dữ liệu

thể thiếu của các công việc trong nhiều cụm kinh tế. Ví dụ: phân tích hệ thống thông
tin đa phương tiện sử dụng để giám sát, thu thập chứng cớ tòa án và an ninh chung…
Việc phát sinh khối kiến thức đa phương tiện và kiến thức kỹ thuật được dùng để lưu
trữ việc tạo hình ảnh, phim và âm thanh có thể được sử dụng trong di sản văn hóa và
nền công nghiệp giải trí
Có rất nhiều định nghĩa khác nhau về CSDL đa phương tiện: Theo nghiên cứu
EURESCOM thì CSDL đa phương tiện là một CSDL có hiệu năng cao, sức chứa lớn
với khả năng hỗ trợ các kiểu dữ liệu đa phương tiện cũng như các kiểu dữ liệu chữ số
cơ bản khác và nó có thể quản lý một khối lượng rất lớn thông tin đa phương tiện.
Dữ liệu âm thanh (audio data): Tín hiệu âm thanh bao gồm tiếng nói, âm nhạc,
tiếng động và mọi sự kết hợp các âm thanh khác nhau. Việc lưu lại một bài diễn
thuyết, một cuộc đàm thoại, các đoạn audio theo một chủ đề nào đó có ý nghĩa rất lớn
trong thực tế. Ví dụ, qua đài phát thanh chúng ta có thể thu thập được nhiều thông tin
với các chủ đề khác nhau, có thể tìm kiếm các bài hát trên internet, thu thập các đoạn
audio bài giảng trong đào tạo từ xa, học ngoại ngữ qua các đoạn audio
Dữ liệu hình ảnh (image data): Dữ liệu ảnh có thể được dùng để lưu trữ dấu
vân tay, nhận dạng khuôn mặt trong điều tra tội phạm; ảnh thẻ trong quản lý nhân sự;
trong những yêu cầu lưu lại hình ảnh như dữ liệu ảnh cổ vật, hiện tượng thiên nhiên,
trái đất… Hơn nữa, trong y học cần có một cơ sở dữ liệu ảnh để có thể truy vấn các
triệu trứng để tìm ra những căn bệnh tương tự không chỉ bằng văn bản mà bằng cả
hình ảnh, ảnh chụp X quang, ảnh chụp cắt lớp Trong thời gian gần đây, việc sử dụng
CSDL ảnh đã mang lại hiệu quả to lớn trong nhiều lĩnh vực khác nhau của đời sống,
kinh tế và xã hội.
Dữ liệu video (video data): Video giống như một tập các hình ảnh ở các thời
điểm được sắp xếp, biểu diễn theo một chuỗi thời gian nhất định. Trên thực tế chính là
chuyển động của các điểm ảnh từ trạng thái này sang trạng thái khác, hay là sự chuyển
động của mỗi đối tượng riêng lẻ được phân tách từ dữ liệu video. Dữ liệu video được
ứng dụng nhiều trong công nghệ giải trí (phim ảnh, clip âm nhạc ), trong đào tạo từ xa
(qua những video bài giảng) Nhiều phòng chức năng có nhiệm vụ lưu trữ và thu thập
các video (tư liệu lịch sử, tư liệu khai quật khảo cổ học của địa phương hay quốc gia )

Mô hình dữ liệu MIRS (Multimedia Information Retrieval System) hình thành
trên nền tảng nguyên tắc hướng đối tượng và phân cấp đa tầng.
Tầng đối tượng
Đối tượng bao gồm một hay nhiều mục media với các quan hệ không gian và
thời gian xác định, như với một đối tượng đa phương tiện là một trang bao gồm một
vài hình ảnh và âm thanh kèm theo.
Nhiệm vụ mấu chốt là làm thế nào để chỉ ra các quan hệ không gian và thời
gian. Quan hệ không gian được đặc tả bởi kích thước và vị trí cửa sổ hiển thị của mỗi
mục. Phương pháp chung đặc tả thời gian là đặc tả trên cơ sở trục thời gian, trong đó
thời gian bắt đầu và độ dài mỗi mục được xác định trên cơ sở đồng hồ chung. Phương
pháp khác là mô hình điều khiển theo sự kiện. 14

Hinh 1.1 Mô hình dữ liệu đa phương tiện
Tầng loại media
Tầng này bao gồm các loại media như văn bản, hình ảnh, audio và video. Các
loại này được suy diễn từ lớp media trừu tượng chung.
Tại mức này, các đặc trưng và thuộc tính được đặc tả. Ví dụ loại media ảnh:
kích thước, biểu đồ màu, các đối tượng chính chứa trong nó được đặc tả. Các đặc
trưng này được sử dụng trực tiếp vào tìm kiếm và tính toán khoảng cách.
Tầng khuôn mẫu media
Tầng này đặc tả khuôn mẫu, trong đó dữ liệu được lưu trữ. Thông thường,
media có nhiều khuôn mẫu, ví dụ ảnh có thể là nén hay ảnh thô. Hơn nữa có rất nhiều
kỹ thuật và chuẩn nén khác nhau. Thông tin chứa trong tầng này được sử dụng để giải
mã, phân tích và trình diễn.
Các nhiệm vụ khác
Chú ý rằng, các ứng dụng khác nhau có thể cần các mô hình dữ liệu khác nhau.
Tuy nhiên nhiều ứng dụng cùng chia sẻ mô hình cơ sở chung, nếu được thiết kế tốt thì

media

15
truy vấn cũng được trích chọn theo cùng cách thức nếu nó không được xác định rõ
ràng trước. Hệ thống tìm kiếm các items trong CSDL với các thuộc tính và đặc trưng
tương tự trên cơ sở thước đo tính tương tự nhất định. Để tìm kiếm hiệu quả, các đặc
trưng và thuộc tính phải được tổ chức thành các cấu trúc có chỉ mục.
1.2.1 Trích chọn đặc trưng
Các mục thông tin đa phương tiện trong CSDL được tiền xử lý để trích chọn
đặc trưng và thuộc tính.
Trong tiến trình tìm kiếm, các đặc trưng và thuộc tính này được so sánh thay
cho chính các mục thông tin. Do vậy, chất lượng của trích chọn đặc trưng xác định
hiệu quả tìm kiếm. Nếu đặc trưng không được tách ra từ item thì không thể tìm thấy
chúng từ CSDL theo đặc trưng đó. Đó là một trong sự khác biệt lớn nhất giữa MIRS
và DBMS. Trong DBMS thì mọi thuộc tính là có sẵn và đầy đủ, trong khi đó các đặc
trưng và thuộc tính phải được trích chọn theo loại truy vấn và thường là không đầy đủ
trong MIRS.
Trích chọn đặc trưng phải thỏa mãn các yêu cầu sau:
 Đặc trưng và thuộc tính trích chọn phải đầy đủ nhất có thể để biểu diễn nội
dung của các mục thông tin.
 Các đặc trưng phải được trình diễn và lưu trữ một cách chặt chẽ, mạch lạc. Mục
đích của việc trích chọn đặc trưng không phải là các đặc trưng phức tạp và đặc
trưng lớn, quan trọng là nó phải có khả năng tìm kiếm và so sánh nhanh các
mục thông tin với nhau.
 Tính toán khoảng cách giữa các đặc trưng phải hiệu quả, nếu không thời gian
đáp ứng của hệ thống rất lớn.
Tổng thể có 4 mức đặc trưng và thuộc tính như sau:

diễn giải liên quan đến con người. Hiện tại, tiến trình nhận dạng và diễn giải được thực
hiện bán tự động.
Việc truy vấn trên cơ sở hai loại đặc trưng nội dung mức thấp và mức cao gọi là
truy vấn trên cơ sở nội dung. Một hệ thống cần sử dụng toàn bộ bốn mức đặc trưng sao
cho hỗ trợ được các câu truy vấn mềm dẻo của người sử dụng. Các kỹ thuật này hỗ trợ
nhau để hình thành mô tả đầy đủ về đối tượng. Ví dụ, mô tả văn bản tốt cho việc thu
thập các khái niệm trừu tượng như cảm giác (vui, buồn ) nhưng không có khả năng
mô tả mẫu dữ liệu đầy đủ về các hình dạng không đều hay texture. Mặt khác, các đặc
trưng nội dung mức thấp có thể thu thập các mẫu dữ liệu này nhưng không mô tả được
các khái niệm trừu tượng.
Khi đối tượng đa phương tiện có nhiều kiểu media, các quan hệ và tương tác
giữa các media phải được sử dụng để trích chọn đặc trưng, diễn giải và truy tìm. Có
một vài kiểu media dễ hiểu và dễ diễn giải hơn vài kiểu khác. Việc áp dụng sự hiểu
biết có được về một hay vài kiểu nào đó, giúp ta hiểu và trích chọn đặc trưng cho các
kiểu khác. Ví dụ, nếu đối tượng đa phương tiện bao gồm rãnh hình (video) và rãnh
tiếng, ta có thể áp dụng nhận dạng tiếng nói để lấy ra tri thức về đối tượng và sử dụng
tri thức này để phân đoạn, trích chọn các đặc trưng và đối tượng trên rãnh hình
(video).
1.2.2 Chỉ số hóa cấu trúc
Sau khi trích chọn đặc trưng, chúng ta phải chỉ số hóa cấu trúc để tổ chức các
đặc trưng sao cho truy vấn được hiệu quả. Như đã biết, phải cần rất nhiều đặc trưng và
nhiều tham số để trình diễn. Ví dụ, phân bổ màu thường được biểu diễn bằng biểu đồ
với nhiều bins màu khác nhau. 17
Chỉ số hóa trong MIRS phải là phân cấp và nhiều mức:
 Mức cao nhất là phân lớp ứng dụng.
 Mức chỉ số hóa thứ hai hình thành trên các mức đặc trưng khác nhau. Các đặc
trưng khác nhau cần chỉ số hóa khác nhau.

hiện được. Người sử dụng hoặc không có thời gian hoặc không muốn tiêu phí thời gian
đọc toàn bộ tập hợp tài liệu, trừ khi anh ta không theo quy luật tự nhiên. 18
Khi những chiếc máy tính tốc độ cao sẵn sàng cho công việc không thuộc số
hóa (non-numerical), nhiều người cho rằng một máy tính có thể đọc toàn bộ tập hợp
tài liệu để trích lọc những tài liệu có liên quan. Hiển nhiên rằng, vấn đề về sử dụng
ngôn ngữ tự nhiên trong một tài liệu không chỉ là đầu vào (input) và kho lưu trữ mà
còn vấn đề về tri thức, thuộc đặc trưng nội dung tài liệu chưa được giải quyết. Có thể
hy vọng sự phát triển trong tương lai có thể tạo đầu vào (input) và kho ngôn ngữ tự
nhiên khả thi hơn. Các phần mềm đang cố gắng tự động hóa trong việc “sao” lại quá
trình “đọc” của con người, quả thực đó là một vấn đề hết sức khó khăn. Khó khăn hơn,
việc “đọc” bao gồm việc rút trích thông tin, cú pháp và ngữ nghĩa từ văn bản và sử
dụng nó để quyết định xem là mỗi tài liệu có liên quan hay không đến một yêu cầu cụ
thể. Nghĩa là, khó khăn không chỉ là làm thế nào để rút trích thông tin mà còn làm sao
để sử dụng nó quyết định sự phù hợp.
“Sự phù hợp”, đó là khái niệm trung tâm của truy tìm thông tin. Mục đích của
một chiến lược truy tìm tự động là truy tìm tất cả các tài liệu phù hợp ở cùng thời điểm
truy tìm, có thể bao gồm một vài tài liệu không thỏa mãn. Tìm ra các đặc trưng của tài
liệu để khi tài liệu phù hợp với truy vấn, nó cho phép tài liệu được truy tìm để trả lời
truy vấn. Khi chỉ mục được làm tự động, nó được giả thiết bằng việc đưa tài liệu văn
bản và câu truy vấn vào cùng bộ phân tích tự động, output sẽ là biểu diễn nội dung của
chúng và nếu tài liệu là phù hợp với truy vấn thì một thủ tục tính toán sẽ cho thấy điều
này.
Truy tìm dựa trên cơ sở nội dung (Content- based retrieval): Người sử dụng có
thể chỉ rõ các điều kiện lựa chọn dựa trên những nội dung của các đối tượng đa
phương tiện. Ví dụ, người sử dụng tìm kiếm ảnh, sử dụng truy vấn như: “Tìm tất cả
các ảnh giống với ảnh này” và “Tìm tất cả các ảnh chứa ít nhất 3 máy bay”. Các hình
ảnh được thêm vào cơ sở dữ liệu, DBMS (DataBase Manager System) phải phân tích

truy vấn mọi tài liệu 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.
Một hệ thống truy tìm thông tin tiêu biểu
Một hệ thống IR tiêu biểu được minh hoạ bằng phương pháp hộp đen. Gồm ba
thành phần: input, bộ xử lý và output.
Bắt đầu với đầu vào (input), vấn đề chính ở đây là có được biểu diễn của tài liệu
và truy vấn thích hợp qua máy tính. Có thể nói, các hệ thống truy tìm hầu hết dựa trên
máy tính với việc chỉ lưu trữ biểu diễn đặc trưng của tài liệu (hoặc truy vấn), có nghĩa
là một tài liệu văn bản không được sử dụng nữa khi nó đã được xử lý để đưa ra các đặc
trưng. Ví dụ, một biểu diễn đặc trưng tài liệu có thể là một danh sách các từ được xem
là quan trọng được trích ra.

Hình 1.2 Hệ thống IR tiêu biểu
Khi một hệ thống truy tìm trực tuyến (on-line), người sử dụng có khả năng thay
đổi yêu cầu trong một phiên tìm kiếm ở trạng thái truy tìm mẫu, do đó hy vọng cải 20
thiện được quá trình truy tìm xảy ra sau. Một thủ tục như vậy thông thường cho phép
phản hồi (Feedback).
Hơn nữa, bộ xử lý, một phần của hệ thống truy tìm có liên quan tới quá trình
truy tìm. Bộ xử lý có thể bao gồm cấu trúc thông tin theo cách thích hợp nào đó, giống
như phân loại. Trên thực tế, nó cũng bao gồm cả việc biểu diễn chức năng truy tìm, đó
là thực hiện chiến lược tìm kiếm câu trả lời cho một truy vấn. Trong biểu đồ, các tài
liệu được đặt vào một ô riêng biệt để nhấn mạnh thực tế là không có đầu vào (input) rõ
ràng nhưng có thể sử dụng trong suốt quá trình truy tìm.
Cuối cùng, chúng ta xét đến đầu ra (output) thường là một tập trích dẫn hoặc
các tài liệu. Trong một hệ thống hoạt động, đây là phần còn lại. Tuy nhiên, một hệ
thống thực nghiệm có thể cho phép thực hiện việc đánh giá.
1.3.3 Phân biệt các hệ thống IR và DBMS (DataBase Manager System)


Hình 1.3 Tiến trình truy vấn tài liệu
Bên phải hình 1.3 chỉ ra 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.
Bên trái hình 1.3 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 câu truy vấn. 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. Sau đó, 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à có ích. Một hệ thống IR tốt cho phép người sử dụng cung cấp phản hồi
về sự thích hợp của tập tài liệu kết quả 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, đại diện tài liệu. Phiên 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 đã được hiệu chỉnh. Nếu
cần, tiến trình phản hồi truy tì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.
1.4 xếp hạng tài liệu (Ranking) [1] [8]
Một máy tìm kiếm có thể cho lại tới hàng vài nghìn tài liệu phù hợp, nhưng một
người sử dụng thông thường sẽ chỉ có thể xem xét được một số lượng nhỏ các tài liệu
tìm được đó. Vì thế, xếp hạng các tài liệu phù hợp theo mức độ tương thích với người
dùng là một vấn đề quan trọng, cũng là tiêu điểm trong việc đánh giá một phương
pháp truy tìm.
Chỉ qua một phần thông tin của người sử dụng được trích lọc biểu thị qua truy
vấn, hệ thống sẽ tìm kiếm và trả lời bằng một tập các tài liệu phù hợp. Yêu cầu đó
Câu truy vấn
Tài liệu văn bản
Đại diện câu
truy vấn
Đại diện tài
liệu
Xử lý
Xử lý

ngữ xuất hiện thường xuyên trong các tài liệu thì nó chưa chắc đã 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
các tài liệu khác, tức là số lượng tài liệu được truy tìm lớn nhưng độ chính xác không
cao. IDF giúp cải thiện vấn đề này, trọng số của thuật ngữ sẽ rất cao nếu nó xuất hiện
thường xuyên chỉ trong một vài tài liệu, tức là giúp tăng cường sự phân biệt.
Cho D
i
= (d
i1
, d
i2
, …, d
iM
) là tập hợp các tài liệu, với truy vấn Q biểu diễn như
một tài liệu. Trong đó, d
ij
là trọng số thuật ngữ j trong tài liệu i, Q(j) biểu thị trọng số
của thuật ngữ j trong truy vấn Q (i =1, 2 , N; j = 1, 2, , M). Các trọng số d
ij
và Q(j) có
thể là 1 (nếu chứa thuật ngữ) hay 0 (nếu không chứa thuật ngữ) trong đại số quan hệ;
hoặc tính bằng TF-IDF hoặc có thể bằng nhiều cách khác. Tài liệu D
i
được đánh giá là
“gần” với truy vấn Q dựa vào thước đo sau:
1. Khoảng cách thuật ngữ (term distance):
2
1
))((


23
Trong trường hợp xấu nhất, cần đến O(N) phép so sánh, mỗi so sánh cho một
tài liệu và mỗi so sánh cần O(M) thời gian cho từng thuật ngữ. Vậy, sẽ cần O(M×N)
thời gian để tìm giải pháp tốt nhất. Kỹ thuật chỉ số ngữ nghĩa tiềm tàng (LSI) sẽ làm
giảm đáng kể thời gian nói trên.
Xét ví dụ, với 10 tài liệu (ký hiệu: d1, d2, , d10); và 6 thuật ngữ (ký hiệu: t1, t2,
, t6). Trong đó:
t1 = database t2 = SQL t3 = index
t4 = regression t5 = likelihood t6 = linear
Ta sẽ lập được một ma trận tần số tài liệu - thuật ngữ M (106), trong đó mỗi
phần tử ij (hàng i, cột j) chứa số lần xuất hiện của thuật ngữ j trong tài liệu i.

t1
t2
t3
t4
t5
t6
d1
24
21
9
0
0
3
d2
32

18
7
16
d7
0
0
1
32
12
0
d8
3
0
0
22
4
2
d9
1
0
0
34
27
25
D10
6
0
0
17
4

0
0
0
4.53
21.48
10.21
0
1.07
0
0.63
0
0
11.78
1.42
15.94
0.21
0
0
22.18
4.28
0 24
0.31
0
0
15.24
1.42
1.38

0.79
0.43
d6
0.14
0.02
d7
0.06
0.01
d8
0.02
0.02
d9
0.09
0.01
d10
0.01
0.00
Bảng 1.3 Kết quả khoảng cách từ truy vấn Q với các tài liệu
Kết quả tính được xếp hạng các tài liệu theo mức độ phù hợp. Kết quả trên cho
thấy, sử dụng ma trận TF tài liệu d5 là “gần” nhất, còn với ma trận TF-IDF thì d2 được
xem là “gần” nhất. 25

CHƢƠNG 2. MỘT SỐ KỸ THUẬT TÌM KIẾM

Tất cả các chiến lược tìm kiếm được dựa vào việc so sánh giữa truy vấn với các
tài liệu được lưu trữ. Đôi khi, việc so sánh này chỉ là gián tiếp khi truy vấn được so
sánh với các cụm (hoặc chính xác hơn với những đặc điểm đại diện cho các cụm).

với toán tử AND. Câu truy vấn (term1 AND NOT term2) dẫn tới truy tìm bản ghi có 26
term1 nhưng không có term2.
2.1.2 Cấu trúc tệp
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
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 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 hợ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ệm cận này không hiệu quả vì mỗi lần truy vấn
thì toàn bộ tập hợp 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 truy tìm.
Cách sử dụng chung nhất là tệp mục lục (inverted). Đó là loại tệp chỉ mục.
Các tệp mục lục (Inverted Files)
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ỉ số
định danh (ID) bản ghi cho toàn bộ bản ghi chứa thuật ngữ này. Một đầu vào tệp mục
lục thông thường chứa từ khóa (thuật ngữ) và một số ID tài liệu. Mỗi từ khóa và các
ID tài liệu (mà nó chứa từ khóa) được tổ chức thành một hàng. Ví dụ tệp mục lục như
sau:
Term1: Record1, Record3
Term2: Record1, Record2
Term3: Record2, Record3, Record4
Term4: Record1, Record2, Record3, Record4