Luận văn Kiểm lỗi chính tả tiếng việt

hương pháp kiểm lỗi chính tả Ta có thể tạm chia ra hai phương pháp chính đó là dựa vào luật và dựa vào thống kê. Các phương pháp dựa theo luật có ưu điểm là không tốn quá nhiều tài nguyên của 3 thiết bị, tuy nhiên các chương trình sử dụng phương pháp này không có khả năng học, và hiện tại kết quả cũng chưa cao đối với nhiều ngôn ngữ. Có khá nhiều phương pháp dựa vào thống kê khác nhau đã được đưa ra để kiểm lỗi chính tả tiếng Anh. Trong phạm vi giới hạn của luận văn, chúng tôi xin chỉ liệt kê một vài phương pháp được đánh giá là nổi bật. “Một số nghiên cứu sử dụng mô hình kênh nhiễu như Mays và cộng sự (1990), Church và Gale (1991), Brill và Moore (2001)”. “Phương pháp lai Bayes, sử dụng hàm phân loại Naive Bayes”. “Kết hợp mô hình trigram từ loại và hàm phân loại Bayes”. Các phương pháp: “học dựa trên biến đổi (Mangu và Brill, 1997), phân tích nghĩa ẩn (Jones và Martin, 1997), differential-grammars (Powers, 1997), Winnow- based (Golding và Roth, 1999), và khôi phục cố kết từ vựng (Hirst và Budanitsky, 2001)”1 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ệt là một ngôn ngữ đơn lập, quan hệ giữa các từ được biểu thị 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) Âm tiết là đơn vị phát âm tự nhiên nhỏ nhất trong ngôn ngữ. Trong tiếng Việt, một âm tiết bao giờ cũng được phát ra với một thanh điệu, và khi viết được tách rời với âm tiết khác bằng một khoảng trống. Trên chữ viết, mỗi âm tiết tiếng Việt được ghi thành một “chữ” và đọc thành một “tiếng”. Có 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 2.1. Cấu trúc 3 thành phần: [Phụ âm] 1 Nguyễn Phương Thái, Kiểm lỗi chính tả cảm ngữ cảnh tiếng Việt, 2003, Luận văn thạc sĩ, Hà Nội 4 Bảng 2.2. Cấu trúc 4 thành phần: [Phụ âm đầu] [Phụ âm cuối] Bảng 2.3. Cấu trúc 5 thành phần: Vần [Âm đầu] [Âm đệm] [Âm cuối] - 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. Luận văn này sử dụng cấu trúc âm tiết bốn thành phần. Bảng 2.4. Các thành phần âm tiết: Phụ âm đầu b c d đ g h k l m n q r s t v x ch gh gi kh ng nh ph qu th tr ngh Nguyên âm a ă â e ê i o ô ơ u ư y ai ao au ay âu ây eo êu ia iu iê oa oă oe oi oo ôi ơi ua uâ ui uê uô uơ uy ưa ưi ươ ưu yê oai oay uây uôi iêu uyê ươu ươi uya yêu uyu Phụ âm cuối c p t m n ch ng nh Thanh điệu Ngang, huyền, hỏi, ngã, sắc, nặng  Từ: Từ là đơn vị ngôn ngữ có nghĩa hoàn chỉnh. Từ tiếng Việt bao gồm một hay 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: 5 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ấu thanh được đánh khá tùy tiệ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. Hiện tại với các trường hợp nguyên âm là oa, oe, uy mà không có phụ âm kết thúc như hòa, hòe, thùy… có hai cách đánh dấu thanh là: hòa hoặc hoà. Ở luận văn này thống nhất cách viết thứ nhất – hòa – giống như các quy tắc đánh dấu thanh ở trên. 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ó trong từ điển, có trong từ điển nhưng sai về ngữ nghĩa, sai cấu tạo nhưng có thể là từ tiếng nước ngoài. Các lỗi sai về cấu tạo âm tiết có thể dễ dàng phát hiện bằng cách sử dụng từ điển, tập âm tiết. Dưới đây chúng tôi chỉ tập trung đến các lỗi sai về nghĩa của từ khi âm tiết có trong từ điển. Có nhiều nguyên nhân khác nhau dẫn đến các lỗi trên, trong luận văn này chúng tôi chỉ xét đến hai nguyên nhân: do đánh máy và do lỗi phát âm (tiếng địa phương). 1.3.1. Lỗi do đánh máy Đây là loại lỗi phổ biến, và hầu hết đều ở mức âm tiết. Loại lỗi này gây ra các lỗi sai chính tả đơn và lỗi chính tả phức. Có bốn loại lỗi chính tả đơn: 6 - Chèn: như nhầm “an” thành “anh” - Xoá: như nhầm “chung” thành “chun” - Thay thế: như nhầm “vào” thành “cào” - Hoán vị: như nhầm “hoà” thành “hào” Lỗi chính tả phức là sự kết hợp liên tiếp trong số các lỗi chính tả đơn ở trên. Để phát hiện được lỗi và đưa ra gợi ý sửa lỗi, chúng ta cần xác định được tập nhầm lẫn âm tiết của âm tiết mà ta đang xét. Với các lỗi do đánh máy, tập nhầm lẫn âm tiết được sinh ra gồm các âm tiết có “khoảng cách soạn thảo” (edit distance) so với âm tiết đang xét nhỏ hơn một ngưỡng chọn trước. Khoảng các soạn thảo cho biết mức độ khác nhau giữa xâu ban đầu và xâu bị biến đổi. Trước khi tính khoảng cách soạn thảo nhỏ nhất, chúng tôi tách riêng dấu thanh và biến đổi xâu ban đầu đã loại bỏ dấu về dạng đánh máy TELEX. Ví dụ: “chào” -> “chao” + “f”, “trưởng” -> “truwowng” + “r”. Khi đó, việc tính khoảng cách soạn thảo sẽ cho kết quả tính giá tương đối đúng với việc soạn thảo trên bàn phím. Việc tính giá cho phép thay thế dựa vào vị trí các phím trên bàn phím. Các phím liền kề nhau có giá thấp hơn so với các phím không liền kề (c -> v nhỏ hơn c -> s). Để tạo tập nhầm lẫn cho các lỗi soạn thảo, chúng tôi tách từ ban đầu ra thành 4 phần theo cấu trúc âm tiết, sau đó xử lý từng phần và ghép chúng lại với nhau. VD: âm tiết (sai) hcào được tách ra thành 4 phần và được xử lý: - hc: c, ch, h,… -> cào, chào, hào,… - ao: oa, eo, au,… -> hcòa, hcèo, hcàu,… - (rỗng): n, m, t,… -> hcàon, hcàom, hcàot,… - f(dấu huyền): s, r, x,… -> hcáo, hcảo, hcão,… Tiếp đó, các âm tiết mới được tạo ra sẽ được kiểm tra trong từ điển âm tiết1, âm tiết có trong từ điển sẽ được đưa vào tập nhầm lẫn âm tiết và tập này sẽ được sắp xếp theo thứ tự tăng dần về khoảng cách soạn thảo so với âm tiết ban đầu. 1.3.2. Lỗi do phát âm 1 Hoàng Phê (chủ biên), Từ điển tiếng Việt, 2002, Nhà xuất bản Đà Nẵng 7 Lỗi do phát âm xảy ra cả trong văn bản viết tay và văn bản đánh máy. Lỗi này xảy ra do thói quen “đọc như thế nào thì viết như thế”, do đó lỗi này thường gắn liền với các phương ngữ. VD: nhiều -> nhìu; hỏi -> họi; ra, gia -> da… Có thể tập hợp một số lỗi phát âm theo như trong bảng Phụ lục 2. Tập nhầm lẫn do phát âm có tính đối xứng, tức là các âm trong cùng một tập có thể nhầm lẫn với nhau. Để đưa ra các đề nghị cho loại lỗi này chỉ cần tra âm tiết dựa vào bảng lỗi phát âm. 1.4. Mục tiêu của luận văn Do nhược điểm của phương pháp kiểm lỗi chính tả tiếng Việt chỉ dựa theo luật là khá phức tạp và không có khả năng học. Luận văn này hướng tới việc tìm hiểu và ứng dụng kiểm lỗi chính tả tiếng Việt mức độ từ vựng dựa vào thông tin ngữ cảnh, sử dụng phương pháp học máy thống kê trên mô hình ngôn ngữ n-gram. Nhờ khả năng học, chương trình có thể thích ứng được với sự thay đổi không ngừng của ngôn ngữ mà không tốn quá nhiều công sức của con người. Đồng thời, luận văn cũng đề xuất việc kiểm lỗi chính tả trực tuyến và cài đặt chương trình ứng dụng chạy trên nền web, dựa trên phương pháp lý thuyết được nêu ra trong luận văn. 8 Chương 2: Mô hình ngôn ngữ Chương này nhắc lại một số lý thuyết về n-gram và đưa ra hướng tiếp cận sử dụng n-gram vào việc kiểm lỗi chính tả cảm ngữ cảnh. Chương này có tham khảo tài liệu [1]. 2.1. Giới thiệu Mô hình n-gram là một mô hình xác suất sử dụng cho việc dự đoán phần tử tiếp theo trong một dãy tuần tự các đối tượng. Các đối tượng chúng ta xét tới ở đây là các âm tiết và dấu câu. 2.2. Tính toán xác suất dựa trên n-gram Giả sử ta muốn dự đoán âm tiết tiếp theo s5 dựa trên thông tin ngữ cảnh trước đó của các âm tiết s1s2s3s4. Chúng ta cần tính xác suất của sự kiện âm tiết tiếp theo là s5 khi các âm tiết trước nó là s1…s4, hay nói cách khác, ta cần tìm xác suất: P(s1,…,s5) Tổng quát, với sn, ta cần tìm: P(s1,…,sn) Theo quy tắc dây chuyền (chain rule) ta có: P(s1,…,sn) = P(s1).P(s2|s1)…P(sn|s1,…,sn-1) Áp dụng công thức trên cho một câu có n âm tiết, ta sẽ tìm ra được tổ hợp âm tiết “tốt nhất” cho câu, và tổ hợp này được coi là đúng chính tả. Tuy nhiên, việc tính xác suất đó trong thực tế là điều gần như không thể: bởi chúng hiếm khi xảy ra, và nếu có thể tính được thì cũng cần có một lượng dữ liệu rất lớn được dùng để tính toán. Để giải quyết vấn đề trên, chúng ta có thể xấp xỉ những xác suất đó bằng một giá trị n-gram nhất định với n cho trước. Với n = 1, ta có 1-gram (Unigram): P(sn|s1,…,sn-1)  P(sn) Với n = 2, ta có 2-gram (Bigram) P(sn|s1,…,sn-1)  P(sn|sn-1) 9 Với luận văn này, chúng tôi chọn n = 3 (Trigram). Trong chương trình ứng dụng, chúng tôi sử dụng kết hợp linh hoạt cả unigram, bigram và trigram (không nhất thiết chỉ sử dụng trigram) để tính toán xác suất của một âm tiết trong những trường hợp một câu có quá nhiều lỗi sai hay có nhiều lỗi sai đứng sát nhau dẫn đến thiếu thông tin do giới hạn của phạm vi ngữ cảnh 3 âm tiết. 2.3. N-gram đơn giản Ở phần này, chúng tôi nêu lên cách sử dụng n-gram vào việc dự đoán một từ trong tiếng Anh, từ đó suy ra cách áp dụng phương pháp cho âm tiết trong tiếng Việt. Giả sử chúng ta có thông tin lịch sử h là “its water is so transparent that” và chúng ta muốn tính toán xác suất từ w tiếp theo sẽ là “the”: P(the|its water is so transparent that) Để tính toán xác suất trên ta có thể dựa vào tần suất xuất hiện của w và h. Ví dụ, chúng ta có thể lấy một lượng dữ liệu đầu vào (corpus) rất lớn, đếm số lần xuất hiện của h và số lần xuất hiện w đi theo sau h. Việc này có thể trả lời được câu hỏi: “Trong tổng số lần xuất hiện h, có bao nhiêu lần đứng tiếp sau nó là w”: Với một corpus đủ lớn, như internet chẳng hạn, chúng ta có thể đếm được các tần suất và ước lượng được xác suất nêu ở công thức trên. Tuy nhiên, chúng ta có thể dễ dàng nhận thấy rằng ngay cả dữ liệu trên internet cũng không đủ lớn để cho ta những ước lượng tốt trong hầu hết các trường hợp thực tế. Bởi lẽ ngôn ngữ con người hết sức sáng tạo, nó biến đổi không ngừng, và do đó mà không phải lúc nào chúng ta cũng có thể đếm được toàn bộ các câu nói. Thậm chí chỉ một sửa đổi nhỏ của một câu thôi cũng có thể khiến số lần xuất hiện của nó trên web là bằng không. Tương tự như vậy, nếu chúng ta muốn biết xác suất liên kết của toàn bộ chuỗi từ W như “its water is so transparent”, chúng ta có thể đặt ra câu hỏi “trong toàn bộ tổ hợp khác nhau có thể có của chuỗi 5 từ đó, có bao nhiêu trong số chúng có thứ tự như trên?”. Chúng ta sẽ phải đếm số lần xuất hiện của “its water is so transparent” và sau đó chia chúng cho tổng số lần xuất hiện của từng từ trong số 5 từ đó. Việc này đòi hỏi một lượng tính toán không hề nhỏ. 10 Chính bởi lẽ đó, chúng ta cần có những phương pháp tốt hơn để ước lượng giá trị xác suất của từ w với thông tin lịch sử h cho trước, và xác suất của toàn bộ chuỗi từ W. Để dễ dàng hơn trong việc diễn đạt, chúng ta sẽ có một vài quy ước như sau: Để biểu thị xác suất của một biến độc lập ngẫu nhiên Xi lấy giá trị là “the”, hay P(Xi = “the”), chúng ta sẽ rút gọn lại là P(the). Chuỗi N từ có thể biểu diễn dạng w1…wn hoặc . Với xác suất liên kết của từng từ riêng biệt trong chuỗi: P(X = w1, Y = w2, … ,) được thay bằng P(w1,w2,…,wn). Để tính xác suất P(w1,w2,…,wn) của các chuỗi từ, ta có thể phân tích xác suất này sử dụng quy tắc dây chuyền: Áp dụng cho từ, ta có: Quy tắc dây chuyền cho thấy mối liên hệ giữa việc tính xác suất liên kết của một chuỗi với việc tính xác suất điều kiện của một từ với các từ cho trước. Công thức trên cho thấy ta có thể ước lượng xác suất liên kết của một chỗi bằng cách nhân các xác suất điều kiện với nhau. Tuy nhiên, sử dụng quy tắc dây chuyền vẫn chưa giải quyết được vấn đề mà chúng ta đã đề cập ở trên: Ta không thể ước lượng xác suất bằng cách đếm số lần xuất hiện của chuỗi từ, bởi ngôn ngữ rất phong phú, từng ngữ cảnh riêng biệt đều có thể chưa bao giờ xuất hiện trước đó. Có thể hiểu việc sử dụng mô hình n-gram là thay vì tính xác suất của từ cho trước dựa trên toàn bộ thông tin lịch sử h, chúng ta xấp xỉ thông tin đó chỉ bằng một vài từ cuối, gần nhất. 11 Ví dụ với mô hình bigram, xấp xỉ xác suất của một từ cho trước với toàn bộ từ trước đó bằng xác suất điều kiện của từ đứng ngay trước nó . Hay nói cách khác, thay vì tính xác suất: P(the|Walden Pond’s water is so transparent that) Chúng ta xấp xỉ nó bởi xác suất: P(the|that) Việc này giả thiết rằng xác suất của một từ chỉ phụ thuộc vào từ trước đó, được gọi là một giả thuyết Markov (Markov assumption). Các mô hình Markov là một lớp các mô hình xác suất giả thiết rằng chúng ta có thể dự đoán được xác suất của một đơn vị (unit) nào đó trong tương lai mà không cần phải dựa vào quá nhiều thông tin trong quá khứ. Chúng ta có thể suy ra được bigram (lấy thông tin của một từ trước đó), trigram (lấy thông tin của hai từ trước đó) cho tới N-gram (lấy thông tin của N – 1 từ đứng trước). Suy ra công thức tổng quát xấp xỉ N-gram cho xác suất điều kiện của từ tiếp theo trong một chuỗi là: Từ giả thiết bigram cho xác suất của một từ độc lập, chúng ta có thể tính xác suất của một chuỗi đầy đủ bằng cách áp dụng công thức trên với N = 2 với công thức của quy tắc dây chuyền: Vậy làm thế nào để ước lượng được các giá trị xác suất bigram hay n-gram này? Một cách đơn giản và dễ nhận thấy nhất để ước lượng xác suất đó là ước lượng hợp lý cực đại (Maximum Likelihood Estimation hay MLE). Chúng ta dùng MLE cho các tham số của một mô hình n-gram bằng cách đếm trong corpus, và chuẩn hóa chúng sao cho giá trị của nó nằm giữa 0 và 1. Ví dụ, để tính một giá trị xác suất bigram của một từ y với từ cho trước x đứng trước nó, chúng ta sẽ tính toán giá trị đếm bigram C(xy) và chuẩn hóa nó với tổng số tất cả các bigram khác cùng có từ đứng trước là x: 12 Chúng ta có thể đơn giản hóa công thức trên, khi tổng số lần xuất hiện của tất cả các bigram bắt đầu bởi từ wn-1 cho trước phải bằng với giá trị unigram cho từ wn-1 đó: Với trường hợp tổng quát sử dụng MLE cho N-gram, ta có công thức: 2.4. Làm mịn (smoothing) Có một vấn đề gặp phải trong quá trình tính toán ước lượng hợp lý cực đại, đó là vấn đề dữ liệu thưa (sparse data) xảy ra do ước lượng hợp lý cực đại dựa trên một tập dữ liệu huấn luyện riêng biệt. Với một n-gram bất kỳ, đôi khi chúng ta có thể có được xấp xỉ tốt của xác suất. Nhưng do bất kỳ corpus nào cũng có giới hạn nhất định, một vài từ nào đó hoàn toàn chính xác nằm trong chuỗi lại không xuất hiện trong corpus. Lượng dữ liệu bị thiếu này cho thấy N-gram cho bất kỳ một corpus cho trước nào cũng có một số lượng lớn trường hợp xác xuất N-gram bằng không cần có một xác suất nào đó khác không cho nó. Hơn nữa, phương pháp ước lượng hợp lý cực đại cũng sinh ra các xấp xỉ không tốt khi các giá trị đếm khác không nhưng lại quá nhỏ, dẫn đến giá trị ước lượng xấp xỉ bằng không. Chúng ta cần có một phương pháp giúp có được những ước lượng tốt hơn so với những tần suất thấp hay tần suất bằng không. Các giá trị đếm bằng không thậm chí còn gây ra một vấn đề nghiêm trọng hơn. Khi xử lý hiện tượng nhập nhằng cho một câu, mà câu đó lại chứa một giá trị N-gram không hề xuất hiện trong tập huấn luyện, thì ước lượng hợp lý cực đại xác suất của N-gram này, cũng như của toàn bộ câu, sẽ có giá trị bằng không! Điều này có nghĩa rằng để đánh giá được mô hình ngôn ngữ, chúng ta cần thay đổi phương thức ước lượng hợp lý cực đại sao cho tất cả các giá trị N-gram đều phải khác không, kể cả khi chúng không xuất hiện trong tập huấn luyện. Vì những lý do nêu trên, chúng ta cần sử dụng các phương pháp làm mịn để giải quyết, giảm thiểu các vấn đề gặp phải do lượng dữ liệu có hạn. Ở luận văn này, chúng 13 tôi chỉ sử dụng phương pháp làm mịn Laplace (Laplace Smoothing, hay còn gọi là Add One Smoothing – thêm một). Một cách làm mịn đơn giản là cộng thêm 1 vào tất cả các giá trị đếm trước khi chúng ta chuẩn hóa chúng thành giá trị xác suất. Giải thuật này được gọi là làm mịn Laplace, hay luật Laplace(Lidstone, 1920; ?; Jeffreys, 1948). Chúng ta sẽ áp dụng làm mịn Laplace bắt đầu với các xác suất unigram. Ước lượng xấp xỉ cực đại của xác suất unigram cho từ wi là giá trị đếm ci được chuẩn hóa bởi tổng số từ vựng N: Làm mịn Laplace chỉ đơn giản cộng một vào mỗi giá trị đếm. Và khi trong bảng từ vựng có V từ (hay V là tổng số từ có trong tập dữ liệu), mỗi từ được cộng thêm một, chúng ta cũng cần cộng thêm vào mẫu số một giá trị là V: Tương tự như vậy, với các giá trị xác suất bigram ta có công thức làm mịn: Trong đó V là số loại từ (mỗi từ khác nhau được coi là một loại) có trong tập dữ liệu, hay V chính là số lượng các unigram. Và như vậy ta có thể phát triển tính tương tự cho các giá trị N-gram khác như 3-gram, 4-gram,… Có một giải pháp khá hiệu quả cho việc tính toán các giá trị xác suất n-gram trên máy tính đó là sử dụng dạng logarit hóa của các giá trị xác suất. Vì sau khi làm mịn như ở trên, tất các xác suất P đều có giá trị nằm trong khoảng 0 < P < 1. Do đó, việc logarit hóa giúp cho tránh được vấn đề về giới hạn dữ liệu do giá trị xác suất quá nhỏ, nằm ngoài khả năng biểu thị của kiểu dữ liệu (underflow), đặc biệt là khi ta nhân nhiều giá trị xác suất n-gram với nhau. Vì khi giá trị quá nhỏ, máy tính sẽ coi nó bằng không, và đồng thời cũng làm tăng tốc độ tính toán do thay vì nhân – chia các giá trị với nhau thì với logarit, chúng trở thành các phép toán cộng – trừ, một công việc dễ dàng hơn nhiều cho bộ xử lý. Ví dụ: p1.p2.p3.p4 = exp(log p1 + log p2 + log p3 + log p4) 14 2.5. Áp dụng cho tiếng Việt Do đặc điểm của tiếng Anh, các từ được ngăn cách nhau bởi khoảng trắng hoặc các dấu câu. Tuy nhiên trong tiếng Việt, một từ có thể được kết hợp bởi nhiều âm tiết (tiếng), các âm tiết của từ được cách nhau bởi khoảng trắng. Tuy nhiên trong tiếng Việt, trật tự của các tiếng trong một từ là một trong những yếu tố quyết định nghĩa của từ đó, do vậy ta hoàn toàn có thể áp dụng mô hình n-gram cho tiếng Việt với đơn vị là một âm tiết. Và khi đó, các giá trị biểu thị cho một từ wi ở trên có thể được hiểu như một âm tiết trong tiếng Việt. 15 Chương 3: Phương pháp kiểm lỗi chính tả tiếng Việt dựa trên n-gram Như đã trình bày ở chương trước, 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ó. Trong chương này, chúng tôi xin trình bày 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. 3.1. Collocation Thuật ngữ collocation mà chúng tôi sử dụng ở đây dùng để chỉ các âm tiết đứng liền kề nhau trong phạm vi “cửa sổ từ” (hay chính xác hơn là “cửa sổ âm tiết”). Trong luận văn này, chúng tôi 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 âm tiết đang xét là s, ta xét 2 âm tiết đứng trước là b2, b1 và xét 2 âm tiết đứng sau là a1, a2. Như vậy thứ tự sẽ là: b2 b1 s a1 a2 Chúng tôi tính tần suất n-gram theo âm tiết, bao gồm unigram, 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. Ngoài việc xét đến các âm tiết tiếng Việt, chúng tôi cũng phân loại một số thành phần đặc biệt khác trong câu như dấu câu, chữ số, ngày tháng, chữ viết hoa. Cụ thể: - numbergroup: 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 - capitalword: dãy các âm tiết được viết hoa chữ cái đầu đứng liền nhau (dãy này có thể chỉ chứa một âm tiết). VD: “Nguyễn văn A” sẽ được chuyển thành “capitalword văn capitalword”, và “trường Công Nghệ” sẽ được chuyển thành “trường capitalword”. - webaddressgroup: các địa chỉ web có dạng như Việc phân loại trên chúng tôi sử dụng các pattern tương ứng và biểu thức chính quy (Regular Expression) để xử lý xâu ký tự. 16 3.2. Huấn luyện Việc huấn luyện được thực hiện trên văn bản tiếng Việt đã được phân tích và chuẩn hóa thành các loại như trên. Dữ liệu văn bản thô được lấy từ internet, cụ thể là từ năm nguồn: báo Dân trí (dantri.com.vn), báo VietNamNet (vietnamnet.vn), báo VnExpress (vnexpress.net), báo Lao Động (laodong.com.vn), website về văn học Việt Nam và thế giới vanhoc.xitrum.net. Dữ liệu trên được lấy từ internet dưới dạng HTML, sau đó được xử lý, loại bỏ các mã HTML và các nội dung không cần thiết (các menu, quảng cáo…), tách câu và lưu dưới dạng tệp văn bản Unicode. Việc này được thực hiện bởi Cao Văn Việt, luận văn “Xây dựng mô hình ngôn ngữ cho tiếng Việt”. Công đoạn đánh dấu văn bản, phân tích từ tố (tokenize), chuẩn hóa dấu câu (hoà -> hòa…) được thực hiện ngay trong quá trình huấn luyện. Điều này thuận tiện cho việc đưa dữ liệu huấn luyện thêm sau này, và có thể sử dụng để học theo hình thức “người dùng đóng góp”, do chương trình hoạt động trên môi trường web (tương tự như tính năng đóng góp bản dịch tốt hơn của Google Translate). Như đã trình bày ở trên, dữ liệu được tách thành từng câu, mỗi câu sẽ lại được phân loại các thành phần đặc biệt (số đếm, ngày tháng…) và từ đó phân tích từ tố, phục vụ cho việc thống kê tần suất n-gram. Dữ liệu thống kê n-gram được chúng tôi lưu trên hệ quản trị cơ sở dữ liệu (CSDL) MySQL. Các thống kê unigram, bigram, trigram được lưu trữ trong 3 bảng (table) riêng biệt. Mỗi bảng đều chứa thông tin các âm tiết, thứ tự của chúng và số lần xuất hiện của tổ hợp đó trong corpus. Ngoài ra, để thuận tiện cho việc truy vấn và tính toán, chúng tôi có 2 bảng dữ liệu khác là bảng danh sách các âm tiết trong tiếng Việt (6699 bản ghi), bảng còn lại lưu trữ thông tin về số lượng bản ghi và tổng các giá trị tần suất của mỗi bảng trong 3 bảng huấn luyện kể trên. Bảng thông tin này được sử dụng trong việc tính các xác suất n-gram và làm mịn. Chương trình sử dụng bộ dữ liệu huấn luyện là tệp văn bản đầu vào có kích thước 300MB, sau khi chạy phần huấn luyện cho unigram, bigram và trigram chúng tôi thu được 3 bảng với thông tin như sau: 17 Bảng thông in các bảng dữ liệu huấn luyện: Bảng Số bản ghi Tổng giá trị đếm Kích thước tệp dữ liệu MySQL sinh ra Ct_unigram 7597 52,030,196 316KB Ct_bigrams 1,788,725 49,354,488 96,635KB Ct_trigrams 12,409,262 52,030,066 736,667KB Chú ý: dấu phẩy (,) ở trên dùng để phân cách phần nghìn, triệu. Do một số đặc điểm của hệ CSDL MySQL và ngôn ngữ lập trình web PHP, chúng tôi có thực hiện một số kỹ thuật nhằm tăng tốc độ huấn luyện, tính toán. Những kỹ thuật đó chúng tôi sẽ trình bày trong chương sau. 3.3. Thuật toán kiểm lỗi Phần này chúng tôi sẽ trình bày hai thuật toán kiểm lỗi chính tả cho một câu. Hai thuật toàn này về cơ bản là giống nhau, chỉ khác nhau ở bước soát lỗi và quyết định âm tiết nào là “đúng”. Thuật toán của chúng tôi bao gồm hai bước: - Sinh tập nhầm lẫn âm tiết. - Sử dụng n-gram lựa chọn các âm tiết tốt nhất trong tập nhầm lẫn âm tiết. Ở bước thứ hai, chúng tôi đưa ra hai thuật toán, tạm gọi là thuật toán thứ nhất và thuật toán thứ hai. Thuật toán thứ nhất coi tất cả các âm tiết trong câu là sai; thuật toán thứ hai giả thiết chỉ có một âm tiết sai và các âm tiết khác đều đúng. Chi tiết chúng tôi xin trình bày dưới đây. 3.3.1. Sinh tập nhầm lẫn âm tiết Công đoạn sinh ra tập nhầm lẫn âm tiết được thực hiện riêng biệt cho từng âm tiết, sau khi đã được phân tách từ tố. Với mỗi âm tiết, chúng tôi dùng hàm phân tích cấu tạo âm tiết tiếng Việt, tách âm tiết đó thành 4 phần: phụ âm đầu, nguyên âm, phụ âm cuối, dấu thanh. Chúng tôi phân tích dựa vào bảng các nguyên âm, phụ âm và dấu thanh của một âm tiết. Với điều kiện rằng một âm tiết phải có nguyên âm, chúng tôi xác định vị trí nguyên âm trong âm tiết trước, từ phần nguyên âm được trích xuất, chúng tôi xác định được dấu thanh của âm tiết. Công đoạn trên dựa vào kết quả của hàm chuyển đổi từ dạng có dấu sang dạng đánh máy TELEX. 18 Tiếp đó, khi đã xác định được nguyên âm, ta có thể dễ dàng xác định được phần phụ âm đầu và phụ âm cuối của âm tiết đó. Phụ âm đầu và phụ âm cuối của nguyên âm đều có thể là rỗng (âm tiết chỉ có nguyên âm). Việc xác định này có thể trích xuất được các thành phần của âm tiết ngay cả khi âm tiết đó bị đánh máy sai do chúng tôi xác định các “khu vực” của âm tiết dựa vào khoảng ký tự liền nhau lớn nhất nằm trong các bảng nguyên âm và phụ âm. Ví dụ: - âm tiết: đào Dạng telex: ddaof Xâu telex còn lại Vị trí bắt đầu của nguyên âm: 2 => Phụ âm đầu: dd -> đ aof => Phụ âm cuối: (rỗng) aof => Nguyên âm: aof -> ao f => Dấu thanh: f (dấu huyền) - âm tiết: đườgn (âm tiết này bị đánh máy sai) Dạng telex: dduwowfgn Vị trí bắt đầu của nguyên âm: 2 => Phụ âm đầu: dd -> đ uwowfgn => Phụ âm cuối: gn uwowf => Nguyên âm: uwowf -> ươ f => Dấu thanh: f Từ kết quả ở trên, chúng tôi tạo tập nhầm lẫn âm tiết dựa trên lỗi đánh máy cho từng phần của âm tiết. Do chỉ xét đến các trường hợp lỗi sai do đánh máy nhầm, và lỗi sai do phát âm nên chúng tôi coi mỗi âm tiết chỉ sai duy nhất một trong 4 thành phần kể trên (không xét các trường hợp cố ý đánh sai chính tả). Với mỗi âm tiết, sau khi được chia ra 4 thành phần như trên, chúng tôi thực hiện việc tạo tập nhầm lẫn cho từng thành phần, sau đó kết hợp với các phần còn lại. Với 19 mỗi thành phần mới được tạo ra, chúng tôi so sánh với thành phần ban đầu bằng cách tính toán khoảng cách soạn thảo nhỏ nhất (Minimum Edit Distance - MED), các thành phần được tạo ra có MED lớn hơn ngưỡng chọn trước sẽ bị loại bỏ. Ở đây chúng tôi chọn ngưỡng MED là 1 cho phụ âm và 2 cho nguyên âm, không xét MED đối với dấu thanh. Chương trình sử dụng giải thuật Damerau–Levenshtein distance dựa trên thuật toán quy hoạch động tính khoảng cách soạn thảo nhỏ nhất được công bố bởi Wagner và Fischer. Giải thuật này có tính đến giá (cost) của phép hoán vị (giải thuật ban đầu coi phép hoán vị là kết hợp của phép chèn và xoá). Dưới đây là giả mã của thuật toán MED: int DamerauLevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2]) // d is a table with lenStr1+1 rows and lenStr2+1 columns declare int d[0..lenStr1, 0..lenStr2] // i and j are used to iterate over str1 and str2 declare int i, j, cost //for loop is inclusive, need table 1 row/column larger than string length. for i from 0 to lenStr1 d[i, 0] := i for j from 1 to lenStr2 d[0, j] := j //Pseudo-code assumes string indices start at 1, not 0. //If implemented, make sure to start comparing at 1st letter of strings. for i from 1 to lenStr1 for j from 1 to lenStr2 d[i, j] := minimum( d[i-1, j ] + del-cost(str1[i]), // deletion d[i , j-1] + ins-cost(str2[j]), // insertion d[i-1, j-1] + subs-cost(str1[i],str2[j]) // substitution ) if(i > 1 and j > 1 and str1[i] = str2[j-1] and str1[i-1] = str2[j]) then d[i, j] := minimum( d[i, j], d[i-2, j-2] + cost // transposition ) return d[lenStr1, lenStr2] 20 Sau khi kết hợp, âm tiết mới được tạo ra, chúng tôi kiểm tra các âm tiết đó trong từ điểm âm tiết tiếng Việt để loại bỏ những âm tiết không có trong tiếng Việt. Cần làm việc này do thành phần bị đánh máy sai có thể không phải thành phần mà ta đang xét. Ví dụ, với âm tiết sai trườgn, như đã phân tích ở trên, ta xét từng thành phần: - Phụ âm đầu: tr -> t, r, th Ta có các âm tiết mới: tườgn, rườgn, thườgn. Dễ dàng nhận thấy rằng thành phần bị đánh máy sai là thành phần phụ âm cuối, đo đó tất cả những âm tiết mới được tạo ra khi xét các thành phần khác đều không xuất hiện trong từ điển âm tiết. Do vậy trong ví dụ này ta sẽ bỏ qua việc xét các thành phần khác mà chỉ xét đến thành phần phụ âm cuối. Phụ âm cuối: gn -> n, ng. Để ý rằng các phụ âm như g, nh không được xét bởi: với nh, MED so với gn là 2 (2 thao tác 1 xóa và 1 chèn), còn với phụ âm g, chúng tôi có xét đến thuộc tính về khả năng đứng sau nguyên âm của phụ âm đó, và trong tiếng Việt, phụ âm g không bao giờ đóng vai trò của phụ âm cuối. Các phụ âm có thể đứng ở cuối âm tiết là: ng, ch, nh, c, t, m, n, p. Có 2 trường hợp đặc biệt của phụ âm đầu đó là 2 phụ âm qu và gi. Khi xét thành phần nguyên âm ta cần chú ý tới 2 phụ âm này, và chúng tôi cũng xét thuộc tính của nguyên âm về khả năng đứng sau 2 phụ âm trên. Bảng phụ lục 1 cho thấy khả năng kết hợp với 2 phụ âm trên của các nguyên âm. Có một điểm chú ý liên quan tới phụ âm gi đó là trong các âm tiết như gì, gìn thì nguyên âm là i và phụ âm đầu là g. Sau khi tạo ra tập nhầm lẫn âm tiết do đánh máy, chúng tôi tạo tập nhầm lẫn âm tiết do lỗi phát âm. Để tạo ra tập này, như đã nêu ở Chương 1, chúng tôi sử dụng bảng lỗi phát âm. Các lỗi phát âm được chúng tôi chia ra thành 4 loại: phụ âm đầu, nguyên âm, dấu thanh, và “phần đuôi”. Phần đuôi ở đây được hiểu là sự kết hợp của nguyên âm và phụ âm cuối. Việc tạo tập nhầm lẫn do phát âm cũng tương tự như tạo tập nhầm lẫn do đánh máy, đó là xét theo từng loại, mỗi loại sẽ tra trong bảng tương ứng. Tuy nhiên với 4 loại trên, chúng tôi không xét đến dấu thanh bởi ở trên chúng tôi đã xét toàn bộ các dấu thanh có thể. Kết hợp hai tập trên ta được tập nhầm lẫn cho âm tiết đang xét. 21 3.3.2. Sử dụng n-gram để đưa ra âm tiết gợi ý Ở công đoạn này, trong quá trình thực hiện, chúng tôi có thử nghiệm hai phương pháp khác nhau như đã nói ở trên. Tuy nhiên, do hiệu quả và tốc độ thực thi của thuật toán thứ nhất và thuật toán thứ hai chênh nhau khá nhiều, do đó trong chương trình thực tế và các kết quả kiểm thử, chúng tôi chỉ sử dụng giải thuật thứ hai. Với giải thuật thứ nhất, ta giả sử tất cả các âm tiết đều sai. Khi đó, ta cần xác định được ít nhất một âm tiết được cho là đúng làm cơ sở. Ở đây, chúng tôi dựa vào tập nhầm lẫn âm tiết của 3 âm tiết đầu tiên, tính xác suất tốt nhất trong tất cả các tổ hợp 3 âm tiết có thể từ 3 tập nhầm lẫn âm tiết của chúng. Công thức tính xác suất: P(s1s2s3) = P(s1).P(s2|s1).P(s3|s1s2) Từ 3 âm tiết đã được lựa chọn và được cho là đúng này, ta lần lượt tính xác suất cho từng âm tiết tiếp theo: s4, s5,… P(s2s3s4) = P(s1).P(s3|s2).P(s4|s2s3) … Giải thuật này có ưu điểm là cài đặt đơn giản và hoàn toàn áp dụng tư tưởng của mô hình n-gram. Tuy nhiên, giải thuật này có nhược điểm là tốc độ thực hiện chậm do phải tính xác suất của tất cả các tổ hợp của âm tiết đầu. Giả sử mỗi âm tiết có 15 candidates khác nhau, ta phải tính xác suất 153 = 3375 lần, chỉ riêng cho 3 âm tiết đầu. Hơn nữa, giải thuật này sử dụng ít thông tin ngữ cảnh nên độ chính xác không cao. Do vậy chúng tôi đã sử dụng một giải thuật khác, được đánh giá tốt hơn, chính là giải thuật thứ hai chúng tôi trình bày sau đây. Với giải thuật này, ta giả sử chỉ có một âm tiết sai, tất cả các âm tiết còn lại là đúng. Lúc này, ta cần xác định âm tiết nào có thể dùng để sửa lỗi tốt nhất. Để làm được điều này, với từng âm tiết, ta lần lượt giả sử âm tiết si đó là sai, sau đó tìm ra âm tiết sửa sai tốt nhất s’i trong tập nhầm lẫn cho âm tiết đó. Âm tiết si có xác suất là pi và s’i có xác suất p’i. Ta có tỷ lệ mức độ sửa lỗi đối với âm tiết si là . Lần lượt xét toàn bộ các âm tiết của câu ta sẽ tìm được âm tiết có Fi lớn nhất; âm tiết đó chính là âm tiết cần sửa. Sau khi thay thế âm tiết cần sửa bởi candidate tốt nhất của nó, ta lặp lại quá trình trên cho tới khi không tìm được âm tiết nào cần sửa. Để tính được các xác suất pi và p’i, chúng tôi sử dụng hàm tính xác suất: 22 P(s1s2s3) = P(s1).P(s2|s1).P(s3|s1s2) Khác với giải thuật thứ nhất, chúng tôi áp dụng hàm tính xác suất trên cho các bộ 3 âm tiết: si-2si-1si , si-1sisi+1 và sisi+1si+2 sau đó tính giá trị trung bình của chúng. Cụ thể: Dựa vào công thức trên, có thể thấy ta cần tính toán các xác suất dựa trên trigrams. Điều này dẫn đến một vấn đề với các âm tiết nằm ở vị trí cận biên của câu: với âm tiết đầu tiên, ta không tính được các xác suất , cũng như vậy với các âm tiết cuối. Có một cách khá đơn giản là khi ta không tính được một xác suất nào đó trong số 3 xác suất trên, ta loại bỏ nó. Ví dụ với âm tiết đầu tiên, ta tính xác suất: Và với âm tiết thứ 2, ta sử dụng xác suất: Có một vấn đề khác nữa khi kiểm tra các âm tiết là trường hợp có quá nhiều lỗi trong một câu. Khi đó, chương trình sẽ phải xét các âm tiết trong câu rất nhiều lần để tìm ra được tổ hợp tốt nhất, và việc này tốn khá nhiều năng lực của bộ xử lý khi tính toán các xác suất trigram. Để tránh vấn đề trên, trước mỗi lượt xét câu, chúng tôi tính trung bình xác suất của tất cả các âm tiết trong câu (các xác suất này được tính toán trong lượt xét câu trước đó nên không tốn thêm thời gian tính toán). Với giá trị trung bình xác suất nhỏ hơn ngưỡng chọn trước, chúng tôi sẽ tính toán sử dụng các xác suất bigram và unigram tương ứng với từng ngưỡng (ở đây chúng tôi tạm chọn 10-6 cho bigram và cho 10-9 unigram). Và khi đó, với mỗi vòng tính toán cho câu, chúng tôi lại xác định “mức” cho các tính toán xác suất tiếp theo của vòng đó. 3.4. Kết quả và thảo luận 3.4.1. Kết quả Để tiến hành kiểm thử, chúng tôi sử dụng dữ liệu đầu vào là một tệp văn bản chứa khoảng 1000 câu tiếng Việt với nội dung trong nhiều lĩnh vực khác nhau (thời sự, văn hóa, kinh tế, văn học…), và dữ liệu văn bản này là đúng chính tả. 23 Chương trình kiểm thử nạp dữ liệu các câu đúng vào, sau đó tách câu và tự động sinh lỗi ngẫu nhiên theo từng câu. Các câu sau khi được sinh lỗi tự động tiếp tục được lấy làm dữ liệu đầu vào cho chức năng kiểm lỗi chính tả mà chúng tôi đã cài đặt theo giải thuật ở trên, kết quả là 3 văn bản: văn bản gốc (đúng chính tả), văn bản sinh lỗi và văn bản sau khi kiểm lỗi. Các văn bản sinh lỗi và sau khi kiểm lỗi được chúng tôi đánh dấu để tiện cho việc theo dõi và đánh giá. Sau khi thực hiện một số lượng test nhất định, chúng tôi xin đưa ra bảng thống kê của một số kết quả đánh giá như dưới đây: STT Tổng số câu Số lỗi sinh ra Số lỗi sửa thành công Số lỗi sửa không đúng Số lỗi tối đa trong một câu 1 998 76 64 (84.21%) 128 (168.42%) 1 2 998 79 65 (82.28%) 86 (108.86%) 1 3 998 415 355 (85.54%) 607 (146.26%) 1 4 998 421 377 (89.55%) 546 (129.69%) 1 5 998 407 363 (89.19%) 556 (136.61%) 1 6 998 802 660 (82.29%) 648 (80.80%) 2 7 998 491 414 (84.32%) 269 (54.79%) 3 8 998 301 238 (79.07%) 207 (68.77%) 4 Ở đây, số lỗi sửa không đúng bao gồm lỗi sửa không thành công và lỗi do làm sai đi những âm tiết đúng. Vấn đề này là vấn đề tất yếu gặp phải khi sử dụng phương pháp kiểm lỗi có tính “mù”, do chỉ sử dụng thông tin ngữ cảnh bằng thống kê N-gram mà không sử dụng thêm loại tri thức ngôn ngữ nào khác. Qua bảng kết quả ở trên, ta có thể thấy kết quả sửa lỗi thành công là chưa cao, và tỷ lệ sửa lỗi không đúng lại rất lớn. Điều này thường xảy ra ở những câu dài, có số lỗi chính tả ít như: “Cụ thể, Trung tâm đề nghị các doanh nghiệp gửi đến Trung tâm danh sách chi tiết xe taxi đang hoạt động của từng doonh nghiệp trước ngày 25/5 để tiến hành chốt sổ” 24 Được sửa thành: “Cụ thể, Trung tâm đề nghị các doanh nghiệp gửi đến Trung tấm danh sách ghi tiết xem taxi đang hoạt động của từng doanh nghiệp trước ngày 25/5 để tiến hành chốt sổ” Tuy nhiên, lại có những trường hợp câu rất ngắn, lỗi sai trong câu rất nhiều nhưng chương trình vẫn có thể sửa lỗi đúng 100% như: “Ăn iu em nhìu lém! Em có iu ăn hông?” được sửa thành “Anh yêu em nhiều lắm! Em có yêu anh không?” Hay: “chún tôi cóa thể làm được đìu đóa” được sửa thành “chúng tôi có thể làm được điều đó” Để sửa được những lỗi như 2 ví dụ trên chúng tôi phải kết hợp sử dụng unigram mà không chỉ sử dụng trigram do thông tin ngữ cảnh quá nghèo nàn. 3.4.2. Thảo luận Từ những kết quả ở trên, ta có thể thấy rằng chỉ sử dụng thông tin ngữ cảnh bằng thống kê N-gram để kiểm lỗi chính tả là chưa hiệu quả. Tuy nhiên, các kết quả đó cũng cho thấy khả năng nâng cao kết quả sửa lỗi là rất lớn. Vì khi chỉ sử dụng N-gram, sự phụ thuộc của kết quả vào dữ liệu huấn luyện là rất lớn. Hơn nữa, ta có thể để ý rằng, khi số lỗi trong một câu tăng lên thì tỉ lệ lỗi mới sinh ra lại giảm xuống khá nhiều, trong khi tỉ lệ sửa lỗi đúng không thay đổi là mấy. Điều này cho thấy các lỗi mới sinh ra trong quá trình kiểm tra thường xảy ra với các tổ hợp âm tiết nhất định, tỉ lệ này thay đổi khi tổ hợp âm tiết đó bị thay đổi. Chứng tỏ, các lỗi đó là do sự phụ thuộc của công tác kiểm lỗi vào dữ liệu huấn luyện gây ra. Do vậy, ta có thể nghĩ tới một số hướng giải quyết vấn đề trên đó là sử dụng thêm các tri thức ngôn ngữ khác ngoài âm tiết. Đồng thời có thể sử dụng kết hợp mô hình N-gram với các phương khác để giảm bớt độ “mù” của chương trình nhằm nâng cao kết quả sửa lỗi và tốc độ xử lý. 25 Chương 4: Ứng dụng trên môi trường Web Chương này chúng tôi trình bày một số vấn đề về lập trình trên nền web cho luận văn này, một số ưu điểm, nhược điểm cũng như một vài phương pháp khắc phục các nhược điểm đó. 4.1. Môi trường lập trình web Như ta đã biết, ngày này, Internet không còn xa lạ với người dùng phổ thông, và song song với sự phát triển của Internet là các ứng dụng trên nền web (web applications) càng ngày càng phát triển cả về số lượng lẫn chất lượng. Các ứng dụng này có rất nhiều loại khác nhau, về nhiều lĩnh vực khác nhau và cũng được viết trên nhiều hệ ngôn ngữ lập trình khác nhau. Trong luận văn này, chúng tôi sử dụng các ngôn ngữ lập trình web với nội dung động là: HTML, Javascript, PHP, MySQL và có sử dụng thêm C++ cho một số công đoạn tối ưu hóa. Sau đây chúng ta sẽ cùng đi vào những vấn đề chi tiết hơn. 4.2. Ưu điểm và nhược điểm 4.2.1. Ưu điểm Ưu điểm đầu tiên của các ứng dụng chạy trên web đó là có thể sử dụng ở bất kỳ đâu có Internet và không phụ thuộc vào platform. Một ứng dụng web có thể sử dụng trên gần như tất cả các hệ máy bởi nó chỉ cần có một trình duyệt (browser) và có kết nối internet. Một ưu điểm khác nữa của các ứng dụng web khiến nó không phụ thuộc vào hệ máy bởi các xử lý phức tạp của ứng dụng được thực hiện tại server (server-side applications), do đó máy của người dùng đầu cuối (end-user) không cần có tài nguyên phần cứng quá lớn, thậm chí là rất nhỏ như các thiết bị di động: netbook, smartphone… Bên cạnh đó, các chức năng độc lập của chương trình có thể được sử dụng trong các chương trình khác như một module. Ví dụ như chức năng kiểm lỗi chính tả tiếng Việt này có thể được sử dụng trong việc kiểm tra lỗi chính tả khi soạn email. Một ưu điểm khác khi sử dụng hệ CSDL đó là có thể truy xuất dữ liệu từng phần mà không phải nạp toàn bộ dữ liệu vào trong bộ nhớ chính (RAM). 26 4.2.2. Nhược điểm Ưu điểm đầu tiên của ứng dụng web cũng chính là nhược điểm của nó, đó chính là internet. Một ứng dụng web tất nhiên không thể sử dụng khi không có internet. Cũng như vậy, khi ta sử dụng một phần mềm client, chương trình này cần gửi thông tin đầu vào đến server để xử lý và sau đó nhận lại kết quả trả về từ server. Quá trình này cần thông qua đường truyền internet. Một số nhược điểm khác chúng tôi đề cập đến sau đây là những nhược điểm cụ thể của chính chương trình trong luận văn này. Nhược điểm đầu tiên của việc sử dụng các ngôn ngữ lập trình web kể trên đó là: chúng là các ngôn ngữ dạng script, hay nói cách khác, chúng là các ngôn ngữ dạng thông dịch (translate). Và chúng ta cũng biết đặc điểm của các chương trình sử dụng ngôn ngữ thông dịch là có tốc độ thực thi thấp hơn so với các chương trình được biên dịch (compile). Bên cạnh đó, việc truy xuất dữ liệu giữa PHP và MySQL cần thông qua các truy vấn (query). Điều này đòi hỏi thêm một bước xử lý trung gian nữa khiến tốc độ của chương trình giảm đi một chút. Ngoài ra, các lệnh của 2 ngôn ngữ này (PHP và MySQL) được thực hiện chỉ với một tiến trình (process) và một luồng (thread) đối với một request được gửi đến server. Do vậy tốc độ xử lý sẽ chậm hơn so với việc chạy đa luồng. Để giải quyết một số vấn đề kể trên, chúng tôi có sử dụng một vài kỹ thuật nhằm tăng tốc độ thực thi của chương trình. 4.2.3. Một số kỹ thuật nhằm khắc phục nhược điểm Về vấn đề của ngôn ngữ thông dịch, chúng tôi đã thực hiện kỹ thuật cải thiện tốc độ của chương trình bằng cách viết lại các thành phần thường xuyên được gọi sang dạng biên dịch. Có nghĩa là, những thành phần được gọi thường xuyên, chúng tôi dịch ra mã máy và để chương trình gọi dưới dạng một hàm (function). Cụ thể: - Với MySQL, do đặc điểm của PHP khi truy vấn MySQL là chỉ gọi được các query dạng đơn (mỗi query chỉ chứa một lệnh), các cụm truy vấn thường xuyên được gọi liền nhau được chúng tôi viết gộp lại thành StoreProcedure trong MySQL database. Đặc điểm của StoreProcedure là nó được lưu trữ dưới dạng mã máy và có thể gọi dưới dạng một hàm thông qua truy vấn. Việc này giúp cho giảm bớt lượt truy 27 vấn giữa PHP và MySQL, đồng thời các truy vấn MySQL được thực thi nhanh hơn do đã được dịch ra dưới dạng mã máy. - Với PHP, chúng tôi cũng làm tương tự bởi ngôn ngữ PHP có một đặc điểm lợi thế là có thể viết các extensions dạng dll(Dynamic Linking Library) để mở rộng tùy ý. Extension được chúng tôi viết bằng ngôn ngữ C++, một ngôn ngữ đặc biệt tối ưu về mã lệnh thực thi. Vấn đề tiếp theo là vấn đề về xử lý đơn tiến trình. Chúng tôi thực hiện 2 kỹ thuật để giải quyết vấn đề này. Về xử lý đa tiến trình, chúng tôi lợi dụng đặc điểm: PHP và MySQL được chạy với 2 tiến trình riêng biệt trên server. Do đó, chúng tôi sử dụng StoreProcedure để kết hợp xử lý tính toán sử dụng đồng thời 2 tiến trình khác nhau đó. Cụ thể, chúng tôi sử dụng MySQL để truy vấn dữ liệu và tính toán các xác suất ngram, đồng thời sử dụng PHP để lựa chọn âm tiết theo giải thuật nêu trên dựa vào các giá trị xác suất trả về từ MySQL. Phương pháp này giúp tăng đáng kể tốc độ của chương trình: khi chưa kết hợp, nếu một request kiểm tra một câu trung bình mất 3-6 giây, thì sau khi kết hợp thời gian chỉ còn khoảng từ 0.8-1.2 giây. Một kỹ thuật nữa chúng tôi áp dụng để khiến CPU xử lý nhiều luồng đó là lợi dụng chính đặc điểm mỗi request được thực hiện với một thread, chúng tôi sử dụng XmlHttpRequest để chia công việc ra làm nhiều request khác nhau và gửi đến server cùng lúc. Sau khi toàn bộ các request được hoàn thành, chúng tôi tổng hợp lại kết quả cuối cùng. Chúng tôi áp dụng thủ thuật này cho việc kiểm tra chính tả của một đoạn văn. Đầu tiên, đoạn văn được phân tích thành các câu, sau đó mỗi câu sẽ được gửi đến server theo các request riêng biệt để xử lý. Kết quả được tổng hợp lại khi tất cả các câu đã được xử lý xong. Cách giải quyết này cũng mang lại hiệu quả nhất định: khi chỉ sử dụng một request, nếu một đoạn văn gồm 10 câu mất một khoảng thời gian là 1phút, thậm chí có khi đến 3 phút để kiểm tra (!) thì khi sử dụng 10 request riêng biệt, thời gian thực thi chỉ từ 15-20 giây. Chúng tôi cũng sử dụng kỹ thuật này cho quá trình huấn luyện, thời gian đã giảm từ 3 ngày (chưa xong) xuống chỉ còn khoảng 9-10 giờ là hoàn thành. Có sự chênh lệch lớn như vậy là do CPU không sử dụng hết năng lực của nó khi nó không bị ép buộc. Một kỹ thuật khác chúng tôi sử dụng để tăng tốc độ quá trình truy vấn dữ liệu cũng như huấn luyện là việc lợi dụng đặc tính của MySQL là tự động Index dữ liệu dựa vào Primary Key. Công việc tìm kiếm dữ liệu văn bản (full text search) trong MySQL tốn khá nhiều thời gian, do đó chúng tôi đã mã hóa dãy các âm tiết có thứ tự của thống kê n-gram thành mã MD5 và dùng mã này làm Primary Key. Mã hóa MD5 28 là mã hóa một chiều 128bit do đó có thể coi mã đó là duy nhất đối với một tổ hợp các âm tiết nhất định. Mẹo này khá đơn giản, nhưng hiệu quả mà nó đem lại rất lớn. Ta có thể thấy rõ điều này: trong quá trình huấn luyện, nếu sử dụng các truy vấn tìm kiếm thông thường, tốc độ nhập dữ liệu là 40-50 bản ghi/giây (!), so với tốc độ xấp xỉ 5000 bản ghi/giây khi sử dụng Primary Key dạng mã hóa. Mặc dù thông tin về các âm tiết và thứ tự của chúng đã có trong mã MD5, chúng tôi vẫn giữ lại các trường chứa âm tiết để lợi dụng chức năng nén dữ liệu của MySQL. Thực tế khi chúng tôi xóa bỏ 3 trường âm tiết của bảng thống kê trigram, kích thước tệp dữ liệu đã tăng từ hơn 700MB lên gần 1.5GB. Ngoài ra còn một số kỹ thuật nhỏ khác như tăng bộ đệm cho truy vấn, mã thực thi… cũng được chúng tôi áp dụng. Chúng tôi sẽ tiếp tục cải tiến trong quá trình phát triển luận văn và chương trình. 29 Kết luận Luận văn đã trình bày cách tiếp cận, và một phương pháp giải quyết bài toán kiểm lỗi chính tả tiếng Việt. Trọng tâm của luận văn là sử dụng mô hình ngôn ngữ N- gram để kiểm lỗi chính tả cảm ngữ cảnh 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ài toàn kiểm lỗi chính tả tiếng Việt, tận dụng được nguồn tài nguyên dồi dào trên internet để giải quyết bài toán nhằm giảm công sức con người. - Cài đặt chương trình ứng dụng trên internet Các vấn đề tồn tại: - Tỉ lệ sửa lỗi chính xác còn chưa cao do chỉ sử dụng duy nhất phương pháp thống kê N-gram vào việc kiểm lỗi. - Tốc độ chương trình còn chưa cao. Qua kết quả của luận văn cho thấy, mặc dù độ chính xác chưa cao nhưng nó cho ta thấy tầm quan trọng của việc sử dụng mô hình ngôn ngữ N-gram trong bài toàn kiểm lỗi chính tả nói chung và kiểm lỗi chính tả tiếng Việt nói riêng. Bên cạnh đó, tốc độ của chương trình tuy chưa cao nhưng khả năng tối ưu chương trình vẫn còn rất lớn. Chúng tôi tin tưởng rằng độ chính xác sẽ được nâng cao đáng kể khi kết hợp với các phương pháp học máy và ra quyết định khác. Đồng thời sử dụng các thuộc tính và các tri thức ngôn ngữ nâng cao hơn nữa. Như vậy, luận văn đã cho thấy khả năng ứng dụng rộng rãi của các chương trình thực thi trên nền web – internet, đặc biệt là với bài toán có tính ứng dụng thực tiễn cao như bài toán kiểm lỗi chính tả. Hướng nghiên cứu của chúng tôi là: - Sử dụng các tri thức ngôn ngữ nâng cao hơn như từ, ngữ pháp, ngữ nghĩa. - Tối ưu hóa tốc độ và bộ nhớ cho các quá trình kiểm lỗi. - Kết hợp các mô hình ngôn ngữ khác để kiểm lỗi chính tả như Maximum Entropy 30 Phụ lục Phụ lục 1: Bảng kết hợp nguyên âm với các phụ âm gi, qu Nguyên âm Không Gi Qu oai x oay x uây x uôi x iêu x uyê x ươu x ươi x uya x yêu x uyu x ai x x ao x au x ay x x âu x ây x x eo x x êu x ia x iu x iê x 31 oa x oă x oe x oi x oo x ôi x ơi x x ua x uâ x ui x uê x uô x uơ x uy x ưa x ưi x ươ x ưu x yê x a x x ă x x â x x e x x ê x x i x o x 32 ô x ơ x x u x ư x y x Phụ lục 2: Bảng một số lỗi phát âm tiếng Việt CH- TR- D- GI- R- D- GI- V- L- N- S- X- -C -T -N -NG -AI -AY -ANH -ĂN -EM -ÊM -ÊCH -ÊT -IÊM -IM -IÊU -IU -IÊU -ƯƠU -OAI -OI -OM -ÔM -ƠM Hỏi Nặng Ngã Sắc 33 Tài liệu tham khảo Tiếng Anh [1] Daniel Jurafsky & James H. Martin. Speech and language processing: An introduction to speech recognition, computational linguistics and natural language processing. 2007. [2] Department of Computer Science, Columbia University, 2009, N-Grams and Corpus Linguistics, Lecture. [3] Georgetown University, Introduction to Natural Language Processing, Autumn 2005, Course’s Lecture. [4] Julia Hockenmaier, Introduction to NLP, Fall 2008, Lecture 3: Probability theory, N-grams and perplexity. Tiếng Việt [5] Cao Văn Việt, Xây dựng mô hình ngôn ngữ cho tiếng Việt, 2010, Luận văn tốt nghiệp, Hà Nội. [6] Đoàn Xuân Kiên, Xem lại một vấn đề ngữ âm tiếng Việt: Cấu trúc âm tiết, 1998, Tập san Hợp Lưu 48. [7] Đinh Thị Phương Thu, Huỳnh Quyết Thắng, Nguyễn Văn Lợi. Sử dụng 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, 10/2007, tạp chí BCVT & CNTT kỳ 3. [8] Hoàng Phê, Chính tả tiếng Việt, 1999, Nhà xuất bản Đà Nẵng. [9] Hoàng Phê (chủ biên), Từ điển tiếng Việt, 2002, Nhà xuất bản Đà Nẵng. [10] Ngonngu.net, Âm tiết và đặc điểm âm tiết tiếng Việt, 2006, [11] Nguyễn Phương Thái, Kiểm lỗi chính tả cảm ngữ cảnh tiếng Việt, 2003, Luận văn thạc sĩ, Hà Nội. [12] Nguyễn Gia Định, Trần Thanh Lương, Thuật toán kiểm tra âm tiết tiếng việt dựa trên luật cấu tạo âm tiết, 2004, Trường Đại học Khoa học - Đại học Huế, Tạp chí khoa học – Đại học Huế, Số 25. 34 [13] Trung Tâm Từ Điển Học - Vietnam Lexicography Centre, Quy tắc đặt dấu thanh trong tiếng Việt, [14] Ủy ban khoa học xã hội Việt Nam, Ngữ pháp tiếng Việt, Nhà xuất bản Khoa học Xã hội – Hà Nội, 1983.