Luận án Nghiên cứu phát triển một số kỹ thuật tách từ Tiếng Việt

ắc, nặng (5 thanh cuối là có dấu). Việc biểu diễn kí tự Việt có dấu trong bảng mã unicode giữa dựng sẵn và tổ hợp khác nhau ở 7 mã: 2 mã kí tự đ và Đ, 5 mã dấu thanh. - 130 - Thuật toán A2. Thuật toán chuyển mã unicode. //=========================================================== //Đầu vào: s là dãy kí tự Việt unicode dựng sẵn/tổ hợp/cả hai //Đầu ra : trả về dãy kí tự Việt unicode dựng sẵn st. //=========================================================== string ToStdUnicode(s: string){ stNoMarkedViet  "aăâeêioôơuưy"; stMarkedViet  "àảãáạằẳẵắặầẩẫấậèẻẽéẹềểễếệìỉĩíị" + "òỏõóọồổỗốộờởỡớợùủũúụừửữứựỳỷỹýỵ"; i  1; st  ""; // chuỗi convert về mã unicode dựng sẵn. while (i  len(s)){ kt  s[i]; code2  0; if (i < len(s)) code2  (int)s[i+1]; mark  0; // không dấu: dấu ngang switch code2 { case 768: mark  1; break; // dấu huyền case 777: mark  2; break; // dấu hỏi case 771: mark  3; break; // dấu ngã case 769: mark  4; break; // dấu sắc case 803: mark  5; break; // dấu nặng } if (dau > 0) { p  Position(lower(kt), stNoMarkedViet); if (p > 0) { p  p*5 + mark - 1; //vị trí trong stMaredkViet isUpper  (kt = Upper(kt)); kt  stMaredkViet[p]; if isUpper kt  Upper(kt); } i  i + 1; }else { switch (int)kt { case 240: kt  "đ"; break; // => mã mới 273 case 208: kt  "Đ"; break; // => mã mới 272 } } st  st + kt; i  i + 1; } return st; } Độ phức tạp của thuật toán là O(n), với n là số kí tự trong chuỗi vào s. - 131 - A3. Thuật toán sửa lỗi chính tả dấu thanh tiếng Việt tự động Theo [27], cấu tạo âm tiết tiếng Việt được mô tả như Hình A.1. Hình A3.1. Cấu tạo âm tiết tiếng Việt Theo [20] thì có đến 5 quy tắc đặt dấu thanh cho tiếng Việt, và theo [27] thì rút gọn lại còn 2 quy tắc cơ bản như sau: Quy tắc 1. Khi vần có một nguyên âm, dấu thanh đặt tại nguyên âm đó. Quy tắc 2. Khi vần có từ hai nguyên âm trở lên: + Nếu vần đang xét về nguyên tắc có thể kết hợp (hoặc đã sẵn có) một trong số các phụ âm: C, CH, M, N, NG, NH, P, T làm âm cuối, ta đặt dấu thanh vào nguyên âm cuối cùng bên phải (hoàng, quyết, quyển, giường, thiếp, bước,...). + Nếu vần đang xét về nguyên tắc không thể kết hợp được với một trong số các phụ âm cuối, ta đặt dấu thanh vào nguyên âm bên trái của nguyên âm cuối cùng (hoài, hỏi, hảo, màu, múa, phía,...). Phân tích âm tiết tiếng Việt Theo kết quả phân tích âm tiết tiếng Việt trên máy tính [27] thì cấu tạo âm tiết tiếng Việt được mô tả theo cách sau: ÂM-TIẾT = [PHỤ ÂM ĐẦU] + + [PHỤ ÂM CUỐI] với [...] là phần không bắt buộc, và là bắt buộc phải có. (i) Phụ âm đầu: có 27 dạng: B, C, CH, D, Đ, G, GH, GI, H, K, KH, L, M, N, NG, NGH, NH, P, QU, R, S, T, TH, TR, V, X và rỗng (không có). (ii) Âm giữa: là tổ hợp các nguyên âm tạo thành. Theo định nghĩa này, có thể chia các âm giữa thành ba loại: + Âm giữa loại 1: có thể kết hợp với phụ âm cuối hoặc không để tạo vần. Có 14 dạng: A, E, Ê, I, Y, O, Ô, Ơ, U, Ư, OA, OE, UÊ, UY. + Âm giữa loại 2: là những âm không thể kết hợp với phụ âm cuối. Có 33 dạng: AI, AO, AU, AY, ÂU, ÂY, EO, ÊU, IA, IU, OI, ÔI, ƠI, ƠU, UA, UI, UƠ, ƯA, ƯI, ƯU, IÊU, OAI, OAO, OAY, OEO, UÂY, UÔI, UYA, UYU, ƯƠI, ƯƠU, YÊU, YU. - 132 - + Âm giữa loại 3: là bắt buộc phải kết hợp với phụ âm cuối để tạo vần. Có 10 dạng: Ă, Â, IÊ, OĂ, OO, UÂ, UÔ, UYÊ, ƯƠ, YÊ. (iii) Phụ âm cuối: có 8 dạng: C, CH, M, N, NG, NH, P, T. Trong đó, chia thành hai nhóm với cách đánh dấu thanh khác nhau: + M, N, NG, NH: các âm giữa có thể nhận đến 6 dấu thanh. + C, CH, P, T: các âm giữa chỉ có thể nhận thanh sắc và nặng. Quy tắc đánh dấu thanh như sau: - Vị trí đặt dấu thanh: theo nguyên tắc đặt tại âm chính, được xác định: + Với âm giữa loại 1/3: đặt dấu thanh tại vị trí nguyên âm cuối. A, E, Ê, I, Y, O, Ô, Ơ, U, Ư, OA, OE, UÊ, UY. Ă, Â, IÊ, OĂ, OO, UÂ, UÔ, UYÊ, ƯƠ, YÊ. + Với âm giữa loại 2: đặt vào vị trí bên trái của nguyên âm cuối. AI, AO, AU, AY, ÂU, ÂY, EO, ÊU, IA, IU, OI, ÔI, ƠI, ƠU, UA, UI, UƠ, ƯA, ƯI, ƯU, IÊU, OAI, OAO, OAY, OEO, UÂY, UÔI, UYA, UYU, ƯƠI, ƯƠU, YÊU, YU. - Với âm tiết có phụ âm cuối: C, CH, P, T thì chỉ đặt thanh sắc/nặng. Thuật toán A3. Thuật toán sửa lỗi chính tả dấu thanh tự động. Bước 1. Tách văn bản thành mảng các đơn vị ati (bằng dấu cách). Bước 2. Nếu ati chứa nguyên âm có dấu, và ati  từ điển âm tiết (lỗi) thì tách ra 4 phần: dấu thanh, phụ âm đầu, âm giữa và phụ âm cuối. Bước 3. Tạo lại âm tiết ati mới với các thông tin cũ (gồm có phụ âm đầu, âm giữa và phụ âm cuối) với dấu thanh đặt theo quy tắc đã nêu. Bước 4. Ghép mảng các đơn vị ati lại thành văn bản mới. Độ phức tạp thuật toán là O(n), với n là số lượng âm tiết trong văn bản. A4. Thuật toán xây dựng từ điển automat tối thiểu Thông thường, việc tìm kiếm 1 từ trong từ điển với kích thước n mất thời gian là O(log2n) với tìm kiếm nhị phân. Các giải pháp kiểm lỗi chính tả trong [1], [27] rút thời gian tìm kiếm còn O(1), nhất là dùng DFA (Deterministic Finite Automata) dạng cây hậu tố (Suffix-Trie) hay DFA tối thiểu (min-DFA). Giả sử từ điển có 40 từ được sắp xếp và đánh số từ 0 đến 39: a, an, ang, anh, ga, gan, gang, ganh, ha, han, hang, hanh, na, nan, nang, nanh, nga, ngan, ngang, nganh, nha, nhan, nhang, nhanh, ra, ran, rang, ranh, ta, tan, tang, tanh, tha, than, thang, thanh, tra, tran, trang, tranh. - 133 - Automat (DFA) cây hậu tố cho từ điển 40 từ có câu trúc như Hình A4.1. Hình A4.1. Automat cây hậu tố của từ điển 40 từ Automat cây hậu tố gồm có 50 trạng thái (1 trạng thái bắt đầu, 9 trạng thái chưa kết thúc và 40 trạng thái kết thúc). Tiến hành rút gọn tối thiểu, các nút tương đương được rút gọn, các nhánh giống nhau được ghép lại trên toàn bộ Automat. Cuối cùng ta thu được một Automat tối thiểu chỉ còn 7 trạng thái (với 1 trạng thái bắt đầu: q0, 3 trạng thái kết thúc: q4, q5, q6) rất gọn như sau: - 134 - Hình A4.2. Automat sau khi được rút gọn cho từ điển 40 từ A4.1. Thuật toán xây dựng Automat tối thiểu Để tạo một Automat có kích thước tối thiểu, có thể tiến hành biến đổi Automat đã xây dựng. Đối với các từ điển lớn, nếu xây dựng Automat dạng cây hậu tố như Hình A4.1 chiếm khá nhiều bộ nhớ, nếu thực hiện rút gọn Automat dựa vào cây hậu tố sẽ chi phí rất nhiều thời gian. Do vậy, ta tiến hành xây dựng trực tiếp Automat tối thiểu mà nhiều tác giả đã nghiên cứu như: Mohri, Mihov, Watson, Hopcroft, Daciuk, Ciura, Deorowicz,... Khai báo dữ liệu dùng cho việc xây dựng Automat tối thiểu: Class State { string Alphabet; /* bảng chữ cái chấp nhận */ State[sizeof(Alphabet)] Child; /* các nút con */ bool isFinal; /* có thuộc tập kết thúc không ? */ } State MinDFA; /* Automat tối thiểu chứa từ điển */ /* cần xây dựng DFA có số trạng thái là tối thiểu */ Hashtable Register; /* tập chứa các nút của minDFA */ State q0  MinDFA; /* trạng thái ban đầu của DFA */ Thuật toán A4.1. Thuật toán xây dựng Automat tối thiểu theo [93]. 1) Register  ; 2) For i  1 To sizeof(DIC) { /* từ điển DIC đã sắp xếp*/ a) W  DIC[i]; /* đọc từng từ trong từ điển */ b) CommonPrefix  common_prefix(W); /* tiền tố chung */ c) LastState  *(q0, CommonPrefix); d) CurrentSuffix  W[length(CommonPrefix)+l..length(W)]; e) If has_children(LastState) et) replace_or_register(LastState); /* tối thiểu */ f) add_suffix(LastState, CurrentSuffix); /*thêm hậu tố */ } 3) replace_or_register(q0); /* tối thiểu lần cuối */ - 135 - Trong đó: string common_prefix(W) { /* lấy tiền tố chung */ 1) WordPrefix  ""; 2) i  1; 3) q  q0; 4) While (i  length(W)) && (q  NULL) Do { a) WordPrefix  WordPrefix + W[i]; b) q  *(q,W[i]); c) i  i + 1; } 5) Return WordPrefix; } /* trả về tiền tố chung của từ W với Automat */ void replace_or_register(state) { /* thực hiện tối thiểu */ 1) child  last_child(state); /* nút con (cuối) của state */ 2) If has_children(child) a) replace_or_register(child); /* gọi đệ quy */ 3) If qQ (q  Register  q  child) { 3t1) last_child(state)  q; 3t2) delete(child); /* tối thiểu = xoá nút tg/đương */ }Else { 3f) Register  Register  {child}; } /* tập chứa các nút tối thiểu của Automat */ } Đánh giá độ phức tạp thuật toán A4.1: Từ điển đã sắp xếp có m từ, nên vòng lặp chính thực hiện m lần. Hàm common_prefix thực hiện O(|w|) lần, với |w| là độ dài cực đại của 1 từ. Hàm replace_or_register thực hiện đệ quy tối đa |w| lần cho mỗi từ. Trong mỗi lần gọi đệ quy, có một thanh ghi Register lưu giữ khoá theo thứ tự từ điển để tìm kiếm và có thể có 1 phép thêm vào. Thời gian tìm kiếm một nút trên thanh ghi này là O(logn), với n là số nút trạng thái của Automat tối thiểu. Việc so sánh sự tương đương giữa hai nút trạng thái (bước 3 của hàm replace_or_register) theo số cung ra là ||, với  là bảng chữ cái cực đại chấp nhận được của automat tối thiểu (với || < n). Tổng thời gian tìm kiếm một nút trạng thái sẽ là O(||logn). Việc thêm một trạng thái vào thanh ghi với thời gian là O(logn). Do vậy, tổng thời gian cho toàn bộ thuật toán là O(m|w|||logn). Nếu sử dụng bảng băm cho thanh ghi Register, thì thời gian cho tìm kiếm sẽ là O(||), thời gian thêm vào thanh ghi sẽ là O(1), khi đó độ phức tạp cho toàn bộ thuật toán sẽ là O(m|w|||), thường |w| là hữu hạn nhỏ, nên độ phức tạp sẽ là O(m||). - 136 - Thuật toán kiểm tra một từ ở trong hay ngoài từ điển bằng MinDFA Với Automat đã xây dựng bằng cấu trúc cây hậu tố Suffix-Trie hay Automat tối thiểu (MinDFA), ta sử dụng tập trạng thái kết thúc của Automat để kiểm tra một từ có thuộc từ điển hay không theo quy tắc: từ w là thuộc từ điển nếu (q0,w)  F (là tập trạng thái kết thúc). Thuật toán A4.2. Kiểm tra một từ ở trong hay ngoài từ điển. bool InDict(string w, State MinDFA) { 1) i  1; 2) q  MinDFA; 3) While (i  length(w)) { a) If ((q,w[i]) == NULL) Return FALSE; b) q  (q,w[i]); c) i  i + 1; } 4) Return isFinal(q); } Độ dài của một từ |w| là một hữu hạn nhỏ, nên độ phức tạp là O(1). Kết quả thử nghiệm Thực hiện với từ điển mẫu gồm 40 từ như ví dụ đã nêu, và thử nghiệm với các từ điển âm tiết, từ điển từ vựng tiếng Việt VCL như trong bảng A4.1. Bảng A4.1. Kết quả thử nghiệm Automat tối thiểu trên một số từ điển TT Từ điển (TĐ) K/thước từ điển Số nút đã tạo Số nút bị xoá Số nút tối thiểu K/thước MinDFA 1 TĐ mẫu 40 từ 142 byte 50 43 7 87 byte 2 TĐ 7015 âm tiết 24 KB 8620 8020 600 20 KB 3 TĐ 8428 âm tiết 29 KB 10051 9456 595 22 KB 4 TĐ 12062 âm tiết 42 KB 13663 13327 336 18 KB 5 TĐ VCL 31148 từ 230 KB 99050 74662 24388 270 KB Kích thước của MinDFA được tính dựa trên tổng kích thước các nút: + Kích thước bảng chữ cái chấp nhận theo ngữ cảnh của mỗi nút trạng thái (mỗi chữ cái tương ứng với 1 byte). + Tổng kích thước các con trỏ nút trạng thái ứng với bảng chữ cái, tương ứng với một cung ra trong Hình A4.2 (mỗi con trỏ có kích thước là 4 byte). + Kích thước của biến isFinal là 1 byte, tại mỗi nút trạng thái. Ví dụ, với Hình A4.2, DFA tối thiểu có kích thước như sau: Mem(DFA) = số_cung*5 + số_nút = 16*5 + 7 = 87 bytes Như vậy, DFA tối thiểu có thời gian tìm kiếm là O(1) và có kích thước tối - 137 - thiểu, tương đương với kích thước từ điển, trong một số trường hợp còn nhỏ hơn nhiều (xem Bảng A4.1, dòng 4: 18KB / 42 KB). A4.2. Thuật toán xây dựng bộ chỉ số cho Automat tối thiểu Hàm InDict dùng Automat thay vì trả về TRUE/FALSE, được thay bằng hàm WordToIndex: nếu một từ không có trong từ điển sẽ trả về giá trị -1, ngược lại sẽ trả về giá trị Index ứng với chỉ số của nó trong từ điển. Biến đổi ngược, với chỉ số Index hợp lệ sẽ trả về một từ tương ứng bằng hàm IndexToWord. Automat tối thiểu được xây dựng theo [93] và [102] có các nút móc xích nhau, nên việc đánh trọng số là khá phức tạp. Trong [55] và [102] đưa ra phương pháp gán trọng số cho các nút để thực hiện phép băm hoàn hảo theo thứ tự từ điển. Như vậy phải duyệt lại khá nhiều tại các nút rẽ nhánh khi Automat hoạt động. Luận án đề xuất gán trọng số trên các cung ra của các nút trạng thái, song song với kí hiệu chuyển trạng thái. Như vậy, thuật toán quét của Automat gần như không thay đổi, chỉ thêm một phép cộng dồn trọng số; không cần duyệt tại các nút rẽ nhánh. Dùng mảng Number mô tả trọng số trên cung ra ứng với tập kí hiệu chuyển trạng (Alphabet): Class State { string Alphabet; /* bảng chữ cái chấp nhận */ State[sizeof(Alphabet)] Child; /* các nút con */ Int[sizeof(Alphabet)] Number; /* trọng số ra */ bool isFinal; /* có thuộc tập kết thúc không ? */ } Với Automat tối thiểu (Hình A4.2), tiến hành duyệt từ điển để đánh chỉ số cho các cung của Automat như Hình A4.3. Thuật toán A4.3. Thuật toán đánh trọng số cho Automat tối thiểu. 1) PrevWord  ""; 2) For i  1 To sizeof(DIC) { /* DIC sắp xếp theo từ điển */ a) q  Automat; b) Index  0; /* bắt đầu từ 0 */ c) CurWord  DIC[i]; d) j  1; e) While (jlength(CurWord))&&(CurWord[j]==PreWord[j]) { e1) Index  Index + q.Number[CurWord[j]]; e2) p  (q, CurWord[j]); e3) j  j + 1; } f) p.Number[CurWord[j]]  i  Index; /* trọng số nút */ g) PreWord  CurWord; } - 138 - Tất cả các cung ra của Automat tối thiểu ban đầu được khởi tạo với trọng số Index là 0. Thuật toán này có độ phức tạp O(N), trong đó N là kích thước từ điển. Với Automat tối thiểu có trọng số như trên có thể chuyển đổi một từ thành chỉ số và ngược lại. Minh hoạ gán trọng số trong Hình A4.3. Hình A4.3. Gán trọng số trên các cung của Automat tối thiểu Thuật toán A4.4. Thuật toán mã hoá từ sang chỉ số: WordToIndex. int WordToIndex(string w) { 1) i  1; 2) q  Automat; 3) Index  0; 4) While i  length(w) { a) If ((q, w[i])== NULL) Return -1;/* ngoài TĐ */ b) Index  Index + q.Number[w[i]]; c) q  q = (q, w[i]); d) i  i + 1; } 5) If isFinal(q) Return Index /* từ có trong từ điển */ Else Return -1; /* không có trong từ điển */ } Độ dài cực đại từ |w| là nhỏ, nên độ phức tạp của thuật toán là O(1) Thuật toán A4.5. Thuật toán giải mã chỉ số ra từ dùng Automat tối thiểu. string IndexToWord(int Index) { 1) q  Automat; 2) Word  ""; 3) Repeat a) i  0; b) Repeat i  i + 1; Until (q.number[i]>Index) Or (i>Length(q.Alphabet); c) If (q.number[i] > Index) i  i – 1; d) Word  Word & q.Alphabet[i]; - 139 - e) Index  Index - q.Number[i]; f) q  (q, q.Alphabet[i]); Until (Index = 0) Or (q = NULL); 4) While (q  NULL) && (not isFinal(q)) { a) Word  Word & q^.Alphabet[1]; b) q  q^.Child[q^.Alphabet[1]]; } 5) If (q  NULL) Return Word /* tìm thấy */ Else Return ""; /* từ rỗng */ } Kích thước bảng chữ cái || là hữu hạn, nên độ phức tạp là O(||) = O(1). Hoặc có thể dùng từ điển sắp xếp DIC để lấy từ theo chỉ số Index. string IndexToWord(int Index) { Return DIC[Index]; } Độ phức tạp của thuật toán là O(1). B. MINH HOẠ KẾT QUẢ THỐNG KÊ TỪ CÁC TÀI NGUYÊN B1. Minh hoạ một số lỗi trong kho ngữ liệu VietTreeBank + Lỗi mã unicode tổ hợp và dựng sẵn trong các văn bản thuộc Corpus: Ví dụ: Từ điển VCL và kho ngữ liệu VietTreeBank sử dụng bảng mã Unicode dựng sẵn theo chuẩn TCVN 6909:2001. Tuy nhiên cả hai tài nguyên này có một số chỗ vẫn sử dụng bảng mã Unicode tổ hợp. (155 lỗi) + Lỗi chính tả, không thống nhất vị trí dấu thanh, lỗi do đánh máy: Ví dụ: Từ điển VCL và kho VietTreeBank (kho 70.000 câu) còn nhiều lỗi chính tả. Đặc biệt là kho ngữ liệu VietTreeBank có nhiều lỗi chưa thống nhất cách đánh dấu thanh trên các âm tiết (tiếng) có các tổ hợp nguyên âm: "oa", "oe", "uy" theo chuẩn chính tả hiện hành. (7.801 lỗi) + Lỗi tách câu: Ví dụ: Kho VietTreeBank (kho 70.000 câu) có quá nhiều lỗi tách câu không đúng do không có quy tắc phân tách giữa số, kí tự và dấu câu. Chẳng hạn, trong file 27157.seg có chứa 4 câu đã được tách bị lỗi như sau: Mọi thắc_mắc xin liên_hệ Vi_Thảo , email : huynhvithao @ tuoitre . com . vn . Chân_thành cảm_ơn các bạn . - 140 - Nếu tách đúng sẽ còn 2 câu là: Mọi thắc_mắc xin liên_hệ Vi_Thảo , email : huynhvithao@tuoitre.com.vn . Chân_thành cảm_ơn các bạn . Hoặc trong file 37924.seg có chứa 2 câu đã được tách như sau: TP. HCM : từ 1-7 , giá nước tăng lên 2.700 - 8.000 đồng / m 3 Nếu tách đúng, chúng sẽ còn 1 câu là: TP. HCM : từ 1-7 , giá nước tăng lên 2.700 - 8.000 đồng / m3 + Lỗi thực thể: Vấn đề tách thực thể ngày tháng không thống nhất trong các kho ngữ liệu của VietTreeBank (SP73) [10]: giữa kho 70.000 câu đã tách từ (SP731); kho 10.000 câu đã tách từ và gán nhãn từ loại (SP732); và kho 10000 câu đã tách từ, gán nhãn từ loại và gán nhãn cú pháp (SP733). Ví dụ: file 9778.seg thuộc VietTreeBank (70.000 câu) có hai dạng khác nhau về ngày tháng năm: "ngày 20 - 11" và "ngày_20_-_11_-_2003" Trong SP731, đa số thực thể ngày tháng năm được ghép lại, chẳng hạn: 2004_/_01_/_15 , 20_-_1_-_1975 , 18-1-2003 (trong file 16424.seg) Ngày_12_tháng_4_năm_2004 (trong file 28422.seg) ngày_23_-_1_-_2003 (trong file 11119.seg) tháng_11_-_2003 (trong file 10155.seg) năm_2006 (trong file 1019.seg) Trong SP732, các thực thể ngày tháng được tách ra: 2-10-1971 (trong file 82342.seg.pos) ngày 11 - 9 - 2005 (trong file 100276.seg.pos) tháng 3 - 2005 (trong file 100649.seg.pos) năm 2005 (trong file 100824.seg.pos) Trong SP733, các thực thể ngày tháng được tách ra: 30-4-1975 (trong file 109898.van.prd) ngày 28 - 4 - 1969 (trong file 90324.prd, 90324.raw) tháng 5 - 2004 (trong file 90483.prd, 90483.raw) năm 1967 (trong file 90324.prd, 90324.raw) - 141 - Các thực thể ngày tháng của kho SP731 là khác so với SP732 và SP733, do vậy, kho SP731 cần được sửa lại cho thống nhất với SP732 và SP733. B2. Thống kê sửa lỗi chính tả các kho ngữ liệu mẫu tiếng Việt Bảng B2.1. Thống kê sửa lỗi chính tả các kho ngữ liệu mẫu tiếng Việt (Sử dụng từ điển VCL 31.158 từ vựng và từ điển VSD 7015 âm tiết) SP731 SP732 Thống kê chung về các kho ngữ liệu gốc Số lượng (%) Số lượng (%) Tổng số đơn vị từ 1538050 100 221778 100 Tổng đơn vị âm tiết 1981510 100 264368 100 Tổng số dấu cách thừa 11270 146 Tổng số dấu nối thừa 80 5 Trước khi sửa lỗi Tổng từ ngoài từ điển 23026 1,50 3295 1,49 Tổng âm tiết ngoài TĐ 8825 0,45 1191 0,45 Mã unicode được sửa 155 5 Lỗi chính tả được sửa 7801 929 Sau khi sửa tự động Tổng từ ngoài từ điển 18077 1,18 2710 1,22 Tổng âm tiết ngoài TĐ 3683 0,19 587 0,22 B3. Thống kê các kí tự đặc biệt trong các kho ngữ liệu Kí tự đặc biệt: _ | ` ^ ~ ! @ # $ % & * ( ) - + = { } [ ] \ / ; : . , .. " ... ' Mục đích thống kê nhằm chọn các kí tự đặc biệt ít xuất hiện làm kí hiệu cho bài toán tách từ hay gán nhãn từ loại. (Kết quả từ Bảng B3.1: "_" và "|"). Bảng B3.1. Thống kê kí tự đặc biệt (kí hiệu) trong các kho ngữ liệu TT Kí hiệu SP731 SP732 rawCorpus 1 ! 1.936 579 10.075 2 " 26.289 5.637 76.860 3 # 0 0 22 4 $ 0 0 102 5 % 1.612 74 6.043 6 & 329 39 621 7 ' 134 2 166 8 ( 9.457 744 38.934 9 ) 9.463 746 44.282 10 * 1.277 46 1.938 - 142 - 11 + 42 1 1.985 12 , 82.704 11.952 418.064 13 - 22.822 1.950 67.051 14 . 61.962 9.184 288.684 15 .. 35 0 65 16 ... 6.585 1.422 6.685 17 : 13.883 1.592 42.115 18 ; 1.990 107 21.380 19 < 0 0 162 20 = 6 0 1.401 21 > 16 18 374 22 ? 2.532 397 14.371 23 @ 32 1 63 24 [ 0 0 9.524 25 \ 0 0 101 26 / 7.587 123 9.809 27 ] 0 0 9.501 28 ^ 0 0 28 29 ` 0 0 14 30 { 0 0 139 31 | 0 0 4 32 } 0 0 135 33 ~ 0 1 44 34 _ 0 0 3 B4. Thống kê phân loại thực thể và độ dài thực thể trong các kho ngữ liệu B4.1. Thống kê phân loại thực thể trong các kho ngữ liệu mẫu Bảng B4.1. Thống kê phân loại thực thể trong các kho ngữ liệu mẫu SP731 SP732 Tiêu chí thống kê Số lượng tỉ lệ (%) Số lượng tỉ lệ (%) Tổng số từ - thực thể 119770 100 10917 100 Thực thể tên riêng 45815 38,25 5240 48,00 Thực thể tên viết tắt 27961 23,35 1813 16,61 Thực thể mã (kí tự+số) 1174 0,98 49 0,45 Thực thể số 36407 30,40 3618 33,14 Thực thể số bằng chữ 107 0,09 36 0,33 Thực thể ngày tháng 4026 3,36 41 0,38 Thực thể thời gian 2626 2,19 43 0,39 - 143 - Thực thể tỉ lệ % 1612 1,35 74 0,68 Thực thể url/domain 19 0,02 0 0,00 Thực thể email 14 0,01 0 0,00 Thực thể đơn vị đo 0 0,00 0 0,00 Thực thể khác 9 0,01 3 0,03 B4.2. Thống kê thực thể theo độ dài trong các kho ngữ liệu mẫu Bảng B4.2. Thống kê thực thể theo độ dài trong các kho ngữ liệu mẫu SP731 SP732 Tiêu chí thống kê Số lượng tỉ lệ (%) Số lượng tỉ lệ (%) Tổng số đơn vị từ 1542673 100 221221 100 Tổng số từ - thực thể 119770 7,764 10917 4,935 Tổng thực thể 1 âm tiết 79242 5,137 6723 3,039 Tổng thực thể ≥ 2 âm tiết 40528 2,627 4194 1,896 Tổng thực thể 2 âm tiết 30019 1,946 3075 1,390 Tổng thực thể 3 âm tiết 9865 0,639 1083 0,490 Tổng thực thể 4 âm tiết 630 0,041 35 0,016 Tổng thực thể ≥ 5 âm tiết 14 0,001 1 0,000 B5. Danh sách các từ tố tên riêng, tên riêng đặc biệt và tên họ người Việt B5.1. Danh sách các từ tố nhập nhằng với các thực thể tên riêng Bảng B5.1. Danh sách các từ tố nhập nhằng với các thực thể tên riêng Kiểu từ tố Danh sách từ tố của tên riêng (ListPreNE) Chỉ người Anh, Bà, Bác, Bạn, Bầu, Bé, Cả, Cai, Cái, Cậu, Cha, Cháu, Chị, Chồng, Chú, Chúa, Cô, Cố, Con, Cu, Cụ, Dì, Dượng, Em, Già, Họ, Lão, Má, Mẹ, Mợ, Ngài, Ông, Soái, Tên, Thằng, Thầy, Thím, Tổng, Tướng, Vợ, Vua Chỉ bộ phận người Bụng, Cằm, Chân, Cổ, Da, Đầu, Đít, Đùi, Gan, Hông, Lưng, Lưỡi, Má, Mắt, Mật, Mặt, Miệng, Mồm, Mông, Mũi, Ngực, Óc, Phổi, Răng, Râu, Ruột, Tai, Tay, Thận, Tim, Tóc, Vai, Xương Chỉ địa điểm Ao, Ấp, Bãi, Bản, Bang, Bến, Biển, Bờ, Bót, Buôn, Cầu, Chợ, Chùa, Cồn, Cửa, Dải, Dinh, Đảo, Đầm, Đập, Đền, Đình, Đỉnh, Đồi, Đồn, Đường, Hẻm, Hồ, Huyện, Kênh, Làng, Lao, Lăng, Miền, Mỏ, Ngách, Ngõ, Ngọn, Núi, Nước, Phía, Phố, Phủ, Phường, Quận, Quê, Rạch, Rừng, Sân, Sông, Suối, Tháp, Thôn, Tỉnh, Vịnh, Vườn, Xã, Xóm - 144 - Chỉ tổ chức Ban, Băng, Báo, Bộ, Cục, Cụm, Đài, Đảng, Đạo, Đoàn, Đội, Hãng, Hạt, Hội, Kho, Khoa, Khu, Lớp, Nha, Nhóm, Phái, Phòng, Sở, Tổ, Trại, Trạm, Trường, Viện, Vụ Chỉ vật, sự việc, hiện tượng Bảng, Bệnh, Báo, Bò, Bọn, Bún, Cá, Cái, Cặp, Cây, Chiếc, Chim, Chó, Chủ, Chuột, Con, Cơm, Cục, Cúp, Cừu, Dê, Đêm, Đôi, Đống, Đợt, Gà, Gạo, Gấu, Giải, Giày, Giầy, Giọng, Heo, Hổ, Hôm, Hồn, Kịch, Kiểu, Lễ, Loại, Lời, Lợn, Lúa, Lừa, Luật, Mèo, Mì, Môn, Muỗi, Mỳ, Năm, Nền, Nếp, Ngành, Ngày, Nghề, Ngựa, Người, Nhà, Nơi, Nước, Phim, Phở, Quĩ, Quỹ, Rượu, Số, Sổ, Tấm, Tàu, Tết, Tháng, Thuốc, Tiếng, Tờ, Toà, Trà, Trận, Trâu, Tụi, Tuồng, Tương, Việc, Vịt, Voi, Xe Khác Bên, Biết, Bỏ, Bởi, Bỗng, Cả, Các, Cạnh, Chắc, Chính, Chờ, Chống, Chúc, Có, Còn, Của, Cùng, Dẫn, Dắt, Do, Dù, Dưới, Đánh, Đá, Đấm, Đặt, Đẩy, Để, Đến, Đi, Đợi, Đưa, Được, Gần, Gặp, Giờ, Giữa, Gọi, Hay, Hiện, Hoặc, Hồi, Hỏi, Kéo, Khách, Khi, Là, Lên, Lôi, Lúc, Mà, Mời, Mong, Một, Nay, Nếu, Ngay, Nghe, Ngoài, Nhiều, Nhìn, Nhớ, Nhờ, Như, Nhưng, Những, Nói, Ở, Ra, Riêng, Rồi, Rời, Sang, Sau, Tại, Tận, Tặng, Tay, Thấy, Theo, Thư, Thưa, Thương, Tới, Trên, Trong, Trước, Từ, Tuyển, Và, Vào, Về, Vì, Với, Vượt, Xin, Xuống B5.2. Danh sách các tên riêng đặc biệt (có nhập nhằng với từ tố) Bảng B5.2. Danh sách các tên riêng đặc biệt (có nhập nhằng với từ tố) Kiểu từ tố Danh sách tên riêng đặc biệt (ListSpecialNE) Từ tố chỉ người Anh_Sơn, Ba_Bể, Ba_Chẽ, Ba_Đình, Ba_Tri, Ba_Tơ, Ba_Vì, Bà_Bướm, Bà_Chúa, Bà_Chúa_Kho, Bà_Chúa_Xứ, Bà_Đen, Bà_Huyện_Thanh_Quan, Bà_Quẹo, Bà_Rịa_Vũng_Tàu, Bà_Rịa, Bà_Triệu, Bà_Trưng, Bác_Ái, Bác_Hồ, Bác_Tôn, Bố_Trạch, Cai_Lậy, Chú_Ía, Cô_Tô, Cụ_Hồ Từ tố chỉ địa điểm Bãi_Cháy, Bãi_Dâu, Bãi_Lữ, Bản_Đôn, Bến_Cát, Bến_Cầu, Bến_Dược, Bến_Lức, Bến_Nghé, Bến_Thuỷ, Bến_Tre, Biển_Chết, Biển_Đen, Biển_Đông, Buôn_Đôn, Buôn_Hồ, Buôn_Ma_Thuột, Cầu_Giấy, Cầu_Kè, Cầu_Kho, Cầu_Kiệu, Cầu_Muối, Cầu_Ngang, Cầu_Ông_Lãnh,Chợ_Cầu,Chợ_Đồn, Chợ_Gạo, Chợ_Lách, Chợ_Mới, Cồn_Cỏ, Đầm_Dơi, Đầm_Hà, Đầm_Vạc, Đất_Đỏ, Mỏ_Cày, Núi_Thành, Rạch_Giá, Sông_Cầu, Sông_Công, Sông_Hinh, Sông_Lô, Sông_Mã, Tháp_Chàm, Tháp_Mười, Xóm_Chiếu, Xóm_Củi - 145 - Từ tố chỉ tổ chức Ban_Tích, Đài_Bắc, Đài_Loan, Hội_An, Trạm_Tấu, Trường_Sa, Trường_Sơn_Đông, Trường_Sơn_Tây, Trường_Sơn, Vụ_Bản Từ tố chỉ vật, sự việc, hiện tượng Cái_Bè, Cái_Nước, Cái_Răng, Cờ_Đỏ, Con_Cuông, Củ_Chi, Cửa_Hội, Cửa_Lò, Cửa_Tùng, Cửa_Việt, Đống_Đa, Gò_Công, Gò_Dầu, Gò_Quao, Gò_Vấp, Hòn_Đất, Hòn_Khoai, Nhà_Bè, Trà_Bồng, Trà_Cổ, Trà_Cú, Trà_Lĩnh, Trà_Nóc, Trà_Ôn, Trà_Vinh, Vũng_Liêm, Vũng_Tàu, Vũng_Thơm Từ tố khác Bàn_Cờ, Bảo_Lâm, Bảo_Lộc, Bảo_Thắng, Bảo_Yên, Các_Mác, Cần_Đước, Cần_Giờ, Cần_Giuộc, Chà_Và, Hai_Bà_Trưng, Mê_Linh, Như_Anh, Như_Hằng, Như_Lan, Như_Mai, Như_Quỳnh, Như_Thanh, Như_Xuân, Từ_Liêm, Từ_Sơn B5.3. Thống kê khảo sát tên họ của người Việt Luận án thực hiện sưu tầm danh sách họ và tên của các thí sinh thi vào hai trường đại học của tất cả các tỉnh thành trong năm 2013, nhằm thống kê phân bố tỉ lệ họ người Việt và lọc ra danh sách họ người Việt. Tổng số thí sinh trong danh sách: 48.584 Số tên họ khác nhau của danh sách: 354 Bảng B5.3. Danh sách tên họ sắp xếp theo thứ tự tần suất và alphabet Tên Họ Số lg Tên Họ Số lg Tên Họ Số lg Tên Họ Số lg Tên Họ Số lg Tên Họ Số lg Nguyễn 16087 Hứa 25 Nguỵ 6 Quàng 3 Bê 1 Lỡ 1 Trần 4497 Kim 23 Phù 6 Tân 3 Bo 1 Lôi 1 Lê 4002 Lữ 23 Sái 6 Thiên 3 Cái 1 Lồng 1 Phạm 3311 Phương 23 Sử 6 Vàng 3 Cảnh 1 Lư 1 Vũ 1760 Từ 23 Tào 6 Viên 3 Cát 1 Luân 1 Hoàng 1458 Giáp 22 Tiêu 6 Bàng 2 Cầm 1 Mại 1 Đỗ 1401 Lường 20 Trầm 6 Báo 2 Cần 1 Man 1 Bùi 1289 Cù 19 Trượng 6 Cam 2 Chảo 1 Mao 1 Phan 1039 Khổng 19 Bành 5 Chương 2 Chẩu 1 Miêu 1 Ngô 1002 Khúc 19 Cung 5 Diêm 2 Chềnh 1 Miểu 1 Đặng 999 Y 18 Đình 5 Du 2 Chiêm 1 Mỗ 1 Võ 907 Lăng 17 Ksor 5 Đại 2 Chinh 1 Mộng 1 Huỳnh 695 Lục 17 Mẫn 5 Ê 2 Chìu 1 Mùng 1 Đinh 685 Vy 17 Quan 5 Hữu 2 Chuông 1 Muộn 1 Dương 674 Thạch 16 Quang 5 Kha 2 Chuyên 1 Nại 1 Hồ 646 An 15 Ung 5 Khang 2 Coọc 1 Ngàn 1 Trương 643 Ma 15 Uông 5 Khâu 2 Cố 1 Ngần 1 Đào 595 Nhữ 15 Ứng 5 Kheo 2 Cồ 1 Ngũ 1 Trịnh 504 H 14 Vân 5 Khoa 2 Cổ 1 Như 1 Đoàn 503 Thiều 14 Vòng 5 Kỳ 2 Diêu 1 Ni 1 Hà 438 Âu 13 Bàn 4 Lành 2 Dịp 1 Phẩm 1 Mai 438 Mã 13 Bồ 4 Lao 2 Dùng 1 Phu 1 - 146 - Lương 364 Quảng 13 Chamaléa 4 Lèo 2 Duy 1 Phúc 1 Cao 342 Chử 12 Định 4 Lều 2 Đảo 1 Quế 1 Lưu 311 Long 12 Đới 4 Liên 2 Đăng 1 Quyền 1 Phùng 294 Quản 12 Giàng 4 Liêu 2 Đầu 1 Roãn 1 Tạ 237 Lò 11 Hồng 4 Liễu 2 Địch 1 Sần 1 Chu 222 Mang 11 Lô 4 Lộ 2 Điện 1 Sin 1 Vương 145 Bế 10 Luyện 4 Mạch 2 Điệp 1 Sìn 1 Tô 136 Dư 10 Mầu 4 Mè 2 Điêu 1 Sô 1 Đàm 121 Lỗ 10 Ngân 4 Mùi 2 Đồ 1 Sơn 1 Lý 112 Danh 9 Ngọc 4 Não 2 Đôn 1 Sư 1 Lâm 110 H' 9 Ôn 4 Ngư 2 Đông 1 Tanh 1 Thái 104 Khương 9 Phú 4 Nhan 2 Đức 1 Tẩy 1 Kiều 102 Bá 8 Sầm 4 Phó 2 Giả 1 Thạc 1 Lại 93 Chung 8 Sú 4 Pinăng 2 Giao 1 Thập 1 Tống 80 Ngọ 8 Sùng 4 Sa 2 Giềng 1 Thịnh 1 Nông 78 Nguyên 8 Thành 4 Tài 2 Hách 1 Thuận 1 Văn 73 Trang 8 Thị 4 Tằng 2 Hảng 1 Thung 1 Triệu 66 Tưởng 8 Trình 4 Thẩm 2 Hành 1 Thượng 1 Đồng 64 Công 7 Tường 4 Thang 2 Hắc 1 Thuyên 1 Châu 61 Hán 7 Ca 3 Thế 2 Hiền 1 Tính 1 Lã 59 Hàn 7 Cà 3 Thiệu 2 Hình 1 Toàn 1 Quách 58 Hàng 7 Chế 3 Thới 2 Hỗ 1 Trác 1 Nghiêm 53 Linh 7 Chúc 3 Thòng 2 Hờ 1 Trọng 1 Vi 53 Nhâm 7 Đan 3 Tiết 2 Hoành 1 Trung 1 Thân 52 Trà 7 Đàng 3 Tòng 2 Hy 1 Tuấn 1 Đậu 45 Biện 6 Đạt 3 Và 2 Hỷ 1 Vạn 1 Tăng 45 Cáp 6 Điểu 3 Văng 2 Ích 1 Viết 1 Phí 42 Đạo 6 Giản 3 Vì 2 Ka 1 Voòng 1 Khuất 39 Đổng 6 Hùng 3 Vừ 2 Khắc 1 Xiêm 1 Bạch 36 Đường 6 K' 3 Yên 2 Kiềng 1 Xíu 1 Tôn 33 Hạ 6 Khà 3 A 1 Kống 1 Xồng 1 Diệp 30 Hoa 6 Khiếu 3 Alê 1 Kpă 1 Ya 1 Ninh 30 Katơr 6 Lai 3 Anh 1 Kỹ 1 Giang 29 Lầu 6 Lượng 3 Ân 1 Làu 1 Doãn 28 Lộc 6 Mấu 3 Bạc 1 Lầm 1 La 28 Lù 6 Nay 3 Dỉ 1 Li 1 Cấn 27 Mạnh 6 Ông 3 Bảo 1 Liêng 1 Mạc 26 Mông 6 Pi 3 Bằng 1 Liểu 1 Từ bảng B5.3, ta có thể vẽ biểu đồ tỉ lệ họ người Việt như Hình B5.1. Biểu đồ Hình B5.1 cho ta thấy, họ Nguyễn chiếm khoảng 1/3 tổng số, kế đến là họ Trần, Lê, Phạm, Vũ,... Hình B5.1. Biểu đồ phân bố tỉ lệ tên họ người - 147 - C. PHÉP ĐO ĐỘ TƯƠNG TỰ NGỮ NGHĨA DÙNG TỪ ĐIỂN VCL Độ tương tự ngữ nghĩa (semantic similarity) giữa các từ, các câu, hay các văn bản đóng một vai trò ngày càng quan trọng trong nghiên cứu xử lý ngôn ngữ tự nhiên. Đối với tiếng Anh, đã có nhiều nghiên cứu thực hiện dựa trên kho ngữ liệu (Corpus), cây ngữ nghĩa (Semantic Tree) và mạng từ (WordNet). Tuy nhiên đối với tiếng Việt thì còn khá mới mẻ, đặc biệt là cây ngữ nghĩa và mạng từ tiếng Việt cho đến nay vẫn chưa xây dựng xong. Do vậy, tiếp cận dựa trên định nghĩa của từ trong từ điển VCL là mới mẻ cần có những nghiên cứu và thử nghiệm. Vấn đề là làm thế nào để đo sự tương tự (sự giống nhau, hay sự tương đồng) giữa hai từ, hai câu, hoặc hai văn bản. Độ tương tự là một đại lượng phản ánh cường độ của mối quan hệ giữa hai đối tượng hoặc hai đặc trưng (ở đây là hai từ, hai câu hoặc hai văn bản) và giá trị của nó trong đoạn [-1,1] hoặc [0,1]. Ta có thể coi độ tương tự như một hàm tính điểm (score function). Hiện nay có hai phương pháp điển hình để đo độ tương tự của hai từ, hai câu hoặc hai văn bản là phương pháp thống kê và phương pháp xử lý ngôn ngữ tự nhiên. Với phương pháp thống kê, có một số phương pháp sử dụng các độ đo dựa vào tần suất xuất hiện của từ trong câu, nổi bật là phương pháp sử dụng độ tương tự Cosin. Phương pháp này xử lý nhanh, tốn ít chi phí tuy nhiên vẫn chưa đảm bảo độ chính xác cao về mặt ngữ nghĩa. Còn các phương pháp sử dụng xử lý ngôn ngữ tự nhiên, một số cách tiếp cận đặc trưng được đưa ra là sử dụng phân tích cấu trúc ngữ pháp, sử dụng mạng ngữ nghĩa đối với từ, như sử dụng Wordnet. Phương pháp xử lý ngôn ngữ tự nhiên xử lý chậm hơn, tốn nhiều chi phí hơn tuy nhiên khi xét về mặt ngữ nghĩa thì cho kết quả cao hơn so với phương pháp thống kê. Hiện nay, từ điển VCL (Vietnamese Computational Lexicon) [10] (dùng cho xử lý ngôn ngữ tiếng Việt trên máy tính) có 41.734 mục nghĩa với 31.158 từ khác nhau, gồm nhiều thông tin về cú pháp và ngữ nghĩa như: từ loại, tiểu từ loại, lớp ngữ nghĩa, đồng nghĩa, trái nghĩa, định nghĩa của từ,... Đây là cơ sở để tác giả luận án đưa ra phương pháp đo độ tương tự ngữ nghĩa giữa hai từ dựa trên định nghĩa của nó. Và đây cũng là một tiếp cận mới trong việc đo độ tương tự ngữ nghĩa giữa hai từ tiếng Việt mà không dùng thống kê, không dùng mạng từ WordNet, và cũng không dùng cây ngữ nghĩa như các nghiên cứu khác đã tiếp cận. Về mặt bản chất, đo độ tương tự ngữ nghĩa giữa hai từ thông qua hai định nghĩa trong từ điển, là đo độ tương tự giữa hai văn bản. Trong nghiên cứu ở đây sẽ trình bày tóm tắt một số cách đo độ tương tự ngữ nghĩa giữa hai văn bản. - 148 - C1. Độ tương tự dựa vào so khớp chuỗi xấp xỉ theo khoảng cách Dùng một số thuật toán so khớp chuỗi xấp xỉ. Cho 2 văn bản X, Y là 2 dãy từ tiếng Việt: X = {x1, x2, x3,..., xn} và Y = {y1, y2, y3,..., ym}, với | X | = n; | Y | = m; Ta có thể áp dụng một số công thức tính khoảng cách giữa 2 văn bản X, Y trên cơ sở âm tiết để tính độ tương tự của chúng. a. Độ tương tự dựa vào khoảng cách hiệu chỉnh ED (Edit Distance) |)||,max(| ),(|)||,max(|),( YX YXEDYXYXSimED  (C.1) Ví dụ: x = "con chó cắn con mèo" => X = (con, chó, cắn, con, mèo) y = "con mèo cắn con chuột" => Y = (con, mèo, cắn, con, chuột) Áp dụng công thức (C.1) để tính, ta có: ED(X,Y) = 2, do vậy: 6.05 25),( YXSimED b. Độ tương tự dựa vào LCS (Longest Common Subsequence) |||| |),(|2),( YX YXLCSYXSimLCS  (C.2) Với X = (con, chó, cắn, con, mèo) và Y = (con, mèo, cắn, con, chuột) Ta có: LCS(X,Y) = (con, cắn, con), nên | LCS(X,Y) | = 3, do vậy: 6.055 32),(  YXSimLCS Tương tự áp dụng với các độ đo khoảng cách còn lại như: HD (Hamming Distance), DLD (Damerau–Levenshtein Distance). Ngoài ra, có thể dùng các độ đo khoảng cách JW (Jaro–Winkler distance), khoảng cách Trigram (Trigram Distance), hay Ratcliff/Obershelp để tính độ tương tự giữa hai văn bản. C2. Độ tương tự dựa vào phép đo đồng xuất hiện Biểu diễn 2 văn bản X, Y theo hai dãy từ: X = {x1, x2, x3,..., xn} và Y = {y1, y2, y3,..., ym} Ta có: | X | = n; | Y | = m; và | X  Y | = số từ đồng xuất hiện trong X và Y. | X  Y | = | X | + | Y |  | X  Y | a. Độ tương tự Dice của hai văn bản X và Y |||| ||2),( YX YXYXSimDice   (C.3) - 149 - b. Độ tương tự Jaccard của hai văn bản X và Y || ||),( YX YXYXSimJaccard   (C.4) Ví dụ: x = "con chó cắn con mèo" và y = "con mèo cắn con chuột" Ta có: | X | = 5; | Y | = 5; | X  Y | = 4; | X  Y | = 6 Do vậy: 8.010 42|||| ||2),(   YX YXYXSDice 67.06 4 || ||),(   YX YXYXSJaccard C3. Độ tương tự theo vector (Vector Space Model) Văn bản được biểu diễn chuẩn hoá độ dài theo dạng vector như sau: = {x1, x2, x3,..., xm} và x y = {y1, y2, y3,..., ym} a. Độ tương tự Cosin (theo vector tần suất xuất hiện)     m k k m k k m k kk Cos yx yx yx yxyxYXSim 1 2 1 2 1 ||.|| .),cos(),(   (C.5) Ví dụ: x = "con chó cắn con mèo" => Cx = (con, chó, cắn, mèo) y = "con mèo cắn con chuột" => Cy = (con, mèo, cắn, chuột) Gọi Cxy = Cx  Cy = (con, chó, cắn, mèo, chuột) là dãy từ chung. Sau khi sắp xếp lại, ta có: Cxy = (cắn, chó, chuột, con, mèo) Theo tần suất xuất hiện, thì: X = (cắn:1, chó:1, chuột:0, con:2, mèo:1) x = (1, 1, 0, 2, 1) Y = (cắn:1, chó:0, chuột:1, con:2, mèo:1) y = (1, 0, 1, 2, 1) 86.07 6 )14101()14011( 14001),(  YXSimCos Hình C3.1. Minh hoạ vector và giá trị Cosin (Rich) - 150 - b. Độ tương tự theo vector thứ tự từ (Word-Order) Dùng cho 2 câu có các từ giống nhau, chỉ khác nhau thứ tự sắp xếp. |||| ||||1),( YX YX Order rr rrYXSim     (C.6) Ví dụ: x = "con chó cắn con mèo" => )5,4,3,2,1(Xr y = "con mèo cắn con chó" => )2,4,3,5,1(Yr Từ đó ta có: )3,0,0,3,0(  YX rr  )7,8,6,7,2( YX rr  7.010 31202 18178672 300)3(01),( 22222 22222  YXSimOrder D. MỘT SỐ THUẬT TOÁN SO KHỚP CỰC ĐẠI D1. So khớp cực đại MM (Maximum Matching) D1.1. So khớp cực đại tiến FMM Thực hiện so khớp cực đại với hướng tiến từ trái sang phải theo thứ tự của các âm tiết trong dãy vào. Có hai tiếp cận, một là quét toàn bộ dãy vào so sánh với từ điển, hai là chọn cửa sổ âm tiết để so sánh với từ điển. Tiếp cận thứ hai, giới hạn kích thước cửa sổ âm tiết, làm cho thuật toán nhanh hơn, tuy nhiên có thể bỏ sót một số từ có kích thước dài hơn cửa sổ âm tiết. Thuật toán D1.1. So khớp cực đại tiến với toàn bộ dãy vào FMM. + Đầu vào n âm tiết: S = a1 a2 a3 ... an-1 an. + Đầu ra là m từ: S = w1 w2 w3 ..... wm . (từ ghép được nối bằng "_"). 01 Function FMM(string S, State MinDFA) { 02 a  SplitToArray(S," "); /* tách ra từng âm tiết */ 03 n  count(a); i  1; 04 Repeat 05 w  a[i]; 06 q[i]  w; 07 k  i; 08 for j  k + 1 to n { 09 w  w + " " + a[j]; 10 if (InDict(w.ToLower, MinDFA)) { /* dùng MinDFA */ 11 q(i)  w.replace(" ","_"); /* là từ dài nhất */ 12 i  j; 13 } 14 } - 151 - 15 i  i + 1; 16 Until i > n; 17 i  1; 18 outS  ""; 19 Repeat 20 va SplitToArray(q[i],"_");/*độ phức tạp = count(va)*/ 21 outS  outS + " " + q[i]; 22 i  i + count(va); 23 Until (i > n); 24 return outS.Trim; 25 } Dãy vào gồm có n âm tiết. Dòng 02, hàm SplitToArray(S," ") tách dãy vào S thành từng âm tiết, cần thời gian là O(n). Từ dòng 04 đến 16, gồm hai vòng lặp lồng nhau đều duyệt n âm tiết, cần thời gian tối đa là O(n2). Từ dòng 19 đến dòng 23 là xuất kết quả tách từ, cần thời gian tối đa là O(n). Như vậy, độ phức tạp chung của thuật toán D1.1 là O(n2). Nếu sử dụng tìm kiếm nhị phân trong từ điển có N từ (tại dòng 10) thì sẽ tốn thêm một hệ số thời gian là O(log2N), khi đó, độ phức tạp của thuật toán sẽ là O(n2log2N). D1.2. So khớp cực đại lùi BMM Ngược lại với FMM, phương pháp BMM thực hiện so khớp cực đại theo hướng lùi từ phải qua trái theo thứ tự của các âm tiết trong dãy vào. Tương tự như FMM, BMM cũng có hai tiếp cận là quét toàn bộ hay dựa vào cửa sổ âm tiết để so sánh với từ điển, và cũng có ưu nhược điểm tương tự với FMM. Thuật toán D1.2. So khớp cực đại lùi với toàn bộ dãy vào BMM. + Đầu vào n âm tiết: S = a1 a2 a3 ... an-1 an. + Đầu ra là m từ: S = w1 w2 w3 ..... wm . (từ ghép được nối bằng "_"). 01 Function BMM(string S, State MinDFA) { 02 a  SplitToArray(S," "); /* tách ra từng âm tiết */ 03 n  count(a); i  n; /* từ phải qua trái: n => 1 */ 04 Repeat 05 w  a[i]; 06 q[i]  w; k  i; 07 for j  k - 1 downto 1 { 08 w  a[j] + " " + w; 09 if (InDict(w.ToLower, MinDFA)) /* dùng MinDFA */ 10 q(i)  w.replace(" ","_"); /* là từ dài nhất */ 11 i  j; 12 } 13 i  i - 1; 14 Until i < 1; 15 i  n; - 152 - 16 outS  ""; 17 Repeat 18 va SplitToArray(q[i],"_");/*độ phức tạp = count(va)*/ 19 outS  q[i] + " " + outS; 20 i  i - count(va); 21 Until (i < 1); 22 return outS.Trim; 23 } Tương tự như thuật toán D1.1, thuật toán D1.2 có độ phức tạp là O(n2), với n là số lượng âm tiết trong dãy vào. D2. So khớp cực đại có cửa sổ D2.1. So khớp cực đại tiến có cửa sổ WFMM Thuật toán D2.1. So khớp cực đại tiến với cửa sổ âm tiết WFMM. + Đầu vào n âm tiết: S = a1 a2 a3 ... an-1 an. + Đầu ra là m từ: S = w1 w2 w3 ..... wm . (từ ghép được nối bằng "_") 01 Function WFMM(string S, State MinDFA) { 02 a  SplitToArray(S," "); /* tách ra từng âm tiết */ 03 n  count(a); i  1; /* từ trái qua phải: 1 => n */ 04 Repeat 05 w  a[i]; q[i]  w; 06 k  i; winsize  if((k+3<n),k+3,n);/*cửa số âm tiết*/ 07 for j  k + 1 to winsize { 08 w  w + " " + a[j]; 09 if (InDict(w.ToLower, MinDFA)) /* dùng MinDFA */ 10 q(i)  w.replace(" ","_"); /* là từ dài nhất */ 11 i  j; 12 } 13 i  i + 1; 14 Until i > n; 15 i  1; 16 outS  ""; 17 Repeat 18 va SplitToArray(q[i],"_");/*độ phức tạp = count(va)*/ 19 outS  outS + " " + q[i]; 20 i  i + count(va); 21 Until (i > n); 22 return outS; 23 } Độ phức tạp của thuật toán D2.1 là O(n), n là số âm tiết trong dãy vào. D2.2. So khớp cực đại lùi có cửa sổ WBMM Thuật toán D2.2. So khớp cực đại lùi với cửa sổ âm tiết WBMM. + Đầu vào n âm tiết: S = a1 a2 a3 ... an-1 an. + Đầu ra là m từ: S = w1 w2 w3 ..... wm . (từ ghép được nối bằng "_"). - 153 - 01 Function WBMM(string S, State MinDFA) { 02 a  SplitToArray(S," "); /* tách ra từng âm tiết */ 03 n  count(a); i  n; /* từ phải qua trái: n => 1 */ 04 Repeat 05 w  a[i]; q[i]  w; 06 k  i; winsize  if((k-3>1),k-3,1);/*cửa số âm tiết*/ 07 for j  k - 1 downto winsize { 08 w  a[j] + " " + w; 09 if (InDict(w.ToLower, MinDFA)) /* dùng MinDFA */ 10 q(i)  w.replace(" ","_"); /* là từ dài nhất */ 11 i  j; 12 } 13 i  i - 1; 14 Until i < 1; 15 i  n; 16 outS  ""; 17 Repeat 18 va SplitToArray(q[i],"_");/*độ phức tạp = count(va)*/ 19 outS  q[i] + " " + outS; 20 i  i - count(va); 21 Until (i < 1); 22 return outS; 23 } Tương tự như thuật toán D2.1, việc chọn cửa sổ âm tiết cố định làm cho thuật toán D2.2 có độ phức tạp là O(n), với n là số lượng âm tiết trong dãy vào. E. THUẬT TOÁN NHẬN DIỆN VÀ KHỬ NHẬP NHẰNG TÊN RIÊNG E1. Thuật toán nhận diện tên riêng, nhận diện số và phân số bằng chữ E1.1. Thuật toán nhận diện thực thể tên riêng + Đầu vào là dãy âm tiết: S = w[1] w[2] w[3] .... w[i] ... w[n]. + Đầu ra outS có các tên riêng được nối nhau bằng dấu "_". + Ý tưởng: nếu dãy con từ 2 âm tiết trở lên là Proper thì đó là tên riêng. 01 TenRieng  ""; 02 for i  1 to n { 03 if isProper(w[i]) { 04 if (TenRieng == "") { 05 TenRieng  w[i]; 06 id  i; 07 }else 08 TenRieng  TenRieng + "_" + w[i]; 09 }else { 10 if (TenRieng != "") { - 154 - 11 w[id]  TenRieng; 12 for j  id + 1 to i – 1 13 w[j]  ""; 14 TenRieng  ""; 15 } 16 } 17 } 18 if (TenRieng != "") { 19 w[id]  TenRieng; 20 for j  id + 1 to i – 1 21 w[j]  ""; 22 } 23 outS  w[1]; 24 for i  2 to n do { 25 if (w[i] != "") 26 outS  outS + " " + w[i]; 27 } Độ phức tạp thuật toán là O(n), với n là số âm tiết trong dãy vào. E1.2. Thuật toán nhận diện dãy số và phân số bằng chữ + Đầu vào là dãy âm tiết: S = w[1] w[2] w[3] .... w[i] ... w[n]. + Đầu ra outS có dãy số, phân số bằng chữ được nối nhau bởi dấu "_". 01 for i  1 to n - 1 { 02 if (i ≤ n - 2) && isNumStr(w[i],w[i+1],w[i+2]) { 03 w[i]  w[i] + "_" + w[i+1] + "_" + w[i+2]; 04 w[i+1]  ""; 05 w[i+2]  ""; 06 i  i + 2; 07 } 08 elseif isNumStr(w[i],w[i+1]) { 09 w[i]  w[i] + "_" + w[i+1] + "_" + w[i+2]; 10 w[i+1]  ""; 11 i  i + 1; 12 } 13 } 14 for i  1 to n – 2 { 15 if isFracStr(w[i],w[i+1],w[i+2]) { 16 w[i]  w[i] + "_" + w[i+1] + "_" + w[i+2]; 17 w[i+1]  ""; 18 w[i+2]  ""; 19 i  i + 2; 20 } 21 } 22 outS  w[1]; - 155 - 23 for i  2 to n do { 24 if (w[i] != "") 25 outS  outS + " " + w[i]; 26 } Độ phức tạp thuật toán là O(n), với n là số âm tiết trong dãy vào. E2. Các thuật toán khử nhập nhằng tên riêng E2.1. Thuật toán nhận diện tên riêng, khử nhập nhằng từ tiền tố + Đầu vào là dãy âm tiết: S = a[1] a[2] a[3] .... a[i] ... a[n]. + Đầu ra outS có các tên riêng được nối nhau bằng dấu "_". 01 TenRieng  ""; 02 for i  1 to n { 03 if isProper(a[i]) { 04 if (TenRieng == "") { 05 TenRieng  a[i]; 06 id  i; 07 }else 08 TenRieng  TenRieng + "_" + a[i]; 09 }else { 10 if (TenRieng != "") { 11 a[id]  TenRieng; 12 if (a[id]  ListSpecialPN) { 13 v  SplitToArray(a[id],"_"); 14 if count(v) ≥ 2) && (v[1]  ListPrePN) { 15 a[id]  v[1] + " " + v[2]; /* tách */ 16 for j  3 to count(v) { 17 a[id]  a[id] + "_" + v[j]; 18 } 19 } 20 } 21 for j  id + 1 to i – 1 { 22 a[j]  ""; 23 } 24 TenRieng  ""; 25 } 26 } 27 } 28 if (TenRieng != "") { 29 a[id]  TenRieng; 30 if (a[id]  ListSpecialPN) { 31 v  SplitToArray(a[id],"_"); 32 if count(v) ≥ 2) && (v[1]  ListPrePN) { 33 a[id]  v[1] + " " + v[2]; /* tách */ 34 for j  3 to count(v) { - 156 - 35 a[id]  a[id] + "_" + v[j]; 36 } 37 } 38 } 39 for j  id + 1 to i – 1 { 40 a[j]  ""; 41 } 42 } 43 outS  a[1]; 44 for i  2 to n do { 45 if (a[i] != "") 46 outS  outS + " " + a[i]; 47 } c tạp của thuật toán này là O(n), n là số âm tiết trong dãy vào. E2 ]. w[m]. u tố. Độ phứ .2. Khử nhập nhằng tên riêng với từ hậu tố sau tách từ + Đầu vào, S ban đầu gồm n âm tiết: a[1], a[2], a[3],... a[n S đã qua tách từ (m đơn vị): w[1], w[2], w[3], ... , + Đầu ra: outS, sửa lỗi w[i], w[i+1] bị nhập nhằng tên riêng với từ hậ 01 for i = 1 to m – 1 { 02 ww  (w[i] & "_" & w[i+1]).replace("_"," "); 03 if WordToIndex(lower(ww),MinDFA) ≥ 0 { 04 w[i]  ww; w[i+1]  ""; 05 i  i + 1; 06 }else { 07 pw  SplitToArray(w[i],"_"); 08 ww  w[i+1].replace("_"," "); 09 jpos  0; 10 for j  1 to count(pw) { 11 ww  pw[count(pw)-j+1] + " " + ww; 12 if (WordToIndex(lower(ww),MinDFA) ≥ 0) { 13 jpos  j; 14 wpos  ww; 15 } 16 } 17 if (jpos > 0) { 18 w[i+1]  wpos.replace(" ","_"); 19 w[i]  pw[1]; 20 for j  2 to count(pw) – jpos { 21 w[i]  w[i] + "_" + pw[j]; 22 } 23 } 24 } 25 } - 157 - 26 outS  w[1]; 27 for i  2 to n do { 28 if (w[i] != "") 29 outS  outS + " " + w[i]; 30 } đó: + WordToIndex(w, MinDFA) = -1: từ w không có trong từ điển. ị. ộ phức t án [3], ... , w[m]. Trong + WordToIndex(w, MinDFA) ≥ 0: là mã của từ w trong từ điển. + SplitToArray(w,"_"): tách dãy w bởi dấu "_" ra mảng các đơn v Đ ạp của SplitToArray là O(1), của WordToIndex là O(1) (xem thuật to A4.4, Phụ lục A4). Vòng lặp ngoài cùng (dòng 01) duyệt số từ trong câu (m), trong đó, có hai vòng lặp con (dòng 10 và 20) không lồng nhau, mỗi vòng duyệt số âm tiết trong một từ (w[i]). Do vậy, thuật toán đã duyệt toàn bộ số âm tiết trong câu, nên độ phức tạp của thuật toán sẽ là O(n), với n là số âm tiết trong dãy vào. E2.3. Khử nhập nhằng tên riêng với từ hậu tố trước tách từ + Đầu vào, S ban đầu gồm n âm tiết: a[1], a[2], a[3],... a[n]. S đã qua thuật toán 3.3 (m đơn vị): w[1], w[2], w + Đầu ra: outS, sửa lỗi w[i], w[i+1] bị nhập nhằng tên riêng với từ hậu tố. 01 for i = 1 to m – 1 { 02 if ("_"  w[i]) { /* là tên riêng */ 03 swi  0; 04 if ("_"  w[i+1]) { 05 sw[1]  w[i+1]; swi  swi + 1; 06 if ("_"  w[i+2]) { 07 sw[2]  w[i+2]; swi  swi + 1; 08 if ("_"  w[i+3]) { 09 sw[3]  w[i+3]; swi  swi + 1; 10 } 11 } 12 } 13 if (swi > 0) { 14 pw  SplitToArray(w[i],"_"); 15 jpos  0; kpos  0; 16 w1  pw[count(pw)]; j  1; 17 Repeat 18 w2  sw[1]; k 1;  19 ww  w1 + " " + w2; 20 Repeat 21 if (WordToIndex(lower(ww),MinDFA) ≥ 0) { 22 kpos  k; jpos  j; 23 wpos  ww; prew  w1; 24 } 25 k  k + 1; 26 if (k <= swi) { - 158 - 27 w2  w2 + " " + sw[k]; 28 ww  w1 + " " + w2; 29 } 30 Until (k > swi) or (count(ww) > 4); 31 j  j + 1; 32 if (j <= count(pw)) 33 w1  pw[count(pw) - j + 1] + " " + w1; 34 Until (j > count(pw)) or (count(w1) > 3); 35 if (wpos != "") { 36 w[i+1]  wpos.Replace(" ", "_"); 37 for k  2 to kpos { 38 w[i+k]  ""; 39 } 40 if (count( ew) =pr = count(pw)) { 41 w[i]  ""; 42 }else { 43 w[i]  pw[1]; 44 for j  2 to count(pw) – jpos { 45 w[i]  w[i] + "_" + pw[j]; 46 } 47 } 48 i  i + kpos; 49 } 50 } 51 } 52 } 53 outS  w[1]; 54 for i  2 to n do { 55 if (w[i] != "") 56 outS  outS + " " + w[i]; 57 } rằng độ phức tạp của hàm SplitToArray là O(1), và độ phức tạp của hàm F. THUẬT TOÁN TÌM THAM SỐ HỌC TỐI ƯU F1. Thuật toán di truyền GA và cực đại hoá kỳ vọng EM ization): ố hợp lý cực đại M Ta biết WordToIndex đều là O(1) (xem thuật toán A4.4, Phụ lục A4). Vòng lặp ngoài cùng (dòng 01) duyệt số đơn vị âm tiết/tên riêng trong câu (m), trong đó, hai vòng lặp con lồng nhau (dòng 17 và 20) sử dụng tối đa 3x4=12 lần duyệt âm tiết khi có tên riêng và dãy hậu tố, và hai vòng lặp con (dòng 37 và 44) duyệt lại từ w[i] theo âm tiết. Vì vậy, thuật toán trên có độ phức tạp là O(n), với n là số âm tiết dãy vào. F1.1. Thuật toán cực đại kỳ vọng EM (Expectation Maxim EM là một thuật toán lặp rất tổng quát cho việc ước lượng tham s LE (Maximum-Likelihood Estimation) khi một số biến ngẫu nhiên có liên quan - 159 - thì không quan sát hoặc không đầy đủ. Sự hội tụ của thuật toán luôn phụ thuộc vào giá trị ban đầu (xem Hình F1.1). hội tụ của thuật toán EM đến một giá trị cực đạHình F1.1. Sự cục bộ (EM), - Ư F1.1). gọi là thuật toán di truyền GA, Hình F1.2. Lai ghép nhiễm sắc thể g ai cá thể cha mẹ để tạo ra con mới hép và đột biến. i khi vector tham số được khởi tạo một giá trị ngẫu nhiên ban đầu (0). u điểm: thuật toán thực hiện leo đồi và hội tụ nhanh. - Nhược điểm: điểm tối ưu thường là cực trị cục bộ (Hình F1.2. Thuật toán di truyền GA (Genetic Algorithm): Một thuật toán tìm kiếm heuristic thích nghi với tên được đưa ra dựa trên các ý tưởng tiến hóa của chọn lọc tự nhiên và di truyền dựa trên nhiễm sắc thể (chromosomes). Về cơ bản, một số tập tham số ngẫu nhiên được áp dụng cho một thuật toán và giá trị tối ưu được tính toán cho mỗi thuật toán. Các tập tốt nhất được pha trộn với nhau, sử dụng sự kết hợp với nhau của các phép chọn lọc (selection), lai ghép (crossover) và đột biến (mutate). Và các tập mới được áp dụng với thuật toán cho đến khi thu được giá trị tham số tối ưu. cha mẹ iữa h - Ưu điểm: thuật toán tìm được giá trị lân cận tối ưu toàn cục. - Nhược điểm: tốc độ hội tụ chậm vì thực hiện phép chọn, lai g 0,45 0,19 0,78 0,32 0,21 0,89 0,17 0,6 0,41 0,33 0,45 0,19 0,78 0,41 0,33 con - 160 - Hình F1.3. Sơ đồ giải thuật di truyền GA cơ bản F1.3. Thuật toán kết hợp GA-EM Giải thuật di truyền dựa trên học thuyết chọn lọc tự nhiên (học thuyết tiến hoá) và nó cho phép đạt được những điểm lân cận cực trị toàn cục. Tuy nhiên, nếu điểm xuất phát của quá trình tìm kiếm nằm trong vùng của cực trị toàn cục thì thuật toán EM lại cho phép đạt được kết quả tốt. Vì vậy, trong một số bài toán, có thể kết hợp thuật toán EM với giải thuật di truyền GA [146] để đạt được kết quả mong muốn. Thuật toán kết hợp GA-EM như sau: Bước 1. Khởi tạo tập ngẫu nhiên 0; Bước 2. Thực hiện EM với 0 cho đến khi nó hội tụ đến EM; Bước 3. Thực hiện GA để tìm GA sao cho: L(GA) ≥ L(EM); Bước 4. Thực hiện EM với GA cho đến khi nó hội tụ đến GAEM ; Bước 5. Nếu | EM. – GAEM | >  thì Đặt EM. = GAEM.; Quay lại Bước 3 ; Bước 6. Xuất GAEM Hình F1.4. Minh hoạ 1 bước lặp thực hiện thuật toán kết hợp GA-EM - 161 - F2. Thuật toán EM trên các đoạn con Tham số  có miền xác định là [L.. R], giả sử đồ thị hàm mục tiêu F theo tham số  có dạng như mô tả trong hình F2.1. Ý tưởng thực hiện: chia [L.. R] thành n đoạn con. Với mỗi đoạn con, thực hiện chọn ngẫu nhiên một giá trị tham số khởi tạo và sử dụng thuật toán EM để tìm điểm tối ưu. Như vậy, trên toàn bộ n đoạn con, có thể tìm được tham số tối ưu toàn cục dễ dàng hơn so với thuật toán kết hợp GA-EM. Hình F2.1. Minh hoạ phương pháp trung điểm tìm điểm tối ưu toàn cục Khi dùng phương pháp này để xác định tham số  mà cụ thể là P0, Png hay , thì hàm mục tiêu L() gồm 2 phần: o Phần 1: thực hiện tách từ bằng các độ đo thống kê có tham số ; o Phần 2: thực hiện đánh giá độ chính xác F1score: L() = F1score;