Nhận dạng văn bản một số ngôn ngữ La tinh

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

------------------

LÊ MẠNH ĐOAN

NHẬN DẠNG VĂN BẢN

MỘT SỐ NGÔN NGỮ LA TINH

LUẬN VĂN THẠC SĨ : KHOA HỌC MÁY TÍNH

THÁI NGUYÊN, NĂM 2017

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

------------------

LÊ MẠNH ĐOAN

NHẬN DẠNG VĂN BẢN

MỘT SỐ NGÔN NGỮ LA TINH

Chuyên ngành: Khoa học máy tính

Mã số : 60 48 01 01

LUẬN VĂN THẠC SĨ : KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC : TS. Hồ Văn Canh

THÁI NGUYÊN, NĂM 2017

i

LỜI CẢM ƠN

Trước hết cho phép em chân thành cảm ơn các Thầy giáo, Cô giáo trong khoa

Công nghệ thông tin và các cán bộ, nhân viên phòng Đào tạo Sau đại học, Trường

Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên đã luôn

nhiệt tình giúp đỡ và tạo điều kiện tốt nhất cho em trong suốt quá trình học tập tại

trường.

Xin chân thành cảm ơn các anh, các chị và các bạn học viên lớp Cao học

CK14H - Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái

Nguyên đã luôn động viên, giúp đỡ và nhiệt tình chia sẻ với em những kinh nghiệm

học tập, công tác trong suốt khoá học.

Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc đến TS. Hồ Văn Canh, người đã tận

tình giúp đỡ em hình thành và hoàn chỉnh luận văn.

Mặc dù đã có nhiều cố gắng, song do hạn hẹp về thời gian, điều kiện nghiên

cứu và trình độ, luận văn không tránh khỏi những khiếm khuyết. Em chân thành

mong nhận được sự đóng góp ý kiến của các Thầy giáo, Cô giáo và đồng nghiệp.

Một lần nữa em xin cảm ơn!

Thái Nguyên, tháng 04 năm 2017

Người thực hiện luận văn

Lê Mạnh Đoan

ii

DANH MỤC CÁC HÌNH

Hình 1.1. Sơ đồ tổng quát một hệ nhận dạng..............................................................8

Hình 1.2. Cấu tạo nơron sinh học..............................................................................15

Hình 3.1. Sơ đồ khối của thuật toán dựa trên xich Markov cấp 1 hữu hạn trạng thái ......40

Hình 3.2.Giao diện của chương trình........................................................................55

Hình 3.3 Thực hiện lấy dữ liệu đầu vào....................................................................56

Hình 3.4 Màn hình thực thi thuật toán xích Markov cấp 1 hữu hạn trạng thái.........57

Hình 3.5 Kết quả hiển thị dang file.txt của thuật toán xích Markov cấp 1 hữu hạn .58

iii

DANH MỤC CÁC BẢNG

Bảng 3.1. B1 ..............................................................................................................34

Bảng 3.2. B2 .............................................................................................................35

Bảng 3.3. B3 .............................................................................................................36

Bảng 3.4. B4 .............................................................................................................37

Bảng 3.5. B5 .............................................................................................................38

Bảng 1. Bảng tần số bộ đôi móc xích của Tiếng Anh (tính trên 10.000 ký tự) ........68

Bảng 2. Bảng tần số bộ đôi móc xích của Tiếng Pháp (tính trên 10.000 ký tự).......69

Bảng 3. Bảng tần số bộ đôi móc xích của Tiếng Đức (tính trên 10.000 ký tự) ........70

Bảng 4. Bảng tần số bộ đôi móc xích của Tiếng Tây Ban Nha (tính trên 10.000

ký tự).........................................................................................................................71

Bảng 5. Ước lượng bộ đôi móc xích tiếng Đức (A1) ...............................................72

Bảng 6. Ước lượng bộ đôi móc xích tiếng Pháp (A2)...............................................73

Bảng 7. Ước lượng bộ đôi móc xích tiếng Anh (A3)................................................74

Bảng 8. Ước lượng bộ đôi móc xích tiếng Tây Ban Nha (A4).................................75

iv

MỤC LỤC

LỜI CẢM ƠN............................................................................................................ i

DANH MỤC CÁC HÌNH........................................................................................ ii

DANH MỤC CÁC BẢNG ...................................................................................... iii

MỤC LỤC................................................................................................................ iv

MỞ ĐẦU ....................................................................................................................1

CHƯƠNG I. TỔNG QUAN VỀ NHẬN DẠNG .....................................................4

1.1. Tổng quan về nhận dạng..................................................................................4

1.1.1. Không gian biểu diễn đối tượng, không gian diễn dịch ...........................4

1.1.2. Mô hình và bản chất của quá trình nhận dạng..........................................5

1.2. Nhận dạng dựa trên phân hoạch không gian....................................................8

1.2.1. Phân hoạch không gian.............................................................................8

1.2.2. Hàm phân lớp hay hàm ra quyết định ......................................................8

1.2.3. Nhận dạng thống kê..................................................................................9

1.2.4. Một số thuật toán nhận dạng tiêu biểu trong tự học ...............................10

1.3. Nhận dạng theo cấu trúc ................................................................................12

1.3.1. Biểu diễn định tính .................................................................................12

1.3.2. Phương pháp ra quyết định dựa vào cấu trúc .........................................13

1.4. Nhận dạng bằng mạng nơron.........................................................................14

1.4.1. Bộ não và Nơron sinh học ......................................................................14

1.4.2. Mô hình mạng nơron ..............................................................................16

1.5. Kết luận..........................................................................................................18

CHƯƠNG II. KỸ THUẬT NHẬN DẠNG BẰNG THỐNG KÊ ........................19

2.1. Bài toán ..........................................................................................................19

2.2. Nhận dạng có giám sát...................................................................................20

2.3. Nhận dạng không có giám sát........................................................................23

2.3.1. Cơ sở lý thuyết........................................................................................23

2.3.2. Bài toán...................................................................................................24

2.3.2.1 Giải bài toán trường hợp cho trước số k...............................................24

v

2.3.2.2 Trường hợp số k chưa cho biết trước ...................................................26

2.4. Mô hình xích Markov ....................................................................................27

2.5. Đặc trưng của ngôn ngữ tự nhiên ..................................................................30

CHƯƠNG III. THỰC NGHIỆM...........................................................................31

3.1. Bài toán nhận dạng văn bản La Tinh .............................................................31

3.2. Thuật toán dựa trên xích Markov cấp 1 hữu hạn trạng thái...........................31

3.2.1. Xây dựng cơ sở dữ liệu để máy học .......................................................31

3.2.2. Nhận biết trực tiếp ..................................................................................39

3.2.3. Một số ví dụ............................................................................................41

3.3. Chương trình Demo .......................................................................................54

3.3.1 Giao diện chính của chương trình ...........................................................55

3.3.2 Xây dựng các mẫu thử.............................................................................56

3.3.3.Thực thi chương trình với thuật toán xích Markov cấp 1 hữu hạn trạng

thái ....................................................................................................................56

KẾT LUẬN..............................................................................................................59

TÀI LIỆU THAM KHẢO ......................................................................................60

PHỤ LỤC.................................................................................................................61

1

MỞ ĐẦU

Nhận dạng là một lý thuyết toán học có nhiều ứng dụng trong thực tiễn, như

nhận dạng tiếng nói, nhận dạng hình ảnh, nhận dạng chữ ký, phân loại ngôn ngữ ,

xây dựng tiêu chuẩn bản rõ ứng dụng trong phân tích các bản mã v.v..Thông qua

mạng Internet, em được biết trên thế giới cũng như trong nước đã có nhiều nhà

nghiên cứu về vấn đề này và đã có những phần mềm áp dụng cho nhiều lĩnh vực

khác nhau: phần mềm nhận dạng tiếng việt, phần mềm nhận dạng vân tay, phần

mềm kiểm soát E-mail trên hệ thống Internet…

Nhận dạng chữ là bài toán rất hữu ích, quen thuộc được ứng dụng nhiều trong

thực tế đặc biệt là trong lĩnh vực nhận dạng và phân loại văn bản vì thế đã thu hút

nhiều tác giả quan tâm nghiên cứu bằng các phương pháp nhận dạng khác nhau:

logic mờ, giải thuật di truyền, mô hình xác suất thống kê, mô hình mạng nơ ron. Đã

có rất nhiều công trình nghiên cứu thực hiện việc nhận dạng, phân loại văn bản La

Tinh đã đạt tỷ lệ chính xác khá cao, tuy nhiên các ứng dụng đó cũng chưa thể đáp

ứng hoàn toàn nhu cầu của người sử dụng nên ngày nay người ta vẫn tiếp tục

nghiên cứu những phương pháp nhận dạng tốt hơn hướng đến dùng cho các thiết bị

di động, và các bài toán thời gian thực. Sau khi tìm hiểu về sự tiến bộ của công nghệ

nhận dạng chữ La Tinh cũng như các tính năng cơ bản của các phần mềm nhận

dạng chữ, được sự tư vấn của giáo viên hướng dẫn, tôi đã lựa chọn được một hướng

nghiên cứu thiết thực với đề tài: "Nhận dạng văn bản một số ngôn ngữ La tinh". Để

nhận dạng được các đối tượng nào đó, trước hết và điều quan trọng nhất là phải biết

được các đặc trưng của từng đối tượng đó. Việc xác định được các đặc trưng của

từng ngôn ngữ La tinh mà Đề tài quan tâm là một khó khăn rất lớn do phải thống kê

thật nhiều và thật khách quan. Do đó, trong phạm vi Đề tài Luận văn, em chỉ hạn

chế vào việc xác định những ngôn ngữ La tinh phổ biến nhất hiện nay, đó là tiếng

Anh, tiếng Pháp, tiếng Đức, và tiếng Tây Ban Nha. Ngoài ra, Đề tài Luận văn cũng

hạn chế cho việc nhận dạng ngôn ngữ La tinh mà không phải là cho ngôn ngữ Phi

La tinh như tiếng Trung Quốc, tiếng Nhật, tiếng Hàn, tiếng Thái Lan, v.v. vì như

vậy ta lại phải chuyển đổi các ngôn ngữ đó sang số có phần phức tạp trong lúc đó,

em lại không có kiến thức về các ngôn ngữ đó. Về nguyên tắc, nếu có thuật toán

nhận dạng ngôn ngữ La tinh tốt thì thuật toán đó có thể áp dụng vào các ngôn ngữ

tùy ý khác.