ỨNG DỤNG CỦA AUTOMATA HỮU HẠN TRONG VIỆC PHÂN TÍCH TỪ VỰNG MỞ RỘNG

Cách dùng otomat hữu hạn để mô tả một loạt các từ vựng là một kỹ thuật đã được khẳng định. Có thể ứng dụng mang tính truyền thống. Nó được tìm thấy trong cấu trúc lệnh nơi mà ôtômat có thể được sử dụng để làm mẫu và thực hiện những phân tích từ vựng học mang tính hiệu quả. Ứng dụng của ôtmat hữu hạn để giải quyết một vài vấn đề đặc biệt trong việc xử lý ngôn ngữ tự nhiên là khá phổ biến....
Nội dung trích xuất từ tài liệu:
ỨNG DỤNG CỦA AUTOMATA HỮU HẠN TRONG VIỆC PHÂN TÍCH TỪ VỰNG MỞ RỘNG BÀI TẬP LỚN: LÝ THUYẾT NGÔN NGỮ ỨNG DỤNG CỦA VĂN PHẠM VÀ AUTOMATA     THÀNH VIÊN NHÓM 4 CÙNG THỰC HIỆN: NGUYỄN NGỌC TÂM 1. NGUYỄN THỊ SEN 2. NGUYỄN THỊ SÁNG 3. NGUYỄN THỊ HỒNG THẮM 4. CÙNG SỰ HƯỚNG DẪN CỦA TH.s TRẦN XUÂN SANG GIÁO VIÊN CHUYÊN MÔN PHẦN I: ỨNG DỤNG CỦA AUTOMATA HỮU HẠN TRONG VIỆC PHÂN TÍCH TỪ VỰNG MỞ RỘNG Applic atio ns o f finite Auto mata Re pre s e nting larg e Vo c abularie s GIỚI THIỆU Cách dùng otomat hữu hạn để mô tả một loạt các từ vựng là một kỹ thuật đã được khẳng định. Có thể ứng dụng mang tính truyền thống. Nó được tìm thấy trong cấu trúc lệnh nơi mà ôtômat có thể được sử dụng để làm mẫu và thực hiện những phân tích từ vựng học mang tính hiệu quả. Ứng dụng của ôtmat hữu hạn để giải quyết một vài vấn đề đặc biệt trong việc xử lý ngôn ngữ tự nhiên là khá phổ biến. Tuy nhiên, ý tưởng gói gọn các “từ vựng mở rộng” vào otomat đơn định và nhiều ứng dụng của nó dường như còn mang tính mới mẻ. Cơ sở để thúc đẩy cho nghiên cứu này là một chương trình kiểm tra lỗi chính tả áp dụng cho hầu hết các ngôn ngữ. Cho ví dụ , chương trình kiểm tra chính tả mà chúng ta đề cập có thể xử lý khoảng 30.000 từ mỗi giây, với automat hơn 200.000 từ đặt vừa khít vào 124 kbytes bộ nhớ. Trong chủ đề này chúng ta sẽ bàn đến chi tiết những vấn đề sau: 1. Thực hiện kiểm tra chính tả dựa trên ôtmat 2. Mô tả thuật toán và cấu trúc dữ liệu được sử sụng 3. Một vài sự thống kê và đo lường 4. Một vài ứng dụng 1. Thực hiện kiểm tra chính tả dựa trên ôtmat Một trong những chương trình kiểm tra chính tả được sử dụng rộng rãi nhất là chương trình UNIX Spell. Chương trình này thực hiện kiểm tra bằng cách loạI bỏ từ được cho khỏi tiền tố của nó, cho ví dụ: Re- work –ed  work và over – tak- ing  take. Bằng cách sử dụng việc loại bỏ tiền tố, từ điển ban đầu khoảng 250.000 từ vựng đã giảm xuống còn 30.000 từ . Tuy nhiên, việc loại bỏ phụ tố( bao gồm tiền tố và hậu tố) có thể dẫn đến việc chấp nhận những từ không tồn tại. Thêm nữa, chương trình kiểm tra sẽ chấp nhận những từ không có nghĩa trong khi kiểm tra chính tả :womans thay vì woman’s( số nhiều của woman là women), tos thay vì toes( hoặc có thể là toss), và toing thay vì toeing( hoặc towing). Để có thê khắc phục những nhược điểm trên , chúng tôi đã quyết định thử một phương pháp khác bằng cách xây dựng một otomat hữu hạn đơn định cục bộ (aminimal acyclic deterministic partial finite automaton) có thể chấp nhận một cách chính xác khoảng 206.000 từ có mặt trong từ vựng. Theo cách này chúng ta có thể tránh được vấn đề đưa vào những từ không tồn tại. Bên cạnh đó Hình 1: Otomat đơn định cho tất cả các dạng của các động từ : re  work , replay, overwork và  overplay  Otomat có thể cung cấp một cách đơn giản và chung chung để loại bỏ một cách tuyệt đối các tiền tố và hậu tố vì mỗi trong số chúng sẽ được mô tả duy nhất một lần. Trong hình 1, chúng tôi chỉ ra một otomat cho tất cả các dạng của các động từ tiếng anh rework, replay, overwork and overplay. Chú ý rằng để bao gồm tất cả các dạng của động từ work, chỉ cần thêm duy nhất một chuyển (transition) được gán nhãn bởi chữ cái w từ trạng thái 0  9. 2. Cách thực hiện của automata Function BuildAutomaton(Vocabulary); Begin A  EmptyAutomaton; Repeat While A not full do Include the next word of Vocabulary in A; A minimal(A) Until no more words in vocabulary; Return A; End; Đây là thuật toán mô tả cách xây dựng otomat của ‘từ vựng’ mở rộng : i. Hai vòng lặp để tăng cường khả năng trong quá trình xử lý nhất là đối với loại ngôn ngữ chứa nhiều từ vựng. ii. Với thuật toán này thì tốc độ cũng như thời gian truy cập từ vựng phụ thuộc vào chiều dài của từ đang được tìm kiếm, mà không phụ thuộc vào kích cỡ của otomat. iii. Thuật toán tìm kiếm cho một từ là rất hiệu quả, bắt đầu từ trạng thái đầu tiên nó đi qua otomat bằng cách sử dụng các chữ cái liên tiếp nhau của từ đó để lựa chọn trạng thái chuyển, cho đến khi hoặc một trạng thái kết thúc được đưa ra hoặc không có sự chuyển nào tồn tại(hoặc từ đó thuộc từ vựng hay không) iiii. Từ vựng tiếng anh chứa khoảng 81.000 từ đã tạo ra automata với khoảng 30.000 trạng thái và 68.000 chuyển. Mỗi trạng thái có thể được mô tả bởi một cặp chuyển : một ký tự ( một byte) và một mục trạng thái ( hai bytes) ; một byte phụ cho mỗI trạng thái nắm dữ số lượng các chuyển có mặt. 3. Tìm hiểu một vài thống kế và đo lường Nhiều từ mới được thêm một cách đơn giản từ các từ vựng đã có trong otomat . .Điều này có thể làm otomat được thu nhỏ lại Cho ví dụ, nếu từ overplayed bị loại khỏi otomat trong hinh 1, otomat kết quả sẽ thực sự tăng từ 17 trạng thái và 22 chuyển tới 18 trạng thái và 25 chuyển.         Hình2: Otomat chấp nhận tất cả các từ có tối đa là b ...