Luận văn Hệ thống tìm kiếm thông tin xuyên ngôn ngữ Việt - Anh - Hoa

Hệ thống tìm kiếm thông tin xuyên ngôn ngữ Việt – Anh – Hoa MỤC LỤC MỤC LỤC............................................................................................................ 1 MỞ ĐẦU .............................................................................................................. 3 Chương 1: TỔNG QUAN................................................................................... 5 1.1 Giới thiệu mô hình tìm kiếm thông tin (Information Retrieval): ..............5 1.2 Hệ thống tìm kiếm thông tin xuyên ngôn ngữ (CLIR):...............................9 1.2.1 Khái niệm:................................................................................................9 1.2.2 Các vấn đề của CLIR:...........................................................................10 1.3 Các hướng tiếp cận:......................................................................................11 1.3.1 Dịch máy (Machine Translation for Text Translation):....................11 1.3.2 Dựa trên từ điển đa ngữ (Multilingual Thesauri):.............................14 1.3.3 Dựa trên ngữ liệu (Corpus-based techniques):...................................22 1.4 Một số công trình nghiên cứu trong và ngoài nước: .................................30 1.4.1 Ở Việt Nam: ...........................................................................................30 1.4.2 Trên thế giới: .........................................................................................31 1.5 Kết luận: ........................................................................................................32 Chương 2: CƠ SỞ LÝ THUYẾT..................................................................... 35 2.1 Giới thiệu về MRD (Machine Readable Dictionary).................................35 2.1.1 Sơ lược lịch sử phát triển MRD trên thế giới: ....................................35 2.1.2 Vai trò và cấu trúc của MRD:..............................................................39 2.1.3 Khai thác tài nguyên từ điển:...............................................................41 2.1.4 Xây dựng từ điển tự động:....................................................................42 2.1.5 Cấu trúc vĩ mô và vi mô của từ điển MRD:........................................43 2.1.6 Một số từ điển MRD: ............................................................................43 2.2 Các phương pháp tách từ: ...........................................................................51 2.2.1 Mô hình WFST:.....................................................................................51 2.2.2 Mô hình MMSEG: ................................................................................57 2.3 Các phương pháp khử nhập nhằng: ...........................................................64 2.3.1 Giới thiệu: ..............................................................................................64 2.3.2 Khử nhập nhằng:...................................................................................65 2.4 Kết luận: ........................................................................................................70 Chương 3: PHÂN TÍCH và THIẾT KẾ ......................................................... 72 3.1 Tổng quan hệ thống:.....................................................................................72 3.1.1 Phát biểu bài toán: ................................................................................72 3.1.2 Mô hình hệ thống: .................................................................................72 3.1.3 Phát sinh quản lý:..................................................................................73 3.2 Phân tích – thiết kế hệ thống: ......................................................................76 3.2.1 Mô hình Usecase:...................................................................................76 3.2.2 Đặc tả usecase: .......................................................................................77 3.2.3 Sơ đồ tuần tự: ........................................................................................78 3.2.4 Thiết kế lớp: ...........................................................................................81 3.2.5 Thiết kế giao diện: .................................................................................94 GVHD: TS. Hồ Bảo Quốc Nguyễn Thị Hồng Nhung - 0112235 TS. Đinh Điền Nguyễn Thị Tuyết Mai - 0112229 1 Hệ thống tìm kiếm thông tin xuyên ngôn ngữ Việt – Anh – Hoa 3.3 Xây dựng hệ thống: ......................................................................................97 3.3.1 Tổ chức các MRD:.................................................................................97 3.3.2 Phương pháp tìm kiếm dựa trên MRD:............................................106 3.3.3 Tìm kiếm tài liệu bằng công cụ tìm kiếm:.........................................110 CHƯƠNG 4: CÀI ĐẶT VÀ THỬ NGHIỆM ............................................... 112 4.1 Cài đặt:.........................................................................................................112 4.1.1 Tiền xử lý: ............................................................................................112 4.1.2 Cấu trúc dữ liệu:..................................................................................112 4.1.3 Dịch từ từ điển:....................................................................................113 4.1.4 Khử nhập nhằng :................................................................................113 4.1.5 Tìm kiếm: .............................................................................................116 4.2 Thử nghiệm: ................................................................................................117 4.2.1 Module dịch và khử nhập nhằng: ......................................................117 4.2.2 Chương trình demo trên web:............................................................117 4.3 Đánh giá :.....................................................................................................119 4.3.1 Module dịch và khử nhập nhằng: ......................................................119 4.3.2 Chương trình tìm kiểm trên Web:.....................................................120 Chương 5: KẾT LUẬN và HƯỚNG PHÁT TRIỂN ................................... 122 5.1 Kết luận: ......................................................................................................122 5.2 Huớng phát triển: .......................................................................................122 5.2.1 Đối với từ điển và ngữ liệu: ................................................................122 5.2.2 Đối với IR Engine:...............................................................................123 5.2.3 Mở rộng ngôn ngữ tìm kiếm cho hệ thống: ......................................124 PHỤ LỤC ......................................................................................................... 125 TÀI LIỆU THAM KHẢO .............................................................................. 132 GVHD: TS. Hồ Bảo Quốc Nguyễn Thị Hồng Nhung - 0112235 TS. Đinh Điền Nguyễn Thị Tuyết Mai - 0112229 2 Hệ thống tìm kiếm thông tin xuyên ngôn ngữ Việt – Anh – Hoa MỞ ĐẦU Với sự phát triển nhanh chóng của công nghệ tin học, khối lượng thông tin được lưu trữ trên máy tính ngày càng nhiều. Vì vậy cần có các hệ thống tìm kiếm thông tin (Information Retrieval) cho phép người dùng tìm kiếm một cách chính xác và nhanh nhất các thông tin mà họ cần trên kho tư liệu khổng lồ này. Hơn nữa, trong xu thế toàn cầu hóa như hiện nay, rất nhiều các tổ chức, các công ty quốc tế hình thành, lại xuất hiện một nhu cầu mới trong việc tìm kiếm thông tin đó là tìm kiếm thông tin đa ngữ để người dùng có thể khai thác một cách hiệu quả nhất kho tài liệu đa ngữ mà họ có. Một ví dụ cụ thể về kho tư liệu đa ngữ là Internet. Các trang Web bằng nhiều ngôn ngữ khác nhau xuất hiện ngày càng nhiều, trong khi các công cụ tìm kiếm đơn ngữ (search engine) chỉ có thể trả về các tài liệu được viết cùng ngôn ngữ với ngôn ngữ của câu truy vấn (query). Do đó vấn đề đặt ra là liệu có thể xây dựng một hệ tìm kiếm thông tin mà thông tin trả về là tất cả các tài liệu ở các ngôn ngữ khác nhau trong kho tư liệu có liên quan đến câu truy vấn (không phụ thuộc vào ngôn ngữ của câu truy vấn). Đây chính là bài toán đặt ra cho việc nghiên cứu các hệ tìm kiếm đa ngữ/ xuyên ngữ (multilanguage IR/ cross language IR). Mục tiêu của các hệ thống tìm kiếm xuyên ngữ là cung cấp công cụ cho người dùng để có thể mô tả nhu cầu tìm kiếm thông tin ở ngôn ngữ mà mình diễn đạt giỏi nhất (thường là tiếng mẹ đẻ), hệ thống sẽ phải trả về tất cả các tài liệu ở tất cả các ngôn ngữ có trong kho tư liệu đang tìm kiếm có liên quan đến nhu cầu thông tin của người dùng. Trên đây là nhu cầu chung của hầu hết các ngôn ngữ và tiếng Việt của chúng ta cũng không phải là ngoại lệ. Khác với các ngôn ngữ khác, tiếng Việt có nhiều đặc điểm riêng biệt và rất khó xử lý bằng máy tính, nên các đề tài nghiên cứu hay các chương trình ứng dụng liên quan đến các hệ thống tìm kiếm bằng tiếng Việt còn rất ít. Mà nhu cầu tìm kiếm tài liệu trên kho tàng kiến thức của thế giới của người Việt là rất lớn. Với mong muốn phát triển nhiều hơn nữa các hệ thống tìm kiếm xuyên ngôn ngữ bằng tiếng Việt, chúng tôi xây dựng “Hệ thống tìm kiếm thông tin xuyên ngôn ngữ Việt – GVHD: TS. Hồ Bảo Quốc Nguyễn Thị Hồng Nhung - 0112235 TS. Đinh Điền Nguyễn Thị Tuyết Mai - 0112229 3 Hệ thống tìm kiếm thông tin xuyên ngôn ngữ Việt – Anh – Hoa Anh – Hoa” cho phép người dùng nhập câu truy vấn bằng tiếng Việt và trả về các tài liệu có liên quan bằng tiếng Việt, tiếng Anh và tiếng Hoa. Trong luận văn này chúng tôi lựa chọn tiếng Anh và tiếng Hoa là hai đại diện tiêu biểu cho hai loại hình ngôn ngữ biến hình và đơn lập. Từ đó cho thấy rằng hệ thống tìm kiếm thông tin xuyên ngữ có thể thực thi trên hai loại hình ngôn ngữ khác nhau. Bố cục của luận văn gồm các chương sau: • Chương 1 – TỔNG QUAN : giới thiệu tổng quan về hệ thống tìm kiếm (IR), hệ thống tìm kiếm thông tin xuyên ngôn ngữ (CLIR), các hướng tiếp cận và các vấn đề cần giải quyết của hệ thống. • Chương 2 – CƠ SỞ LÝ THUYẾT: trình bày cơ sở lý thuyết và các phương pháp đã nghiên cứu trong luận văn. • Chương 3 – PHÂN TÍCH VÀ THIẾT KẾ: phân tích và thiết kế hệ thống. • Chương 4 – CÀI ĐẶT VÀ KIỂM TRA: cài đặt, kiểm thử chương trình. • Chương 5 – KẾT LUẬN và HƯỚNG PHÁT TRIỂN: trình bày các kết quả đạt được, các đánh giá về hệ thống và hướng phát triển trong tương lai. • Phần TÀI LIỆU THAM KHẢO và PHỤ LỤC: trình bày các thông tin có liên quan được sử dụng trong luận văn. GVHD: TS. Hồ Bảo Quốc Nguyễn Thị Hồng Nhung - 0112235 TS. Đinh Điền Nguyễn Thị Tuyết Mai - 0112229 4 Hệ thống tìm kiếm thông tin xuyên ngôn ngữ Việt – Anh – Hoa Chương 1: TỔNG QUAN Trong chương này, chúng tôi sẽ trình bày khái quát về các hệ thống tìm kiếm (Information Retrieval), hệ thống tìm kiếm thông tin xuyên ngôn ngữ (Cross-Language Information Retrieval) và một số khảo sát về tình hình nghiên cứu trong và ngoài nước. Cuối chương chúng tôi sẽ rút ra kết luận chung và lựa chọn hướng tiếp cận cho hệ thống của mình. Nội dung trình bày bao gồm: 9 Giới thiệu mô hình tìm kiếm thông tin. 9 Hệ thống tìm kiếm thông tin xuyên ngôn ngữ. 9 Một số công trình nghiên cứu trong và ngoài nước. 9 Kết luận. 1.1 Giới thiệu mô hình tìm kiếm thông tin (Information Retrieval): Hệ thống tìm kiếm thông tin xuyên ngữ (Cross Language Information Retrieval - CLIR) có liên hệ rất mật thiết với hệ thống tìm kiếm thông tin (Information Retrieval - IR) và cũng có rất nhiều đặc trưng của hệ thống này (IR). Qui trình của hệ thống tìm kiếm thông tin như sau: • Người dùng muốn xem những tài liệu liên quan đến một chủ đề nào đó. • Người dùng cung cấp một mô tả về chủ đề đó dưới dạng câu truy vấn. • Từ câu truy vấn này hệ thống sẽ lọc ra những cụm từ chỉ mục. • Những cụm từ chỉ mục này sẽ được so khớp với những cụm từ chỉ mục của các tài liệu đã được xử lý trước đó. • Những tài liệu nào có mức độ liên quan cao nhất sẽ được trả về cho người dùng. GVHD: TS. Hồ Bảo Quốc Nguyễn Thị Hồng Nhung - 0112235 TS. Đinh Điền Nguyễn Thị Tuyết Mai - 0112229 5 Hệ thống tìm kiếm thông tin xuyên ngôn ngữ Việt – Anh – Hoa Mục đích của IR là hiển thị 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 chính xác cho 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 IR bao gồm 2 thành 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à để tự động qui trình kiểm tra các tài liệu bằng cách tính toán độ tương quan giữa các câu truy vấn và tài liệu. Qui trình tự động này thành công khi nó trả về các kết quả giống với các kết quả được con người tạo ra khi so sánh câu truy vấn với các tài liệu. Có một vấn đề thường xảy ra đối với hệ thống tìm kiếm là những từ mà người dùng đưa ra trong câu truy vấn thường khác xa những từ trong tập tài liệu chứa thông tin mà họ tìm kiếm. Trường hợp như thế gọi là “paraphrase problem” (vấn đề về diễn giải). Để giải quyết vấn đề này hệ thống đã tạo ra các hàm biểu diễn xử lý các câu truy vấn và các tài liệu một cách khác nhau để đạt đến một độ tương thích nào đó. d Hàm biểu diễn câu truy vấn Không gian biểu diễn R [0,1] Xử lý của con người j Hàm biểu diễn tài liệu Câu truy vấn Biểu diễn 2 Tài liệu c Hàm so sánh q Biểu diễn 1 [0,1] Không gian tài liệu D Không gian câu truy vấn Q GVHD: TS. Hồ Bảo Quốc Nguyễn Thị Hồng Nhung - 0112235 TS. Đinh Điền Nguyễn Thị Tuyết Mai - 0112229 6 Hệ thống tìm kiếm thông tin xuyên ngôn ngữ Việt – Anh – Hoa Hình 1.1: Mô hình hệ thống tìm kiếm thông tin Gọi miền xác định của hàm biểu diễn câu truy vấn q là Q, tập hợp các câu truy vấn có thể có; và miền giá trị của nó là R, không gian thống nhất biểu diễn thông tin. Gọi miền xác định của hàm biểu diễn tài liệu d là D, tập hợp các tài liệu; và miền giá trị của nó là R2 . Miền xác định của hàm so sánh c là R x R và miền giá trị của nó là [0,1], tập các số thực từ 0 đến 1. Trong một hệ thống tìm kiếm lí tưởng: c(q(query), d(doc)) = j(query, doc) , ∀query∈ Q, ∀doc ∈ D, khi j: Q x D --> [0,1] biểu diễn việc xử lý của người dùng giữa các mối quan hệ của 2 thông tin, được tính dựa trên một tiêu chuẩn nào đó (ví dụ: sự giống nhau về nội dung hay sự giống nhau về kiểu …). Hình 1.1 minh họa mối quan hệ này. Có hai kiểu hệ thống tìm kiếm: tìm kiếm dựa trên so khớp chính xác và dựa trên sắp xếp. Mô hình trên đây có thể mô tả cả 2 cách tiếp cận. Trong hệ thống tìm kiếm dựa trên so khớp chính xác, miền giá trị của c được giới hạn từ 0 đến 1, và nó được chuyển sang nhị phân để quyết định liệu 1 tài liệu có thỏa biểu thức bool được xác định bởi câu truy vấn hay không? Các IR dựa trên so khớp chính xác thường cung cấp các tài liệu không sắp xếp thỏa câu truy vấn của người dùng, hầu hết các hệ thống tìm kiếm hiện nay đều dùng cách này. Cách hoạt động chi tiết của hệ thống sẽ được mô tả ở phần sau. Đối với hệ thống IR dựa trên sắp xếp, thì các tài liệu sẽ được sắp xếp theo thứ tự giảm dần về mức độ liên quan. Có 3 loại hệ thống tìm kiếm dựa trên sắp xếp: “ranked Boolean”, “probabilistic” và “similarity based”. Trong 3 cách trên miền giá trị của c là [0,1], tuy nhiên chúng khác nhau ở cách tính “giá trị trạng thái tìm kiếm” (“retrieval status value”): • Trong hệ thống dựa trên “ranked Boolean” giá trị này là mức độ mà thông tin thỏa mãn biểu thức bool được chỉ ra bởi các thông tin còn lại. GVHD: TS. Hồ Bảo Quốc Nguyễn Thị Hồng Nhung - 0112235 TS. Đinh Điền Nguyễn Thị Tuyết Mai - 0112229 7 Hệ thống tìm kiếm thông tin xuyên ngôn ngữ Việt – Anh – Hoa • Trong hệ thống dựa trên “probabilistic” , khái niệm này hơi khác một chút, giá trị này là xác suất mà thông tin có liên quan đến một câu truy vấn. Rất nhiều hệ thống tìm kiếm dựa trên xác suất được thiết kế để chấp nhận câu truy vấn được diễn tả bằng ngôn ngữ tự nhiên hơn là một biểu thức bool. • Trong hệ thống tìm kiếm dựa trên sự giống nhau, giá trị trạng thái tìm kiếm được tính bằng cách tính mức độ giống nhau của nội dung thông tin. Trong các hệ thống tìm kiếm dựa trên so khớp chính xác, việc đánh giá hệ thống chủ yếu dựa trên việc đánh giá mức độ liên quan. Giả sử j là giá trị nhị phân và được cho trước. Nói cách khác, ta giả sử rằng các tài liệu hoặc có hoặc không có liên quan đến câu truy vấn, và độ liên quan giữa tài liệu và câu truy vấn do con người xác định là chính xác. Theo giả định này, tính hiệu quả của các hệ thống tìm kiếm dựa trên so khớp chính xác được đánh giá dựa trên 2 đại lượng thống kê là “độ chính xác” (precision) và “độ bao phủ” (recall). Độ chính xác là tỉ lệ các tài liệu được chọn, các tài liệu thực sự liên quan đến các thông tin mà người dùng cần, độ bao phủ là tỉ lệ tài liệu có liên quan được sắp xếp chính xác theo độ liên quan bởi hệ thống tìm kiếm. Nói cách khác, độ chính xác bằng 1 trừ đi tỉ lệ cảnh báo sai, trong khi đó độ bao phủ đo mức độ hoàn chỉnh của việc tìm kiếm. Bảng 1.1 minh họa cho các mối quan hệ này. Actually is Selected as Relevant Not relevant Relevant Found False alarm Not Relevant Missed alarmFalseFound Foundecision +=Pr MissedFound Foundcall +=Re GVHD: TS. Hồ Bảo Quốc Nguyễn Thị Hồng Nhung - 0112235 TS. Đinh Điền Nguyễn Thị Tuyết Mai - 0112229 8 Hệ thống tìm kiếm thông tin xuyên ngôn ngữ Việt – Anh – Hoa Bảng 1.1: Tính độ hiệu quả của hệ thống tìm kiếm thông tin Việc đánh giá tính hiệu quả của hệ thống tìm kiếm dựa trên sắp xếp thì phức tạp hơn. Một cách tính độ hiệu quả phổ biến cho các hệ thống này là “độ chính xác trung bình”. Nó được tính bằng cách chọn một tập lớn hơn các tài liệu ở đầu danh sách có giá trị bao phủ giữa 0 và 1. Phương pháp thường được sử dụng là phương pháp tính dựa trên 5, 7, 11 điểm theo độ bao phủ. Độ chính xác sau đó sẽ được tính cho từng tập một. Qui trình sẽ được lặp lại cho từng câu truy vấn, và tương ứng mỗi độ chính xác trung bình sẽ cho một độ bao phủ. Mỗi giá trị trung bình của những số này sau đó sẽ được tính toán và ghi nhận như là một đặc trưng của hệ thống. Độ chính xác trung bình càng lớn thì càng tốt, và việc so sánh chỉ thực sự có ý nghĩa khi chúng ta sử dụng cùng một tập tài liệu và câu truy vấn. Tuy nhiên độ chính xác trung bình cũng làm giảm đi mức độ thay đổi của các câu truy vấn có các đặc tính khác nhau (ví dụ như số lượng tài liệu có liên quan khác nhau). Hơn thế nữa, các tài liệu có liên quan thường tập trung ở đầu danh sách sắp xếp nên thông thường độ chính xác sẽ giảm mỗi khi tập tài liệu được mở rộng để tăng độ bao phủ. 1.2 Hệ thống tìm kiếm thông tin xuyên ngôn ngữ (CLIR): 1.2.1 Khái niệm: Hệ thống tìm kiếm thông tin xuyên ngôn ngữ (CLIR) là hệ thống tìm kiếm (IR) cho phép người dùng nhập câu truy vấn bằng một ngôn ngữ để tìm kiếm các tài liệu trong một ngôn ngữ khác. Đối tượng sử dụng hệ thống tìm kiếm thông tin xuyên ngữ (CLIR) là: • Những người có khả năng đọc các tài liệu tiếng nước ngoài, nhưng gặp khó khăn khi tạo câu truy vấn bằng ngôn ngữ đó. • Những người gặp khó khăn khi đọc/ tìm kiếm các tài liệu tiếng nước ngoài nhưng lại cần một số lượng giới hạn các tài liệu được tìm kiếm bằng CLIR để sử dụng trong các hệ thống dịch máy (MT), thay vì phải dịch toàn bộ tập hợp các tài liệu. GVHD: TS. Hồ Bảo Quốc Nguyễn Thị Hồng Nhung - 0112235 TS. Đinh Điền Nguyễn Thị Tuyết Mai - 0112229 9 Hệ thống tìm kiếm thông tin xuyên ngôn ngữ Việt – Anh – Hoa