Xem mẫu
- 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ốn ký tự
Trong trường hợp đặc biệt, chúng ta nên nhớ rằng, nếu
cho 26 ký tự alphabet, một từ vựng trong tất cả các dãy ký tự
có chiều dài tối đa M sẽ có (26M+1-1)/25 từ; cho ví dụ, cho
M=4, chúng ta sẽ có 475,225 từ. Mặt khác, otomat cho từ
vựng đó chỉ có 27M+1 chuyển đổi (109 đối với M=4; xem
hình 2)
- 4. Một vài ứng dụng
H ình 3: Cách đánh số của ôtômat
Chúng ta thừa nhận rằng, sự mô tả của otomat gồm một số
nguyên cái mà đưa ra số lượng của từ được chấp nhận bởi otomat
bắt đầu từ trạng thái đó. Chúng ta gọi otomat như vậy được gọi
là otomat được đánh số, kiểu như trong hình 4. chúng ta sẽ xây
dựng hai hàm liên quan giữa các số từ 1 tới L (L là số lượng các
từ được chấp nhận bởi ôtmat) và các từ như sau:
- được gọi là otomat được đánh số, kiểu như trong hình 4.
Chúng ta sẽ xây dựng hai hàm liên quan giữa các số từ 1 tới L
(L là số lượng các từ được chấp nhận bởi ôtmat) và các từ
như sau:
- 4.1 Từ điển đa ngôn ngữ
Otomat được đánh số có thể được sử dụng để thực hiện
từ điển đa ngôn ngữ cho việc chuyển đổi giữa từ và từ. Các
từ vựng đối với một vài ngôn ngữ có thể được mô tả bởi một
otomat với nhiều trạng thái khởi tạo. Một điều thú vị là, bằng
cách đảo ngược các từ trong khi xây dựng otomat, yêu cầu xử
lý sẽ tận dụng tối đa sự tồn tại trong việc kiểm tra sự tương
đương giữa các ngôn ngữ (tối ưu bộ nhớ), chẳng hạn như
các tiền tố và các từ gốc tồn tại trong nhiều ngôn ngữ Châu
Âu nói chung. Bên trong ottomat, đối với mỗi ngôn ngữ, chúng
ta có thể sử dụng một mảng được đánh số bởi các con số của
từ và vẽ chúng vào danh sách được định vị cho ngôn ngữ
khác.
- 4.2 Từ đồng nghĩa
Cho một từ 'word', các từ đồng nghĩa của nó bao gồm như
sau:
work:
noun: avocation, calling, employment, field, job, occupation,
proffesion, trade, vocation, chore, grind, sweet
verb: answer, do, fulfill, meetqualify, suffice
Về mặt phạm trù ngữ pháp, từ đó là thuộc về danh từ, động
từ…. Chúng ta có một chuỗi các danh sách các từ có liên quan,
với mỗi danh sách tương xứng với một cách hiểu khác nhau
của từ, nếu chúng ta đưa một từ bất kỳ nằm trong một danh
sách các từ có liên quan. Kết quả mà chúng ta sẽ nhận được
là danh sách các từ đồng nghĩa.
- Chúng ta thực hiện việc tìm từ đồng nghĩa này bằng
cách sử dụng một otomat được đánh số với nhiều trạng
thái khởi đầu : mỗi trạng thái phù hợp với một phạm trù
ngữ pháp. Bên cạnh đó, chúng ta sử dụng một vài các cấu
trúc dữ liệu để mô tả danh sách các từ theo tuần tự các con
số. Giả sử, sự thực hiện này được kiểm tra đối với các từ
đồng nghĩa tiếng Anh. Otomat của nó chấp nhận khoảng
9.500 từ , có tối thiểu 9.000 trạng thái và 18.000
chuyển.Yêu cầu lưu trữ là 88kbytes cho otomat và khoảng
39kbytes cho cấu trúc dữ liệu
- 5. Future work
Chúng ta có thể thấy rằng otomat đơn định cung cấp
một công cụ có ích cho nhiều ứng dụng. Một trong những
phương hướng mà họ theo đuổi trong tương lai là làm một
vài thử nghiệm trên các ngôn ngữ khác hơn so với tiếng Anh
và thử xây dựng Otomat cho từ vựng mở rộng hơn rất nhiều.
- PHẦN II:
AUTOMATA ĐẨY XUỐNG
nguon tai.lieu . vn
