Tự động sửa đổi và gợi ý truy vấn tìm kiếm dựa trên các phương pháp đối sánh chuỗi xấp xỉ

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

TRẦN THÚY NHUNG

Tự ĐộNG SửA ĐổI VÀ GợI Ý TRUY VấN

TÌM KIếM DựA TRÊN CÁC PHƯƠNG PHÁP

ĐốI SÁNH CHUỗI XấP Xỉ

Chuyên ngành: KHOA HỌC MÁY TÍNH

Mã số chuyên ngành: 60 48 0101

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC

TS. Phan Xuân Hiếu

Thái Nguyên - 2015

i

LỜI CAM ĐOAN

Tên em là Trần Thúy Nhung, học viên lớp Cao học K12E, chuyên

ngành Khoa học máy tính, khóa học 2013 – 2015. Em xin cam đoan luận văn:

“TỰ ĐỘNG SỬA ĐỔI VÀ GỢI Ý TRUY VẤN TÌM KIẾM DỰA TRÊN

CÁC PHƢƠNG PHÁP ĐỐI SÁNH CHUỖI XẤP XỈ”.

Dƣới sự hƣớng dẫn của TS. Phan Xuân Hiếu - Trƣờng Đại học Công nghệ

- Đại học Quốc gia Hà Nội, với các nội dung trình bày đƣợc trích dẫn đầy đủ

từ các nguồn tài liệu tham khảo chính thống (báo khoa học, các sách có bản

quyền), các nội dung trình bày trong luận văn hoàn toàn trung thực. Và đây là

công trình nghiên cứu của bản thân kết hợp với sự hƣớng dẫn của TS. Phan

Xuân Hiếu tạo lập ra.

Nếu có nội dung nào sao chụp lại hoặc không phải do chính bản thân

tạo ra, em xin hoàn toàn chịu tránh nhiệm và chịu các hình thức kỷ luật.

Phú Thọ, ngày ... tháng 9 năm 2015

HỌC VIÊN

Trần Thúy Nhung

ii

LỜI CẢM ƠN

Điều đầu tiên em xin gửi lời cảm ơn tới các Thầy, Cô Trƣờng Đại học

Công nghệ thông tin và Truyền thông Thái Nguyên trong thời gian vừa qua đã

cung cấp và truyền đạt chƣơng trình học với các môn học có nội dung bổ ích.

Thông qua chƣơng trình học, em đƣợc lĩnh hội nhiều về kiến thức chuyên

môn, các phƣơng pháp tiếp cận bài toán trong tin học.

Em xin gửi lời cảm ơn sâu sắc tới TS. Phan Xuân Hiếu, ngƣời Thầy

đã hƣớng dẫn, chỉ bảo, giám sát, theo dõi, cung cấp phƣơng pháp, nguồn dữ

liệu tiếp cận bài toán để em có thể hoàn thành đƣợc luận văn của mình.

Em xin cảm ơn Ban Giám hiệu trƣờng Cao đẳng Kinh tế - Kỹ thuật Phú

Thọ cùng các đồng nghiệp trong Trƣờng, xin cảm ơn Khoa Công nghệ thông

tin – Trƣờng Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tạo mọi điều

kiện giúp đỡ để em hoàn thành chƣơng trình học tập và luận văn tốt nghiệp.

Điều cuối cùng em xin cảm ơn gia đình, bạn bè luôn nhiệt tình ủng

hộ, động viên, giúp đỡ cả về vật chất lẫn tinh thần trong thời gian học tập

và nghiên cứu.

Trong quá trình thực hiện luận văn, mặc dù đã có rất nhiều cố gắng

nhƣng cũng không tránh khỏi những thiếu sót. Kính mong nhận đƣợc sự cảm

thông và tận tình chỉ bảo của các Thầy, Cô và các bạn.

Em xin trân trọng cảm ơn!.

Phú Thọ, ngày …… tháng 9 năm 2015.

HỌC VIÊN

Trần Thúy Nhung

iii

MỤC LỤC

LỜI CAM ĐOAN .............................................................................................. i

LỜI CẢM ƠN ...................................................................................................ii

DANH MỤC CÁC BẢNG................................................................................ v

DANH MỤC CÁC HÌNH................................................................................. v

MỞ ĐẦU........................................................................................................... 1

CHƢƠNG 1: GIỚI THIỆU BÀI TOÁN........................................................... 4

1.1 Giới thiệu bài toán Tự động sửa đổi và gợi ý truy vấn tìm kiếm................ 4

1.1.2 Hỗ trợ truy vấn tìm kiếm bằng sửa đổi và gợi ý ............................... 7

1.1.3 Hỗ trợ truy vấn tìm kiếm xấp xỉ bằng Tiếng Việt........................... 10

1.2 Các cách tiếp cận giải quyết bài toán........................................................ 11

1.2.1 Cách tiếp cận thông thƣờng............................................................ 11

1.2.2 Cách tiếp cận theo thuật toán chuỗi con chung có độ dài lớn nhất.13

1.2.3 Cách cách tiếp cận theo các thuật toán Similar Text ..................... 14

1.3 Cách tiếp cận đối sánh chuỗi xấp xỉ.......................................................... 14

1.3.1 Bài toán đối sánh chuỗi xấp xỉ ....................................................... 14

1.3.2 Ứng dụng của đối sánh chuỗi xấp xỉ.............................................. 16

CHƢƠNG 2: ĐỐI SÁNH CHUỖI XẤP XỈ CHO VẤN ĐỀ TỰ ĐỘNG SỬA

ĐỔI VÀ GỢI Ý TRUY VẤN ......................................................................... 19

2.1 Các phƣơng pháp đối sánh chuỗi xấp xỉ ................................................... 19

2.1.1 Khoảng các Hamming .................................................................... 19

2.1.2 Khoảng cách Episode ..................................................................... 21

2.1.3 Khoảng cách Longest Common Sequence (LSC)......................... 21

2.2 Phƣơng pháp đối sánh theo độ đo Levenshtein (string edit distance) ...... 23

2.2.1 Độ đo Levenshtein.......................................................................... 23

iv

2.2.2 Giải thuật tính độ đo Levenshtein .................................................. 24

2.2.3 Mô tả giải thuật............................................................................... 26

2.2.4 Trình tự các bƣớc thông qua ví dụ cụ thể....................................... 27

2.3 Tự động sửa đổi và gợi ý truy vấn dựa trên độ đo Levenshtein ............... 31

2.3.1 Đánh chỉ mục các truy vấn tìm kiếm đã có (lịch sử) ..................... 31

2.3.2 Thu gọn không gian đối sánh ......................................................... 36

2.3.3 Đối sánh chuỗi với độ đo Levenshtein.......................................... 39

2.3.4 Đối sánh với độ đo Cosine ............................................................. 40

2.3.5 Đối sánh với độ đo KL................................................................... 41

2.3.6 Áp dụng độ đo Levenshtine vào thực tiễn luận văn....................... 41

CHƢƠNG 3: THỰC NGHIỆM, ĐÁNH GIÁ VÀ ỨNG DỤNG................... 45

3.1 Thực nghiệm và đánh giá đối sánh từng cặp chuỗi đơn lẻ ....................... 47

3.2 Thực nghiệm và đánh giá đối sánh đa chuỗi............................................. 50

3.3 Thực nghiệm và đánh giá thu gọn không gian đối sánh ........................... 51

3.3.1 Một số điểm tƣơng đồng giữa ký tự Tiếng Việt và ký tự La Tinh. 52

3.3.2 Thực nghiệm và đánh giá ............................................................... 54

3.4 Thực nghiệm và đánh giá tự động sửa đổi và gợi ý truy vấn ................... 62

3.5 Ứng dụng sửa đổi và gợi ý truy vấn tự động ............................................ 65

KẾT LUẬN VÀ KIẾN NGHỊ......................................................................... 69

TÀI LIỆU THAM KHẢO............................................................................... 71

v

DANH MỤC CÁC BẢNG

Bảng 2.1: Bảng mô tả khoảng cách Hamming giữa hai chuỗi có độ dài nhƣ nhau .......19

Bảng 2.2: Độ đo Levenshtein giữa hai chuỗi S và T .....................................................24

Bảng 2.3: Kỹ thuật đánh chỉ mục xuôi...........................................................................32

Bảng 2.4: Đánh chỉ số ngƣợc .........................................................................................34

Bảng 3.1: Các từ/chuỗi đƣợc xây dựng làm thực nghiệm thu gọn không gian đối sánh. ....................54

DANH MỤC CÁC HÌNH

Hình 1.1 Mô hình truy vấn tìm kiếm ...............................................................................5

Hình 2.1: Thuật toán Hamming .....................................................................................21

Hinh 2.2: Độ lệch pha Cosine của vector A và vector B ...............................................41

Hình 3.1: Hệ thống thực nghiệm trên thuật toán Levenshtein .......................................46

Hình 3.2 Đối sánh chuỗi đơn lẻ......................................................................................48

Hình 3.3: Đối sánh với cặp chuỗi ―Công nghệ‖ và ―Công nghệ‖..................................49

Hình 3.4: Đối sánh đa chuỗi...........................................................................................51

Hình 3.5: Thu gọn không gian với từ khóa ―Hệ thống‖ D=15 và K=15 ......................56

Hình 3.6: Thu gọn không gian với từ khóa ―Hệ thống‖ D=10 và K=15 .......................57

Hình 3.7: Thu gọn không gian với chuỗi ―Hệ thống‖có D = 5, K = 5...........................58

Hình 3.8: Thu hẹp không gian với chuỗi ―Hệ thống thông tin‖ với D=30;K=20...................59

Hình 3.9: Thu gọn không gian với chuỗi ―hệ thống thông tin‖ với D=10; K=15...................60

Hình 3.10: Thu gọn không gian với ―chuỗi hệ thống thông tin‖ D=5 và K=5.......................61

Hình 3.11: Hệ thống sửa từ cho từ ―Cổng‖....................................................................63

Hình 3.12: Hệ thống sửa đổi từ cho từ khóa ―Tộngn‖ ..................................................64

Hình 3.13: Hệ thống sửa đổi với từ khóa ―Gợi‖ ...........................................................64

Hình 3.14: Gợi ý chuỗi ―Gựi ý truy vấn‖.......................................................................66

Hình 3.15: Kết quả của các chuỗi gợi ý ―Hệ thống thông tin‖ .....................................67

Hình 3.16: Kết quả của các chuỗi gợi ý ―Phần mểmm‖ ...............................................67

Hình 3.17: Kết quả của các chuỗi gợi ý ―Phần mểm‖ ..................................................68