TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN CÔNG NGHỆ TRI THỨC
^
]NGUYỄN LƯU THÙY NGÂN - 9912621
ĐỖ XUÂN QUANG - 9912652 XÂY DỰNG CHƯƠNG TRÌNH
CHUYỂN ĐỔI CÂY CÚ PHÁP TRONG
HỆ DỊCH TỰ ĐỘNG ANH - VIỆT
LUẬN VĂN CỬ NHÂN TIN HỌC
GIÁO VIÊN HƯỚNG DẪN
TS. ĐINH ĐIỀN
Lời đầu tiên chúng em xin chân thành cảm ơn thầy Đinh
Điền, người đã trực tiếp hướng dẫn chúng em hoàn thành luận văn
này. Thầy là người đã truyền thụ cho chúng em rất nhiều kiến thức
về tin học và ngôn ngữ học, giúp chúng em có được hiểu biết sâu
hơn về một trong các ứng dụng có ý nghĩa vô cùng to lớn trong
cuộc sống của tin học – vấn đề dịch máy.
Chúng em cũng xin chân thành cảm ơn các thầy cô trong
khoa Công nghệ thông tin đã tận tình chỉ bảo và giúp đỡ cho
chúng em trong suốt thời gian chúng em học đại học và trong quá
trình chúng em thực hiện luận văn.
Chúng con xin chân thành cảm ơn ba mẹ, các anh và những
người thân trong gia đình đã nuôi dạy, tạo mọi điều kiện tốt nhất
cho chúng con học tập và động viên chúng con trong thời gian
thực hiện luận văn.
Và cuối cùng, chúng tôi xin gởi lời cảm ơn đến tất cả bạn bè
và nhất là các bạn trong nhóm VCL (Vietnamese Computational
Linguistics), những người đã hỗ trợ chúng tôi trong quá trình
chúng tôi hoàn thiện luận văn này.
Tp. Hồ Chí Minh, tháng 07 năm 2003
Nguyễn Lưu Thùy Ngân - 9912621
Đỗ Xuân Quang - 9912652 Luận văn tốt nghiệp
Trang 3N
Á
O
OV
V
I
I
Ê
Ê
N
NH
H
Ư
Ư
Ớ
Ớ
N
N
G
GD
D
Ẫ
N
H
H
Ậ
Ậ
N
NX
X
É
É
T
TC
C
Ủ
Ủ
A
AG
G
I
I
Á
Ệ
N
N
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Tp. Hồ Chí Minh, tháng 07 năm 2003
Giáo viên phản biện
Luận văn tốt nghiệp
Trang 5
L
L
ờ
ờ
i
i
pháp đảm nhiệm việc thay đổi trật tự, chèn, xoá các thành phần trong cây cú pháp
của câu tiếng Anh sao cho sau khi hoàn tất việc gắn nghĩa, ta sẽ thu được câu tiếng
Việt có trật tự từ hợp lý.
Luận văn được tổ chức thành các phần chính sau:
Chương 1: Giới thiệu tầm quan trọng, mục tiêu, phạm vi của đề tài, cơ sở
lý thuyết ngôn ngữ học, tin học và hướng tiếp cận vấn đề.
Chương 2: Điểm qua các cách tiếp cận chuyển đổi cấu trúc.
Chương 3: Thuật toán nền tảng, mô hình học và mô hình áp dụng chuyển
đổi cây cú pháp.
Chương 4: Thiết kế – Cài đặt
Chương 5: Thử nghiệm – đánh giá
Chương 6: Kết quả – Kết luận – Hướng phát triển
Phần phụ lục. Tài liệu tham khảo.
Luận văn tốt nghiệp
Trang 6
M
M
ụ
ụ
c
c
u.......................................................................................................5
M
M
ụ
ụ
c
cl
l
ụ
ụ
c
c.............................................................................................................6
Danh sách các hình .......................................................................................11
Danh sách các bảng.......................................................................................13
C
C
h
h
ư
ư
ơ
ơ
n
1.2
Vai trò của chuyển đổi cây cú pháp trong cách tiếp cận dựa trên
chuyển đổi..................................................................................................20
1.3
Cơ sở lý thuyết................................................................................22
1.3.1
Cơ sở lý thuyết ngôn ngữ học của việc chuyển đổi ..............................23
1.3.2
Cơ sở lý thuyết tin học - Hướng tiếp cận vấn đề ..................................33
C
C
h
h
ư
ư
ơ
ơ
n
n
g
g
2.2.2
Chuyển đổi ngữ động từ........................................................................41
2.2.3
Sự chuyển đổi của định ngữ, bổ ngữ.....................................................42
2.2.4
Tự điển chuyển đổi................................................................................43
2.2.5
Nhận xét ................................................................................................44
2.3
Hướng tiếp cận sử dụng TAG đồng bộ (STAG)..........................44
2.3.1
Văn phạm TAG.....................................................................................45
2.3.2
TAG đồng bộ (STAG) ..........................................................................49
2.3.3
2.5.1
Rút trích các cấu trúc vị từ - đối số .......................................................60
2.5.2
Khối chuyển đổi cấu trúc ......................................................................62
2.5.3
Nhận xét ................................................................................................64
2.6
Tổng kết chương ............................................................................65
C
C
h
h
ư
ư
ơ
ơ
n
n
g
g
Hình thức hóa TBL ...............................................................................72
3.2.2
Thuật toán FnTBL.................................................................................73
3.3
Mô hình chuyển đổi cây cú pháp sử dụng thuật toán FnTBL ...78
3.3.1
Mô hình áp dụng chuyển đổi cây cú pháp ............................................80
3.3.2
Mô hình học luật chuyển đổi bằng phương pháp học FnTBL..............82
3.4
Nâng cao khả năng mở rộng cho mô hình học ............................95
C
C
h
h
ư
ư
ơ
ơ
4.2.3
Xây dựng cây quan hệ.........................................................................103
4.2.4
Thuật toán chuyển đổi theo nguyên tắc ..............................................105
4.3
Học chuyển đổi cùng cấp.............................................................106
4.3.1
Xây dựng ngữ liệu học........................................................................106
4.3.2
Xây dựng khung luật cho bộ học chuyển đổi cùng cấp ......................108
4.3.3
Sơ đồ lớp của chương trình học ..........................................................114
4.3.4
Xây dựng bộ luật (giai đoạn học cùng cấp) ........................................114
4.3.5
C
C
h
h
ư
ư
ơ
ơ
n
n
g
g5
5......................................................................................................128
THỬ NGHIỆM – ĐÁNH GIÁ ....................................................................128
5.1
Thử nghiệm...................................................................................128
5.1.1
Độ đo sử dụng .....................................................................................128
5.1.2
Kết quả học rút luật chuyển đổi ..........................................................129
6
6......................................................................................................137
TỔNG KẾT ..................................................................................................137
6.1
Kết quả..........................................................................................137
6.2
Hướng phát triển..........................................................................137
6.3
Kết luận.........................................................................................138
PHỤ LỤC 1..................................................................................................139
KHUNG LUẬT VÀ MỘT SỐ LUẬT CÙNG CẤP......................................139
PHỤ LỤC 2..................................................................................................141
KHUNG LUẬT VÀ MỘT SỐ LUẬT KHÁC CẤP......................................141
PHỤ LỤC 3..................................................................................................142
MỘT SỐ KẾT QUẢ DỊCH SỬ DỤNG KHỐI CHUYỂN ĐỔI CÂY CÚ
PHÁP VCLTRANSFER..............................................................................142
Hình 5: Cây cú pháp của câu “I have already read that interesting book.” .............. 21
Hình 6: So sánh trật tự định ngữ tiếng Anh và tiếng Việt ........................................26
Hình 7: Áp dụng luật cố định để thực hiện việc chuyển đổi cấu trúc....................... 36
Hình 8: Trường hợp chuyển đổi khác cấp luật cố định không thể thực hiện được...37
Hình 9: Khả năng chuyển đổi cú pháp của luật cố định............................................ 38
Hình 10: Giản đồ cây khởi tạo và cây phụ trợ của TAG........................................... 46
Hình 11: Tác tố kết hợp ............................................................................................. 47
Hình 12: Tác tố thay thế............................................................................................. 48
Hình 13: Một số mẫu cây sơ cấp trong tự điển chuyển đổi cây Anh-Pháp ..............50
Hình 14: Cây phân tích ngữ pháp chuyển dịch đảo.. ................................................55
Hình 15: Chuyển đổi khung giữa các ngôn ngữ........................................................ 63
Hình 16: Sơ đồ phương pháp học TBL tổng quát ..................................................... 70
Hình 17: Một ví dụ minh hoạ chuyển đổi cây cú pháp ............................................ 79
Hình 18: Mô hình áp dụng chuyển đổi cây cú pháp.................................................. 81
Hình 19: Mô hình học luật chuyển đổi cây cú pháp theo thuật toán FnTBL............ 82
sau khi được áp dụng luật
R
R................................... 113
Hình 31: Sơ đồ lớp khối học luật chuyển đổi cùng cấp .......................................... 114
Hình 32: Mô hình áp dụng tập luật chuyển đổi cùng cấp ....................................... 116
Hình 33: Cây cú pháp của câu tiếng Anh “It is a good type of book.”................... 118
Hình 34: Một cây cú pháp tiếng Anh sau khi chuyển sang cấu trúc tiếng Việt......119
Hình 35: Một phần cây cú pháp với đường đi của thành phần [ADVP] .................123
Hình 36: Sơ đồ lớp khối học luật chuyển đổi khác cấp........................................... 125
Hình 37: Mô hình áp dụng tập luật chuyển đổi khác cấp........................................127
Hình 38: Đánh giá tập luật học chuyển đổi cùng cấp..............................................130
Hình 39: Đánh giá tập luật học chuyển đổi khác cấp .............................................131
Luận văn tốt nghiệp
Trang 13
Danh sách các bảng
Bảng 1: Trật tự các thành phần trong ngữ danh từ tiếng Anh...................................27
Bảng 17: Kết quả thử nghiệm việc áp dụng chuyển đổi cây cú pháp..................... 135
Chương 1 - Tổng quan về chuyển đổi cây cú pháp
Trang 14
C
C
h
h
ư
ư
ơ
ơ
n
n
g
g1
1TỔNG QUAN VỀ CHUYỂN ĐỔI CÂY
CÚ PHÁP
Chương này giới thiệu về đề tài luận văn - mục đích và phạm vi thực hiện.
Phần 2 của chương trình bày một cách tổng quát về chuyển đổi cây cú pháp: vai trò,
vị trí của khối chuyển đổi cây cú pháp trong hệ dịch Anh-Việt. Ngoài ra, những
khái niệm then chốt liên quan đến đề tài, cũng như các cơ sở về lý thuyết ngôn ngữ
ngữ tự nhiên là điều không tưởng, mục tiêu hệ dịch phải thu gọn lại trong một lĩnh
vực hẹp để hạn chế bớt tính nhập nhằng của ngôn ngữ.
Có 3 chiến lược dịch máy, đó là :
Dịch trực tiếp
Dịch dựa trên ngôn ngữ trung gian
Dịch dựa trên chuyển đổi
Cho đến nay, các hệ dịch dựa trên chuyển đổi được đánh giá cao vì tính khả
thi của nó. Tùy thuộc vào hai ngôn ngữ cần dịch mà hệ thống có thể thiết kế các
khối phân tích, chuyển đổi, tái tạo với độ phức tạp thích hợp. Một số hệ dịch dựa
trên chuyển đổi tiêu biểu như, hệ dịch Anh-Pháp METEO được xây dựng bởi đại
học Montreal - TAUM, được đưa vào sử dụng để dịch các bản tin dự báo thời tiết;
hệ dịch GETA (Đại học Grenoble, 1971-),...
Trong các hệ dịch dựa trên chuyển đổi, bước chuyển đổi là bước quan trọng
nhất, giữ vai trò quyết định chất lượng hệ dịch. Chuyển đổi này bao gồm hai phần
chuyển đổi chính, đó là chuyển đổi từ vựng và chuyển đổi cấu trúc. Chuyển đổi từ
vựng là quá trình chọn nghĩa đúng cho các từ ở ngôn ngữ nguồn thể hiện sang từ
tương ứng của ngôn ngữ đích. Còn chuyển đổi cấu trúc là quá trình sắp xếp lại,
thêm bớt, thay thế các thành phần cấu trúc của câu ở ngôn ngữ nguồn để có được
cấu trúc tương ứng ở ngôn ngữ đích.
Chương 1 - Tổng quan về chuyển đổi cây cú pháp
Trang 16
Trong luận văn này, chúng em tìm hiểu và xây dựng chương trình chuyển đổi
cây cú pháp Anh-Việt, đóng vai trò là một khối chuyển đổi cấu trúc trong hệ dịch tự
động Anh-Việt dựa trên sự chuyển đổi. Như đã trình bày ở phần trên, việc thực hiện
một chương trình có khả năng bao quát tất cả các cấu trúc chuyển đổi có thể có là
một vấn đề không tưởng trong xử lý ngôn ngữ tự nhiên. Do đó, chúng em giới hạn
giản
Văn bản
kết quả
Chương 1 - Tổng quan về chuyển đổi cây cú pháp
Trang 17
Các hệ dịch này hạn chế tối đa các bước phân tích cần thiết để giải quyết nhập
nhằng, cũng như đơn giản hoá cả việc xác định các thành phần tương ứng ở ngôn
ngữ đích thông qua tự điển lẫn xác định trật tự đúng của các từ trong ngôn ngữ đích.
Giữa khối phân tích và tái tạo câu không có bất kỳ bước trung gian nào. Các từ
trong văn bản nguồn chỉ qua một bước phân tích hình thái duy nhất. Cách làm này
chỉ phù hợp khi ngôn ngữ nguồn và đích có rất nhiều điểm giống nhau như tiếng
Anh và tiếng Tây Ban Nha, không phù hợp với phần lớn ngôn ngữ khác.
1.1.2 Chiến lược dịch dựa trên ngôn ngữ trung gian
Trong chiến lược này, ngữ nghĩa của văn bản ngôn ngữ nguồn được biểu diễn
lại theo một ngôn ngữ trung gian, và văn bản ngôn ngữ đích cũng được phát sinh từ
ngôn ngữ trung gian này. Do đó, chỉ có duy nhất một cách biểu diễn cho một đơn vị
ngữ nghĩa, bất kể ngôn ngữ gốc của nó là gì.
Hình 2: Mô hình dịch dựa trên ngôn ngữ trung gian
Xử lý trong hệ thống dựa trên ngôn ngữ trung gian bao gồm hai bước quan
trọng, đó là :
Phân tích văn bản nguồn để biểu diễn lại dưới dạng thức của một ngôn ngữ
trung gian.
Sử dụng những đơn vị ngữ nghĩa và cấu trúc cú pháp của ngôn ngữ đích để
phát sinh văn bản kết quả từ cách biểu diễn theo dạng ngôn ngữ trung gian.
Ngôn ngữ trung gian được sử dụng trong những hệ dịch như vậy đòi hỏi phải
đủ phong phú để biểu diễn được tất cả các đơn vị từ vựng và cú pháp của các ngôn
Văn bản nguồn
Biểu diễn trung gian của
ngôn ngữ nguồn
Văn bản kết quả
Ngữ pháp ngôn
ngữ nguồn / Tự
điển
Luật chuyển đổi /
Tự điển
Biểu diễn trung gian của
ngôn ngữ đích
Ngữ pháp ngôn
ngữ đích / Tự điển
PHÂN TÍCH
CHUYỂN ĐỔI
PHÁT SINH
Chương 1 - Tổng quan về chuyển đổi cây cú pháp
Trang 19
Quá trình phân tích có thể được thực hiện ở nhiều cấp độ khác nhau tùy thuộc
vào hai ngôn ngữ, chẳng hạn như phân tích hình thái, cấu trúc, ngữ nghĩa,... Các cấp
độ phân tích khác nhau dẫn đến nhiều cấp độ của dạng thức trung gian. Những dạng
thức này chứa các thành phần từ vựng nguồn và đích, phản ánh cấu trúc của hai
ngôn ngữ. Có nhiều loại biểu diễn khác nhau được sử dụng trong các hệ dịch dựa
trên sự chuyển đổi như: cây phụ thuộc, cấu trúc ngữ, ...
Chiến lược dịch máy dựa trên chuyển đổi có nhiều ưu điểm. Trước hết, tính
tương đồng giữa ngôn ngữ nguồn và đích càng cao thì bước chuyển đổi càng đơn
giản. Tương tự, giai đoạn phân tích và phát sinh cũng sẽ đơn giản hơn so với các hệ
dịch dựa trên ngôn ngữ trung gian.
Trong ba chiến lược nói trên thì chiến lược dựa trên sự chuyển đổi được quan
Dịch trực tiếp
Văn bản đích
Chương 1 - Tổng quan về chuyển đổi cây cú pháp
Trang 21
hơn mà vẫn giữ đúng ngữ nghĩa và sắc thái của văn bản gốc. Như vậy khối chuyển
đổi cấu trúc giữ nhiệm vụ thực hiện những thay đổi cần thiết khi biểu diễn trung
gian của ngôn ngữ nguồn không thể ánh xạ trực tiếp thành cách biểu diễn tương tự
trong ngôn ngữ đích do có sự khác biệt về cấu trúc của hai ngôn ngữ.
Cấu trúc cú pháp của một câu được biểu diễn dưới dạng cây cú pháp. Chuyển
đổi cấu trúc của một câu từ ngôn ngữ nguồn sang ngôn ngữ đích tức là quá trình xác
định mối liên hệ giữa các thành phần trong cây cú pháp và tìm ra những qui luật để
chuyển cây cú pháp đó về dạng phù hợp với ngôn ngữ đích. Nói cách khác ta phải
tìm một cây cú pháp tương đương với cây cú pháp của ngôn ngữ nguồn.
Ví dụ :
Có câu tiếng Anh “I have read that interesting book.” được phân tích
cú pháp và các nghĩa của từ trong câu đã được chọn đúng như sau (từ có nghĩa
ε
tức là từ chỉ đóng vai trò cú pháp, nó không có nghĩa thực sự) :
Hình 5: Cây cú pháp của câu “I have already read that
interesting book.”
N
N
P
PV
D
V
VV
V
P
PV
VN
N
P
Phave/
ε
already/rồi
read/đọc
I/Tôi
.
.
D
J
Jbook/cuốn sách
that/đó
interesting/thú vị
Chương 1 - Tổng quan về chuyển đổi cây cú pháp
Trang 22
Nếu chỉ đơn thuần là gắn nghĩa thì câu tiếng Việt được phát sinh là “Tôi rồi
đọc đó thú vị cuốn sách .”. Trong tiếng Việt, câu này hoàn toàn vô nghĩa vì trật tự
các thành phần ở sai vị trí sẽ dẫn đến trật tự từ sai và ta không biết được nghĩa chính
xác của câu là gì.
Chương trình chuyển đổi cây cú pháp có nhiệm vụ thay đổi vị trí, chèn hoặc
xoá các thành phần trong cây cú pháp sao cho trật tự từ bề mặt của câu trở nên
đúng. Trong ví dụ trên, ta thấy nếu chương trình chuyển đổi thay đổi cây cú pháp
của câu theo các luật sau :
1. (ADJP (DT) (A))→ (ADJP (A) (DT)) : Nếu ngữ tính từ bao gồm một chỉ định
từ (DT) đứng trước một tính từ (A) thì đảo trật tự 2 thành phần con đó.
2. (NP (ADJP) (N)) → (NP (N) (ADJP)) : Nếu ngữ danh từ bao gồm một ngữ
tính từ (ADJP) đứng trước danh từ (N) thì đảo trật tự 2 thành phần con đó.
3. (VP (AUX have) (VP)) → (VP
ε
(VP)) : Nếu ngữ động từ bao gồm một trợ
động từ have đứng trước một ngữ động từ khác từ xoá trợ động từ đi.
4. (VP (ADV already) (VP)) → (VP (VP) (ADV already)) : Nếu ngữ động từ bao
gồm trạng từ already đứng trước ngữ động từ thì đảo trật tự 2 thành phần
1.3.1.1 Ngữ pháp tạo sinh
Ngữ pháp
Để tạo thành một câu có nghĩa trong một ngôn ngữ nào đó, ta không thể chỉ
đơn giản kết hợp các từ bất kỳ theo thứ tự ngẫu nhiên, mà sự kết hợp đó phải tuân
thủ những luật ngữ pháp của ngôn ngữ đó.
Định nghĩa: Ngữ pháp G được định nghĩa là sự hợp thành của 4 thành phần
()
0
,,, SPNG Σ=
, với :
N : tập hợp các thành tố không kết thúc (nonterminal) như NP, VP,...
∑
: tập hợp các thành tố kết thúc (terminal) như Adj, Noun,...
P : Tập hợp các luật ngữ pháp
S
0
: Ký hiệu thành tố khởi đầu câu
Chương 1 - Tổng quan về chuyển đổi cây cú pháp
Trang 24
Tập hợp luật ngữ pháp bao gồm 2 loại luật là luật từ pháp và luật cú pháp.
Luật từ pháp đảm bảo cho mỗi từ tồn tại trong câu đều có nghĩa riêng. Luật cú pháp
quy định trật tự kết hợp các thành phần ngữ pháp để tạo thành một câu hoàn chỉnh
có nghĩa.
1
,X
2
,
..., X
n
vào làm con của nút gốc theo thứ tự từ trái sang phải.
2. Nếu có nút con X
i
và các luật X
i
→Y
1
Y
2
... Y
n
, thì ta sẽ gắn các nút Y
1
,Y
2
,
..., Y
n
vào làm con trực tiếp của nút X
i
theo thứ tự từ trái sang phải.
3. Tiếp tục như thế cho đến khi tập hợp các nút con cuối cùng đều là thành tố
kết thúc (terminal) hoặc là chuỗi rỗng
ε
tiếng Việt, phần lớn các tiền định ngữ này đứng sau danh từ chính. Tuy nhiên cũng
có một số trường hợp ngoại lệ.
Copyright: Tài liệu đại học ©