Báo cáo nghiên cứu khoa học Kỹ thuật tách từ trong câu tiếng Việt và ứng dụng tìm kiếm thông tin trên Website
MỤC LỤC
MỤC LỤC ...................................................................................................................1
TÓM TẮT ĐỀ TÀI .........................................................................................................4
DANH MỤC CÁC CHỮ VIẾT TẮT..............................................................................5
DANH MỤC CÁC BẢNG..............................................................................................6
DANH MỤC CÁC HÌNH VẼ.........................................................................................7
1.1. Giới thiệu về tìm kiếm thông tin ..............................................................................9
1.1.1. Quy trình xây dựng hệ thống tìm kiếm thông tin ..................................................9
1.1.3. Các bước xây dựng hệ thống tìm kiếm thông tin.................................................11
1.2. Một số mô hình xây dựng hệ thống tìm kiếm thông tin .........................................12
1.2.1. Mô hình tìm kiếm Boolean..................................................................................13
1.2.4. Mô hình xác suất – Probabilistic model ..............................................................15
1.2.5. Mô hình chỉ mục ngữ nghĩa ngầm – LSI.............................................................15
1.3. Một số hệ thống tìm kiếm thông tin hiện nay.........................................................16
1.3.3. Cốc Cốc................................................................................................................17
1.3.4. Một số hệ thống tìm kiếm thông tin khác............................................................17
1.4.1. Khó khăn trong việc tách từ tiếng Việt................................................................18
1.4.2. Khó khăn về bảng mã tiếng Việt .........................................................................18
1.4.3. Một số khó khăn khác..........................................................................................18
TỪ TIẾNG VIỆT...........................................................................................................19
2.1. Giới thiệu về Crawler .............................................................................................19
2.2. Cơ bản về hoạt động của Crawler ..........................................................................20
1
2.2.1. Tập tin Robot.txt..................................................................................................21
2.3. Các kỹ thuật xây dựng Crawler ..............................................................................23
2.3.1. Cấu trúc dữ liệu của URL Frontier ......................................................................25
2.3.2. Bộ lọc địa chỉ .......................................................................................................26
2.3.4. Trích xuất URL và sự chuẩn hóa.........................................................................27
2.3.5. Mô hình thẻ HTML dạng cây ..............................................................................28
2.3.6. Crawler đa tiến trình ............................................................................................29
2.4. Một số giải thuật Crawler.......................................................................................31
2.4.1. Thuật toán tìm kiếm theo chiều rộng (Breadth-First)..........................................32
2.4.2. Thuật toán tìm kiếm tối ưu (Best-First)...............................................................33
3.1. Một số kỹ thuật tách từ trong tiếng Việt.................................................................35
3.1.3. Mô hình tách từ bằng WFST và mạng Neural.....................................................37
3.2. Phương pháp lập chỉ mục. ......................................................................................38
3.2.1. Xác định các từ chỉ mục ......................................................................................38
3.2.2.1.Các công thức tính trọng số cục bộ của từ chỉ mục lij ......................................39
3.2.2.2.Các công thức tính trọng số toàn cục của từ chỉ mục gi ...................................40
3.2.2.3.Công thức tính hệ số chuẩn hoá nj ....................................................................41
3.2.4. Xây dựng ma trận xấp xỉ Ak ................................................................................44
3.2.5. Chọn hệ số k trong mô hình LSI..........................................................................45
3.3. Tập tin nghịch đảo tài liệu......................................................................................46
3.3.1. Phân biệt giữa tập tin nghịch đảo và tập tin trực tiếp ..........................................46
3.3.2. Sử dụng tập tin nghịch đảo để lập chỉ mục..........................................................47
3.4. Truy vấn và xếp hạng thông tin..............................................................................47
2
4.1. Giới thiệu bài toán ..................................................................................................51
4.2. Chức năng của chương trình...................................................................................52
4.3. Lập chỉ mục ............................................................................................................52
4.3.1. Lớp lập chỉ mục ...................................................................................................52
4.3.2. Giao diện lập chỉ mục ..........................................................................................53
4.4. Tách từ....................................................................................................................54
4.4.1. Lớp tách từ...........................................................................................................54
4.4.3. Giao diện tách từ..................................................................................................56
4.5. Tìm kiếm.................................................................................................................56
4.5.2. Giao diện tìm kiếm ..............................................................................................57
4.6. Kết quả thực nghiệm...............................................................................................57
KẾT LUẬN VÀ KIẾN NGHỊ.......................................................................................59
1. Kết luận .....................................................................................................................59
2. Khuyến nghị ..............................................................................................................60
TÀI LIỆU THAM KHẢO.............................................................................................61
3
TÓM TẮT ĐỀ TÀI
Đề tài nghiên cứu: Kỹ thuật tách từ trong câu tiếng Việt và Ứng dụng trong tìm kiếm
thông tin trên website.
Tóm tắt: Tìm hiểu các kỹ thuật tách từ tiếng Việt và lập chỉ mục cho văn bản. Lựa chọn
phương pháp tối ưu để tìm kiếm thông tin. Áp dụng với bài toán tách từ và tìm kiếm
thông tin tiếng Việt trên website.
4
DANH MỤC CÁC CHỮ VIẾT TẮT
IR
HTML
LSI
Information Retrieval
HyperText Markup Language
Latent Semantic Indexing
Similar
sim
SVD
Tdf
Tf
Singular Value Decomposition
Term document frequency
Term frequency
URL
VSM
WWW
XML
Uniform Resource Locator
Vector Space Model
Word Wide Web
eXtensible Markup Language
5
DANH MỤC CÁC BẢNG
Bảng 3.1: Bảng tính các hàm trọng số cục bộ lij ...........................................................39
Bảng 3.2: Bảng các hàm trọng số toàn cục gi................................................................41
Bảng 3.3: Cách tập tin nghịch đảo lưu trữ.....................................................................46
Bảng 3.4: Cách tập tin trực tiếp lưu trữ.........................................................................46
Bảng 3.5: Thêm một tài liệu mới vào tập tin nghịch đảo..............................................47
6
DANH MỤC CÁC HÌNH VẼ
Hình 1.2: Các bộ phận của máy tìm kiếm .....................................................................11
Hình 2.1: Hành trình của Crawler .................................................................................20
Hình 2.2: Quy trình hoạt động của Crawler ..................................................................24
Hình 2.4: Mô hình đa tiến trình của Crawler.................................................................30
Hình 2.5: Mô hình Crawler dò tìm theo chiều rộng ......................................................32
Hình 2.6: Mô hình hoạt động của thuật toán Breadth-First...........................................32
Hình 2.8: Thuật toán tìm kiếm tối ưu (Best-First).........................................................34
Hình 3.1: Biểu diễn ma trận xấp xỉ Ak có hạng là k......................................................44
Hình 4.2: Màn hình tạo chỉ mục....................................................................................53
Hình 4.3: Màn hình lấy dữ liệu index............................................................................54
Hình 4.4: Màn hình chi tiết tách từ................................................................................56
Hình 4.5: Màn hình tìm kiếm ........................................................................................57
7
MỞ ĐẦU
Ngày nay, lịch sử nhân loại đã bước sang một trang mới nhờ sự bùng nổ của công
nghệ thông tin. Những thành tựu của ngành công nghệ thông tin là vô cùng to lớn, nó
đã chi phối và làm thay đổi mọi mặt của đời sống xã hội, làm cho cuộc sống của con
người văn minh, hiện đại hơn. Sự ra đời của Internet chính là bước tiến vĩ đại của
nhân loại, là yếu tố quan trọng bậc nhất chi phối cuộc sống của chúng ta ngày nay.
Nhờ có Internet thế giới trở nên ‘phẳng’ hơn, ở mọi nơi trên trái đất chúng ta đều có
thể học tập và tìm kiếm thông tin.
Theo guồng quay của cuộc sống, thế giới Internet ngày càng rộng lớn và phong phú
hơn. Cứ mỗi phút trôi qua có thêm hàng triệu trang web được sinh ra để làm giàu cho
vốn tài nguyên tri thức của nhân loại. Tuy nhiên, một trong những khó khăn của 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 trên web. Để trợ gúp công việc này, các hệ thống tìm kiếm trên web đã lần lượt
được phát triển nhằm phục vụ cho nhu cầu tìm kiếm thông tin của người sử dụng.
Phổ biến nhất là các hệ thống tìm kiếm theo từ khóa. Hiện nay có nhiều hệ thống hoạt
động hiệu quả trên Internet như Google, Cốc Cốc, Baidu, Yandex, 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. Việc tìm kiếm thông tin tiếng Việt trên web vẫn chưa chính
xác cao. Do đó, nhu cầu phải có một công cụ tìm kiếm “hiểu” và xử lý tốt văn bản
tiếng Việt trên web đang là chủ đề được nhiều người quan tâm.
Mục tiêu của đề tài này nhằm xây dựng một hệ thống tìm kiếm thông tin bằng tiếng
Việt trên web có sử dụng các kết quả của xử lý ngôn ngữ tự nhiên tự động để xác
định các chỉ mục và xếp hạng tìm kiếm là các từ của tiếng Việt.
8
CHƯƠNG 1. TỔNG QUAN VỀ TÁCH TỪ TIẾNG VIỆT
Nội dung chương này nhằm giới thiệu tổng quan về tìm kiếm thông tin. Giới thiệu
quy trình xây dựng một hệ thống tìm kiếm thông tin. Một số mô hình tìm kiếm thông
tin trên Web phổ biến hiện nay. Đồng thời tóm lược một số khó khăn trong xây dựng
hệ thống tìm kiếm thông tin tiếng Việt.
1.1. Giới thiệu về tìm kiếm thông tin
Tìm kiếm thông tin Information Retrieval (IR) là tìm kiếm tài nguyên trên một tập
lớn các dữ liệu phi cấu trúc được lưu trữ trên máy tính nhằm thỏa mãn nhu cầu về
thông tin.
Tìm kiếm thông tin là ngành khoa học liên quan đến việc phân tích, thiết kế và triển
khai các hệ thống máy tính nhằm biểu diễn, tổ chức và truy cập khối lượng lớn thông
tin được số hoá. Nền tảng của nó là khoa học thông tin (Information Science), nghiên
cứu việc "tập hợp, tổ chức, lưu trữ, truy cập, phân loại thông tin".
Mục đích của tìm kiếm thông tin 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ọ. 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ỗi cách tiếp cận trong
tìm kiếm thông tin bao gồm hai phần chính: một là các kỹ thuật để biểu diễn thông
tin (câu truy vấn, tài liệu) và hai là phương pháp so sánh các cách biểu diễn này. Mục
đích là để thực hiện tự động qui trình kiểm tra các tài liệu bằng cách tính độ tương
quan giữa các câu truy vấn và tài liệu. Quy trình này thành công khi nó trả về các kết
quả được người dùng tạo ra khi so sánh câu truy vấn với các tài liệu.
Các nghiên cứu trong lĩnh vực IR nhắm tới mục tiêu nâng cao chất lượng của các giai
đoạn trong tìm kiếm, bao gồm 1) Tiếp nhận và phân tích yêu cầu từ người dùng; 2)
Thực hiện việc tìm kiếm; và 3) Gửi trả kết quả cho người dùng. Các mô hình khác
nhau được nghiên cứu, xây dựng nhằm tái biểu diễn câu truy vấn và tài liệu tìm kiếm,
sau đó áp dụng các chiến lược tìm kiếm phù hợp.
1.1.1. Quy trình xây dựng hệ thống tìm kiếm thông tin
Cách hoạt động cơ bản của một hệ thống tìm kiếm thông tin cổ điển.
9
Hình 1.1: Mô hình hoạt động của hệ thống tìm kiếm thông tin
Ở giai đoạn đầu tiên, giai đoạn tiền xử lý, tài liệu thô của ngữ liệu được xử lý thành
các tài liệu được tách từ, phân đoạn (tokenized documents) và sau đó được lập chỉ
mục thành một danh sách các vị trí của từ (postings per terms).
Ở giai đoạn thứ hai, người sử dụng đưa ra một câu truy vấn (phi cấu trúc bằng
ngôn ngữ tự nhiên) mô tả nhu cầu thông tin của họ. Hệ thống tìm kiếm thông tin
sẽ biểu diễn câu truy vấn này thành những câu truy vấn có hoặc không có cấu trúc
mà máy có thể hiểu được. Hệ thống tìm kiếm thông tin bắt đầu thực hiện đối chiếu
để tìm ra các tài liệu, các yếu tố thông tin có thể trả lời và liên quan đến câu truy
vấn.
Cuối cùng, các tài liệu, yếu tố thông tin tìm thấy được hiển thị thành một danh sách
tài liệu và được sắp xếp theo thứ tự liên quan (ranked retrieved documents). Thông
thường, những tài liệu, yếu tố thông tin có liên quan nhiều nhất được xếp trên
những tài liệu ít liên quan hơn.
10
1.1.2. Các bộ phận cấu thành của hệ thống tìm kiếm thông tin
Một hệ thống tìm kiếm thông tin hoạt động trên môi trường mạng thông tin (Internet)
hay trên môi trường máy tính cá nhân (PC) đều gồm có thành phần chính sau:
Hình 1.2: Các bộ phận của máy tìm kiếm
Bộ thu thập thông tin – Crawler: đây là một chương trình tự động duyệt qua các
cấu trúc siêu liên kết để thu thập tài liệu và một cách đệ quy nó nhận về tất cả các
tài liệu có liên kết với tài liệu này. Đối với hệ thống tìm kiếm trên máy PC, người
dùng thường chỉ định dữ liệu có sẵn trên máy tính. Robot được biết đến dưới nhiền
tên gọi khác nhau: spider, web wandeere hoặc web worm…
Bộ lập chỉ mục – Index: thực hiện việc phân tích, trích chọn những thông tin cần
thiết (thường là các từ đơn, từ ghép, cụm từ quan trọng) từ những dữ liệu mà robot
thu thập được hoặc do người dùng chỉ định và tổ chức thành cơ sở dữ liệu riêng để
có thể tìm kiếm trên đó một cách nhanh chóng, hiệu quả. Hệ thống chỉ mục là danh
sách các từ khóa, chỉ rõ các từ khóa nào xuất hiện ở trang nào, địa chỉ nào…
Bộ tìm kiếm thông tin – Search Engine: bộ tìm kiếm tương tác với người sử dụng
thông qua giao diện giao tiếp, có nhiệm vụ tiếp nhận và trả về những tài liệu thỏa
yêu cầu người dùng. Bộ tìm kiếm tiếp nhận yêu cầu của người dùng, thực hiện một
số biến đổi như sửa lỗi chính tả, chuẩn hóa từ khóa,…sau đó thực hiện so khớp với
cơ sở dữ liệu do bộ lập chỉ mục tạo ra để lọc lấy danh sách các tài liệu thỏa mãn
tốt nhất cho người dùng.
1.1.3. Các bước xây dựng hệ thống tìm kiếm thông tin
Xây dựng một hệ thống tìm kiếm thông tin sẽ thực hiện qua 4 bước như sau: Tách từ
tự động cho tập tài liệu, Lập chỉ mục cho tài liệu, Tìm kiếm, Sắp xếp các tài liệu trả
về.
Bước 1: Tách từ tự động cho tập các tài liệu
Tách từ trong tiếng Anh chỉ dựa vào khoảng trắng. Tuy nhiên đối với tiếng Việt,
giai đoạn tách từ này tương đối khó khăn. Cấu trúc ngữ pháp tiếng Việt rất phức
11
tạp, không chỉ đơn thuần dựa vào khoảng trắng để tách từ. Hiện nay có rất nhiều
công cụ dùng để tách từ tiếng Việt, mỗi phương pháp có ưu điểm, nhược điểm
riêng. Các phương pháp này sẽ được trình bày ở chương 3 mục 3.1.
Bước 2: Lập chỉ mục cho tài liệu
Sau khi có được tập các từ đã được trích, ta sẽ chọn các từ để làm từ chỉ mục.
Tuy nhiên, không phải từ nào cũng được chọn làm từ chỉ mục. Các từ có khả
năng đại diện cho tài liệu sẽ được chọn, các từ này được gọi là keyword. Do đó,
trước khi lập chỉ mục sẽ là giai đoạn tiền xử lý đối với các từ trích được để chọn
ra các key word thích hợp. Ta sẽ loại bỏ danh sách các từ ít có khả năng đại diện
cho nội dung văn bản dựa vào danh sách gọi là stop list. Đối với tiếng Anh hay
tiếng Việt đều có danh sách stop list.
Bước 3: Tìm kiếm và sắp xếp các tài liệu trả về
Đây là quá trình người dùng nhập câu hỏi và yêu cầu tìm kiếm, câu hỏi mà người
dùng nhập vào cũng sẽ được xử lý, nghĩa là ta cũng sẽ thực hiện tách từ cho câu
hỏi. Phương pháp tách từ cho câu hỏi cũng nên là phương pháp tách từ cho các
tài liệu thu thập được để đảm bảo sự tương thích. Sau đó, hệ thống sẽ tìm kiếm
trong tập tin chỉ mục để xác định các tài liệu liên quan đến câu hỏi của người
dùng.
Các tài liệu sau khi đã xác định là liên quan đến câu hỏi của người dùng sẽ được
sắp xếp lại, bởi vì trong các tài liệu đó có những tài liệu liên quan đến câu hỏi
nhiều hơn. Hệ thống sẽ dựa vào một số phương pháp để xác định tài liệu nào liên
quan nhiều nhất, sắp xếp lại và trả về cho người dùng theo thứ tự ưu tiên.
1.2. Một số mô hình xây dựng hệ thống tìm kiếm thông tin
Mục tiêu của các hệ thống tìm kiếm thông tin là trả về các tài liệu càng liên quan đến
câu hỏi càng tốt. Vì thế đã có rất nhiều mô hình tìm kiếm thông tin nhằm tính toán
một cách chính xác độ tương quan này. Sau đây là một số mô hình tìm kiếm thông
tin cơ bản.
12
1.2.1. Mô hình tìm kiếm Boolean
Đây là mô hình cơ bản và đơn giản dựa trên đại số Bool, sử dụng nguyên tắc so sánh
chính xác khi tìm kiếm tài liệu. Hệ thống yêu cầu người sử dụng cung cấp câu truy
vấn dưới hình thức là các từ khoá kèm theo các toán tử AND, OR, NOT.
Mô hình vùng (Regions models) là một mở rộng của mô hình Boolean. Coi bộ sưu
tập tài liệu như một chuỗi từ liên tục, mỗi chuỗi tuỳ ý các từ nối tiếp là một vùng. Các
toán tử CONTAINING, CONTAINED_BY hay FOLLOWED_BY được bổ sung để
so sánh tài liệu và yêu cầu.
Điểm hạn chế lớn nhất của mô hình Boolean và mô hình vùng là chúng không hỗ trợ
việc xếp hạng các tài liệu, không xử lý được vấn đề đồng nghĩa và đa nghĩa, có cú
pháp phức tạp và dễ gây nhầm lẫn.
Ưu điểm của mô hình Boolean:
Đơn giản và dễ sử dụng.
Nhược điểm của mô hình Boolean:
Vì dựa trên phép toán logic nhị phân nên một văn bản được tìm kiếm chỉ xác định
hai trạng thái: liên quan hoặc không với câu truy vấn. Số lượng văn bản trả về
tuỳ thuộc vào số từ xuất hiện của câu truy vấn có liên quan hay không;
Chuyển một câu truy vấn sang dạng boolean là không đơn giản;
Văn bản trả về không được quan tâm đến thứ tự quan hệ với câu truy vấn.
1.2.2. Mô hình tính điểm và trọng số cho mục từ - Term weight
Mô hình tìm kiếm Boolean chỉ trả về giá trị logic là có hoặc không có trong tài liệu
tìm kiếm, kết quả trả về không có thứ hạng. Vai trò của các mục từ tìm kiếm là ngang
nhau, chỉ xác định là có xuất hiện hay không trong tài liệu. Điều này đã dẫn đến kết
quả tìm kiếm không được như mong muốn của người dùng. Để cải tiến mô hình này,
người ta áp dụng cách tính điểm cho kết quả trả về, dựa trên trọng số của mục từ trên
tài liệu.
Mỗi mục từ trong ma trận từ chỉ mục được gán một trọng số, giá trị này phụ thuộc
vào số lần xuất hiện của mục từ trên tài liệu chứa mục từ và tập tài liệu.
Tính kết quả độ liên quan của câu truy vấn trên từng văn bản và sau đó sắp xếp kết
quả trả về.
Ưu điểm của mô hình tính điểm trọng số:
13
Sử dụng trọng số cho từ chỉ mục khác trọng số nhị phân (non-binary). Trọng số
từ chỉ mục không giới hạn bởi hai trị 0 hoặc 1, các trọng số này được sử dụng để
tính toán độ đo tương tự của mỗi văn bản với câu truy vấn. Kết quả trả về có quan
tâm đến thứ tự xuất hiện.
Nhược điểm của mô hình tính điểm và trọng số:
Kết quả tính trọng số chưa xét vai trò của các mục từ trong câu truy vấn. Có thể
số lượng các mục từ như nhau nhưng vai trò khác nhau hoàn toàn.
1.2.3. Mô hình không gian vector – Vector Space Model (VSM)
Mô hình không gian vector tính toán độ tương quan giữa câu hỏi và tài liệu bằng cách
định nghĩa một vector biểu diễn cho mỗi tài liệu, và một vector biểu diễn cho câu hỏi
[Salton, 1875].
Trong đó, tài liệu và câu truy vấn được biểu diễn dưới dạng các vector. Một văn bản
d được biểu diễn như một vector của các từ chỉ mục d = (t1,t2,...,tn) với ti là từ chỉ mục
thứ i (1≤ i ≤ n) ( các giá trị có thể là số lần xuất hiện của term ti trong văn bản d). Mỗi
từ chỉ mục trong văn bản biểu diễn một chiều (dimension) trong không gian. Tương
tự, câu truy vấn cũng được biểu diễn như một vector q = (t1,t2,...,tn).
Sau khi đã biểu diễn tập văn bản và câu truy vấn thành các vector trong không gian
vector, sử dụng độ đo cosin để tính độ đo tương tự giữa các vector văn bản và vector
truy vấn, kết quả sau khi tính toán có thể được xếp hạng theo độ đo tương tự với
vector truy vấn.
Ưu điểm của mô hình không gian vector:
Đơn giản, dễ hiểu;
Đưa ra khái niệm phù hợp một phần; công thức xếp hạng cosin cho phép đồng
thời xác định sự phù hợp và phục vụ sắp xếp danh sách kết quả..
Nhược điểm mô hình không gian vector:
Số chiều biểu diễn cho tập văn bản có thể rất lớn nên tốn nhiều không gian lưu
trữ;
Các văn bản trả về tuy cải thiện là có quan tâm đến việc xếp hạng các văn bản
theo mức độ liên quan nhưng vẫn không có quan hệ về ngữ nghĩa với câu truy
vấn. Các từ khoá được giả định độc lập và do đó mô hình không đánh giá được
ngữ nghĩa của câu truy vấn tài liệu.
14
1.2.4. Mô hình xác suất – Probabilistic model
Cho câu truy vấn của người dùng q và văn bản d trong tập văn bản. Mô hình xác suất
tính xác suất mà văn bản d liên quan đến cấu truy vấn của người dùng. Mô hình giả
thiết xác suất liên quan của một văn bản với câu truy vấn phụ thuộc cách biểu diễn
chúng. Tập văn bản kết quả được xem là liên quan và có tổng xác suất liên quan với
câu truy vấn lớn nhất.
Trong mô hình này, câu hỏi được đặt ra là "Với xác suất nào, một tài liệu là phù hợp
với một câu truy vấn". Từ năm 1960, Bill Maron and Larry Kuhns định nghĩa mô
liệu D ban đầu được lập bằng tay. Gọi P(D|T) là xác suất tài liệu D thoả mãn so với
thuật ngữ T, luật Bayes được áp dụng như sau:
( | )
푃 푇 퐷 푃(퐷)
( | )
푃 퐷 푇 =
(1.1)
푃(푇)
Trong công thức, P(T) cố định ứng với một thuật ngữ T; P(D) được coi là xác suất
ban đầu được xác định trước từ việc sử dụng tài liệu; giá trị P(T|D) được xác định
trong quá trình xem xét tài liệu D và lập chỉ mục.
Ưu điểm của mô hình xác suất:
Văn bản được sắp xếp dựa vào xác suất liên quan đến câu truy vấn.
Nhược điểm mô hình xác suất:
Mô hình không quan tâm đến số lần xuất hiện của từ chỉ mục trong văn bản.
Việc tính toán xác suất khá phức tạp và tốn nhiều chi phí.
Mô hình không hỗ trợ cho việc biểu diễn tài liệu, việc này được thực hiện trong
một quá trình độc lập.
1.2.5. Mô hình chỉ mục ngữ nghĩa ngầm – LSI
Latent Semantic Indexing (LSI) là phương pháp tạo chỉ mục tự động dựa trên khái
niệm để khắc phục hai hạn chế tồn tại trong mô hình không gian vector chuẩn về hai
có thể được sử dụng để biểu diễn một khái niệm, vì vậy hệ thống không thể trả về
những văn bản liên quan đến câu truy vấn của người dùng khi họ sử dụng những từ
trong câu truy vấn đồng nghĩa với những từ trong văn bản. Với polysemy, một từ có
thể có nhiều nghĩa, vì vậy hệ thống có thể trả về những văn bản không liên quan. Điều
15
này thực tế rất thường xảy ra bởi vì các văn bản trong tập văn bản được viết bởi rất
nhiều tác giả, với cách dùng từ rất khác nhau. Một cách tiếp cận tốt hơn cho phép
người dùng truy vấn văn bản dựa trên khái niệm (concept) hay nghĩa (meaning) của
văn bản.
Mô hình LSI cố gắng khắc phục hai hạn chế trên trong mô hình không gian vector
bằng cách chỉ mục khái niệm được tạo ra bởi phương pháp thống kê (phân tích SVD
ma trận term – document A) thay cho việc sử dụng các từ chỉ mục đơn. Mô hình LSI
dựa trên giả thiết là có các ngữ nghĩa ngầm (latent semantic) trong việc sử dụng từ:
có nhiều từ biểu diễn cho một khái niệm và một khái niệm có thể được biểu diễn bởi
nhiều từ.
Ưu điểm mô hình chỉ mục ngữ nghĩa ngầm:
Latent Semantic Indexing (LSI ) là phương pháp tạo chỉ mục tự động dựa trên
khái niệm để khắc phục hạn chế tồn tại trong mô hình không gian vector về hai
Việc giảm số chiều cải thiện đáng kể chi phí lưu trữ và thời gian thực thi.
Nhược điểm mô hình chỉ mục ngữ nghĩa ngầm:
Việc tìm kiếm cũng phải quyét qua tất cả các cột trong ma trận LSI nên cũng tốn
chi phí và thời gian.
1.3. Một số hệ thống tìm kiếm thông tin hiện nay
1.3.1. Google Search
Google đứng đầu danh sách Search Engine trên toàn cầu. Không chỉ ở Việt Nam mà
trên toàn thế giới, Google luôn là lựa chọn hàng đầu khi một ai đó muốn tra cứu thông
tin trên internet.
Ngoài google.com là chung cho toàn thế giới bên cạnh đó thì mỗi quốc gia google
điều có một tên miền riêng để tìm kiếm tập trung theo quốc gia đó. Với google ta có
thể tìm kiếm web, hình ảnh, video, tin tức, map và nhiều chức năng khác nữa. Theo
thống kê của ComCore trong năm 2015 thì Google chiếm tỷ lệ lớn khối lượng tìm
kiếm trên toàn thế giới với hơn 63.9%.
16
1.3.2. Bing và Yahoo
Bing là cái tên mới của MSN.com. Với tên miền mới và nhiều cải tiến vượt bậc trong
những năm gần đây nhưng Bing.com vẫn chưa thể so sánh với Google về Search
Engines.
Yahoo là một trong những hệ thống tìm kiếm lâu đời. Tuy nhiên thời gian gần đây,
Yahoo gần như không có nhiều cập nhật cho công cụ tìm kiếm.
1.3.3. Cốc Cốc
Cốc Cốc là hệ thống mới và phổ biến ở Việt Nam hiện nay với sản phẩm nổi tiếng là
trình duyệt web Coc Coc. Bên cạnh đó thì mảng quan trọng nữa là Search Engines
thuần Việt để cạnh tranh với các đổi thủ khác từ nước ngoài như Google. Cốc Cốc
ngoài chức năng tìm kiếm web như các công cụ khác thì còn có chức năng tìm theo
Toán học, Ngôi sao, Nhà nhà. Toán học thì chuyên giải các bài toán từ lớp 1 -12 đây
là địa chỉ không thể thiếu cho học sinh tự học và tìm hiểu về toán. Ngôi sao là chuyên
trang tìm kiếm các ngôi sao trong làng giải trí trong và ngoài nước với hình ảnh HD
và thông tin tổng quát về ngôi sao. Nhà nhà tương tự như tìm kiếm Map nhưng thế
mạnh ở đây là thuần Việt nên mọi sẽ được tìm kiếm chi tiết hơn Google. Đó cũng là
những thế mạnh đã làm nên sự khác biệt để cạnh tranh với Google, bằng chứng cho
thấy Cốc Cốc đang đứng vị trí số 1 tại Việt Nam theo thống kê của Alexa.
1.3.4. Một số hệ thống tìm kiếm thông tin khác
Ask.com là Search Engines không giống như Google, Bing hay Yahoo mà nó chuyên
về mảng tìm kiếm giải đáp câu hỏi của người sử dụng. Kết quả trả về cũng đa dạng
có cả hình ảnh, video và các câu gợi ý trả lời.
Yandex là máy tìm kiếm của Nga. Các chức năng chính như tìm kiếm Web, Image,
Video, Map và có cả trình duyệt web Yandex Browser.
Baidu là máy tìm kiếm lớn nhất của Trung Quốc và chiếm lĩnh thị phần tìm kiếm.
Các chức năng nổi bật như tìm kiếm web, danh bạ web, map…
17
1.4. Khó khăn trong xây dựng một hệ thống tài liệu thông tin tiếng Việt
1.4.1. Khó khăn trong việc tách từ tiếng Việt
Tách từ là giai đoạn khó khăn nhất khi xây dựng một hệ thống tìm kiếm thông tin
tiếng Việt. Đối với tiếng Anh, việc xác định từ chỉ đơn giản dựa vào khoảng trắng để
tách từ.
Ví dụ. Câu: “I am a student” sẽ được tách thành 4 từ: I, am, a, student.
Tuy nhiên, đối với tiếng Việt, tách từ dựa vào khoảng trắng chỉ thu được các tiếng.
Từ có thể được ghép từ một hay nhiều tiếng. Từ phải có ý nghĩa hoàn chỉnh và có cấu
tạo ổn định.
Ví dụ. Câu: “Tôi là một sinh viên” được tách thành 4 từ: Tôi, là, một, sinh viên.
Trong đó, từ “sinh viên” được hình thành từ 2 tiếng: “sinh” và “viên”
Hiện nay, có rất nhiều phương pháp được sử dụng để tách từ tiếng Việt. Tuy nhiên,
với sự phức tạp của ngữ pháp tiếng Việt nên chưa có phương pháp nào đạt được chính
xác 100%. Và việc lựa chọn phương pháp nào là tốt nhất cũng đang là vấn đề tranh
cãi.
1.4.2. Khó khăn về bảng mã tiếng Việt
Không như tiếng Anh, tiếng Việt có rất nhiều bảng mã đòi hỏi phải xử lý. Một số
công cụ tìm kiếm tiếng Việt hỗ trợ bảng mã rất tốt như Vinaseek, hỗ trợ mọi bảng mã
(VNI, TCVN3, ViQR,…)
1.4.3. Một số khó khăn khác
- Tiếng Việt có các từ đồng nghĩa nhưng khác âm. Các công cụ hiện nay không hỗ trợ
việc xác định các từ đồng nghĩa. Vì vậy kết quả trả về sẽ không đầy đủ.
- Ngược lại, có những từ đồng âm khác nghĩa. Các hệ thống sẽ trả về các tài liệu có chứa
các từ đã được tách trong câu hỏi mà không cần xác định chúng có thực sự liên quan
hay không. Vì vậy, kết quả trả về sẽ không chính xác.
- Một số từ xuất hiện rất nhiều nhưng không có ý nghĩa trong tài liệu. Các từ như: và,
với, nhưng,…có tần số xuất hiện rất lớn trong bất cứ văn bản nào. Nếu tìm cách trả
về các tài liệu có chứa những từ này sẽ thu được kết quả vô nghĩa, không cần thiết.
Do đó, chúng ta cần tìm cách loại bỏ những từ này trước khi tìm kiếm.
18
CHƯƠNG 2. QUY TRÌNH XÂY DỰNG HỆ THỐNG TÌM
KIẾM THÔNG TIN TÁCH TỪ TIẾNG VIỆT
Trong chương này, đề tài lần lượt trình bày các khái niệm cơ bản trong trình thu thập
web. Phần lớn nội dung trong chương sẽ đi sâu vào tìm hiểu các thành phần cấu thành
một trình thu thập thông tin, một số thuật toán Crawler hay áp dụng để thu thập dữ
liệu.
2.1. Giới thiệu về Crawler
Trình thu thập web (Web crawler) là một chương trình khai thác cấu trúc đồ thị của
web di chuyển từ trang này qua trang khác. Thời kỳ đầu nó có những tên khá tượng
hình như bọ web, rô-bốt, nhện và sâu, nhưng ngày nay tên gọi phổ biến nhất là vẫn
là Crawler. Mặc dù vậy cụm từ ‘thu thập’ không lột tả được hết tốc độ của những
chương trình này, vì chúng có tốc độ làm việc đáng kinh ngạc, có thể thu thập dữ liệu
lên đến hàng chục ngàn trang trong vòng một vài phút.
Nguyên lý hoạt động của một Crawler rất đơn giản, nó xuất phát từ những trang đầu
tiên cho trước gọi là hạt giống (seed pages), và duyệt từ trang này đến trang khác
thông qua những liên kết chứa trong những trang mà nó đi qua, quá trình này gọi là
Crawling. Như vậy, Crawler sẽ duyệt vòng quanh và ngày một trải rộng phạm vi ra
trên toàn bộ những Web Site trên Internet. Crawler tổng hợp nội dung (văn bản và
những liên kết) từ những Web Site và lưu chúng vào trong cơ sở dữ liệu, lập chỉ mục
và đánh giá PageRank cho những trang này dựa vào các thuật toán mà mỗi máy tìm
kiếm sử dụng.
Khi một Crawler được đưa lên trên môi trường Web, thông thường nó sẽ được khởi
tạo bởi một vài trang Web. Việc đầu tiên mà Crawler sẽ làm trên những trang này là
thu nhận tất cả các liên kết trên các trang Web, sau đó là đọc nội dung của các trang
này và lần theo những liên kết mà Crawler đã tổng hợp trước đó để bắt đầu một quá
trình thu thập mới. Những liên kết được tổng hợp từ những trang Web được đưa vào
một khu vực chứa gọi là Crawl Frontier; các liên kết được đưa vào Crawl Frontier
một cách có hệ thống theo một thuật toán mà mỗi Crawler sử dụng.
Những liên kết trong Crawler Frontier đôi khi cũng hướng Crawler đến những trang
Web mà Crawler đã duyệt qua trước đó, đây là một vấn đề phải giải quyết khi tiến
hành phát triển một Crawler. Crawler sẽ duyệt qua những liên kết này cho đến khi nó
19
Tải về để xem bản đầy đủ
62 trang
26/03/2022
5800
Bạn đang xem 20 trang mẫu của tài liệu "Báo cáo nghiên cứu khoa học Kỹ thuật tách từ trong câu tiếng Việt và ứng dụng tìm kiếm thông tin trên Website", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bao_cao_ky_thuat_tach_tu_trong_cau_tieng_viet_va_ung_dung_ti.pdf
