ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN


Trần Quốc Cường

HỆ THỐNG TÌM KIẾM THÔNG TIN QUA
MẠNG

KHÓA LUẬN CAO HỌC
NGÀNH: KHOA HỌC MÁY TÍNH
Mã số: 60480101

NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. NGÔ THANH HÙNG

TP HỒ CHÍ MINH - NĂM 2016


LỜI CAM ĐOAN
Lời đầu tiên, tôi xin gửi lời cảm ơn chân thành nhất đến toàn thể quý thầy cô trường
Đại học Công Nghệ Thông Tin – Đại học Quốc gia Thành phố Hồ Chí Minh, quý
thầy cô ngành khoa học máy tính đã dạy dỗ, truyền đạt những kiến thức quý báu cho
tôi trong suốt thời gian học tập và rèn luyện tại trường.
Tiếp theo, tôi xin gửi lời cám ơn sâu sắc đến Thầy hướng dẫn TS. Ngô Thanh Hùng,
cám ơn thầy đã tận tình hướng dẫn và tạo mọi điều kiện tốt nhất để tôi hoàn thành
khóa luận cao học này.
Vì thời gian thực hiện khóa luận ngắn nên khóa luận chỉ đạt đến những thành quả
nhất định và còn nhiều vấn đề còn hạn chế mong Thầy/Cô thông cảm và góp ý giúp
tôi để hoàn thành tốt hơn.
Nhân tiện, tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi và được sự

hướng dẫn khoa học của Thầy TS. Ngô Thanh Hùng. Các nội dung nghiên cứu, kết
quả trong đề tài này là trung thực và chưa công bố dưới bất kỳ hình thức nào trước
đây. Những số liệu trong các bảng biểu phục vụ cho việc phân tích, nhận xét, đánh
giá được chính tác giả thu thập từ các nguồn khác nhau có ghi rõ trong phần tài liệu
tham khảo.
Nếu phát hiện có bất kỳ sự gian lận nào tôi xin hoàn toàn chịu trách nhiệm về nội
dung khóa luận của mình.
Xin chân thành cảm ơn !
Học viên

Trần Quốc Cường
1


MỤC LỤC
LỜI CAM ĐOAN ............................................................................................................ 1
DANH MỤC CHỮ VIẾT TẮT........................................................................................ 5
DANH MỤC HÌNH ......................................................................................................... 6
DANH MỤC BẢNG ........................................................................................................ 7
CHƯƠNG 1.

TỔNG QUAN ĐỀ TÀI ......................................................................... 8

1.1.

Tên đề tài: ........................................................................................................... 8

1.2.

Mục tiêu đề tài .................................................................................................... 8


1.3.

Nội dung, phạm vi và phương pháp nghiên cứu đề tài....................................... 9

1.3.1.

Nội dung nghiên cứu .................................................................................... 9

1.3.2.

Phạm vi nghiên cứu ..................................................................................... 9

1.3.3.

Phương pháp nghiên cứu ............................................................................ 9

Ý nghĩa khoa học và thực tiễn ............................................................................ 9

1.4.

1.4.1.

Ý nghĩa khoa học .......................................................................................... 9

1.4.2.

Ý nghĩa thực tiễn ........................................................................................ 10

CHƯƠNG 2.


CƠ SỞ LÝ THUYẾT .......................................................................... 11

Kỹ thuật tìm kiếm toàn văn bản Full-text Search ............................................. 11

2.1.

2.1.1.

Lập chỉ mục ................................................................................................ 11

2.1.2.

Inverted Index ............................................................................................ 12

2.1.3.

Tokenization............................................................................................... 13

2.1.4.

Xử lý truy vấn với inverted index ............................................................... 19

2.1.5.

Scoring........................................................................................................ 19

2.1.6.

Thư viện LUCENE ....................................................................................... 22


2.1.6.1.

Giới thiệu về Lucene ........................................................................... 22

2.1.6.2.

Lucene và các thành phần của ứng dụng tìm kiếm ............................. 22

2.1.6.3.

Các tiến trình hoạt động ...................................................................... 23

a.

Xây dựng tập chỉ mục tìm kiếm................................................................. 23

b.

Tìm kiếm trên tập chỉ mục ......................................................................... 23

2.1.6.4.

Tiến trình phân tích của Lucene.......................................................... 24
2


Kỹ thuật chuyển đổi định dạng Tika Parser ..................................................... 24

2.2.


2.2.1.

Giới thiệu ................................................................................................... 24

2.2.2.

Ứng dụng Apache Tika ............................................................................... 25

2.2.3.

Kiến trúc của Tika ....................................................................................... 26

a.

Cơ chế phát hiện ngôn ngữ (Language detection mechanism):................. 26

b.

Cơ chế phát hiện MIME (MIME detection mechanism) ........................... 27

c.

Giao diện phân tích (Parser interface) ....................................................... 27

d.

Lớp Tika Facade (Tika Facade class): ....................................................... 27

2.2.4.


Đặc tính của Tika ........................................................................................ 28

2.2.5.

Các chức năng của Tika .............................................................................. 28

a.

Phát hiện loại tài liệu ................................................................................. 28

b.

Khai thác nội dung. .................................................................................... 28

c.

Khai thác siêu dữ liệu. ............................................................................... 29

d.

Nhận biết ngôn ngữ.................................................................................... 29

2.3.

Hệ thống Compass ............................................................................................ 29

2.3.1.

Giới thiệu ................................................................................................... 29


2.3.2.

Mô hình và nguyên tắc hoạt động Compass: ............................................ 30

a.

Cấu trúc: ..................................................................................................... 30

b.

Nguyên tắc hoạt động ................................................................................ 31

c.

Đặc điểm của hệ thống............................................................................... 31

CHƯƠNG 3. PHÂN TÍCH VÀ THIẾT KẾ HỆ THỐNG ............................................. 32
3.1.

Mô tả yêu cầu hệ thống..................................................................................... 32

3.2.

Phân tích thiết kế hệ thống ............................................................................... 32

3.2.1.

Mô hình hệ thống: ..................................................................................... 32


3.2.2.

Mô hình chi tiết .......................................................................................... 33

3.2.2.1.

Lập chỉ mục ......................................................................................... 33

3.2.2.2.

Phân tách thành những cây n-tree theo từng chủ đề. .......................... 33

3.2.2.3.

Đăng nhập hệ thống: ........................................................................... 34

3.2.2.4.

Thực hiện tìm kiếm: ............................................................................ 35
3


CHƯƠNG 4. CÀI ĐẶT VÀ KIỂM THỬ HỆ THỐNG ................................................ 40
4.1.

Nền tảng công nghệ sử dụng ............................................................................ 40

4.2.

Cài đặt hệ thống ................................................................................................ 40


4.2.1.

Môi trường cài đặt: .................................................................................... 40

4.2.2.

Cài đặt ........................................................................................................ 40

4.2.2.1.

Lập chỉ mục:........................................................................................ 40

4.2.2.2.

Lập n-tree: ........................................................................................... 41

4.2.2.3.

Tìm kiếm: ............................................................................................ 41

4.3.

Mô tả hệ thống .................................................................................................. 42

4.4.

Kiểm thử hệ thống ............................................................................................ 44

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

❖

Kết quả đạt được ............................................................................................... 50

❖

Một số hạn chế .................................................................................................. 50

❖

Hướng phát triển ............................................................................................... 51

TÀI LIỆU THAM KHẢO .............................................................................................. 52
PHỤ LỤC ....................................................................................................................... 53

4


DANH MỤC CHỮ VIẾT TẮT
TF

Term Frequency

IDF

Inverse Document Frequency

DF

Document Frequency


RAM

Ramdom Access Memory

SQL

Structured Query Language

NoSQL

Not Only SQL

XML

Extensible Markup Language

HTML

HyperText Markup Language

JSON

JavaScript Object Notation

GUI

Graphical User Interface

CPU


Central Processing Unit

API

Application Programing Interface

HTTP

Hypertext Transfer Protocol

JMX

Java Management Extensions

TM

Topic Map

5


DANH MỤC HÌNH
Hình 2.1 – Quá trình lập chỉ mục ..................................................................... 13
Hình 2.2 - Ví dụ về tìm kiếm sử dụng Boolean logic ........................................ 19
Hình 2.3 - Ví dụ về Parametric Index............................................................... 20
Hình 2.4 -Các thành phần cơ bản của một ứng dụng tìm kiếm........................ 22
Hình 2.5- Các thao tác chính trong tiến trình lập chỉ mục .............................. 23
Hình 2.6 -Qui trình chuyển đổi nội dung tìm kiếm ........................................... 24
Hình 2.7- Tiến trình phân tích trong quá trình lập chỉ mục ............................. 24

Hình 2.8 – Minh họa ứng dụng của Tika parser. ............................................. 25
Hình 2.9 – Minh họa tiến trình hoạt động của Tika parser. ............................ 25
Hình 2.10 – Minh họa cấu trúc của Tika parser .............................................. 26
Hình 2.11 – Minh họa các cấp độ của các kỹ thuật tìm kiếm. ......................... 29
Hình 2.12 – Minh họa một số chủ đề liên quan................................................ 30
Hình 2.13 – Sơ lược các thành phần của Compass.......................................... 31
Hình3.1- Mô hình sơ lược của hệ thống. .......................................................... 32
Hình3.2- Minh họa tiến trình tạo chỉ mục. ....................................................... 33
Hình3.3- Minh họa tiến trình tạo Topic map. ................................................. 33
Hình3.4- minh họa cách tạo cây n-tree trong Topic Map. ............................... 34
Hình3.5- Minh họa các chức năng của người dùng. ........................................ 35
Hình3.6- Minh họa tiến trình thực hiện tìm kiếm. ............................................ 35
Hình3.7-Minh họa cho cây n-tree dạng “vòng” .............................................. 37
Hình3.8-Minh họa cho cây n-tree dạng một nhánh. ........................................ 38
Hình3.9-Minh họa cho cây n-tree bất kỳ. ......................................................... 39
Hình4.1-Minh họa hệ thống tìm kiếm thông tin qua mạng. ............................. 42
Hình 4.2 – Màn hình chính của ứng dụng. ....................................................... 43
Hình 4.3 - Các chức năng dành cho khách ..................................................... 43
Hình 4.4 - Các chức năng dành cho quyền quản trị ....................................... 44

6


DANH MỤC BẢNG
Bảng 2.1 - Một số quy luật của thuật toán Porter ........................................... 16
Bảng 2.2 - Ví dụ so sánh thuật toán Porter and các thuật toán stemming khác
.......................................................................................................................... 17
Bảng 2.3 - Ví dụ so sánh thuật toán Porter và thuật toán Krovetz .................. 18
Bảng 3.1- Bảng ví dụ minh họa về phương pháp tìm kiếm Full Text Search. . 36
Bảng 4.1- Bảng mô tả các chủ đề mẫu được thể hiện trong dữ liệu. ............... 45

Bảng 4.2- Kết quả thu được khi người dùng nhập từ “chương”. .................... 46
Bảng 4.3- Kết quả thu được khi người dùng nhập “nhân viên”. ..................... 47
Bảng 4.4: mô tả ví dụ chạy thử nghiệm những từ đồng nghĩa với từ “chương”
.......................................................................................................................... 48
Bảng 4.5: mô tả ví dụ chạy thử nghiệm những từ đồng nghĩa với từ “nhân
viên” ................................................................................................................. 48

7


CHƯƠNG 1.

TỔNG QUAN ĐỀ TÀI

Ngày nay, sự phát triển của Internet đã làm thay đổi mạnh mẽ cách thức hoạt
động của các tổ chức, cơ quan. Các ứng dụng web, mạng xã hội, điện toán đám mây
đã góp phần làm cho công việc trở nên dễ dàng hơn, đa dạng hơn. Tuy nhiên, điều
này cũng góp phần vào việc tạo ra khối lượng thông tin vô cùng lớn và do đó quá
trình tìm kiếm thông tin trở nên khó khăn hơn.
Cũng chính vì dung lượng dữ liệu lớn đi cùng với tốc độ gia tăng dung lượng rất
nhanh, việc lưu trữ và tìm kiếm dữ liệu trở thành một thách thức không hề nhỏ.
Hiện nay, đã xuất hiện các hệ thống tìm kiếm từ các trang: Yahoo, Google....để
tìm kiếm thông tin. Nhưng đối với doanh nghiệp, cơ quan... để thực hiện việc tìm
kiếm các văn bản nội bộ, không thể thực hiện trên các trang tìm kiếm đó mà cần phải
có một hệ thống hỗ trợ cho việc tìm kiếm từ Internet đối với văn bản nội bộ để đảm
bảo cho dữ liệu được tìm kiếm chính xác nhất, giảm thời gian nhất.
Vì vậy, trong khóa luận này tập trung nghiên cứu những kỹ thuật để xây dựng
một hệ thống tìm kiếm thông tin qua mạng.
1.1. Tên đề tài:
“Hệ thống tìm kiếm thông tin qua mạng”.

1.2. Mục tiêu đề tài
-

Tìm hiểu các kỹ thuật, công nghệ để xây dựng một hệ thống lưu trữ tìm
kiếm thông tin cho nội bộ doanh nghiệp.

-

Hệ thống cho phép tải các tài liệu văn bản doanh nghiệp lên máy chủ
trung tâm. Máy chủ sẽ lập các chỉ mục đối với các tài liệu nhằm hỗ trợ
việc tìm kiếm toàn văn bản và tìm kiếm theo những từ liên quan cùng chủ
đề.

8


1.3. Nội dung, phạm vi và phương pháp nghiên cứu đề tài
1.3.1. Nội dung nghiên cứu
Xây dựng hệ thống tìm kiếm dựa trên phương pháp tìm kiếm theo toàn văn
bản và tìm kiếm theo các từ liên quan cùng chủ đề. Nghiên cứu sử dụng các
kỹ thuật sau:
-

Nghiên cứu kỹ thuật tìm kiếm toàn văn bản (lập chỉ mục, chuyển đổi văn
bản về dạng Text).

-

Nghiên cứu và xây dựng các cây n-tree các từ đồng nghĩa.


-

Xây dựng Website tìm kiếm thông tin cho nội bộ doanh nghiệp.

1.3.2. Phạm vi nghiên cứu
-

Đề tài có thể dùng công nghệ Web application để giúp người dùng có thể
truy cập bất cứ nơi đâu.

-

Sử dụng công nghệ Compass(open source framework) để tìm kiếm từ hoặc
cụm từ của “từ khóa” hoặc theo từ đồng nghĩa đề tìm kiếm các từ có liên
quan trong phạm vi giới hạn.

1.3.3. Phương pháp nghiên cứu
Đề tài được thực hiện dựa trên phương pháp khảo sát, phân tích và áp dụng
các kiến thức đã nghiên cứu, tìm hiểu để xây dựng hệ thống.
1.4. Ý nghĩa khoa học và thực tiễn
1.4.1. Ý nghĩa khoa học
-

Đề tài sử dụng các phương pháp thuật toán tìm kiếm mà hiện tại được sử
dụng nhằm tìm kiếm dữ liệu nhanh chóng, chính xác, đầy đủ.

-

Sử dụng n-Tree các từ đồng nghĩa để cải tiến khả năng tìm kiếm đầy đủ
thông tin.


9


-

Sử dụng kỹ thuật toàn văn bản để tìm kiếm tất cả các từ khóa.

1.4.2. Ý nghĩa thực tiễn
-

Áp dụng cho các bộ phận quản lý về các văn bản đi hoặc văn bản đến trong
thời gian dài.

-

Áp dụng cho nhân viên trong doanh nghiệp tìm kiếm nội dung của một văn
bản.

-

Áp dụng kỹ thuật tìm kiếm theo cơ chế toàn văn bản và tìm kiếm theo từ
đồng nghĩa liên quan thông qua n-Tree có trong tập tin văn bản.

10


CHƯƠNG 2.

CƠ SỞ LÝ THUYẾT


Nội dung chương sẽ trình bày phần lý thuyết về nội dung được sử dụng trong
hệ thống tìm kiếm thông tin qua mạng, bao gồm các nội dung sau:
-

Kỹ thuật tìm kiếm toàn văn bản (full-text search), tạo chỉ mục(lucene)

-

Kỹ thuật chuyển định dạng tập tin sang dạng text (Tika parser)

- Hệ thống compass để tìm kiếm theo những từ đồng nghĩa liên quan (Compass
System).
2.1. Kỹ thuật tìm kiếm toàn văn bản Full-text Search
Full-text search là kỹ thuật tìm kiếm trên full-text database. Full-text database
có thể được hiểu là một cơ sở dữ liệu chứa toàn bộ text của các văn bản. Trong
kỹ thuật full-text search, thay vì phải tìm trực tiếp trong các văn bản để tìm ra
văn bản phù hợp cho người dùng, search engine sẽ cố gắng tìm các chỉ mục.
[4, 7, 8]
2.1.1. Lập chỉ mục
Khi tìm kiếm văn bản trong một cơ sở dữ liệu không lớn, việc tìm trực tiếp
trong từng văn bản (document) không phải là vấn đề lớn, kỹ thuật này gọi
là “serial scanning”. [7]
Nhưng với một cơ sở dữ liệu có số lượng văn bản lớn, tìm kiếm theo cách
này hoàn toàn không hiệu quả về mặt tốc độ. Vì vậy, có hai vấn đề chính
mà khi thực hiện full-text search cần phải thực hiện: Đánh chỉ mục
(indexing) và tìm kiếm (searching).
Giai đoạn đánh chỉ mục sẽ duyệt qua tất cả text trong tập các văn bản của
cơ sở dữ liệu và xây dựng nên một danh sách các từ khóa phục vụ cho việc
tìm kiếm (danh sách này được gọi là index).

Trong giai đoạn tìm kiếm, search engine (cổ máy tìm kiếm) sẽ tìm kiếm
trong danh sách chỉ mục để lấy ra các văn bản liên quan, thay vì phải tìm
kiếm trong văn bản gốc.
Indexer (bộ lập chỉ mục) sẽ tạo một mục cho mỗi từ khóa được tìm thấy

11


trong văn bản, cũng có thể lưu vị trí của mỗi từ khóa xuất hiện trong mỗi
văn bản. Thông thường, Indexer sẽ bỏ qua các Stop Word (đây là những từ
xuất hiện thường xuyên và thường không có ý nghĩa trong việc tìm kiếm)
như “the”, “and”…
Một số Indexer cũng thực hiện kỹ thuật Stemming trong một ngôn ngữ
nhất định, đây là kỹ thuật đưa các từ về trạng thái gốc, ví dụ như các từ
như “drive”, “drove”, “driven” sẽ được lưu trong index thành “drive”.
2.1.2. Inverted Index
Điều làm nên sự khác biệt cơ bản của full-text search và search thông
thường chính là Inverted Index.
Inverted Index (hay còn được gọi là Postings File hoặc Inverted File) là
một cấu trúc dữ liệu chỉ mục (Index Data Structure) lưu trữ ánh xạ từ các
từ khóa tới các văn bản chứa nó.
Có hai biến thể chính của Inverted Index: Record Level Inverted
Index (hay Inverted File Index, hay Inverted File) lưu các tham chiếu
tới các văn bản cho mỗi từ khóa, và Word Level Inverted Index (hay
Full Inverted Index, hay Inverted List) lưu trữ thêm vị trí của mỗi term
trong documents. Word Level Inverted Index thường có nhiều tính
năng hơn, như là Phrase Searching (tìm kiếm theo câu), nhưng phải lưu
trữ nhiều hơn.

12



Hình 2.1 – Quá trình lập chỉ mục1

2.1.3. Tokenization
Tokenization là quá trình bóc tách văn bản thành các từ, câu, hay các thành
phần có nghĩa được gọi là token. Các tokens sẽ là đầu vào của một số quá
trình xử lý, chuẩn hóa, cuối cùng sẽ cho ra danh sách các terms để lưu trữ
trong index.
Thông thường, quá trình bóc tách chuỗi được thực hiện ở cấp từ (word
level). Tuy nhiên, nó thường khó xác định được thông qua nghĩa của từ.
Thường một Tokenizer dựa trên phương thức heuristic đơn giản, ví dụ
như:
o Dấu chấm câu, khoảng trắng có thể có hoặc không được đưa vào danh
sách các tokens kết quả.
o Chuỗi các ký tự (cũng như chữ số) liền kề nhau sẽ được xem là một
token.
o Các tokens được phân ra bởi ký tự khoảng trắng hoặc dấu câu.
Nguồn hình ảnh: Sách: Introduction to information retrieval. Vol. 1. Cambridge: Cambridge
university press, 2008. [4]
1

13


a. Stop word
Luôn tồn tại một số từ cực kỳ phổ biến mà sự xuất hiện của những từ đó
không giúp ích nhiều trong việc chọn ra văn bản thích hợp với yêu cầu tìm
kiếm của người dùng. Những từ này gọi là Stop Word, chúng bị bỏ qua
trong quá trình tách token.

Những từ này có thể được xác định bởi Collections Frequency - Tổng số lần
xuất hiện của mỗi term trong tập các văn bản. Hoặc cũng có thể sử
dụng Stop list chứa các Stop words để Tokenizer bỏ qua trong quá trình bóc
tách văn bản. Việc sử dụng Stop list cũng làm giảm đáng kể số lượng term mà
hệ thống phải lưu trữ.
a an
and are
has he in
is
to was were will

as
at
it
its
width

be
of

by
on

for
that

from
the

Tuy nhiên, trong một số trường hợp, việc không index Stop words có thể gây

hại, chẳng hạn như khi thực hiện phrase search, việc bỏ qua Stop words có
thể làm cho kết quả trả về thiếu chính xác. Ví dụ với phrase query “Flights to
London”, nếu bỏ qua từ “to”, nghĩa của cả câu sẽ hoàn toàn bị
mất, dữ liệu tìm kiếm có thể sẽ thiếu chính xác, hoặc không phù hợp. Chính
vì vậy, Web search engines thông thường sẽ không dùng Stop words.
b. Token Normalization (Chuẩn hóa token)
Token Normalization là quá trình làm cho tokens phù hợp với các quy tắc đã
quy định trước, giúp trùng khớp dữ liệu, cho dù có sự khác nhau giữa các ký
tự trong chuỗi của tokens.
o Ví dụ: khi người dùng tìm kiếm “VN” thì cũng sẽ trùng khớp với các
văn bản chứa “Vietnam”.
Cách phổ biến để thực hiện chuẩn hóa là ngầm xây dựng những lớp tương
đương (Equivalence Classes).
Để thực hiện, chúng ta có thể sử dụng quy tắc loại bỏ dấu gạch ngang.

14


o Ví dụ, nếu hai token “anti-discriminatory” và “antidiscriminatory”
cùng ánh xạ tới term “antidiscriminatory” trong cả văn bản lẫn câu
truy vấn (query), thì khi tìm kiếm với một trong hai term trên, hệ
thống cũng sẽ chọn ra văn bản chứa term còn lại.
Ngoài ra còn có thể duy trì mối quan hệ giữa các token chưa đc được chuẩn
hóa (Unnormalized Token). Phương thức này có thể được mở rộng bằng cách
xây dựng bằng tay danh sách các từ đồng nghĩa (synonyms) như “car” và
“automobile”. Mối quan hệ giữa các terms có thể được có được bằng hai
cách.
o Cách thông thường là đánh chỉ mục những tokens chưa được chuẩn
hóa và duy trì danh sách mở rộng truy vấn của nhiều token.
▪ Ví dụ, khi tìm kiếm “car” thì hệ thống sẽ tìm cả “car” và

“automobile”.
o Một cách khác là thực hiện mở rộng trong lúc xây dựng chỉ mục.
▪ Khi thực hiện đánh chỉ mục cho văn bản có từ “car” thì
“automobile” cũng sẽ được index.
Phương thức đầu tiên thêm một bộ từ điển mở rộng truy vấn, vì thế sẽ phải
xử lý nhiều hơn trong lúc truy vấn, thời gian truy vấn cũng sẽ lâu hơn.
Trong khi đó, phương thức thứ hai phải lưu trữ nhiều terms hơn, nhưng lại
là phương thức linh hoạt.
Ngoài ra, trong giai đoạn chuẩn hóa tokens còn thực hiện một số kỹ thuật
như loại bỏ dấu câu, chuyển tất cả thành ký tự thường (không ghi hoa).
c. Stemming
Vì lý do ngữ pháp, văn bản có thể dùng các hình thức khác nhau của từ, như
“organize”, “organizes”, “organizing”. Trong một số trường hợp, sẽ rất hữu
dụng nếu search một trong các từ đó và hệ thống trả về các văn bản chứa các
từ còn lại.
Mục tiêu của Stemming là làm giảm các biến thể về hình thức của từ, đôi
lúc sẽ chuyển các hình thức liên quan của từ thành hình thức gốc.

15


Ví dụ:
o am, are, is => be
o car, cars, car’s, cars’ => car
o the boy’s cars are different colors => the boy car be differ
color Một thuật toán phổ biến để thực hiện stemming trong tiếng
Anh là thuật toán Porter.
Quy luật

Ví dụ


sses → ss
ies → i
ss → ss
s→

caresses → caress
ponies → poni
caress → caress
cats → cat

Bảng 2.1 - Một số quy luật của thuật toán Porter2
Ngoài thuật toán Porter vẫn còn một nhiều thuật toán stemming khác, dưới
đây bảng 2.2 là so sánh giữa thuật toán Porter và hai thuật toán stemming
khác là Lovins và Paice:

2

Nguồn hình ảnh: Introduction to information retrieval. Vol. 1, trang 58 [4]

16


Thuật toán

Lovins

Porter

Paice


Ví dụ
Such as analysis can reveal features that are not easily
visible from the variations in the individual genes and can
lead to a picture of expression that is more biologically
transparent and accessible to interpretion
Such an analys can reve featur that ar not eas vis from th
vari in th individu gen and can lead to a pictur of expres
that is mor biolog transpar and acces to interpres
Such an analysi can reveal featur that ar not easili visibl
from the variat in the individu gene and can lead to a pictur
of express that is more biolog transpar and access to
interpret
Such
an analys can rev feat that are not easy vis from the
vary in the individ gen and can lead to a pict of express that
is mor biolog transp and access to interpret

Bảng 2.2 - Ví dụ so sánh thuật toán Porter and các thuật toán stemming khác3
d. Lemmatization
Lemmatization là kỹ thuật stemming dựa trên bộ từ điển, kỹ thuật này dùng
phân tích từ vựng và hình thái của từ để loại bỏ hậu tố khác biệt của từ để
đưa về thể gốc hay thể cơ bản của từ.
Ví dụ, “saw” -> “see” hoặc “saw” phụ thuộc vào token đó trong câu là động
từ hay danh từ.
Vì nó phải phụ thuộc nhiều vào bộ từ điển nên chỉ hỗ trợ một phần nhỏ
trong việc trích xuất thông tin.
e. Krovetz Stemmer
Đây là một kỹ thuật lai (hybrid) giữa hai kỹ thuật trên, liên tục dùng từ điển
để kiểm tra từ hợp lệ.

Với phương pháp này, đầu tiên nó sẽ sử dụng từ điển để kiểm tra từ hợp lệ,
nếu như từ không được tìm thấy trong bộ từ điển thì sẽ sử dụng thuật toán
stemming như Porter để loại bỏ hậu tố và biến thể, sau đó tiếp tục dùng từ
3

Nguồn hình ảnh: Introduction to information retrieval. Vol. 1, trang 59 [4]

17


điển để kiểm tra.
Dưới đây bảng 2.3 là so sánh giữa Porter stemmer và Krovetz stemmer so
với văn bản gốc

Văn bản gốc

Document will describe marketing strategies carried
out by U.S. companies for their agricultural chemicals,
report predictions for market share of such chemicals,
or

report

market

statistics

for

agrochemicals,


presticide, herbicide, fungicide, insecticide, fertilizer,
predicted sales, market share, stimulate demand, price
cut, volume of sales
Thuật

toán

Porter

document describ market strategi carri compani
agricultur chemic report predict market share chemic
report market statist agrochem pesticid herbicid
fungicid insecticid fertil predict sale market share
stimul demand price cut volum sale

Thuật toán
Krovetz

document describe marketing strategy carry company
agriculture chemical report prediction market share
chemical report market statistic agrochemic pesticide
herbicide fungicide insecticide fertilizer predict sale
stimulate demand price cut volume sale

Bảng 2.3 - Ví dụ so sánh thuật toán Porter và thuật toán Krovetz4

Nguồn hình ảnh: Slide Tokenizationt trong bài giảng Information retrieval (Simon Fraser
University)[4]
4


18


2.1.4. Xử lý truy vấn với inverted index
Để tìm kiếm trong tập hợp số lượng lớn các văn bản được index
dưới dạng inverted index, search engine sẽ sử dụng boolean logic.
Xem xét câu truy vấn đơn giản sau: “Brutus AND Calpurnia”
o Khi thực hiện câu truy vấn trên, search engine sẽ xác định vị trí
của “Brutus” trong index dictionary, lấy ra các postings của nó,
tiếp sau đó, xác định vị trí của “Calpurnia” trong index dictionary
và tương tự cũng lấy ra các postings chứa nó. Công việc cuối cùng
là thực hiện giao hai danh sách postings để tìm ra các postings
chứa đồng thời cả “Brutus” và “Calpurnia”. Ở đây, chúng ta giao
hai danh sách postings nhờ vào phép toán AND. Ngoài ra, chúng
ta còn có thể dùng NOT và OR.

Hình 2.2 - Ví dụ về tìm kiếm sử dụng Boolean logic
2.1.5. Scoring
Trong trường hợp số lượng văn bản trong cơ sở dữ liệu quá lớn, kết quả
trả về của truy vấn có thể là rất nhiều, vượt quá khả năng có thể xem hết của
người dùng, vậy nên search engine xử lý, sắp xếp mức độ phù hợp của văn
bản so với truy vấn từ người dùng, sao cho những văn bản phù hợp nhất phải
được nằm ở trên đầu danh sách trả về. Giai đoạn này gọi là Ranking.
a. Parametric Index
Thông thường, các văn bản không đơn thuần chỉ chứa text, mà còn có
thể có cấu trúc nhất định, giúp cho máy tính có thể xử lý dễ dàng hơn.
Trong một văn bản có thể có nhiều fields (như là title, author,
content…).
Dưới đây là một ví dụ về Parametric index, term “william” có thể chứa


19


trong field abstract, title hay author. Việc index như vậy sẽ dễ dàng hơn khi
người dùng muốn tìm kiếm trong một field nhất định, thay vì toàn văn bản
(ví dụ như người dùng chỉ muốn tìm văn bản có title chứa william).

Hình 2.3 - Ví dụ về Parametric Index
b. Weighted zone scoring
Trong việc đánh giá mức độ phù hợp của văn bản so với truy vấn, mỗi
field, zone khác nhau có thể có mức độ quan trọng khác nhau.
Với một câu truy vấn q, và một văn bản d, ta có điểm của cặp (q, d) sẽ
nằm trong khoảng [0, 1].
o score(q,d) ∈ [0,1]
o Giả sử, mỗi văn bản có L field/zone, ta có: g1…gL ∈ [0,1]

 
L =1

i =1

o Trong mỗi truy vấn, gọi s1...sL là các giá trị boolean của mỗi field/zone,
nếu term cần tìm xuất hiện trong field i thì si sẽ có giá trị là 1, ngược lại
có giá trị là 0
o Xem ví dụ dưới đây:

20



o Cho:
gabstract = 0.5
gtitle = 0.3
gauthor = 0.2
với câu truy vấn q = “william” ta tính điểm của văn bản 2 như
sau: score(q, D2) = 0 x 0.5 + 1 x 0.3 + 1 x 0.2 = 0.5
c. TF.IDF weighting
Một phương pháp nữa để ranking văn bản là dùng tần suất xuất hiện
của term.
Ta gọi TF(t, d) là tần suất xuất hiện của term t trong văn bản d; và DF(t) là
số lượng văn bản chứa term t trong tất cả các văn bản trong cơ sở dữ liệu.
Khi DF(t) lớn chứng tỏ term t xuất hiện trong nhiều văn bản, điều đó càng
chứng tỏ term t ít quan trọng trong việc tìm kiếm.
Từ DF ta có khái niệm mới đó là Inverse document frequency - IDF(t)
o IDF (t ) = log

N
DF (t )

o Với N là tổng số documents trong cơ sở dữ liệu và DF là số lượng
văn bản chứa term t.
IDF(t) cao nếu term t xuất hiện trong ít documents, nó mang ý nghĩa lớn
trong việc tìm ra các văn bản phù hợp.
IDF(t) thấp nếu term t xuất hiện trong nhiều documents, term t xuất hiện
càng nhiều, nó càng ít quan trọng.
Ta có thể nói như sau, TF(t, d) sẽ đo mức độ quan trọng của term trong một
văn bản, IDF(t) sẽ đo mức độ quan trọng của term trong toàn bộ các văn bản.
Ta tính được score của văn bản d với term t như sau:
o score(t, d) = TF(t, d) . IDF(t)
o score(t, d) cao khi term t xuất hiện thường xuyên trong văn bản d, và

không xuất hiện thường xuyên (ít thường xuyên) trong toàn bộ cơ sở

21


dữ liệu, hay càng ít văn bản chứa t.
o score(t, d) không cao khi term t xuất hiện không nhiều trong văn bản d,
hoặc xuất hiện trong nhiều văn bản.
o score(t, d) thấp nếu term t xuất hiện trong hầu hết các văn bản (IDF rất
thấp, tiến dần tới 0).
Trong một câu truy vấn, có thể có nhiều term, vậy ta có công thức tính điểm
của document d với câu truy vấn q như bên dưới:
o score(q, d) = ∑t∈q score(t, d) = ∑t∈q TF(t, d) IDF(t)
2.1.6. Thư viện LUCENE
2.1.6.1. Giới thiệu về Lucene
Lịch sử phát triểnLucene là thư viện mã nguồn mở hỗ trợ các chức năng cần thiết của
một hệ thống tìm kiếm thông tin.
Mã nguồn của thư viện Lucene được đặt ở trang web:
Tại đây, chúng ta có thể tải thêm các tài liệu tương ứng
với từng phiên bản của Lucene. [5]
2.1.6.2. Lucene và các thành phần của ứng dụng tìm kiếm
Lucene là một thư viện mã nguồn mở, cung cấp các thành phần cần thiết của một ứng
dụng tìm kiếm. Lucene hỗ trợ hai thành phần chính: lập chỉ mục và tìm kiếm.

Hình 2.4 -Các thành phần cơ bản của một ứng dụng tìm kiếm

22


2.1.6.3.


Các tiến trình hoạt động

a. Xây dựng tập chỉ mục tìm kiếm
✓ Cách mô hình hoá nội dung văn bản với Lucene:
Trước hết, nội dung văn bản thô ban đầu sẽ được bóc tách và biểu diễn dưới
dạng các đối tượng Document và Field, sau đó lưu vào tập chỉ mục. Khi bắt đầu tìm
kiếm, giá trị của các Field sẽ được so khớp với câu truy vấn và trả về kết quả.
✓ Tiến trình lập chỉ mục:
Trong quá trình lập chỉ mục, các tài liệu nguồn ban đầu được rút trích lấy ra nội
dung văn bản thuần và Lucene tạo ra đối tượng Document để quản lý, tổ chức các
Field để lưu trữ những văn bản này. Sau đó, văn bản trong các Field sẽ được phân
tích để tạo ra các token. Cuối cùng, các token này được lưu trữ vào tập chỉ mục ở
dạng cấu trúc phân đoạn.

Hình 2.5- Các thao tác chính trong tiến trình lập chỉ mục
b. Tìm kiếm trên tập chỉ mục
Khi người sử dụng truy vấn trên tập chỉ mục Lucene, một đối tượng TopDocs
sẽ được trả về. Đối tượng này chứa danh sách các đối tượng ScoreDoc đã được sắp
xếp mặc định theo điểm số (score).

23


Hình 2.6 -Qui trình chuyển đổi nội dung tìm kiếm
2.1.6.4.

Tiến trình phân tích của Lucene

Phân tích là tiến trình chuyển đổi giá trị của trường thông tin sang một dạng

biểu diễn cơ bản nhất, biểu diễn các mục từ. Những mục từ này được sử dụng để xác
định những tài liệu có liên quan với câu truy vấn trong suốt quá trình tìm kiếm. Để
có thể tách giá trị của các trường thông tin thành các mục từ cần phải thực hiện một
số thao tác như: rút trích từ, loại bỏ dấu câu, chuyển đổi sang ký tự thường, gỡ bỏ
stopword, qui đổi về từ gốc.

Hình 2.7- Tiến trình phân tích trong quá trình lập chỉ mục
2.2. Kỹ thuật chuyển đổi định dạng Tika Parser
2.2.1. Giới thiệu
Trong quá trình tìm kiếm, tồn tại các tập tin ở những dạng khác nhau, điều này
tạo nên sự phức tạp và khó khăn trong quá trình tìm kiếm. phương pháp này loại bỏ
sự phức tạp của các định dạng tập tin khác nhau và thay bằng một cơ chế đơn giản
hơn để trích xuất nội dung văn bản có cấu trúc và siêu dữ liệu từ tất cả các loại tài
liệu. [10]
Tika parser : là một thư viện để phân tách những loại định dạng tập tin để
24