Bài tập lớn xử lý ngôn ngữ tự nhiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
──────── * ───────
BÀI TẬP LỚN
MÔN: XỬ LÝ NGÔN NGỮ TỰ NHIÊN
ĐỀ TÀI: TÌM HIỂU KIẾN TRÚC CỦA SEARCH ENGINE
FRAMEWORK LUCENE & ỨNG DỤNG NUTCH
GVHD: Th.s Hoàng Anh Việt
Nhóm sinh viên:
Nguyễn Thế Anh 20080070
Trần Anh Thơ 20082569
Nguyễn Vương Quyền 20082142
Nguyễn Văn Hưng 20081293
Lớp: Công nghệ phần mềm K53
Hà Nội - 11/2012
1
Bài tập lớn xử lý ngôn ngữ tự nhiên
MỤC LỤC
MỤC LỤC 2
PHẦN I: NGUYÊN LÝ VÀ MÔ HÌNH CHUNG CỦA SEARCH ENGINE 3
1. Giới thiệu chung 3
2. Phân loại 4
2.1. Máy tìm kiếm thông thường 4
2.2. Máy siêu tìm kiếm - Meta Search Engine 4
3. Nguyên lý hoạt động của search engine 5
4. Mô hình của seach engine 6
4.1. Bộ tìm duyệt Crawler 6
4.2. Kho dữ liệu Repository 8
4.3. Bộ lập chỉ mục Indexer 10
4.4. Bộ tìm kiếm thông tin – Search Engine 11

2. Phân loại
Xét theo phương pháp tìm kiếm thì các Search Engine được chia làm hai loại chính: Tìm
kiếm thông thường và siêu tìm kiếm.
2.1. Máy tìm kiếm thông thường
Các máy tìm kiếm thông thường thực hiện công việc tìm kiếm theoqui trình thu
thập tài liệu, phân loại và tạo chỉ mục. Chúng gồm hai loại,Search Engine sử dụng thư
mục chủ đề và Search Engine tạo chỉ mục tự động.
Các Search Engine sử dụng thư mục chủ đề phân lớp sẵn các trangtrên Internet
vào các thư mục chủ đề và theo các cấp chi tiết hơn của chủ đề.
2.2. Máy siêu tìm kiếm - Meta Search Engine
Meta Search Engine là loại máy truy tìm ảo, nó hoạt động dựa trên sự tồn tại của
các Search Engine sẵn có. Các Meta Search Engine không có cơ sở dữ liệu của riêng
mình. Khi có yêu cầu tìm kiếm máy siêu tìm kiếm sẽ gửi từ khóa đến các Search Engine
khác một cách đồng loạt và nhận về các kết quả tìm được. Nhiệm vụ còn lại của máy siêu
tìm kiếm là phân tích và phân hạng lại các kết quả tìm được.
4
Bài tập lớn xử lý ngôn ngữ tự nhiên
3. Nguyên lý hoạt động của search engine
Search engine điều khiển robot đi thu thập thông tin trên mạng thông qua các siêu
liên kết ( hyperlink ). Khi robot phát hiện ra một site mới, nó gởi tài liệu (web page) về
cho server chính để tạo cơ sở dữ liệu chỉ mục phục vụ cho nhu cầu tìm kiếm thông tin.
Bởi vì thông tin trên mạng luôn thay đổi nên robots phải liên tục cập nhật các site
cũ. Mật độ cập nhật phụ thuộc vào từng hệ thống search engine. Khi search engine nhận
câu truy vấn từ user, nó sẽ tiến hành phân tích, tìm trong cơ sở dữ liệu chỉ mục & trả về
những tài liệu thoả yêu cầu.
5
Bài tập lớn xử lý ngôn ngữ tự nhiên
4. Mô hình của seach engine
4.1. Bộ tìm duyệt Crawler
Bộ tìm duyệt Crawler thu thập các trang trên Internet rồi chuyển chobộ đánh chỉ

đánh giá các trang dựa vào giá trị phân hạng.Từsự đánh giá này Crawler biết được các
trang có mức độ quan trọng cao hơnđể lấy về trong lần kế tiếp. Để đánh giá chất lượng
của Crawler người ta cóthể định nghĩa độ đo chất lượng quality metric của nó bằng một
trong haicách sau:
- Crawl & stop: Bộ Crawler C xuất phát từ trang khởi đầu P0 và dừng lại sau khi
ghé thăm k trang, k là số lượng trang mà Crawler có thể tải về trong một lần
duyệt. Một Crawler tốt sẽ ghé thăm các trang theo thứ tự R1,….Rk trongđó R1
là trang có thứ hạng cao nhất, lần lượt đến R2,… . Gọi R1, …,RK là cáctrang
hot. Trong số k trang được Crawler ghé thăm chỉ có m trang (m<=k) sẽđược
sắp thứ hạng cao hơn hoặc bằng trang Rk
- Crawl & Stop with Threshold: vẫn giả sử rằng bộ Crawler ghé thăm ktrang.
Tuy nhiên lúc này đích quan trọng G đã được cho sẵn, và bất cứ trang nào có
độ quan trọng lớn hơn G thì đều được coi là trang hot.
- Độ đo thứ hạng (Ordering Metrics): Một Crawler lưu giữ những URLs mà nó
đã ghé thăm trong quá trình dò tìm vào một hàng đợi. Sau đó nó lựa chọnmột
URL trong hàng đợi cho lần ghé thăm tiếp theo. Ở mỗi lần lựa chọn thì
Crawler chọn URL u có giá trị Orderingcao nhất để ghé thăm. Độ đo thứ hạng
(Ordering Metric) được thiết lập dựa vào một trong các độ đo khác. Ví dụ nếu
ta đang thực hiện tìm những trang có giá trị IB(P) cao, thì ta sẽ lấygiá trị IB’(P)
làm độ đo thứ hạng, trong đó P là trang mà được trang u trỏ tới.
4.1.3 Page Refresh
Khi Crawler lựa chọn và tải về các trang “quan trọng”, sau một khoảng thời gian
nhất định nó phải thực hiện cập nhật các trang đó. Có rất nhiều cách để cập nhật các trang
web, và các cách khác nhau sẽ cho các kếtquả khác nhau. Sau đây là hai cách:
- Uniform refresh policy: Chiến lược cập nhật đồng loạt. Crawler ghé thăm lại
tất cả các trang theo cùng một tần suất f.
- Proportional refresh policy: Cập nhật theo tỷ lệ, một trang thường xuyên thay
đổi thì Crawler ghé thăm thường xuyên hơn. Để chính xác hơn ta giả sử μi là
tần suất thay đổi của trang ei, và fi là tần suất mà Crawler ghé thăm lại trang ei.
Crawler phải ước lượng μi của mỗi trang để thiết lập chiến lược ghé thăm lại mỗi

dữ liệu.
4.2.1 Các yêu cầu đối với repository
- Một Repository quản lý một tập các đối tượng dữ liệu “data object” lớn.
- Có khả năng mở rộng
- Có cách truy cập kép (dual access mode): Truy nhập ngẫu nhiên được sử dụng
để nhanh chóng nhận về trang web và gán cho mỗi trang một định danh duy
nhất. Truy cập tuần tự được sử dụng để nhận về tập hợp hoàn chỉnh, hay vài
tập hợp con lớn.
- Có thể cập nhật khối lượng lớn.
- Loại bỏ những trang không còn tồn tại.
- Kho dữ liệu được thiết kế phân tán (Distributed Repository).
4.2.2 Nguyên tắc phân tán trang
Các trang có thể được gán cho các nút dựa trên một số nguyên tắc khác nhau. Như
nguyên tắc phân tán đồng bộ (Uniform distribution), tất cả các nút được xử lý đồng nhất.
Một trang có thể được gán cho một nút bất kỳ trong hệ thống. Các nút sẽ chứa các phần
của tập hợp các trang tuỳ theo khả năng lưu trữ của nút. Ngược lại, với cách phân tán
băm (hash distribution) việc định vị các trang vào các nút dựa trên định danh của trang.
4.2.3 Phương pháp tổ chức trang vật lý
Trong một nút đơn, có 3 thao tác có thể thực hiện: thêm trang/chèntrang (page
addition/insertion), truy cập tuần tự tốc độ cao, và truy cập ngẫu nhiên. Cách tổ chức các
trang theo kiểu vật lý tại mỗi nút chính là việc xem xét xem mức độ hỗ trợ mỗi thao tác
trên của nút đó.
4.2.4 Chiến lược cập nhật
Việc thiết kế chiến lược cập nhật phụ thuộc vào tính chất của Crawler. Có hai cách
cấu trúc Crawler: Batch-mode hoặc Steady Crawler: một Crawler kiểu batch-mode được
xử lý định kỳ mỗi tháng một lần, và cho phép duyệt một số lần nhất định (hoặc đến khi
toàn bộ các trang trong tập đích đã được duyệt) sauđó Crawler dừng lại. Với bộ Crawler
như trên thì kho dữ liệu web được cập nhật trong một số ngày nhất định trong tháng.
Ngược lại, một bộ Crawler ổn định (steady Crawler) chạy liên tục, nó liên tục cập nhật và
bổ sung các trang mới cho Repository.

(Rank_Frequency) Các bước để xác định một mục từ quan trọng
- Cho một tập hợp n tài liệu, thực hiện tính toán tần số xuất hiện củacác mục từ
trong tài liệu đó.
- Ký hiệu F
ik
(Frequency): là tần số xuất hiện của mục từ k trong tài liệu I
- Xác định tổng tần số xuất hiện TFk (Total Frequency) cho mỗi từbằng cách
cộng những tần số của mỗi mục từ duy nhất trên tất cả n tài liệu.
TF
k
=
- Sắp xếp các mục từ theothứ tự giảm dần của tần số xuất hiện.Chọn một giá trị
làm ngưỡng và loại bỏ tất cả những từ có tổng tầnsố xuất hiện cao hơn ngưỡng
này (stop-word).
4.3.1.2 Tính trọng số của mục từ
Trọng số của mục từ: là tần số xuất hiện của mục từ trong toàn bộ tàiliệu, những từ
thường xuyên xuất hiện trong tất cả các tài liệu thì “ít có ýnghĩa hơn” là những từ chỉ tập
trung trong một số tài liệu.
Ngược lại khi tần số xuất hiện của mục từ k trong tập tài liệu càngcao thì mục từ
đó càng có ý nghĩa.
Lập chỉ mục tự động cho tài liệu là xác định tự động mục từ chỉ mụccho các tài
liệu.Loại bỏ các từ stop-word vì những từ này có độ phân biệtkém và không thể sử dụng
để xác định nội dung của tài liệu.
Bước tiếp theo là chuẩn hoá mục từ, tức là đưa mục từ về dạngnguyên gốc bằng
cách loại bỏ tiền tố, hậu tố, và các biến thể khác của từ nhưtừ ở dạng số nhiều, quá khứ,

4.3.2 Cấu trúc của chỉ mục đảo
Sau khi phân tích các trang web, và thực hiện tách các từ, chuẩn hoá các từ về
dạng nguyên gốc, loại bỏ các từ stop word. Ta thu được một danh mục các từ mỗi từ
được gắn kèm danh sách các trang chứa từ đó. Danh mục này gọi là chỉ mục đảo

trọng” trỏ đến thì B cũng có độ quan trọng hơn C. Giả sử ta có một tập các trang Web với
các liên kết giữa chúng, khi đó ta có một đồ thị với các đỉnh là các trang Web và các cạnh
là các liên kết giữa chúng.
PR được thể hiện với 11 giá trị: từ 0 – 10, chỉ số PR càng cao thì độ uy tính của trang
web đó càng lớn.
Nếu bạn dùng trình duyệt firefox, bạn có thể dụng công cụ SearchStatus tại địa chỉ
. Hoặc bạn có thể vào
để cài đặt công cụ SEOQuake, có thể xem với mọi trình duyệt
Công thức tính PageRank
PR(A) = (1-d) + d(PR(t1)/C(t1) + … + PR(tn)/C(tn)).
- Trong đó PR(A) là Pagerank của trang A
- t1, t2…tn là các trang liên kết tới trang A
- C là số link outbound của trang nguồn t1, t2 …tn đó (link ra ngoài)
- d là hệ số suy giảm (hệ số tắt dần của chuỗi)
13
Bài tập lớn xử lý ngôn ngữ tự nhiên
Ví dụ nhé Page A của bạn có 3 trang page B (PR=6) page C (PR=3) và page D (PR = 4).
Link tới Page B có 3 link dẫn ra ngoài, Page C có 6 link dẫn ra ngoài, Page D có 12 link
dẫn ra ngoài
Vậy PR của A = 0.15 + 0.85*( 6/3 + 3/6 + 4/12) =2 (xấp xỉ)
Một khi đã biết được công thức, ta có thể chủ động hơn khi trao đổi liên kết với các site
khác. Chẳng hạn nếu bạn liên kết với một site PR =7,8 gì đó và site đó chỉ có 1 link
outbound dẫn đến bài viết trên site của ta.
14
Bài tập lớn xử lý ngôn ngữ tự nhiên
PHẦN II: FRAMEWORK LUCENE
1. Giới thiệu
Lucene là một thư viện mã nguồn mở viết bằng java cho phép dễ dàng tích hợp
thêm chức năng tìm kiếm đến bất cứ ứng dụng nào. Nó cung cấp các API hỗ trợ
cho việc đánh chỉ mục và tìm kiếm . Lucene có thể được sử dụng để tích hợp chức

hình bên dưới
Ta sẽ lần lượt xem xét các thành phần của hệ thống search engine
2.1. Các thành phần indexing
Giả sử ta chúng ta cần tìm kiếm trên một số lượng lớn các file. Cách tiếp cận
thông thường là duyệt từng file xem có chứa từ hoặc cụm từ ta đưa ra hay không.
Phương pháp này sẽ làm việc nhưng không hiệu quả nếu số lượng file hoặc kích
thước file là quá lớn. Để tìm kiếm hiệu quả hơn, ta cần đánh chỉ mục tập văn bản
16
Bài tập lớn xử lý ngôn ngữ tự nhiên
tìm kiếm, chuyển đổi chúng thành khuôn dạng cho phép ta tìm kiếm nhanh hơn và
loại bỏ tiến trình quét tuần tự. Tiến trình này được gọi là indexing và kết quả đầu
ra của nó gọi là index
Quá trình indexing bao gồm một dãy các bước phân biệt mà chúng ta sẽ lần lượt
làm rõ sau đây.
a. Thu thập nội dung (Acquire content)
Bước đầu tiên là thu thập nội dung (acquire content). Tiến trình này sử dụng
một crawler hoặc spider để thu thập các nội dung cần thiết sẽ được đánh chỉ
mục. Các crawler sẽ chạy liên tục như một dịch vụ để đợi khi có những nội
dung mới hoặc thay đổi, nó sẽ cập nhật các nội dung này.
Lucene như là một thư viện core và nó không cung cấp bất cứ chức năng nào
để hỗ trợ thu thập nội dung. Chúng ta có thể một số thư viện mã nguồn mở sẵn
có để thực hiện chức năng thu thập nội dung thông tin sau
• Solr: Một project con của Apache Lucene hỗ trợ thu thập thông tin
trong CSDL quan hệ, XML feeds, xử lý các tài liệu thông qua Tika
• Nutch: Một project con của Apache Lucene, có một crawler để thu
thập nội dung của các website
• Grub: Một web crawler mã nguồn mở
• Heritrix, Droids, Aperture…
Sau khi thu thập được các nội dung thông tin, chúng ta sẽ tạo ra các phần nhỏ
được gọi là các tài liệu của nội dung

Sau khi tách ra được các document và các trường text thì search engine vẫn
chưa thể đánh chỉ mục được ngay mà còn phải thông qua giai đoạn phân tích
văn bản
c. Phân tích tài liệu (analyze document)
Không có search engine nào đánh chỉ mục trực tiếp text, đúng hơn là text phải
được chia nhỏ thành một dãy các phần tử nguyên tử được gọi là token. Bước
phân tích tài liệu sẽ thực hiện nhiệm vụ này. Từng token có thể coi là một từ
trong ngôn ngữ và bước này sẽ xác định cách những trường văn bản trong một
document được phân chia thành một dãy các token.
18
Bài tập lớn xử lý ngôn ngữ tự nhiên
Lucene cung cấp một tập các bộ phân tích được xây dựng sẵn, chúng sẽ giúp
bạn kiểm soát quá trình phân tích dễ dàng hơn. Bước cuối cùng là đánh chỉ
mục cho document
d. Đánh chỉ mục tài liệu (Index document)
Trong bước tiếp theo, document được thêm vào chỉ mục. Lucene cung cấp mọi
điều cần thiết cho bước này với các API đơn giản.
2.2. Các thành phần tìm kiếm (Components for searching)
Searching là quá trình tìm kiếm các từ trong một chỉ mục để tìm những tài liệu nơi
mà các từ đó xuất hiện. Chất lượng của tìm kiếm được mô tả dựa trên 2 độ đo là
precision và recall. Recall đo chất lượng của kết quả tìm ra có phù hợp hay không
trong khi precision đo mức độ loại bỏ các tài liệu không phù hợp. Chúng ta hãy
lần lượt xem các thành phần tìm kiếm của một search engine
a. Search user interface
User interface là phần mà người sử dụng tương tác trực tiếp trên trình duyệt,
ứng dụng desktop hoặc thiết bị di động khi họ tương tác với ứng dụng tìm
kiếm. Lucene không cung cấp bất cứ giao diện tìm kiếm mặc định nào, nó phải
được chúng ta tự xây dựng. Khi mà người sử dụng submit yêu cầu tìm kiếm,
nó phải được dịch ra thành đối tượng Query phù hợp cho search engine
b. Xây dựng truy vấn (Build query)

tương ứng với tài liệu khớp và các tài liệu khớp là không được sắp xếp,
một truy vấn sẽ chỉ nhận diện được các bộ phù hợp
• Mô hình không gian vector (Vector space model): Cả các truy vấn và
documents được mô hình hóa như các vector trong không gian nhiều
chiều. Sự phù hợp giữa một câu truy vấn và một tài liệu được tính toán
bởi một số đo khoảng cách vector giữa các vector này
• Mô hình xác suất (Probabilistic model): Trong mô hình này, ta phải tính
xác suất mà một tài liệu khớp với một câu truy vấn sử dụng cách tiếp
cận xác suất đầy đủ
Cách tiếp cận của Lucene kết hợp mô hình không gian vector và mô hình logic
thuần túy và cho phép chúng ta quyết định xem mô hình nào sẽ được sử dụng.
Cuối cùng, Lucene trả lại các tài liệu mà chúng ta sẽ hiển thị ra danh sách kết
quả cho người dùng
d. Render results
Khi chúng ta nhận được bộ các document khớp với truy vấn đã được sắp xếp
theo thứ tự phù hợp thì chúng ta có thể hiển thị chúng đến giao diện người
dùng.
Đến đây, chúng ta đã kết thúc việc xem xét các thành phần của quá trình indexing
và searching trong ứng dụng search nhưng vẫn chưa hoàn thành.
3. Các lớp chính của Lucene
3.1. Các lớp chính đánh chỉ mục
Một số lớp chính để thực thi việc đánh chỉ mục bao gồm
• IndexWriter
• Directory
• Analyzer
• Document
• Field
Hình bên dưới chỉ ra vai trò của các lớp trên tham gia vào quá trình đánh chỉ mục
20
Bài tập lớn xử lý ngôn ngữ tự nhiên

Tiếp theo, tiến trình đánh chỉ mục đòi hỏi một tài liệu (Document) chứa các
trường phân biệt (Field)
d. Document
Lớp này mô tả tập hợp các trường (Field). Document có thể được coi như một
tài liệu ảo như một trang web, một thông điệp email hoặc một file text… Các
trường của tài liệu mô tả tài liệu hoặc các siêu dữ liệu gắn với tài liệu đó. Các
nguồn dữ liệu gốc như một trường trong CSDL, một file microsoft office, một
chương của một ebook là không phù hợp cho việc đánh chỉ mục trong Lucene.
Chúng ta phải tách ra được các văn bản từ các tài liệu nhị phân trên và thêm nó
vào như một thể hiện của Field để Lucene có thể xử lý. Các Field có thể là các
siêu dữ liệu như author, title, content, date…
Lucene chỉ xử lý các dữ liệu xâu và số, tức là nó chỉ hỗ trợ các kiểu
java.lang.String, java.io.Reader và các kiểu số thông thường như int, float,
double, long…
Một Document là một container chứa nhiều Field và một Field là lớp chứa nội
dung văn bản được đánh chỉ mục
e. Field
Từng Document là một chỉ mục chứa một hoặc nhiều Field được đặt tên được
đại diện bởi lớp Field. Từng Field có một tên, giá trị tương ứng và một tập các
lựa chọn để kiểm soát cách mà Lucene sẽ đánh chỉ mục giá trị của Field. Một
tài liệu có thể chứa nhiều hơn một Field cùng tên. Trong trường hợp này các
giá trị của các field sẽ được nối với nhau trong khi đánh chỉ mục theo thứ tự
các field được thêm vào document.
3.2. Các lớp chính tìm kiếm
Các lớp được cung cấp để thực hiện chức năng tìm kiếm cũng khá đơn giản.
Dưới đây là một số lớp chính
• IndexSearcher
• Term
• Query
• TermQuery

một container chứa các con trỏ trỏ đến N kết quả được xếp hạng cao nhất.
Trong đó kết quả là các tài liệu khớp với truy vấn yêu cầu. Với từng bản ghi
trong N kết quả, TopDocs ghi lại các giá trị docID sẽ được sử dụng để lấy ra
các giá trị Document và các điểm trọng số của các tài liệu tương ứng
23
Bài tập lớn xử lý ngôn ngữ tự nhiên
PHẦN III: ỨNG DỤNG NUTCH
1. Giới thiệu về Nutch
1.1. Định nghĩa
Nutch là một search engine mã nguồn mở cài đặt trên ngôn ngữ lập trình
Java. Nutch cung cấp tất cả các công cụ cần thiết để cho phép bạn tạo ra một
search engine (SE) của riêng bạn.
Cài đặt Nutch trên một trong các quy mô: hệ thống file cục bộ, intranet
hoặc trên một web nào đó.Cả ba cách cài đặt đó đều có những đặc tính khác
nhau.Ví dụ: thu thập hệ thống file là đáng tin cậy hơn hai cách cài đặt kia vì có thể
lỗi mạng xảy ra hay bộ nhớ cache không có sẵn.
Các vấn đề với Nutch: Thu thập thông tin cần tìm kiếm trên hàng tỉ trang
web cần giải quyết một vấn đề là chúng ta sẽ bắt đầu từ đâu? Bao nhiêu lần thì
chúng ta thu thập lại? Chúng ta sẽ phải xử lí các trường hợp như link bị hỏng, các
sites không hồi đáp và các nội dung trùng lặp hay khó hiểu? Có một tập các thách
thức để cung cấp khả năng tìm kiếm mở rộng và xử lí hàng trăm câu truy vấn đồng
thời trên một tập dữ liệu lớn
1.2. Đặc điểm
1.2.1. Hỗ trợ nhiều protocol
Hiện nay Nutch hỗ trợ các các protocol khác nhau như: http, ftp, file.
Nhờ kiến trúc plugin-based, ta có thể dễ dàng mở rộng ra thêm các
protocol cho Nutch
1.2.2. Hỗ trợ nhiều loại tài liệu khác nhau
Hiện nay, Nutch có thể phân tách (parse) khá nhiều loại tài liệu khác nhau như:
• Plain text

một bộ thu thập dữ liệu web . Một kịch bản phổ biến là bạn có một cơ sở dữ liệu
web mà bạn muốn tìm kiếm. Cách tôt nhất là để làm điều này là bạn đánh chỉ mục
trực tiếp từ cơ sở dữ liệu sử dụng Lucene API và sau đó cài đặt giải thuật để tìm
kiếm chỉ số, lại sử dụng Lucene. Nutch thì phù hợp hơn với những websites mà
bạn không thể truy cập trực tiếp đến tầng dữ liệu hoặc nó đến từ các nguồn dữ
liệu rời rạc.
2. Các nền tảng phát triển của Nutch
2.1. Lucene
25