TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
************************************
BÀI TẬP LỚN
XỬ LÝ NGÔN NGỮ TỰ NHIÊN
ĐỀ TÀI: : Xây dựng bộ tách từ Tiếng Việt

Hà Nội – 05/2012
Giáo viên hướng dẫn : PGS.Lê Thanh Hương
Sinh viên thực hiện : Trần QuangHưng - 20071489
Nguyễn Nam Thanh -
20072552
Đỗ Quang Trường - 20063382
Võ Hải Nam - 20073735
Lớp : HTTT K52
MỤC LỤC
1 MỞ ĐẦU 3
1.1 GIỚI THIỆU 3
1.2 MỘT SỐ ĐẶC ĐIỂM CHÍNH TRONG TIẾNG VIỆT 3
1.3 ĐẶT VẤN ĐỀ 6
2 CÁC PHƯƠNG PHÁP GIẢI QUYẾT BÀI TOÁN 7
2.1 PHƯƠNG PHÁP MAXIMUM MATCHING : FORWARD/ BACKWARD 7
2.2 PHƯƠNG PHÁP GIẢI THUẬT HỌC CẢI BIẾN (TRANSFORMATION-BASED LEARNING,TBL). .8
2.3 MÔ HÌNH TÁCH TỪ WFST VÀ MẠNG NEURAL 9
2.4 PHƯƠNG PHÁP QUY HOẠCH ĐỘNG (DYNAMIC PROGRAMMING) 12
2.5 PHƯƠNG PHÁP TÁCH TỪ TIẾNG VIỆT DỰA TRÊN THỐNG KÊ TỪ INTERNET VÀ THUẬT
TOÁN DI TRUYỀN 13
2.6 PHƯƠNG PHÁP CONDITIOANL RANDOM FIELDS 15
2.7 PHƯƠNG PHÁP TÁCH TỪ KẾT HỢP GIỮA Ô-TÔ-MÁT VÀ XÁC SUẤT THỐNG KÊ 17
3 CÀI ĐẶT 19
4 THỬ NGHIỆM VÀ ĐÁNH GIÁ 21

1.2.1 TIẾNG
Về mặt ngữ âm, tiếng là âm tiết. Âm tiết bao gồm những đơn vị ở bậc
thấp hơn gọi là âm vị. Mỗi âm vị được ghi bằng một ký tự gọi là chữ
Trần QuangHưng - Xây dựng và code chính cho hệ thống
Nguyễn Nam Thanh – Tìm hiểu các phương pháp tách từ
Đỗ Quang Trường – Xây dựng cập nhật bộ từ điển
Về mặt ngữ nghĩa, tiếng là đơn vị nhỏ nhất có nghĩa, nhưng cũng có một
số tiếng không có nghĩa.
Về mặt giá trị ngữ pháp, tiếng là đơn vị cấu tạo từ. Sử dụng tiếng việt để
tạo thành từ, ta có hai trường hợp như sau:
• Từ một tiếng: gọi là từ đơn. Trường hợp này một từ chỉ có duy nhất một
tiếng. Ví dụ: ông, bà…
• Từ hai tiếng trở lên: gọi là từ phức. Trường hợp này một từ có thể có hai
hay nhiều tiếng trở lên. Ví dụ: xã hội, an ninh, hợp tác xã…
1.2.2 TỪ
Có rất nhiều quan niệm về từ trong tiếng Việt , từ nhiều quan niệm về từ
tiếng Việt khác nhau đó chúng ta có thể thấy đặc trưng cơ bản của "từ " là
sự hoàn chỉnh về mặt nội dung, từ là đơn vị nhỏ nhất để đặt câu.
Người ta dùng "từ" kết hợp thành câu chứ không phải dùng "tiếng" do
đó quá trình lập chỉ mục bằng cách tách câu thành các "từ" cho kết qua
tốt hơn là tách câu bằng “tiếng”.
Theo trung tâm từ điển Vietlex
1
thì từ vựng trong tiếng việt có 40,181
từ, nó ngày càng được mở rộng dùng trong giao tiếp, báo chí và văn học.
Những từ đó được tạo thành bởi 7,729 tiếng.
Có một vài điều thú vị khi thống kê độ dài của từ với thước đo là số âm
tiết như Bảng 2 -1 dưới đây. Đầu tiên có khoảng 81.55% tiếng tạo ra từ,
người ta gọi đó là từ đơn; 15,69% từ là từ đơn âm tiết. Thứ hai, có 70,72%
từ ghép được tạo ra từ hai âm tiết. Cuối cùng, có 13,59% từ được ghép từ ít

xác định mặc nhiên bằng khoảng
trắng
• 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 kèm theo
với danh từ, như: cái bàn, cuốn
sách, bức thư, con chó, con
• Là loại hình biến cách
(flexion) hay còn gọi là loại hình
khuất chiết
• Từ có biến đổi hình thái, ý
nghĩa ngữ pháp nằm ở trong từ.
Ví dụ: I see him và He sees me.
• Phương thức ngữ pháp chủ
yếu là : phụ tố.
Ví dụ: studying và studied
• Kết hợp giữa các hình vị là
chặt chẽ, khó xác định, được nhận
diện bằng khoảng trắng hoặc dấu
câu.
• Hiện tượng cấu tạo bằng từ
ghép thêm phụ tố (affix) vào gốc từ
là rất phổ biến.
Ví dụ: anticomputerizational
( anticompute-er-ize-ation-al)
sông,vì sao…
• Có hiện tượng láy và nói lái
trong tiếng Việt
Ví dụ: lấp lánh, lung linh
Hiện đại -> hại điện, thầy giáo->

đến khi tìm được từ dài nhất. Từ có vẻ hợp lý nhất sẽ là từ dài nhất. Chọn từ
đó, sau đó tìm tiếp như trên cho những từ còn lại cho đến khi xác định được
toàn bộ chuỗi từ.
Dạng phức tạp: Quy tắc của dạng này là phân đoạn có vẻ hợp lý nhất là
đoạn ba từ với chiều dài tối đa. Thuật toán bắt đầu như dạng đơn giản. Nếu
phát hiện ra những cách tách từ gây nhập nhằng (ví dụ, C1 là từ và C1C2
cũng là từ), ta xem các chữ kế tiếp để tìm tất cả các đoạn ba từ có thể có bắt
đầu với C1 hoặc C1C2. Ví dụ ta được những đoạn sau:
C1C2 C3 C4
C1C2 C3 C4 C5
C1C2 C3 C4 C5 C6
Chuỗi dài nhất sẽ là chuỗi thứ ba. Vậy từ đầu tiên của chuỗi thứ ba
(C1C2) sẽ được chọn. Thực hiện lại các bước cho đến khi được chuỗi từ
hoàn chỉnh.
2.1.2 ƯU ĐIỂM
• Với cách này, ta dễ dàng tách được chính xác các ngữ/câu như “ hợp
tác xã ||mua bán”, “thành lập || nước || Việt Nam || dân chủ || cộng hòa”
• Cách tách từ đơn giản, nhanh, chỉ cần dựa vào từ điển
• Trong tiếng Hoa, cách này đạt được độ chính xác 98,41% Error:
Reference source not found
2.1.3 NHƯỢC ĐIỂM
• Độ chính xác của phương pháp phụ thuộc hoàn toàn vào tính đủ và
tính chính xác của từ điển
• Phương pháp này sẽ tách từ sai trong các trường hợp “ học sinh || học
sinh|| học”, “một || ông || quan tài || giỏi”, “trước || bàn là || một || ly ||
nước”…
2.2 PHƯƠNG PHÁP GIẢI THUẬT HỌC CẢI BIẾN
(TRANSFORMATION-BASED LEARNING,TBL)
2.2.1 NỘI DUNG
Đây là cách tiếp cận dựa trên ngữ liệu đã đánh dấu. Theo cách tiếp cận này,

từ trong ngữ liệu. Dùng WFST để duyệt qua câu cần xét. Cách duyệt có
trọng số lớn nhất (hay bé ???) sẽ là cách tách từ được chọn. Giải pháp này
cũng đã được áp dụng trong Error: Reference source not found kèm với
mạng neutral để khử nhập nhằng. Hệ thống tách từ tiếng Việt của Đinh
Điền et al Error: Reference source not found gồm hai tầng: tầng WFST
ngoài việc tách từ còn xử lý thêm các vấn đề liên quan đến đặc thù của
tiếng Việt như từ láy, tên riêng… và tầng mạng neural dùng để khử nhập
nhằng nếu có.
 Tầng WFST :gồm có ba bước
 Xây dựng từ điển trọng số : theo mô hình WFST, việc phân đoạn từ được
xem như là một sự chuyển dịch trạng thái có xác suất (Stochastic
Transduction). Chúng ta miêu tả từ điển D là một đồ thị biến đổi trạng thái
hữu hạn có trọng số. Giả sử:
• H: là tập các từ chính tả tiếng Việt (còn gọi là “tiếng”)
• P: là từ loại của từ (POS: Part – Of – Speech).
Mỗi cung của D có thể là:
• Từ một phần tử của H tới một phần tử của H, hoặc
• Từ ε (ký hiệu kết thúc từ) tới một phần tử của P
Các nhãn trong D biểu thị một chi phí ước lượng (estimated cost) bằng
công thức :
Cost = - log(f/N)
• Với f: tần số của từ, N: kích thước tập mẫu.
Đối với các trường hợp từ mới chưa gặp, tác giả áp dụng xác suất có điều
kiện Goog-Turning (Baayen) để tính toán trọng số.
 Xây dựng các khả năng phân đoạn từ : Để giảm sự bùng nổ tổ hợp khi
sinh ra các dãy các từ có thể từ một dãy các tiếng trong câu, tác giả đề xuất
một phương pháp mới là kết hợp dùng từ điển để hạn chế sinh ra các bùng
nổ tổ hợp. Khi phát hiện thấy một cách phân đoạn từ nào đó không phù hợp
(không có trong từ điển, không phải là từ láy, không phải là danh từ
riêng…) thì tác giả loại bỏ các nhánh xuất phát từ cách phân đoạn từ đó.

2.3.3 NHƯỢC ĐIỂM
Cũng tương tự như phương pháp TBL, việc xây dựng tập ngữ liệu là rất
công phu, nhưng thật sự rất cần thiết để phục vụ cho mục đích dịch máy sau
này của tác giả
2.4 PHƯƠNG PHÁP QUY HOẠCH ĐỘNG (DYNAMIC
PROGRAMMING)
2.4.1 NỘI DUNG
• Phương pháp quy hoạch động được đưa ra bởi Lê An Hà Error:
Reference source not found chỉ sử dụng tập ngữ liệu thô để lấy thông tin về
tần số thống kê của từ , làm tăng độ tin cậy cho việc tính toán. Việc tính
toán bắt đầu với những đơn vị chắc chắn như câu, các cụm từ (chunk) được
phân cách bởi dấu câu ( như dấu phẩy, gạch nối, chấm phẩy…) vì những
thành phần này không có tính nhập nhằng ngay cả trong văn viết cũng như
nói. Sau đó, tác giả cố gắng tối đa hoá xác suất của ngữ bằng cách tìm ra
nhiều cách tách ngữ đó. Cách tách cuối cùng là cách tách là cho cụm từ đó
có xác suất cao nhất. Ý tưởng của cách tách từ này cho một ngữ cần tách từ,
ta phải tìm ra các tổ hợp từ tạo nên ngữ đó sao cho tổ hợp đó đạt được xác
suất tối đa. Tuy nhiên trong phương pháp tính toán này, tác giả gặp phải
vấn đề bùng nổ tổ hợp và phân tích ngữ liệu thô. Để giải quyết vấn đề trên,
tác giả đã sử dụng phương pháp quy hoạch động (dynamic programming) vì
lúc đó, xác suất cực đại của một ngữ nhỏ hơn chỉ phải tính toán một lần và
sử dụng lại trong các lần sau.
2.4.2 ƯU ĐIỂM
Không cần sử dụng tập ngữ liệu đã đánh dấu chính xác
2.4.3 NHƯỢC ĐIỂM
• Trong thí nghiệm, tác giả chỉ dừng lại ở việc tách các từ có ba tiếng
bởi vì tập ngữ liệu đầu vào vẫn còn khá nhỏ.
• Xác suất từ đúng là 51%, xác suất từ chấp nhận được 65% Error:
Reference source not found. Xác suất này tương đối thấp so với các phương
pháp tách từ khác đã đề cập ở trên.

wp
)(
)(
=

MAX
wwcount
wwp
)&(
)&(
21
21
=
Trong đó, MAX= 4 * 10
9
count(w) số lượng văn bản trên Internet tìm thấy có chứa từ w hoặc cùng
chứa w
1
và w
2
đối với count(w
1
& w
2
)
o Tính độ xác suất phụ thuộc của một từ lên một từ khác

)(
)&(
)|(

21
)& &&()(
)& &&(
)(

GA Engine for Text Segmentation : mỗi cá thể trong quần thể được
biểu diễn bởi chuỗi các bit 0,1, trong đó, mỗi bit đại diện cho một tiếng
trong văn bản, mỗi nhóm bit cùng loại đại diện cho một segment.
o Các cá thể được khởi tạo ngẫu nhiên, trong đó, mỗi segment được giới
hạn trong khoảng 5. GA engine sau đó thực hiện các bước đột biến và lai
ghép nhằm mục đích làm tăng giá trị fitness của các cá thể, để đạt được
cách tách từ tốt nhất có thể.

Text Categorization : tác giả dùng độ hỗ trợ (support degree) của văn
bản cần phân loại cho các từ khoá để phân loại văn bản.
2.5.2 ƯU ĐIỂM
• Không cần sử dụng bất cứ tập huấn luyện hoặc từ điển nào
• Phương pháp tương đối đơn giản.
• Không tốn thời gian huấn luyện
2.5.3 NHƯỢC ĐIỂM
• So với các phương pháp trước, IGATEC có độ chính xác thấp hơn
LRMM
• và WFST nhưng vẫn chấp nhận được đối với mục đích tách từ dành cho
phân loại văn bản.
• Thời gian chạy ban đầu khá chậm do phải lấy thông tin từ Internet mà
đường truyền ở Việt Nam còn hạn chế.
• Chưa có các thử nghiệm trên tập dữ liệu đủ lớn.
2.6 PHƯƠNG PHÁP CONDITIOANL RANDOM FIELDS
2.6.1 NỘI DUNG
Mô hình CRFs được đưa ra bởi nhóm tác giả Nguyễn Cẩm Tú Error:

T
t k
ttkk
tossf
z
osp
1
1
),,,(exp
)0(
1
)|(
λ
θ
(1)
Gọi
∑ ∑∑






=
=
−
'
1
1
),','(exp)(

(s
t-1
,s
t
,t) = δ(s
t-1
,l) δ(s
t
,l). (3)
Ở đây δ là Kronecker-δ. Mỗi đặc trưng trạng thái (2) kết hợp nhãn l của
trạng thái hiện tại s
t
và một vị từ ngữ cảnh – một hàm nhị phân x
k
(o, t) xác
định các ngữ cảnh quan trọng của quan sát o tại vị trí t. Một đặc trưng
chuyển (3) biểu diễn sự phụ thuộc chuỗi bằng các kết hợp nhãn l‟ của trạng
thái trước s
t-1
và nhãn l của trạng thái hiện tại s
t
. Người ta thường huấn
luyện CRFs bằng cách làm cực đại hóa hàm likelihood theo dữ liệu huấn
luyện sử dụng các kỹ thuật tối ưu như L-BFGS. Việc lập luận (dựa trên mô
hình đã học) là tìm ra chuỗi nhãn tương ứng của một chuỗi quan sát đầu
vào.
2.6.2 ƯU ĐIỂM
Đạt độ chính xác khá cao (94%)
2.6.3 NHƯỢC ĐIỂM
• Phải xây dựng tập huấn luyện và các model rất công phu và phức tạp. Hơn

Q là tập trạng thái kết thúc.
∑ là tập các ký tự hữu hạn, là các chữ cái trong bảng chữ cái alphabet.
δ là một ánh xạ δ: Q x
∑

→
Q biểu diễn quá trình chuyển đổi.
Khi δ(q,a) không xác định thì δ(q,a) =
⊥
.
Mở rộng ánh xạ δ tới một phần ánh xạ δ
*
: Q x
∑

→
Q như sau ( với
a
∈∑
, x
∈

∑
*
)
2
http://www.pg.gda.pl/~jandac/fsa.html
Lấy DAFSA (Deterministic, acyclic, finite-state automata) là tập tất cả
Ô-tô-mát hữu hạn trạng thái xác định trong hàm chuyển đổi δ là không tuần
hoàn – sẽ không tồn tại xâu w và trạng thái q như sau δ

∈

∑
*
| δ
*
(q,x)
∈
F}
(q) gọi là ngôn ngữ đúng (right language) của q. Lưu ý rằng L(M)=
(q
0
). Ngôn ngữ đúng của một trạng thái có thể được định nghĩa đệ quy:
(q) = { a (δ(q,a)) | a
∈
∑ δ(q,a)
≠

⊥
) ∪
Định nghĩa một thuộc tính của một Ô-tô-mát chỉ rõ rằng tất cả các trạng
thái mà nó có thể tới được từ trạng thái bạn đầu:
Reachable(M)
≡

∀
q
∈
Q
∃

≠
q’
⇒
(q’)))
∧
Reachable(M)
Xử lý tối thiểu Ô-tô-mát được đưa ra bởi Watson et al Error: Reference
source not found và tính chính xác của giải thuật được chứng minh bởi
Mihov et al Error: Reference source not found.
2.7.2 ƯU ĐIỂM
• Độ chính xác cao
2.7.3 NHƯỢC ĐIỂM
• Cài đặt phức tạp
3 CÀI ĐẶT
Trong bài toán này nhóm chúng em sẽ sử dụng phương pháp so khớp cực
đại.
Các bước giải quyết :
-Xây dựng từ điển.
-Tìm từ trong từ điển : xác định tất cả các từ có trong câu
- Liệt kê tất cả các câu có thể.
-Phân giải nhập nhằng : sử dụng phương pháp so khớp cực đại đưa ra câu có số từ ít nhất
Xây dựng từ điển : bao gồm một tập các file dữ liệu từ điển dưới dạng
chuẩn XML được tổ chức như sau :
<Dictionary>
<LexicalEntry>
<HeadWord>a</HeadWord>
<Morphology>
<WordType>symbol</WordType>
</Morphology>
<Syntactic>

kết thúc, danh sách các từ loại của từ.
-Xác định các câu từ danh sách các từ tìm được : sử dụng giải thuật đệ
quy xây dựng lại các câu từ danh sách các từ tìm được.
-Xác định câu được chấp nhận : theo phương pháp so khớp dài nhất.
4 THỬ NGHIỆM VÀ ĐÁNH GIÁ
Giao diện chương trình :
21
Thử nghiệm :
Kết quả chương trình đối với một số câu :
-Nếu nhà máy nghỉ thì ta đi về
Danh sách các từ :
[0,1:nếu(C)]
[1,2:nhà(N)]
[1,3:nhà máy(N)]
[2,3:máy(V,A,N)]
[3,4:nghỉ(V)]
[4,5:thì(I,C,N)]
[5,6:ta(A,N,P)]
[6,7:đi(R,I,V)]
[7,8:về(C,V)]
Các cách tách từ :
nếu|nhà|máy|nghỉ|thì|ta|đi|về
nếu|nhà máy|nghỉ|thì|ta|đi|về => Lựa chọn
-Ông già đi nhanh quá
Danh sách các từ :
[0,1:ông(N,L)]
[0,2:ông già(N)]
[1,2:già(N,A)]
[2,3:đi(R,I,V)]
[3,4:nhanh(A)]

Sống|chiến đấu|lao|động|học tập|theo|gương|BácHồ|vĩ|đại
Sống|chiến|đấu|lao động|học tập|theo|gương|BácHồ|vĩ|đại
Sống|chiến|đấu|lao|động|học tập|theo|gương|BácHồ|vĩ|đại
Sống|chiến đấu|lao động|học tập|theo|gương|BácHồ|vĩ đại => Lựa chọn
Sống|chiến đấu|lao động|học|tập|theo|gương|BácHồ|vĩ đại
Sống|chiến đấu|lao|động học|tập|theo|gương|BácHồ|vĩ đại
Sống|chiến đấu|lao|động|học tập|theo|gương|BácHồ|vĩ đại
Sống|chiến|đấu|lao động|học tập|theo|gương|BácHồ|vĩ đại
Sống|chiến đấu|lao|động|học|tập|theo|gương|BácHồ|vĩ đại
Sống|chiến|đấu|lao động|học|tập|theo|gương|BácHồ|vĩ đại
Sống|chiến|đấu|lao|động học|tập|theo|gương|BácHồ|vĩ đại
Sống|chiến|đấu|lao|động|học tập|theo|gương|BácHồ|vĩ đại
Sống|chiến|đấu|lao|động|học|tập|theo|gương|BácHồ|vĩ đại
Đánh giá hệ thống :
-Kết quả thu được của chương trình là khá chính xác, song vẫn chưa thể xử
lý hết các trường hợp nhập nhằng khi các từ có câu có cùng số từ vựng.
-Độ chính xác của hệ thống phụ thuộc nhiều vào phong phú của từ điển.
-Không xử lý được các tổ hợp từ cố định, ví dụ : “ông chẳng bà chuộc”…
Một số giải pháp đề xuất :
-Về vấn đề xử lý nhập nhằng, có thể áp dụng thêm một số phương pháp như
xử lý cú pháp, xác suất thống kê để xử lý các trường hợp nhập nhằng.
-Đối với các vấn đề các tổ hợp từ cố định, có thể đưa ra tất cả các từ ghép
có trong phần đầu của xâu vào
23
5 KẾT LUẬN
Sau thời gian nghiên cứu và cài đặt chương trình tách từ cho văn bản
tiếng Việt sử dụng kỹ thuật Ô-tô-mát kết hợp với xác suất thống kê, em đã
có thêm rất nhiều kiến thức về bài toán tách từ tiếng việt, hiểu được bản
chất của kỹ thuật Ô-tô-mát và mô hình n-gram. Hệ thống tìm kiếm tài liệu
tiếng Việt theo lĩnh vực chuyên sâu cũng đã dần được hoàn thiện và bước