Thạc Sĩ Xây dựng kho dữ liệu an toàn với mã Huffman

5

MỤC LỤC
CHƯƠNG 1. TỔNG QUAN VỀ KHO LƯU TRỮ DỮ LIỆU . 15
1.1. Sự cần thiết của kho lưu trữ dữ liệu 15
1.2. Kho lưu trữ 15
1.2.1. Khái niệm . 16
1.2.2. Cấu trúc của một hệ thống kho dữ liệu 16
1.3. Lưu trữ đám mây 17
1.3.1. Công nghệ lưu trữ đám mây . 17
1.3.2. Các loại hình đám mây lưu trữ . 17
1.3.3. Mô hình kiến trúc . 18
a. SaaS 19
b. IaaS . 19
c. PaaS 20
1.3.4. Đặc điểm của Đám mây . 20
a. Tự sửa chữa 20
b. Lượng truy cập lớn . 20
c. Khả năng mở rộng tuyến tính . 21
d. Hướng dịch vụ 21
e. Điều khiển SLA(Service level agreement) . 21
f. Khả năng ảo hóa . 21
g. Tính ứng dụng linh hoạt . 21
1.3.5. Lợi ích của công nghệ lưu trữ đám mây . 22
a. Tính linh hoạt . 22
b. Khắc phục sự cố . 22
c. Phần mềm tự động cập nhật . 22 6

d. Miễn giảm chi phí đầu tư . 23
e. Tăng cường làm việc nhóm 23
f. Làm việc ở mọi nơi 23
g. Kiểm soát dữ liệu 23
h. Bảo mật . 24
i. Tính cạnh tranh . 24
j. Thân thiện với môi trường 24
1.3.6. Dịch vụ đám mây lưu trữ 24
a. Mô hình dịch vụ đám mây lưu trữ 24
b. Một số dịch vụ đám mây lưu trữ hiện nay . 25
CHƯƠNG 2. XÂY DỰNG HỆ THỐNG LƯU TRỮ ĐÁM MÂY VỚI HADOOP 30
2.1. Phát biểu bài toán và lựa chọn giải pháp 30
2.1.1. Phát biểu bài toán . 30
2.1.2. Lựa chọn giải pháp công nghệ . 30
2.2. Big Data 31
2.2.1 Big Data là gì? 31
2.2.2. Hadoop là gì? . 31
a. Giới thiệu sơ lược Apache Hadoop 31
b. Định nghĩa về Hadoop 32
2.2.3. Thành phẩn của Hadoop 33
2.2.4. Lợi ích từ công nghệ Big Datacủa Hadoop . 34
2.3. Hadoop Distributed File System (HDFS) . 35
2.3.1. Giới thiệu . 35
2.3.2. Kiến trúc HDFS . 36
2.3.3. Quá trình đọc file trên HDFS . 37 7

2.3.4. Ghi file trên HDFS . 39
2.4. Triển khai cài đặt hệ thống lưu trữ đám mây với HDFS 40
CHƯƠNG 3. TỔNG QUAN VỀ MÃ HÓA DỮ LIỆU 44
3.1. Sự cần thiết của mã hóa dữ liệu 44
3.2. Mã hóa dữ liệu 44
3.2.1. Khái niệm về mã hóa thông tin 44
3.2.2. Phân loại các thuật toán mã hóa 45
c. Mã hóa cổ điển . 45
d. Mã đối xứng . 46
e. Mã hóa bất đối xứng . 46
f. Mã hóa hàm băm 47
g. Mã hóa khóa lai 48
h. Mã hóa khóa bí mật 49
i. Mã hóa khóa công khai 49
3.3. Hệ mã hóa Vigenere . 51
3.3.1. Hệ mã hóa Caesar 51
3.3.2. Hệ mã hóa Vigenere 52
CHƯƠNG 4. TỔNG QUAN VỀ NÉN VÀ GIẢI NÉN . 54
4.1. Sự cần thiết của nén dữ liệu 54
4.2. Nén dữ liệu 55
4.2.1. Định nghĩa nén dữ liệu . 55
4.2.2. Quá trình nèn và giải nén . 56
4.2.3. Nén văn bản . 56
4.3. Giải thuật mã hóa Huffman 57
4.3.1. Mã hóa dữ liệu trong máy tính 57 8

4.3.2. Mã phi tiền tố . 57
4.3.3. Lý thuyết Mã Huffman 58
a. Bài toán: 58
b. Thuật toán xây dựng cây mã Huffman . 59
c. Thuật toán giải mã 61
d. Ứng dụng mã hóa Huffman để nén file 61
CHƯƠNG 5. GIỚI THIỆU BÀI TOÁN MÃ HÓA VĂN BẢN TIẾNG VIỆT . 63
5.1. Yêu cầu bài toán . 63
5.2. Đề xuất giải pháp cho mã hóa và nén văn bản tiếng Việt 63
5.2.1. Mã hóa văn bản tiếng Việt với phương pháp mã hóa Vigenere 63
5.2.2. Nén văn bản tiếng Việt với phương pháp mã hóa Huffman 63
5.2.3. Tập văn bản mẫu cho việc mã hóa và nén văn bản Tiếng Việt . 64
5.3. Xử lý văn bản và liệt kê tỷ lệ xuất hiện của các từ . 66
5.4. Xây dựng bộ mã Huffman 68
5.5. Má hóa văn bản Tiếng việt sử dụng phương pháp mã Vigenere 68
5.5.1. Yêu cầu bài toán 68
5.5.2. Mô hình xử lý 69
5.5.3. Giải thích mô hình xử lý 69
a. Các bước để mã hóa một văn bản . 69
b. Các bước để giải mã văn bản . 69
c. Ghi chú . 70
5.6. Nén và giải nén văn bản Tiến Việt sử dụng phương pháp mã Huffman 70
5.6.1. Yêu cầu bài toán 70
5.6.2. Mô hình xử lý 71
5.6.3. Kết quả thực hiện . 72 9

a. Nén dữ liệu . 72
b. Giải nén dữ liệu 73
5.6.4. Giới thiệu chương trình nén và giải nén văn bản tiếng Việt 74
a. Cửa sổ Form xây dựng bộ mã Huffman: 74
b. Nén văn bản tiếng Việt . 75
c. Giải nén văn bản tiếng Việt. . 76
KẾT LUẬN . 77
TÀI LIỆU THAM KHẢO 78
10


MỞ ĐẦU
Khoảng 10 năm trước, khi việc lưu trữ thông tin cá nhân trên các thiết bị lưu trữ di
động như đĩa mềm (floopy disk) với dung lượng khá khiêm tốn 4MB và USB thời điểm
cao nhất lúc bấy giờ là 128MB; Việc sở hữu một ổ cứng với dung lượng 40GB đã là đủ
lớn thậm chí là dư thừa cho nhu cầu sử dụng của cá nhân.
Nhưng hiện nay, với sự phát triển của Công nghệ thông tin, nhu cầu sử dụng tài
nguyên và lưu trữ dữ liệu của con người ngày càng nhiều và những con số đó đã trở nên
hết sức nhỏ bé. Dung lượng dữ liệu gia tăng không ngừng, yêu cầu ngày càng cao về hiệu
năng truy xuất, tính ổn định và sự sẵn sàng của dữ liệu; việc lưu trữ đã và đang trở nên rất
quan trọng.
Lưu trữ dữ liệu không còn đơn giản là cung cấp các thiết bị lưu trữ dung lượng lớn mà
còn bao gồm cả khả năng quản lý, chia sẻ cũng như sao lưu và phục hồi dữ liệu trong mọi
trường hợp
Với sự tiến bộ mạnh mẽ của internet, việc sử dụng cáp quang với tốc độ khá nhanh
ngày càng trở lên phổ cập; Chính nhờ đó đã phát triển nên một ngành dịch vụ khá mới
hiện nay đó là các dịch vụ lưu trữ thông tin trên mạng và qua đám mây. Rất nhiều các
công ty lớn như Microsoft, Apple, Google, Dropbox, Mediafire, Rapidshare đang
cung cấp các dịch vụ lưu trữ và chia sẻ dữ liệu trên nền điện toán đám mây.
Tuy đáp ứng được yêu cầu về việc lưu trữ, chia sẻ dữ liệu cũng như dung lượng lớn
nhưng việc lưu trữ qua các đám mây cũng có những nhược điểm về vấn đề an ninh dữ
liệu trước sự tấn công của tin tặc, tính pháp lý liên quan đến các dữ liệu được lưu trữ trên
mạng
Mục tiêu của luận văn này nhằm nghiên cứu giải pháp xây dựng kho lưu trữ dữ liệu
hiệu quả và an toàn, bảo mật dữ liệu người dùng dựa trên việc xây dựng các thuật toán
mã hóa phục vụ cho việc má hóa văn bản, nén và giải nén văn bản theo ngôn ngữ Tiếng
Việt.
Thông qua việc phân tích từ (từ đơn, từ ghép) trong tiếng Việt và áp dụng vào các giải
thuật mã hóa, qua đó nâng cao hiệu quả của việc mã hóa cũng như nén dữ liệu trong kho
lưu trữ an toàn. 11

Nhiệm vụ của luận văn là:
- Phân tích các văn bản tiếng Việt mẫu, từ đó xây dựng các bộ thư viện mẫu cho
việc thiết lập bộ mã Huffman.
- Thống kê tuần suất xuất hiện của các từ đơn, từ kép trong văn bản tiếng Việt.
- Nghiên cứu mã Vigiener cho việc mã hóa văn bản tiếng Việt dựa trên kết quả của
việc phân tích Tiếng Việt.
- Nghiên cứu giải thuật Huffman cho nén và giải nén văn bản.
- Áp dụng bộ thư viện mẫu từ tiếng Việt để xây dựng bộ mã Huffman.
- Nghiên cứu mô hình kho lưu trữ dữ liệu.
Phạm vi nghiên cứu:
- Nghiên cứu mã hóa văn bản tiếng Việt dựa trên mã Vigiener.
- Nghiên cứu nén các văn bản tiếng Việt dựa trên thuật toán Huffman.
- Xây dựng kho lưu trữ dữ liệu với các văn bản Tiếng Việt đã được nén và mã hóa,
đảm bảo tối ưu dung lượng lưu trữ cũng như đảm bảo tính riêng tư của người sử
dụng.
Phương pháp nghiên cứu:
- Nghiên cứu giải pháp xây dựng kho lưu trữ đám mây
- Nghiên cứu thuật toán mã hóa Huffman cho việc nén và giải nén các văn bản.
- Nghiên cứ thuật toán mã hóa Vigiener.
- Xây dựng một bộ thư viện dữ liệu cho việc phân tích văn bản tiếng Việt.
- Nghiên cứu và tìm cơ chế phân tích các văn bản tiếng Việt thành các từ đơn, từ
ghép phục vụ cho việc nén dữ liệu.
- Sử dụng các công cụ lập trình để xây dựng phần mềm phục vụ cho việc nén và
giải nén các văn bản tiếng Việt.
Nội dung Luận văn gồm các chương:
Chương 1. Tổng quan về kho lưu trữ dữ liệu
o Sự cần thiết của kho lưu trữ
o Các khái niệm về Kho lưu trữ
o Lưu trữ đám mây
Chương 2. Xây dựng hệ thống lưu trữ đám mây với Hadoop
o Bài toán
o Tìm hiểu về Big data 12

o Hadoop Distributed File System – HDFS
o Triển khai cài đặt hệ thống lưu trữ đám mây với HDFS
Chương 3. Tổng quan về mã hóa dữ liệu
o Sự cần thiết của mã hóa dữ liệu
o Các khái niệm về mẫ hóa dữ liệu
o Hệ mã hóa Viginere
Chương 4. Tổng quan về nén và giải nén
o Sự cần thiết của nén dữ liệu
o Nén dữ liệu
o Giải thuật mã hóa Huffman
Chương 5. Giới thiệu bài toán mã hóa văn bản tiếng Việt
o Yêu cầu bài toán
o Xử lý văn bản tiếng Việt.
o Xây dựng bộ mã Huffman
o Nén và mã hóa văn bản tiếng Việt
Kết luận
Tài liệu tham khảo. 13

DANH MỤC HÌNH

Hình CI.II.2 - 1 Cấu trúc của hệ thống kho lưu trữ 16
Hình CI.III.3 – 1 Mô hình kiến trúc lưu trữ đám mây 18
Hình CI.III.5.b – 1 Truy cập đám mây . 22
Hình CI.III.6.a – 1Mô hình dịch vụ đám mây lưu trữ 25
Hình CI.III.6.b – 1 ONEDRIVE . 26
Hình CI.III.6.b – 2 Dropbox . 27
Hình CI.III.6.b – 3 Google Drive 28
Hình CI.III.6.b – 4. Box 29
Hình CII.II.5 – 1. Thành phần của Hadoop 34
Hình CII.III.2 – 1. Kiến trúc HDFS 36
Hình CII.III.3 – 1. Quá trình đọc file trên HDFS . 38
Hình CII.III.4 – 1. Quá trình ghi file trên HDFS 39
Hình CII.IV – 1. Máy ảo HDFS 41
Hình CII.IV – 2. Giao diện HDFS 42
Hình CII.IV – 3. Mô hình xây dựng phần mềm Client tương tác HDFS . 43
Hình CIII.II.1-1 Quá trình mã hóa và giải mã 44
Hình CIII.II.2.b-1 Mô hình mã đối xứng 46
Hình CIII.II.2.c-1 Mô hình mã bất đỗi xứng . 47
Hình CIII.II.2.d-1 Mô hình mã hóa hàm băm . 48
Hình CIII.II.2.e-1 Mô hình mã hóa khóa lai. 49
Hình CIII.II.2.f-1 Mô hình mẫ hóa khóa bí mật . 49
Hình CIII.II.2.g-1 Mã hóa thông điệp sử dụng khóa công khai . 50
Hình CIII.II.2.g-2 Giải mã thông điệp sử dụng khóa riêng 50 14

Hình CIII.III.1 Mẫ Caesar với độ dịch là 3 51
Hình vuông Vigenère hay bảng Vigenère, công cụ của phép mã hóa Vigenere. . 52
Hình CIV.II.2 - 1. Quá trình nén dữ liệu 56
Hình CIV.II.2 - 2. Quá trình giải nén dữ liệu . 56
Hình CIV.III.2.b – 1 Xây dựng mã Huffman – bước 1 59
Hình CIV.III.2.b – 2 Xây dựng mã Huffman – bước 2 60
Hình CIV.III.2.b – 3 Xây dựng mã Huffman – bước 3 60
Hình CIV.III.2.b – 4 Xây dựng mã Huffman – bước 4 60
Hình CIII.II.3 – 1 Độ giao giữa các Tập văn bản mẫu . 65
Hình CIII.III-1 Mô hình liệt kê tỷ lệ xuất hiện của các từ trong Tiếng Việt 67
Hình CIII.IV – 1 Mô hình xây dựng bộ mã Huffman 68
Hình CIII.V.2 – Mô hình nén văn bản Tiếng Việt với mã hóa Vigenere . 69
Hình CIII.VI – 1 Mô hình nén và giải nén văn bản 71
Hình CIII.VI.4.a – 1 Cửa sổ chức năng xây dựng bộ mã Huffman 74
Hình CIII.VI.4.b – 1 Cửa sổ chức năng mã hóa văn bản 75
Hình CV.VI.4.c – 1 Cửa sổ chức năng giải mã văn bản . 76 CHƯƠNG 1. TỔNG QUAN VỀ KHO LƯU TRỮ DỮ LIỆU
1.1. Sự cần thiết của kho lưu trữ dữ liệu
Cùng với sự phát triển không ngừng và nhanh chóng của khoa học công nghệ, đặc biệt
là công nghệ thông tin, tri thức của con người ngày càng được nâng cao, vai trò và ý
nghĩa của lưu trữ tài liệu ngày càng được coi trọng và khẳng định.
Với Internet không chỉ diễn ra sự giao tiếp, phổ cập thông tin mà còn hình thành nên
một thị trường thông tin hàng hóa rộng lớn, nhiều tiềm năng. Bên cạnh đó, do yêu cầu của
quá trình hội nhập đang diễn ra mạnh mẽ, việc công khai minh bạch các văn bản, chính
sách của nhà nước đến mọi đối tượng trở thành vấn đề bắt buộc. Đặc biệt việc nâng chất
lượng thông tin phục vụ nhu cầu nghiên cứu, quyết định đầu tư, sản xuất, kinh tế, văn
hóa, xã hội, lịch sử, truyền thống đang rất được chú trọng. Một trong những nguồn
thông tin đặc biệt là thông tin từ tài liệu lưu trữ.
Mặt khác dưới góc độ quản lý nhà nước, việc bào quàn và sử dụng có hiệu quả tài liệu
lưu trữ có ý nghĩa cực kỳ quan trọng đối với kinh tế, xã hội, lịch sừ của mồi quốc gia và
địa phương.
Với các doanh nghiệp hoạt động kinh doanh, các dữ liệu của doanh nghiệp phát sinh
ngày càng nhiều, ngoài những thông tin sản phẩm, dịch vụ thì các thông tin liên quan đến
sự tương tác với khách hàng như việc tham gia trò chuyện, yêu cầu tư vấn và thực hiện
các so sánh về giá cả, chất lượng Người ta muốn tận dụng nguồn dữ liệu này để sử
dụng cho những mục đích hỗ trợ cho công việc kinh doanh ví dụ như cho mục đích thống
kê hay phân tích.
Vì vậy, song song với chương trình cung cấp thông tin qua Internet và hệ thống thông
tin viễn thông khác thì việc ứng dụng các công nghệ, kỹ thuật hiện đại vào bảo quản lâu
dài các tài liệu điện tử có giá trị (dần thay cho phương pháp bảo quản truyền thống) trở
thành nhiệm vụ cấp bách của công tác lưu trữ.
1.2. Kho lưu trữ
Theo định nghĩa của wiki: Kho dữ liệu (tiếng Anh: data warehouse) là kho lưu trữ dữ
liệu lưu trữ bằng thiết bị điện tử của một tổ chức. Các kho dữ liệu được thiết kế để hỗ trợ
việc phân tích dữ liệu và lập báo cáo.