ĐẠI HỌC QUỐC GIA TP.HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA ---------------- TRẦN ĐÌNH HUY XÂY DỰNG MÁY TÌM KIẾM TÁC VỤ DỰA TRÊN TÀI LIỆU ĐẶC TẢ API CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ CHUYÊN NGÀNH: 60.01 LUẬN VĂN THẠC SĨ TPHCM, ngày 18 tháng 07 năm 2012 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH Cán bộ hướng dẫn khoa học: TS. Nguyễn Hứa Phùng Cán bộ chấm nhận xét 1: TS. Bùi Hoài Thắng Cán bộ chấm nhận xét 2: TS.
Nguyễn Chánh Thành Luận văn thạc sĩ được bảo vệ tại HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày 18 tháng 07 năm 2012. Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: 1. Bùi Hoài Thắng (PB1) 3. Nguyễn Chánh Thành (PB2) 4.
Nguyễn Hứa Phùng (UV) 5. Huỳnh Tường Nguyên (TK) Xác nhận của Chủ tịch Hội đồng đánh giá luận văn và Trưởng Khoa quản lý chuyên ngành sau khi luận văn đã sửa chữa. CHỦ TỊCH HỘI ĐỒNG TRƯỞNG KHOA (Họ tên và chữ ký) (Họ tên và chữ ký) Đại Học Quốc Gia Tp. Hồ Chí Minh CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƢỜNG ĐẠI HỌC BÁCH KHOA Độc Lập – Tự Do – Hạnh Phúc ------------------ ------------------------ NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ và tên học viên: TRẦN ĐÌNH HUY MSHV: 10070482 Ngày, tháng, năm sinh: 12/04/1986 Nơi sinh: Cần Thơ Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60.01 I-TÊN ĐỀ TÀI: XÂY DỰNG MÁY TÌM KIẾM TÁC VỤ DỰA TRÊN TÀI LIỆU ĐẶC TẢ API.
II-NHIỆM VỤ VÀ NỘI DUNG: Tìm hiểu về nhu cầu tìm kiếm ―thông tin liên quan đến tác vụ‖ của ngƣời lập trình. Trình bày các hạn chế về tìm kiếm tác vụ của các máy tìm kiếm mã nguồn truyền thống. Sau đó đề xuất hƣớng khắc phục dựa trên khai thác tài liệu đặc tả API. Xây dựng mô hình tìm kiếm tác vụ với hai chức năng chính là ―tìm kiếm định nghĩa tác vụ‖ và ―sinh mã tự động cho lệnh gọi tác vụ‖.
Hiện thực máy tìm kiếm tác vụ mô phỏng cho ý tƣởng đề tài. Đánh giá hệ thống bằng cách so sánh với các máy tìm kiếm truyền thống khác. III-NGÀY GIAO NHIỆM VỤ: 27/05/2011 IV-NGÀY HOÀN THÀNH NHIỆM VỤ: 30/06/2012 V-CÁN BỘ HƯỚNG DẪN: TS NGUYỄN HỨA PHÙNG Tp. HCM, ngày 18 tháng 7 năm 2012 CÁN BỘ HƯỚNG DẪN CHỦ NHIỆM BỘ MÔN ĐÀO TẠO (Họ tên và chữ ký) (Họ tên và chữ ký) TRƯỞNG KHOA (Họ tên và chữ ký) LỜI CẢM ƠN Chân thành bày tỏ lòng biết ơn Thầy TS Nguyễn Hứa Phùng đã trực tiếp hƣớng dẫn, tận tình chỉ bảo và tạo mọi điều kiện thuận lợi nhất, giúp đỡ tôi hoàn thành Luận Văn này.
Chân thành cảm ơn Quý Thầy Cô chuyên ngành Khoa Học Máy Tính, Trƣờng Đại Học Bách Khoa Tp. Hồ Chí Minh đã hết lòng giảng dạy, truyền đạt kiến thức và giúp đỡ tôi trong suốt thời gian học tập tại Trƣờng. Chân thành cám ơn Phòng Đào Tạo Sau Đại Học, Trƣờng Đại Học Bách Khoa Tp. Hồ Chí Minh đã tạo điều kiện tốt cho tôi về trang thiết bị và tài liệu học tập trong suốt khóa học.
Chân thành cám ơn các bạn học viên cao học K2010, K2011 và gia đình đã ủng hộ, giúp đỡ tôi trong học tập và thực hiện Luận Văn này. TÓM TẮT LUẬN VĂN Ngƣời lập trình thƣờng xuyên sử dụng các tác vụ có sẵn của các thƣ viện lập trình trong quá trình phát triển phần mềm. Tuy nhiên, các thƣ viện này thƣờng lớn và phức tạp. Bên cạnh đó, các đặc tả tác vụ thay đổi liên tục qua từng năm.
Do đó, nó thì khó khăn cho lập trình viên để ―tìm đƣợc tác vụ mong muốn‖ và ―biết sử dụng các tác vụ đó nhƣ thế nào‖. Trong đề tài luận văn này, chúng tôi sẽ trình bày hai hƣớng tiếp cận để giải quyết hai vấn đề trên. Đầu tiên là phƣơng pháp để tìm kiếm chính xác tác vụ dựa trên khai thác đặc tả API. Phƣơng pháp này có thể tìm kiếm các tác vụ phù hợp dựa trên chức năng đƣợc mô tả trong đặc tả API của chúng.
Tiếp theo là phƣơng pháp để sinh mã tự động lệnh gọi cho các tác vụ tìm thấy. Trong phƣơng pháp thứ hai, ngƣời lập trình có thể gọi tác vụ bằng câu truy vấn dạng ngôn ngữ tự nhiên. Ngoài ra, chúng tôi đã thi công một máy tìm kiếm tác vụ đơn giản, gọi là MSE. Bên cạnh đó, chúng tôi cũng đã tiến hành các đánh giá cần thiết để chứng minh MSE có độ chính xác và độ bao phủ cao hơn các máy tìm kiếm mã nguồn truyền thống.
ABSTRACT Programmers nearly always use existing functions of the API libraries while developing software. However, these libraries are normally large and complex. Besides, function specifications in these libraries are continuously changing every year. Thus, it‘s difficult for programmers to find ―what functions they want‖ and know ―how to call those functions‖.
In this thesis, we present two novel approaches to address these problems. The first is the approach to find right functions based on the API specification. This approach can search suitable functions by their functionalities described in the API specification. The second is approach to automatically generate code for ―function call‖.
In the second approach, programmer can call a function by natural language query. This thesis has implemented a function search engine for Java, called MSE. Besides, we have performed some evaluations to demonstrate that MSE is better than the existing online search engines in precision and recall. LỜI CAM ĐOAN Tôi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các công trình khác nhƣ đã ghi rõ trong luận văn, các công việc trình bày trong luận văn này là do chính tôi thực hiện và chƣa có phần nội dung nào của luận văn này đƣợc nộp để lấy một bằng cấp ở trƣờng này hoặc trƣờng khác.
Tác giả luận văn Trần Đình Huy DANH MỤC HÌNH Hình 1.1: Phân loại tìm kiếm theo mức độ chuyên biệt .2: Mô hình tìm kiếm tác vụ truyền thống và mô hình trong đề tài.1: Phân tích cú pháp dựa trên thông tin .1: Mô hình tìm kiếm tác vụ .2: Luật rút trích từ khóa các biến trong câu truy vấn .3: Cây cú pháp trong Stanford-Parser .1: Kiến trúc hệ thống .2: Cấu trúc dữ liệu cho mẫu truy vấn và mẫu tác vụ .3: Mô tả quá trình tƣơng tác giữa các bộ phận trong hệ thống.4: Qui trình hoạt động của bộ tiền xử lý tài liệu API .5: Qui trình hoạt động của bộ lập chỉ mục .6: Qui trình hoạt động của bộ rút trích từ khóa .7: Qui trình hoạt động của bộ xếp hạng .8: Qui trình hoạt động của bộ truy xuất bộ nhớ .9: Qui trình hoạt động của bộ tìm kiếm tác vụ .10: Qui trình hoạt động của bộ biểu diễn câu truy vấn .11: Qui trình hoạt động của bộ biểu diễn tác vụ .12: Qui trình hoạt động của bộ so khớp .13: Qui trình hoạt động của bộ yêu cầu nạp tác vụ .14: Qui trình hoạt động tổng quát tìm kiếm định nghĩa tác vụ .15: Qui trình hoạt động chi tiết tìm kiếm định nghĩa tác vụ .16: Qui trình hoạt động tìm kiếm lệnh gọi tác vụ .17: Qui trình hoạt động chi tiết tìm kiếm lệnh gọi tác vụ .1: Kết quả đo lƣờng độ chính xác cho ứng viên .2: Kết quả đo lƣờng độ chính xác cho công việc .3: Kết quả đo lƣờng độ bao phủ dựa cho ứng viên .4: Kết quả đo lƣờng độ bao phủ cho công việc .5: Độ phù hợp giữa tập kết quả trả về và yêu cầu của ứng viên.6: Thống kê chi phí tìm kiếm cho tất cả yêu cầu của các ứng viên .7: Thống kê độ hao phí cho từng ứng viên. 103 DANH MỤC BẢNG Bảng 3.1 Bảng so sánh đặc trƣng các máy tìm kiếm mã nguồn .2 Phân loại máy tìm kiếm dựa trên mục tiêu tìm kiếm .3 Tập nhãn từ loại tiếng Anh dùng trong Stanford-Parser .1: Bảng trình bày các đặc điểm của ứng viên tham gia thử nghiệm .2: Bảng so sánh đặc trƣng của các máy tìm kiếm .3: Bảng thống kê số kết quả liên quan tìm kiếm đƣợc .4: Kết quả thử nghiệm cho chức năng sinh mã tự động. 100 MỤC LỤC CHƢƠNG 1.1 Tổng quan về đề tài .1 Nhu cầu tìm kiếm tài nguyên lập trình .2 Tổng quan về tìm kiếm tác vụ .2 Phƣơng pháp nghiên cứu .4 Bố cục luận văn .1 Mô hình tìm kiếm.1 Mô hình tìm kiếm dựa trên từ khóa .2 Mô hình tìm kiếm dựa trên khái niệm .3 Mô hình tìm kiếm dựa trên từ khóa trong ngữ cảnh .1 Phƣơng pháp rút trích từ khóa .2 Phƣơng pháp truy vấn dữ liệu.3 Phƣơng pháp lập chỉ mục .4 Phƣơng pháp đo lƣờng.3 Cơ sở lý thuyết về xử lý ngôn ngữ tự nhiên.1 Gán nhãn từ loại.2 Phân tích cú pháp .4 Ứng dụng xử lý ngôn ngữ tự nhiên vào quá trình tìm kiếm .1 Phân lớp từ vựng.2 Xử lý biến thể hình thái của từ vựng .3 Tạo biến thể đồng nghĩa cho từ vựng .4 Mở rộng ngữ nghĩa từ vựng. CÔNG TRÌNH LIÊN QUAN .1 Các công trình liên quan tìm kiếm mã nguồn .1 Đặc trƣng của máy tìm kiếm mã nguồn .2 Máy tìm kiếm mã nguồn truyền thống .3 Máy tìm kiếm mã nguồn dựa trên khai thác API .2 Khảo sát một số công trình liên quan đến phƣơng pháp tìm kiếm .1 Khảo sát các phƣơng pháp tìm kiếm thông tin .2 Khảo sát các phƣơng pháp lập chỉ mục .3 Khảo sát các phƣơng pháp xếp hạng (rank) .3 Công cụ hỗ trợ .1 Bộ phân tích cú pháp Stanford-Parser .2 Bộ từ điển WordNet.
MÔ HÌNH TÌM KIẾM TÁC VỤ .1 Phƣơng pháp rút trích từ khóa trong câu ngôn ngữ tự nhiên .2 Phƣơng pháp khai thác tài liệu API .1 Tiền xử lý tài liệu API .2 Rút trích thông tin trong tài liệu API .3 Phƣơng pháp rút trích thông tin trong câu truy vấn .4 Phƣơng pháp so khớp các tác vụ trong tài liệu API với câu truy vấn.5 Phƣơng pháp sinh mã cho lệnh gọi tác vụ .6 Phƣơng pháp xếp hạng cho kết quả trả về .1 Xếp hạng dựa trên độ đo tƣơng tự .2 Xếp hạng dựa trên ràng buộc .3 Phƣơng pháp xếp hạng tổng hợp .7 Phƣơng pháp lập chỉ mục.1 Chọn nội dung dùng để lập chỉ mục trong tài liệu API .2 Đơn vị chỉ mục .3 Cấu trúc chỉ mục .4 Phân trang kết quả trả về. HIỆN THỰC HỆ THỐNG .1 Kiến trúc hệ thống .2 Biểu diễn dữ liệu .3 Giao tiếp giữa các bộ phận .4 Hoạt động của hệ thống .1 Hoạt động tìm kiếm tác vụ .2 Hoạt động sinh mã tự động cho lệnh gọi tác vụ .1 Mục tiêu thử nghiệm .1 Các tiêu chí đánh giá khả năng tìm kiếm tác vụ .2 Các tiêu chí đánh giá khả năng sinh mã tự động cho lệnh gọi .2 Môi trƣờng thử nghiệm .1 Ứng viên tham gia thử nghiệm .
