Trong các lĩnh vực của công nghệ thông tin -viễn thông hiện nay, việc truyền tải tin
tức đã là một công việc xảy ra thường xuyên. Tuy nhiên, thông tin được truyền tải đi
thường rất lớn, điều này gây khó khăn cho công việc truyền tải: gây tốn kém tài
nguyên mạng, tiêu phí khả năng của hệ thống Để giải quyết vấn đề đó, các thuật
toán nén đã được ra đời.
Mỗi phương pháp nén có hiệu quả khác nhau với các loại tệp khác nhau. Luận văn
này sẽ trình bày một phương pháp nén có hiệu quả cao trong việc truyền tải tệp tin
trên mạng phục vụ cho việc cập nhật phiên bản của tệp tin. Phương pháp dựa trên sự
sai khác nhau giữa tệp nguồn và tệp đích (gọi là Differential Compression –hay Delta
Compression) -trong quá trình cập nhật, tệp nguồn là tệp cũ, tệp đích là tệp mới-và
tạo ra một bản vá có kích thước nhỏ đáng kể so với tệp đích. Khi đó, thay vì phải
truyền tệp đích có kích thước lớn trên mạng, ta chỉ cần truyền bản vá có kích thước
rất nhỏ. Phương pháp đã đạt được tỉ lệ nén cao, rất hiệu quả trong việc tiết kiệm tài
nguyên mạng. Nếu tỷ lệ nén cho các tệp thực thi thường dao động quanh 3:1 thì tỷ lệ
nén của bản vá so với tệp đích theo phương pháp Delta có thể nằm trong khoảng từ
10:1 tới 1000:1 và thậm chí có thể lớn hơn –tùy thuộc vào dung lượng tệp đích và
mức độ khác biệt của nó với tệp nguồn. Luận văn cũng trình bày ứng dụng của
phương pháp nén trong việc cập nhật phần mềm nghiệp vụ tại Ngân hàng Công
thương Việt Nam.
84 trang |
Chia sẻ: lvbuiluyen | Lượt xem: 2216 | Lượt tải: 3
Bạn đang xem trước 20 trang tài liệu Công nghệ nén delta ứng dụng trong cập nhật phần mềm tại ngân hàng công thương Việt Nam, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Thị Hương
CÔNG NGHỆ NÉN DELTA
ỨNG DỤNG TRONG CẬP NHẬT PHẦN MỀM TẠI
NGÂN HÀNG CÔNG THƯƠNG VIỆT NAM
Ngành: Công nghệ thông tin
Chuyên ngành: Truyền dữ liệu và mạng máy tính
Mã số: 60 48 15
LUẬN VĂN THẠC SĨ
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS. TS. Nguyễn Văn Tam
Hà Nội – 2009
2
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Những số liệu trình bày
trong luận văn là trung thực và có nguồn gốc rõ ràng. Các kết luận khoa học của luận
văn chưa được công bố trong bất kỳ công trình nghiên cứu khoa học nào.
Hà Nội, ngày 4/12/2009
Tác giả
Nguyễn Thị Hương
3
LỜI CẢM ƠN
Em xin gửi lời cảm ơn sâu sắc tới thầy giáo hướng dẫn PGS, TS Nguyễn Văn Tam
đã tận tình chỉ bảo em những kiến thức quý giá giúp em hoàn thành luận văn này.
Em cũng xin chân thành cảm ơn các thầy, cô giáo khoa Công nghệ thông tin - bộ môn
Truyền dữ liệu và mạng máy tính đã nhiệt tình chỉ bảo, góp ý để luận văn của em
được hoàn thiện.
Tôi xin cảm ơn các đồng chí đồng nghiệp làm việc tại phòng Nghiên cứu phát triển,
phòng Ứng dụng triển khai, bảo trì và phát triển phần mềm – Trung tâm công nghệ
thông tin – Ngân hàng công thương Việt Nam đã cung cấp các tài liệu cần thiết để tôi
hoàn thành luận văn này.
Do thời gian nghiên cứu cũng như năng lực có hạn, luận văn ko tránh khỏi những
thiếu sót, mong nhận được sự đóng góp ý kiến của quý thầy cô và các bạn.
Hà Nội, ngày 4/12/2009
Tác giả
Nguyễn Thị Hương
4
MỤC LỤC
TRANG PHỤ BÌA..………………………………………………………………….1
LỜI CAM ĐOAN........................................................................................................2
LỜI CẢM ƠN.............................................................................................................3
MỤC LỤC ..................................................................................................................4
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT ............................................................6
DANH MỤC CÁC BẢNG BIỂU .................................................................................7
DANH MỤC CÁC HÌNH VẼ .......................................................................................8
MỞ ĐẦU ....................................................................................................................9
CHƯƠNG 1 - GIỚI THIỆU CHUNG VỀ MỘT SỐ CÔNG NGHỆ NÉN..................... 10
1.1 Tầm quan trọng của nén dữ liệu trong truyền tin ................................................. 10
1.2 Nguyên tắc của nén dữ liệu ................................................................................. 10
1.3 Một số phương pháp nén dữ liệu......................................................................... 11
1.3.1 Phương pháp mã hoá độ dài loạt (Run-Length Encoding)............................ 11
1.3.2 Phương pháp mã hoá Huffman........................................................................ 12
1.3.3 Phương pháp nén LZW ................................................................................... 14
1.3.4 Chọn phương pháp nén ................................................................................... 17
CHƯƠNG 2 – CÔNG NGHỆ NÉN DELTA ................................................................... 19
2.1 Tổng quan về công nghệ nén Delta ..................................................................... 19
2.1.1 Tổng quan....................................................................................................... 19
2.1.2 Tính hiệu quả .................................................................................................. 20
2.2 Nền tảng ................................................................................................................... 20
2.1.3 Nền tảng chung ............................................................................................... 20
2.1.4 Bộ nén LZ77 - Nền tảng của bộ nén Delta....................................................... 22
2.3 Thuật toán nén Delta.......................................................................................... 24
2.3.1 Giới thiệu........................................................................................................ 25
2.3.2 Đặt vấn đề:...................................................................................................... 26
2.3.3 Những nghiên cứu đầu tiên ............................................................................. 27
2.3.4 Thuật toán cơ bản ........................................................................................... 28
2.3.5 Sự cải tiến của thuật toán ............................................................................ 32
2.3.6 Xây dựng lại xâu đích ................................................................................. 34
2.4 Một vài kết quả thí nghiệm ................................................................................. 37
2.5 Các vấn đề liên quan........................................................................................... 39
2.5.1 Khoảng trống miễn cưỡng trong bộ nén delta .................................................. 39
2.5.2 Chọn file tham chiếu ....................................................................................... 40
2.5.3 Đồng bộ các file từ xa ..................................................................................... 41
2.5.3.1 Thuật toán rsync...................................................................................... 41
2.5.3.2 Các kết quả thực nghiệm của rsync.......................................................... 43
2.5.3.3 Các ứng dụng .......................................................................................... 44
CHƯƠNG 3 - ỨNG DỤNG THUẬT TOÁN NÉN DELTA TRONG VIỆC CẬP NHẬT
CÁC PHẦN MỀM NGHIỆP VỤ TẠI NGÂN HÀNG CÔNG THƯƠNG VIỆT NAM . 46
3.1 Mô hình hệ thống công nghệ thông tin trong ngân hàng Công Thương Việt Nam46
3.2 Quy trình cập nhật các phần mềm nghiệp vụ trong ngân hàng Công Thương Việt
Nam 47
3.3 Chương trình cập nhật tự động các phần mềm nghiệp vụ .................................... 47
3.3.1 Thiết kế hệ thống ............................................................................................ 47
5
3.3.2 Thiết kế chương trình...................................................................................... 48
3.3.2.1 Chương trình đặt lịch tự động.................................................................. 48
3.3.2.2 Chương trình quản lý trên Server TW...................................................... 49
3.3.2.2.1 Quản lý gói cập nhật .......................................................................... 49
3.3.2.3.2 Quản lý danh sách chi nhánh.............................................................. 55
3.3.2.3.3 Quản lý danh sách ứng dụng .............................................................. 56
3.3.2.3.4 Upload thủ công gói cập nhật............................................................. 57
3.3.2.3.5 Xem nhật ký upload ........................................................................... 58
3.3.3 Thực thi chương trình ..................................................................................... 59
3.3.3.1 Chương trình đặt lịch tự động.................................................................. 59
3.3.3.2 Chương trình quản lý trên server TW ..................................................... 63
3.3.3.2.1 Quản lý gói cập nhật ......................................................................... 63
3.3.3.2.2 Quản lý danh sách chi nhánh............................................................. 65
3.3.3.2.3 Quản lý danh sách ứng dụng ............................................................. 67
3.3.3.2.4 Upload thủ công gói cập nhật............................................................ 68
3.3.3.2.5 Xem nhật ký upload .......................................................................... 69
CHƯƠNG 4 - KẾT LUẬN............................................................................................... 71
4.1 Kết luận.................................................................................................................... 71
4.2. Ưu nhược điểm của phương pháp ............................................................................ 71
4.3 Hướng nghiên cứu trong tương lai ............................................................................ 72
TÀI LIỆU THAM KHẢO................................................................................................ 73
Bảng đối chiếu encoding các bộ chữ hiện hành với Unicode........................................... 74
Thuật toán Knuth-Morris-Pratt Pattern Matching............................................................ 83
6
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT
Chữ viết tắt
Nội dung tiếng Anh
Nội dung tiếng Việt
Delta compression Differential compression Phương pháp nén dựa trên
sự sai khác nhau giữa 2
file
LCS Longgest common
subsequence
Chuỗi chung dài nhất (của
2 xâu /chuỗi)
LZW Tên một phương pháp nén
được phát minh bởi
Lempel - Zip và Welch
Match Sự phù hợp (sự khớp
nhau) giữa 2 xâu
Patch file Bản vá của 1 file cần cập
nhật
QAM Quadrature Amplitude
Modulation
Điều chế biên độ trực giao
Script
Đoạn lệnh (viết bằng một
ngôn ngữ lập trình nào đó)
nhằm thực hiện một mục
đích cho trước.
String Xâu các ký tự văn bản
UTF Unicode Transformation
Format
Mã định dạng unicode
7
DANH MỤC CÁC BẢNG BIỂU
Bảng 2.1: Các kết quả nén cho bộ dữ liệu gcc và emacs (KB /s) ......................................... 24
Bảng 2.2: Các kết quả nén cho tập dữ liệu gcc và emacs (KB)............................................ 44
Bảng 2.3: Các kết quả nén cho emacs với các tập dữ liệu khác nhau (KB) .......................... 44
8
DANH MỤC CÁC HÌNH VẼ
Hình 2.1 Bộ nén dữ liệu thông thường................................................................................ 19
Hình 2.2 Bộ nén Delta........................................................................................................ 20
Hình 2.3: Sự đối lập của kích thước nén file và sự giống nhau giữa các file (KB) ............... 38
Hình 2.4: Sự đối lập giữa thời gian thực hiện và sự giống nhau của các file........................ 38
Hình 3.1: Mô hình hệ thống công nghệ thông tin tại NHCTVN .......................................... 46
Hình 3.2: Các mô đun chính chương trình quản lý tại Server TW ....................................... 49
Hình 3.3: Các chức năng của mô đun Quản lý gói cập nhật ................................................ 50
Hình 3.4: Lưu đồ chức năng Tạo mới/chỉnh sửa gói cập nhật ............................................. 50
Hình 3.5: Các chức năng của mô đun Quản lý danh sách chi nhánh.................................... 55
Hình 3.6: Mối quan hệ giữa chức năng quản lý danh sách chi nhánh và các chức năng khác
.......................................................................................................................................... 56
Hình 3.7: Các mô đun chính của chức năng Quản lý danh sách ứng dụng........................... 57
Hình 3.8: Mối quan hệ giữa chức năng Quản lý danh sách ứng dụng và chức năng Quản lý
gói cập nhật........................................................................................................................ 57
Hình 3.9: Mối quan hệ giữa chức năng Upload thủ công gói cập nhật và các chức năng khác
.......................................................................................................................................... 58
Hình 3.10: Mối quan hệ giữa chức năng Xem nhật ký upload và các chức năng khác. ........ 58
Hình 3.11: Thực thi chương trình đặt lịch tự động (1)......................................................... 59
Hình 3.12: Thực thi chương trình đặt lịch tự động (2)......................................................... 60
Hình 3.13: Thực thi chương trình đặt lịch tự động (3)......................................................... 60
Hình 3.14: Thực thi chương trình đặt lịch tự động (4)......................................................... 61
Hình 3.15: Thực thi chương trình đặt lịch tự động (5)......................................................... 61
Hình 3.16: Thực thi chương trình đặt lịch tự động (6)......................................................... 62
Hình 3.17: Thực thi chương trình đặt lịch tự động (6)......................................................... 62
Hình 3.18: Giao diện màn hình quản lý trên Server TW ..................................................... 63
Hình 3.19: Thực thi mô đun Quản lý gói cập nhật (1) ......................................................... 63
Hình 3.20: Thực thi mô đun Quản lý gói cập nhật (2) ......................................................... 64
Hình 3.21: Thực thi mô đun Quản lý gói cập nhật (3) ......................................................... 64
Hình 3.22: Thực thi mô đun Quản lý gói cập nhật (4) ......................................................... 65
Hình 3.23: Thực thi mô đun Quản lý danh sách chi nhánh (1) ............................................ 66
Hình 3.24: Thực thi mô đun Quản lý danh sách chi nhánh (2) ............................................ 66
Hình 3.25: Thực thi mô đun Quản lý danh sách chi nhánh (3) ............................................ 67
Hình 3.26: Thực thi mô đun Quản lý danh sách ứng dụng (1) ............................................. 67
Hình 3.27: Thực thi mô đun Quản lý danh sách ứng dụng (2) ............................................. 68
Hình 3.28: Thực thi mô đun Upload thủ công gói cập nhật (1)............................................ 68
Hình 3.29: Thực thi mô đun Upload thủ công gói cập nhật (2) .......................................... 69
Hình 3.30: Thực thi mô đun Upload thủ công gói cập nhật (3) .......................................... 69
Hình 3.31: Thực thi mô đun Xem nhật ký upload (1) ......................................................... 70
Hình 3.32: Thực thi mô đun Xem nhật ký upload (2) ......................................................... 70
9
MỞ ĐẦU
Trong các lĩnh vực của công nghệ thông tin - viễn thông hiện nay, việc truyền tải tin
tức đã là một công việc xảy ra thường xuyên. Tuy nhiên, thông tin được truyền tải đi
thường rất lớn, điều này gây khó khăn cho công việc truyền tải: gây tốn kém tài
nguyên mạng, tiêu phí khả năng của hệ thống… Để giải quyết vấn đề đó, các thuật
toán nén đã được ra đời.
Mỗi phương pháp nén có hiệu quả khác nhau với các loại tệp khác nhau. Luận văn
này sẽ trình bày một phương pháp nén có hiệu quả cao trong việc truyền tải tệp tin
trên mạng phục vụ cho việc cập nhật phiên bản của tệp tin. Phương pháp dựa trên sự
sai khác nhau giữa tệp nguồn và tệp đích (gọi là Differential Compression – hay Delta
Compression) - trong quá trình cập nhật, tệp nguồn là tệp cũ, tệp đích là tệp mới- và
tạo ra một bản vá có kích thước nhỏ đáng kể so với tệp đích. Khi đó, thay vì phải
truyền tệp đích có kích thước lớn trên mạng, ta chỉ cần truyền bản vá có kích thước
rất nhỏ. Phương pháp đã đạt được tỉ lệ nén cao, rất hiệu quả trong việc tiết kiệm tài
nguyên mạng. Nếu tỷ lệ nén cho các tệp thực thi thường dao động quanh 3:1 thì tỷ lệ
nén của bản vá so với tệp đích theo phương pháp Delta có thể nằm trong khoảng từ
10:1 tới 1000:1 và thậm chí có thể lớn hơn – tùy thuộc vào dung lượng tệp đích và
mức độ khác biệt của nó với tệp nguồn. Luận văn cũng trình bày ứng dụng của
phương pháp nén trong việc cập nhật phần mềm nghiệp vụ tại Ngân hàng Công
thương Việt Nam.
10
CHƯƠNG 1 - GIỚI THIỆU CHUNG VỀ MỘT SỐ CÔNG NGHỆ NÉN
1.1 Tầm quan trọng của nén dữ liệu trong truyền tin
Trong kỹ thuật truyền tin nối tiếp, do các bit dữ liệu được truyền đi nối tiếp, lại bị
giới hạn về dải thông của kênh truyền và giới hạn về các chuẩn ghép nối...nên tốc độ
truyền tin tương đối chậm. Ðể tăng tốc độ truyền, ta có thể dùng nhiều phương pháp
như sử dụng kỹ thuật điều chế pha nhiều mức, điều chế QAM, TCM ...
Nén dữ liệu trước khi truyền đi cũng là một trong các phương pháp nhằm tăng tốc độ
truyền dữ liệu. Trong các modem hiện đại, việc thực hiện nén dữ liệu trước khi
truyền đi có thể được thực hiện ngay trong modem theo các giao thức V42bis.
Phương pháp này đòi hỏi hai modem phải có cùng một giao thức nén dữ liệu, điều
này nhiều khi khó thoả mãn.
Có một phương pháp khác là thực hiện nén các tập tin ngay tại các máy vi tính trước
khi truyền đi, tại các máy tính nhận, các tập tin lại được giải nén để phục hồi lại dạng
ban đầu. Phương pháp này có ưu điểm là bên phát và bên thu chỉ cần có chung phần
mềm nén và giải nén, ngoài ra còn có thể áp dụng được để truyền dữ liệu qua các
modem không hỗ trợ nén dữ liệu hoặc truyền dữ liệu trực tiếp qua cổng COM của
máy tính. Nhược điểm của phương pháp này là các máy vi tính phải tốn thêm thời
gian nén và giải nén, nhưng do sự phát triển nhanh chóng của các bộ vi xử lý mà thời
gian thực hiện nén và giải nén được giảm nhỏ hơn rất nhiều thời gian để truyền dữ
liệu. Ví dụ, khi truyền một tập tin có kích thước là 100Kbyte với dạng thức của một
SDU là: 8 bits dữ liệu, 2 bit STOP và 1 bit START, không dùng bit chẵn lẻ, tốc độ
truyền là 9600bits/giây thì mất khoảng 120 giây, trong khi một máy vi tính với bộ vi
xử lí 80386 có thể thực hiện nén tập tin trên xuống còn 50Kbyte chỉ mất chưa đến 10
giây.
1.2 Nguyên tắc của nén dữ liệu
Thông thường, hầu hết các tập tin trong máy tính có rất nhiều thông tin dư thừa, việc
thực hiện nén tập tin thực chất là mã hoá lại các tập tin để loại bỏ các thông tin dư
thừa.
Nhìn chung không thể có phương phát nén tổng quát nào cho kết quả tốt đối với tất
cả các loại tập tin vì nếu không ta sẽ áp dụng n lần phương pháp nén này để đạt được
một tập tin nhỏ tuỳ ý! Kỹ thuật nén tập tin thường được áp dụng cho các tập tin văn
bản (Trong đó có một số kí tự nào đó có xác suất xuất hiện nhiều hơn các kí tự
khác), các tập tin ảnh bitmap (Mà có thể có những mảng lớn đồng nhất), các tập tin
11
dùng để biểu diễn âm thanh dưới dạng số hoá và các tín hiệu tương tự (analog signal)
khác (Các tín hiệu này có thể có các mẫu được lặp lại nhiều lần). Ðối với các tập tin
nhị phân như tập tin chương trình thì sau khi nén cũng không tiết kiệm được nhiều.
Ngoài ra, trong một số trường hợp để nâng cao hệ số nén người ta có thể bỏ bớt một
số thông tin của tập tin (Ví dụ như kỹ thật nén ảnh JPEG).
1.3 Một số phương pháp nén dữ liệu
1.3.1 Phương pháp mã hoá độ dài loạt (Run-Length Encoding)
Loại dư thừa đơn giản nhất trong một tập tin là các đường chạy dài gồm các kí tự lặp
lại, điều này thường thấy trong các tập tin đồ hoạ bitmap, các vùng dữ liệu hằng của
các tập tin chương trình, một số tập tin văn bản...
Ví dụ, xét chuỗi sau:
AAAABBBAABBBBBCCCCCCCCDABCBAAABBBBCCCD
Chuỗi này có thể được mã hoá một cách cô đọng hơn bằng cách thay thế chuỗi kí tự
lặp lại bằng một thể hiện duy nhất của kí tự lặp lại cùng với một biến đếm số lần kí
tự đó được lặp lại. Ta muốn nói rằng chuỗi này gồm bốn chữ A theo sau bởi ba chữ
B rồi lại theo sau bởi hai chữ A, rồi lại theo sau bởi năm chữ B... Việc nén một chuỗi
theo phương pháp này được gọi là mã hoá độ dài loạt. Khi có những loạt dài, việc
tiết kiệm có thể là đáng kể. Có nhiều cách để thực hiện ý tưởng này, tuỳ thuộc vào
các đặc trưng của ứng dụng (các loạt chạy có khuynh hướng tương đối dài hay không
? Có bao nhiêu bit được dùng để mã hoá các kí tự đang được mã ?).
Nếu ta biết rằng chuỗi của chúng ta chỉ chứa các chữ cái, thì ta có thể mã hoá biến
đếm một cách đơn giản bằng cách xen kẽ các con số với các chữ cái. Vì vậy chuỗi kí
tự trên được mã hoá lại như s