TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
__________________*___________________

ĐỒ ÁN

TỐT NGHIỆP ĐẠI HỌC
NGÀNH CÔNG NGHỆ THÔNG TIN

XÂY DỰNG HỆ THỐNG TÌM KIẾM TÀI
LIỆU DỰA TRÊN VỊ TRÍ

: Vũ Hà Dũng
Lớp Tin Pháp – K53
Giáo viên hướng dẫn : TS. Vũ Tuyết Trinh
Sinh viên thực hiện

HÀ NỘI, 5-2013


PHIẾU GIAO NHIỆM VỤ ĐỒ ÁN TỐT NGHIỆP
1. Thông tin về sinh viên:
Họ và tên sinh viên: Vũ Hà Dũng
Điện thoại liên lạc: 01679704032
Email:
Lớp: Tin Pháp K53
Hệ đào tạo: Chính quy
Đồ án tốt nghiệp được thực hiện tại: Phòng 702 tòa nhà B1, Viện Công nghệ Thông tin và
Truyền thông, Đại học Bách Khoa Hà Nội.
Thời gian làm ĐATN: Từ ngày 28/02/2013 đến ngày 15/05/2013
2. Mục đích nội dung của ĐATN: Tìm hiểu và triển khai kỹ thuật tìm kiếm thông tin văn

bản và thông tin vị trí. Xây dựng và cài đặt thử nghiệm một hệ thống tìm kiếm tài liệu dựa
trên vị trí.
3. Các nhiệm vụ cụ thể của ĐATN:
 Tìm hiểu cơ sở lý thuyết của tìm kiếm thông tin văn bản và tìm kiếm dựa trên vị trí.
 Đề xuất thuật toán đánh giá xếp hạng văn bản dựa trên cả từ khóa lẫn vị trí.
 Cài đặt, đánh giá hệ thống thử nghiệm.
4. Lời cam đoan của sinh viên:
Tôi – Vũ Hà Dũng – cam kết ĐATN là công trình nghiên cứu của bản thân tôi dưới sự
hướng dẫn của TS. Vũ Tuyết Trinh.
Các kết quả nêu trong ĐATN là trung thực, không phải là sao chép toàn văn của bất kỳ
công trình nào khác.
Hà Nội, ngày 15 tháng 05 năm 2013
Tác giả ĐATN

Vũ Hà Dũng
5. Xác nhận của giáo viên hướng dẫn về mức độ hoàn thành của ĐATN và cho phép bảo
vệ:
………………………………………………………………………………………………
………………………………………………………………………………………………
………………………………………………………………………………………………
Hà Nội, ngày
tháng
năm 2013
Giáo viên hướng dẫn

TS. Vũ Tuyết Trinh
1
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53



TÓM TẮT NỘI DUNG ĐỒ ÁN TỐT NGHIỆP
Ngày nay, cùng với sự phát triển của công nghệ thông tin, số lượng các tài liệu điện tử
cũng gia tăng từng ngày. Đến nay, số lượng các tài liệu được lưu trữ lên đến hàng tỷ trang.
Trong khi đó, nhu cầu khai thác trong kho tài liệu khổng lồ này để tìm kiếm những thông
tin cần thiết đang là nhu cầu thường ngày và thiết thực của người sử dụng. Vấn đề đặt ra là
làm thế nào khai thác được khối thông tin đó để nó trở nên có ích đối với người dùng. Bên
cạnh đó, vài năm gần đây, các thiết bị di động đã phát triển mạnh mẽ và trở nên phổ biến
với tất cả mọi người. Những thiết bị này không đơn thuần chỉ là một công cụ để liên lạc
nữa, mà khi được kết nối internet, nó đã mở ra nhiều tiềm năng phát triển cho các dịch vụ
có sử dụng vị trí của người dùng, trong đó có dịch vụ tìm kiếm dựa trên vị trí. Vì vậy, tôi
đã chọn đề tài “Xây dựng hệ thống tìm kiếm tài liệu dựa trên vị trí” để làm đồ án tốt nghiệp.
Mục đích của chúng tôi là tìm hiểu và triển khai kỹ thuật tìm kiếm thông tin văn bản và
thông tin vị trí. Chúng tôi sử dụng cấu trúc chỉ mục có thể kết hợp lập chỉ mục cả từ khóa
lẫn vị trí, đồng thời đưa ra giải thuật để có thể đánh giá xếp hạng các văn bản dựa trên cả
hai tiêu chí này.
Chúng tôi xây dựng một hệ thống tìm kiếm các tài liệu về lĩnh vực du lịch dựa trên thư
viện mã nguồn mở Lucene[7]. Trong phạm vi của đề tài này, chúng tôi giả sử các tài liệu
đó đã được gán nhãn địa điểm từ trước. Chúng tôi đưa ra ba mô hình tìm kiếm và cài đặt hệ
thống dựa trên cấu trúc chỉ mục cũng như thuật toán đề xuất, sau đó đánh giá so sánh kết
quả tìm kiếm dựa trên ba mô hình này.

2
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


MỤC LỤC
PHIẾU GIAO NHIỆM VỤ ĐỒ ÁN TỐT NGHIỆP
TÓM TẮT NỘI DUNG ĐỒ ÁN TỐT NGHIỆP
Chương 1: Đặt vấn đề
1.1 Tìm kiếm thông tin là gì?

1.2 Tại sao vị trí lại quan trọng trong tìm kiếm thông tin?
1.3 Mục đích và phạm vi của đề tài
1.4 Bố cục của đồ án
Chương 2: Cơ sở lý thuyết
2.1 Kiến trúc tổng quan của một hệ thống tìm kiếm thông tin
2.2 Tìm kiếm văn bản dựa trên từ khóa
2.2.1 Quá trình lập chỉ mục
2.2.2 Quá trình tìm kiếm
2.3 Tìm kiếm dựa trên vị trí
2.4 Thảo luận
Chương 3: Kỹ thuật tìm kiếm văn bản dựa trên vị trí
3.1 Phân tích yêu cầu hệ thống
3.2 Định hướng giải pháp
3.3 Kết hợp điểm từ khóa và điểm không gian
3.4 Các mô hình tìm kiếm văn bản dựa trên vị trí
3.4.1 Tìm kiếm vị trí rồi tìm kiếm từ khóa:
3.4.2 Tìm kiếm từ khóa và tìm kiếm vị trí:
3.4.3 Tìm kiếm từ khóa rồi tìm kiếm không gian:
3.5 Thuật toán
3.6 Bàn luận
Chương 4: Cài đặt thử nghiệm
4.1 Môi trường thử nghiệm
4.2 Cài đặt hệ thống
4.3 Kết quả thực nghiệm
Chương 5: Kết luận
5.1 Kết luận
5.2 Hướng phát triển của đồ án
Tài liệu tham khảo

1

2
7
7
8
8
8
9
9
10
10
11
13
16
18
18
19
19
20
20
21
21
22
23
24
24
25
26
28
28
28

29

3
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


DANH MỤC CÁC HÌNH VẼ
Hình 2-1: Kiến trúc tổng quan của một hệ thống IR
Hình 2-2: Mô tả một Inverted File
Hình 2-3: Hệ thống các tầng liên tiếp chia bề mặt trái đất thành các vùng
với kích thước nhỏ dần
Hình 2-4: Ô có tọa độ (57, 34) ở lớp thứ 8
Hình 2-5: Biểu diễn truy vấn q và các đối tượng d
Hình 3-1: Cấu trúc chỉ mục lai R*-tree-Inverted file [3]
Hình 3-2: Trộn hai danh sách với  = 0.5 và lấy k = 3 tài liệu có điểm cao
nhất
Hình 3-3: Minh họa quá trình tìm kiếm vị trí rồi tìm kiếm từ khóa
Hình 3-4: Minh họa quá trình tìm kiếm vị trí và tìm kiếm từ khóa
Hình 3-5: Minh họa quá trình tìm kiếm từ khóa rồi tìm kiếm vị trí
Hình 4-1: Mô tả quá trình tìm kiếm của hệ thống
Hình 4-2: Giao diện chính của hệ thống tìm kiếm
Hình 4-3: Kết quả tìm kiếm của một truy vấn

9
11
14
15
16
18
20

20
21
22
25
26
26

4
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


DANH MỤC CÁC BẢNG
Bảng 2-1: Tần số xuất hiện của term t trong truy vấn q và tài liệu d
Bảng 2-2: Độ tương tự về không gian giữa vị trí truy vấn với vị trí đối
tượng
Bảng 4-1: Thời gian và số lượng kết quả cho truy vấn “bảo tàng” và vị trí
“Hà Nội”
Bảng 4-2: Số lượng kết quả cho truy vấn “hang động” và vị trí “Hà Nội”

13
16
26
27

5
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ
STT


Từ viết tắt/Thuật ngữ

Giải thích ý nghĩa

1

IR

Truy xuất thông tin

2

Document

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

3

Query

Truy vấn

4

tf-idf

Con số thể hiện độ tương tự giữa truy vấn và văn bản về
mặt từ khóa


5

Lucene

Thư viện mã nguồn mở cho phép tìm kiếm trên văn bản

6

Inverted Files

Cấu trúc để lập chỉ mục theo từ khóa

6
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


Chương 1: Đặt vấn đề
1.1 Tìm kiếm thông tin là gì?
Cùng với sự phát triển của công nghệ thông tin, số lượng các tài liệu điện tử
cũng gia tăng từng ngày. Đến nay, số lượng các tài liệu được lưu trữ lên đến hàng tỷ
trang. Trong khi đó, nhu cầu khai thác trong kho tài liệu khổng lồ này để tìm kiếm
những thông tin cần thiết đang là nhu cầu thường ngày và thiết thực của người sử
dụng. Tuy nhiên, một trong những khó khăn con người gặp phải trong việc khai
thác thông tin là khả năng tìm chính xác thông tin họ cần trong kho tài liệu. Để trợ
giúp công việc này, các hệ thống tìm kiếm đã lần lượt được phát triển nhằm phục vụ
cho nhu cầu tìm kiếm của người sử dụng. Có thể lấy một vài ví dụ điển hình về
những hệ thống tìm kiếm theo từ khóa nổi tiếng như là Google, Bing, Yahoo!, …
Tuy nhiên, phần lớn các công cụ tìm kiếm này là những sản phẩm thương mại và
mã nguồn được giữ bí mật. Một vài hệ thống tìm kiếm trên máy tính cá nhân như
Windows Search, Google Desktop, … đã đáp ứng phần nào nhu cầu của người sử

dụng, miễn phí cho cá nhân, song cũng chỉ đáp ứng được trên phạm vi nhỏ. Điều
này dẫn tới kết quả là nhiều nhà phát triển riêng biệt hoặc các tổ chức sử dụng sẽ
phải tự mình xây dựng từ đầu một công cụ tìm kiếm nếu hệ thống của họ cần chức
năng tìm kiếm này. Một cách tiếp cận hiệu quả để giải quyết vấn đề này là sử dụng
các thư viện mã nguồn mở để xây dựng hệ thống tìm kiếm.
Tìm kiếm thông tin (Information Retrieval - IR) là tìm kiếm tài nguyên
(thường là các tài liệu) trên một tập lớn các dữ liệu phi cấu trúc (thường là văn bản)
được lưu trữ trên các máy tính nhằm thỏa mãn một nhu cầu về thông tin nào đó.
Mục đích của IR là trả lại cho người dùng một tập các thông tin thỏa mãn nhu cầu
của họ.
Một hệ thống IR là một chương trình phần mềm lưu trữ và quản lý thông tin
về các tài liệu. Hệ thống trợ giúp người dùng tìm kiếm thông tin họ cần. Chúng ta
định nghĩa rằng thông tin cần thiết là “câu truy vấn” (query) và các thông tin được
chọn là “tài liệu” (documents). Mục đích của một hệ thống IR là cho biết về sự tồn
tại và vị trí của các tài liệu có thể chứa thông tin cần thiết. Có thể một số tài liệu
được đề xuất sẽ thoả mãn nhu cầu thông tin của người dùng. Những tài liệu đó được
gọi là các tài liệu có liên quan. Một hệ thống IR hoàn hảo sẽ chỉ thu thập những tài
liệu có liên quan và bỏ qua những tài liệu không liên quan. Tuy nhiên, sẽ không thể
tồn tại những hệ thống như vậy bởi các câu lệnh tìm kiếm thường không đầy đủ và
độ liên quan (relevance) phụ thuộc vào ý kiến chủ quan của người dùng. Hai người
dùng có thể đưa ra cùng truy vấn giống nhau cho một hệ thống IR nhưng lại có cách
đánh giá độ liên quan khác nhau đối với các tài liệu được thu thập. Thực tế, mục
tiêu chính của một hệ thống IR là thu thập tất cả các tài liệu có liên quan tới một
truy vấn của người dùng đồng thời thu thập ít nhất có thể các tài liệu không liên
quan.
7
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


1.2 Tại sao vị trí lại quan trọng trong tìm kiếm thông tin?

Vài năm gần đây, các thiết bị di động đã phát triển mạnh mẽ và trở nên phổ
biến với tất cả mọi người. Những thiết bị này không đơn thuần chỉ là một công cụ
để liên lạc nữa, mà khi được kết nối internet, nó đã mở ra nhiều tiềm năng phát triển
cho các dịch vụ có sử dụng vị trí của người dùng, trong đó có dịch vụ tìm kiếm dựa
trên vị trí. Lấy ví dụ, bạn là một du khách nước ngoài tới Hà Nội, bạn muốn tìm
kiếm các tài liệu giới thiệu những quán ăn trong phạm vi thủ đô Hà Nội. Chỉ với
một thiết bị di động có kết nối internet, bạn sẽ nhập một truy vấn với nội dung là
“quán ăn” để tìm những tài liệu liên quan tới địa điểm bạn cần tìm. Nếu như với
một hệ thống IR bình thường, thì nó sẽ trả về tất cả các quán ăn không chỉ riêng ở
Hà Nội, mà có thể của nhiều tỉnh thành khác. Điều này là không cần thiết, và do đó
bạn sẽ phải mất thời gian để sàng lọc lại các kết quả được trả về. Tuy nhiên, với một
hệ thống IR dựa trên vị trí, nó sẽ nhận biết được vị trí hiện tại của bạn để có thể tìm
các địa điểm chính xác và phù hợp với yêu cầu hơn. Hệ thống sẽ ngầm hiểu ý định
của người dùng, và người dùng cũng không phải mất thời gian để nhập những dữ
liệu hiển nhiên về vị trí xung quanh họ, vì vị trí đã nói lên yêu cầu thông tin của bạn.
1.3 Mục đích và phạm vi của đề tài:
Mục đích của đề tài này là tìm hiểu và triển khai kỹ thuật tìm kiếm thông tin
văn bản và thông tin vị trí trên tập tài liệu đã được gán nhãn trước. Trên cơ sở đó
xây dựng một hệ thống tìm kiếm tài liệu về lĩnh vực du lịch. Hệ thống sẽ nhận đầu
vào là một câu truy vấn của người dùng (bao gồm cả từ khóa và vị trí), rồi sử dụng
thông tin vị trí để đưa ra các tài liệu có độ liên quan cao hơn cho người dùng. Hệ
thống sẽ kết hợp độ liên quan về từ khóa với độ liên quan về vị trí để trả về các tài
liệu với độ liên quan cao nhất với truy vấn của người dùng.
1.4 Bố cục của đồ án:
Phần còn lại của đồ án bao gồm 4 chương, với nội dung như sau:
Chương 2 trình bày cơ sở lý thuyết của tìm kiếm văn bản dựa trên từ khóa và không
gian.
Chương 3 trình bày kỹ thuật tìm kiếm văn bản dựa trên vị trí.
Chương 4 xây dựng hệ thống tìm kiếm và trình bày các kết quả thực nghiệm.
Chương 5 kết luận và hướng phát triển tiếp theo của đồ án.


8
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


Chương 2: Cơ sở lý thuyết
Trong chương này, chúng tôi sẽ trình bày cơ sở lý thuyết của quá trình tìm
kiếm văn bản dựa trên từ khóa và dựa trên vị trí. Quá trình tìm kiếm bao gồm hai
quá trình chính là lập chỉ mục và xếp hạng các các tài liệu trả về.
2.1 Kiến trúc tổng quan của một hệ thống tìm kiếm thông tin:

User query

Represent query

Resources
(Internet, …)

Crawling

Documents

Indexing
Searching
Index files

Results

Hình 2-1: Kiến trúc tổng quan của một hệ thống IR


Một hệ thống IR bao gồm ba thành phần chính:
 Thu thập tài liệu (Crawling): hệ thống sẽ thu thập tài liệu từ nhiều nguồn khác
nhau. Việc thu thập này có thể được thực hiện thủ công hoặc tự động (nhờ
một chương trình gọi là “web crawler”).
 Lập chỉ mục (Indexing): hệ thống sẽ phân tích và lập chỉ mục các tài liệu thu
thập được nhằm tăng tốc độ truy xuất trong quá trình tìm kiếm.
 Tìm kiếm (Searching): người dùng nhập vào câu truy vấn. Truy vấn này sẽ
được phân tích, xử lý và biểu diễn lại để tạo nên truy vấn thật sự mà hệ thống
có thể “hiểu” được. Sau đó, truy vấn đã được xử lý được sử dụng để thu thập
các tài liệu có chứa truy vấn. Các tài liệu này sẽ được xếp hạng (ranking) theo
mức độ liên quan và trả về cho người dùng.
9
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


Trong phạm vi của đồ án, chúng tôi giả sử các tài liệu đã được thu thập và gán
nhãn từ trước. Do đó, chúng tôi sẽ tập trung chính vào phần lập chỉ mục và tìm
kiếm.
2.2 Tìm kiếm văn bản dựa trên từ khóa:
2.2.1 Quá trình lập chỉ mục:
Mục đích của lập chỉ mục là tạo ra biểu diễn bên trong của thông tin trong
từng tài liệu.
Các tài liệu trước khi lập chỉ mục sẽ qua một giai đoạn gọi là tiền xử lý.
Những tài liệu này được tiền xử lý bằng một số phương pháp thao tác văn bản tự
động như loại bỏ khoảng trắng, phân tích từ vựng, loại bỏ từ dừng, … Phân tích từ
vựng là quá trình biến đổi các ký tự trong tài liệu thành một tập các từ được đề cử
để chọn làm từ chỉ mục bằng cách xử lý các chữ số, dấu nối, các ký hiệu chấm câu
và chữ viết hoa viết thường. Văn bản cần được chia thành các token sử dụng khoảng
trắng phân tách và các ký tự kết thúc câu. Loại bỏ từ dừng nhằm loại bỏ những từ
có tần suất xuất hiện cao trong hầu hết các tài liệu mà lại không mang nội dung có ý

nghĩa. Như vậy, quá trình tiền xử lý nhằm mục đích chắt lọc tập tài liệu để nhận
được tập các từ (term).
Tiếp theo là quá trình xây dựng chỉ mục (indexing) cho văn bản nhằm tăng tốc
độ truy nhập trong giai đoạn tìm kiếm. Có nhiều loại cấu trúc chỉ mục nhưng phổ
biến nhất là Inverted Files, trong đó tập tài liệu được biến đổi thành một tập các
term kèm theo một danh sách tương ứng các tài liệu chứa chúng và trọng số của
chúng trong mỗi tài liệu. Trọng số của một term trong một tài liệu là số lần xuất
hiện của chúng trong tài liệu. Tần số càng lớn thì tầm quan trọng của nó càng lớn.
Điều này được gọi là gán trọng số theo tần số từ (term frequency – tf).
Cấu trúc của Inverted File thường gồm một tệp từ điển (dictionary file) và một
tệp các posting (postings file). Một tệp từ điển chứa một tập các term, tổng số các
tài liệu mà nó xuất hiện và một con trỏ trỏ tới bản ghi các posting của nó. Tệp các
posting chứa thông tin về một term trong từng tài liệu mà nó xuất hiện. Thông tin
trong một bản ghi posting thường gồm: mã tài liệu, tần số của term trong tài liệu đó,
và một con trỏ trỏ tới posting tiếp theo của từ đó.
Hình vẽ dưới đây miêu tả quá trình tạo một Inverted File.

10
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


Hình 2-2: Mô tả một Inverted File

2.2.2 Quá trình tìm kiếm:
Quá trình tìm kiếm bao gồm hai bước chính là đối sánh từ và tính điểm xếp
hạng tài liệu.

Đối sánh từ: Yêu cầu thông tin của người dùng được phát biểu bằng một câu
truy vấn - là đầu vào của hệ thống IR. Ở bước đầu, hệ thống IR thực hiện các thao
tác xử lý đối với truy vấn của người dùng tương tự như đối với các tài liệu ban đầu

trong quá trình lập chỉ mục. Kết quả nhận được là một danh sách các term, đó chính
là biểu diễn bên trong của yêu cầu thông tin từ người dùng. Mỗi term thu được từ
thao tác xử lý văn bản được dùng để xác định, thông qua tập chỉ mục, một danh
sách các tài liệu mà trong đó nó xuất hiện. Nếu có nhiều từ xuất hiện trong truy vấn
thì bước tìm kiếm sẽ trả về hợp của các tài liệu thu thập được theo tất cả các từ hoặc
một số từ, tùy theo kiểu truy vấn. Tóm lại, tìm kiếm là quá trình đối sánh (matching)
các term trong các tài liệu với các term trong truy vấn.

11
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53



Tính điểm và xếp hạng tài liệu: Mọi tài liệu thu thập được sẽ được đánh giá
theo độ liên quan của chúng đối với truy vấn. Thông thường, đánh giá này phụ
thuộc vào một giải thuật xếp hạng, giải thuật này tính toán ra kết quả là một con số
thực cho từng tài liệu. Tài liệu ứng với một số giá trị càng lớn thì càng được xem là
có độ liên quan nhiều hơn. Tiếp theo, các tài liệu được thu thập sẽ được trả về theo
thứ tự giảm dần theo kết quả của giải thuật xếp hạng. Nhờ vậy, người dùng có cơ
hội để xem xét kỹ hơn các tài liệu liên quan nhất, nằm ở phần trên trong thứ tự sắp
xếp, so với các tài liệu không liên quan. Do đó, giải thuật xếp hạng được xem là
phần cốt yếu của một hệ thống IR.
Để đánh giá độ liên quan của các tài liệu với truy vấn, người ta sử dụng trọng
số tf-idf.
Tần số từ khóa - tf: Mỗi từ khóa trong một tài liệu được gán một trọng số, phụ
thuộc vào số lượng các thể hiện của từ khóa đó trong tài liệu. Phương pháp đơn giản
nhất là gán trọng số bằng với số lần xuất hiện của từ khóa t trong tài liệu d. Lược đồ
gán trọng số này được gọi là tần số xuất hiện từ khóa và ký hiệu là tft,d, với phần chỉ
số dưới biểu thị cho từ khóa và tài liệu. Tuy nhiên, nếu có n thể hiện của một term
trong một tài liệu thì cũng không thực sự có nghĩa là tài liệu đó có tầm quan trọng

gấp n lần so với một tài liệu khác chỉ chứa một thể hiện của term đó. Do vậy, đã có
những nghiên cứu đáng chú ý tập trung vào các hàm trọng số thay vì dựa vào số
lượng các thể hiện của một term. Trong đó, hàm loga khá phổ biến, hàm này gán
trọng số theo công thức:
.
Tần số tài liệu nghịch đảo - idf: Tần số từ khóa dạng thô nêu trên có nhược
điểm là tất cả các từ khóa đều được xem là quan trọng ngang nhau khi đánh giá độ
liên quan đối với một truy vấn. Mà thực tế thì có những từ khóa có ít hoặc không có
vai trò gì trong việc đánh giá này. Để giải quyết vấn đề này cần có một cơ chế để
làm giảm ảnh hưởng của một từ khóa, nếu nó xuất hiện quá nhiều lần trong bất kỳ
tài liệu nào, đối với quyết định về độ liên quan. Ý tưởng là sử dụng tần số tài liệu dft,
được định nghĩa là số lượng các tài liệu có chứa từ khóa t trong tập tài liệu. Tần số
tài liệu df của một từ khóa được sử dụng để tính trọng số của từ khóa đó. Ký hiệu
tổng số tài liệu trong một tập hợp là N, tần số idf (inverse document frequency) của
một từ khóa t được định nghĩa như sau:

. Do đó, tần số từ khóa của

một term ít xuất hiện thì cao trong khi tần số idf của một từ khóa xuất hiện nhiều sẽ
thấp.
Gán trọng số tf – idf:
Kết hợp các biểu thức tần số tf và idf để sinh ra trọng số kết hợp cho từng từ
khóa trong mỗi tài liệu. Lược đồ gán trọng số tf-idf gán cho từ khóa t một trọng số
12
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


trong tài liệu d theo công thức sau: 
. Như vậy, trọng số tfidft,d gán cho từ khóa t một trọng số trong tài liệu d có giá trị:
 lớn nhất khi t xuất hiện nhiều lần trong một số lượng nhỏ tài liệu

 thấp hơn khi t xuất hiện ít trong một tài liệu hoặc xuất hiện trong
nhiều tài liệu
 thấp nhất nếu t xuất hiện trong gần như tất cả các tài liệu.
Độ tương tự về từ khóa giữa truy vấn q và tài liệu d được đánh giá bởi công
thức sau:

Trên thực tế, trong quá trình tính toán, người ta có thể qua bỏ thành phần
vì với một truy vấn q cho trước, giá trị của nó là như nhau đối với mọi
tài liệu d.
Ví dụ, với truy vấn “quán ăn ngon” trên tập dữ liệu với N = 1000000 tài liệu,
tần số xuất hiện của ba mục từ “quán”, “ăn”, “ngon” như sau:
Term
Truy vấn q
Tài liệu d
dft
idft
tft, d
quán
50000
1.3
1
ăn
10000
2.0
1
ngon
1000
3.0
2
Bảng 2-1:Tần số xuất hiện của term t trong truy vấn q và tài liệu d


Điểm số

.

2.3 Tìm kiếm dựa trên vị trí:
Mục đích của việc tìm kiếm theo không gian là tìm tất cả đối tượng người
dùng quan tâm (chẳng hạn chùa chiền, công viên, rạp chiếu phim, …) gần khu vực
nơi mà truy cập đề cập đến, ví dụ như “tìm các quán ăn gần trường Đại học Bách
Khoa Hà Nội”.
Để có thể làm được điều này, giả sử mỗi một đối tượng đã được gắn với một
tọa độ duy nhất trên bề mặt trái đất, chính là vĩ độ (latitude) và kinh độ (longitude).
Bước đầu tiên, chúng ta “trải phẳng” địa cầu bằng cách sử dụng phép chiếu
trong toán học. Đây là công việc cần thiết để chúng ta có thể biểu diễn bất kỳ một
địa điểm nào trên bề mặt trái đất thành một điểm xác định trong hệ tọa độ hai chiều.
Quá trình này tương tự như việc chúng ta chiếu sáng vào trái đất và thu được hình
chiếu của nó trên mặt phẳng. Ta sẽ sử dụng phép chiếu sin (sinusoidal projection)
để làm điều này. Công thức của nó như sau:
13
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


với  là vĩ độ,

là kinh độ,

0

là kinh tuyến gốc


Như vậy, ứng với một vị trí trên bề mặt trái đất (vĩ độ, kinh độ) sẽ tương ứng với
một tọa độ (hoành độ, tung độ) trong hệ tọa độ hai chiều.
Bước tiếp theo, chúng ta sẽ tạo hệ thống lớp theo cấu trúc phân cấp cho hình
chiếu của bề mặt trái đất, được gọi là các lớp Đề-các (Cartesian tiers); mỗi lớp có số
lượng ô tăng lên. Số lượng ô của mỗi lớp là 2ID lớp x 2ID lớp. Hình vẽ dưới đây miêu tả
cho các lớp này. Ở lớp 0 (tier = 0) có 20 x 20 = 1 ô, lớp 1 (tier = 1) có 21 x 21 = 4 ô,
lớp 2 (tier = 2) có 22 x 22 = 16 ô, …

Hình 2-3: Hệ thống các tầng liên tiếp chia bề mặt trái đất thành các vùng với kích thước
nhỏ dần

Mỗi ô trong mỗi một tầng sẽ được gán với một ID duy nhất. Giả sử ở lớp thứ 8
(tier ID = 8) với 256 x 256 ô, và một ô có tọa độ (57, 34), sẽ được biểu diễn bởi một
số duy nhất là 57,034 gọi là ID của ô. Tổng quát, tại mỗi một lớp, cứ mỗi ô có tọa
độ (x, y) sẽ được biểu diễn thành một số thập phân có giá trị bằng (x + y.10-n) với n
là số nguyên dương nhỏ nhất thỏa mãn 10n lớn hơn 2ID lớp. Trong ví dụ trên, n = 3
thỏa mãn điều kiện vì 103 = 1000 > 28 = 256. Do đó, ô ở vị trí (57, 34) sẽ có ID là
57,034.

14
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


Hình 2-4: Ô có tọa độ (57, 34) ở lớp thứ 8

Việc sắp xếp như vậy cho phép truy xuất nhanh các vị trí được lưu trữ ở nhiều
lớp khác nhau. Lấy ví dụ, tưởng tượng chúng ta có một triệu địa điểm liên quan tới
chùa chiền ở nhiều vùng khác nhau của Việt Nam, và chúng ta muốn tìm kiếm các
địa điểm ở Hà Nội. Nếu không lập chỉ mục theo không gian, ta sẽ phải lần lượt tính
khoảng cách từ vị trí truy vấn tới từng địa điểm xem có thỏa mãn vùng tìm kiếm

không. Nhưng với phương pháp này, nếu ta biết được vị trí hiện tại, bán kính tìm
kiếm, ta sẽ xác định được ID của ô với kích thước nhỏ nhất bao trùm vùng tìm kiếm.
Việc đơn giản còn lại chỉ là tìm kiếm tất cả các địa điểm nằm trong ô đó. Điều này
chắc chắn nhanh hơn việc tính khoảng cách tới từng địa điểm để xem địa điểm đó
có thỏa mãn vùng tìm kiếm của chúng ta hay không.
Sau khi tìm được các đối tượng thỏa mãn vùng tìm kiếm, chúng ta sẽ xếp
hạng các đối tượng này bằng cách đánh giá độ liên quan giữa vị trí của chúng với vị
trí truy vấn. Để đánh giá độ tương tự về không gian, chúng ta sử dụng khoảng cách
giữa vị trí truy vấn với vị trí của các đối tượng. Với vị trí truy vấn Lq và bán kính
tìm kiếm, ta sẽ có được một tập các đối tượng thỏa mãn về vị trí tìm kiếm của người
dùng. Khoảng cách giữa vị trí của người dùng với vị trí của các đối tượng này sẽ là
cơ sở để đánh giá mức độ phù hợp của chúng với truy vấn về mặt không gian. Cụ
thể, đối tượng nào có khoảng cách tới vị trí truy vấn càng lớn thì sẽ có điểm càng
nhỏ, và ngược lại, đối tượng nào càng gần với vị trí truy vấn đương nhiên sẽ có
điểm cao hơn. Công thức dưới đây sẽ đánh giá mức độ tương tự về không gian giữa
vị trí truy vấn q và đối tượng d:
với distance là khoảng cách giữa vị trí truy vấn tới đối tượng d,
radius là bán kính tìm kiếm.
15
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


Trong trường hợp khoảng cách này lớn hơn bán kính tìm kiếm thì ta coi như
.
Dưới đây là một ví dụ minh họa về tính điểm độ tương tự về không gian. Có 5
đối tượng với điểm truy vấn và bán kính truy vấn như hình vẽ dưới đây.

Hình 2-5: Biểu diễn truy vấn q và các đối tượng d

Khi đó, độ tương tự về không gian giữa truy vấn q với các đối tượng d là:

Đối tượng
Khoảng cách tới truy vấn (km)
Điểm
d1
2
0.8
d2
4
0.6
d3
6
0.4
d4
8
0.2
d5
12
0
Bảng 2-2: Độ tương tự về không gian giữa vị trí truy vấn với vị trí đối tượng

2.4 Thảo luận:
Qua mục 2.2 và 2.3, chúng tôi đã trình bày về cơ sở lý thuyết của tìm kiếm tài
liệu dựa trên từ khóa và dựa trên vị trí, bao gồm quá trình lập chỉ mục và quá trình
tìm kiếm, xếp hạng các tài liệu dựa trên độ tương tự. Trong quá trình lập chỉ mục,
cấu trúc chỉ mục phổ biến nhất là Inverted Files bởi những ưu điểm nó mang lại cho
kích thước lưu trữ chỉ mục và tốc độ tìm kiếm. Trong quá trình xếp hạng các tài liệu,
cách tính điểm độ tương tự của từ khóa và không gian là không giống nhau. Với từ
khóa, độ tương tự được tính bằng tổng các trọng số tf-idf của của tài liệu d với từng
term trong q. Với vị trí, độ tương tự lại tính dựa trên khoảng cách bề mặt giữa vị trí
đối tượng d với vị trí mà truy vấn đề cập tới. Vấn đề đặt ra là chúng ta phải kết hợp

độ tương tự về từ khóa với độ tương tự về không gian, thành một độ tương tự toàn
16
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


phần, sau đó xếp hạng các tài liệu dựa trên độ tương tự mới này và trả kết quả tìm
kiếm về cho người dùng.

17
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


Chương 3: Kỹ thuật tìm kiếm văn bản dựa trên vị trí
Chương này sẽ giải quyết vấn đề đặt ra ở chương 2, đó chính là việc kết hợp
độ tương tự về từ khóa với độ tương tự về không gian thành một độ tương tự duy
nhất, để có thể đánh giá và xếp hạng các tài liệu trên độ tương tự mới này. Chúng
tôi cũng đưa ra các mô hình khác nhau trong việc tìm kiếm tài liệu văn bản dựa
trên vị trí.
3.1 Phân tích yêu cầu hệ thống:
Qua chương 2 nhận thấy rằng, nếu đặt ra vấn đề là phải tìm kiếm văn bản dựa
trên vị trí, thì chúng ta sẽ tìm kiếm văn bản theo từ khóa trước, sau đó tính khoảng
cách từ vị trí truy vấn tới từng vị trí của văn bản đó xem có thỏa mãn không. Hoặc
ngược lại, ta sẽ đi tính khoảng cách từ vị trí truy vấn tới từng vị trí của văn bản, sau
đó mới tìm theo từ khóa. Như vậy là sẽ chỉ lập được một chỉ mục, hoặc chỉ mục về
từ khóa, hoặc chỉ mục về không gian. Không những thế, cách làm này còn không
khả thi trong trường hợp số lượng văn bản lớn, vì khi đó việc tính toán khoảng cách
tới tất cả vị trí của văn bản đòi hỏi rất nhiều thời gian.
Chính vì lý do đó, người ta đề xuất ra một cấu trúc chỉ mục mới có thể kết hợp
được cả chỉ mục về từ khóa lẫn chỉ mục về không gian thành một chỉ mục duy nhất.
Một cấu trúc chỉ mục lai như vậy được minh họa như sau:


Hình 3-1: Cấu trúc chỉ mục lai R*-tree-Inverted file [3]

Với cấu trúc chỉ mục này, với một truy vấn không gian-từ khóa cho trước, đầu
tiên, ta sẽ duyệt những nút lá của R*-tree có chứa vị trí truy vấn trước, và sau đó tìm
đến tất cả các văn bản trong Inverted file tương ứng với tập từ khóa. Thêm vào đó,

18
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


ta không thể thực hiện song song, độc lập tìm kiếm dựa trên từ khóa và tìm kiếm
dựa trên vị trí.
Vì thế, yêu cầu đặt ra đối với hệ thống tìm kiếm là phải kết hợp được cả chỉ
mục về từ khóa với chỉ mục về không gian thành một cấu trúc chỉ mục duy nhất.
Không những thế, hệ thống cũng phải xếp hạng các văn bản trả về dựa trên cả độ
tương tự về từ khóa lẫn độ tương tự về không gian, chứ không chỉ đơn thuần đánh
giá các kết quả theo độ tương tự về từ khóa (hoặc không gian).
3.2 Định hướng giải pháp:
Bài toán của chúng ta như sau: có một tập D = {d0, d1, …, dn} của n văn bản
(trang web). Mỗi văn bản có chứa một tập từ khóa Kd và một vị trí duy nhất được
biểu diễn bởi tọa độ (vĩ độ và kinh độ) trên bề mặt Trái Đất.
Một truy vấn đầu vào có dạng Q = (Tq, Lq) với Lq là vị trí cần truy vấn, ví dụ
“Hà Nội”, “Đà Nẵng”, … và Tq là tập từ khóa trong truy vấn, ví dụ “quán ăn”, “bảo
tàng”, …
Chúng tôi sử dụng thư viện mã nguồn mở Lucene để lập chỉ mục về từ khóa,
đồng thời sử dụng cấu trúc chỉ mục ô [4] để lập chỉ mục về không gian. Ngoài ra,
chúng tôi cũng đánh giá độ tương tự của các văn bản trả về dựa trên độ tương tự về
từ khóa lẫn độ tương tự về không gian.
3.3 Kết hợp điểm từ khóa và điểm không gian:

Sau khi thực hiện lần lượt hai bước: tìm kiếm trên từ khóa và tìm kiếm trên
không gian, ta sẽ có hai danh sách kết quả trả về. Với truy vấn từ khóa Tq cho ta
danh sách thứ nhất các tài liệu có liên quan tới truy vấn, mỗi tài liệu có độ tương tự
về từ khóa là
. Tương tự, truy vấn không gian Lq cho ta danh sách thứ hai các tài
liệu nằm trong vùng truy vấn của người dùng, mỗi tài liệu cũng sẽ có độ tương tự về
không gian là
. Đến đây, chúng ta sẽ trộn hai danh sách này lại thành một danh
sách duy nhất, với độ tương tự cho mỗi tài liệu trong danh sách cuối cùng được tính
theo công thức:
với 0 <  < 1 là hằng số cho trước.
Nếu như một thành phần nào đó (

hoặc

) của một tài liệu không xuất

hiện trong hai danh sách kết quả tìm kiếm thì ta sẽ coi điểm thành phần đó bằng 0.
Sau đó ta lấy ra k tài liệu có điểm tổng cao nhất làm kết quả tìm kiếm trả về cho
người dùng.
Hình vẽ dưới đây mô tả quá trình trộn hai danh sách tìm kiếm và xếp hạng lại
tập tài liệu để có được danh sách kết quả cuối cùng.

19
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


Hình 3-2:Trộn hai danh sách với  = 0.5 và lấy k = 3 tài liệu có điểm cao nhất

3.4 Các mô hình tìm kiếm văn bản dựa trên vị trí:

3.4.1 Tìm kiếm vị trí rồi tìm kiếm từ khóa:
Với cách tiếp cận này, chúng ta sẽ tìm kiếm trên không gian trước rồi mới tìm
kiếm trên từ khóa. Vị trí cần truy vấn của người dùng Lq sẽ được chuyển thành tọa
độ địa lý (vĩ độ, kinh độ). Cùng với bán kính tìm kiếm xác định, ta có được một truy
vấn không gian mà tâm là vị trí của người dùng, và bán kính bằng bán kính truy vấn.
Truy vấn này sẽ trả về cho chúng ta ID của một ô trong hệ thống lớp Đề-các, có
chứa vùng truy vấn của người dùng. Sau đó chúng ta sẽ tìm trong ô đó các tài liệu
thỏa mãn tập từ khóa Tq.

Hình 3-3: Minh họa quá trình tìm kiếm vị trí rồi tìm kiếm từ khóa
20
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


Không gian tìm kiếm được thiết lập. Thực hiện tìm kiếm từ khóa trên không gian đó, ta
được tập kết quả gồm 2 tài liệu d1 và d3

Phương pháp này sẽ giới hạn lại vùng truy vấn, lọc bớt các kết quả không cần
thiết đi, nên sẽ tránh được lãng phí do phải tìm kiếm những tài liệu không liên quan
tới vùng truy vấn. Tuy nhiên, việc xác định bán kính tìm kiếm là mấu chốt trong
việc tìm kiếm, vì rất có thể có khả năng không tồn tại một tài liệu nào phù hợp về từ
khóa trong vùng truy vấn.
3.4.2 Tìm kiếm từ khóa và tìm kiếm vị trí:
Trong cách tiếp cận này, chúng ta sẽ tìm kiếm từ khóa và không gian song
song song với nhau. Truy vấn từ khóa sẽ trả cho chúng ta một danh sách các tài liệu
phù hợp với tập từ khóa của người dùng. Truy vấn không gian sẽ cho ta một tập tất
cả các tài liệu nằm ở trong vùng truy vấn. Cuối cùng, ta sẽ trộn hai danh sách này
với nhau, và chọn ra các tài liệu có độ phù hợp cao nhất làm kết quả tìm kiếm cuối
cùng.


Hình 3-4: Minh họa quá trình tìm kiếm vị trí và tìm kiếm từ khóa
Thực hiện tìm kiếm từ khóa ta được tập 3 tài liệu d1, d3, d5. Thực hiện tìm kiếm không gian
ta được tập 3 tài liệu d1, d2, d3. Kết quả cuối cùng là hợp của 2 tập.

3.4.3 Tìm kiếm từ khóa rồi tìm kiếm không gian:
Ngược với cách tiếp cận đầu tiên, trong cách tiếp cận này, chúng ta sẽ tìm theo
từ khóa trước rồi mới thực hiện tìm kiếm theo không gian. Một danh sách các tài
liệu phù hợp với tập từ khóa được trả về sau truy vấn từ khóa đầu tiên. Sau đó, ta sẽ
tính khoảng cách giữa vị trí truy vấn và vị trí của từng tài liệu, chọn ra những tài
liệu nào có khoảng cách nhỏ hơn bán kính truy vấn làm kết quả tìm kiếm cuối cùng.
Phương pháp này trong mọi trường hợp sẽ luôn tìm được kết quả tìm kiếm, tuy
nhiên sẽ rất mất thời gian vì phải “vét cạn”, tính khoảng cách cho tất cả các tài liệu,
do đó sẽ dẫn đến tình trạng lãng phí khi phải tìm cả những liệu không nằm trong
vùng truy vấn.
21
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


Hình 3-5: Minh họa quá trình tìm kiếm từ khóa rồi tìm kiếm vị trí

3.5 Thuật toán:
Sau khi nghiên cứu các kỹ thuật ở phần trước, mục này sẽ đề xuất một giải
thuật để tìm kiếm tài liệu dựa trên vị trí. Giải thuật được mô tả bằng mã giả như sau:
khởi tạo

,

,

cho từng tài liệu d


foreach term t trong do
lấy danh sách inverted list của t
foreach tài liệu d trong inverted list do
tính
endfor
endfor
lấy danh sách inverted list của
foreach tài liệu d trong inverted list do
tính
endfor
foreach
if

> 0 do
> 0 then

else
endif
endfor
lấy k tài liệu có

cao nhất
22

Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


3.6 Bàn luận:
Trong chương này, chúng tôi đã trình bày một cấu trúc chỉ mục kết hợp lập chỉ mục

cả từ khóa lẫn vị trí. Chúng tôi cũng đề xuất một thuật toán để kết hợp độ tương tự
về từ khóa với độ tương tự về không gian thành một độ tương tự duy nhất, để có thể
đánh giá xếp hạng các văn bản tìm được từ câu truy vấn. Bên cạnh đó, chúng tôi
cũng có đưa ra các mô hình tìm kiếm: tìm kiếm theo vị trí rồi tìm kiếm theo từ khóa,
tìm kiếm theo vị trí và tìm kiếm theo từ khóa, tìm kiếm theo từ khóa rồi tìm kiếm
theo vị trí. Mỗi một cách tiếp cận đều có những ưu và nhược điểm riêng của nó.
Trong chương tới, chúng tôi sẽ cài đặt thử nghiệm hệ thống tìm kiếm văn bản trên
lĩnh vực du lịch dựa vào những gì vừa mới trình bày ở trên. Ngoài ra, chúng tôi
cũng so sánh đánh giá kết quả tìm kiếm trong từng mô hình tìm kiếm.

23
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53


Chương 4: Cài đặt thử nghiệm
Trong chương này chúng tôi xây dựng hệ thống tìm kiếm tài liệu về lĩnh vực
du lịch và trình bày một số kết quả thực nghiệm đạt được.
4.1 Môi trường thử nghiệm:
Hệ thống tìm kiếm được xây dựng dựa trên thư viện mở Lucene. Lucene là
một thư viện tìm kiếm thông tin có khả năng xử lý và khả năng mở rộng ở mức cao,
cho phép chúng ta có thể tích hợp vào các ứng dụng. Lucene là một dự án mã nguồn
mở và nguyên thuỷ được phát triển bằng ngôn ngữ Java. Ngày nay Lucene được
phát triển bằng nhiều ngôn ngữ khác nhau như Delphi, Perl, C#, C++, Python, Ruby
và PHP …
Thành phần chức năng chính của Lucene bao gồm hai phần: thành phần tạo
chỉ mục và thành phần tìm kiếm. Đây là hai thành phần quan trọng cho một hệ
thống tìm kiếm.
 Thành phần tạo chỉ mục: bao gồm các phần chức năng xử lý tạo chỉ mục, từ
văn bản đầu vào để cho ra kết quả là một tập chỉ mục. Lucene chỉ hỗ trợ trên
văn bản sau khi được tách nội dung ở dạng ký tự thuần, nó cho phép lập chỉ

mục trên từng trường thông tin của văn bản và cho phép thiết lập hệ sốcho
từng trường thông tin để nâng cao vai trò lúc tìm kiếm.
 Directory: cho phép định nghĩa vùng nhớ, xác định nơi lưu trữ trên
bộ nhớ ngoài và bộ nhớ trên RAM trong quá trình tạo chỉ mục.
 Document và Field: định nghĩa tài liệu và các trường thông tin của tài
liệu sử dụng cho lập chỉ mục. Nó cũng sử dụng cho việc lấy kết quả
trả về cho thành phần tìm kiếm.
 Analyzer: thực hiện chức năng xử lý và tách văn bản để lấy nội dung,
chuẩn hóa, loại bỏmục từ không cần thiết, … để chuẩn bị cho việc
lập chỉ mục.
 IndexWriter: là phần chính trong thành phần tạo chỉ mục, nó thực
hiện việc tạo mới hoặc mở chỉ mục, sau đó thực hiện thêm mới hoặc
cập nhật nội dung của chỉ mục.
 Thành phần tìm kiếm: bao gồm các phần chức năng cho xử lý tìm kiếm, từ
yêu cầu của người dùng, thông qua biên dịch và so khớp để lấy về kết quả
tốt nhất. Lucene hỗ trợ nhiều loại truy vấn thuận tiện cho người sử dụng, nó
cho phép tìm theo trường thông tin hay các thiết lập nâng cao như sắp xếp
kết quả, giới hạn thời gian hoặc số lượng kết quả, phân trang …
 Term: term là một đơn vị cơ bản của tìm kiếm, tương tự như thành
phần Field, Term cũng bao gồm tên và giá trị tương ứng.

24
Sinh viên thực hiện: Vũ Hà Dũng, 20080538, Tin Pháp K53