BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

NGUYỄN THỊ THU HƯƠNG MÔ HÌNH
VĂN PHẠM LIÊN KẾT TIẾNG VIỆT

Chuyên ngành: Khoa học máy tính
Mã số: 62.48.01.01

LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN Người hướng dẫn khoa học:
GS. TS. NGUYỄN THÚC HẢI
GS.TS. NGUYỄN THANH THỦY

Hà Nội - Năm 2013
1
MỤC LỤC
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT 4
DANH MỤC CÁC HÌNH VẼ 5
DANH MỤC BẢNG BIỂU 8
DANH MỤC CÁC KẾT NỐI QUAN TRỌNG 9
MỞ ĐẦU 11

2.2.Kết luận 69 
CHƯƠNG 3 PHÂN TÍCH CÚ PHÁP TRÊN VĂN PHẠM LIÊN KẾT 72
3.1. Bộ phân tích cú pháp liên kết 72
3.1.1. Giải thuật phân tích cú pháp 72
3.1.2. Lược tỉa 74
3.1.3. Kết quả thử nghiệm phân tích câu đơn và câu ghép đơn giản 76
3.2. Phân tích cú pháp cho câu ghép 79
3.2.1. Xây dựng cây diễn ngôn 83
3.2.2. Giải thuật phân tích cú pháp câu ghép 92
3.2.3. Tìm từ để kết nối mệnh đề 94
3.2.4. Kết quả thử nghiệm phân tích câu ghép 96
3.2.5. Độ phức tạp tính toán 99
3.3. Khử nhập nhằng 99
3.3.1. Khử nhập nhằng thành phần 100
3.3.2. Khử nhập nhằng liên hợp 106
3.4. Kết luận 110
CHƯƠNG 4 HỆ THỐNG DỊCH MÁY SỬ DỤNG DẠNG TUYỂN CÓ CHÚ GIẢI .
112
4.1. Tổng quan về dịch máy 112
4.1.1. Tình hình phát triển dịch máy ở Việt Nam 112
4.1.2. Phương pháp đánh giá chất lượng dịch máy 114
4.2. Khác biệt ngôn ngữ Việt - Anh 115
4.2.1. Khác biệt hình thái 115
4.2.2. Khác biệt về trật tự từ 118
4.3.Hệ thống dịch máy sử dụng dạng tuyển có chú giải 119
4.3.1.Tìm nghĩa từ trong từ điển ADJ 121
4.3.2. Xây dựng bộ luật dịch 122
4.3.3. Hoàn thiện câu dịch 129
4.3.4. Kết quả thử nghiệm với bộ dịch dựa trên dạng tuyển có chú giải 129
3

CCR Chunks/Constituents/Relation
SVO Subject-Verb-Object: Trật tự câu theo kiểu chủ ngữ- động từ- bổ ngữ
SVM Support Vector Machine: Máy vectơ hỗ trợ
CRF Conditional Random Fields: Trường ngẫu nhiên có điều kiện
EDU Elementary Discourse Unit: Đơn vị diễn ngôn nguyên tố
HPSG Head driven Phrase Structure Grammar: Văn phạm cấu trúc đoạn hướng trung tâm
EBNF Extended Backus Naur Form: Công thức siêu ngữ Backus mở rộng
5
DANH MỤC CÁC HÌNH VẼ
Hình 1.1. Cây ngữ cấu của câu “Tôi thích chân gà”. 21
Hình 1.2. Hai cây ngữ cấu của câu “Họ sẽ không chuyển hàng xuống thuyền vào
ngày mai”. 22

Hình 1.3. Văn phạm phi ngữ cảnh xác suất và cây ngữ cấu của câu “Last week IBM
bought Lotus” 27

Hình 1.4. Phân tích câu “John loves a woman” trong một mô hình văn phạm phụ
thuộc 31

Hình 1.5. Đồ thị phụ thuộc của câu “Economic news had little effect on financial
market” 32

Hình 1.6. Câu đúng ngữ pháp “Tại sao cậu không tới” 36
Hình 1.7. Kết nối lớn của từ “và” 38
Hình 1.8. Chu trình trong phân tích câu 39
Hình 1.9. Nút liên kết 41
Hình 2.1. Cấu trúc danh ngữ với đầy đủ các thành tố 50
Hình 2.2. Liên kết trong cụm từ “những cái bàn” 53
Hình 2.3. Liên kết trong cụm từ “cái giường lò xo”
55

Hình 3.8. Kêt quả phân tích liên kết của câu “Mỗi một mùa trắng tay đều khó nuốt
trôi” 77

Hình 3.9. Kết quả phân tích liên kết của câu “Phần lớn bọ ngựa ăn côn trùng” 78
Hình 3.10. Cây phân tích diễn ngôn của câu “[trời mưa rất to và
A1
] [gió rất mạnh
nên
B1
] [tôi phải nghỉ học,
C1
] [mẹ tôi phải nghỉ làm.
D1
]” 83
Hình 3.11. Giải thuật phân đoạn diễn ngôn (có khử nhập nhằng) 88
Hình 3.12. Hàm isClause 89
Hình 3.13. Các dạng cây cấu trúc diễn ngôn 92
Hình 3.14. Giải thuật phân tích cú pháp cho câu ghép 937

Hình 3.15. Hàm Insert_Link_From_RST_Tree 94

Hình 3.16. Minh họa cách lưu trữ phân tích liên kết của câu “Tôi mua một bông
hoa” 95

Hình 3.17. Phân tích câu “Tôi mua một bông hoa” 95
Hình 3.18. Phân tích cụm từ “một cái bút rất tốt” 96
Hình 3.19. Kết quả phân tích câu “Trời mưa rất to và gió rất mạnh nên tôi phải

Bảng 3.4. Các biểu thức chính quy biểu diễn một số dấu hiệu diễn ngôn tiềm tàng84
Bảng 3.5. Hành động ứng với một số dấu hiệu diễn ngôn 85
Bảng 3.6. Chi tiết tập mẫu câu ghép 97
Bảng 3.7. Kết quả phân tích các tập mẫu câu ghép 98
Bảng 3.8. So sánh kết quả phân tích diễn ngôn 108
Bảng 4.1. Những khác biệt quan trọng về hình thái giữa tiếng Việt và tiếng Anh 116
Bảng 4.2. Đại từ xưng hô tiếng Anh 117
Bảng 4.3. Đại từ xưng hô tiếng Việt 117
Bảng 4.4. So sánh kết quả các hệ thống dịch 132

9 DANH MỤC CÁC KẾT NỐI QUAN TRỌNG
CLI Kết nối chỉ chất liệu (ẩn giới từ).
DI Kết nối động từ “đi” với động từ khác.
DpN Kết nối định từ chỉ số nhiều với danh từ.
DpNt Kết nối định từ chỉ số nhiều với danh từ cụ thể.
DsN Kết nối định từ chỉ số ít với danh từ.
DT_LA Kết nối danh từ, đại từ xưng hô với động từ quan hệ “là”.
ĐT_XONG Kết nối một động từ và động từ “xong”.

RnV Kết nối phủ định từ và động từ.
RnV1 Kết nối động từ với phụ từ phủ định.
RpA Kết nối phụ từ thời gian (quá khứ) và tính từ.
RpV Kết nối động từ với phụ từ thời gian (quá khứ).
RpVt Kết nối định từ chỉ thì quá khứ và động từ.
RtA Kết nối phụ từ thời gian (hiện tại) và tính từ.
RtV Kết nối động từ với phụ từ thời gian (hiện tại).
SA Kết nối danh từ, đại từ xưng hô với tính từ.
SA Kết nối danh từ và tính từ.
SH Kết nối giới từ sở hữu và danh từ chỉ chủ sở hữu.
SHA Kết nối hai danh từ chỉ quan hệ sở hữu ẩn.
SS_NHAT Kết nối tính từ với từ “nhất”.
SV Kết nối danh từ, đại từ xưng hô làm chủ ngữ với động từ.
THS Kết nối các từ để hỏi đứng sau động từ và động từ.
THT Kết nối các từ để hỏi đứng trước động từ và động từ.
VmVt Kết nối động từ tình thái và động từ cụ thể.
VtAp Kết nối ngoại động từ và tính từ chỉ tính chất.
VtEp Kết nối ngoại động từ và giới từ vị trí.
VtVs Kết nối động từ ngoại động và động từ trạng thái.

11

MỞ ĐẦU
Xử lý ngôn ngữ tự nhiên trên máy tính là một trong những bài toán khó của công nghệ
thông tin. Nghiên cứu về xử lý ngôn ngữ tự nhiên đã được khởi động từ những năm 40 của
thế kỷ 20, ngay sau khi xuất hiện máy tính điện tử. Dù được bắt đầu muộn hơn, xử lý tiếng
Việt đã phát triển rất mạnh mẽ trong những năm gần đây do sự bùng nổ thông tin trên


12

hướng tiếp cận thống kê với kho ngữ liệu khổng lồ của Google. Nhìn chung, các sản phẩm
dịch tự động chủ yếu theo hướng Anh - Việt. Số lượng và chất lượng của các hệ thống dịch
Việt Anh còn hạn chế.
Về khai thác văn bản trên Internet, nhiều nhà nghiên cứu Việt Nam quan tâm đến các
lĩnh vực biểu diễn văn bản như Hồ Tú Bảo [29],[33]; khai phá web, web ngữ nghĩa như
Cao Hoàng Trụ [117], Hồ Tú Bảo[63]; tóm tắt văn bản như Lê Thanh Hương [66], nhóm
Hà Thành Lê [15] Tuy nhiên, không có nhiều nghiên cứu được thực hiện trên văn bản
tiếng Việt như hệ thống tóm tắt văn bản của nhóm Hà Thành Lê [15], hệ thống rút trích nội
dung trang web tiếng Việt của nhóm Đỗ Phúc [19].
Do đặc điểm về cấu tạo từ, phân tách và gán nhãn từ là giai đoạn tiền xử lý bắt buộc
trong các hệ thống xử lý tiếng Việt. Công cụ phân tách từ vnTokenizer đã được Nguyễn
Thị Minh Huyền và các đồng nghiệp phát triển, sử dụng ôtô mat hữu hạn kết hợp phân tích
biểu thức chính quy để xác định các chuỗi từ [102]. Trường hợp nhập nhằng được giải
quyết bằng thuật toán trực cảm (heuristic), ưu tiên cách phân tách cho kết quả chứa những
từ có độ dài lớn nhất. Phương pháp này đạt độ chính xác cao với bộ ngữ liệu mẫu (trên
98,5%) [116]. Bộ tách từ JVnSegmenter của nhóm Phan Xuân Hiếu [121] sử dụng công
nghệ CRF và SVM cũng cho kết quả 94%. Ngoài ra có thể kể đến bộ tách từ của Lê An Hà
[60] tính xác suất và độ hợp lý cực đại (maximum likelihood). Bài toán gán nhãn từ loại
thường được giải quyết cùng bài toán tách từ. Cùng với bộ JVnSegmenter, các tác giả của
nó xây dựng bộ gán nhãn từ JVnTagger sử dung CRF và entropy cực đại [7]. Bộ
vnTokennizer cũng đi kèm với vnQTAG [13]. Một số nghiên cứu của các tác giả Việt Nam
cũng tập trung vào khử nhập nhằng nghĩa từ như Lê Anh Cường [45], [46], Đinh Điền
[48].
Các bộ ngữ liệu là tài nguyên hết sức quan trọng trong xử lý tiếng Việt. Các đề tài cấp
nhà nước KC.01-03, KC.01.01/06-10 đã thu thập được một kho ngữ liệu tiếng Việt lấy từ
các bài báo điện tử. Hiện nay, bộ ngữ liệu 1 triệu âm tiết đã tách từ, 10.000 câu được gán
nhãn từ loại, treebank tiếng Việt với 10.000 phân tích câu đã được xây dựng. Đây cũng là

thống kê, rất ít nghiên cứu tách rời hoàn toàn các mô hình biểu diễn cú pháp. Việc tham
khảo cấu trúc cú pháp của văn bản nguồn cũng như văn bản đích xuất hiện trong các hệ
thống dịch của nhóm Đinh Điền [3], nhóm Đại học Bách khoa thành phố Hồ Chí Minh
[124], nhóm nghiên cứu tại JAIST [115]. Sử dụng phương pháp học thống kê kết hợp biểu
diễn cú pháp sẽ cho những sản phẩm có chất lượng tốt hơn hẳn, chẳng hạn trong lĩnh vực
dịch máy [115]. Như vậy vấn đề biểu diễn cú pháp vẫn là vấn đề hết sức quan trọng trong
xử lý tiếng Việt.
Mô hình văn phạm phi ngữ cảnh là mô hình phổ biến nhất để biểu diễn cú pháp tiếng
Việt và phân tích cú pháp theo những phương pháp nổi tiếng CYK, Earley [12], [27], [5].
Mô hình này cũng được sử dụng cho một số hệ thống dịch máy [124].
Việc phân chia từ thành các lớp mà không quan tâm đến những đặc điểm từ vựng của
văn phạm ngữ cấu cổ điển có thể làm cho bộ phân tích cú pháp chấp nhận nhiều câu không
bao giờ được sử dụng trong thực tế, ví dụ câu tiếng Việt “Tôi mua hai thóc”. Câu này, 14

không tồn tại trong tiếng Việt vì từ “thóc” trong không bao giờ đi trực tiếp sau số từ. Hiện
tượng này cũng rất phổ biến trong các ngôn ngữ khác. Xu hướng từ vựng hóa các văn
phạm được nhiều nhà nghiên cứu quan tâm. Nhiều mô hình văn phạm từ vựng hóa đã được
xây dựng cho ngôn ngữ tự nhiên như văn phạm phi ngữ cảnh từ vựng hóa,văn phạm chức
năng từ vựng hóa, văn phạm cấu trúc đoạn hướng trung tâm, văn phạm kết nối cây từ vựng
hóa, văn phạm phạm trù tổ hợp, văn phạm liên kết Hiện nay, xu hướng từ vựng hóa cũng
đã ảnh hưởng tới các văn phạm tiếng Việt. Các mô hình văn phạm phi ngữ cảnh từ vựng
hóa kết hợp xác suất [22], văn phạm kết nối cây từ vựng hóa [20] đã được phát triển cho
tiếng Việt. Tuy nhiên chỉ có một số ít các văn phạm như văn phạm phạm trù tổ hợp, văn
phạm liên kết là hoàn toàn từ vựng hóa, tức là tồn tại những luật riêng cho từng mục từ
[112]. Mô hình hoàn toàn từ vựng hóa cho phép đặc tả nhiều ngoại lệ về cú pháp và từ
pháp của tiếng Việt.
Tập ký hiệu không kết thúc có kích cỡ lớn làm cho phân tích câu trong văn phạm phi

tiếng Thái Lan với bộ phân tích cú pháp của Tongchim [119], tiếng Tagalog (Philippines)
với bộ phân tích của Maguilimotan và Matsumoto [85]. Mô hình văn phạm phụ thuộc cũng
rất hữu hiệu cho những ứng dụng như tóm tắt văn bản [91], [108], rút trích thông tin [42],
dịch máy [49], [55]
Vai trò quan trọng của mô hình phụ thuộc là rõ ràng. Tuy nhiên mô hình văn phạm phụ
thuộc có những điểm khó về mặt ngôn ngữ học. Theo Nguyễn Tài Cẩn [2] còn nhiều tranh
luận về sự phụ thuộc giữa các yếu tố trong câu tiếng Việt, chẳng hạn một số đối tượng có
thể đóng vai trò phụ về cú pháp, nhưng lại đóng vai trò chính về từ pháp hay vai trò trung
tâm của danh ngữ, động ngữ thuộc về đối tượng nào cũng còn nhiều quan điểm khác nhau.
Do vậy, dù được nhắc đến trong một số tài liệu như [6], chưa có công trình nào về văn
phạm phụ thuộc được công bố trong lĩnh vực ngôn ngữ học. Tiếng Việt có một bộ phân
tích cú pháp phụ thuộc theo mô hình đồ thị [17] nhưng khó phát triển hơn nữa, do chưa có
một hệ thống văn phạm phụ thuộc đầy đủ. Với mong muốn tiếp cận với mô hình văn phạm
dạng phụ thuộc nhưng thiên về từ pháp, luận án đã chọn cho đề tài của mình một mô hình
theo hướng phụ thuộc nhưng hoàn toàn từ vựng hóa: mô hình văn phạm liên kết.
Văn phạm liên kết là mô hình do D.Sleator và D. Temperley đưa ra [111], cho phép mỗi
từ có một số mối liên hệ với các từ ở bên trái hoặc bên phải, thỏa mãn một số yêu cầu về
tính phẳng, tính liên thông, tính thỏa mãn, tính thứ tự và tính loại trừ. Văn phạm liên kết là
văn phạm theo cách tiếp cận phụ thuộc, thể hiện ở những điểm sau:
1. Phân tích liên kết không chứa ký hiệu không kết thúc, thậm chí cấu trúc còn đơn giản
hơn cây phụ thuộc. Có thể coi phân tích liên kết như một danh sách tuyến tính với mỗi
nút chứa không quá 3 mối liên hệ với nút khác. Ngân hàng phân tích vì thế đơn giản
hơn ngân hàng cây ngữ cấu. Nhiều cơ sở dữ liệu được thiết lập từ các ngân hàng phân
tích lớn như ngân hàng dữ liệu đa phương tiện [128]. Phân tích liên kết được sử dụng
phổ biến cho những ứng dụng khác như trích chọn thông tin [84], [106], [110], dịch
máy [35], hỏi đáp tự động [95], [105] Nhiều bộ phân tích cú pháp cho các ngôn ngữ
khác nhau được xây dựng trên mô hình văn phạm liên kết cho tiếng Anh[111], tiếng
Nga [132], tiếng Đức [76], tiếng Thổ Nhĩ Kỳ [68]
không tồn tại với bất cứ loại từ nào khác.
7. Liên kết có thể dùng để biểu diễn tri thức [53], liên kết cũng rấ
t gần với đồ thị khái
niệm nên có thể chuyển từ liên kết sang đồ thị khái niệm dễ dàng [131]. Phân tích liên
kết cũng được sử dụng để trích chọn thông tin [50], [52], [90], [97], đặc biệt là thông
tin ngữ nghĩa [82]. 17

8. Liên kết có nhãn nên biểu diễn trực tiếp mối liên hệ vị ngữ - bổ ngữ và các mối liên hệ
khác, tạo thuận lợi cho việc dịch sang ngôn ngữ có biến đổi hình thái, tốt hơn những
mô hình mà quan hệ phụ thuộc không được gán nhãn (theo Zamin [129]).
Qua khảo cứu và thử nghiệm bước đầu, luận án rút ra một số nhận xét:
1. Từ trước đến nay, cách phổ biến nhất để biểu diễn cú pháp tiếng Việt là thông qua mô
hình văn phạm ngữ cấu (phi ngữ cảnh) với cây ngữ cấu. Tuy nhiên tiếng Việt có những
đặc điểm riêng mà cấu trúc này không dễ biểu diễn: ẩn giới từ sở hữu, chuyển loại từ,
sự kết hợp số từ và các danh từ chỉ đơn vị… Những đặc điểm này có thể được biểu
diễn một cách linh hoạt và
đơn giản qua mô hình liên kết. Đặc biệt khi giải quyết bài
toán dịch từ tiếng Việt sang ngôn ngữ khác, việc phát hiện được mối quan hệ trực tiếp
giữa các từ cho khả năng chuyển đổi sang cấu trúc của ngôn ngữ đích với chất lượng
cao.
2. Phân tích câu theo mô hình liên kết rất gần với suy nghĩ của con người, do vậy có thể
hỗ trợ hiệu quả cho những học viên ti
ếng Việt khi tìm hiểu cú pháp và đặt câu. Kết quả
phân tích liên kết của câu lại đơn giản hơn nhiều so với cây ngữ cấu. Tuy là một đồ thị,
nhưng phân tích liên kết gần như một danh sách tuyên tính của các từ, mỗi từ có mối
liên hệ với không quá 3 từ khác. Điều đó cho phép tra cứu ngân hàng phân tích dễ dàng
hơn treebank, tạo thuận lợi cho các hướng tiếp cận theo phương pháp thống kê.

Các hướng tiếp cận để biểu diễn cú pháp (đặc biệt là hướng tiếp cận phụ thuộc), mô hình
văn phạm liên kết và mối liên hệ với mô hình văn phạm phụ thuộc, các mô hình văn phạm
liên kết đã được xây dựng cho tiếng Anh, tiếng Nga và một số ngôn ngữ khác. Bộ phân
tích cú pháp tiếng Anh và các giải thuật phân tách mệnh đề của câu ghép là những vấn đề
mà luận án nghiên cứu để xây dựng bộ phân tích liên kết tiếng Việt. Để minh họa cho khả
năng biểu diễn của mô hình văn phạm liên kết tiếng Việt, luận án đi vào tìm hiểu các hệ
thống dịch để xây dựng bộ dịch máy sử dụng văn phạm liên kết.
Trong khuôn khổ của luận án, công việc sẽ được giới hạn trong phạm vi :
1. Xây dựng mô hình liên kết để biểu diễn cú pháp tiếng Việt. Bộ từ điển liên kết của
tiếng Việt được xây dựng có tính chất thử nghiệm, bao quát được những hiện tượng cú
pháp cơ bản nhất và một số trường hợp cá biệt thường gặp trong thực tế.
2. Bộ phân tích cú pháp liên kết tiếng Việt cũng phải qua những giai đoạn tiền xử lý như
bất cứ bộ phân tích cú pháp nào khác. Theo cách tiếp cận này, bộ phân tích cú pháp
không gán nhãn từ trước khi phân tích cú pháp, nhưng không thể bỏ qua giai đoạn tách
từ. Luận án đã sử dụng bộ tách từ vnTokenizer của TS. Lê Hồ
ng Phương, được cung
cấp miễn phí trên mạng.
3. Nghiên cứu mô hình văn phạm liên kết xác suất để khử nhập nhằng trong phân tích cú
pháp. Đây là mô hình phức tạp hơn nhiều so với văn phạm phi ngữ cảnh xác suất. Luận
án giới hạn phạm vi làm việc là thử nghiệm các giải thuật được đề xuất.
4. Nghiên cứu lý thuyết cấu trúc diễn ngôn và giải thuật phân đoạn diễ
n ngôn mức câu để
phân tách câu ghép thành các mệnh đề. Đề xuất các kết nối lớn cho các mệnh đề trên
cơ sở các quan hệ diễn ngôn để cho ra phân tích tổng thể của câu ghép.
5. Việc xây dựng hệ thống dịch Việt - Anh dựa trên dạng tuyển có chú giải là một minh
họa cho việc ứng dụng mô hình văn phạm liên kết tiếng Việt. Hệ thống này được thử 19


Theo Jurafsky [70], quan hệ văn phạm là cách hình thức hóa những tư tưởng của văn
phạm truyền thống như chủ ngữ hay bổ ngữ và những mối quan hệ khác. Nhiều mô hình
văn phạm đã được đưa ra theo các hướng tiếp cận: cấu trúc (constituency), quan hệ văn
phạm (grammar relation), phân loại con (subcategorization) hay phụ thuộc (dependency).
Hai hướng tiếp cận phổ biến nhất hiện nay là cấu trúc và phụ thuộc. Chương này sẽ gi
ới
thiệu các mô hình văn phạm phổ biến và vị trí của văn phạm liên kết trong hệ thống các mô
hình văn phạm đó.
1.1. Cách tiếp cận cấu trúc và văn phạm phi ngữ cảnh
Vấn đề đầu tiên đặt ra khi mô tả các quy tắc cú pháp là biểu diễn được các quy luật để
nhóm các từ lại thành câu. Nếu ngữ pháp tiếng Việt [28] quy định câu phải chứa một nòng
cốt (đơn hoặc ghép), nòng cốt đơn phải chứa chủ ngữ, vị ngữ với chủ ngữ luôn đi trước vị
ngữ, thì vấn đề mô tả quy tắc cú pháp sẽ chuyển thành vấn đề tạo lập các cấu trúc
(constituent) và đưa ra các quy tắc về vị trí của các cấu trúc.
Mô hình cho phép nghiên cứu việc tạo lập các cấu trúc một cách đệ quy chính là mô
hình văn phạm phi ngữ cảnh. Mô hình hình thức này tương đương với dạng chuẩn BNF
(Backus Naur Form) của ngôn ngữ lập trình.
1.1.1. Văn phạm phi ngữ cảnh biểu diễn ngôn ngữ tự nhiên
Văn phạm phi ngữ cảnh bao gồm một tập các luật hay sản xuất, mỗi luật biểu diễn cách
thức mà các ký hiệu của ngôn ngữ được nhóm lại rồi sắp theo thứ tự và một tập từ vựng
bao gồm các từ và ký hiệu.
Ví dụ: Một tập sản xuất của văn phạm phi ngữ cảnh tiếng Việt với ý nghĩa của các ký
hiệu không kế
t thúc: S - câu, NP - danh ngữ, VP - động ngữ, N - danh từ, V - động từ, P -
đại từ.
S  NP VP NP  P
NP  N P VP  V NP 21


22

Vấn đề nhập nhằng là một trong những vấn đề phức tạp nhất mà các bộ phân tích cú
pháp phải giải quyết. Theo [70], trong giai đoạn phân tích cú pháp, vấn đề nhập nhằng
hướng về cấu trúc (structural ambiguity). Giả thiết ta chỉ xét câu đơn, tức là câu chỉ có một
nòng cốt và bỏ qua vấn đề nhập nhằng từ loại. Vấn đề nhập nhằng cấu trúc xảy ra khi một
câu có nhiều hơn một cây phân tích. Trong hình 1.2 là hai cây ngữ cấu khác nhau cho câu
“Họ sẽ không chuyển hàng xuống thuyền vào ngày mai” (câu ví dụ trong [20]) với văn
phạm phi ngữ cảnh
S → NP VP
NP → P
VP → R VP | R R V N PP PP PP-TMP | VP PP | V NP PP
PP → E NP
PP-TMP →E NP
Ý nghĩa của các ký hiệu: S - câu, NP - danh ngữ, VP- động ngữ, PP - giới ngữ, N -
danh từ, V - động từ, P - đại từ, R - phụ từ, E - giới từ, PP-TMP - giới ngữ chỉ thời gian.

Hình 1.2. Hai cây ngữ cấu của câu “Họ sẽ không chuyển hàng xuống thuyền vào ngày mai”. 23

Một trong những cách tiếp cận đầu tiên để giải quyết vấn đề nhập nhằng khi phân tích
cú pháp trên mô hình văn phạm phi ngữ cảnh là mô hình văn phạm phi ngữ cảnh xác suất
(Probabilistic Context Free Grammar).
1.1.2. Văn phạm phi ngữ cảnh xác suất
Trong mô hình văn phạm phi ngữ cảnh xác suất, mỗi luật được gắn thêm một xác suất
cho thấy luật đó có thường xuyên được sử dụng trong các cây ngữ cấu hay không.
Định nghĩa 1.2. [70] Văn phạm phi ngữ cảnh xác suất là bộ bốn

S

 argmax
..
Pr

T
|
S

argmax
..
PrT,S
PrS

 argmax
..
Pr

T,S

 argmax
..
PrT
Biểu thức T.s.t.S = yield(T) yêu cầu tính trên tất cả các cây ngữ cấu T có kết quả là câu S.
Trong trường hợp lý tưởng, nếu có một treebank đủ lớn, có thể tính xác suất của mỗi
luật theo công thức:
Pr



sản sinh bởi các luật N
i
 N
j
N
k
và N
i
 w
j
. Trong đó O
i
, i1,mthực
chất là các ký hiệu kết thúc (từ) w
1
, w
m
của xâu đưa vào.
Theo mô hình HMM, ma trận tham số của văn phạm phi ngữ cảnh xác suất là α [i, j, k]
và β [i, r] với:
α[i,j,k]=Pr(N
i
N
j
N
k
|G)
β[i,r]=Pr(N
i
r|G)

.

 Tập ký hiệu kết thúc của văn phạm là {w
1
, , w
V
}.
 Câu được phân tích w
1
w
m
.
 w
pq
là bộ phận của câu cần phân tích từ từ thứ p đến từ thứ q.
 N


là ký hiệu không kết thúc N
j
sinh ra dãy các từ ở vị trí từ p đến q trong câu.
 
j
(p, q) là xác suất ngoài.
 
j
(p, q) là xác suất trong.