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). Mời các bạn tham khảo! | 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 Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh 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] .
