ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

DƢƠNG THỊ HÀ

XỬ LÍ BÀI TOÁN THÊM DẤU CHO TIẾNG VIỆT
KHÔNG DẤU DỰA TRÊN NGHIÊN CỨU MÔ HÌNH
NGÔN NGỮ N_GRAM

CHUYÊN NGHÀNH: KHOA HỌC MÁY TÍNH
Học viên thực hiện: Dƣơng Thị Hà
Lớp: K9B
Giáo viên hƣớng dẫn: TS. Vũ Tất Thắng 2012 i

LỜI CAM ĐOAN

Tôi xin cam đoan, toàn bộ nội dung liên quan tới đề tài được trình bày
trong luận văn là bản thân tôi tự tìm hiểu và nghiên cứu, dưới sự hướng dẫn
khoa học của TS. Vũ Tất Thắng Viện công nghệ thông tin thuộc Viện Khoa
học và Công nghệ Việt Nam.
Các tài liệu, số liệu tham khảo được trích dẫn đầy đủ nguồn gốc.
Thái Nguyên, ngày 20 tháng 9 năm 2012


Học viên Dương Thị Hà
iii

DANH MỤC HÌNH

Trang

Hình 3.1 Quy trình tách từ 36
Hình 3.2 Số lượng các cụm N-gram với âm tiết khi tăng kích thước dữ liệu 46
Hình 3.3 Số lượng các cụm N-gram với từ khi tăng kích thước dữ liệu 47
Hình 3.4 Lưu đồ thực hiện của mô hình đề xuất 53
Hình 3.5 Mô hình tổng quát 54
iv

DANH MỤC BẢNG
Trang

Bảng 3.1 Số lượng các cụm N-gram trong văn bản huấn luyện với âm tiết 46
Bảng 3.2 Số lượng các cụm N-gram trong văn bản huấn luyện với từ 47
Bảng 3.3 Độ hỗn loạn thông tin của các phương pháp làm mịn cho âm tiết 48

1.4.1 Khái quát. 12
1.4.2 Công thức tính “xác suất thô”. 15
1.4.3 Những vấn đề khó khăn khi xây dựng mô hình ngôn ngữ N-gram.
16
1.4.3.1 Phân bố không đều. 16
1.4.3.2 Kích thước bộ nhớ của mô hình ngôn ngữ. 16
CHƯƠNG 2MÔ HÌNH NGÔN NGỮ N-GRAM 17
2.1 CÁC KĨ THUẬT LÀM MỊN HÓA SỰ PHÂN BỐ XÁC SUẤT
TRONG MÔ HÌNH N-GRAM ĐỂ TĂNG CHẤT CHẤT LƯỢNG CỦA
MÔ HÌNH 17
2.1.1 Các thuật toán chiết khấu (Discounting). 18 vi

2.1.1.1 Kĩ thuật làm mịn theo thuật toán Add-one. 18
2.1.1.2 Kĩ thuật làm mịn theo thuật toán Witten-Bell. 20
2.1.1.3 Kĩ thuật làm mịn theo thuật toán Good-Turing. 21
2.1.2 Kĩ thuật truy hồi (Back-0ff). 21
2.1.3 Kĩ thuật nội suy (Interpolation) 23
2.1.4 Kĩ thuật làm mịn Kneser-Ney. 24
2.1.5 Kĩ thuật làm mịn Chen-Goodman. 25
2.2 CÁC KĨ THUẬT LÀM GIẢM KÍCH THƯỚC MÔ HÌNH 26
2.2.1 Pruning (loại bỏ) 26
2.2.1.1 Cắt bỏ (cut-off) 27
2.2.1.2 Sự khác biệt trọng số (Weighted difference) 28
2.2.2 Đồng hóa (Quantization) 29
2.2.3 Nén (Compression) 30
2.3 CÁC ĐỘ ĐO ĐỂ ĐÁNH GIÁ CHẤT LƯỢNG CỦA MÔ HÌNH N-
GRAM 30

3.5.1.1. Phát biểu bài toán 50
3.5.1.2. Đặc điểm 50
3.5.1.3. Hướng giải quyết: 51
3.5.2 Các hệ thống thêm dấu ứng dụng về N-gram đã có 51
3.5.2.1 VietPad 51
3.5.2.2 VnMark – Mô hình thêm dấu tiếng Việt. 51
3.5.3 Đề xuất hệ thống 53
3.5.3.1 Mô hình 53
3.5.3.2. Mô hình huấn luyện 60
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI 61
TÀI LIỆU THAM KHẢO 631MỞ ĐẦU
1. Lí do chọn đề tài
Ngôn ngữ tự nhiên là ngôn ngữ được con người sử dụng trong giao tiếp
hàng ngày, nó khác hẳn với ngôn ngữ nhân tạo (ngôn ngữ lập trình, ngôn ngữ
máy…). Việc làm cho máy tính hiểu được ngôn ngữ tự nhiên không phải dễ
dàng. Để hiểu đúng nội dung của một văn bản viết bằng ngôn ngữ tự nhiên,
trong quá trình đọc hay nghe thì thực tế là ta đã nhận thức được ngữ cảnh của
văn bản đó. Mặt khác, ngôn ngữ tự nhiên có các bộ luật, cấu trúc ngữ pháp
phong phú hơn nhiều so với các ngôn ngữ máy tính, để có thể xây dựng một
bộ luật về ngữ pháp, từ vựng…, thật hoàn chỉnh để máy có thể hiểu ngôn ngữ
tự nhiên là một việc rất tốn công sức và đòi hỏi người thực hiện phải có hiểu
biết sâu sắc về ngôn ngữ học.
Mô hình ngôn ngữ (Language Model – LM) có thể cho biết xác suất một
câu (hoặc cụm từ) thuộc một ngôn ngữ có xác suất sinh ra là bao nhiêu hay

Ứng dụng của phương pháp thêm dấu là khá nhiều như: Thêm dấu cho các
mail; cho các quản trị web, các trang web yêu cầu viết tiếng Việt nhưng người
dùng không có sẵn bộ gõ; thêm dấu cho tin nhắn điện thoại…
2. Mục tiêu và nhiệm vụ
a) Mục tiêu: Do phạm vi bài toán khá lớn và thời gian làm luận văn là có
giới hạn nên mục tiêu nghiên cứu của luận văn tập trung ở các điểm sau:
Về học thuật:
Đề tài này tập trung vào việc ứng dụng một số phương pháp tách từ, tiếng,
phương pháp làm mịn trong mô hình ngôn ngữ N-gram nhằm tăng hiệu quả
thêm dấu cho tiếng Việt không dấu.
Về phát triển và triển khai ứng dụng:
Kết quả của đề tài sẽ ứng dụng trong việc hỗ trợ trong việc thêm dấu cho
tiếng Việt không dấu. 3

b) Nhiệm vụ:
- Nghiên cứu các vấn đề khi xây dựng mô hình ngôn ngữ N-gram.
- Nghiên cứu các phương pháp làm mịn trong mô hình ngôn ngữ N-gram.
- Nghiên cứu các kỹ thuật làm giảm kích thước dữ liệu.
3. Phương pháp nghiên cứu
- Tìm hiểu N-gram thông qua tài liệu.
- Tìm hiểu phương pháp xác định ngôn ngữ văn bản thực tế được các
chương trình thêm dấu tự động sử dụng.
- Đối sánh kết quả với các phương pháp thêm dấu tự động khác khi áp dụng
mô hình ngôn ngữ N-gram cho văn bản tiếng Việt không dấu.
Ngoài ra, luận văn còn sử dụng một số phương pháp tiếp cận hệ thống,
phương pháp chuyên gia và phương pháp thống kê và mô hình hóa.
4. Đối tượng và phạm vi nghiên cứu

Chương 2: Mô hình ngôn ngữ N-gram
2.1 Các kĩ thuật làm mịn hóa sự phân bố xác suất trong mô hình N-gram để
tăng chất lượng của mô hình.
2.2 Các kĩ thuật làm giảm kích thước mô hình.
2.3 Các độ đo để đánh giá chất lượng của mô hình N-gram.
Chương 3: Xây dựng N-gram cho tiếng Việt và ứng dụng trong bài toán
thêm dấu cho tiếng Việt không dấu
3.1 Công cụ xử lí mô hình.
3.2 Công cụ xử lí văn bản tiếng Việt.
3.3 Dữ liệu thực nghiệm.
3.4 Đánh giá chất lượng N-gram cho tiếng Việt tương ứng với kĩ thuật trong
chương 2.
3.5 N-gram và ứng dụng để thêm dấu cho tiếng Việt không dấu.
Kết luận và hướng phát triển của đề tài5

CHƯƠNG 1
TỔNG QUAN VỀ CÁC MÔ HÌNH NGÔN NGỮ VÀ CÁC ỨNG
DỤNG TRONG LĨNH VỰC XỬ LÍ NGÔN NGỮ TỰ NHIÊN
Ngôn ngữ tự nhiên là ngôn ngữ được con người dùng trong các hoạt động
giao tiếp hàng ngày như nghe, nói, đọc, viết [13]. Con người có khả năng dễ
dàng hiểu và xử lí thông tin thực tế ấy nhưng để máy tính hiểu ngôn ngữ tự
nhiên thì không phải dễ. Khó khăn ấy là do, ngôn ngữ tự nhiên có những cấu
trúc cú pháp, những bộ luật phong phú hơn nhiều so với ngôn ngữ của máy
tính, ngoài ra muốn hiểu đúng nội dung giao tiếp còn phải nắm được ngữ cảnh
của nó. Vì vậy, để xây dựng một bộ từ vựng, cú pháp hoàn chỉnh, chính xác là
việc rất tốn công sức, đòi hỏi người thực hiện phải có hiểu biết sâu sắc về
ngôn ngữ học.

dụ: bức thư, mạng máy tính.
- Câu: gồm các từ/ngữ có quan hệ ngữ pháp hay ngữ nghĩa với nhau và có
chức năng cơ bản là thông báo, ví dụ: I am reading my books
- Văn bản: hệ thống các câu được liên kết với nhau về mặt hình thức, từ
ngữ, ngữ nghĩa và ngữ dụng
1.2.1 Từ vựng tiếng Việt.
Việc đưa ra chính xác định nghĩa thế nào là một từ thì không phải đơn
giản, đòi hỏi công sức của các nhà ngôn ngữ học. Chúng ta đưa ra một định
nghĩa sau về từ làm một ví dụ:
“Từ là đơn vị nhỏ nhất có nghĩa, có kết cấu vỏ ngữ âm bền vững, hoàn
chỉnh, có chức năng gọi tên, được vận dụng độc lập, tái hiện tự do trong lời
nói để tạo câu”[10]. 7

Nhưng xét về góc độ ứng dụng thì ta có thể hiểu một cách đơn giản là
“từ được cấu tạo bởi một hoặc nhiều tiếng”.
1.2.2 Tiếng – đơn vị cấu tạo lên từ.
1.2.2.1 Khái niệm.
Tiếng là đơn vị cơ sở để cấu tạo nên từ tiếng Việt. Tiếng do một hay
nhiều âm phát ra cùng một lúc tạo thành. Tiếng có âm đầu, vần, thanh. Vần có
âm đệm, âm chính, âm cuối. Ví dụ: “Toàn” có phụ âm đầu T, âm đệm O, âm
chính A, âm cuối N và thanh huyền.
Trong các yếu tố tạo thành tiếng, âm chính và thanh lúc nào cũng có,
còn âm đầu, âm đệm và âm cuôi có thể vắng mặt. Ví dụ: à, ế, ở…
Về mặt hình thức thì tiếng là một đoạn phát âm của người nói, dù
chúng ta có phát âm chậm đến mấy thì ta cũng không thể tách tiếng ra thành
các đơn vị khác được. Tiếng được các nhà ngôn ngữ học gọi là âm tiết
(syllable).

 Thanh điệu: Mỗi tiếng đều có 1 thanh điệu là một trong sáu loại sau:
sắc, hỏi, ngã, nặng, huyền và bằng. Chúng có tác dụng phân biệt tiếng về
cao độ. Ví dụ: “quác”, “quạc”
 Âm đầu: Có tác dụng mở đầu âm tiết như “mùa”, “hùa”, “hoa”,
“thoa”…
 Âm đệm: Có tác dụng biến đổi âm sắc của âm tiết sau lúc mở đầu.
Ví dụ: “hòa”, “hà”…
 Âm chính: Là hạt nhân và mang âm sắc chủ đạo của tiếng. Ví dụ:
“túy”, “túi”,…
 Âm cuối: Có tác dụng kết thúc tiếng với các âm sắc khác nhau, do đó
có thể phân biệt các tiếng. Ví dụ: “nhàn”, “nhài”…
 Cụm gồm âm đệm, âm chính, âm cuối gọi là vần. Ví dụ: vần “uay”,
“anh”…
Đây là 5 thành tố của tiếng mà bất cứ tiếng nào trong tiếng Việt đều có
cấu trúc như vậy (vần không phải là thành tố mà chỉ là cách gọi của nhóm 3 9

âm nói trên). Nhưng cũng có một số trường hợp một số âm trùng nhau, nhất là
với những tiếng chỉ có 3 kí tự trở xuống.
1.2.3 Cấu tạo từ.
Như đã nêu ở trên, từ trong tiếng Việt hoặc là bằng 1 tiếng hoặc là tổ
hợp của nhiều tiếng khác nhau để tạo ra các loại từ. Sau đây, trong giới hạn,
luận văn xin đề cập tới một số loại từ sau.
1.2.3.1 Từ đơn.
Từ đơn, hay còn gọi là từ đơn âm tiết, là các từ được cấu tạo từ 1 tiếng
duy nhất. Ví dụ: nước, nhà, hoa, lá…
1.2.3.2 Từ ghép.
Từ ghép là từ được cấu tạo từ 2 tiếng trở lên. Giữa các tiếng có mối

Tóm lại, tiếng Việt được xếp vào loại hình đơn lập (isolate) hay còn gọi là
loại hình phi hình thái, không biến hình, đơn tiết với những đặc điểm chính
sau:
- Trong hoạt động ngôn ngữ, từ không biến đổi hình thái, ý nghĩa ngữ pháp
nằm ở ngoài từ. Ví dụ, tôi nhìn thấy anh ấy; anh ấy nhìn tôi.
- Phương pháp chủ yếu là trật tự từ và từ hư. Ví dụ, gạo xay và xay gạo.
- Tồn tại một loại đơn vị đặc biệt, đó là “hình tiết” mà vỏ ngữ âm trùng khít
với âm tiết, và đơn vị đó “cũng chính là hình vị tiếng Việt” hay còn gọi là
tiếng (theo tác giả Đinh Điền thì có khoảng 10.000 tiếng, nhưng theo khảo sát
của hội người mù Việt Nam khi làm chương trình sách nói thì chỉ có khoảng
3000 từ).
- Ranh giới từ không xác định mặc nhiên bằng khoảng trắng như các thứ
tiếng biến hình khác. Ví dụ: “học sinh học sinh học”. Điều này khiến cho việc
phân tích hình thái (tách từ) tiếng Việt trở nên khó khăn. Việc nhận ranh giới
từ là quan trọng làm tiền đề cho xử lí tiếp sau đó như: kiểm lỗi chính tả, gán
nhãn từ, thống kê tần suất từ…
- Tồn tại loại từ đặc biệt “từ chỉ loại” (classifier) hay còn gọi là phó danh từ
chỉ loại đi kèm với danh từ như: cái bàn, cuốn sách, bức thư…
- Về mặt âm học, các âm tiết tiếng Việt đều mang 1 trong 6 thanh điệu
(ngang, sắc, huyền, hỏi, ngã, nặng). Đây là âm vị siêu đoạn tính. 11

- Có hiện tượng láy trong từ tiếng Việt như: lấp lánh, lung linh… Ngoài ra,
còn có hiện tượng nói lái (do mối liên kết giữa phụ âm đầu và phần vần trong
âm tiết là lỏng lẻo) như: hiện đại  hại điện…
- Ngoài ra, theo[1] tiếng Việt còn có một loại từ là từ Ngẫu hợp. Đây là
những từ mà người bản ngữ hiện nay không tìm thấy mối quan hệ gì về ngữ
âm hay ngữ nghĩa giữa các tiếng cấu tạo nên chúng. Ví dụ: bồ câu, bồ hòn,

một mô hình Markov mới – mô hình MEMM như một đáp án cho những vấn
đề của mô hình Markov truyền thống. Mô hình MMEM quan niệm rằng các
quan sát đã được cho trước và chúng ta không cần quan tâm đến xác suất sinh
ra chúng, điều duy nhất cần quan tâm là xác suất chuyển trạng thái. So với mô
hình HMM, ở đây quan sát hiện tại không chỉ phụ thuộc vào trạng thái hiện
tại mà còn phụ thuộc vào trạng thái trước đó, điều đó có nghĩa là quan sát
hiện tại được gắn liền với các trạng thái riêng lẻ như mô hình HMM truyền
thống.
* CRF được giới thiệu lần đầu tiên vào đầu năm 2001 bởi Lafferty và
các đồng nghiệp. Giống như MMEM, CRF là mô hình dựa trên xác suất điều
kiện, nó có thể tích hợp được các thuộc tính đa dạng của chuỗi dữ liệu quan
sát nhằm hỗ trợ cho quá trình phân lớp. Tuy vậy, khác với MEMM, CRF là
đồ thị vô hướng. Điều này cho phép CRF có thể định nghĩa phân phối xác
suất của toàn bộ chuỗi trạng thái với điều kiện biết chuỗi trạng cho trước thay
vì phân phối trên mỗi trạng thái với điều kiện biết trạng thái trước đó và quan
sát hiện tại như các mô hình MEMM.
1.4 MÔ HÌNH NGÔN NGỮ N-GRAM.
1.4.1 Khái quát.
Mô hình ngôn ngữ thống kê cho phép gán (ước lượng) xác suất xuất hiện
của một chuỗi gồm m phần tử, thường là từ P(w
1
w
2
…w
m
), hay nói cách khác 13


w
2
w
3
)*…*P(w
m
|w
1
w
2
…
w
m
)
Theo công thức này, phương pháp tính xác suất sẽ khó được áp dụng trong
thực tế, bởi vì việc tính xác suất dây chuyền như vậy đòi hỏi rất nhiều thông
tin huấn luyện và tiêu tốn nhiều thời gian xử lí. Khi ấy ta tìm giải pháp cho
bài toán tính xác suất của chuỗi từ quy về bài toán tính xác suất của 1 từ với
điều kiện biết các từ trước nó. Đối với những từ ở đầu câu, ta không thể ước
lượng nó do không đủ n-1 từ trước nó. Khi đó, ta có thể thay P(w1) bằng
P(w1|start) là xác suất để w1 đứng đầu chuỗi hay nói cách khác là người ta có
thể đưa thêm kí hiệu đầu dòng start vào mỗi chuỗi. Tương tự như vậy, ta có
thể bổ sung vào công thức tính xác suất của câu giá trị P(stop|w
n
) là xác suất
để từ w
n
xuất hiện ở cuối câu.
Trong thực tế, dựa vào giả thuyết Markov, người ta chỉ tính xác suất của 1
từ dựa vào nhiều nhất n từ liền ngay trước nó, thường n = 0, 1, 2, 3. Do đó,

một từ (w
m
) được coi như chỉ phụ thuộc vào n từ đứng liền ngay trước nó (w
m-
n
w
m-n+1
…w
m-1
), chứ không phải phụ thuộc vào tất cả các từ đứng trước nó (w
1

w
2
…w
m-1
). Như vậy, công thức tính xác suất văn bản như sau:
P(w
1
w
2
…w
m
) = P(w
1
)*P(w
2
|w
1
)*P(w

 Mô hình 2-gram (bigram): Tính xác suất của 1 từ dựa vào 1 từ liền
ngay trước nó.
P=P(bạn|học) 15

 Mô hình 3-gram (trigram): Tính xác suất của 1 từ dựa vào 2 từ liền
ngay trước nó.
P=p(bạn|tày bạn)
1.4.2 Công thức tính “xác suất thô”.
Để sử dụng được, mô hình n-gram cần được cung cấp nhiều thông tin về
xác suất. Các thông tin này được rút trích từ một kho ngữ liệu cho trước, gọi
là kho ngữ liệu huấn luyện.
Gọi C(w
i-n+1
…w
i-1
w
i
) là tần số xuất hiện của chuỗi w
i-n+1
…w
i-1
w
i
trong tập
văn bản huấn luyện.
Gọi P(w
i

i-n+1
w
i-1
w)

Dễ thấy,


w
C(w
i-n+1
w
i-1
w) là tần số xuất hiện của cụm từ w
i-n+1
w
i-1
trong
văn bản huấn luyện. Nên công thức trên viết lại là:
P(w
i
|w
i-n+1
w
i-1
)=
C(w
i-n+1
w
i-1

3
=125
000 000 000. Tuy nhiên, số cụm 3-gram xuất hiện thống kê được chỉ xấp xỉ
1500 000. Như vậy, có rất nhiều cụm 3-gram không xuất hiện hoặc xuất hiện
rất ít nên khả năng nó không xuất hiện trong trong dữ liệu huấn luyện mô hình
là rất dễ xảy ra.
Khi tính toán xác suất của 1 câu, có rất nhiều trường hợp sẽ gặp cụm N-
gram chưa xuất hiện lần nào trong tập dữ liệu huấn luyện. Điều này làm xác
suất của câu bằng 0, trong khi đó có thể là 1 câu hoàn toàn đúng về mặt ngữ
nghĩa và ngữ pháp. Để khắc phục trường hợp này, người ta phải sử dụng một
số phương pháp “làm mịn” kết quả thống kê mà ta sẽ đề cập trong phần 2.1.
1.4.3.2 Kích thước bộ nhớ của mô hình ngôn ngữ.
Khi kích thước tập văn bản huấn luyện lớn, số lượng cụm N-gram và kích
thước mô hình ngôn ngữ cũng lớn, điều này không những khó khăn trong việc
lưu trữ mà còn làm giảm tốc độ xử lí của mô hình ngôn ngữ do bộ nhớ máy
tính là hữu hạn. Để xây dựng mô hình ngôn ngữ hiệu quả, chúng ta phải giảm
kích thước của mô hình ngôn ngữ mà vẫn đảm bảo độ chính xác, điều này
được làm rõ trong phần 2.3. 17CHƯƠNG 2
MÔ HÌNH NGÔN NGỮ N-GRAM
2.1. CÁC KĨ THUẬT LÀM MỊN HÓA SỰ PHÂN BỐ XÁC SUẤT
TRONG MÔ HÌNH N-GRAM ĐỂ TĂNG CHẤT CHẤT LƯỢNG CỦA
MÔ HÌNH.
Do hoàn toàn dựa vào ngữ liệu huấn luyện, mô hình N-gram có một nhược
điểm, đó là khi ngữ liệu không đủ sự dày đặc cần thiết, các xác suất thu được