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

ĐẠ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