Tài liệu Cách tiếp cận dựa trên ngữ liệu cho kiểm lỗi chính tả tiếng việt

TR NG I H C KHOA H C T NHIÊN KHOA CÔNG NGH THÔNG TIN MÔN CÔNG NGH TRI TH C Châu H i Duy - 0112005 CÁCH TI P C N D A TRÊN NG LI U CHO KI M L I CHÍNH T TI NG VI T KHÓA LU N C NHÂN TIN H C GIÁO VIÊN H TS. inh NG D N n NIÊN KHÓA 2001 – 2005 ic m n Ñ&Ò u tiên em xin t lòng bi t n sâu s c tình giúp , tr c ti p h ng d n và truy n có th th c hi n và hoàn thành n th y inh n, ng i ãt n t nhi u kinh nghi m quý báu em tài này. Em xin chân thành c m n các th y cô thu c khoa Công ngh Thông tin, tr ng i h c Khoa h c T nhiên. Các th y cô ã t n tình d y d , truy n em nhi u ki n th c quý báu trong su t nh ng n m ih c t cho em có c ngày n ông bà, cha m , nh ng ng i ã sinh n các b n trong nhóm VCL, c bi t là hôm nay. Con xin g i l i c m n sâu s c thành và nuôi d ng con thành ng i. Sau cùng tôi xin g i l i c m n n V Th y – ng trình có th ho t i ã t ng h p và cung c p ng li u hu n luy n ch ng ng. TP. H Chí Minh, tháng 7 n m 2005 Châu H i Duy – 0112005 Nh n xét c a Giáo viên ph n bi n ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... ..................................................................................................................... Ch ký c a GVPB cl c u ..................................................................................................... 1 Ch ng 1. 1.1. ng quan ........................................................................... 3 Ki m l i chính t c a ti ng n 1.1.1. Ki m l i chính t cho các ngôn ng châu Âu................................... 4 1.1.1.1. Ph ng pháp T ng c nh........................................................ 4 1.1.1.2. Ph ng pháp 1.1.1.3. Ph ng pháp Danh sách quy t 1.1.2. c tr ng lân c n................................................ 4 nh.......................................... 5 Ki m l i chính t cho các ngôn ng châu Á..................................... 6 1.1.2.1. Mô hình CInsunSpell cho ti ng Hoa......................................... 6 1.1.2.2. Ph 1.1.3. 1.2. c ngoài........................................... 4 ng pháp c a Nagata cho ti ng Nh t .................................. 7 ánh giá chung v các mô hình trên ................................................ 9 Ki m l i chính t ti ng Vi t...........................................................10 1.2.1. Ch 1.2.2. Ki m l i chính t d a vào phân tích cú pháp ................................. 11 1.2.3. Ki m l i chính t b ng mô hình l 1.2.4. Word 2003 phiên b n ti ng Vi t .................................................... 13 Ch ng 2. ng trình VietSpell.................................................................. 10 i t ......................................... 12 s lý thuy t ...................................................................14 2.1. Chu n chính t ...............................................................................15 2.2. t s ki n th c c b n v chính t ti ng Vi t ..............................15 2.2.1. Các y u t c a ti ng và ch vi t: ................................................... 15 2.2.1.1. Âm ......................................................................................... 16 2.2.1.2. Ch cái................................................................................... 17 2.2.1.3. Thanh và d u.......................................................................... 17 2.2.1.4. Ti ng hay âm ti t.................................................................... 17 2.2.1.5. Hình v ................................................................................... 17 2.2.1.6. .......................................................................................... 18 2.2.2. Quy cách ghi d u thanh trên ch vi t............................................. 19 2.2.3. t qu u tra l i chính t ........................................................... 19 2.2.3.1. thanh 2.2.3.2. âm 2.2.3.3. âm chính ........................................................................... 20 2.2.3.4. âm cu i ............................................................................. 20 2.2.4. u ......................................................................... 19 u .............................................................................. 20 Nguyên nhân ................................................................................. 20 2.2.4.1. thanh 2.2.4.2. âm 2.2.4.3. âm chính ........................................................................... 21 2.2.4.4. âm cu i ............................................................................. 21 2.3. c u ......................................................................... 20 u .............................................................................. 21 m chung c a m t h ki m l i chính t ...............................22 2.3.1. Các ch c n ng chính ..................................................................... 22 2.3.2. Các lo i l i chính t ....................................................................... 22 2.3.3. Nguyên nhân gây ra l i chính t .................................................... 23 2.3.4. Các sai l m c a trình ki m l i........................................................ 24 2.4. s tin h c .................................................................................25 2.4.1. Lu t Bayes .................................................................................... 25 2.4.2. Mô hình N-Gram t ng quát ........................................................... 26 2.4.2.1. ng b ng N-Gram........................................................ 26 2.4.2.2. Hu n luy n N-Gram ............................................................... 28 2.4.2.3. Làm m n................................................................................. 29 2.4.3. Ch cl Tách t .......................................................................................... 30 2.4.3.1. Kh p t i a ............................................................................ 31 2.4.3.2. WFST..................................................................................... 32 ng 3. Mô hình ..............................................................................33 3.1. Mô hình t ng quát .........................................................................34 3.2. Ti n x lý ......................................................................................37 3.2.1. Tách c m ti ng .............................................................................. 37 3.2.2. Tách ti ng...................................................................................... 37 3.2.3. c “nhi u” ................................................................................... 38 3.3. 3.2.3.1. Nh n di n ti ng Anh .............................................................. 38 3.2.3.2. Nh n di n t vi t t t ............................................................... 38 3.2.3.3. Nh n di n phiên âm................................................................ 38 Ki m l i non-word ........................................................................39 3.3.1. Phát hi n l i .................................................................................. 39 3.3.2. a l i ........................................................................................... 39 3.4. 3.3.2.1. a l i phát âm ...................................................................... 39 3.3.2.2. a l i nh p li u..................................................................... 40 3.3.2.3. Các l i khác ........................................................................... 43 Ki m l i real-word ........................................................................43 3.4.1. Phát hi n l i b ng bigram .............................................................. 44 3.4.1.1. Ýt ng chính ........................................................................ 44 3.4.1.2. t h p v i trigram ................................................................ 45 3.4.1.3. Làm m n................................................................................. 47 3.4.1.4. Heuristic h n ch l i tích c c ................................................. 47 3.4.2. Phát hi n l i b ng FMM và n-gram ............................................... 48 3.5. p danh sách ng viên s a l i......................................................50 3.6. c trong quá trình ki m l i..........................................................51 Ch ng 4. 4.1. Cài Cài 4.1.1. t th c nghi m ..........................................................52 t ...........................................................................................53 Chu n hoá ti ng............................................................................. 53 4.1.1.1. Mã hoá các ch cái................................................................. 53 4.1.1.2. Mã hoá ti ng .......................................................................... 53 4.1.1.3. u trúc l p Tieng.................................................................. 55 4.1.2. Mã hoá t và n-gram ..................................................................... 57 4.1.2.1. Mã hoá t ............................................................................... 57 4.1.2.2. Mã hoá n-gram ....................................................................... 58 4.1.2.3. u trúc l p Tu ...................................................................... 59 4.1.3. 4.1.4. u trúc d li u cho các t n và các b n-gram......................... 59 Phát sinh ng viên ......................................................................... 60 4.1.4.1. Phát sinh các ti ng g n gi ng ................................................. 60 4.1.4.2. Phát sinh các t g n gi ng ...................................................... 61 4.1.5. Ki m l i chính t ........................................................................... 64 4.1.5.1. Dò tìm l i ............................................................................... 64 4.1.5.2. p x p các ng viên s a l i .................................................. 66 4.1.5.3. c trong quá trình ki m l i................................................... 66 4.1.6. Hu n luy n .................................................................................... 66 4.1.7. Tích h p vào Word........................................................................ 69 4.1.8. Các x lý khác............................................................................... 70 4.1.8.1. ng mã ti ng Vi t................................................................. 70 4.1.8.2. Linh tinh................................................................................. 70 4.1.9. 4.2. Vài hình nh v Ch ng trình........................................................ 71 Th nghi m và ánh giá ...............................................................73 4.2.1. Các tham s th nghi m ................................................................ 73 4.2.2. t qu .......................................................................................... 74 4.2.3. Nh n xét........................................................................................ 79 4.2.4. So sánh v i VietSpell .................................................................... 80 4.2.4.1. Kh n ng phát hi n l i............................................................ 80 4.2.4.2. Kh n ng ngh s a l i ........................................................ 80 4.3. ánh giá và K t lu n .....................................................................88 4.4. ng phát tri n............................................................................89 Tài li u tham kh o ...................................................................................90 Ph l c ....................................................................................................92 Danh sách hình Hình 1: Dò tìm l i b ng ma tr n ti ng nh m l n.................................................... 8 Hình 2: Mô hình t ng quát .................................................................................. 36 Hình 3: Bigram c m r ng v phía sau .......................................................... 47 Hình 4: Mã ti ng................................................................................................. 54 Hình 5: Mã t ..................................................................................................... 57 Hình 6: Mã n-gram ............................................................................................. 58 Hình 7: S ki m l i b ng FMM và n-gram..................................................... 65 Hình 8: Quá trình ki m l i .................................................................................. 71 Hình 9: Quá trình ki m l i hoàn t t ..................................................................... 72 Hình 10: K t qu th nghi m v i P_bi' = 5.33 .................................................... 75 Hình 11: K t qu th nghi m v i P_bi' = 4.95 .................................................... 76 Hình 12: K t qu th nghi m v i P_bi' = 4.73 .................................................... 77 Hình 13: K t qu th nghi m v i P_bi' = 4.59 .................................................... 78 Danh sách b ng ng 1: Các thành ph n d nh m l n khi phát âm ............................................... 39 ng 2: Phím g c và các phím lân c n................................................................ 42 ng 3: K t qu th nghi m................................................................................ 74 Danh sách thu t toán Thu t toán 1: Phát sinh ti ng ng viên d a vào l i phát âm................................. 40 Thu t toán 2: Phát hi n l i b ng bigram.............................................................. 45 Thu t toán 3: K t h p bigram và trigram phát hi n l i ................................... 46 Thu t toán 4: Phát hi n l i b ng FMM và n-gram ............................................... 49 Thu t toán 5: Phát sinh t ng viên..................................................................... 62 Thu t toán 6: Binary Search c i ti n.................................................................... 63 Thu t toán 7: Quá trình hu n luy n ..................................................................... 67 Thu t toán 8: Các b c t o n-gram trong giai n hu n luy n........................... 68 Cách ti p c n d a trên ng li u cho ki m l i chính t ti ng Vi t u tv n Là m t ch vi t ghi âm, ch vi t ti ng Vi t c ng có r t nhi u quy cách k t h p t ng ký t c a b ng ch cái v i nhau nh v t o thành nh ng t có ngh a, i là chính t . Vi c dùng úng chính t r t quan tr ng, nh t là trong các v n b n hành chính. M t v n b n sai chính t có th gây khó ch u cho ng ng i c không tin t ng vào trình c a chính ng Tr c, làm i ã t o ra v n b n ó. Nh ng quan tr ng h n h t, vi c sai chính t có th làm ng i dung c n truy n i i ti p nh n hi u sai t. c ây, vi c ki m l i chính t ph i hoàn toàn d a vào s c ng nhiên, xã h i càng phát tri n, l ng thông tin c n truy n i. Tuy t ngày càng nhi u, vi c ki m l i chính t “th công” r t m t th i gian và công s c. n ây, cùng v i s phát tri n nhanh chóng c a công ngh thông tin, ng l c i hành chánh t ra: làm sao n t ngày càng c m r ng và m t nhu c u m i ang máy tính có th thay th (m t ph n hay toàn b ) cho con ng i trong vi c ki m l i chính t , hay nói cách khác là làm sao ch ng trình b t l i chính t t xây d ng m t ng. Ngoài ra, hi n nay trong nhi u v n b n khoa h c c a ti ng Vi t th dùng thêm ti ng Anh ng có chú thích cho các thu t ng ho c cho các t không th ch sát ngh a. Do ó, m t ch ng trình ki m l i chính t t ng cho các v n b n có c ti ng Vi t và ti ng Anh là r t c n thi t. Thêm vào ó, vi c ki m l i chính t còn có th c dùng trong giai n ti n x lý c a r t nhi u bài toán khác v x lý ngôn ng t nhiên, ví d nh : phân lo i v n b n, tóm t t v n b n, d ch t ng, nh n d ng ch vi t, nh n d ng gi ng nói, … Tuy nhiên, trong khi bài toán ki m l i chính t cho các ngôn ng châu Âu ã c gi i quy t m t cách khá tr n v n, vi c ki m l i chính t cho ti ng Vi t l i -1- Cách ti p c n d a trên ng li u cho ki m l i chính t ti ng Vi t p nhi u khó kh n. Vì v y, cho n nay, m c dù ã có vài công trình v này nh ng h u nh ch a có công trình nào c tiêu c a Nh c áp d ng vào th c t . tài ã nói trên, m t ch ng trình ki m l i chính t t trong hoàn c nh hi n nay. Tuy ã có m t s công trình v ch a áp d ng tài c vào th c t . T nh ng ng là r t c n thi t tài này nh ng h u h t u ki n trên, tôi ã ch n ki m l i chính t làm lu n v n t t nghi p c a mình. c tiêu sau cùng c a hoàn ch nh, có th tài này là m t ch ng trình ki m l i chính t c s d ng ngay trong th c t . ngoài hi u qu th c t , các mô hình ngôn ng t c áp d ng c yêu c u này, ây không nên quá u k , ph c t p ho c òi h i nhi u không gian nh . Tù nh ng yêu c u trên, tôi ch n n-gram ti ng làm h Mô hình n-gram có m t s u m, ó là không quá ph c t p trong x lý, và n u c t ch c c u trúc d li u t t, l Trong mô hình c a ng ti p c n chính. ng b nh chi m d ng là ch p nh n tài này, n-gram c dùng làm ph ng ti n c. tính toán các xác su t, các m i liên k t gi a nh ng ti ng trong v n b n, dò tìm ra nh ng vùng b i, và sau cùng a ra các ngh s a ch a cho ng i dùng l a ch n. c c lu n v n Lu n v n này g m 4 ch • Ch ng v i n i dung chính nh sau: ng 1: Trình bày tình hình phát tri n c a ki m l i chính t trên th gi i, ánh giá m t s ph • Ch ng 2: Các v n ng pháp ã lý thuy t c công b . c dùng n trong lu n v n, g m lý thuy t ngôn ng h c và tin h c. • Ch ng 3: Mô hình và ph • Ch ng 4: Tóm t t quá trình cài giá v lu n v n cùng h ng pháp c s d ng trong lu n v n. t, cùng v i các th nghi m và ánh ng phát tri n sau này. Ngoài ra còn có ph n tài li u tham kh o và ph l c. -2- Cách ti p c n d a trên ng li u cho ki m l i chính t ti ng Vi t Ch ng 1. ng quan nh ng n m 60 c a th k XX, bài toán ki m l i chính t máy tính ã nh n c s quan tâm c a các nhà khoa h c. Cho thu t toán, mô hình chúng gi i quy t bài toán này ã ng b ng n nay, r t nhi u c công b , tuy nhiên h u h t u t p trung vào các ngôn ng bi n cách c a châu Âu nh ti ng Anh, ti ng Pháp,… còn ki m l i chính t cho các ngôn ng Hoa, ti ng Vi t,… ch m i b t Hi n nay, v n ang u c nghiên c u g n ây. c quan tâm nh t trong ki m l i chính t là ki m i chính t c m ng c nh. Khác v i các ph th ng, v n xem xét các t m t cách tr t t t ,… Do ó, ph n các ng pháp ki m l i chính t truy n c l p nhau và ch y u d a vào t trong ki m l i chính t c m ng c nh, không, h th ng ph i xét n l p c a châu Á nh ti ng quy t n, nh m t t có b sai chính t hay c tr ng xung quanh nó nh t lân c n, t lo i, ng pháp ki m l i c m ng c nh có th phát hi n c nh ng l i sai v cách dùng t , t c là t v n không b sai chính t , nh ng trong hoàn c nh c a câu v n thì vi c dùng nó là không h p lý. Tuy nhiên, i cùng v i hi u qu cao là s khó kh n trong cách ti p c n. a vào lo i hình ngôn ng (bi n cách hay ki m l i chính t có th c chia thành hai “tr n l p), các ph ng pháp ng phái” chính: ki m l i cho các ngôn ng châu Âu và ki m l i cho các ngôn ng châu Á. Ph n chính t ã u c a ch ng này xin gi i thi u m t vài ph ng pháp ki m l i c công b và ng d ng thành công trong th c t cho các ngôn ng c ngoài. Ph n cu i ch ng s m qua các công trình ã ki m l i ti ng Vi t, cùng v i m t s nh n xét v chúng. -3- c công b cho Cách ti p c n d a trên ng li u cho ki m l i chính t ti ng Vi t 1.1. Ki m l i chính t c a ti ng n c ngoài 1.1.1. Ki m l i chính t cho các ngôn ng châu Âu Nh ã nói trên, bài toán ki m l i chính t cho các ngôn ng châu Âu, nh t là ti ng Anh, ã nhau nh T nhiên, ph c tìm hi u t r t s m, v i nhi u mô hình, ph ng pháp khác ng c nh [GS96] , Lai Bayes [Gol95], Winnow [GR99],… Tuy ng pháp ki m l i chính t c m ng c nh nh n c quan tâm nh t do nó có nhi u u c nhi u nhà khoa m so v i cách ki m l i ch d a vào t n. 1.1.1.1. Ph ng pháp T ng c nh1 t trong nh ng um i phân bi t m t t v i nh ng t nh p nh ng v i nó là các t xung quanh nó trong câu. Ví d , khi ang xem xét ch n l a gi a dessert và desert, n u có các t nh arid, sand, sun,… g n ó, ta s ch n desert, còn n u g p các t nh chocolate, delicious,… g n ó, ta s ch n dessert. Ph ng pháp T ng c nh c Golding xây d ng d a trên nh n xét này. Trong giai n c, v i m i t th ng b vi t sai chính t , h th ng s ghi nh nh ng t th ng xu t hi n xung quanh nó trong ng li u. Khi ch y th c t , v i m i t nghi ng , h th ng s xem xét các t lân c n v i nó, sau ó ch n ra t thích h p nh t làm t thay th . 1.1.1.2. Ph Ph ng pháp c tr ng lân c n2 ng pháp T ng c nh r t t t trong vi c phát hi n các nguyên t c chung nh t ph thu c vào nh ng t lân c n, nh ng không quan tâm chúng. Trong tr p 1 2 ng h p ó, các ph ng pháp rút ra các quy lu t v tr t t . Context words Collocations -4- n tr t t c a c tr ng lân c n t ra r t thích Cách ti p c n d a trên ng li u cho ki m l i chính t ti ng Vi t t c tr ng lân c n là m t m u các y u t v cú pháp xung quanh t ang xét. Có hai c tr ng th ng c s d ng trong ph ng pháp này, ó là nhãn t lo i và t lân c n. Ph ph ng pháp c tr ng lân c n ng pháp T ng c nh. Ý t c th c hi n theo cách th c t ng chính nh m l n v i nhau d a vào các ây là phân bi t nh ng t d b dùng c tr ng lân c n c a chúng. M i n cung c p vài d u hi u v i kh n ng quy t p nh m l n. Nh ng d u hi u này lu t quy t nh (th ng t v i c tr ng lân nh3 khác nhau cho nh ng t trong c k t h p v i nhau và tính toán theo m t ng là Bayes). Sau cùng, t nào có h p lý cao nh t s c ch n. Tuy nhiên, ph t t có các ph ng pháp c tr ng lân c n c ng có nh c m, ó là khi c tr ng mâu thu n ho c hàm ch a nhau, g i là xung ng pháp này ho t ng t t, các c tr ng xung t v i nhau c n hi n và lo i b . Hi n nay, ngoài heuristic, v n ch a có m t ph ch nh gi i quy t v n Danh sách quy t ng pháp Danh sách quy t ng pháp hoàn nh nh là s k t h p c a T ng c nh và m c a c hai ph nguyên t c t t nh t theo cách dùng c tr ng lân c n ng pháp này: T ng c nh s rút ra các c l p v i tr t t t , còn c tr ng lân c n tr ng - ng pháp này òi h i ph i xây d ng m t danh sách r t l n các ây là các t ng c nh và các p x p theo kh n ng quy t c tr ng ph n ánh c tr ng lân c n. Nh ng nh gi m d n, trong ó kh n ng quy t tin c y c a nó trong vi c ra quy t ng c nh. c tr ng phù h p u tiên s c dùng Strength Conflict -5- c tr ng c c nh c a m i nh. M t t nh p nh ng c phân lo i b ng cách duy t qua danh sách và so kh p t ng 4 c rút ra các nguyên t c ph thu c vào tr t t . Ph 3 c phát này. 1.1.1.3. Ph t n d ng u t4. phân lo i t c tr ng v i ang xét. Cách ti p c n d a trên ng li u cho ki m l i chính t ti ng Vi t Vì Danh sách quy t nh a ra l i gi i ch d a vào m t c tr ng m nh nh t, hi u su t c a nó ph n l n tùy thu c vào cách xác nh kh n ng quy t cho nh ng ng pháp này, b i vì vi c c tr ng. ây chính là nh c m c a ph nh tìm ra m t công th c ánh giá t ng quát là r t khó. Do ó, Danh sách quy t tr ng h n. Theo ó, danh sách nh có th c c i ti n b ng cách dùng nhi u c l a ch n các t t t nh t, h th ng s duy t qua toàn b c tr ng, so sánh t ng c tr ng v i ng c nh, r i k t h p chúng a ra l i gi i sau cùng. Vi c k t h p các c tr ng có th c th c hi n nh vào t b phân lo i, ví d nh nh Bayes. 1.1.2. Ki m l i chính t cho các ngôn ng châu Á n ây, ki m l i chính t cho các ngôn ng châu Á ã t c quan tâm và c m t s thành t u. Không nh các ngôn ng châu Âu, vi c ki m l i chính cho các ngôn ng n l p c a châu Á g p nhi u khó kh n. Nguyên nhân ch u là do các ngôn ng c a châu Á nh ti ng Hoa, ti ng Nh t, ti ng Hàn,… không có ranh gi i t rõ ràng. áp d ng nh ng mô hình ki m l i chính t c m ng nh c a các ngôn ng châu Âu, v n b n ti ng châu Á c n . Vi c xác không nh ranh gi i t ngay khi v n b n n gi n. V i v n b n c xác nh ranh gi i u vào là úng chính t ã là u vào sai chính t , bài toán tách t càng khó kh n n. Do ó, các nhà ngôn ng h c – tin h c c a châu Á ã i cho ki m l i chính t . Ph n này s ra m t s mô hình m qua m t vài mô hình trong s ó. 1.1.2.1. Mô hình CInsunSpell cho ti ng Hoa Mô hình ki m l i này có tên là CInsunSpell [JX00] c Jianhua và Wang Xiaolong, là s k t h p gi a Trigram ti ng, ph ng Bayes và Phân ph i tr ng s t ng5, Hoa. 5 Automatic Weight Distribution -6- xu t b i Li ng pháp c c dùng cho s a l i chính t ti ng Cách ti p c n d a trên ng li u cho ki m l i chính t ti ng Vi t Trigram kích th c5 c dùng trong b c dùng c ki m l i. Theo ó, m t “c a s ” trigram ánh giá m i liên k t gi a các ti ng v i nhau. C a s trigram th c ra là m t chu i con, v i ti ng c n xét xung quanh (2 ti ng li n tr sai chính t khi hai liên k t tr c và 2 ti ng li n sau). Ti ng trung tâm c và sau nó có có giá tr nh h n m t giá tr ng u y u. Liên k t c xem là c xem là y u khi ng. u h t các mô hình dùng n-gram th a th t, d n trung tâm, và 4 ti ng lân c n u g p tr ng i chính, ó là d li u quá n các xác su t n-gram s r t th p (th ng có giá tr b ng 0). kh c ph c, các tác gi c a CInsunSpell dùng thêm bigram cùng v i làm m n b ng cách m r ng c a s bigram t 3 ti ng thành 4 ti ng v phía sau nâng cao hi u su t phát hi n l i. phân lo i Bayes c dùng trong b c s a l i. Ý t chu i thích h p nh t (có xác su t cao nh t) t chu i i. u vào ánh giá s phù h p c a chu i s a l i, Bayes pháp Phân ph i tr ng s t bi n chu i ng d a trên S phép bi n ng chính là tìm làm ph ng án s a c k t h p v i ph ng i ít nh t6 [WF74] u vào thành chu i s a l i. Theo th nghi m c a các tác gi , CInsunSpell có t l phát hi n l i là kho ng 60%, t l l i tích c c kho ng 10%. Hai giá tr này thay ng ng c dùng trong h th ng. 1.1.2.2. Ph Ph ng pháp c a Nagata cho ti ng Nh t ng pháp c a Nagata [Na98] c áp d ng nh n d ng ch vi t (OCR). Tuy nhiên nó v n có th chính t do con ng Ph nh p vào ng pháp c a Masaaki g m hai giai c dùng n: Trong giai c chia thành nhi u chu i ti ng, v i n. Trong giai u tiên cho các h th ng s a các l i i gây ra. thành m t t có trong t 6 i tùy vào các n ho c n th nh t, câu u ki n m i chu i ti ng t o n gi ng v i ít nh t m t t nào ó trong t n th hai, b ng các ph Minimun edit distance -7- ng pháp th ng kê, n chu i t t t nh t Cách ti p c n d a trên ng li u cho ki m l i chính t ti ng Vi t c t o thành t nh ng “t ” ã có a l i. D giai n tr c) c ch n làm ng viên i ây là ví d minh h a cho cách ti p c n này: Câu u vào: Tôi lam vi c h p tát x h p tác s t t xã mua bán Ma tr n ti ng nh m l n: lám làm báng lãm l m Tôi lam vi c p tát mua p tác mua p t lãm p tác m p tác lám làm vi c bán xã xã Hình 1: Dò tìm l i b ng ma tr n ti ng nh m l n có th chia chu i th ng dùng hai ph u vào thành các chu i con m t cách h p lý, h ng pháp, ó là Mô hình ngôn ng th ng kê và Thu t toán Forward-DB Backward A* tách t . Ngôn ng th ng kê c dùng tính xác su t k t h p c a chu i con và chu i nhãn t lo i. Xác su t k t h p này th c ra là tích xác su t xu t hi n c a chu i con v i xác su t xu t hi n chu i nhãn trong ng li u hu n luy n. Sau cùng Thu t toán Forward-DB Backward A* [Na94] -8- c dùng ánh giá các xác su t báng Cách ti p c n d a trên ng li u cho ki m l i chính t ti ng Vi t t h p ó, sau cùng tìm ra cách k t h p có xác su t l n nh t làm l i gi i cho bài toán tách t . Theo ánh giá c a tác gi , ph ng pháp này giúp c i thi n chính xác c a OCR t 90% lên 96%, hi u su t tách t là 93%. 1.1.3. ánh giá chung v các mô hình trên Các ph ng pháp T ng c nh, c tr ng lân c n và Danh sách quy t ã nh c ng d ng r t thành công cho các ngôn ng châu Âu nh ti ng Anh, ti ng Pháp, ti ng Tây Ban Nha,… Tuy nhiên nb n u vào c n ph i áp d ng các mô hình ó cho ti ng Vi t, c tách t b ng m t mô hình tách t m . Mô hình tách t m không t t s làm gi m áng k hi u su t chung c a toàn h th ng. Cho n nay v n ch a có m t mô hình tách t m hoàn ch nh cho ti ng Vi t. Ngoài ra, u h t các ph lo i, trong khi ng pháp cho ti ng Anh u òi h i ng li u ã c gán nhãn t n nay v n ch a có kho ng li u ti ng Vi t tho mãn yêu c u này. Thêm vào ó, các ph ng pháp nh Danh sách quy t nh và Bayes òi h i h th ng ph i th c hi n nhi u thao tác x lý khá ph c t p nh n ra t sai chính t nên c ng khó c áp d ng vào th c t . Do ó chúng tôi ch xem nh ng mô hình a Golding nh là ngu n tài li u tham kh o thêm mà không áp d ng chúng. i h th ng CInSunSpell cho ki m l i ti ng Hoa, các tác gi Bigram và Trigram m c ti ng ã dùng c a dò tìm ti ng sai chính t . ó là cách ti p c n t phù h p cho ti ng Vi t vì không c n ph i tách t . Bên c nh ó, mô hình này còn có nh ng u m khác. nh trong quá trình x lý. u u m u tiên là tính m th hai, c ng là CInsunSpell không òi h i kho ng li u hu n luy n ã n gi n trong cài c t c ng m quan tr ng nh t, c tách t hay gán nhãn lo i mà ch c n m t kho ng li u úng chính t . V i nh ng c m ó, vi c áp d ng CInsunSpell cho ti ng Vi t có nhi u kh n ng s thành công trong th c t . Mô hình s a l i chính t c a Masaaki cho ti ng Nh t, v m t lý thuy t c ng có th áp d ng ngay cho ti ng Vi t mà không c n s a là các ngôn ng i nhi u vì Nh t-Vi t u n l p. Tuy nhiên, c ng nh m t s mô hình dùng cho ti ng -9- Cách ti p c n d a trên ng li u cho ki m l i chính t ti ng Vi t Anh, mô hình này c n có kho ng li u ã u ch a th áp ng c tách t và gán nhãn t lo i, ó là c. Bên c nh ó, vi c dò tìm ph ng án s a l i b ng ma tr n ti ng nh m l n, khi áp d ng vào ti ng Vi t, s ph i ng u v i m t th thách m i: bùng n t h p, nh t là trong th c t , các l i sai khi nh p li u r t a ng nên t p nh m l n khá l n. Do ó, vi c áp d ng mô hình c a Maasaki cho ti ng Vi t ngay lúc này là r t khó kh n. 1.2. Ki m l i chính t ti ng Vi t Ki m l i chính t là m t bài toán khó, nh t là ki m l i chính t cho các ngôn ng n l p nh ti ng Vi t, ti ng Hoa. Tr c khi tôi th c hi n tài này, nh ng ng i i tr c ã công b m t s công trình nghiên c u v ki m l i chính t ti ng Vi t v i các h nhau. M i cách ti p c n có các VietSpell, h u h t chúng này s u ch a u-khuy t ng ti p c n khác m khác nhau. Tuy nhiên, ngoài c áp d ng thành công trong th c t . Ph n m qua các công trình ó, cùng v i m t vài nh n xét v chúng. Ngoài ra, trong n m nay c ng có m t s ki n áng chú ý: Microsoft phát hành trình x lý n b n MS Word 2003 giao di n ti ng Vi t có kèm ch c n ng ki m l i chính t ti ng Vi t. 1.2.1. Ch ng trình VietSpell VietSpell c a L u Hà Xuyên là ch i hoá và ng trình ki m l i chính t c s d ng r ng rãi hi n nay. Ch ã th ng ng trình này có nhi u u m nh g n nh , x lý nhanh, tích h p t t. Nh ng nh n xét, ánh giá v ch này ng trình c rút ra t VietSpell Pro phiên b n 3.0. Nhìn chung, VietSpell là m t ch ng trình t t, b i vì ngoài vi c ki m l i chính t , nó còn có các ch c n ng h u ích cho ng nh ng ch c n ng ó không c xem xét ây. Tuy nhiên, p pháp, khách hàng ph i tr ti n b n quy n. nào c ng áp ng c. - 10 - i Vi t nh chuy n mã, b gõ, dùng nó m t cách u này không ph i ng i dùng Cách ti p c n d a trên ng li u cho ki m l i chính t ti ng Vi t Tuy nhiên, v i ch c n ng ki m l i chính t , VietSpell không h có m t mô hình ngôn ng hoàn ch nh, mà ch phát hi n l i d a vào các heuristic, nên v n còn ph m m t s l i tích c c l n tiêu c c, Bên c nh ó, VietSpell v n gây ra m t s xung t v i MS Word, nh t là v i MS Word các phiên b n sau này nh Word 2003. Ngoài ra, VietSpell v n còn m t s l i v k thu t thi t k ch ch n kh i sai, ôi khi làm h v n b n ngu n, a ra ng trình nh ngh s a l i m t cách không h p lý, … 1.2.2. Ki m l i chính t d a vào phân tích cú pháp m 1999, trong lu n v n t t nghi p i h c, Nguy n c H i và Nguy n Ph m H nh Nhi [HN99] ã phân tích cú pháp. ây xu t mô hình ki m l i chính t ti ng Vi t b ng cách c xem là cách ti p c n d a trên lu t. Theo mô hình này, câu u vào s c h th ng ti n hành phân tích cú pháp b ng thu t toán Earley. Nh ng ch không phân tích c s b xem là l i chính t . Earley là m t thu t toán m nh cho phân tích cú pháp. Tuy nhiên do có ph c t p cao: O(n3) v i n là s ti ng trong câu, Earley c n c cài tt t t ng th i gian x lý. áp d ng Earley cho ti ng Vi t, câu u ki n nó có th b sai chính t . u vào c n ph i c tách t trong ó là khó kh n th nh t. m khó kh n th hai, là các lu t ng pháp c a ngôn ng t nhiên r t ph c t p, ti ng Vi t có kho ng 3000 lu t, trong khi ch ng trình ch t p h p kh n ti p theo, ti ng Vi t là ngôn ng các ti ng tr c kho ng 700 lu t. m khó n l p, s ti ng l i ít, nên vi c ph i h p t o thành câu “nghe có v h p lý” c ng nhi u, do ó có r t nhi u ng h p câu sai chính t nh ng v n phân tích cú pháp chính c a ph c. ây là h n ch ng pháp này. ng v i cách ti p c n trên, [TPLT98] ã xây d ng ch chính t VPCTTV. Ch 140 t lo i, 2000 lu n và ng trình ki m l i ng trình này có ph n hoàn ch nh h n [HN99] do có t chính xác 95%. - 11 - n