Kỹ thuật tối ưu đa mục tiêu thiết kế bảng băm từ điển cho kiểm lỗi Tiếng Việt - Trần Ngọc Anh

Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh T. N. Anh, , Long, "Kü thuËt tèi ­u ®a môc tiªu kiÓm lçi tiÕng ViÖt." 76 Kü THUËT TèI ¦U §A MôC TI£U THIÕT KÕ B¶NG B¡M Tõ §IÓN CHO KIÓM LçI TIÕNG VIÖT TRẦN NGỌC ANH*, TRƯƠNG QUỐC HÙNG*, PHAN TUẤN ANH*, PHẠM HỒNG SƠN**, NGUYỄN LONG*. Tóm tắt: Bài toán thiết kế bảng băm cho từ điển âm tiết tiếng Việt phải giải quyết hai vấn đề có liên quan trong sự đối lập nhau, đó là kích thước bảng băm và khả năng đụng độ. Chúng tôi đưa ra cách giải quyết bài toán này nhằm cả hai mục tiêu là khả năng dụng độ và kích thước bảng băm cùng phải nhỏ. Kết quả thử nghiệm với các điểm tối ưu trên tập Pareto với kích thước bảng băm cỡ 1,11n (n là kích thước từ điển), độ phức tạp thời gian tìm kiếm trên bảng băm là O(1), cho thấy ưu điểm của thuật toán được đề xuất so với một số thuật toán khác như tìm kiếm nhị phân, automat hữu hạn đơn định hoặc phân tích dựa trên cấu trúc âm tiết tiếng Việt. Từ khoá: Tối ưu đa mục tiêu; Tập Pareto; Bảng băm tối ưu. 1. ĐẶT VẤN ĐỀ Bài toán kiểm lỗi âm tiết tiếng Việt là một trong những bài toán cơ bản nhất của xử lý ngôn ngữ tự nhiên tiếng Việt[3][4]. Hiện nay, đã có rất nhiều phương pháp tiếp cận khác nhau như: Tìm kiếm nhị phân dựa theo từ điển đã được sắp xếp[3][4]; Dùng các từ điển và hàm băm dạng Soundex, Editex, Phontex hỗ trợ sửa lỗi[4]; Dùng mảng cấu trúc âm tiết tiếng Việt[3][4]; Dùng cây từ điển ký tự: B-Tree hay cây hậu tố Suffix-Tree[4]; Dùng Automat hữu hạn đơn định, Automat tối thiểu[4]; Dùng mô hình thống kê n-grams ký tự[2][4]; Dùng bảng băm từ điển tối ưu[4]. Trong đó, dùng bảng băm từ điển tối ưu là hướng tiếp cận mới, sử dụng lời giải tối ưu đa mục tiêu cho thiết kế bảng băm. Cụ thể: mục tiêu 1 là tối thiểu hoá đụng độ, và mục tiêu 2 là tối thiểu hoá kích thước bảng băm[14]. Rõ ràng hai mục tiêu này mâu thuẫn loại trừ lẫn nhau. Trên cơ sở nghiên cứu về bộ mã ký tự Việt[4], về bảng băm từ điển âm tiết[4], về thống kê âm tiết tiếng Việt[1] và phương pháp tìm lời giải tối ưu đa mục tiêu[7][10][12], để tìm ra các tham số thiết kế tối ưu cho bảng băm từ điển. Với cách tiếp cận đó, bài báo được trình bày tiếp tục theo thứ tự sau: Tách âm tiết tiếng Việt bằng Automat hữu hạn; Xây dựng các hàm mục tiêu cho thiết kế bảng băm từ điển âm tiết; Tìm tập Pareto thiết kế bảng băm tối ưu; Thử nghiệm đánh giá; cuối cùng là phần kết luận. 2. VẤN ĐỀ TÁCH ÂM TIẾT TRONG VĂN BẢN Bước đầu tiên trước khi thực hiện kiểm tra âm tiết tiếng Việt là cần phải tách được từng âm tiết trong văn bản. Để thực hiện tách âm tiết tiếng Việt, có thể dùng Automat hữu hạn tiền định DFA (Deterministc Finite Automata) được mô tả như hình 1. DFA có 2 trạng thái q0 và q1, trong đó trạng thái bắt đầu q0 cũng là trạng thái kết thúc. Với  là bảng chữ cái chấp nhận được (tiếng Việt). Ban đầu thẻ từ Token =  (rỗng), trạng thái xuất phát q0, DFA sẽ đọc từng ký tự a để chuyển trạng thái. Tại trạng thái q1, dãy ký tự đọc vào sẽ đưa vào thẻ từ Token. Nếu trạng thái mới trở lại q0 mà thẻ từ Token   thì xuất Token rồi gán lại thẻ từ Token = . Cứ như vậy, DFA sẽ tách được toàn bộ các âm tiết trong văn bản tiếng Việt. Bảng chữ cái chấp nhận được (tiếng Việt)  gồm: 17 chữ cái phụ âm (b c d đ g h k l m n p q r s t v x) và 12 chữ cái nguyên âm (a ă â e ê i o ô ơ u ư y). Mỗi chữ cái nguyên âm có thể kết hợp với 6 thanh (ngang, huyền, hỏi, ngã, sắc, nặng), nên số chữ cái nguyên âm có dấu thanh là 126 = 72. Do vậy, tổng số ký tự Việt là 17+72 = 89. Nghiªn cøu khoa häc c«ng nghÖ T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 30, 04 - 2014 77 Hình 1. Automat hữu hạn tiền định (DFA) tách âm tiết. Thuật toán minh hoạ DFA tách âm tiết: (* trạng thái bắt đầu q0 *) 1) Token  ’’; 2) Repeat a) i  0; b) SizeRealBuffer  ReadFile(File, Buffer); c) While (i < SizeRealBuffer) Do c1) If Buffer[i]  AlphabetTable Then (* chuyển sang trạng thái q1 *) c1t) Token  Token + Buffer[i] Else (* chuyển sang trạng thái q0 *) c1f) If Token  ’’ Then (*Kiểm tra thẻ từ Token, ví dụ:*) c1f1) (*If SyllableCheck(Token) Then *) (*-----------------------------*) c1f2) Token  ’’; (*sau khi xử lý*) c2) i  i + 1; Until SizeRealBuffer = 0; (*kết thúc tệp văn bản*) 3) If token  ’’ Then (*Kiểm tra thẻ từ Token sau cùng*) (* If SyllableCheck(Token) Then *) 3. XÂY DỰNG CÁC HÀM MỤC TIÊU THIẾT KẾ BẢNG BĂM TỪ ĐIỂN 3.1. Bảng băm và hàm băm Bảng băm T (hash table) là một mảng có kích thước M. Hàm băm h là một ánh xạ từ tập khoá K sang tập chỉ số i của bảng băm: h: K i, 0  i  M-1. Phần tử của bảng băm: T[i] (hình 2). Ở đây, tập khoá chính là từ điển âm tiết tiếng Việt. Mỗi âm tiết (syllable) là một chuỗi ký tự Việt, ứng với một khoá K. Ta biết rằng, mỗi ký tự Việt tương ứng với một mã của nó. (Chẳng hạn, chúng ta sử dụng ký tự Việt theo bảng mã Unicode TCVN 6909:2001). Như vậy, mỗi âm tiết w có thể tương ứng với một khoá K theo cách tính: Kw = m1a n-1 + m2a n-2 + ... + mna 0 , trong đó, n là độ dài của chuỗi âm tiết; m1, m2,..., mn là các mã tương ứng của từng ký tự trong chuỗi âm tiết; a là cơ số  |  | = 89 (là kích thước bảng chữ cái), a có thể được chọn khảo sát trong khoảng từ 89 đến 255. Từ đó, ta có hàm băm tương ứng cho âm tiết w như sau: h(w) = (m1a n-1 + m2a n-2 + ... + mna 0) mod M. (1) Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh T. N. Anh, , Long, "Kü thuËt tèi ­u ®a môc tiªu kiÓm lçi tiÕng ViÖt." 78 Hình 2. Mô tả bảng băm và hàm băm. 3.2. Khả năng đụng độ Trường hợp w1  w2 và h(w1)  h(w2): không xảy ra đụng độ. Trường hợp w1  w2 và h(w1) = h(w2): xảy ra đụng độ. Trong thực tế khi thiết kế bảng băm, nếu không tính toán cẩn thận sẽ gặp phải khá nhiều đụng độ, điều đó làm tăng thời gian tìm kiếm. Để ước lượng thời gian tìm kiếm, có thể mô tả cấu trúc bảng băm như sau: Giả sử bảng băm T sử dụng phương pháp kết nối trực tiếp như hình 3. Hình 3. Mô tả bảng băm T theo phương pháp kết nối trực tiếp. Khi thêm một phần tử vào bảng băm mà xảy ra đụng độ, có nghĩa là danh sách kết nối tăng thêm một phần tử. Như vậy, có thể tính được tổng số đụng độ cho toàn bộ bảng băm khi các danh sách liên kết có kích thước lớn hơn 1. Cũng có thể nói một cách khác, đụng độ chính là chi phí thời gian tìm kiếm một từ khoá trong bảng băm. Với bảng băm T bằng phương pháp kết nối trực tiếp (hình 3), ta gọi T[k].count là kích thước danh sách liên kết của phần tử thứ k của bảng băm T, khi đó, D[k] là số khả năng đụng độ tại phần tử thứ k của bảng băm T, được xác định:       1].[0 1].[1].[ ][ countkTkhi countkTkhicountkT kD , (2) khả năng đụng độ cực đại của bảng băm T là: ]}[{max 10 max kDD Mk   , (3) tổng khả năng đụng độ của toàn bộ bảng băm T là:     1 0 ][ M k dic kDD . (4) Xét văn bản huấn luyện thực tế, mỗi từ wi trong danh sách đụng độ là D[k] sắp xếp tần suất xuất hiện là fw[i] giảm dần, tương ứng với xác suất xuất hiện là pw[i] giảm dần. Do vậy, tổng khả năng đụng độ theo thống kê âm tiết sẽ là:      1 0 ][ 1 ][ M k kD i wfre ipiD , (5) Nghiªn cøu khoa häc c«ng nghÖ T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 30, 04 - 2014 79 trong đó, 1][ 1 0 ][ 0     M k kD i w ip (tổng toàn bộ xác suất của bảng băm). 3.3. Không gian bài toán Như vậy, bài toán thiết kế bảng băm tối ưu với 2 mục tiêu (xung đột[9]) cụ thể: - Tối thiểu hoá kích thước bảng băm: fM = M  min - Tối thiểu hoá thời gian tìm kiếm: fD = Ddic (hoặc Dfreq)  min * Không gian quyết định (hình 4a). Qua thống kê từ điển tiếng Việt[11], chúng tôi xác định được từ điển có chứa 6950 âm tiết tiếng Việt khác nhau. Do vậy, ta có các tham số sau: + Từ điển N = 6950 âm tiết + Cơ số a: 89  a  255 (mã ký tự Việt) + Giới hạn bảng băm: ta chọn kích thước bảng băm để khảo sát trong vùng lân cận trên so với kích thước từ điển. Có thể khảo sát M trong khoảng: N  M  3N(6950  M  20850). * Không gian mục tiêu (hình 4b): {(fD, fM)}. 3.4. Kiểm tra âm tiết tiếng Việt dựa vào bảng băm Với bảng băm T và hàm băm h(w), ta có thuật toán kiểm lỗi chính tả âm tiết sau: Function SyllableCheck(w: string): Boolean; 1) List  T[h(w)]; 2) i  0; 3) Repeat i  i + 1; Until (List[i] = w) or (i = List.Count); 4) Return (List[i] = w); Trong thuật toán này, List là danh sách chứa các âm tiết có cùng địa chỉ băm, và List.count chính là khả năng đụng độ theo công thức (2). Do vậy, độ phức tạp của thuật toán này là O(Dmax). Tốc độ tìm kiếm không chỉ phụ thuộc Dmax, mà còn phụ thuộc hệ số tải  = N/M của bảng băm, thường người ta chọn   0.9, tức là kích thước bảng băm thường chọn lớn hơn N/ số phần tử cần được lưu trữ. (Với từ điển tiếng Việt có N = 6950 âm tiết, ta chọn M  Mmin = 6950/0.9  7722). 4. TÌM TẬP PARETO THIẾT KÊ BẢNG BĂM TỐI ƯU Trong bài toán tối ưu đa mục tiêu, kết quả cần đạt được là một tập giải pháp xấp xỉ để người ra quyết định lựa chọn phương án phù hợp, tập xấp xỉ này được gọi là tập tối ưu đa mục tiêu. Tập này thường được lựa chọn theo phương pháp tối ưu Pareto. Hình 4. Không gian bài toán fD fM a fM a) b) Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh T. N. Anh, , Long, "Kü thuËt tèi ­u ®a môc tiªu kiÓm lçi tiÕng ViÖt." 80 Hình 5. Minh hoạ tập Pareto của miền mục tiêu (f1, f2)  min. Một tập hợp điểm được gọi là tập tối ưu Pareto (hình 5) nếu di chuyển từ một điểm (ví dụ điểm A) đến một điểm khác (điểm B) trong tập, bất kỳ cải thiện nào trong các hàm mục tiêu từ giá trị hiện tại sẽ làm ít nhất một giá trị của một hàm mục tiêu khác kém đi so với giá trị hiện tại[9]. Theo định nghĩa này, điểm C không phải là điểm tối ưu Pareto. Điểm C là không thuộc Pareto vì nó bị trội bởi cả hai điểm A và điểm B. Điểm A và B hoàn toàn không bị trội bởi bất kỳ điểm nào khác, vì thế, chúng nằm trên đường cong Pareto. Cùng vì thế, tập Pareto còn được gọi là tập các điểm không bị trội. Một trong những phương pháp giải bài toán tối ưu đa mục tiêu, đó là phương pháp - Contraint. Theo phương pháp này, chỉ những mục tiêu nào được tối ưu trong khi các mục tiêu khác được chuyển hoá thành các ràng buộc của mục tiêu đã lựa chọn. Khi đó, bài toán tối ưu k mục tiêu (k ≥ 2) được mô tả: min ( ) / ( )jf x x D   (6) sao cho, )(xf j  ≤ với i =1, 2, ..., k; i  j và D  Rn. Trong phương pháp vector được xác định và sử dụng biên (biên trên trong trường hợp cực tiểu) cho tất cả các mục tiêu i. Để đưa ra vector , phương pháp này sẽ tìm một giải pháp tối ưu qua việc tối ưu mục tiêu j. Bằng việc thay đổi sẽ đạt được một tập tối ưu. Trong thực nghiệm chúng tôi áp dụng phương pháp -Contraint để thiết kế bảng băm tối ưu dựa trên 2 yếu tố: tối thiểu hoá đụng độ (Ddic  min, hoặc Dfreq  min) và tối thiểu hoá kích thước bộ nhớ (M  min). Vì đây là hai mục tiêu xung đột với nhau, do vậy, đây là dạng bài toán tối ưu đa mục tiêu [9]. Có thể giải quyết một cách đơn giản bằng cách tìm các tham số tối ưu theo thứ tự: Tìm tập các giá trị tối ưu về khả năng đụng độ trước, sau đó tìm tập các giá trị tối ưu về kích thước bộ nhớ, đó cũng là tập Pareto [7], [13] cần tìm. Trong một số trường hợp, có thể kết hợp phương pháp tương tác để định hướng vào vùng kết quả trong không gian mục tiêu [12]. Phương pháp -Contraint được xây dựng theo các bước sau: + Bước 1: Với mỗi fM → Tìm min fD → Kết quả: fM, min fD. + Bước 2: Sắp xếp min fD, fM giảm dần theo min fD, rồi đến fM. + Bước 3: Với mỗi min fD chỉ giữ lại min fM → Tập tối ưu Pareto. Trên cơ sở đó, với mỗi từ điển âm tiết tiếng Việt được sắp xếp theo alphabet (Ddic) hay tần suất (Dfreq), ta có các thuật toán sau: Thuật toán 1: Tìm tập thiết kế tối ưu cho bảng băm với (Ddic, M)  min B1) Tìm tập Ddic  min theo M: For M  Mmin To Mmax 1) minDmax  DIC.count; 2) minDdic  DIC.count; 3) For a  amin To amax a) For i  0 To M - 1 Nghiªn cøu khoa häc c«ng nghÖ T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 30, 04 - 2014 81 a1) T[i]  ; b) For i  0 To DIC.count – 1 b1) w  DIC[i]; b2) T[h(w)]  T[h(w)]  {w}; c) Dmax  0; d) Ddic  0; e) For i  0 To M – 1 e1) If (T[i].count - 1 > Dmax) Then e1t) Dmax  T[i].count - 1; e2) If (T[i].count > 1) Then e2t) Ddic  Ddic + T[i].count - 1; f) If (minDdic = Ddic) and (minDmax > Dmax) Then ft1) aopt  a; ft2) minDmax  Dmax; Else If (minDdic > Ddic) Then ff1) aopt  a; ff2) minDmax  Dmax; ff3) minDdic  Ddic; 4) List[M-Mmin].Mopt  M; 5) List[M-Mmin].aopt  aopt; 6) List[M-Mmin].Dmax  minDmax; 7) List[M-Mmin].Ddic  minDdic; B2) Tìm tập M  min theo Ddic (tìm tập Pareto) 1) Sắp xếp List theo Ddic tăng dần; 2) Mỗi Ddic chỉ giữ lại một phần tử có Mopt = min; 3) i  0; //Loại bỏ tiếp các điểm bị trội. 4) While (i < List.Count - 1) a) k  i; b) minM = List[k].Mopt; c) For j  i + 1 To List.Count - 1 c1) If (List[j].Mopt < minM) Then i) k  j; ii) minM  List[j].Mopt; d) If (k > i) Then d1) j  i; d2) d  i; d3) while (d < k) i) List.RemoveAt(j);//Loại bỏ phần tử ii) d  d + 1; e) i  i + 1; Trong thực tế, có nhiều âm tiết xuất hiện với tần số cao [1], nếu chúng rơi vào những địa chỉ có khả năng đụng độ cao sẽ ảnh hưởng trực tiếp đến thời gian kiểm lỗi cho toàn văn bản. Chính vì vậy, có thể cải thiện thời gian thực hiện thông qua việc khảo sát với các văn bản tiếng Việt thực tế, thống kê âm tiết. Từ điển freqDIC với các âm tiết được sắp xếp giảm dần theo tần suất xuất hiện của chúng. Thuật toán 2: Tìm tập thiết kế tối ưu cho bảng băm với (Dfreq, M)  min //Từ điển FreqDIC được sắp xếp giảm dần theo tần suất. B1) Tìm tập Dfreq  min theo M: For M  Mmin To Mmax 1) minDmax  freqDIC.count; 2) minDfreq  freqDIC.count; 3) fmax  f[0]; (*f[i]: tần suất của âm tiết freqDIC[i]*) 4) For a  amin To amax Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh T. N. Anh, , Long, "Kü thuËt tèi ­u ®a môc tiªu kiÓm lçi tiÕng ViÖt." 82 a) For i  0 To M – 1 a1) T[i]  ; b) For i  0 To freqDIC.count – 1 b1) w  freqDIC[i]; (* chèn vào cuối T[h(w)] *) b2) T[h(w)]  T[h(w)]  {w,f[i]/fmax}; c) Dmax  0; d) Dfreq  0; e) For i  0 To M – 1 e1) If T[i].count - 1 > Dmax Then e1t) Dmax  T[i].count - 1; e2) If T[i].count > 1 Then e2t) For k = 1 To T[i].count – 1 i) Dfreq  Dfreq + k*T[i].Item[k].p; f) If (minDfreq = Dfreq) and (minDmax > Dmax) Then ft1) aopt  a; ft2) minDmax  Dmax; Else If minDfreq > Dfreq Then ff1) aopt  a; ff2) minDmax  Dmax; ff3) minDfreq  Dfreq; 4) List[M-Mmin].Mopt  M; 5) List[M-Mmin].aopt  aopt; 6) List[M-Mmin].Dmax  minDmax; 7) List[M-Mmin].Dfreq  minDfreq; B2) Tìm tập M  min theo Dfreq: Tương tự B2 ở thuật toán 1. (Ddic được thay bằng Dfreq trong phần này) Với các văn bản thực tế đủ lớn, đủ bao trùm nhiều lĩnh vực khác nhau của tiếng Việt, qua thống kê theo âm tiết để tính tần suất xuất hiện của chúng. Đối với các từ xuất hiện với tần suất rất cao, nếu rơi vào danh sách đụng độ cao sẽ ảnh hưởng đến thời gian tìm kiếm. Nếu những từ này đứng ở đầu danh sách đụng độ, thì vấn đề có thể xem như đã được giải quyết. Do đó, nếu từ điển được sắp xếp trước theo tần suất giảm dần thì thuật toán 2 sẽ tìm được kết quả có ý nghĩa thực tế hơn thuật toán 1. Với các tập kết quả tìm được qua 2 thuật toán, các tập tối ưu Pareto, ta có thể chọn một số điểm để thử nghiệm khảo sát đánh giá. 5. THỬ NGHIỆM ĐÁNH GIÁ 5.1. Tập tối ưu cho thiết kế bảng băm kiểm tra âm tiết tiếng Việt Các tham số cho thuật toán 1 và 2 (mục 4) như sau: từ điển 6950 âm tiết; hệ số a: 89  a  255; khoảng khảo sát bảng băm: 6950  M  20850. Các tập tối ưu pareto tìm được theo các thuật toán, biểu diễn ở dạng đồ thị dưới dây. a) Tập Pareto (Ddic min,M min) b) Tập Pareto (Dfreq min,M min) Hình 6. Các tập tối ưu Pareto Nghiªn cøu khoa häc c«ng nghÖ T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 30, 04 - 2014 83 a) Tập cục bộ (Dsummin, Mmin) b) Tập cục bộ (Dfreqmin, Mmin) Hình 7. Các tập tối ưu cục bộ Dmax min 5.2. Thử nghiệm và đánh giá bảng băm từ điển tối ưu 5.2.1. Lựa chọn thiết kế tối ưu tiêu biểu cho bảng băm Như đã phân tích, độ phức tạp của thuật toán kiểm lỗi âm tiết bằng bảng băm chính là khả năng đụng độ O(Dmax). Theo hình 7.a và 7b thì {Dmax} = {3..6}, tức là O(Dmax) = O(1). Về toàn cục, ta phải lựa chọn Ddic/Dtext min và M min. Với kích thước từ điển n = 6950 âm tiết, ta thấy với: n  M  3n thì O(M) = O(n). Các hình 6a và 6b minh hoạ các tập tối ưu Pareto. Chọn điểm tối ưu đầu tiên cho mỗi trường hợp, gần nhau và ở lân cận của Mmin = N/  7722 để khảo sát (bảng 1). Bảng 1. Chọn điểm tối ưu tiêu biểu đầu tiên ở lân cận của Mmin. Chọn điểm đầu tiên Mopt aopt Dmax Dopt Ddic min (hình 6a) 7713 239 4 2177 Dfreq min (hình 6b) 7735 163 4 2.528 Thực hiện thử nghiệm kiểm lỗi âm tiết với 3 trường hợp sau:  Thử nghiệm TN1: Bảng băm tối ưu: Mopt = 7713, Dopt = 2177 (Dopt = Ddic). Xây dựng bảng băm này với từ điển âm tiết được sắp xếp theo alphabet.  Thử nghiệm TN2: Bảng băm tối ưu: Mopt = 7713, Dopt = 2177. Xây dựng bảng băm này với từ điển âm tiết được sắp xếp theo tần suất giảm dần.  Thử nghiệm TN3: Bảng băm tối ưu: Mop t= 7735, Dopt = 2.528 (Dopt = Dfreq). Xây dựng bảng băm với từ điển âm tiết được sắp xếp theo tần suất giảm dần. Bộ chương trình kiểm lỗi âm tiết tiếng Việt trên file văn bản, thiết kế hàm SyllableCheck trên cơ sở bảng băm và hàm băm. Ngoài ra, dùng các thuật toán khác như: tìm kiếm nhị phân [1], cấu trúc âm tiết [1], Automat hữu hạn [1], [9], [5] để so sánh. Nếu âm tiết hợp lệ, hàm SyllableCheck sẽ trả về TRUE, ngược lại là FALSE. Các thử nghiệm chạy trên Laptop Lenovo-3000-Y410, Intel Core2Duo CPU T5750 @2.0GHz (2CPU), 3GB RAM, 160GB HDD, hệ điều hành Windows XP SP2. Ngữ liệu văn bản tiếng Việt dùng cho thử nghiệm là kho ngữ liệu VietTreeBank với gần 2 triệu âm tiết, có kích thước cỡ 10MB. Cứ kiểm 10.000 âm tiết sẽ ghi nhận thời gian một lần để khảo sát. Chạy 10-15 lần, lấy 5 lần thử tốt nhất, rồi tính trung bình để so sánh ba thử nghiệm TN1, TN2 và TN3. 5.2.2. Kết quả thử nghiệm kiểm lỗi âm tiết tiếng Việt với điểm tối ưu đầu tiên Kết quả thử nghiệm được trình bày trong bảng 2. Từ bảng 2, ta thấy thời gian chạy các thử nghiệm: T1 < T2 < T3. Như vậy, cả về lý luận (đã phân tích ở mục 3.2) lẫn thực nghiệm đều chứng tỏ việc thiết kế bảng băm tối ưu khi sử dụng từ điển được sắp xếp giảm dần theo tần suất thống kê âm tiết sẽ cho kết quả tốt hơn (thời gian chạy ngắn hơn). Tức là các âm tiết có tần suất cao được ưu tiên sinh khoá trước, các âm tiết có tần suất thấp được sinh khoá sau. Các phần tử đụng độ của bảng băm này chủ yếu chứa các âm tiết có tần suất thấp, làm cho việc tìm kiếm thực tế trở nên nhanh hơn. Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh T. N. Anh, , Long, "Kü thuËt tèi ­u ®a môc tiªu kiÓm lçi tiÕng ViÖt." 84 Bảng 2. So sánh thời gian chạy trung bình với các thử nghiệm. Lần thử Thử nghiệm TN1 Thử nghiệm TN2 Thử nghiệm TN3 T1(giây) T2(giây) T3(giây) 1 4,015 3,922 3,719 2 4,078 3,953 3,766 3 4,016 3,937 3,750 4 4,016 3,953 3,812 5 4,047 3,922 3,787 TB 4,034 3,937 3,766 5.2.3. So sánh thời gian thực hiện với một số thuật toán khác Thử nghiệm kiểm lỗi âm tiết tiếng Việt bằng tìm kiếm nhị phân (TKNP)[1], cấu trúc âm tiết (CTÂT)[1] và Automat hữu hạn đơn định DFA (Deterministic Finite Automat) [1], [9], [5] để so sánh thời gian chạy với bảng băm tối ưu đã nêu. Bảng 3. So sánh thời gian chạy của các thuật toán khác nhau. Lần thử TKNP CTÂT DFA TN1 TN2 TN3 TB (giây) TC (giây) TA (giây) T1 (giây) T2 (giây) T3 (giây) 1 9,906 7,406 5,360 4,015 3,922 3,719 2 9,953 7,313 5,359 4,078 3,953 3,766 3 9,891 7,437 5,422 4,016 3,937 3,750 4 9,907 7,391 5,407 4,016 3,953 3,812 5 9,937 7,391 5,391 4,047 3,922 3,781 TB 9,919 7,388 5,388 4,034 3,937 3,766 Kết quả thử nghiệm với các thuật toán (tìm kiếm nhị phân, luật cấu tạo âm tiết, và Automat hữu hạn đơn định) cho thấy: bảng băm được thiết kế với tham số tối ưu đầu tiên của tập tối ưu Pareto (hình 6) trong các trường hợp có và không có sử dụng thống kê âm tiết, đều cho kết quả thực nghiệm tốt hơn về thời gian chạy, trong đó bảng băm tối ưu theo thống kê âm tiết là hiệu quả nhất. Các điểm tối ưu còn lại (ở bên phải) trên đường cong Pareto (hình 6a, 6b) hiển nhiên cho kết quả tốt hơn nữa về thời gian chạy. 6. KẾT LUẬN Tối ưu đa mục tiêu là hướng tiếp cận mới trong thiết kế bảng băm từ điển. Qua thử nghiệm với các điểm tối ưu trên tập Pareto với kích thước bảng băm xấp xỉ từ điển, M ≈ 1,11n (n là kích thước từ điển âm tiết), độ phức tạp thời gian là O(1), cho thấy, thời gian kiểm lỗi âm tiết tiếng Việt bằng bảng băm này nhanh hơn các thuật toán khác như: tìm kiếm nhị phân, cấu tạo âm tiết, automat hữu hạn đơn định. Kết quả nghiên cứu này rất có ý nghĩa và giá trị cho hướng nghiên cứu về xử lý ngôn ngữ tiếng Việt. TÀI LIỆU THAM KHẢO [1]. Anh Nguyễn Lê, Lai Trần Duy, Long Phạm Thế, Xuất Nguyễn Văn, “Giáo trình Lý Thuyết Mã nén”, NXB. Học Viện KTQS, 2001. [2]. Anh Trần Ngọc, Tĩnh Đào Thanh, “Kỹ thuật mã hoá âm tiết tiếng Việt và các mô hình n- grams ứng dụng kiểm lỗi cách dùng từ và cụm từ tiếng Việt”, Tạp chí CNTT & TT, Tập V-1, Số 6 (26), 9/2011. Hình 8. Đồ thị so sánh thời gian chạy của các thuật toán khác nhau. giây NAT Nghiªn cøu khoa häc c«ng nghÖ T¹p chÝ Nghiªn cøu KH&CN Qu©n sù, Sè 30, 04 - 2014 85 [3]. Anh Trần Ngọc, Tĩnh Đào Thanh, "Về bài toán kiểm lỗi chính tả tiếng Việt trên máy tính", Tạp chí Khoa học và Kỹ thuật, HVKTQS, số 116, 2006, tr.29-40. [4]. Anh Trần Ngọc, “Kỹ thuật mã hoá từ tiếng Việt và ứng dụng kiểm lỗi chính tả từ - cụm từ trong văn bản”, Luận văn thạc sĩ CNTT, Học viện KTQS, Hà Nội, 2007. [5]. Clifford A. Shaffer, “A Practical Introduction to Data Structures and Algorithm Analysis”, 3rd Edition (C++ Version), Book, 2010. [6]. Daciuk J. Mihov S. Watson B.W. Watson R.E., “Incremental Construction of Minimal Acycle Finite-State Automata”, Book, 2000. [7]. Eckart Zitzler, Marco Laumanns and Stefan Bleuler, “A Tutorial on Evolutionary Multiobjective Optimization”, Book, 2004. [8]. Gilles Brassard, Paul Bratley, “Algorithmics: Theory and Practice”, Book, 1988. [9]. Huyen N.T.M., Luong V.X., Phuong L.H. (2003), "Tách từ bằng từ điển và gán nhãn từ loại bằng xác suất", In Kỷ yếu hội thảo quốc gia ICT.RDA, 2003. [10]. Lam T. Bui and Sameer Alam, “Multi-Objective Optimization in Computation Intelligence: Theory and Practice”, Information Science Reference. IGI Global, 5, 2008. [11]. Linh Hoàng Thị Tuyền, Lương Vũ Xuân, Thuỷ Phạm Thị, Thu Đào Thị Minh, Hoà Đặng Thanh, [Phê Hoàng], “Từ điển Tiếng Việt”, Book, 2011. [12]. Long Nguyen, and Lam Thu Bui, "A multi-point interactive method for multi-objective evolutionary algorithms". In Proceeding of International Conference on Knowledge Systems Engineering, IEEE Computer Society, CPS, 2012, pages 107–112. [13]. Shan Y., Ang Y., and Bui L.T., “Success in Evolutionary Computation”, Studies in Computational Intelligence. 2008. [14]. Thomas H.C., Charles E.L., Ronald L.R., Clifford S., Introduction to Algorithms, Third Edition, The MIT Press, 2009. ABSTRACT MULTI-OBJECTIVE OPTIMIZATION TECHNIQUES TO DESIGNHASH TABLES OF DICTIONARY FOR VIETNAMESE SPELL CHECKING To design a hash table for a dictionary of Vietnamese syllables, it is neccesary to solve both issues that relate in opposition each to other: size of hash table and hash collisions. In this paper the method to resolve this problem for both objectives: size of hash table and hash collisions, which should be optimality smaller, is proposed. The test results with some optimal points on the Pareto set, size of hash table 1.11n (n is the size of the dictionary) and the time complexity of searching the hash table O(1) shows that the advantages of the proposed algorithms are better than that of others as binary search, deterministic finite automata, or analysis based on Vietnamese syllable structure. Keywords: Multi-objects optimazation; Pareto set; Optimal hash table. Nhận bài ngày 15 tháng 02 năm 2014 Hoàn thiện ngày 10 tháng 03 năm 2014 Chấp nhận đăng ngày 20 tháng 03 năm 2014 Địa chỉ: * Học viện Kỹ thuật Quân sự; ** Trường Sĩ quan Tăng - Thiết giáp.