MỘT SỐ THUẬT TOÁN NHẬN DẠNG
VÀ CHUYỂN MÃ TIẾNG VIỆT

ThS. PHẠM XUÂN TÍCH
Bộ môn Khoa học máy tính
Khoa Công nghệ thông tin
Trường Đại học Giao thông Vận tải

Tóm tắt: Hiện nay, tiếng Việt có hơn 40 loại bảng mã khác nhau được sử dụng để mã hóa
các loại văn bản: từ trang web, các dữ liệu điện tử đến các cơ sở dữ iệu… Việc nhận biết bảng
mã và chuyển đổi giữa các bảng mã tiếng Việt là rất cần thiết, không chỉ mang lại lợi ích cho
các lập trình viên mà cho cả nhân viên văn phòng, nhân viên xử lý văn bản. Công việc này cũng
tạo tiền đề cho các việc xử lý tiếp theo trong tiếng Việt như: kiểm tra phát hiện lỗi chính tả, tóm
tắt văn bản, làm từ điển, thậm chí cả dịch máy và xử lý ngôn ngữ tự nhiên. Trong khuôn khổ bài
báo này, chúng tôi đưa ra một thuật toán nhận dạng mã để dễ dàng chuyển đổi mã tiếng Việt mà
các chương trình hiện nay hầu hết chỉ chuyển mã biết trước mà không nhận dạng được các bảng
mã, cũng như không xử lý được các văn bản tiếng Việt có nhiều loại mã trong cùng một văn bản.
Summary: In recent years, there are over 40 Vietnamese codes for encoding on all types of
data from websites, databases to documents, and many others. Codes recognization and
conversion have so many advantages for not only programmers but office clients and secretaries
as well It makes premises for advanced Vietnamese processing such as: spell checking, syntact
correcting, document abstracting, dictionary constructing, even machine translating and natural
language processing.
In this article, we present an algorithrm which can recognize many kinds of Vietnamese
codes to make them easy to convert, while almost other programs can only convert some known
codes and cannot recognize codes or process Vietnamese documents having more than one code.

CNTT-CB
I. MÃ HOÁ TIẾNG VIỆT TRONG CÔNG NGHỆ THÔNG TIN
Công nghệ thông tin là một ngành non trẻ ở nước ta, với khoảng 20 năm phát triển nhưng

o
0x006f 0x00f2 0x00f3 0x1ecd 0x1ecf 0x00f5
ô
0x00f4 0x1ed3 0x1ed1 0x1ed9 0x1ed5 0x1ed7
ơ
0x01a1 0x1edd 0x1edb 0x1ee3 0x1edf 0x1ee1
u
0x0075 0x00f9 0x00fa 0x1ee5 0x1ee7 0x0169
ư
0x01b0 0x1eeb 0x1ee9 0x1ef1 0x1eed 0x1eef
y
0x0079 0x1ef3 0x00fd 0x1ef5 0x1ef7 0x1ef9
A
0x0041 0x00c0 0x00c1 0x1ea0 0x1ea2 0x00c3
Ă
0x0102 0x1eb0 0x1eae 0x1eb6 0x1eb2 0x1eb4
Â
0x00c2 0x1ea6 0x1ea4 0x1eac 0x1ea8 0x1eaa
E
0x0045 0x00c8 0x00c9 0x1eb8 0x1eba 0x1ebc
Ê
0x00ca 0x1ec0 0x1ebe 0x1ec6 0x1ec2 0x1ec4
I
0x0049 0x00cc 0x00cd 0x1eca 0x1ec8 0x0128
O
0x004f 0x00d2 0x00d3 0x1ecc 0x1ece 0x00d5
Ô
0x00d4 0x1ed2 0x1ed0 0x1ed8 0x1ed4 0x1ed6
Ơ
0x01a0 0x1edc 0x1eda 0x1ee2 0x1ede 0x1ee0

được gọi là tiên đề hay ký hiệu xuất phát của văn phạm,
{
}
ϕψϕ ψ
+∗
= → ∈ Σ∪ ∈ Σ∪ →∉ Σ∪P ( V) , ( V) , ( V) - Tập các quy tắc sinh
của văn phạm [1.].
Định nghĩa 2: Văn phạm sao cho tất cả các quy tắc sinh thuộc một trong
hai dạng: , được gọi là văn phạm chính quy hay văn
phạm otomat [1].
(
σ
=ΣG,V,,P
)
Σ→→ ∈∈AaB,Aavíi A,BV, a
Định nghĩa 3: Otomat hữu hạn có lối ra là một bộ sáu
0
(, ,, ,, )ASXYs
ϕ
ψ
=
trong đó S,
X, Y là các tập hữu hạn được gọi một cách tương ứng là tập trạng thái, bảng chữ cái vào và
bảng chữ cái ra của otomat A [1].
0
sS∈ được gọi là trạng thái khởi đầu
ϕ

1
s
2
s
a
0
s
0
s
0
s
b
1
s
2
s
1
s
c
1
s
0
s
2
s

Hàm chuyển trạng thái ψ

0
s

(khoảng 40 bảng mã)
X – Tập tất cả các mã tiếng Việt của các ký tự của tất cả các mã có thể
Y – Là một tập mã nhất định (chẳng hạn TCVN3) làm bảng mã trung gian chuyển đổi về
nó trước khi chuyển sang mã đích.
ϕ - Là hàm chuyển dựa vào các mã trong tập X thuộc vào bảng mã nào của tập S ta xây
dựng tương ứng để nhận biết mã từ
S X
×
vào S định hướng để nhận các mã tiếp theo.
ψ - Là hàm ra, sau khi đã nhận biết được bảng mã của ký tự dựa vào ϕ ta chuyển sang một
mã trung gian hoặc mã đích luôn.
Bước 2. Viết thuật toán chuyển mã có độ phức tạp tuyến tính
Khi đã có otomat, thuật toán đơn giản chỉ hoạt động biến đổi trạng thái theo otomat đã được
xây dựng với cấu trúc dữ liệu là 2 bảng phi và xi thay cho 2 hàm để tra cứu tính toán cho nhanh.
function recognize_and_convert(Phi,Xi:Array,source:string):string
Begin
destination:= “”;
state:=recognize();
for i:=1 to length(source) do
begin
state:= Phi[source[i]][state];
destination:=concat(destination,Xi[state]);
end
return destination;
CNTT-
CB
end;
Vì mọi otomat không tất định ta đều xây dựng được một otomat tất định tương đương mà
việc phân tích dựa trên otomat tất định là tuyến tính. Do đó, ta luôn xây dựng được một thuật
toán tuyến tính để nhận dạng và chuyển đổi mã tiếng Việt.