Đồ án Kiểm tra, sửa lỗi chính tả cho dữ liệu blog khoá luận tốt nghiệp đại học hệ chính quy - Nguyễn Thị Xuân Hương

Nội dung text: Đồ án Kiểm tra, sửa lỗi chính tả cho dữ liệu blog khoá luận tốt nghiệp đại học hệ chính quy - Nguyễn Thị Xuân Hương

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÕNG o0o ĐỒ ÁN TỐT NGHIỆP NGÀNH CÔNG NGHỆ THÔNG TIN Hải Phòng 2015
2. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÕNG o0o KIỂM TRA, SỬA LỖI CHÍNH TẢ CHO DỮ LIỆU BLOG KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hƣớng dẫn: Ths. Nguyễn Thị Xuân Hƣơng Hải Phòng 2015
3. BỘ GIÁO DỤC VÀ ĐÀO TẠO CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÕNG Độc lập - Tự do - Hạnh phúc o0o o0o NHIỆM VỤ THIẾT KẾ TỐT NGHIỆP Sinh viên: Nguyễn Thị Lƣơng Mã số:1112101011 Lớp: CT1501 Ngành:Công nghệ Thông tin Tên đề tài:Kiểm tra,sửa lỗi chính tả cho dữ liệu Blog
4. NHIỆM VỤ ĐỀ TÀI 1. Nội dung và các yêu cầu cần giải quyết trong nhiệm vụ đề tài tốt nghiệp a. Nội dung: - Tìm hiểu về dữ liệu Blog trên mạng xã hội và các lỗi gặp phải - Xây dựng chƣơng trình kiểm tra và sửa lỗi chính tả b. Các yêu cầu cần giải quyết - Tìm hiểu một số phƣơng pháp kiểm tra lỗi chính tả - Cài đặt chƣơng trình thực nghiệm 2. Các số liệu cần thiết để thiết kế, tính toán - Sử dụng dữ liệu tìm đƣợc để cài đặt chƣơng trình 3. Địa điểm thực tập
5. CÁN BỘ HƢỚNG DẪN ĐỀ TÀI TỐT NGHIỆP Ngƣời hƣớng dẫn thứ nhất: Họ và tên: Nguyễn Thị Xuân Hƣơng Học hàm, học vị: Thạc Sĩ Cơquan công tác: Trƣờng đại học Dân Lập Hải Phòng Nộidung hƣớng dẫn: Ngƣời hƣớng dẫn thứ hai: Họvà tên: Họchàm, học vị Cơquan công tác: Nộidung hƣớng dẫn: . Đề tài tốt nghiệp đƣợc giao ngày 06 tháng 04 năm 2015 Yêu cầu phải hoàn thành trƣớc ngày 11 tháng 07 năm 2015 Đã nhận nhiệm vụ: Đ.T.T.N Đã nhận nhiệm vụ: Đ.T.T.N Sinh viên Cán bộ hƣớng dẫn Đ.T.T.N Hải Phòng, ngày tháng năm 2015 Hiệu trƣởng GS.TS.NGƯT Trần Hữu Nghị
6. PHẦN NHẬN XÉT TÓM TẮT CỦA CÁN BỘ HƢỚNG DẪN 1. Tinh thần thái độ của sinh viên trong quá trình làm đề tài tốt nghiệp: Đánh giá chất lƣợng của đề tài tốt nghiệp (so với nội dung yêu cầu đã đề ra trong nhiệm vụ đề tài tốt nghiệp) Ch o điểm của cán bộ hƣớng dẫn: ( Điểm ghi bằng số và chữ ) Ngày tháng năm 2015 Cán bộ hƣớng dẫn chính ( Ký, ghi rõ họ tên )
7. PHẦN NHẬN XÉT ĐÁNH GIÁ CỦA CÁN BỘ CHẤM PHẢN BIỆN ĐỀ TÀI TỐT NGHIỆP 1. Đánh giá chất lƣợng đề tài tốt nghiệp (về các mặt nhƣ cơ sở lý luận, thuyết minh chƣơng trình, giá trị thực tế, ) 2. Cho điểm của cán bộ phản biện ( Điểm ghi bằng số và chữ ) Ngày tháng năm 2015 Cán bộ chấm phản biện (Ký, ghi rõ họ tên)
8. LỜI CẢM ƠN EmxinchânthànhcảmơncácThầy,CôkhoaCôngnghệThôngtin Trƣờng Đại học Dânlập Hải Phòng đã tận tình dạy dỗ, truyền đạt cho chúng em nhữngkiến thức quý báu trong suốt bốn năm học vừa qua. Em xin tỏ lòng biết ơn sâu sắc đến Ths Nguyễn Thị Xuân Hƣơng, ngƣời đã tận tình giúp đỡ và truyền đạt nhiều kinh nghiệm để cho em có thể đƣợc thực hiện và hoàn thành đề tài. Cuối cùng em xin gửi lời cảm ơn chân thành tới tất cả ngƣời thân và bạn bè đã giúp đỡ, động viên em trong suốt quá trình học tập cũng nhƣ trong quá trình thực hiện đề tài. Em xin chân thành cảm ơn! Hải Phòng, tháng 07 năm 2015. Sinh viên Nguyễn Thị Lƣơng
9. MỞ ĐẦU Hệ thống chữ viết tiếng Việt là một hệ thống chữ viết linh động, có thể dễ dàng biểu thị tiếng nói dƣới dạng chữ viết chỉ cần dựa trên những luật nhất định mà không đòi hỏi quá nhiều về mặt kiến thức từ vựng nhƣ nhiều ngôn ngữ khác(tiếng Anh, Pháp, Trung ). Tuy nhiên, việc giaotiếp hằng ngày chủ yếu là qua tiếng nói, điều này dẫn đến việc có nhiều cách phát âm không giống nhau giữa các vùng miền khác nhau đối với cùng một từ. Việc này rất dễ dẫn đến mắc lỗi sai chính tả trong khi viết. Ngoài ra, việc sử dụng máy tính để soạn thảo văn bản cũng làm xuất hiện một số lỗi trong quá trình đánh máy. Thêm vào đó, cùng với sự phát triển mạnh mẽ của Internet và các hình thức trao đổi trực tuyến qua các diễn đàn, các trang mạng xã hội, các trang sản phẩm, là rất phổ biến. Đã có một lƣợng lớn Dữ liệu ngƣời dùng tạo ra khi họ đƣa ra các nhận xét, bình luận và thể hiện cảm xúc của mình về các sản phẩm, dịch vụ, các vấn đề khoa học, nghệ thuật, chính trị, xã hội, Việc nghiên cứu, phân tích các dữ liệu này có ý nghĩa quan trọng đối với các nhà sản xuất, kinh doanh, các nhà quản lý, để từ đó đƣa ra các quyết sách với các hoạt động của họ trong tƣơng lai. Gần đây, các nghiên cứu dành cho lĩnh vực này đã thu hút đƣợc sự quan tâm của rất nhiều các nhà nghiên cứu và đã có rất nhiều kết quả đƣợc ứng dụng trong thực tế. Tuy nhiên, các dữ liệu này thƣờng có rất nhiều lỗi chính tả do chủ quan của ngƣời dùng khi gõ văn bản. Vì vậy, việc phát hiện và sửa lỗi chính tả cho loại dữ liệu này chính là bƣớc tiền xử lý có ý nghĩa quan trọng để làm tăng độ chính xác cho các nghiên cứu tiếp theo. Một hệ thống kiểm tra chính tả thông thƣờng bao gồm hai thành phần chính là phát hiện và điều chỉnh. Trong một số trƣờng hợp, hệ thống cung cấp một số gợi ý sửa chữa cho các ngƣời dùng lựa chọn. Các lỗi chính tả đƣợc 9
10. xem xét trong nghiên cứu trƣớc đây bao gồm: lỗi chính tả không-từ (non- word) và lỗi chính tả thực-từ (real-word). - Các lỗi không phải là từ (non-word) là chuỗi mà không tồn tại trong từ điển. Ví dụ, các sau câu trong tiếng Việt: "Hôm nay Tôi ddi học". Chuỗi "ddi" là một lỗi chính tả từ, và nó không tồn tại trong từ điển Tiếng Việt, và thƣờng đƣợc tạo ra trong quá trình đánh máy (tƣơng ứng của nó từ đúng là "đi"). Ngoài ra, các lỗi viết tắt do sự chủ quan của ngƣời dùng nhƣ: “ko”(“không”), “đc” (“được”), - Các lỗi từ thực tế (real-word) xảy ra trong các tài liệu khi các từ đƣợc sử dụng lẫn lộn. Ví dụ, các câu sau đây bằng tiếng Việt: "Quyển xách này rất hay", từ "xách" (carry) là không chính xác đƣợc sử dụng trong khi một chính xác tƣơng ứng là "Sách" (book). Đồ án này tìm hiểu một số phƣơng pháp kiểm tra chính tả và sử dụng thông tin ngữ cảnh để sửa loại lỗi. Thông tin ngữ cảnh đƣợc thống kê từ ngữ liệu dựa trên mô hình ngôn ngữ n-gram. Đồ án gồm có 4phần: Chƣơng1: Giớithiệutổngquanvềtiếng Việt,bàitoánkiểmlỗichínhtả . Chƣơng 2: Trình bày về một số phƣơng pháp kiểm lỗi chính tả. Chƣơng 3: Một số công cụ và chƣơng trình thực nghiệm. Phần cuối cùng là Kết luận. 10
11. MỤC LỤC LỜI CẢM ƠN 8 MỞ ĐẦU 9 MỤC LỤC 11 DANH SÁCH BẢNG VÀ HÌNH VẼ 13 Chƣơng 1. TỔNG QUAN 14 Chƣơng 2. MỘT SỐ PHƢƠNG PHÁP KIỂM TRA LỖI CHÍNH TẢ 21 2.1 Phƣơng pháp tra cứu từ điển (Dictionary Lookup Technique) 21 2.2 Phƣơng pháp chuỗi con chung dài nhất (The Longest Common Subsequence algorithm) 24 2.2.1 Đặc tả bài toán 24 2.2.2 Đánh giá các giải pháp 25 2.3 Sử dụng mô hình ngôn ngữ N-gram 26 2.3.1 Một số khái niệm 26 2.3.2 Mô hình N-gram 28 2.3.3 Kiểm tra lỗi chính tả dựa trên n-gram. 31 2.3.4 Tiền xử lý dữ liệu 32 2.3.5 Tính tần suất n-gram. 32 Chƣơng 3. MỘT SỐ CÔNG CỤ VÀ CHƢƠNG TRÌNH THỬ NGHIỆM 35 3.1 Một số công cụ: 35 3.1.1 Bộ công cụ xây dựng mô hình ngôn ngữ - SRILM: 35 3.1.2 Ngôn ngữ C# 38 11
12. 3.2 Chƣơng trình thực nghiệm 40 KẾT LUẬN 41 12
13. DANH SÁCH BẢNG VÀ HÌNH VẼ Bảng 1.1. Cấu trúc 3 thành phần của âm tiết: ___ 16 Bảng 1.2 cấu trúc 4 thành phần của âm tiết: ___ 16 Bảng 1.3 cấu trúc 5 thành phần của âm tiết: ___ 16 Bảng 1.4 các thành phần âm tiết ___ 16 Bảng 2.1: Bƣớc 1, lần lặp i = 0 ___ 23 Bảng 2.2: Bƣớc 2, lần lặp i -1 ___ 23 Bảng 2.3, Bƣớc 3, lần lặp i = 3 ___ 23 Bảng 2.4, Bƣớc cuối cùng, lần lặp i = n, j = m ___ 24 Hình 2.1. Mô hình Markov bậc 2 ___ 29 Hình 3.1 Sơ đồ chƣơng trình kiểm tra lỗi chính tả: Vẽ lại theo bài báo 5. __ 40 Hình 3.2. Giao diện của chƣơng trình. ___ 41 13
14. Chƣơng 1. TỔNG QUAN Chƣơng này giớithiệu về bàitoán kiểmlỗi chínhtả, một số phƣơng pháp kiểm lỗi chính tả và phƣơng pháp sẽ đƣợc sử dụng trong Đồ án này. Trình bày mộtsố đặc điểm củatiếng Việt và chữ viếttiếng Việt, tập trung vào những đặc điểm có thể sử dụng để kiểm tra và sửa lỗi chính tả tiếng Việt. Đồ án chỉ đề cập đến vấn đề chính tả tiếng Việt, do đó khi nói “tiếng Việt” cũng có thể đƣợc hiểu là “chữviết tiếng Việt”. 1.1 Giới thiệu 1.1.1. Bài toán kiểm lỗi chính tả Bàitoán kiểmlỗichínhtảlà một bàitoán khá phứctạp, đƣợc khôngít đơn vịnghiên cứu, phát triển và nó có tính ứng dụng cao, đặc biệt là trong các ứng dụng soạn thảo hay nhận dạng văn bản. Chƣơngtrình kiểmlỗi chínhtả cần có hai chức năng chính, cơ bảnlà chỉralỗi sai và đƣa ra gợi ý sửa lỗi. Tuy nhiên, các chức năng kiểm lỗi chính tả đƣợc tích hợp trong nhiều ứng dụng soạn thảo tiếng Việt hiện nay (Vietkey, Unikey ) không đƣa ra gợi ý cho ngƣời dùng lựa chọn. Đề giải quyết bài toàn này, hiện nay đã có một số cá nhân hoặc nhóm nghiên cứu và phát triển phần mềm kiểm lỗi chính tả nhƣ: Chƣơng trình kiểm lỗi chính tả VietSpell 3.0 của Lƣu Hà Xuyên, CopCon của Mai Tuấn Khôi và cộng sự. Chƣơngtrình kiểmlỗi chínhtả Cú Mèo của Côngty cổ phần đầutƣ phát triển công nghệ SOBIC. Các phần mềm này có khả năng sửa lỗi chính tả ở mức độ từ ghép hai hoặc ba âm tiết. Và một số các nghiên cứu cho kiểm tra lỗi chính tả Tiếng Việt. 1.1.2. Dữ liệu Blog - Blog là gì? 14
15. “Blog” là một thuật ngữ có nguồn gốc từ cặp từ “Web Log” hay “Weblog” dùng để chỉ một tập san cá nhân trực tuyến, một quyển nhật ký dựa trên nền web hay một bản tin trực tuyến nhằm thông báo những sự kiện xảy ra hàng ngày về một vấn đề gì đó. Nội dung và chủ đề của “blog” thì rất đa dạng, nhƣng thông thƣờng là những câu chuyện cá nhân, bản tin, danh sách các liên kết web, những bài tƣờng thuật, phê bình một bộ phim hay tác phẩm văn học mới xuất bản và cuối cùng là những sự kiện xảy ra trong một nhóm ngƣời nào đó. - Dữ liệu Blog trên mạng xã hội bao gồm các thông tin, nhật ký, các status, các comment mà ngƣời dùng đã đăng tải lên các trang mạng xã hội, các trang sản phẩm, blog, - Một số trang mạng xã hội và trang sản phẩm đƣợc biết đến nhiều ở Việt Nam nhƣ: Facebook, Go.vn, Zing.Vn, . Tinhte.vn, Vatgia.vn, 1.2. Một số đặc điểm trong tiếng Việt 1.2.1. Đặc điểm của tiếng Việt Tiếng Việtlà mộtngônngữđơnlập,quanhệgiữacáctừđƣợcbiểuthịbằng những phƣơng tiện nằm ngoài từ nhƣ trật tự từ, hƣ từ. Đặc điểm này đƣợc áp dụng cho cả về ngữ âm, ngữ pháp và ngữ nghĩa. 1.2.2. Các đơn vị của tiếng Việt -Tiếng (âm tiết) Âmtiếtlà đơn vị phát âmtự nhiên nhỏ nhấttrong ngôn ngữ. Trongtiếng Việt, một âmtiết bao giờ cũng đƣợc phátra với mộtthanh điệu, và khi viết đƣợctáchrời với âmtiết khác bằng một khoảngtrống. Trên chữ viết, mỗi âmtiếttiếng Việt đƣợc ghi thành một “chữ” và đọc thành một “tiếng”. Có 15
16. nhiều cách mô tả cấu trúc âm tiết tiếng Việt khác nhau: 3 thành phần, 4 hay 5 thành phần. Bảng 1.1. Cấu trúc 3 thành phần của âm tiết: Bảng 1.2 cấu trúc 4 thành phầncủa âm tiết: Bảng 1.3 cấu trúc 5 thành phần của âm tiết: - Các thành phần trong dấu <> là bắt buộc - Các thành phần trong dấu[ ] là không bắt buộc - Thanh ngang (không đƣợc viết) cũng đƣợc tính là một dấu thanh. Bảng 1.4 các thành phần âm tiết - Từ: 16
17. Từlàđơnvịngônngữcónghĩahoànchỉnh. Từtiếng Việtbaogồm mộthay nhiều âm tiết sắp xếp theo một thứ tự nhất định. Có từ đơn, từ ghép và từ láy. Từ trong tiếng Việt có khả năng hoạt động tự do và độc lập về mặt cú pháp. Từtiếng Việt không có sự biến dạng (số nhiều, ngôi thứ, bị động ) nhƣ trong nhiều ngôn ngữ khác. - Câu:Câu do các từ hợp thành theo những quy tắc nhất định. Trong tiếng Việt, các quy tắc này rất đa dạng. - Dấu thanh : Tiếng Việt gồm có 6 thanh điệu: ngang, huyền, hỏi, ngã, sắc, nặng. Trong đó có 5 dấu thanh, thanh ngang không đƣợc biểu diễn bởi dấu thanh nào. Trong văn bản viết tay, dấuthanh đƣợc đánh khátùytiện, không đặt vào đúng vịtrí của âm chính. Tuy nhiên, trong văn bản đánh máy, việc đánh dấu thanh cần tuân thủ một số quy tắc sau: Với những âm tiết chỉ có một con chữ nguyên âm, thì dấu thanh đƣợc đặt vào con chữ nguyên âm đó. Vd: á à, ì ạch, ọ ẹ, ủ rũ, ọp ẹp, ục ịch, hà, lán, giá, giục, quả, quỹ, quỵt (Chú ý: gi và qu đƣợc coi là phụ âm). Với những âm tiết, mà trong âm tiết đó chỉ cần có một con chữ nguyên âm mang dấu phụ (Ă, Â, Ê, Ô, Ơ, Ƣ) và không kể kết thúc bằng con chữ gì, thì dấu thanh bao giờ cũng đặt ở con chữ đó (riêng ƢƠ, dấu đặt ở Ơ). Vd: thuyền, trƣờng Với những âm tiết có hai con chữ nguyên âm và kết thúc bằng một con chữ phụ âm hoặc tổ hợp con chữ phụ âm, thì dấu thanh đƣợc đặt vào con chữ nguyên âm cuối cùng. Với những trƣờng hợp còn lại thì dấu thanh đƣợc đặt vào con chữ nguyên âm áp Chót. 17
18. 1.3. Một số lỗi chính tả cơ bản và phương pháp kiểm lỗi mức độ âm tiết Các vấn đề chính tả tiếng Việt có thể gặp phải gồm có: sai cấu tạo, đúng cấu tạo nhƣng không cótrongtừ điển, cótrongtừ điển nhƣngsai về ngữ nghĩa,sai cấutạo nhƣng có thể là từ tiếng nƣớc ngoài. 1.3.1. Các nguyên nhân gây ra lỗi chính tả Có nhiều nguyên nhân khác nhau gây ra lỗi chính tả, tuy vậycóthể tổng hợp lại một sốnguyên nhân nhƣ sau : - Nguyên nhân do nhập liệu sai: Lỗi này có thể do gõ sai/thiếu/thừaphímgâyra,docách càiđặtbàn phím,loạibànphím,doquy tắcgõtiếng Việt của cáckiểugõkhácnhau(Telex,VNI,TCVN, Unicode, ) - Nguyên nhân do phát âmsai: Lỗi này do sự nhầm lẫngiữacáchđọcvàcách viết của những từ đồngâm hoặc âm gần với nhau dẫn đến viết sai (nhƣ lỗi dấu hỏi/ngã, lốisaiâmđầus/x,tr/ch,r/d/gi/v ). Vớitiếng Việt, do có nhiều khác biệt vềcách phát âmgiữa cácvùngtrongkhi hệthốngchữviết lại dựa trên hệ thống phát âm của thủ đô Hà Nội nên dễ dẫn đến các lỗi sai loại này. - Nguyên nhân do sử dụng từ vựng sai: Lỗinàydo khi sử dụng từsai với ý nghĩathực của nó. Đâylà lỗi về vốn từ vựng của ngƣời sử dụng, nhƣng nhiều khi vẫnđòi hỏitrình bắt lỗichính tảphảitìmra những lỗi này. - Cácnguyênnhânkhác:Ngoàiracòncácloại lỗi chính tả khác nhƣ viết hoa, viết tên riêng, thuật ngữ, tên tiếng nƣớc ngoài không đúng qui cách, 1.3.2.Phân loại lỗi chính tả 18
19. Có nhiều cách phân loại lỗi chính tả theo các tiêu chí khác nhau. Ta có thể phân loại theo nguồn gốc sinh ra lỗi nhƣ ởtrên. Nếuxéttheoquanđiểm củachƣơng trình bắt lỗichính tả ở mức từthì lỗichính tảcóthể đƣợcphânlàmhailoạilà lỗinon-wordvà lỗireal-word : - Lỗi non-word là lỗi tạo ra từ sai, nghĩa là từ đó hoàn toàn không có trong từ điển từ vựng tiếng Việt hoặc một số ngữ liệu đầu vào cho quá trình tiền xử lý văn bản nhƣ : từ điểntênriêng, từ điển viết tắt, từ điển vay mƣợn, vd: "Hôm nay tôi ddi học". Chuỗi "ddi" là lỗi chính tả, và nó không tồn tại trong từ điển Tiếng Việt (tƣơng ứng của nó từ đúng là "đi"). Lỗi do viết tắt: “ko” (từ tƣơng ứng là “không”) - Lỗireal-wordlà lỗichính tả mà từ đó có trong từ điển nhƣng sử dụng từ sai. Nếu không dựa vào ngữ cảnh xung quanh thì không thể xác định đƣợc đó có phảilà lỗichính tảhaykhông. Đâylàloại lỗi rất khó phát hiện và xử lý. Các lỗi khác từ: -Lỗi đánh máy. Ví dụ: "BOF" -> "bò" Các lỗi thực từ: - Lỗi về dấu. Ví dụ: "hoi" -> "hỏi" - Lỗi phụ âm đầu. Ví dụ: "bức chanh" -> "bức tranh" - Lỗi phụ âm cuối. Ví dụ: "bắt buột" -> "bắt buộc". 19
20. - Lỗi khu vực (Việt Nam có nhiều khu vực với các phƣơng ngữ khác nhau, trong đó cần phải đƣợc đổi thành ngôn ngữ chung). Ví dụ: "Kim" -> "kiếm" 20
21. Chƣơng 2. MỘT SỐ PHƢƠNG PHÁP KIỂM TRA LỖI CHÍNH TẢ 2.1 Phƣơng pháp tra cứu từ điển (Dictionary Lookup Technique) Phƣơng pháp tra cứu từ điển là một cách đơn giản và hiệu quả cho kết hợp chuỗi gần đúng và đƣợc sử dụng nhƣ một bổ sung trong giai đoạn hậu xử lý. Phƣơng pháp tra cứu từ điển cần một chuỗi là đầu vào, và cố gắng để tìm thấy những chuỗi gần nhất với nó trong từ điển. Trong các phƣơng pháp tra cứu từ điển, có một số vấn đề cần đƣợc giải quyết, chẳng hạn nhƣ: 1) Giá trị bổ sung vào từ điển tra cứu đã dẫn đến tính toán xác suất tiên nghiệm, nólàm tăng mức độ tính toán và phức tạp. 2) Một từ điển nhỏ có thể không đủ để phù hợp với các từ trong ngữ cảnh. 3) Một từ điển lớn làm tăng chi phí tìm đến một mức độ rất lớn. Thuật toánLevenshtein Distance Khoảng cách Levenshtein Distance (LD) là dùng để đo của giống nhau giữa hai chuỗi, chuỗi mã nguồn (s) và chuỗi mục tiêu (t). Khoảng cách là số xóa, chèn thêm, hoặc thay thế cần thiết để chuyển đổi s thành t. Khoảng cách Levenshtein càng lớn thì sự khác nhau trong chuỗi càng nhiều. Trong trƣờng hợp các chuỗi mã nguồn là đầu vào, và chuỗi mục tiêu là một trong những mục trong từ điển. Bằng trực giác "Gumbo" có thể đƣợc chuyển đổi thành "Gambol" bằng cách thay thế "A" cho "U" và thêm "L" (một thay thế và một chèn = hai sự thay đổi). 21
22. - thuật toán: Bƣớc 1: Khởi tạo a)Đặt n là chiều dài của s, thiết lập m là chiều dài của t. b) Xây dựng một ma trận chứa hàng 0 m và 0 n cột. c) Khởi tạo hàng đầu tiên để 0 n, d) Khởi tạo các cột đầu tiên 0 m. Bƣớc 2: xử lý a) Kiểm tra s (i từ 0 đến n). b) Kiểm tra t (j từ 0 đến m). c) Nếu s [i] bằng t [j], chi phí là 0. d) Nếu s [i] không bằng t [j], chi phí là 1. e) thiết lập phần tử d [i, j] của ma trận bằng với tối thiểu là: i) Các phần tửngay lập tức ở trên cộng thêm 1: d [i, j+1] + 1. ii). Các tế bào ngay cho cộng trái 1: d [i+1, j] + 1. iii) Các tế bào đƣờng chéo phía trên và bên lại cộng với các chi phí: d [i, j] + chi phí. Bƣớc 3: tra ra kết quả. Bƣớc 2 đƣợc lặp đi lặp lại cho đến khi d [n, m] giá trị đƣợc tìm thấy Ví dụ từ GUMBO -> GAMBOL 22
23. Bảng 2.1: Bước 1, lần lặp i = 0 Bảng 2.2: Bước 2, lần lặp i -1 Bảng 2.3, Bước 3, lần lặp i = 3 23
24. Bảng 2.4, Bước cuối cùng, lần lặp i = n, j = m 2.2 Phƣơng pháp chuỗi con chung dài nhất (The Longest Common Subsequence algorithm) Đây là một phƣơng pháp phổ biến để tìm ra sự khác nhau giữa hai từ. Một chuỗi con chung dài nhất của hai xâu thể hiện chuỗi con tƣơng hỗ giữa chúng. 2.2.1 Đặc tả bài toán - Khái niệm chuỗi con: Cho chuỗi X=x1x2x3 xn. S là chuỗi thu đƣợc từ X bằng cách bỏ đi một vài ký tự trong X đƣợc gọi là chuỗi con của X. - Ví dụ: X= “computer science” S=”co ur se” =>“course” - Trình tự các ký tự đƣợc đảm bảo không thay đổi Cho X={x1, x2, x3, , xn} là tập các chuỗi. - Khái niệm chuỗi con chung: CS là chuỗi con chung của các chuỗi trong X nếu CS là chuỗi con của tất các các chuỗi trong X. 24
25. - LCS là chuỗi con chung dài nhất của các chuỗi trong X nếu:LCS là chuỗi con chung của các chuỗi trong XVà LCS có chiều dài lớn nhất. 2.2.2 Đánh giá các giải pháp Bài toán: Tìm chuỗi con chung dài nhất - Input: Tập các chuỗi X={x1, x2, x3, , xn}. -Output:Liệt kê tất cả(1) LCS của các chuỗi trong X. - Xác định chiều dài của LCS. ==> Edit Distance. Giải pháp: quy hoạch động -Ý tƣởng: dựa trên quan hệ đệ quy -Chỉ áp dụng đƣợc khi |X| là hằng số: N. -Độ phức tạp thời gian và không gian: - Chỉ có ý nghĩa với N nhỏ(N=2) Các bƣớc: Bƣớc 1: Khởi tạo a)Đặt n là chiều dài của s, thiết lập m là chiều dài của t. b) Xây dựng một ma trận chứa hàng 0 m và 0 n cột. Bƣớc 2: xử lý 1) Kiểm tra s (i từ 0 đến n). 2) Kiểm tra t (j từ 0 đến m). Nếu i =0 hoặc j=0 thì LCS[i][j] = 0; Nếu s[i-1] = t[j-1] thì LCS[i][j]= LCS[i-1][j-1]+1 25
26. Ngƣợc lại LCS[i][j] = max (LCS[i-1][j],LCS[i][j-1]) Bƣớc 3 : Trả ra LCS[s][t] Lấy match quan trọng : Nếu s[i]= t[j] thì trả ra BackTrack(LCS,s,t,i-1,j-1) + string(s[i]) Ngƣợc lai Nếu LCS[i+1][j] > LCS[i][j+1] thì trả ra BackTrack (LSC,s,t,i,j-1) Ngƣợc lai trả ra BackTrack(LCS, s, t, i-1, j) 2.3 Sử dụng mô hình ngôn ngữ N-gram Mô hình ngôn ngữ là một phân bố xác suất trên các tập văn bản, cho biết xác suất một câu ( một cụm từ hoặc một từ) trong bộ dữ liệu mẫu là bao nhiêu. Ví dụ : Khi áp dụng mô hình ngôn ngữ cho tiếng Việt : P[“ngày tết thật là vui”] = 0,001. P[“vui là thật tết ngày”] = 0. Mô hình ngôn ngữ đƣợc áp dụng trong rất nhiều lĩnh vực của xử lý ngôn ngữ tự nhiên nhƣ: kiểm tra lỗi chính tả, dịch máy hay phân đoạn từ Chính vì vậy, nghiên cứu mô hình ngôn ngữ chính là tiền đề nghiên cứu các lĩnh vực tiếp theo. 2.3.1 Một số khái niệm i). Ngữ liệu: Ngữ liệu (Corpus) là 1 dữ liệu tập hợp các văn bản, ngôn ngữ đã đƣợc số hoá. Cách dịch thông thƣờng ở Việt Nam là “kho ngữ liệu” hoặc tập huấn luyện trong một số bài báo khoa học. Ví dụ về corpus nhƣ “tuyển tập các tác phẩm của Nam Cao”, hay “tuyển tập ca từ của Trịnh Công Sơn” 26
27. ii)N-gram: Là tần suất xuất hiện của n kí tự (hoặc từ) liên tiếp nhau có trong dữ liệu của corpus. - Với n = 1, unigram, và tính trên kí tự, ta có thông tin vềtần suất xuất hiện nhiều nhất của các chữ cái. Điều này đƣợc ứng dụng để làm keyboard: các phím hay xuất hiện nhất sẽ ở những vị trí dễ sử dụng nhất (e,a, ). - Với n = 2, ta có khái niệmbigram. Ví dụvới các chữcái tiếng Anh, „th‟,‟he‟,‟in‟,‟an‟,‟er‟ là các cặp kí tự hay xuất hiện nhất. Ngoài ra, ta có thểbiết thêm rằng sau kí tự „q‟ thì phần lớn đều là kí tự „u‟. - Với n = 3, ta cótrigram. Nhƣngvìncànglớnthì sốtrƣờng hợp càng lớn nên thƣờng ngƣời ta chỉ sử dụng với n = 1,2 hoặc đôi lúc là 3. Ví dụ với các kí tự tiếng Việt, tiếng Việt sử dụng 29 kí tự, vậy với n = 1 thì số trƣờng hợp là 29, n = 2 thì số trƣờng hợp là 29^2 = 841 trƣờng hợp, n = 3 có 24389 trƣờng hợp. Bigram đƣợc sử dụng nhiều trong việc phân tích hình thái (từ, cụm từ, từloại) cho cácngôn ngữ khó phân tích nhƣ tiếng Việt, tiếng Nhật, tiếng Trung, Dựa vào tần suất xuấthiện cạnh nhau của các từ,ngƣời ta sẽtính cách chia 1 câu thành cáctừsao cho tổngbigram là cao nhất có thể. Với giải thuật phân tích hình thái dựa vào trọng số nhỏ nhất,ngƣời ta sử dụng n = 1 để xác định tuần suất xuất hiện của các từ và tính trọng số. Để đảm bảo tính thống kê chính xác đòi hỏi các corpus phải lớn và có tính đại diệncao. iii). History (Lịch sử- về ngôn ngữ): ta hiểu là tiền ngữ, chẳng hạn “ngôn ngữ tự nhiên” và “ngôn ngữtựchế” có chung tiền ngữlà “ngôn ngữtự”. Cụthể, với n-gram , thì history của trong W chính là . 27
28. 4i).N-gram không nhìn thấy (Unseen N-Grams): Giảsửta nhìn thấy “xửlý ngôn ngữ” trong tập ngữliệu, nhƣngta hoàntoàn khôngtìmthấy “xử lý ngôn ngữ tự”, khi đó, P(tự|xử lý ngôn ngữ) = 0 Khi đó ta nói cụm “xử lý ngôn ngữ tự” là không nhìn thấy, có xác suất là 0. 2.3.2 Mô hình N-gram Nhiệm vụ của một mô hình ngôn ngữlà cho biết xác suất của một từ hoặc cụm từW= w1w2 .wn thì p(W) theo công thức Bayes : P(A|B) = P(B|A)*P(A) đƣợc xác định: P(w1w2 .wn)= p(w1)*p(w2|w1)*p(w3|w1w2)* .*p(wn|w1w2 wn-1). Theo công thức này, mô hình ngôn ngữ cần phải có một lƣợng bộ nhớ vô cùng lớn để có thể lƣu hết xác suất của tất cả các chuỗi độ dài nhỏ hơn m. Rõ ràng, điều này là không thể khi m là độ dài của các văn bản ngôn ngữ tự nhiên (m có thể tiến tới vô cùng). i). Chuỗi Markov Giả thiết rằng, xác suất tính cho 1 sự kiện: -Chỉ phụ thuộc vào các history trƣớc. -Giới hạn bộ nhớ: chỉ có ktừ đƣợc đƣa vàotrong history(cáctừ “cũ hơn” có khảnăng ít liên quan), chẳng hạn chuỗi w = w‟w1 wk , ta sẽ coi nhƣw~w1 .wkTa gọi là mô hình Markov bậc k. Ví dụ, nếu chúng ta muốn ƣớc lƣợng xác suất 2-gram của một từ wi với mô hình Markov bậc 2 thì chúng ta sẽ dựa trên hai từ trƣớc đó:P(w1,w2, ,wi)=P(wi/wi-2,wi-1) 28
29. Hình 2.1. Mô hình Markov bậc 2 Một cách tổng quát, xác suất xuất hiện của một từ (wm) đƣợc coi nhƣ chỉ phụ thuộc vào n từ đứng liền trƣớc nó (wm-nwm-n+1 wm-1) chứ không phải phụ thuộc vào toàn bộ dãy từ đứng trƣớc (w1w2 w m-1). Nhƣ vậy, công thức tính xác suất văn bản đƣợc tính lại theo công thức: P(w1w2 wm)=P(w1)*P(w2|w1)*P(w3|w1w2)* *P(wm-1|wm-n-1wm-n wm- 2)* P(wm|wm-nwm-n+1 wm-1). ii). Ước lượng xác suất cho mô hình N-gram Để có thể tính đƣợc xác suất của văn bản với lƣợng bộ nhớ chấp nhận đƣợc, sử dụng xấp xỉ Markov bậc n, thay vì tính theo (2.1) ta sử dụng công thức (2.2) dƣới đây: Nếu áp dụng xấp xỉ Markov, xác suất xuất hiện của một từ(Wm) đƣợccoi nhƣchỉ phụ thuộc vào n từ đứng liền trƣớc nó chứ không phải phụ thuộc vào toàn bộ dãy từ đứng trƣớc . Nhƣ vậy, công thức tính xác suất văn bản đƣợc tính lại theo công thức : 29
30. Với công thức này, ta có thể xây dựng mô hình ngôn ngữ dựa trên việc thống kê các cụm có ít hơn n + 1 từ. Mô hình ngôn ngữ này gọi là mô hình ngôn ngữ N-gram. iii).Khó khănkhi xây dựng mô hình ngôn ngữ N-gram  Phân bố không đều Khi sử dụng mô hình N-gram theo công thức “xác suất thô”, sự phân bố không đều trong tập văn bản huấn luyện có thể dẫn đến các ƣớc lƣợng không chính xác. Khi các N-gram phân bố thƣa, nhiều cụm n-gram không xuất hiện hoặc chỉ có số lần xuất hiện nhỏ, việc ƣớc lƣợng các câu có chứa các cụm n- gram này sẽ có kết quả tồi. Với V là kích thƣớc bộtừ vựng, ta sẽ có Vn cụm N-gram có thể sinh từ bộtừ vựng. Tuy nhiên, thực tếthì số cụm N-gram có nghĩa và thƣờng gặp chỉ chiếm rất ít. Ví dụ: tiếng Việt có khoảng hơn 5000 âm tiết khác nhau, ta có tổng số cụm 3-gram có thể có là: 5.0003 = 125.000.000.000 Tuy nhiên, số cụm 3- gram thống kê đƣợc chỉ xấp x 1.500.000. Nhƣ vậy sẽ có rất nhiều cụm 3-gram không xuất hiện hoặc chỉ xuất hiện rất ít. Khi tính toán xác suất của một câu, có rất nhiều trƣờng hợp sẽ gặp cụm N-gram chƣa xuất hiện trong dữ liệu huấn luyện bao giờ. Điều này làm xác suất của cả câu bằng 0, trong khi câu đó có thể là một câu hoàn toàn đúng về mặt ngữ pháp và ngữ nghĩa. Đề khắc phục tình trạng này, ngƣời ta phải sử dụng một số phƣơng pháp “làm mịn” kết quả thống kê.  Kích thước bộ nhớ của mô hình ngôn ngữ Để khắc phục tình trạng các cụm N-gram phân bố thƣa, ngƣời ta áp dụng các phƣơng pháp “làm mịn” kết quả thống kê nhằm đánh giá chính xác hơn (mịn hơn) xác suất của các cụm N-gram. Cácphƣơngpháp“làm mịn”đánhgiálại xác suất của các cụm N-gram bằng cách:Gán cho các cụm N- 30
31. gram có xác suất 0 (không xuất hiện) một giá trị khác 0. Thay đổi lại giá trị xác suất của các cụm N-gram có xác suất khác 0 (có xuất hiện khi thống kê) thành một giá trị phù hợp (tổng xác suất không đổi). Các phƣơng pháp làm mịn có thể đƣợc chia ra thành loại nhƣ sau : - Chiết khấu (Discounting): giảm(lƣợng nhỏ) xác suất của các cụm N- gram có xác suất lớn hơn 0 để bù cho các cụm N-gram không xuất hiện trong tập huấn luyện. - Truy hồi (Back-off) : tính toán xác suất các cụm N-gram không xuất hiện trong tập huấn luyện dựa vào các cụm N-gram ngắn hơn có xác suất lớn hơn 0. - Nội suy (Interpolation): tính toán xác suất của tất cả các cụm N-gram dựa vào xác suất của các cụm N-gram ngắn hơn. 2.3.3 Kiểm tra lỗi chính tả dựa trên n-gram. Nhƣ đã trình bày trên, chúng ta có thể sử dụng mô hình N-gram cho tiếng Việt vào việc tính toán khả năng xuất hiện của một âm tiết dựa vào các âm tiết đứng trƣớc nó.Đồ án tìm hiểu một phƣơng pháp kiểm lỗi chính tả sử dụng thông tin ngữ cảnh bằng mô hình ngôn ngữ N-gram đƣợc đề xuất trong [5]. Hệ thống bao gồm hai thành phần chính: tiền xử lý, tính toán xác suất, sau đó so sánh để lựa chọn một ứng cử viên có khả năng nhất trong bộ nhầm lẫn. Trƣớc khi kiểm tra, các dữ liệu cần phải đƣợc xử lý nhƣ chuẩn hóa, tách câu, dấu chấm câu đánh dấu loại bỏ. Kiến trúc của hệ thống đƣợc minh họa trong hình 3.1. 31
32. 2.3.4 Tiền xử lý dữ liệu Thực tế, các dữ liệu văn bản cần đƣợc xử lý có thể là một dữ liệu không đạt tiêu chuẩn, chẳng hạn nhƣ các văn bản thu từ các trang web mạng xã hội, diễn đàn, blog, vv. Nó đƣợc gọi là dữ liệu Microblog-Style. Giai đoạn tiền xử lý bao gồm ba bƣớc: Bước 1: Nhận biết các âm tiết đặc biệt nhƣ địa chỉ web, email, số và thay thế chúng bằng các ký hiệu đặc biệt. Ví dụ nhƣ: - Số: một tập các chữ số nhƣ 10, 12.5, hay 1,000,000 - Dategroup: cụm các chữ, số và các ký hiệu biểu thị ngày. VD: 10/6/2010 - Timegroup: cụm các chữ, số và các ký hiệu biểu thị thời gian. VD: 11h20 -Trang web: các địa chỉ web có dạng nhƣ , www.wattpad.com . Bước 2: Chia nhỏ tài liệu dựa vào câu vì hai âm tiết trong câu khác nhau không có mối quan hệ với nhau. Bước 3: Loại bỏ tất cả các dấu chấm câu trong câu bởi vì họ không có mối quan hệ của ý nghĩa với các từ. 2.3.5 Tính tần suất n-gram. Trong phƣơng pháp chọn áp dụng cho đồ án này, ta chọn các âm tiết nằm ở các vị trí trong khoảng ±2 so với âm tiết đang xét. Cụ thể: Gọi âmtiết đang xétlàw0,ta xét 2 âmtiết đứngtrƣớclàw_2, w_1 và xét 2 âmtiết đứng sau là w1, w2. Nhƣ vậy thứ tự sẽ là: w_2 w_1 w0 w1 w2việc 32
33. tínhtầnsuấtn-gramtheoâmtiết,baogồmunigram, bigram và trigram. Từ các tần suất này ta sẽ tính đƣợc xác suất của một âm tiết dựa vào các âm tiết lân cận.Ta có thể mô hình phụ thuộc của w0 vào láng giềng lân cận bởi xác suất có điều kiện dƣới đây. P(w0|w_2,w_1,w1,w2) Xác suất này trên có thể đƣợc ƣớc tính bởi hàm sau đây: P(w0|w_2,w_1,w1,w2)=f (P(w0|w_2,w_1), P(w0|w_1,w1), P(w0|w1,w2) Để tính toán xác suất này, chúng ta cần 5 gram và 4 gram. Việc này không khả thi để thực hiện vì số lƣợng dữ liệu quá lớn. Do đó, thay vì tính toán P(w0|w_2,w_1,w1,w2) ta ƣớc tính nó bằngba xác suất trigramP(w0|w_2,w_1), P(w0|w_1,w1), P(w0|w1,w2). i). Xác định từ sai: Để xác định từ sai ta dựa vào unigram, bigram.Một âm tiết đƣợc xác định là lỗi khi nó có n-gram nhỏ hơn một ngƣỡng nhất định. Giả sử rằng âm tiết hiện tại w0 có N-gram là p,w0 đƣợc xác định là lỗi khip e_thresh - p '> p +d_thresh 33
34. e_thresh là một hằng số đƣợc xác định bằng cách sử dụng dữ liệu phát triển, nó đảm bảo rằng nếu một âm tiết là sẽ đƣợc sử dụng để sửa chữa các âm tiết hiện nay, xác suất của nó phải cao hơn một ngƣỡng nhất định. d_thresh đƣợc tính theo công thức: d_thresh = (t-t‟) Trongđó, t là các loại báo lỗi liên tục của âm tiết w0. Trong hệ thống này, t đƣợc thiết lập là 0. t‟ là loại báo lỗi liên tục của w‟0 từ ứng cử viên, đƣợc xác định bằng cách sử dụng các dữ liệu phát triển. Trigram đƣợc sử dụng để tăng khả năng tìm ra ứng cử viên có độchính xác, độ phù hợp để thay thế trong câu. Ví dụ: Trong câu :” bạn phải dọn rác cho đỡ đơ máy là chạy đc mà.” Từ sai là “đc” vì trong bộ âm tiết không có từ này chỉ có từ “đƣợc”. Ta tìm 3gram của 2 từ trƣớc từ sai là “là chạy” và 2 từ sau đó là “mà.” Trong file corpus.txt ta có ngram của 2 từ đó nhƣ sau: -6.45215 là chạy đƣợc -5.12487 là chạy tốt . Tìm 1gram của từ sẽ làm gợi ý “đƣợc”, “tốt” -3.15424 đƣợc -0.12345 -4.12589 tốt -0.36113 . Ta so sánh 3gram với 1gram ta thấy chúng đạt điều kiện thì thêm từ đó vào danh sách gợi ý. 34
35. Chƣơng 3. MỘT SỐ CÔNG CỤ VÀ CHƢƠNG TRÌNH THỬ NGHIỆM 3.1 Một số công cụ: 3.1.1 Bộ công cụ xây dựng mô hình ngôn ngữ - SRILM: SRILM là bộ công cụ để xây dựng và áp dụng các mô hình ngôn ngữ thống kê, chủ yếu là để sử dụng trong nhận dạng tiếng nói,và dịch máythống kê. Bộ công cụ này đƣợc pháttriển bởi “Phòngthí nghiệm và nghiên cứu công nghệ giọng nói SRI” từ năm 1995, có thể chạy trên nền tảng Linux cũng nhƣ Windows. SRILM bao gồm các thành phần sau: - Một tập hợp các thƣ viện C++ giúp cài đặt mô hình ngôn ngữ, hỗ trợ cấu trúc dữ liệu và các chức năng tiện ích nhỏ. - Một tập hợp các chƣơng trình thực thi thực hiện nhiệm vụ xây dựng mô hình ngônngữ,đàotạovàthửnghiệm môhìnhngônngữtrêndữliệu,gắnthẻhoặc phân chia văn bản, BộcôngcụSRILMcórấtnhiềuchƣơngtrìnhcon,đểxâydựng môhình ngôn ngữ ta sử dụng 2 chƣơng trình chính sau: i).N-gram-count: Chƣơngtrình N-gram-countthống kêtầnsố xuất hiện củacáccụm N- gram. Kếtquảcủaviệcthốngkêđƣợcghilạivào mộttệphoặcsửdụngchúngđểxây dựng mô hình ngôn ngữ. Kết quả của việc thống kê đƣợc ghi lại theo định dạng sau: \data\ n-gram 1=n1 35
36. n-gram 2=n2 n-gram N=nN \1-grams: Pw[bow] \2-grams: Pw1w2[bow] \N-grams: pw1. wN \end\ Văn bản trên bắt đầu với một tiêu đề giới thiệu số lƣợng các cụm N- gram vớichiều dài là 1, 2,. n. Tiếp theo, là từng đoạn chứa thông tin về các cụm N-gram có độ dài từ 1 đến n, mỗi đoạn bắt đầu bằng từ khóa \N-grams: trong đó N là độ dài của các cụm N-gram đƣợc liệt kê ở bên dƣới. Mỗi dòng tiếp theo của từng đoạn bắt đầu bằng một số thực là logarit cơ số 10 xác suất của cụm N-gram, tiếp theo là n từ w1, w2,. wn của cụm N-gram đó, và cuối cùng là trọng số truy hồi của cụm N-gram đó (có thể có). Chƣơng trình N- gram-count có một số tùy chọn chính sau: text textfile: thống kê tần số các cụm N-gram từ tệp văn bản đầu vàotextfile. Tệp văn bản này có thể chứa mỗi câu trên một dòng. Kí hiệu kết 36
37. thúc và bắt đầu dòng mới sẽ đƣợc tự động thêm vào nếu trong tệp đầu vào chƣa có. Các dòng trống trong tệp này cũng bị loại bỏ. order n:thiếtlập độ dàilớn nhất của các cụm N-gram sẽthống kê bằng n. Giá trị mặc định nếu không thiết lập tham số này là n = 3 memuse: hiển thị thông tin bộ nhớ mà chƣơng trình sử dụng lm lmfile: xây dựng mô hình ngôn ngữtruy hồitừ cáctần số vừathống kê, sau đó ghi lại vào tệp lmfile theo định dạng ở trên. gtnmin count: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Tham sốnày thiết lập giá trị tần số nhỏ nhất với các cụm N-gram có độ dài là n. Tất cảcác cụm n-gram có độ dài là n, có tần số nhỏ hơn count sẽ bị loại bỏ khỏi mô hình ngôn ngữ. Sau đây là một số tham số thiết lập phƣơng pháp làm mịn cho mô hình ngôn ngữ. Nếu khôngtham số nào dƣới đây đƣợcthiếtlậpthì chƣơngtrìnhsẽ sửdụng phƣơng pháp làm mịn Good-Turing. wbdiscountn: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Sử dụng phƣơng pháp làm mịn Witten-Bell cho N-gram với độ dài là n. kndiscountn: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Sử dụng phƣơng pháp làm mịn của Kneser-Ney đƣợc thay đổi bởi Chen và GoodMan cho N-gram với độ dài là n. ukndiscountn: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Sử dụng phƣơng pháp làm mịn của Kneser-Ney với độ dài là n. addsmoothn delta: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Làm mịn bằng cáchthêm mộtlƣợng delta vàotầnsố củatất cảcác cụm N- gramvới độ dài là n. 37
38. interpolate: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Tính toán tầnsốcủacáccụm N-gramcóđộdàilànbằngcáchnộisuytừcáccụm N-gram có độ dài nhỏ hơn. ii).N-gram: N-gram là chƣơng trình áp dụng mô hình ngôn ngữ để tính xác suất của một câu, tính toán độ hỗn loạn thông tin của văn bản, hay dùng để sinh các câu tiếp theo của một văn bản. Chƣơng trình N-gram có một số tùy chọn chính sau: -order n : thiết lập độ dài lớn nhất của các cụm N-gram sẽ thống kê bằng n. Giá trị mặc định nếu không thiết lập tham số này là n = 3 -memuse: hiển thị thông tin bộ nhớ mà chƣơng trình sử dụng -lm file: đọc mô hình ngôn ngữ từ tệp file. Tham số này là tham số bắt buộc, trừ khi tham số -null đƣợc chọn. -null: không sử dụng mô hình ngôn ngữ đọc từ tệp, mà sử dụng một mô hình ngôn ngữ đặt biệt(xácsuất bằng 1 chotất cả cáctừ). Thamsố nàythƣờng đƣợc sử dụng trong việc gỡ lỗi. -ppltextfile:tínhtoánđiểm(logaritcơsố10củaxácsuất)vàđộhỗnloạn thông tin của tất cả các câu trong tệp textfile, mỗi câu viết trên một dòng. -gen number: sinh ngẫu nhiên number câu từ mô hình ngôn ngữ. 3.1.2 Ngôn ngữ C# C# là một ngôn ngữ lập trình hƣớng đối tƣợng đƣợc phát triển bởi Microsoft. C# đƣợc miêu tả là ngôn ngữ có đƣợc sự cân bằng giữa C++, Visual Basic, Delphi và Java. 38
39. C# là một trong rất nhiều ngôn ngữ lập trình đƣợc hỗ trợ bởi .NET Framework (nhƣ C++, Java,VB ). Đây là một trung tâm biên dịch trong đó tất cả các ngôn ngữ đƣợc hỗ trợ bởi .NET Framework sẽ đƣợc chuyển đổi ra MSIL (một dạng mã trung gian) rồi từ đấy mới đƣợc biên dịch tức thời (Just in time Compiler – JIT Compiler) thành các file thực thi nhƣ exe. Trong kiến trúc .NET Framework chính là CLR (.NET Common Language Runtime), khối chức năng cung cấp tất cả các dịch vụ mà chƣơng trình cần giao tiếp với phần cứng, với hệ điều hành. Đặc điểm của ngôn ngữ lập trình C#, là ngôn ngữ lập trình phản ánh trực tiếp nhất đến .NET Framework mà tất cả các chƣơng trình .NET chạy, và nó phụ thuộc mạnh mẽ vào Framework này. Mọi dữ liệu cơ sở đều là đối tƣợng, đƣợc cấp phát và hủy bỏ bởi trình dọn rác Garbage-Collector (GC), và nhiều kiểu trừu tƣợng khác chẳng hạn nhƣ class, delegate, interface, exception, v.v, phản ánh rõ ràng những đặc trƣng của .NET runtime. Ƣu điểm - C# đƣợc kế thừa những ƣu điểm của C/C++, bỏ đi những dƣ thừa không cần thiết gây khó khăn cho ngƣời sử dụng. - Câu lệnh C# đơn giản, ít từ khóa. Tính năng debug rất thuận tiện. Ngôn ngữ lập trình C# đƣợc đánh giá là dễ học và kết hợp đƣợc nhiều ƣu điểm của các ngôn ngữ lập trình hƣớng đối tƣợng Java và C++. Do đó ngôn ngữ C# đang đựơc ƣu chuộng nhất. - Ngôn ngữ C# là cơ sở để phát triển các ứng dụng windows Form, ASP.NET, Web service Hổ trợ nhiều thƣ viện hàm có sẵn giúp cho ngƣời lập trình lấy hàm dễ dàng và thuận tiện. Nhƣợc điểm 39
40. - C# chỉ có thể chạy đƣợc trên nền Windows và .NET Famework. Vì vậy nó hạn chế phạm các ứng dụng của C#. Đó là nhƣợc điểm lớn nhất của C# với các ngôn ngữ lập trình khác. 3.2 Chƣơng trình thực nghiệm Chƣơng trình sử dụng mô hình ngôn ngữ n-gram để kiểm tra và sửa lỗi chính tả cho dữ liệu Blog. Dữ liệu: Dữ liệu huấn luyện n-gram: sử dụng bộ dữ liệu Việt Treebank và các dữ liệu đƣợc thu thập từ các trang: Wikipedia.org, dantri.com.vn, vnExpress.net. Dữ liệu bao gồm nhiều chủ đề khác nhau nhƣ: toán học, vật lý, khoa học, triết học, lịch sử, kinh tế, thể thao, luật, tin tức, giải trí, Tính n-gram với các unigram, bigram, trigram và loại bỏ các n-gram có tần xuất nhỏ hơn 5. Từ điển âm tiết: lƣu trong file syllables.txt Dữ liệu test:Văn bản đƣợc thu thập từ các trang web đƣợc lƣu trong file: testvb.txt Hình 3.1Sơ đồ chương trình kiểm tra lỗi chính tả: Vẽ lại theo bài báo 5. 40
41. Chƣơng trình kiểm tra chính tả là chƣơng trình kiểm tra lỗi chính tả dữ liệu Blog tiếng Việt đơn giản. Chƣơng trình sử dụng dữ liệu đầu vào là file text chứa dữ liệu blog đƣợc thu thập, sử dụng n-gram để kiểm tra và sửa lỗi. Hình 3.2. Giao diện của chương trình. KẾT LUẬN Đồ án đãtìm hiểu cách tiếp cận, và một số phƣơng pháp giảiquyết bài toán kiểm lỗi chính tả tiếng Việt. Trọng tâm của Đồ án là tìm hiểu phƣơng pháp sửdụng mô hình ngôn ngữ N-gram để kiểm tra lỗi chính tả dữ liệu blog tiếng Việt. Các kết quả chính đạt đƣợc là: - Nắm đƣợc mô hình ngôn ngữ N-gram và ứng dụng nó vào bàitoàn kiểm tra lỗi chính tả dữ liệu blog tiếng Việt. - Cài đặt chƣơng trình thực nghiệm trên c# 41
42. Các vấn đề tồn tại: - Đồ án mới chỉ dừng lại ở mức tìm hiểu phƣơng pháp và cài đặt thử nghiệm. Chƣa có thống kê, đánh giá cho phƣơng pháp. Vẫn còn một số lỗi gợiý sai. - Tốc độ chƣơng trình còn chậm do chƣa tối ƣu bộ nhớ lƣu trữ n-gram Công việc tiếp theo em dự kiến là: - Xây dựng bộ ngữ liệu đủ lớn và bao trùm cho huấn luyện dữ liệu n- gram. - Phân tích và đánh giá phƣơng pháp, trên cơ sở đó có thể nghiên cứu sử dụng các tri thức ngôn ngữ nâng cao hơn nhƣ từ, ngữ pháp, ngữ nghĩa để làm tăng độ chính xác cho thuật toán. - Tối ƣu hóa tốc độ và bộ nhớ cho các quá trình kiểm lỗi. 42
43. TÀI LIỆU THAM KHẢO 1. “Sử dụng luật cấu tạo âm tiết tiếng Việt hai thành phần trong bài toán kiểm tra chính tả tiếng Việt” (Vietnamese Text Spelling Checking Based on Two-IngredientsVietnamese Syllable Composition Rule), Đinh Thị Phƣơng Thu, Huỳnh Quyết Thắng, Nguyễn Văn Lợi. 2. Kỹ thuật mã hóa âm tiết và các mô hình n-grams ứng dụng kiểm lỗi dùng từ và cụm từ tiếng việt, Trần Ngọc Anh, Đào Thanh Tĩnh. Tạp trí công nghệ và truyền thông – các công trình nghiên cứu, pháp triển và ứng dụng CNTT-TT. 3. Parallel Spell-Checking Algorithm Based on Yahoo! N-Grams Dataset Yousse Bassil LACSC – Lebanese Association for Computational Sciences Registered under No. 957, 2011, Beirut, Lebanon. 4. A Survey of Spelling Error Detection and Correction Techniques Ritika Mishra, Navjot Kaur, 2013. 5. Using Large N-gram for Vietnamese Spell Checking, Nguyen Thi Xuan Huong, Tran-Thai Dang, The-Tung Nguyen, and Anh-Cuong Le, KSE 2014. 6. Levenshtein Distance Technique in Dictionary Lookup Methods: An Improved Approach Rishin Haldar and Debajyoti Mukhopadhyay Web Intelligence & Distributed Computing Research Lab Green Tower, C- 9/1, Golf Green, Calcutta 700095, India 43