TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG


Bài tập lớn: Xử lý ngôn ngữ tự nhiên
Đề tài : Tìm hiểu phương pháp tách từ trong văn bản tiếng
việt theo hướng tiếp cận của giải thuật di truyền.
Giảng viên hướng dẫn: PGS.TS Lê Thanh Hương
Sinh viên thực hiện:
1- Nguyễn Thị Thúy. 20082599
2- Lương Thị Hoài Thu 20082588
3- Nguyễn Đình Hưởng 20081338
4- Nguyễn Phước Thọ 20082562

XỬ LÝ NGÔN NGỮ TỰ NHIÊN
HỆ THỐNG THÔNG TIN K53
Hà Nội, 04/2012
MỤC LỤC
MỤC LỤC 2
I.Tổng quan 3
1.Đặt vấn đề 3
2.Tách từ Tiếng Việt 3
II.Các phương pháp tách từ hiện nay 4
1.2.Nhận xét 4
3.2. Học dựa trên sự cải biến (Transformation-based Learning -TBL) 7
3.3. Chuyển đổi trạng thái trọng số hữu hạn (Weighted- Finite State Transducer- WFST)
8
3.4. Phương pháp tách từ dựa trên thống kê từ trên Internet và giải thuật di truyền.
(Internet and Genetics Algorithm-based Text Categorization for Documents in
Vietnamese - IGATEC) 10
IV.Phương pháp tách từ dựa trên thống kê Internet theo hướng tiếp cận của giải thuật di

cách. Tuy nhiên trong tiếng Việt, dấu cách được dùng để phân tách các
tiếng (âm tiết) chứ không phải từ. Cùng với các ngôn ngữ như tiếng Trung,
tiếng Hàn,tiếng Nhật, phân tách từ trong tiếng Việt là một công việc không
hề đơn giản.
2. Tách từ Tiếng Việt
Đối với tiếng Anh hoặc các ngôn ngữ không đơn lập khác “từ là một nhóm
các kí tự có nghĩa được tách biệt bằng khoảng trắng trong câu” do vậy việc
tách từ trở nên rất đơn giản.
Còn đối với ngôn ngữ đơn lập như tiếng Việt, tiếng Hán, tiếng Thái … lại là
một bài toán khó. Bởi những đặc tính chính của ngôn ngữ đơn lập như sau:
 Từ ở dạng nguyên thể , hình thức và ý nghĩa của từ độc lập với cú pháp
 Từ được cấu trúc từ tiếng.
 Từ bao gồm từ đơn và từ phức (bao gồm từ láy và từ ghép).
Phương pháp tách tách từ tiếng Việt dựa trên thống kê từ Internet và thuật giải
di truyền – IGATEC (Internet and Genetics Algorithm based Text
Categorization for Documents in Vietnamese) do H. Nguyễn đề xuất năm
2005 như một hướng tiếp cận mới trong tách từ với mục đích phân loại văn
bản mà không cần dùng đến một từ điển hay tập ngữ liệu học nào.
Vì vậy trong nội dung bài tập lớn này chúng em sẽ tìm hiểu về phương pháp
3
XỬ LÝ NGÔN NGỮ TỰ NHIÊN
IGATEC và demo phương pháp sử dụng open source Vntokenizer.
II. Các phương pháp tách từ hiện nay
1. Vấn đề tách từ Tiếng Việt
1.1. So sánh giữa tiếng Anh và tiếng Việt.
Những đặc điểm chính của tiếng anh và tiếng Việt:
Tiếng Việt Tiếng Anh
- Là ngôn ngữ đơ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 âm tiết.

 Phương thức ngữ pháp chủ yếu là trật tự từ nên nếu áp dụng phương pháp
tính xác xuất xuất hiện của từ có thể không chính xác như mong đợi.
 Ranh giới từ không được xác định mặc định bằng khoảng trắng. Đ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ỏe nên khó khăn.
Việc nhận diện ranh giới từ là quan trọng và làm tiền đề cho các xử lý tiếp
theo sau đó. như: kiểm tra lỗi chính tả, gán nhãn từ loại, thống kê tần suất
từ
 Vì tiếng Anh và tiếng Việt có những điểm khác biệt nên chúng ta không
thể áp dụng y nguyên các thuật toán tiếng Anh cho tiếng Việt.
2. Các hướng tiếp cận của kĩ thuật tách từ tiếng Việt
Dựa vào các kĩ thuật tách từ của tiếng Hán, và những điểm tương đồng giữa tiếng
4
XỬ LÝ NGÔN NGỮ TỰ NHIÊN
Việt và tiếng Hán. Chúng ta có thể xây dựng sơ đồ các hướng tiếp cận của kĩ thuật
tách từ tiếng Việt:
II.1. Hướng tiếp cận dựa trên từ (Word-based approaches)
Hướng tiếp cận dựa trên từ với mục tiêu tách được các từ hoàn chỉnh trong câu.
5
Hybrid
Hybrid
Vietnamese
segmentation
Vietnamese
segmentation
Word-based
Word-based
Character-based
Character-based
Statistic
Statistic

khớp ngắn nhất (shortest match) và so khớp kết hợp (overlap). Trong
so khớp kết hợp mỗi chuỗi được phát sinh từ văn bản có thể chồng lấp
lên chuỗi khác nếu chuỗi đó có trong từ điển.
Hiện nay thì hướng tiếp cận so khớp dài nhất được xem là phương
pháp quan trọng và có hiệu quả nhất trong hướng tiếp cận dựa trên từ
điển.
• Hướng tiếp cận hybrid: Với mục đích kết hợp các hướng tiếp cận khác
nhau để thừa hưởng được các ưu điểm của nhiều kỹ thuật và các hướng
tiếp cận khác nhau nhằm nâng cao kết qủa . Hướng tiếp cận này
thường kết hợp giữa hướng dựa trên thống kê và dựa trên từ điển nhằm
tận dụng các mặt mạnh của các phương pháp này . Tuy nhiên hướng
tiếp cận Hybrid lại mất nhiều thời gian xử lý , không gian đĩa và đòi
hỏi nhiều chi phí.
II.2. Hướng tiếp cận dựa trên kí tự
Trong tiếng việt, hình vị nhỏ nhất là “tiếng” được hình thành bởi nhiều ký tự trong
bảng chữ cái . Hướng tiếp cận này đơn thuần rút trích ra một số lượng nhất định các
tiếng trong văn bản như rút trích từ 1 ký tự (unigram) hay nhiều ký tự (n-gram) và
cũng mang lại một số kết qủa nhất định được minh chứng thông qua một số công trình
nghiên cứu đã được công bố , như của tác giả Lê An Hà [2003] xây dựng tập ngữ liệu
thô 10MB bằng cách sử dụng phương pháp qui hoạch động để cựa đại hóa xác suất
xuất hiện của các ngữ.Rồi công trình nghiên cứu của H. Nguyễn[2005] làm theo
hướng tiếp cận là thay vì sử dụng ngữ liệu thô , công trình tiếp cận theo hướng xem
Internet như một kho ngữ liệu khổng lồ , sau đó tiến hành thống kê và sử dụng thuật
giải di truyền để tìm cách tách từ tối ưu nhất , và một số công trình của một số tác giả
khác.Khi so sánh kết qủa của tác giả Lê An Hà và H.Nguyễnt thì thấy công trình của
H.Nguyễn cho được kết qủa tốt hơn khi tiến hành tách từ , tuy nhiên thời gian xử lý
lâu hơn.Ưu điểm nổi bật của hướng tiếp cận dựa trên nhiều ký tự là tính đơn giản , dễ
ứng dụng , ngoài ra còn có thuận lợi là ít tốn chi phí cho thao tác tạo chỉ mục và xử lý
nhiều câu truy vấn.Qua nhiều công trình nghiên cứu của các tác giả đã được công bố ,
hướng tiếp cận tách từ dựa trên nhiều ký tự , cụ thể là cách tách từ hai ký tự được cho

1 Tôi là sinh viên trường đại học Bách Khoa Hà Nội
2 Là sinh viên trường đại học Bách Khoa Hà Nội
3 Sinh viên trường đại học Bách Khoa Hà Nội
4 Trường đại học Bách Khoa Hà Nội
5 Đại học Bách Khoa Hà Nội
6 Bách Khoa Hà Nội
7 Hà Nội
Ưu điểm:
- Tách từ nhanh đơn giản chỉ cần dựa vào từ điển.
- Độ chính xác tương đối cao.
Hạn chế:
- Độ chính xác phụ thuộc vào hoàn toàn vào tính đầy đủ và chính xác của từ
điển.
- Phương pháp này sẽ không đạt được kết quả nếu chuối từ trước có liên hệ với
các từ sau. Ví dụ : một ông quan tài giỏi => một ||ông|| quan tài|| giỏi.
3.2. Học dựa trên sự cải biến (Transformation-based Learning -TBL)
Đâ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, để
huấn luyện cho máy tính biết cách nhận diện ranh giới từ tiếng Việt, ta có thể cho
máy “học” trên ngữ liệu hàng vạn câu tiếng Việt đã được đánh dấu ranh giới từ
7
XỬ LÝ NGÔN NGỮ TỰ NHIÊN
đúng.
Sau khi học xong, máy sẽ xác định được các tham số (các xác suất) cần thiết cho
mô hình nhận diện từ.
Ưu điểm:
- Đặc điểm của phương pháp này là khả năng tự rút ra quy luật của ngôn ngữ.
- Nó có những ưu điểm của cách tiếp cận dựa trên luật nhưng nó khác phục được
khuyết điểm của việc xây dựng các luật một cách thủ công bởi các chuyên gia.
- Các luật được thử nghiệm tại chỗ để đánh giá độ chính xác và hiệu của luật
(dựa trên ngữ liệu huấn luyện).

- 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:
8
XỬ LÝ NGÔN NGỮ TỰ NHIÊN
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 khả năng phân đoạn từ: để giảm bớt 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ừ đó.
 Lựa chon khả năng phân đoạn từ tối ưu: Sau k hi được
một danh sách các cách phân đoạn từ có thể có của câu,
tác giả chọn trường hợp phân đoạn có trọng số bé nhất
như sau:
- Ví dụ: input = “Tốc độ truyền thong tin sẽ cao”
• Dictionary “tốc độ” 8.68
“truyền” 12.31
“truyền thông” 12.31
“thông tin” 7.24
“tin” 7.33
“sẽ” 6.09
“tăng” 7.43

Hạn chế
- 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ự cần rất cần thiết để phục vụ cho mục đích dịch máy sau này.
3.4. Phương pháp tách từ dựa trên thống kê từ trên Internet và giải thuật di truyền.(Internet
and Genetics Algorithm-based Text Categorization for Documents in Vietnamese -
IGATEC)
Phương pháp tách tách từ tiếng Việt dựa trên thống kê từ Internet và thuật giải
di truyền – IGATEC (Internet and Genetics Algorithm based Text Categorization for
Documents in Vietnamese) do H. Nguyễn đề xuất năm 2005 như một hướng tiếp cận
mới trong tách từ với mục đích phân loại văn bản mà không cần dùng đến một từ điển
hay tập ngữ liệu học nào . Trong hướng tiếp cận này , tác giả kết hợp giữa thuật toán
di truyền với dữ liệu thống kê được lấy từ Internet.
Hệ thống bao gồm :2 phần
a. Online Extractor : Thành phần này có tác dụng lấy thông tin về tần số xuất hiện của
các từ trong văn bản bằng cách sử dụng một search engine nổi tiếng như Google hay
Yahoo chẳng hạn . Sau đó , tác giả sử dụng các công thức dưới đây để tính toán mức độ
phụ thuộc lẫn nhau (mutual information) để làm cơ sở tính fitness cho GA engine.
• Tính xác suất các từ xuất hiện trên Internet :
( )
MAX
)
w
2
&
w
1
count(
)
w
2

• Tính xác suất độ phụ thuộc của một từ lên một từ khác :

( )
w
1
p
)
w
2
&
w
1
p(
)
w
2
|
w
1
p(
=
Thông tin phụ thuộc lẫn nhau (mutual information) của các từ ghép được cấu tạo bởi n
tiếng ( cw = w1w2…wn)

( )
∑
=
−
=
n

cá thể để đạt được cách tách từ tốt nhất có thể.
Uu đ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.
Hạn chế:
- 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 được chấp nhận đố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ó thử nghiệm trên các tập dữ liệu đủ lớn.
3.5. Học máy sử dụng mô hình Markov ẩn (Hidden Markov Models-HMM)
Phương pháp tách từ dựa trên HMM và từ điển:
Áp dụng mô hình Markov ẩn ta có thể mô hình hóa để đưa bài toán tách từ về một mô
hình xác xuất dưới dạng một bài toán tối ưu. Tiếp đó, thuật toán quy hoạch động
Viterbi sẽ giải quyết bài toán tối ưu đó
- Trước hết ta sẽ đưa ra công thức để tính xác suất một phân hoạch.
Đây cũng chính là công thức đo độ tốt của một phân hoạch. Xác suất càng cao thì khả
11
XỬ LÝ NGÔN NGỮ TỰ NHIÊN
năng đúng của phân hoạch đó càng lớn. Vì thế bài toán của ta đưa về bài toán tối ưu
cho hàm mục tiêu là hàm xác suất của phân hoạch.
- Ta ký hiện phân hoạch đang xét là W = W1 W¬2 W3 …Wm
- Hàm mục tiêu:
P(W) =П P(W1) = П P(Wi+j|W)
Trong đó: P(Wi): xác xuất của Wi
P(Wi + 1|Wi): Xác suất chuyển từ Wi sang Wi+1.
Các xác suất này được tính từ dữ liệu thu thập được, ở đây là các văn bản bằng tiếng
Việt. Nếu ta hướng đến bài toán tách từ tổng quát thì các văn bản này phải đảm bảo
không bị quá thiên lệch về một lĩnh vực nào. Tất nhiên tùy vào mục tiêu sử dụng

cứu đã được công bố đều chỉ ra rằng phương pháp tách từ dựa trên từ mang lại kết qủa
có độ chính xác khá cao , điều này có được nhờ vào tập huấn luyện lớn , được đánh dấu
12
XỬ LÝ NGÔN NGỮ TỰ NHIÊN
ranh giới giữa các từ chính xác giúp cho việc học để rút ra các luật để tách từ cho các
văn bản khác được tốt đẹp , tuy nhiên chúng ta cũng dễ nhận thấy hiệu suất của phương
pháp hoàn toàn phụ thuộc vào tập ngữ liệu huấn luyện. Do đó để khắc phục sự
phụ thuộc của từ điển, chúng ta đề nghị sử dụng hướng tiếp cận của H.Nguyễn (sẽ được
trình bày chi tiết trong phần sau ) để tách từ .
Hướng tiếp cận dựa trên ký tự có ưu điểm là dễ thực hiện , thời gian thực hiện tương
đối nhanh , tuy nhiên lại cho kết qủa không chính xác bằng hướng tiếp cận dựa trên từ .
Hướng tiếp cận này nói chung phù hợp cho các ứng dụng không cần độ chính xác tuyệt
đối trong tách từ văn bản như ứng dụng lọc spam mail , firewall ,…Nhìn chung với
hướng tiếp cận này nếu chúng ta có thể cải tiến để nâng cao độ chính xác trong tách từ
thì hướng tiếp cận này là hoàn toàn khả thi và có khả năng thay thế hướng tiếp cận tách
từ dựa trên từ vì đã không phải xây dựng kho ngữ liệu , một công việc đòi hỏi nhiều
công sức , thời gian và sự hỗ trợ của các chuyên gia trong các lĩnh vực khác nhau.
III. Giải thuật di truyền.
1. Tổng quan về giải thuật di truyền
Giải thuật di truyền là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải
pháp thích hợp cho các bài toán tối ưu tổ hợp (combinatorial optimization). Giải thuật
di truyền là một phân ngành của giải thuật tiến hóa vận dụng các nguyên lý của tiến
hóa như di truyền, đột biến, chọn lọc tự nhiên, và trao đổi chéo.
Giải thuật di truyền thường được ứng dụng nhằm sử dụng ngôn ngữ máy tính để
mô phỏng quá trình tiến hoá của một tập hợp những đại diện trừu tượng (gọi là những
nhiễm sắc thể) của các giải pháp có thể (gọi là những cá thể) cho bài toán tối ưu hóa
vấn đề. Tập hợp này sẽ tiến triển theo hướng chọn lọc những giải pháp tốt hơn.
Thông thường, những giải pháp được thể hiện dưới dạng nhị phân với những
chuỗi 0 và 1, nhưng lại mang nhiều thông tin mã hóa khác nhau. Quá trình tiến hóa
xảy ra từ một tập hợp những cá thể hoàn toàn ngẫu nhiên ở tất cả các thế hệ. Trong

- Thay đổi giá trị của gen thứ k
- Đưa nhiễm sắc thể con vào quần thể để tham gia quá trình tiến hóa tiếp theo
• Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn)
- Phép tái sinh: là quá trình các cá thể được sao chép dựa trên độ thích nghi của nó. Độ
thích nghi là một hàm được gán các giá trị thực cho các cá thể trong quần thể của nó.
Phép tái
sinh có thể mô phỏng như sau:
- Tính độ thích nghi của từng cá thể trong quần thể, lập bảng cộng dồn các giá trị thích
nghi đó (theo thứ tự gán cho từng cá thể) ta được tổng độ thích nghi. Giả sử quần thể
có n cá
thể. Gọi độ thích nghi của cá thể thứ i là Fi, tổng dồn thứ i là Ft.Tổng độ thích nghi là
Fm .
- Tạo số ngẫu nhiên F có giá trị trong đoạn từ 0 đến Fm
- Chọn cá thể k đầu tiên thỏa mãn F ≥ Ft đưa vào quần thể của thế hệ mới.
- Phép chọn: là quá trình loại bỏ các cá thể xấu và để lại những cá thể tốt. Phép chọn
được mô tả như sau:
+ Sắp xếp quần thể theo thứ tự độ thích nghi giảm dần
+ Loại bỏ các cá thể cuối dãy, chỉ để lại n cá thể tốt nhất.
14
XỬ LÝ NGÔN NGỮ TỰ NHIÊN

Cấu trúc thuật giải di truyền tổng quát
Bắt đầu
t =0;
Khởi tạo P(t)
Tính độ thích nghi cho các cá thể thuộc P(t);
Khi (điều kiện dừng chưa thỏa) lặp
t=t+1;
Chọn lọc P(t)
Lai P(t)

bit cùng loại đại diện cho cho một segment. Các cá thể trong quần 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ể.
2.1.Công cụ trích xuất thông tin từ Google
Chúng ta chọn Google là công cụ tìm kiếm bởi những ưu thế về tính nhanh chóng, chính
xác và phổ biến của nó so với các công cụ tìm kiếm khác.
Nhiệm vụ của công cụ trích xuất thông tin từ Google sẽ lấy thông tin về:
- Tần số xuất hiện của các văn bản chứa từ (document frequency) trên các trang web để
thực hiện tính toán theo công thức MI, dự đoán khả năng tồn tại của một từ.
- Tần số các văn bản chứ từ với từ khóa đại diện cho chủ để dùng để tính mức độ liên
quan của từ với các loại chủ đề cần phân loại.
Các công thức tính xác suất và độ tương hỗ
2.1.1. Các công thức tính xác suất
Dựa vào nền tảng của các công trình nghiên cứu thống kê trên Internet của Rudi và
Paul (2005).
Các công thức tính xác suất từ xuất hiện trên Internet.
 Gọi count(w) là số lượng trang web chứ từ w;
count(w
1
&w
2
) là số trang web chứa đồng thời w
1
&w
2


16
XỬ LÝ NGÔN NGỮ TỰ NHIÊN

n
& &
w
2
&
w
1
p(
MI(cw)
 Hoặc sử dụng công thức MI cải tiến như sau :
 Giả sử ta có:
- cw=p(w
1
&w
2
&w
n-1
)
- Với n chẵn:
lw=p(w
1
&w
2
&w
n/2
),rw=p(w
n/2+1
&w
n/2+2
&w

thuật toán di truyền. Chính vì tính chất quan trọng của các tham số nên việc lựa chọn
nên chúng ta cần một khảo sát nhỏ về số lượng từ tương ứng với chiều dài từ trên từ
điển thông dụng tại http://dict.vietfun.com để làm cơ sở cho các tham số sau này.
Độ dài từ(tiếng) Tần số xuất hiện Tỉ lệ
1 8933 12.2
2 48995 67.1
3 5727 7.9
17
XỬ LÝ NGÔN NGỮ TỰ NHIÊN
4 7040 9.7
>=5 2301 3.1
2.2.2. Khởi tạo quần thể
a. Biểu diễn cá thể :
Giả sử văn bản đầu vào t bao gồm n tiếng như sau : T=s1s2…sn .Mục đích của
qúa trình thực hiện thuật toán GA là tìm cách tách ra các từ có độ phù hợp cao nhất :
t=w1w2…wm với wk =si…sj ( 1 <= k <= m , 1 <= i,j <= n).
Sau đó mỗi cá thể trong quan 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 cho một segment.
Tác giả đã đưa ra ví dụ như sau :
Tôi Là Sinh Viên Trường Đại Học Bách Khoa Hà Nội
0 1 0 0 1 0 0 1 1 0 0
w1 w2 w3 w4 w5 w6 w7
b. Khởi tạo các tham số :
Trong bước này để cho GA chạy , chúng ta phải khởi tạo giá trị các tham số , bao gồm
: số thế hệ tiến hóa , kích thước quần thể , tỷ lệ lai ghép, … Qua nhiều lần thử sai , tác
giả đã đưa ra giá trị cho các tham số như sau :
Tham số Giá trị
Số thế hệ tiến hóa 100
Kích thước quần thể 50

thời gian tính toán thấp hơn các phương pháp khác.Sau khi khởi tạo xong ,quần thể sẽ
được tiến hóa qua các qúa trình lai ghép , đột biến , sinh sản.
2.2.3. Tiến hóa cá thể
a. Qúa trình lai ghép
Phương pháp lai ghép được tác giả thực hiện bằng cách dựa trên một điểm ngẫu nhiên
trong chuỗi các bit 0 , 1 của các cá thể . Khi có một cặp cá thể bố mẹ , thế hệ con được
tạo ra dựa trên sự kết hợp từ phần đầu tiên của bố với phần cuối của mẹ và ngược lại .
b. Qúa trình đột biến
Ý tưởng thực hiện đột biến được thực hiện bằng cách hoán chuyển vị trí của 2 bit liền
nhau tại một vị trí ngẫu nhiên , cách làm này thể hiện tính tự nhiên do là một tiếng nếu
kết hợp với tiếng trước nếu không phù hợp thì có thể kết hợp với từ đứng sau ( bit
đứng sau ) như thế sẽ tạo ra được các từ có ý nghĩa và loại bỏ các từ vô nghĩa nếu
ghép 2 bit ở 2 vị trí ngẫu nhiên trong câu.
19
XỬ LÝ NGÔN NGỮ TỰ NHIÊN
Ví dụ :
c. Qúa trình sinh sản
Sau khi đã lai ghép và đột biến chúng ta sẽ kết hợp các cá thể bố mẹ với cá thể con
vừa được tạo ra để phục vụ cho bước chọn cá thể . Sau khi kết hợp , chúng ta sẽ chọn lọc
các cá thể trong quần thể để đạt được nhiều kết qủa tách từ tốt .
Ví dụ :
`
d. Qúa trình chọn cá thể
Qúa trình chọn lựa cá thể là buớc rất quan trọng trong qúa trình tiến hóa , vì qúa trình
này sẽ chọn các cá thể tốt , chính việc chọn lựa này sẽ quyết định đến qúa trình tiến hóa
ở thế hệ tiếp theo , cũng như ảnh hưởng đến độ hội tụ trong thuật toán di truyền.Sau khi
chọn lựa , quần thể sẽ được sắp xếp theo giá trị của độ thích nghi giảm dần ,khi đó qúa
trình chọn lọc cá thể sẽ chọn N cá thể có độ thích nghi cao nhất để hình thành nên một
quần thể mới nhằm chuẩn bị cho qúa trình tiến hóa tiếp theo .
Cách thức lựa chọn cá thể thoả mãn điều kiện như sau :

Quá trình thực hiện thuật toán GA cố gắng tăng độ thích nghi (fitness) của mỗi cá thể,
điều này cũng có nghĩa là tăng chất lượng của từ được từ . Và do đó ở mỗi thế hệ tiến
hóa , chỉ số thích nghi của quần thể sẽ tăng lên dần đến một ngưỡng hội tụ T . Khi đó sau
một quá trình tiến hóa độ chêng lệch giữa chỉ số thích nghi của hai cá thể trong quần thể
sẽ giảm dần và tiến dần về 0 hoặc đạt đến ngưỡng hội tụ T mà chúng ta đã chọn.
3. Kết luận
Phương pháp do tác giả H.Nguyễn đề xuất có ưu điểm là không cần sử dụng bất cứ
tập huấn luyện hoặc từ điển nào do đó không mất thời gian để huấn luyện.Phương pháp
tách từ cũng không phức tạp. Tuy nhiên khi so sánh với các phương pháp LRMM và
WFST đã được trình bày ở trên thì IGATEC có độ chính xác thấp hơn nhưng hoàn toàn
chấp nhận được, thời gian chạy ban đầu hơi chậm do phải lấy thông tin từ mạng Internet.
21
XỬ LÝ NGÔN NGỮ TỰ NHIÊN
V. Tìm hiểu opensource Vntokenizer để tách từ trong văn bản tiếng
việt.
1. Giới thiệu chương trình
VnTokenizer là chương trình tách từ tiếng việt tự động. Việc nghiên cứu phát triển và cài đặt
chương trình được thực hiện bởi một nhóm giáo viên trẻ thuộc khoa toán cơ tin học, Trường
đại học khoa học từ nhiên, đại học Quốc gia Hà Nội thực hiện.
Phiên bản 4.0.0 của chương trình là sự phát triển tiếp theo của các phiên bản trên cơ
sở cải tiến và nâng cấp các tính năng, tối ưu khả năng kế thừa và mở rộng chương trình
cho các mục đích xử lý tiếng Việt về lâu dài. Tách đoan vị từ vựng tự động là bước tiền xử
lý không thể thiếu đối với hầu hết các lĩnh vực xử lý tự động ngôn ngữ tự nhiên.
2. Hướng dẫn chạy chương trình
Chương trình được viết bằng ngôn ngữ lập trình Java, sử dụng bộ công cụ phát triển
J2SDK 1.6 để chạy được chương trình, máy tính cần cài đặt JRE từ phiên bản 1.6, có thể tải về từ
trang web Java của Sun MicroSystem: http//java.sun.com và cài đặt. Chú ý là để chạy chương
trình chỉ cần cài JRE, không cần cài JDK
Chương trình được phân phối dưới 2 dạng: chương trình và chương trình nguồn, tương ứng với 2
tệp nén vnTokenizer-bin.zip và vnTokenizer-src.zip.

bản thô.
+) -nu : không sử dụng dấu gạch dưới (no underscore) khi ghi kết quả. Nếu tùy chọn
này được sử dụng thì trong kết quả, các âm tiết không được nối với nhau bằng ký tự
gạch dưới, mà bằng ký tự trắng.
+) -sd : sử dụng mô-đun tách câu trước khi thực hiện tách từ. Nếu tùy chọn này được sử
dụng thì trước tiên vnTokenizer thực hiện tách văn bản input thành một tập các câu, sau
đó thực hiện tách từ từng câu một.Mặc định thì mô-đun tách câu không được sử dụng,
vnTokenizer thực hiện tách từ trên toàn bộ văn bản.
Các tùy chọn này có thể được phối hợp đồng thời với nhau để cho ra kết quả mong
muốn.
Ví dụ:
a) vnTokenizer.sh -i samples/test0.txt -o samples/test0.tok.txt
Tách từ tệp samples/test0.txt và ghi kết quả vào tệp samples/test0.tok.txt
b) vnTokenizer.sh -i samples/test0.txt -o samples/test0.tok.xml -xo
Tương tự như a), tuy nhiên tệp kết quả samples/test0.tok.xml sẽ có định dạng XML
c) vnTokenizer.sh -i samples/test0.txt -o samples/test0.tok.txt -sd
Tương tự như a) và sử dụng mô-đun tách câu trước khi tách từ.
Tách từ một thư mục:
Ngoài các tùy chọn như ở trên, khi tách từ thư mục, chương trình cung cấp thêm tùy
chọn không bắt buộc
+) -e : chỉ định phần mở rộng của các tệp cần tách.
23
XỬ LÝ NGÔN NGỮ TỰ NHIÊN
Ví dụ:
a) vnTokenizer.sh -i samples/input -o samples/output
Thực hiện tách từ tất cả các tệp samples/input/*.txt, ghi kết quả ra thư mục
samples/output.
b) vnTokenizer.sh -i samples/input -o samples/output -e .xyz
Thực hiện tách từ tất cả các tệp samples/input/*.xyz, ghi kết quả ra thư mục
samples/output.