Luận văn 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ư sau: 4A3BAA5B8CDABCB3A4B3CD Ở đây "4A" có nghĩa là "bốn chữ A"... Chú ý là không đáng để mã hoá các loạt chạy có độ dài 1 hoặc 2 vì cần đến hai kí tự để mã hoá. Ðối với các tập tin nhị phân một phiên bản được tinh chế của phương pháp này được dùng để thu được sự tiết kiệm ÐÁNG KỂ. Ý tưởng ở đây là lưu lại các độ dài loạt, tận dụng sự kiện các loạt chạy thay đổi giữa 0 và 1 để tránh phải lưu chính các số 0 và 1 đó. Ðiều này giả định rằng có một vài loạt chạy ngắn (Ta tiết kiệm các bit trên một loạt chạy chỉ khi độ dài của đường chạy là lớn hơn số bit cần để biễu diễn chính 12 nó trong dạng nhị phân), nhưng khó có phương pháp mã hoá độ dài loạt nào hoạt động thật tốt trừ phi hầu hết các loạt chạy đều dài. Việc mã hoá độ dài loạt cần đến các biễu diễn riêng biệt cho tập tin và cho bản đã được mã hoá của nó, vì vậy nó không thể dùng cho mọi tập tin, điều này có thể hoàn toàn bất lợi. Ví dụ, phương pháp nén tập tin kí tự đã được đề nghị ở trên sẽ không dùng được đối với các chuỗi kí tự có chứa số. Nếu những kí tự khác được sử dụng để mã hoá các số đếm, thì nó sẽ không làm việc với các chuỗi chứa các kí tự đó. Giả sử ta phải mã hoá bất kì kí tự nào từ một bảng chữ cái cố định bằng cách chỉ dùng các kí tự từ bảng chữ cái đó. Ðể minh hoạ, giả sử ta phải mã hoá bất kì một chuỗi nào từ một chữ cái đó, ta sẽ giả định rằng ta chỉ có 26 chữ cái trong bảng chữ cái (và cả khoảng trống) để làm việc. Ðể có thể dùng vài chữ cái để biểu diễn các số và các kí tự khác biểu diễn các phần tử của chuỗi sẽ được mã hoá, ta phải chọn một kí tự được gọi là kí tự "Escape". Mỗi một sự xuất hiện của kí tự đó báo hiệu rằng hai chữ cái tiếp theo sẽ tạo thành một cặp (số đếm, kí tự) với các số đếm được biểu diễn bằng cách dùng kí tự thứ i của bảng chữ cái để biểu diễn số i. Vì vậy, chuỗi ví dụ của chúng ta sẽ được biểu diễn như sau với Q được xem là các kí tự "Escape" QDABBBAABQHCDABCBAAAQDBCCCD Tổ hợp của kí tự "Escape", số đếm và một kí tự lặp lại được gọi là một dãy Escape. Chú ý rằng không đáng để mã hoá các đường chạy có chiều dài ít hơn bốn kí tự, vì ít nhất là cần đến ba kí tự để mã hoá bất kì một loạt chạy nào. Trong trường hợp bản thân kí tự "Escape" xuất hiện trong dãy kí tự cần mã hoá ta sử dụng một dãy "Escape" với số đếm là 0 (kí tự space) để biểu diễn kí tự "Escape". Như vậy trong trường hợp kí tự "Escape" xuất hiện nhiều thì có thể làm cho tập tin nén phình to hơn trước. Các loạt chạy dài có thể được cắt ra để mã hoá bằng nhiều dãy Escape, ví dụ, một loạt chạy gồm 51 chữ A sẽ được mã hoá như QZAQYA bằng cách dùng trên. Phương pháp mã hoá độ dài loạt thường được áp dụng cho các tập tin đồ hoạ bitmap vì ở đó thường có các mảng lớn cùng màu được biểu diễn dưới dạng bitmap là các chuỗi bit có đường chạy dài. Trên thực tế, nó được dùng trong các tập tin .PCX, .RLE. 1.3.2 Phương pháp mã hoá Huffman 13 Các tập tin của máy tính được lưu dưới dạng các kí tự có chiều dài không đổi là 8 bits. Trong nhiều tập tin, xác suất xuất hiện các kí tự này là nhiều hơn các kí tự khác, từ đó ta thấy ngay rằng nếu chỉ dùng một vài bit để biểu diễn cho các kí tự có xác suất xuất hiện lớn và dùng nhiều bit hơn để biểu diễn cho các kí tự có xác suất xuất hiện nhỏ thì có thể tiết kiệm được độ dài tập tin một cách đáng kể. Ví dụ, để mã hoá một chuỗi như sau: "ABRACADABRA" Nếu mã hoá chuỗi trên trong dạng mã nhị phân 5 bit ta sẽ có dãy bit sau: 0000100010100100000100011000010010000001000101001000001 Ðể giải mã thông điệp này, chỉ đơn giản là đọc ra 5 bits ở từng thời điểm và chuyển đổi nó tương ứng với việc mã hoá nhị phân đã được định nghĩa ở trên. Trong mã chuẩn này, chữ D xuất hiện chỉ một lần sẽ cần số lượng bit giống chữ A xuất hiện nhiều lần. Ta có thể gán các chuỗi bit ngắn nhất cho các kí tự được dùng phổ biến nhất, giả sử ta gán: A là 0, B là 1, R là 01, C là 10 và D là 11 thì chuỗi trên được biễu diễn như sau: 0 1 01 0 10 0 11 0 1 01 0 Ví dụ này chỉ dùng 15 bits so với 55 bits như ở trên, nhưng nó không thực sự là một mã vì phải lệ thuộc vào khoảng trống để phân cách các kí tự. Nếu không có dấu phân cách thì ta không thể giải mã được thông điệp này. Ta cũng có thể chọn các từ mã sao cho thông điệp có thể được giải mã mà không cần dấu phân cách, ví dụ như: A là 11, B là 00, C là 010, D là 10 và R là 011, các từ mã này gọi là các từ mã có tính prefix (Không có từ mã nào là tiền tố của từ mã khác). Với các từ mã này ta có thể mã hoá thông điệp trên như sau: 1100011110101110110001111 Với chuỗi đã mã hoá này ta hoàn toàn có thể giải mã được mà không cần dấu phân cách. Nhưng bằng cách nào để tìm ra bảng mã một cách tốt nhất ? Vào năm 1952, D.Huffman đã phát minh ra một cách tổng quát để tìm ra bảng mã này một cách tốt nhất. - Bước đầu tiên trong việc xây dựng mã Huffman là đếm số lần xuất hiện của mỗi kí tự trong tập tin sẽ được mã hoá. 14 - Bước tiếp theo là xây dựng một cây nhị phân với các tần số được chứa trong các nút. Hai nút có tấn số bé nhất được tìm thấy và một nút mới được tạo ra với hai nút con là các nút đó với giá trị tần số của nút mới bằng tổng tần suất của hai nút con. Tiếp theo hai nút mới với tần số nhỏ nhất lại được tìm thấy và một nút mới nữa lại được tao ra theo cách trên. Lặp lại như vậy cho đến khi tất cả các nút được tổ hợp thành một cây duy nhất. - Sau khi có cây nhị phân, bảng mã Huffman được phát sinh bằng cách thay thế các tần số ở nút đáy bằng các kí tự tương ứng. Ưu điểm của phương pháp mã hoá Huffman là đạt được hệ số nén cao (Hệ số nén tuỳ thuộc vào cấu trúc của các tập tin). Nhược điểm của phương pháp này là bên nhận muốn giải mã được thông điệp thì phải có một bảng mã giống như bảng mã ở bên gửi, do đó khi nén các tập tin bé hệ số nén không được cao. 1.3.3 Phương pháp nén LZW Phương pháp nén LZW được phát minh bởi Lempel - Zip và Welch. Nó hoạt động đựa trên một ý tưởng rất đơn giản là người mã hoá và người giải mã cùng xây dựng bản mã. Nguyên tắc hoạt động của nó như sau: - Một xâu kí tự là một tập hợp từ hai kí tự trở lên. - Nhớ tất cả các xâu kí tự đã gặp và gán cho nó một dấu hiệu (token) riêng. - Nếu lần sau gặp lại xâu kí tự đó, xâu kí tự sẽ được thay thế bằng dấu hiệu của nó. Phần quan trọng nhất của phương pháp nén này là phải tạo một mảng rất lớn dùng để lưu giữ các xâu kí tự đã gặp (Mảng này được gọi là "Từ điển"). Khi các byte dữ liệu cần nén được đem đến, chúng liền được giữ lại trong một bộ đệm chứa (Accumulator) và đem so sánh với các chuỗi đã có trong "từ điển". Nếu chuỗi dữ liệu trong bộ đệm chứa không có trong "từ điển" thì nó được bổ sung thêm vào "từ điển" và chỉ số của chuỗi ở trong "từ điển" chính là dấu hiệu của chuỗi. Nếu chuỗi trong bộ đệm chứa đã có trong "từ điển" thì dấu hiệu của chuỗi được đem ra thay cho chuỗi ở dòng dữ liệu ra. Có bốn qui tắc để thực hiên việc nén dữ liệu theo thuật toán LZW là: Qui tắc 1: 256 dấu hiệu đầu tiên được dành cho các kí tự đơn (0 - 0ffh). Qui tắc 2: Cố gắng so sánh với "từ điển" khi trong bộ đệm chứa đã có nhiều hơn hai kí tự. 15 Qui tắc 3: Các kí tự ở đầu vào (nhận từ tập tin sẽ được nén) được bổ sung vào bộ đệm chứa đến khi chuỗi kí tự trong bộ đệm chứa không có trong "từ điển". Qui tắc 4: Khi bộ đệm chứa có một chuỗi mà trong "từ điển" không có thì chuỗi trong bộ đệm chứa được đem vào "từ điển". Kí tự cuối cùng của chuỗi kí tự trong bộ đệm chứa phải ở lại trong bộ đệm chứa để tiếp tục tạo thành chuỗi mới. Ví dụ: Các bước để mã hoá chuỗi "!BAN!BA!BAA!BAR!" như sau (Bảng 4. 1): - Bước 1: Kí tự thứ nhất ‘!’ được cất vào bộ đệm chứa để chuẩn bị tạo nên một chuỗi. - Bước 2: Kí tự thứ hai ‘B’ nối thêm vào sau kí tự !. Vì trong "từ điển" chưa có chuỗi "!B" nên chuỗi này được thêm vào "từ điển" và được gán dấu hiệu là 100h (Vì từ 000h đến 0ffh được dành riêng cho các kí tự đơn: Qui tắc 1). ‘!’ được gửi ra còn ‘B’ phải ở lại trong bộ đệm chứa. 16 - Bước 3: Kí tự thứ ba ‘A’ thêm vào sau ‘B’. Chuỗi "BA" cũng chưa có trong "từ điển" nên nó được thêm vào "từ điển" và gán dấu hiệu là 101h. ‘A’ ở lại trong bộ đệm chứa còn ‘B’ được gửi ra. - Bước 4: Kí tự thứ tư ‘N’ thêm vào sau ‘A’ tạo thành chuỗi "AN" cũng chưa có trong "từ điển" nên được thêm vào "từ điển" và có dấu hiệu là 102h. ‘N’ ở lại trong bộ đệm chứa còn ‘A’ được gửi ra. - Bước 5: Kí tự thứ năm ‘!’ thêm vào sau ‘N’ để tạo thành chuỗi "N!", "N!" được thêm vào "từ điển" với dấu hiệu là 103h. ‘!’ ở lại còn ‘N’ được gửi ra. - Bước 6: Kí tự thứ sáu ‘B’ thêm vào sau ‘!’. Lần này thì chuỗi "B!" đã có trong "từ điển" nên không có kí tự nào được gửi ra. "B!" tiếp tục ở lại trong "từ điển" để tạo ra chuỗi mới. - Bước 7: Kí tự thứ bảy ‘A’ thêm vào sau ‘B’ để tạo thành chuỗi "B!A", do "B!A" không có trong "từ điển" nên nó được thêm vào "từ điển" và gán dấu hiệu là 104h đồng thời dấu hiệu 100h được gửi ra thay cho "B!" (Qui tắc 4). A tiếp tục ở lại trong bộ đệm chứa để tạo thành chuỗi mới. Các bước trên cứ thế tiếp tục cho đến khi hết tập tin cần nén. Việc giảm kích thước chỉ thực sự bắt đầu tại bước 7 khi mà một dấu hiệu 12 bits là được gửi ra thay cho hai byte "B!". Trong thuật toán nén này, phần lớn thời gian khi bắt đầu nén chủ yếu mất vào việc tạo "từ điển". Khi "từ điển" đủ lớn, xác suất gặp chuỗi ở bộ đệm chứa trong "từ điển" tăng lên và càng nén được nhiều hơn. Một điều cần chú ý ở đây là mỗi một dấu hiệu, 17 ta phải lưu một chuỗi trong "từ điển" để so sánh. Vì dấu hiệu được biểu diễn bằng một số 12 bits nên "từ điển" sẽ có 4096 lối vào, khi tăng số bit dể biễu diễn dấu hiệu lên thì hiệu quả nén sẽ tốt hơn nhưng lại bị giới hạn bởi bộ nhớ của máy tính. Vì dụ, khi dùng 16 bits để biểu diễn một dấu hiệu thì "từ điển" phải có đến 65536 lối vào, nếu mỗi lối vào có khoảng 20 kí tự thì "từ điển" phải lớn khoảng 1,2 MB. Với một từ điển có dung lượng như vậy rất khó có thể thực hiện trên các máy tính PC hoạt động dưới hệ điều hành DOS vì giới hạn của một đoạn (Segment) là 64KB. Ưu điểm của phương pháp nén LZW là bên nhận có thể tự xây dựng bảng mã mà không cần bên gửi phải gửi kèm theo bản tin nén. 1.3.4 Chọn phương pháp nén Mỗi phương pháp nén có các ưu nhược điểm riêng, thuật toán nén độ dài loạt (Runlength) không thể áp dụng cho mhiều loại tập tin được, ví dụ như tập tin chương trình, tập tin cơ sở dữ liệu... vì ở đó các loạt chạy là rất ngắn, do đó nếu áp dụng thuật toán này không những không làm bé tập tin mà còn làm phình to chúng. Hai thuật toán còn lại (Huffman và LZW) đều có thể áp dụng được để nén nhiều loại tập tin trên các máy vi tính. Thuật toán Huffman có ưu điểm là hệ số nén tương đối cao, phương pháp thực hiện tương đối đơn giản, đòi hỏi ít bộ nhớ, có thể xây dựng dựa trên các mảng bé hơn 64KB. Nhược điểm của nó là phải chứa cả bảng mã vào tập tin nén thì phía nhận mới có thể giải mã được do đó hiệu suất nén chỉ cao khi ta thực hiện nén các tập tin lớn. Thuật toán nén LZW có các ưu điểm là hệ số nén tương đối cao, trong tập tin nén không cần phải chứa bảng mã. Nhược điểm của thuật toán này là tốn nhiều bộ nhớ, khó thực hiện dựa trên các mảng đơn giản (bé hơn 64KB). Các thuật toán nén kể trên thường được áp dụng để nén các tập tin lưu trên máy tính hoặc trước khi truyền thông trên mạng. Trong trường hợp tập tin cần truyền trên mạng chỉ là một bản vá cho các tệp thực thi mà phiên bản cũ của chúng đã tồn tại trên máy đích, việc áp dụng các thuật toán trên sẽ không thực sự hiệu quả. Một công nghệ nén khác được Microsoft phát triển nhằm cập nhật phiên bản mới cho các tệp thực thi. Đó là công nghệ Delta Compression. 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 công nghệ 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 cơ sở. Vì vậy, việc áp dụng công nghệ Delta vào thực tiễn sẽ có ý nghĩa lớn trong truyền dữ liệu trên 18 mạng máy tính, giúp giảm lưu lượng trên đường truyền, giảm thời gian truyền nhận gói tin. 19 CHƯƠNG 2 – CÔNG NGHỆ NÉN DELTA Công nghệ nén Delta được phát triển bởi Microsoft, là một công nghệ nén dựa trên sự sai khác nhau của các file và được sử dụng cho việc cập nhật phần mềm. Quá trình nén dựa trên sự sai khác giữa 2 file, do đó mà tạo ra một file có kích thước nhỏ đáng kể hơn so với các phương pháp nén khác. 2.1 Tổng quan về công nghệ nén Delta 2.1.1 Tổng quan Trong một hệ thống nén dữ liệu thông thường, bộ nén chấp nhận một file và cung cấp một đại diện nhỏ gọn hơn của file đó. Bộ giải nén thực hiện chức năng ngược lại, chấp nhận một dạng file nhỏ gọn và xây dựng lại file ban đầu. Hình 2.1 mô tả quá trình này. Bộ nén chấp nhận dữ liệu F’ và đưa ra một đại diện đã nén C(F’). Sau đó, bộ giải nén chấp nhận C(F’) và xây dựng lại dữ liệu ban đầu F’. Hình 2.1 Bộ nén dữ liệu thông thường Hệ thống nén Delta cũng sử dụng một bộ nén, nhưng bộ nén này chấp nhận 2 input: một file đích (target file) và một file tham chiếu hay file cơ sở (basic file). Giống như các bộ nén thông thường khác, bộ nén Delta cũng cung cấp một đại diện nhỏ gọn hơn của file ban đầu. Đại diện nhỏ gọn hơn này còn được gọi là Delta[4], có thể tham chiếu tới phần dữ liệu tương tự được tìm thấy trong file cơ sở. Bộ giải nén Delta, hay applier, chấp nhận Delta cùng với file cơ sở, và xây dựng lại file đích (target file). 20 Hình 2.2 mô tả quá trình nén Delta. Bộ tạo Delta chấp nhận dữ liệu đích F’ cùng với dữ liệu cơ sở F, và cung cấp một đại diện đã nén ÄF-F’. Sau đó Delta applier chấp nhận delta ÄF-F’ cùng với phần dữ liệu cơ sở F, để xây dựng dữ liệu đích F’. Hình 2.2 Bộ nén Delta 2.1.2 Tính hiệu quả Delta sẽ nhỏ khi các file F và F’ gần giống nhau, điều này giống như sự khác nhau giữa file cơ sở và file đích. Sự khác nhau giữa 2 phiên bản có thể nhỏ (khi cần update/fix các yếu tố mới được làm gần đó) và khi đó, delta sẽ nhỏ. Tuy nhiên, bộ nén Delta không bị giới hạn đối với việc tạo ra các bản delta giữa các phiên bản khác nhau của cùng 1 file [9]. Quá trình tạo này cần 2 file là input. Kích thước của file delta tuỳ thuộc vào sự giống nhau giữa 2 file này. Phần dữ liệu xuất hiện trong target không giống trong basic sẽ được nén. Trong trường hợp xấu nhất, khi basic và target không có điểm nào chung, delta sẽ là một dạng nén của target. Delta Compression API yêu cầu các dạng đặc biệt của các file có thể thực thi (chẳng hạn EXE hoặc DLL). Nói riêng, các dạng file có thể thực thi được thiết kế để chạy trên dòng Intel 32 bit i386 sẽ có cách đối xử riêng. Khi file basis và target là các file thực thi giống nhau, kích thước của delta có thể giảm tới 50-70% [4]. 2.2 Nền tảng 2.1.3 Nền tảng chung 21 Nhắc lại rằng, trong vấn đề về bộ nén delta, chúng ta có 2 file, và mục đích là ước lượng 1 file fδ có kích thước nhỏ nhất có thể và chúng ta có thể xây dựng lại 1 file fnew từ fδ và file fold [4]. Trước đây, đã có nhiều nghiên cứu trong phạm vi sự biến đổi từ string sang string, thực hiện các thao tác insert, update và delete nhằm biến đổi từ string này sang string khác. Các nghiên cứu để giải quyết vấn đề này dựa trên việc tìm kiếm chuỗi ký tự chung lớn nhất của 2 string bằng cách sử dụng chương trình động và bổ sung tất cả các ký tự còn lại vào fnew một cách rõ ràng [8]. Tuy nhiên, vấn đề biến đối string – string vẫn không phải là trường hợp tổng quát đối với bộ nén delta. Để giải quyết các giới hạn trên, Tichy (một nhà nghiên cứu Ấn Độ) đã định nghĩa sự biến đổi string – string bằng việc di chuyển khối [6]. Một sự di chuyển khối lại được định nghĩa qua một bộ ba (p,q,l) trong đó fold [p,…,p+l-1]= fnew [q,…,q+l-1].Nó thể hiện một chuỗi có độ dài l và không có ký tự trống của fold và fnew. Cho trước fold và fnew, file fδ có thể được xây dựng như một tập chuyển đổi cực tiểu của khối di chuyển, vậy mỗi thành phần fnew[i] cũng xuất hiện trong fold sẽ không được chứa trong 1 khối di chuyển [6]. Cũng có một cách khác để xây dựng fδ là từ chuỗi chung dài nhất như đã được nghiên cứu trước đây [7]. Điều kiện tối thiểu đảm bảo sự so sánh tốt nhất theo hướng nghiên cứu di chuyển khối là chuỗi chung dài nhất. Như vậy, khi nào thì fδ là tối ưu với 1 cặp fold và fnew? Tichy cũng chỉ ra rằng thuật toán tham lam sẽ cho ra kết quả trong 1 tập chuyển đổi tối thiểu và fδdựa trên một tập tối thiểu đó có thể được xây dựng trong tuyến không gian và thời gian sử dụng cây tiền tố [6]. Tuy nhiên, các hệ số trong không gian phức tạp làm cho hướng nghiên cứu trở thành không thực tế. Một hướng nghiên cứu thực tế hơn là sử dụng bảng băm với không gian một chiều nhưng thời gian 2 chiều lại vô cùng phức tạp. Hướng nghiên cứu di chuyển theo khối đã nói ở trên đã mô tả một nền tảng cơ bản trong sự phát triển của thuật toán nén Delta. Trong khi các nghiên cứu trước đây tập trung vào sửa đổi – xây dựng một chuỗi tối ưu của thao tác chỉnh sửa nhằm truyền fold vào fnew, thuật toán di chuyển khối dựa trên thuật toán copy, trong đó fnew như một chuỗi tối thiểu của thao tác copy từ fold. Thuật toán nén Lempel-Ziv từ những năm 1980 đã thực hiện kỹ thuật nén delta theo hướng copy. Một cách đặc biệt, thuật toán LZ77 cũng được xem như một chuỗi thao 22 tác liên quan đến việc thay thế một tiền tố của string đang được mã hoá bởi một sự tham chiếu tới một substring y hệt đã được mã hoá trước đó. Trong sự thi hành mang tính thực tế nhất của LZ77, một thuật toán tham lam được sử dụng, nhờ đó, tiền tố phù hợp dài nhất được tìm thấy trong text đã mã hoá ngay trước đó sẽ được thay thế bởi một thao tác copy. Như vậy, nén delta có thể được xem một cách đơn giản như sự thi hành của LZ77 với fold đại diện cho text đã mã hoá trước đó. Trên thực tế, không có gì ngăn chúng ta chứa một phần của fnew đã mã hoá trong việc tìm kiếm một tiền tố phù hợp dài nhất. Một vài thay đổi bổ sung được yêu cầu để nhận một sự thi hành của LZ77 trên cơ sở kỹ thuật nén delta. Có rất nhiều sự thi hành như vậy đã được thiết kế nhưng khung cơ bản thì vẫn tương tự như vậy. Chúng chỉ khác nhau ở sự mã hoá và cơ chế update. Trong phần tiếp theo, chúng ta sẽ mô tả chi tiết một kỹ thuật như thế. 2.1.4 Bộ nén LZ77 - Nền tảng của bộ nén Delta Các bộ nén Delta phổ biến nhất hiện nay dựa trên thuật toán copy theo hướng nghiên cứu của Lempel-Ziv[9]. Một trong các tool đó là vdelta và sự biến thể của nó vcdiff, xdelta được dùng trong XDFS, và công cụ zdelta. Bây giờ, ta sẽ mô tả chi tiết bộ nén như vậy, sử dụng ví dụ của zdelta. Zdelta (tool) dựa trên thư viện nén zlib có thay đổi một chút, có một vài ý tưởng được bổ sung thêm vào đó. Ai đã quen thuộc với zlib, gzip và các thuật toán dựa trên Lempel-Ziv sẽ dễ dàng hiểu được sự mô tả này. Ý tưởng cơ bản là, để mã hoá file hiện thời ta sẽ chỉ ra substring trong file tham chiếu, cách làm này cũng tốt như mã hoá một phần trong file hiện thời. Để nhận biết sự phù hợp trong khi mã hoá, chúng ta duy trì 2 bảng, một cho file tham chiếu, Told, và một cho phần đã mã hoá của file hiện thời, Tnew. Bảng Tnew về bản chất được xử lý theo cách của bảng băm trong gzip, trong đó, chúng ta insert các thực thể mới khi chúng ta xem xét và mã hoá fnew. Bảng Told được xây dựng sớm hơn bằng cách quét fold , giả sử fold không quá lớn. Khi tìm kiếm sự phù hợp, chúng ta tìm trong cả 2 bảng để tìm ra sự phù hợp lớn nhất. Quá trình băm của 1 substring được làm trên 3 ký tự đầu tiên của nó[4] 23 Giả sử rằng cả 2 file tham chiếu và file hiện thời đều vừa trong bộ nhớ chính. Cả 2 bảng băm được khởi tạo rỗng. Các bước cơ bản trong khi mã hoá như sau (giải mã thì có thể suy ra từ việc mã hóa). 1. Tiền xử lý file tham chiếu For i = 0 to len (fold ) -3: (a) Tính hi = h ( fold [i, i+2] ), giá trị băm của 3 ký tự đầu tiên bắt đầu vị trí thứ i trong fold (b) Insert 1 con trỏ vào vị trí i trong bảng băm hi của Told 2. Mã hoá file hiện thời Khởi tạo các con trỏ p1,…pk bằng 0, với k=2 Set j=0 While j<= len(fnew): (a) Tính hj = h ( fnew [ j,j+2] ), giá trị băm của 3 ký tự đầu tiên bắt đầu từ vị trí j trong fnew (b) Tìm hj trong cả Told và Tnew để tìm ra một sự phù hợp tốt nhất, chẳng hạn, 1 substring trong fold hoặc một phần đã mã hoá rồi của fnew (phần có 1 tiền tố chung với độ dài lớn nhất bắt đầu tại vị trí j của fnew). (c) Insert một con trỏ tới vị trí j trong bảng băm hj của Tnew. (d) Nếu sự phù hợp có độ dài ít nhất là 3, mã hoá vị trí của sự phù hợp liên quan tới (tương ứng với) j nếu sự phù hợp trong fnew, và tương ứng với một trong các con trỏ pi nếu sự phù hợp trong fold. Nếu có rất nhiều sự phù hợp như vậy với cùng độ dài được tìm thấy trong (b), chọn cái có khoảng cách tương đối nhỏ nhất tới vị trí j trong fnew hoặc tới một trong các con trỏ trong fold. Cũng phải mã hoá độ dài của phần phù hợp và con trỏ được sử dụng trong tham chiếu. Tăng j thêm một phần bằng độ dài của sự phù hợp, và cập nhật con trỏ pi nếu có. (e) Nếu không có sự phù hợp nào tại độ dài tối thiểu 3, viết ra ký tự fnew[j] và tăng j lên 1. 24 Có một số chi tiết bổ sung trong sự thi hành. Đầu tiên, chúng ta có thể chọn một loạt các chính sách để cập nhật các con trỏ pi. Động cơ của các con trỏ này, giống như trong vdelta, là trong rất nhiều trường hợp, vị trí của sự phù hợp tiếp theo từ fold là một khoảng cách ngắn sau vị trí của cái trước, đặc biệt, khi các file giống nhau. Vậy, bằng việc update một trong số các con trỏ để trỏ tới vị trí cuối của của sự phù hợp trước đó, chúng ta hy vọng rằng sẽ mã hoá một cách ngắn gọn vị trí của sự phù hợp tiếp theo. Thông thường, chính sách di chuyển con trỏ một cách thông minh có thể dẫn tới việc bổ sung sự cái tiến trên các công cụ đang tồn tại. Một chi tiết quan trọng khác liên quan tới phương pháp được sử dụng để mã hoá khoảng cách, độ dài phù hợp, thông tin con trỏ và các ký tự. Ở đây, zdelta sử dụng phương pháp mã hoá Huffman được cung cấp bởi zlib, trong khi vdelta sử dụng sự mã hoá theo byte nhanh hơn rất nhiều nhưng lại ít cô đọng hơn. Ngược lại, xdelta không có sự mã hoá thông minh nào, nó để cho người dùng áp dụng một công cụ nén để đưa ra output[4]. gcc size gcc time emacs size emacs time Uncompressed 27288 - 27326 - Gzip 7479 24/30 8191 26/35 Xdelta 461 20 2131 29 Vcdiff 289 33 1821 36 Zdelta 250 26/32 1465 35/42 Bảng 2.1: Các kết quả nén cho bộ dữ liệu gcc và emacs (KB /s) 2.3 Thuật toán nén Delta Như trên đã nói, Delta sử dụng quá trình biến đổi từ string sang một string bằng các khối di chuyển. Phần này sẽ mô tả chi tiết về thuật toán. Vấn đề biến đổi từ một string sang một string (String – to – string correction [6] ) là quá trình tìm ra một chuỗi các thao tác chỉnh sửa tối thiểu nhằm thay đổi từ một string cho trước (string nguồn trong thuật toán nén) sang một string cho trước khác (string đích trong thuật toán nén)[6]. Có nhiều thuật toán tính một chuỗi chung dài nhất của hai string (Longgest common subsequence - LCS) và sau đó quan tâm tới các ký tự không được chứa trong LCS xem đó như các ký tự khác nhau giữa hai string. 25 Dưới đây là một thuật toán cung cấp chuỗi chỉnh sửa ngắn nhất khi biến đổi một string thành một string khác. Thuật toán sẽ là tối ưu trong trường hợp nó tạo ra một tập tối thiểu của xâu chung của một string đối với một string khác. Hai sự cải tiến về thời gian chạy của thuật toán cũng được nói tới. Thời gian chạy và không gian bộ nhớ của thuật toán cải tiến có thể so sánh được với thuật toán LCS. 2.3.1 Giới thiệu Vấn đề sửa từ string sang string là tìm ra một chuỗi các thao tác chỉnh sửa tối thiểu nhằm thay đổi từ một string cho trước sang một string cho trước khác. Độ dài của chuỗi chỉnh sửa thể hiện sự khác nhau giữa hai string. Các chương trình xác định sự khác nhau theo cách này thường được dùng trong các trường hợp sau: (1) Các chương trình khác nhau giúp xác định các phiên bản của text file khác nhau như thế nào. Chẳng hạn, việc tính toán sự khác nhau giữa các phần đã được xem xét rồi của 1 mô đun phần mềm sẽ giúp các lập trình viên đánh dấu sự phát triển (tiến triển) của mô đun trong quá trình sửa chữa, hoặc giúp cho việc tạo các test case để thi hành các phần đã thay đổi của mô đun. Một ứng dụng khác sẽ tự động tạo ra các vạch thay đổi cho các phiên bản mới. (2) Các tài liệu được xem lại một cách thường xuyên như các chương trình hay các bức đồ hoạ được lưu một cách kinh tế nhất thành một tập có liên quan tới phiên bản cơ sở. Vì các thay đổi thì thường nhỏ và chỉ chiếm khoảng chưa đầy 10% không gian cần thiết cho 1 bản copy hoàn chỉnh, các kỹ thuật khác có thể lưu tương đương khoảng 11 bản đã được xem lại trong 1 không gian nhỏ hơn so với việc lưu giữ 2 bản đã được xem lại (1 bản gốc và 1 bản sao lưu) trong định dạng clear text. (3) Các thay đổi đối với các chương trình và các dữ liệu khác được phân tán một cách kinh tế nhất, chúng là một chuỗi các chỉnh sửa nhằm biến đổi phiên bản cũ thành một phiên bản mới. Hướng nghiên cứu này thường được dùng trong phân tán phần mềm. Một ứng dụng có liên quan có thể được tìm thấy trong các phiên bản hiển thị và các gói đồ hoạ. Các chương trình này cập nhật một cách hiệu quả bằng cách tính sự khác nhau về nội dung giữa phiên bản cũ và mới, sau đó chỉ truyền những thay đổi tới phần hiển thị. (4) Trong lĩnh vực di truyền học, các thuật toán khác nhau so sánh các phân tử dài. Sự khác nhau cung cấp một mối quan hệ giữa các loại cơ thể sinh vật . Hầu hết các chương trình hiện tại tính toán sự khác nhau đều dựa trên các thuật toán xác định chuỗi chung dài nhất (LCS). Một LCS của hai string chứa chuỗi các ký tự 26 chung của hai string bằng cách xoá đi 0 hoặc nhiều ký tự từ mỗi string đó [8]. Chẳng hạn, LCS của hai string shanghai và sakhalin là sahai. Khi một LCS đã được tạo ra, tất cả các ký tự không được chứa trong nó được xem như là phần khác nhau giữa hai string. Qua quá trình scan đồng thời trên hai string, LCS sẽ tách các ký tự này ra một cách nhanh chóng. Chẳng hạn, trong đoạn script dưới đây, dựa trên LCS sahai, chúng ta có thể xây dựng chuỗi sakhalin từ chuỗi shanghai: M 0,1 M 2,1 A “k” M 5,2 A “l” M 7,1 A “n” Trong đó, lệnh dạng M p,l là lệnh di chuyển, nó thêm một chuỗi S[p,….p + l - 1] của chuỗi S tới chuỗi đích. Lệnh dạng A “w” thêm chuỗi w tới chuỗi đích. Trong ví dụ trên, script chiếm nhiều không gian bộ nhớ hơn chuỗi đích. Trong các trường hợp thực tế, chuỗi chung không phân mảnh, và một sự di chuyển đơn bao gồm cả một chuỗi dài. Thêm vào đó, nếu kỹ thuật này được áp dụng đối với text, người ta thường chọn cả một dòng text hơn là các ký tự đơn lẻ. Do đó, không gian nhớ cho 1 hành động di chuyển sẽ không đáng kể so với lệnh thêm (Add), do đó cần giảm một cách tối đa lệnh Add. Chú ý rằng, trong ví dụ trên, lệnh Add cuối cùng có thể được thay thế bằng một lệnh Move, bởi vì ký tự “n” đã xuất hiện trong cả hai chuỗi. Nếu theo định nghĩa của LCS, thì “n” không thể được chứa trong LCS. Thuật toán được giới thiệu sau đây sẽ không bỏ sót các trường hợp như vậy. 2.3.2 Đặt vấn đề: Cho hai string S = S [0,….n], n  0 và T = T[0,….m], m  0, một khối di chuyển là một bộ (p,q,l) với S[p,….p+l-1] = T[q,….q+l-1] ( 0 p  n-l+1, 0 q  m-l +1, l>0) [6]. Như vậy, một khối di chuyển là một chuỗi chung không rỗng của S và T có độ dài l, bắt đầu tại vị trí p trong xâu S và vị trí q trong xâu T. Một tập phủ của T đối với S, biểu thị là S(T), là một tập của khối di chuyển, trong đó mỗi ký tự T[i] xuất hiện trong S sẽ được chứa chính xác trong một khối di chuyển. Ví dụ, một tập phủ của T=abcab đối với S = abda là [(0,0,2),(0,3,2)]. Một tập phủ tầm thường bao gồm các khối di chuyển có độ dài 1, thể hiện mỗi ký tự T[i] cũng xuất hiện trong S. 27 Vấn đề là tìm ra 1 tập phủ tối thiểu, S(T), trong đó |S(T)|  |S(T)| với mọi S(T). Thuộc tính bao phủ của S(T) đảm bảo rằng nó chứa tất cả sự phù hợp có thể, thuộc tính tối thiểu khiến số lượng khối di chuyển (và do đó, cả đoạn script chỉnh sửa) nhỏ nhất có thể. Do thuộc tính bao phủ, rõ ràng rằng S(T) chứa LCS của S và T (xem sự móc nối của các xâu T[qj, ….qj+lj-1], trong đó (pj,qj,lj) là một khối di chuyển của S(T), và các xâu con theo thứ tự tăng của qj). Ép buộc tối thiểu đảm bảo rằng LCS không thể cung cấp 1 sự tạo ra khối di chuyển tốt hơn. 2.3.3 Những nghiên cứu đầu tiên Trước khi trình bày về giải pháp, chúng ta sẽ nói về các nghiên ban đầu. Hướng nghiên cứu đầu tiên là sử dụng LCS. Như chúng ta đã biết, một LCS có thuộc tính không cần thiết tạo ra một tập phủ của các khối di chuyển. Ví dụ, 2 cặp xâu sau đây đều chứa LCS abc nhưng không chứa xâu chung (được di chuyển) de hoặc xâu chung (được lặp lại) abc. LCS phù hợp được chỉ ra ở bên trái, S(T) ở bên phải. S = a b c d e S = a b c d e T = d e a b c T = d e a b c S= a b c S= a b c T= a b c a b c T= a b c a b c Heckel chỉ ra các vấn đề tương tự như vậy với thuật toán LCS và đề xuất một thuật toán (theo thời gian) để dò khối di chuyển [7]. Thuật toán sẽ thực hiện thoả đáng trong trường hợp có các ký tự lặp lại trong xâu. Tuy nhiên, trong các trường hợp khác, thuật toán cho kết quả không tốt. Ví dụ, với hai xâu aabb và bbaa, thuật toán của Heckel sẽ thất bại trong việc tìm ra xâu chung. Một sự cải tiến của hướng nghiên cứu LCS là áp dụng việc tách LCS một cách lặp đi lặp lại. Ví dụ, sau khi tìm ra LCS đầu tiên trong ví dụ trên, ta sẽ loại bỏ nó từ xâu đích 28 T và tính lại LCS. Quá trình này được lặp lại cho tới khi chỉ còn lại một LCS có độ dài 0. Chiến lược phân tách LCS thành công trong việc tìm ra một tập phủ, nhưng không tối thiểu. Ví dụ sau đây minh hoạ: S = a b c d e a S = a b c d e a T = c d a b T = c d a b Giả sử rằng S là xâu nguồn, T là xâu đích, biểu đồ bên trái chỉ ra sự phù hợp đạt được qua một thuật toán phân tách LCS. LCS đầu tiên là cda, LCS thứ hai là b. Vì cda không phải là một xâu con của S, chúng ta sẽ đạt được 3 khối di chuyển. Tập phủ tối thiểu, được chỉ ra ở bên phải, bao gồm 2 khối di chuyển. Một chiến thuật khác là tìm xâu chung dài nhất hơn là chuỗi chung dài nhất (chuỗi bao gồm các khoảng trắng, xâu thì không có khoảng trắng). Việc tính xâu chung dài nhất một cách lặp lại đã có kết quả trong 1 tập phủ, nhưng không cần thiết tạo tính tối thiểu. Hãy xem ví dụ sau: S = a b c d e f d e a b S = a b c d e f d e a b T = c d e a b c T = c d e a b c Sơ đồ bên trái chỉ ra khối di chuyển đạt được bằng cách tìm kiếm lặp đi lặp lại xâu chung dài nhất của S và T. Kết quả là, ta có một tập của 3 khối di chuyển, mặc dù chỉ 2 khối là tối thiểu. Việc tìm kiếm xâu chung dài nhất là một phương pháp tham lam, vì nó có thể che giấu sự phù hợp tốt hơn. 2.3.4 Thuật toán cơ bản Thuật toán bắt đầu từ phía bên trái của xâu đích T, và cố gắng tìm ra tiền tố của T trong S. Nếu không có tiền tố nào của T trong S, ta loại bỏ ký tự đầu tiên của T đi và bắt đầu lại. Nếu có nhiều tiền tố như vậy trong S, ta chọn tiền tố dài nhất và ghi nó như một khối di chuyển. Sau đó, loại bỏ tiền tố tương ứng từ T và sau đó tiếp tục với tiền tố dài nhất trong phần đuôi còn lại của T, và bắt đầu với phần đầu của S. Tiến trình này tiếp tục cho tới khi T hết các ký tự. Khối di chuyển được ghi lại tạo thành S(T), một tập phủ tối thiểu của khối di chuyển của T đối với S, sẽ được hình thành sau đó. Ví dụ dưới đây chỉ ra các bước trong sự thi hành của thuật toán. Bước 1: 29 S = u v w u v w x y T = | z u v w x w u Khối di chuyển dài nhất bắt đầu tại T[0]: none Trong bước 1, chúng ta tìm kiếm 1 tiền tố của T[0,…,6] trong S[0,….,7], do không có sự phù hợp nào, chúng ta tìm kiếm sự phù hợp của tiền tố T[1,…,6] trong bước tiếp theo. Lần này, chúng ta tìm thấy 2 sự phù hợp, và sẽ chọn sự phù hợp dài nhất, bắt đầu tại S[4]. Trong bước thứ 3, chúng ta tìm kiếm cho tiền tố T[5,..6] trong S[0,…7], và tìm thấy sự phù hợp dài nhất tại S[2], có độ dài 2. Bây giờ, T đã được xét hết và thuật toán kết thúc. Chú ý rằng, trong mỗi bước, chúng ta sẽ bắt đầu tại phần bên trái nhất của S để xem xét tất cả sự phù hợp có thể. Thuật toán sẽ được mô tả dưới đây. Chúng ta giả định rằng, xâu nguồn được lưu trong mảng S[0…m] và xâu đích được lưu trong T[0,…n]. T[q] là ký tự đầu tiên của phần đuôi không tương thích. của T, q được khởi tạo bằng 0. Thuật toán như sau: q:=0 While q<= n do Begin L: tìm p và l trong đó (p;q;l) là 1 khối di chuyển lớn nhất. If l>0 then print(p;q;l) q:=q+Max(1,l) End T = z| u v w x w u S = u v w u v w x y Bước 2: Khối di chuyển dài nhất bắt đầu tại T[1]: (3,1,4) T = z u v w x | w u S = u v w u v w x y Bước 3: Khối di chuyển dài nhất bắt đầu tại T[5]: (2,5,2) 30 Thực hiện câu lệnh có nhãn L thì rất đơn giản. Tìm S từ trái sang phải cho tiền tố dài nhất có thể của T[q…n]. Chú ý rằng, việc tìm kiếm có thể kết thúc ngay khi có ít hơn l+1 ký tự còn lại trong S, với l là độ dài lớn nhất của khối di chuyển đã được tìm thấy trong sự lặp lại hiện thời. Tương tự như vậy, sẽ không thể tìm thấy một khối di chuyển dài hơn nếu ký tự cuối cùng T[n] đã được đạt tới. L: l:=0; p:=0; pCur:=0 while pCur +1 <= m and q+1<= n do begin {Determine length of match between S[pCur…] and T[q…]} lCur :=0; while (pCur + lCur <= m) and (q+lCur <= n) and then (S[pCur + lCur] = T[q + lCur]) do lCur := lCur +1; if lCur >1 then begin {new maximum found} l:=lCur; p:=pCur end; pCur:=pCur +1 End Thời gian chạy của thuật toán được giới hạn bởi mn, không gian bộ nhớ yêu cầu là m+n. Bây giờ, chúng ta sẽ chỉ ra rằng thuật toán này sẽ tìm ra một S(T). Rõ ràng, tập các khối di chuyển được in ra là một tập phủ, bởi vì mỗi ký tự trong T mà không được chứa trong khối di chuyển nào (không thành công) sẽ được match lại mỗi ký tự trong S. Để thấy rằng tập phủ là tối thiểu, nghiên cứu T bên dưới, với sự match được cung cấp bởi thuật toán của chúng ta biểu thị dưới đây. Các xâu con trong các khối di chuyển được gộp lại bởi các dấu “(” và “)”. Các xâu con không được chứa trong các khối di chuyển được biểu thị bởi X chẳng hạn. …X(….)X(…)(….)X(….)(….)(….)X… Giả sử có ’S(T) có ít khối di chuyển hơn tập được tạo ra bởi thuật toán của chúng ta. Rõ ràng là, xâu con được định nghĩa bởi X không thể được chia ra bởi ’S(T) vì thuật toán của chúng ta không cung cấp 1 tập phủ. Chúng ta vì thế có thể không quan tâm tới tất cả những xâu con không phù hợp(X), và tập trung vào chuỗi các khối di chuyển liền nhau. Xem xét các khối di chuyển liên tiếp trong T. Để chứng minh tập phủ được tạo ra bởi thuật toán của chúng ta là tối thiểu, ta cần chứng minh rằng không thể chia tập phủ đó 31 thành m sự di chuyển (trong đó m<k, k là số sự di chuyển được tạo ra bởi thuật toán của chúng ta). Điều đó chứng tỏ, thuật toán của chúng ta tạo ra một tập phủ với ít sự di chuyển nhất. Giả sử chúng ta có k 1 khối di chuyển liên tiếp được tạo ra bởi thuật toán của chúng ta. Điều này có nghĩa rằng chúng ta sẽ có k bộ (pi,qi,li), (1  i  k) thoả mãn các điều kiện sau đây: Ai: 1  i  k T[qi,….,qi + li –1) = S[pi,…,pi+li –1] (*) Ai: 1  i  k Ap: 0  p  m - li, T[qi,….,qi + li]  S[p,…,p+li] (**) Ai: 1  i < k T[qi + li] = T[q(i+1)] (***) Điều kiện đầu tiên để định nghĩa một khối di chuyển. Điều kiện thứ hai đảm bảo rằng mỗi khối di chuyển bắt đầu tại T[qi] là cực đại. Điều kiện thứ ba đảm bảo khối di chuyển là liên tục trong T. Chúng ta cần chỉ ra rằng với bất kỳ k khối di chuyển nào thoả mãn (*) tới (***), bất kỳ tập tương đương nào cũng có ít nhất k khối di chuyển. Với bất kỳ tập k khối di chuyển thoả mãn (*) tới (***), bất kỳ tập phủ của k-1 khối di chuyển đầu tiên và một tiền tố không rỗng của khối di chuyển k có ít nhất k khối di chuyển. Đầu tiên, giả sử k=1. Rõ ràng, chúng ta không thể chia bất kỳ tiền tố không rỗng của 1 khối di chuyển đơn thành ít hơn 1 khối di chuyển bao phủ. Bây giờ, giả định rằng k>1, tập phủ của tất cả k-2 khối di chuyển và bất kỳ tiền tố không rỗng nào của khối di chuyển k-1 sẽ chứa ít nhất k-1 khối di chuyển. Giả sử ngược lại, ta chia tập phủ thành ít hơn k-1 khối di chuyển. Có 2 trường hợp. Trường hợp đầu tiên ta gom khối di chuyển h (trong đó, phpk-1) vào các khối di chuyển khác. Giả sử, ta gom vào khối h-1, điều này mâu thuẫn với (**). Nếu ta gom vào khối h+1, điều này cũng giống với việc ta gom khối h+1 vào đuôi của khối h. Điều này cũng mâu thuẫn với (**). Vậy, với bất kỳ khối h nào, ta cũng không thể gom vào khối ngay trước hoặc ngay sau nó. Do thuộc tính liên tục, ta cũng không thể gom vào các khối khác, ngoài 2 khối trước và sau nó. Trường hợp thứ 2, ta có thể chia khối di chuyển k-1 thành ít nhất 2 sự di chuyển không rỗng (nhìn vào hình dưới đây). Orig.block move no k-2 k-1 k Orig.set …….) ( ... | … ) (… | …) ’S(T) covering k-1 …… …) ( …) ’’S(T) covering k …… …) (… …) (…) 32 Do những lựa chọn nhằm giảm số lượng khối di chuyển xuống dưới k, ta sẽ thực hiện hợp các hậu tố của di chuyển gốc k-1 với một tiền tố không rỗng của di chuyển k. Tương tự như vậy, ta sẽ tạo ra (a) một tập phủ của khối di chuyển gốc k-2 và một tiền tố không rỗng của khối di chuyển k-1; (b) hợp của một hậu tố của di chuyển k-1 và một tiền tố của k; (c) một khối di chuyển khác nếu hậu tố của di chuyển k không rỗng. Theo giả thuyết, chúng ta biết rằng, (a) có ít nhất k-1 di chuyển. Thêm vào đó, (b) tạo ra 1 khối di chuyển nữa, (c) cũng có thể tạo ra một khối di chuyển nữa.Và cuối cùng, chúng ta sẽ kết thúc với ít nhất k di chuyển cho tập phủ của k-1 khối di chuyển đầu tiên và bất kỳ tiền tố không rỗng nào của di chuyển k. Vậy, bất kỳ tập tương đương nào của các khối di chuyển được tạo ra bởi thuật toán của chúng ta cũng có ít nhất k thành phần. 2.3.5 Sự cải tiến của thuật toán Cân nhắc trường hợp khi xâu nguồn S có một vài các ký tự giống nhau. Giả sử  là kích thước của phần ký tự giống nhau trong S (không tính các khoảng trắng), xấp xỉ bằng m. Trong trường hợp này, một sự cải thiện đáng kể của thuật toán có thể được thực hiện. Trong khi scan 1 lần S, chúng ta sẽ chuẩn bị một index, với mỗi ký tự s trong S, chúng ta liệt kê ra tất cả các vị trí có s trong S. Trong thuật toán, chúng ta thay thế câu lệnh có nhãn F với câu lệnh sau đây. Giả sử T[q]=s là ký tự đầu tiên của phần đuôi không phù hợp của T. Tìm kiếm trong danh sách L sự xuất hiện của s trong S bằng cách sử dụng index trên. Nếu danh sách rỗng, không có sự phù hợp nào tìm thấy. Mặt khác, ta sẽ tìm kiếm khối di chuyển lớn nhất trong số này bắt đầu với các thành phần của L trong S. Sự thi hành của thuật toán này sẽ như sau. Giả sử độ dài trung bình của một khối di chuyển là l. Vậy, khối di chuyển lớn nhất phải được chọn trong số m/ lựa chọn, mỗi lựa chọn sẽ tốn không nhiều hơn l+1 phép so sánh. Vậy, thời gian chạy của thuật toán là O(l*(m/alpha)*(n/l))=O(mn/). Nếu m  , chúng ta đạt được một thuật toán tương đối tốt. Các đoạn text hoặc các bài văn thì thường có các dòng lặp lại. Trong trường hợp đó, chỉ các dòng lặp lại nên được đặt rỗng hoặc bao gồm các dấu ngoặc đơn giống như begin và end; trong các trường hợp có sự lặp lại khác, chúng ta sẽ viết một chương trình con. Trong trường hợp văn xuôi, chỉ các dòng lặp lại nên được đặt rỗng hoặc chứa các lệnh khuôn mẫu. Để áp dụng thuật toán của chúng ta đối với đoạn text hoặc văn xuôi, cần phải chọn các dòng thích hợp giống như các ký tự nguyên tử. Để tăng 33 tốc sự so sánh, chương trình nên sử dụng các mã băm cho các dòng text hơn là thực hiện các phép so sánh từng ký tự. Chúng ta thực hiện một chương trình kết hợp chặt chẽ với các ý tưởng này, được gọi là bdiff, và so sánh nó với diff (diff sử dụng thuật toán LCS). Chúng ta thực hiện cả hai chương trình trên 1400 cặp file. Mỗi cặp bao gồm 2 sự xem lại text một cách liên tiếp. Hệ thống này lưu rất nhiều các file dữ liệu khác nhau. Hầu hết tất cả các file mẫu chứa các chương trình text. Chúng ta theo dõi diff và bdiff thi hành với tốc độ giống nhau, nhưng bdiff sẽ cung cấp delta chỉ nhỏ hơn khoảng 7% (trung bình). Nhìn bề ngoài, các khối di chuyển và các dòng trùng nhau trong các chương trình text thì thường không đủ để duy trì không gian cần thiết trên thuật toán LCS. Chúng ta mong muốn những tình huống có lợi hơn cho các khối di chuyển các ứng dụng khác đã được nói tới trong phần giới thiệu. Một sự cải tiến khác giúp tăng tốc thuật toán thậm chí nếu xâu nguồn chứa rất nhiều ký tự trùng nhau. Sự cải tiến liên quan tới sự thích nghi của thuật toán Knuth-Moris- Pratt [8], nó cho phép một khuôn mẫu có độ dài l được tìm thấy trong 1 xâu có độ dài m trong O(m+1) bước. Vậy, nếu S có độ dài m, T có độ dài n, và khối di chuyển trung bình có độ dài l, thuật toán của chúng ta nên thao tác O((m+1)*(n/l))=O(mn/l) bước. Chú ý rằng tỉ số m/l biểu thị sự khác nhau của S và T, và thời gian chạy của thuật toán sẽ tương ứng với tỉ số đó. Cũng chú ý rằng tỉ số đó độc lập với các xâu chung trong T và S. Một thành phần quan trọng trong thuật toán Knuth-Moris-Pratt là một mảng phụ N, nó chỉ ra sau 1 mismatch, một phần của mẫu match hay khối di chuyển phải dịch đi bao xa. Mảng N sẽ được tính trước khi có 1 match. Việc tính lại N sẽ đưa ra một vấn đề cho thuật toán. Vì chúng ta không biết được một khối di chuyển sẽ dài bao nhiêu, nên chúng ta sẽ phải tính trước N cho toàn bộ phần đuôi không xử lý của T, mặc dù bình thường chúng ta chỉ sử dụng một phần nhỏ của nó. Không may, N chỉ có thể được tính tăng dần. Những nét chính của thuật toán được chỉ ra trong phần sau. Giả sử, ký tự không phù hợp tiếp theo là T[q]. Bắt đầu khởi tạo N[q] và áp dụng thuật toán Knuth-Moris-Pratt để tìm ra sự xuất hiện đầu tiên của T[q]. (Chú ý rằng đây là một mẫu có độ dài 1). Nếu mẫu này không thể tìm thấy, sẽ không có khối di chuyển nào trong T[q]. Mặt khác, khi mở rộng mẫu thêm 1, ta sẽ tính phần tử tiếp theo trong N, và áp dụng lại thuật toán Knuth-Moris-Pratt để tìm ra sự xuất hiện đầu tiên của mẫu mở rộng. Bắt đầu tìm kiếm với match trước. Tiếp tục quá trình này, cho tới khi 34 mẫu đạt tới một độ dài mà tại đó không có sự match nào. Lúc đó, sự match trước là khối di chuyển cực đại. Cho rằng khối di chuyển lớn nhất bắt đầu tại T[q] là l. Như vậy, sự phù hợp cuối cùng có độ dài l+1, và lỗi. Việc tính tăng dần của N[q,…q+l+1] tại một giá trị tổng sẽ tương ứng với l đảm bảo rằng giá của match trung bình còn lại O(m+l). Chương trình chi tiết được cho trong phần mục lục. Ý tưởng của việc tính tăng dần cấu trúc dữ liệu bổ sung cũng có thể được dáp dụng với thuật toán Boyer-Moore matching [8], kết quả trung bình sẽ nhanh hơn. 2.3.6 Xây dựng lại xâu đích Một đoạn script nhằm xây dựng lại xâu đích T từ xâu nguồn S là một chuỗi của các lệnh move và add. Mỗi khối di chuyển (p, q, l) trong s(T) được biểu thị bởi một lệnh dạng M p,l, tiến hành copy xâu S[p,…p+l-1] tới phần đuôi của xâu T. Với bất kỳ xâu con T[u,…v] bao gồm toàn bộ các ký tự không xuất hiện trong S, đoạn script chứa câu lệnh A T[u,…v], đơn giản nó gắn các xâu con không phù hợp của T. Sau khi hoàn thành tất cả các câu lệnh, T=T. Thông thường, T không thể được xây dựng qua một bước đơn trên S, bởi vì các khối di chuyển có thể xen kẽ. Nếu S là một file liên tiếp, chúng ta có thể cực tiểu số thao tác tua lại được gây ra bởi sự xuất hiện xen kẽ của các khối di chuyển theo sau. Trong khi tạo ra đoạn script, việc lựa chọn 1 hoặc 2 hay nhiều khối di chuyển tương đương sẽ không có ý nghĩa. Ví dụ, giả sử chúng ta có các tập tương đương bắt đầu với T[q]: B1=(p1,q,l) và B2=(p2,q,l), với p1<p2. Nếu khối di chuyển trước có điểm cuối trong S nằm giữa S[p1] và S[p2], thì việc lựa chọn khối di chuyển B2 sẽ tiết kiệm được 1 thao tác tua lại cho S. Thuật toán của chúng ta thì dễ dàng chỉnh sửa để thực hiện ý tưởng đó. Hơn nữa, việc bắt đầu tại phần kết thúc bên trái của S trong khi tìm kiếm sự match dài nhất có thể, chúng ta sẽ phải bắt đầu tại điểm cuối cùng của sự match trước và gói gọn tại điểm kết của S. Hơn nữa, chúng ta đã giới thiệu đoạn script nhằm xây dựng T một cách độc lập từ S. Điều này cũng có nghĩa là biến đổi S “trong không gian”. Dưới đây sẽ bàn về chi tiết thuật toán. 35 Giả sử, chúng ta có mảng B[0,…Max(m,n)] khởi tạo lên S, chẳng hạn B[i] = S[i] với mọi 0in. Mục đích nhằm biến đổi nội dung của B thành T. Khoá của thuật toán này là một mảng bổ sung A[0,…n], lưu dấu vết về vị trí của ký tự gốc S[i] trong B. Khởi tạo, A[i]=S[i] với mọi 0in. Một biến h dùng để duyệt A từ trái sang phải, nó sẽ cho ta chỉ số của ký tự bên phải nhất liên quan tới khối di chuyển. Khi đó, nếu ta có câu lệnh di chuyển thành phần thứ k: M pk,lk,thì h = Max(pj+lj, 0jk). Ta cũng dùng một biến t để chỉ ra chỉ số của ký tự cuối cùng được xử lý trong B. Như vậy, A đại diện cho S và B được biến đổi dần để trở thành T. Bước đầu tiên là loại bỏ tất cả các ký tự từ B mà không có trong T. Đoạn script thực hiện tiền xử lý để nhận biết các ký tự được xoá, sau đó loại bỏ chúng luôn khỏi B. Nó cũng cập nhật mảng map A để phản ánh sự nén đối với các ký tự mà bản sao của chúng trong B đã được xoá, bằng cách đánh dấu các thực thể này của A. Bước thứ hai xử lý các lệnh trong chuỗi. Một lệnh add được insert vào bên phải của t, và t được đặt lại tới ký tự cuối cùng. Nó cũng cập nhật mảng A cho các ký tự được shift sang bên phải do sự insert đó. Với mỗi sự di chuyển dạng M p,l, so sánh p và giá trị hiện thời của h. Nếu p>h, khối di chuyển hiện thời là khối bên phải của khối trước. Các ký tự giữa h và p, chẳng hạn B[A[h+1],…A[p-1]], sẽ không được chứa trong khối di chuyển hiện thời, nhưng sẽ được loại bỏ sau đó. Đánh dấu chúng và đặt h= p+l-1 và t=A[h]. Vậy, các ký tự S[p,…p+l-1] sẽ được chứa trong kết quả. Mặt khác, nếu ph, khối di chuyển hiện thời sẽ nằm bên trái khối di chuyển trước đó, và một xâu con định vị phía trước t phải được di chuyển hoặc copy tiến về phía trước. Tất cả các ký tự trong xâu được đánh dấu để di chuyển bởi các lệnh trước đây bây giờ sẽ được di chuyển, các phần khác đơn giản được copy tiến lên. Cũng có thể hiểu rằng, khối di chuyển hiện thời có liên quan tới các ký tự bên trái hoặc bên phải của h. Trong trường hợp đó, đầu tiên xử lý xâu bên trái của h bằng cách di chuyển hoặc copy các thành phần của B[A[p],…A[Min(p+l-1,h)]] vào phía sau của B[t]. Phần còn lại (có thể rỗng), xâu A[h+1, ….p+l-1] sẽ được chứa bằng cách đặt h=Max(p+l-1,h). Cập nhật A để thể hiện sự di chuyển và thay đổi , và đặt t=A[h]. Dưới đây là một ví dụ về thuật toán, xâu nguồn shanghai và xâu đích là sakhalin bằng cách áp dụng đoạn script M 0,1; M2,1; A’’ k’’; M 1,2; A”l”; M 7,1; M 3,1. Thuật toán cũng có thể được áp dụng để cập nhật phần hiển thị một cách hiệu quả, cung cấp phần hiển thị cho ký tự và dòng được insert và delete, cũng như các thao tác copy/move. Mảng A được đặt trong bộ nhớ chính. h 36 S h a n g h a i X X X s h a n i T Sau khi loại bỏ các ký tự của B không xuất hiện trong A (có sắp xếp lại các ký tự trong B xuất hiện theo trình tự xuất hiện trong A) S h a n g h a i X X X s h a n i Sau khi áp dụng M 0,1 ; M 2,1 A[1] = ”h” được đánh dấu để di chuyển S h a n g h a i X X X s h a k n i t Sau khi áp dụng I “k” A B A A B h h t B 37 Sau khi áp dụng M 7,1; M 3,1 2.4 Một vài kết quả thí nghiệm Bây giờ, chúng ta sẽ chỉ ra một vài kết quả thí nghiệm về các công cụ nén đang tồn tại. Trong các kết quả này, chúng ta so sánh xdelta, vcdiff, và zdelta trong 2 tập file khác nhau. Một tập các file giả định sẽ được tạo ra nhằm mô tả sự tương tự giữa 2 file. Cụ thể, chúng ta sẽ tạo ra 2 file ngẫu nhiên fo và f1 có độ dài cố định, và sau đó thực hiện nén delta giữa fo và một file fm khác được tạo ra bởi sự pha trộn bằng cách copy text từ fo và f1 theo một tiến trình Markov đơn giản. Bằng cách biến đổi các tham số của tiến trình, chúng ta có thể tạo một số file fm với dãy tương tự từ 0 (fm=f1) đến 1 (fm=f0). S h a n g h a i s a k h a l n i X X X Sau khi áp dụng M 1,2; I “l” A h t B 38 Tất cả được chạy trên server Sun E450 bộ xử lý 2400 Mhz UltraSparc Iie và bộ nhớ 4GB, dữ liệu được lưu trong 10000 RPM SCSI . Chú ý rằng chỉ 1 CPU được sử dụng trong khi chạy, và sự tiêu tốn bộ nhớ không có ý nghĩa. (Chúng ta cũng đã chạy mỗi file trong bộ sưu tập và loại bỏ những cái đầu - kết quả chính trong quá trình này là để cực tiểu sự tiêu tốn dung lượng đĩa, và tập trung vào giá của CPU trong các phương pháp khác nhau). 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) 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 39 Với tập dữ liệu gcc và emacs, các số không thể nén và gzip ở phiên bản mới hơn. Chúng ta có thể thấy rằng nén delta có những cải thiện rõ ràng hơn gzip trên các file này, đặc biệt là với các file tương tự gcc. Trong số các bộ nén delta, zdelta nhận được tỉ lệ nén tốt nhất, chủ yếu là do việc sử dụng Huffman thay vì các mã dựa trên byte. Bộ nén xdelta thi hành tồi nhất trong các thí nghiệm này. Xdelta tập trung vào mục đích phân tách và nén, và do đó, một bộ nén chuẩn như gzip có thể được áp dụng đối với output của xdelta. Tuy nhiên, trong các thí nghiệm của chúng ta, các ứng dụng gzip không có kết quả cải thiện tốt nào trong các tập dữ liệu này. Về thời gian chạy, tất cả 3 bộ nén delta đều chậm hơn gzip, xdelta thì xong sớm nhất. Chú ý rằng, với cả gzip và zdelta, chúng ta sẽ tổng kết 2 con số khác nhau thể hiện tác động của phương pháp input/output trong sự thi hành. Đầu tiên, các số thấp hơn truy nhập file trực tiếp, trong khi các số thứ hai được đo lường bằng các chuẩn I/O. Số cho vcdiff được đo lường bằng các chuẩn I/O, trong khi xdelta sử dụng truy nhập file trực tiếp. Đưa các sự khác nhau này vào tính toán, tất cả các bộ nén delta chỉ chiếm 20% so với gzip, thậm chí chúng có thể xử lý 2 tập file trong khi gzip chỉ xử lý được một. Nhìn vào phần đồ thị về sự giống nhau giữa các file, chúng ta sẽ thấy cùng một thứ tự. Khi các file càng khác nhau nhiều, file nén delta có kích thước càng lớn, nhưng vẫn là tốt nhất trong các phép nén, trong khi đó, khi các file gần như là giống nhau thì các phương pháp đều hoạt động tốt. Tuy nhiên, chúng ta thấy rằng, vcdiff và zdelta có tác dụng ngay cả khi các file chỉ khác nhau một chút, trong khi đó, xdelta không cải thiện hơn so với gzip. ( Chú ý rằng gzip tự nó không cung cấp 1 ích lợi nào với các file không thể nén được). Chúng ta cũng thấy rằng thời gian chạy của bộ nén delta giảm khi sự giống nhau giữa các file tăng lên, điều này là do độ dài của sự phù hợp được tìm thấy trong file tham chiếu tăng lên (do đó làm giảm số lần tìm kiếm trong bảng băm). Sự ảnh hưởng lớn này giải thích tại sao bộ nén delta hầu như chạy nhanh bằng gzip đối với các file giống nhau nhiều như gcc và emacs; với các file có độ giống nhau là thấp, 3 bộ nén delta sẽ dài hơn khoảng 60% hoặc 100% so với gzip. 2.5 Các vấn đề liên quan 2.5.1 Khoảng trống miễn cưỡng trong bộ nén delta Như đã mô tả trong phần 2.2, thuật toán tham lam của Tichy đã đạt được kết quả trong một tập tuỳ ý nào đó của khối di chuyển. Cách di chuyển của các khối xác định cách mã hoá trong sự thực thi. Trong phần 2.3, chúng ta đã bàn về một sự thi hành 40 dựa trên khung LZ77. Tuy nhiên, các thuật toán này có thể cho một sự thi hành nghèo nàn hơn khi gặp phải giới hạn về bộ nhớ trong các bộ xử lý nén và giải nén. Đầu tiên, chúng ta thực hiện phép nén delta trong giới hạn về không gian và thời gian, điều này sẽ bị ảnh hưởng khi file fold và fnew có kích thước lớn. Một giải pháp đơn giản trong trường hợp này là có thể giới hạn sự tìm kiếm đối với các tiền tố dài nhất trong fold, các tiền tố này đứng trước các điểm kết thúc của các xâu đã được mã hoá. Tuy nhiên, các kết quả này sẽ không đạt được mức ý nghĩa đó khi các xâu con xuất hiện không cùng thứ tự trong cả fold và fnew. Để giải quyết vấn đề đó, người ta đưa ra một thuật toán là thuật toán chỉnh sửa một bước. Thuật toán sử dụng một buffer chứa tất cả các bản sao của yêu cầu, và thực hiện sự chỉnh sửa trên các yêu cầu này sau khi sự phù hợp tốt nhất được tìm thấy. Có 2 loại chỉnh sửa có thể làm. Chỉnh sửa đuôi (tail correction) được thực hiện sau khi insert 1 bản copy yêu cầu từ một phần chưa mã hoá trước đó của fold. Thuật toán cố gắng để mở rộng xâu phù hợp về phía sau trong cả fold và fnew . Nếu sự phù hợp như vậy được tìm thấy theo hướng giật lùi, có một khả năng cho việc thay thế lệnh copy trước đó bằng cách tích hợp chúng vào lệnh copy hiện thời. Loại chỉnh sửa thứ 2 là chỉnh sửa chung, có thể thực hiện khi 1 xâu con phù hợp M được tìm thấy trong phần đã mã hoá của fnew. Trong trường hợp này, thuật toán sẽ cố gắng để xác định xem đoạn mã hoá trước đó của M có thể đã được nén rồi hay chưa và vì thế M có thể được mã hoá bởi một lệnh copy đơn. Hơn nữa, để giới hạn tiêu tốn không gian chứa các xâu con, chúng ta sử dụng một kỹ thuật gọi là kiểm tra điểm. Kỹ thuật này sẽ đảm bảo một xâu con đã được insert vào bảng băm sao cho vùng vị trí nhỏ nhưng việc lựa chọn số phải thật cẩn thận. Kết quả của sự mở rộng này là kỹ thuật nén delta đảm bảo được cả các yêu cầu về không gian và thời gian, có thể làm việc với kích thước file bất kỳ. 2.5.2 Chọn file tham chiếu Trong một vài ứng dụng, sự thi hành của nén delta phụ thuộc lớn vào việc lựa chọn file tham chiếu phù hợp. Chẳng hạn, để nén một tập các file liên quan, chúng ta cần chọn cho mỗi file một hoặc nhiều file tham chiếu có sự giống nhau với nó; mỗi file tham chiếu tự nó cũng có thể nén theo cách này. Trong trường hợp có 1 file tham chiếu cho mỗi file nén, vấn đề này trở thành tìm một nhánh tốt hơn trong đồ thị tương ứng trực tiếp, trong đó, mỗi cạnh (i,j) có trọng số bằng kích thước của delta với i tương ứng với file tham chiếu j. Trong một số tài liệu, vấn đề này có thể giải quyết theo hướng bình phương của thời gian, tuy nhiên lại mắc phải 2 hạn chế: Đầu tiên, giải pháp có thể chứa một chuỗi các tài liệu rất dài cần phải truy nhập nếu muốn giải 41 nén một file cụ thể nào đó. Thứ hai, với một bộ sưu tập lớn, bình phương thời gian trở thành khó chấp nhận, nhất là vấn đề giá trong việc tính trọng số thích hợp của đồ thị trực tiếp. Nếu chúng ta áp độ dài cao hơn đối với chuỗi tham chiếu, sau đó tìm giải pháp tốt hơn thì sẽ trở thành thuật toán NP Complete. Nếu chúng ta cho phép mỗi file được nén sử dụng hơn 1 file tham chiếu, thì vấn đề này có thể được giảm tới 1 nhánh đồ thị tối ưu, như được chỉ ra trong thuật toán NP Complete thậm chí không có giới hạn độ dài của xâu. Một ví dụ của chuỗi tham chiếu dài là khi giải quyết với các phiên bản khác nhau của cùng 1 file, như một hệ thống điều khiển xem xét lại chẳng hạn. Trong trường hợp này, việc lựa chọn file tham chiếu nhằm cực tiểu hoá dữ liệu là hiển nhiên, nhưng sự lựa chọn này có thể phải yêu cầu đến những phiên bản rất cũ và do đó sẽ khá đắt. Rất nhiều kỹ thuật đã được đề xuất để giải quyết vấn đề này bằng cách tạo ra một số giới hạn các short cut tới các phiên bản cũ hơn. 2.5.3 Đồng bộ các file từ xa Trong phần này, chúng ta tập trung vào vấn đề đồng bộ các file ở xa, trong trường hợp khi server không có quyền truy nhập tới file tham chiếu. Những thuật toán đã biết đối với vấn đề này có khác biệt so với bộ nén delta. Chúng ta sẽ bàn về 2 hướng nghiên cứu chính: (1) hướng nghiên cứu dựa trên chuỗi dấu vân tay được thực hiện theo thuật toán rsync tuy nó không đạt được giới hạn tối ưu nào, và (2) dựa trên việc tô màu đồ thị, hướng này đạt được sự thi hành tối ưu dưới các mô hình hiện thời cho khoảng cách file, nhưng dường như nó không phù hợp trong thực tế. Chúng ta cũng sẽ bàn về các vấn đề liên quan trong việc đánh giá sự tương đồng của file và cách điều hoà tập các bản ghi trong một database. 2.5.3.1 Thuật toán rsync Chúng ta sẽ mô tả về thuật toán đồng bộ file được triển khai rộng rãi rsync của Tridgell và MacKerras. Một hướng nghiên cứu tương tự cũng được thực hiện bởi Pyne[7]. Giả sử ta có 1 cuộc giao tiếp giữa 2 bên thông qua điện thoại, mỗi bên có 1 bản copy của một cuốn sách. Bây giờ, giả sử 2 bản copy có thể khác nhau ở một vài chỗ nào đó. Bằng cách nào chúng ta có thể tìm ra 2 cuốn sách có giống nhau hay không, và nếu không thì chúng khác nhau ở chỗ nào và khác nhau như thế nào, mà không cần đọc hết toàn bộ cuốn sách qua điện thoại? Câu trả lời của câu hỏi đầu tiên rất đơn giản, bằng cách dùng hàm checksum (MD5 chẳng hạn) và so sánh checksum của 2 cuốn sách, như thế nó sẽ xác định được 2 cuốn sách có giống nhau hay không. Câu 42 trả lời cho câu hỏi thứ 2 thì khó hơn một chút. Một hướng nghiên cứu ban đầu là người ta chia cuốn sách thành 2 nửa, nửa đầu và nửa cuối, sau đó sẽ thực hiện checksum trên mỗi nửa, cho tới khi vị trí khác nhau được tìm ra. Tuy nhiên, hướng nghiên cứu này sẽ bị sai trong một trường hợp hết sức đơn giản, khi một cuốn sách chứa thêm một số từ vào đầu. Do đó, một hướng nghiên cứu khác, mạnh hơn là cần thiết mặc dù ý tưởng cơ bản vẫn là sử dụng checksum trên các khối. Chúng ta sẽ mô tả và chọn lọc thuật toán rsync. Ý tưởng cơ bản là giải quyết vấn đề về sự sắp xếp thẳng hàng bằng cách tính checksum khối cho file tham chiếu, và so sánh các checksum này với các checksum khối tương ứng của file hiện thời, và với checksum của tất cả các vị trí có thể của các khối trong file hiện thời. Kết quả là, server biết được đoạn nào của file hiện thời đã tồn tại trong file tham chiếu, và phần nào mới cần giao tiếp với client. Để đạt được hiệu quả, 2 checksum khác nhau sẽ được truyền thông tới server, tuy nhanh nhưng không đáng tin cậy, muốn đạt được sự tin cậy hơn thì cần đắt hơn nhiều. 1. Tại client: (a) Phần fold trong các khối Bi = fold [ib,(i+1)b-1] của kích thước b được xác định sau (b) Với mỗi khối Bi, tính 2 checksum, ui = hu (Bi) và ri = hr (Bi) và truyền chúng tới server. Ở đây, hu là hàm checksum không đáng tin cậy nhưng nhanh, và hr thì đáng tin cậy nhưng đắt. 2. Tại server: (a) Với mỗi cặp checksum nhận được (ui,ri), thêm một thực thể (ui,ri,i) vào cấu trúc dữ liệu từ điển, sử dụng ui như một giá trị khoá. (b) Thực hiện một bước trong fnew, bắt đầu tại vị trí j=0, và liên quan tới các bước sau: (i) Tính hàm checksum không đáng tin cậy hu(fnew [j, j+b-1]) trên khối bắt đầu tại j. (ii) Kiểm tra từ điển xem có khối nào có checksum không tin cậy phù hợp không (iii) Nếu tìm thấy, và nếu có checksum đáng tin cậy cũng phù hợp, truyền một con trỏ tới chỉ số của khối phù hợp trong fold tới client, j tiến tới vị trí b, và tiếp tục. (iv) Nếu không tìm thấy, hoặc nếu checksum tin cậy không phù hợp, truyền ký tự fnew[j] tới client, tăng j thêm 2 và tiếp tục. Tại client: Sử dụng dòng dữ liệu và con trỏ với khối trong fold để xây dựng lại fnew. 43 Checksum nhanh và không tin cậy được sử dụng để tìm ra sự phù hợp, và các checksum tin cậy sau đó được dùng để xác nhận sự phù hợp đó. Checksum phù hợp được thi hành bằng cách sử dụng MD4 (128 bit). Checksum không tin cậy có 32bit, nó cho phép chuyển một cách hiệu quả các đường bao khối bởi 1 ký tự, chẳng hạn, checksum cho f[j+1,j+b] có thể được tính trong thời gian không đổi từ f[j,j+b-1]. Rõ ràng, việc lựa chọn một kích thước khối tốt là tiêu chuẩn để thực hiện thuật toán. Sự lựa chọn tốt nhất lại phụ thuộc lớn vào sự giống nhau giữa 2 file – các file càng giống nhau thì chúng ta càng có thể chọn kích thước khối lớn. Hơn nữa, vị trí của các thay đổi trong file thì cũng rất quan trọng. Nếu một ký tự đơn được thay đổi trong mỗi khối của fold, thì không có sự phù hợp nào sẽ được tìm thấy tại server và rsync sẽ không thể hoàn thành một cách hiệu quả được; mặt khác, nếu tất cả các thay đổi được phân thành một vài vùng trên file, rsync sẽ làm rất tốt thậm chí với một kích thước khối lớn. Tuy nhiên, rsync không có sự thi hành tốt với không gian khoảng cách file. Tất nhiên, thông thường kích thước khối thậm chí có thể thay đổi trong một file. Trong thực hành, rsync bắt đầu với một kích thước khối hàng trăm byte, và sử dụng các phép heuristic để chỉnh sửa sau đó. 2.5.3.2 Các kết quả thực nghiệm của rsync Bây giờ, chúng ta sẽ đưa ra một vài kết quả về sự thi hành của rsync so với nén delta. Các kết quả sử dụng tập dữ liệu gcc và emacs. Chúng ta tổng kết 5 con số cho rsync: số lượng dữ liệu được gửi từ client tới server (request), số lượng dữ liệu được gửi từ server tới client (reply), số lượng dữ liệu được gửi từ server tới client với tuỳ chọn nén đã bật (reply compressed), và tổng số cho cả 2 hướng trong trường hợp không nén (total) và đã nén (total compressed). Gcc Emacs Uncompressed 27288 27326 Gzip 7479 8191 Xdelta 461 2131 Vcdiff 289 1821 Zdelta 250 1465 Rsync request 180 227 Rsyn reply 2445 12528 Rsync reply compressed 695 4200 44 Rsync total 2626 12756 Rsync total compressed 876 4428 Bảng 2.2: Các kết quả nén cho tập dữ liệu gcc và emacs (KB) 700 500 300 200 100 80 Rsync request 227 301 472 686 1328 1679 Rsync reply 12528 11673 10504 9603 8433 8161 Rsync reply compressed 4201 3939 3580 3283 2842 2711 Rsync total 12756 11974 10976 10290 9762 9810 Rsync total compressed 4429 4241 4053 3970 4170 4360 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) 2.5.3.3 Các ứng dụng Các ứng dụng cho đồng bộ file cũng tương tự như đối với thuật toán nén delta. Đồng bộ file thì phổ biến hơn, trong đó nó không yêu cầu các kiến thức về file tham chiếu; mặt khác, nén delta hướng tới thi hành sự đồng bộ một cách tốt hơn theo khía cạnh tỷ lệ nén. Có rất nhiều lý do tại sao server có thể không chứa các file tham chiếu, chẳng hạn do không gian bộ nhớ, do các phiên bản trước đó của file tham chiếu đã được cập nhật lên các phiên bản mới hơn… Dưới đây là một vài ví dụ: - Đồng bộ cho các file người dùng: Có một số gói phần mềm như rsync, Microsoft’s ActiveSync, Puma Technologies’ IntelliSync hay Palm’s HotSync cho phép đồng bộ giữa desktop, thiết bị mobile hay các tài khoản cá nhân có thể truy cập web. Trong phần này, các file hay các bản ghi có thể được update bởi rất nhiều phần khác nhau, và nhãn thời gian có thể được dùng để xác định phiên bản gần nhất. Chúng ta cần chú ý rằng có rất nhiều gợi ý cho các công cụ này. Với dữ liệu dạng file, chúng ta có thể đồng bộ các file từ xa, tránh được việc phải truyền toàn bộ file. Với dữ liệu tồn tại dưới dạng các tập lớn của các bản ghi nhỏ, chẳng hạn như danh sách các địa chỉ hay các cuộc hẹn trong các thiết bị cầm tay, vấn đề là làm thế nào để phân biệt các bản ghi này có thay đổi mà không cần gửi một dấu hiệu riêng hay các nhãn thời gian cho mỗi bản ghi. Vấn đề này, được mô hình hoá thành một tập hoà giải. Có rất nhiều các gói chương trình thực hiện truyền toàn bộ thực thể nếu có thay đổi nào xảy ra, thường thấy tại các tập dữ liệu dựa trên bản ghi nhỏ, không dùng cho các file lớn. Thêm vào đó, cũng có những vấn đề về việc định nghĩa về ngữ nghĩa thích hợp trong hệ thống đồng bộ file. 45 - Lưu trữ từ xa các tập dữ liệu khổng lồ: Việc đồng bộ có thể được sử dụng để lưu trữ từ xa các tập dữ liệu mà chỉ có thay đổi một chút giữa các lần cập nhật. Trong trường hợp này, việc giữ các phiên bản cũ tại server có giá đắt làm cho kỹ thuật nén delta trở lên không hiệu quả. - Truy cập web: Đồng bộ file cũng được dùng cho việc truyền HTTP giữa các client với một server hoặc proxy. Lợi ích của nó là server không cần phải giữ dấu vết của các phiên bản cũ được giữ tại client, và cũng không cần phải tìm lại các phiên bản ấy từ đĩa. Tuy nhiên, như chỉ ra trong phần trên, kỹ thuật đồng bộ file có tỷ lệ nén tồi hơn nén delta, và vì thế nó không chỉ đem lại những lợi ích cho các file tương tự nhau. - Hệ thống phân tán ngang hàng: Đồng bộ cũng được dùng cho việc cập nhật các cấu trúc dữ liệu phân tán cao như: routing table, name services, indexes, hay replication tables. 46 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 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 Nam Dưới đây là mô hình của hệ thống công nghệ thông tin trong ngân hàng. Hình 3.1: Mô hình hệ thống công nghệ thông tin tại NHCTVN Toàn hệ thống ngân hàng bao gồm rất nhiều chi nhánh trên khắp các tỉnh thành của cả nước. Mỗi chi nhánh lại bao gồm nhiều điểm giao dịch, phòng giao dịch. Tại mỗi điểm giao dịch, có thể có nhiều máy tính Client PC chứa các phần mềm nghiệp vụ giúp các giao dịch viên làm việc với khách hàng. Tại mỗi chi nhánh, có một máy chủ Branch Server nhằm quản lý dữ liệu tập trung của toàn bộ chi nhánh. Các máy chủ chi nhánh này lại được quản lý bởi một máy chủ Server vùng. Có ba máy chủ Server vùng là North Server, Middle Server và South Server tương ứng với ba vùng bắc, trung, nam. Các máy chủ Server vùng lại được quản lý bởi một máy chủ Server của toàn hệ thống, gọi là HQ Server. 47 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 Khi có một nghiệp vụ mới, hoặc khi cần thay đổi các tham số cho một vài nghiệp vụ đang tồn tại,… các phần mềm nghiệp vụ cần được cập nhật tới tất cả các máy tính trong toàn hệ thống. Vậy, bài toán đặt ra là làm thế nào để các phần mềm này được cập nhật nhanh, kịp thời và chính xác? Thông thường, các thay đổi về phần mềm nghiệp vụ trong ngân hàng thường bao gồm hai phần: phần thứ nhất cập nhật trong cơ sở dữ liệu (chỉ cập nhật một lần trên máy chủ chi nhánh cho toàn bộ một chi nhánh, bằng cách chạy các file script); phần thứ hai cập nhật các file (dạng exe, rpt, dll…) cập nhật cho tất cả các máy bằng cách copy file. Toàn bộ quá trình do cán bộ điện toán của chi nhánh thực hiện. Trước tiên, cán bộ điện toán chạy file cript để cập nhật database. Sau khi cập nhật thành công database, cán bộ điện toán tiến hành copy các file cập nhật vào mỗi máy của từng giao dịch viên. Quy trình này sẽ xảy ra nhiều sai sót: Nếu file script bị lỗi (do bị mất mát dữ liệu trên đường truyền từ trung ương về chi nhánh), hoặc database chi nhánh không đáp ứng đủ các điều kiện đê chạy thành công file script, quá trình chạy script sẽ bị lỗi. Cũng có khi quá trình chạy script bị lỗi mà cán bộ điện toán không phát hiện ra (do sơ suất hoặc do trình độ thấp, không hiểu hết các lỗi). Điều này sẽ ảnh hưởng tới hoạt động của toàn chi nhánh, gây phiền hà cho khách hàng, mất lòng tin của khách hàng, ảnh hưởng đến uy tín của ngân hàng… Bên cạnh đó, việc cán bộ điện toán phải copy toàn bộ các file cần cập nhật đến mỗi máy tính cũng tiêu tốn rất nhiều thời gian, công sức. Các phòng giao dịch, điểm giao dịch trong một chi nhánh có thể ở các vị trí địa lý rất xa nhau. Trong khi đó, có những phần mềm nghiệp vụ yêu cầu điện toán chi nhánh phải cập nhật ngay trong ngày, hoặc trước giờ giao dịch của buổi sáng hôm sau… Rõ ràng là, quy trình cập nhật này còn rất nhiều nhược điểm. 3.3 Chương trình cập nhật tự động các phần mềm nghiệp vụ 3.3.1 Thiết kế hệ thống Hệ thống đáp ứng các yêu cầu của chương trình cập nhật tự động sẽ không có thay đổi so với hệ thống hiện tại. Tuy nhiên, hệ thống cũng phải đảm bảo các yêu cầu tính thống nhất, trình tự và dễ kiểm soát. Chẳng hạn, khi có một phần mềm nghiệp vụ cần được cập nhật, phần mềm ấy cần phải được cập nhật đồng bộ cho toàn hệ thống. Không thể xảy ra trường hợp, vào cùng một thời điểm, tại các điểm giao dịch khác nhau, phiên bản chạy của một phần mềm nghiệp vụ nào đó khác nhau. Tính dễ kiểm soát được thể hiện ở chỗ, trong quá trình thực hiện cập nhật tự động toàn hệ thống, 48 nếu phát sinh lỗi cập nhật tại một chi nhánh nào đó, lỗi này sẽ không làm ảnh hưởng đến các chi nhánh khác. Đồng thời, cán bộ thực hiện cập nhật có thể phát hiện ngay lỗi đang xảy ra tại chi nhánh nào, lỗi đó là gì (do đường truyền, do virus, do cấu hình máy client không tương thích, …). Quá trình cập nhật lại cho chi nhánh bị lỗi cũng phải không gặp bất kỳ khó khăn nào. Dựa trên mô hình hệ thống công nghệ thông tin và quy trình cập nhật phần mềm nghiệp vụ tại Ngân hàng Công Thương Việt Nam, các cán bộ thuộc Trung tâm công nghệ thông tin – Ngân hàng công thương Việt Nam đã nghiên cứu và hoàn thiện chương trình cập nhật tự động các phần mềm nghiệp vụ. Chương trình đã thực sự giúp ích rất nhiều cho các cán bộ điện toán tại chi nhánh, đồng thời giảm thiểu tối đa những sai sót cũng như sự tiêu tốn về thời gian và dung lượng trên đường truyền dữ liệu. Chương trình thực hiện theo quy trình sau: - Các gói cập nhật được tạo tại Server TW (HQ), sau đó sẽ được upload xuống các Server Vùng (North, Middle, South). - Các Server Vùng được xem như tầng trung gian, có nhiệm vụ trung chuyển các gói cập nhật từ Server HQ xuống các Server chi nhánh trong vùng. - Tại các máy PC client, chương trình sẽ tự động kiểm tra các gói cập nhật từ Server Chi nhánh và tiến hành cập nhật (nếu có). Phần mô tả về thiết kế chương trình dưới đây sẽ phân tích rõ hơn trong mỗi tầng của hệ thống. 3.3.2 Thiết kế chương trình Chương trình gồm 2 phần: - Đặt lịch tự động trên máy chủ Server TW và Server Vùng. - Chương trình quản lý trên Server TW. 3.3.2.1 Chương trình đặt lịch tự động Thực chất, chương trình này sử dụng một tiện ích của windows, nhằm đặt lịch chạy tự động một chương trình (chương trình upload) vào một thời điểm cố định nào đó. Chương trình được cài đặt tại các Server TW, Server vùng, Server chi nhánh. Tại Server TW, mỗi khi có một phần mềm nghiệp vụ cần cập nhật, chương trình quản lý trên Server TW sẽ tạo ra Patch file (file Delta). Vào một thời điểm cụ thể, chương 49 trình đặt lịch tự động trên Server TW chạy một chương trình upload nhằm upload các Patch file về Server vùng. Tại Server vùng, chương trình đặt lịch tự động được cài đặt sau thời điểm chương trình đặt lịch tự động tại Server TW chạy. Cũng giống như Server TW, Server vùng tiến hành upload các Patch file về Server chi nhánh. Như vậy, không cần sự can thiệp của điện toán chi nhánh, ngay khi có gói chương trình cần cập nhật tại TW, toàn bộ các Server chi nhánh sẽ nhận ngay được bản vá của chương trình. Khác với mô hình cũ đã được áp dụng tại ngân hàng công thương Việt Nam, trong mô hình mới này, phần dữ liệu được truyền đi trên mạng là tương đối nhỏ. Do vậy, việc upload các gói cập nhật thường không làm ảnh hưởng lưu lượng các gói tin truyền đi trên mạng, thậm chí trong cả thời gian giao dịch cao điểm của toàn hệ thống. 3.3.2.2 Chương trình quản lý trên Server TW Chương trình này được đặt tại Server TW, với các chức năng chính như sau: Hình 3.2: Các mô đun chính chương trình quản lý tại Server TW Dưới đây sẽ mô tả chi tiết từng chức năng của chương trình. 3.3.2.2.1 Quản lý gói cập nhật Chức năng Quản lý gói cập nhật bao gồm các chức năng sau: Chương trình quản lý tại Server TW Quản lý gói cập nhật Quản lý danh sách chi nhánh Quản lý danh sách ứng dụng Upload thủ công gói cập nhật Xem nhật ký upload 50 Hình 3.3: Các chức năng của mô đun Quản lý gói cập nhật Chức năng Xóa gói cập nhật có thể được thực hiện khi gói cập nhật không còn cần thiết trên hệ thống nữa, người sử dụng có thể tiến hành xóa để dọn dẹp hệ thống. Chức năng Tạo mới/ chỉnh sửa gói cập nhật có luồng xử lý tương tự nhau. Hình 3.4: Lưu đồ chức năng Tạo mới/chỉnh sửa gói cập nhật Quản lý gói cập nhật Tạo mới gói cập nhật Chỉnh sửa gói cập nhật Xóa gói cập nhật Start Fold Fnew Version (Fold) < Version (Fnew) ? Fold  UTFold Fnew  UTFnew Y N Create Patch File End 51 Đầu vào của mô đun Tạo mới/ Chỉnh sửa gói cập nhật bao gồm file chương trình cũ và file chương trình mới. Hai file chương trình này phải cùng tồn tại trên máy chạy mô đun. Đầu tiên, chương trình thực hiện so sánh version của hai file. Việc so sánh này có thể thực hiện dựa trên ngày/giờ tạo của mỗi chương trình. Nếu file Fold có version mới hơn file Fnew thì chương trình đưa ra thông báo cho người sử dụng kiểm tra lại. Để thực hiện tạo Patch file, chương trình cần thực hiện chuyển đổi các file sang dạng mã UTF (xem bảng mã UTF8 trong phần phụ lục tham khảo). Về kỹ thuật tạo patch file đã được trình bày trong phần trên, dưới đây sẽ mô tả hàm cơ bản được dùng trong quá trình tạo patch file. CreatePatchFile có các tham số sau BOOL CreatePatchFile( LPCTSTR lpszPatchFile, // name of patch file DWORD dwPatchLevel, // patch level DWORD dwPatchOptions, // patch options DWORD dwPatchExpires, // patch expiration DWORD dwReserved, // reserved LPCTSTR lpszPassword, // password LPCTSTR lpszOldFile, // name of old file LPCTSTR lpszNewFile, // name of new file LPPATCHSTATUSPROC lpfnCallback, // pointer to callback function LPARAM lParam // callback function parameter ); Giải thích các tham số LpszPatchFile Một con trỏ chỉ ra tên của patch file được tạo ra. Nếu đã tồn tại một file với tên đó rồi, file sẽ được ghi đè. DwPatchLevel Có giá trị từ 1 đến 9 xác định tốc độ và dung lượng bộ nhớ trong việc tạo patch file. Nếu Patch level càng cao, patch file sẽ càng nhỏ, bộ nhớ yêu cầu càng nhỏ. Giá trị 0 là mức patch file mặc định phù hợp cho hầu hết các file. Xem bảng sau: Giá trị Mô tả 52 PATCH_LEVEL_DEFAULT Một mức nén mặc định nên được lựa chọn để phù hợp với hầu hết các file. Giá trị này nên được sử dụng. PATCH_LEVEL_MINIMUM Tốc độ cực đại trong việc tạo patch file, với tuỳ chọn này, patch file được tạo ra nhanh hơn, sử dụng ít bộ nhớ hơn, patch file được tạo ra có kích thước lớn hơn. PATCH_LEVEL_MAXIMUM Tỷ lệ nén file lớn nhất, quá trình tạo file nén lâu hơn, tốn nhiều bộ nhớ hơn và tạo ra patch file nhỏ hơn. dwPatchOptions Một tập các tuỳ chọn được sử dụng trong khi thực hiện quá trình tạo patch file. Một trong các giá trị sau sẽ được sử dụng: Giá trị Mô tả PATCH_OPTION_FIND_FILE Nếu file tham chiếu không được tìm thấy trong hệ thống, chương trình sẽ cố gắng tìm theo các quy tắc về đường dẫn thư mục chuẩn của Windows. Theo đó, thư mục hiện thời, thư mục hệ thống, và các thư mục trong biến môi trường PATH sẽ được tìm. PATCH_OPTION_BACKUP_FILE Tạo một file backup trên hệ thống trước khi áp dụng patch file. Nếu cờ này không được dựng, file sẽ được cập nhật ngay mà không có bản backup. PATCH_OPTION_COMPARE_FILETIME So sánh thời gian file đích được chỉnh sửa với thời gian file tham chiếu được chỉnh sửa. Nếu file đích có thời gian chỉnh sửa muộn hơn so với file tham chiếu tại thời điểm patch đã được tạo, chương trình sẽ đưa ra lỗi AP_ERROR_NEWER_FILETIME. Điều này đảm bảo rằng file cập nhật luôn có thời gian chỉnh sửa sau 53 file tham chiếu. PATCH_OPTION_COMPARE_VERSION So sánh phiên bản của file tham chiếu với file đích. Nếu file tham chiếu có phiên bản mới hơn so với file đích tại thời điểm patch file được tạo thì chương trình sẽ đưa ra lỗi: AP_ERROR_NEWER_VERSION. Điều này đảm bảo rằng file cập nhật luôn có phiên bản mới hơn file tham chiếu PATCH_OPTION_IGNORE_FILETIME Bỏ qua sự khác nhau về thời gian chỉnh sửa file của các file đích và file tham chiếu tại thời điểm patch file được tạo ra. PATCH_OPTION_IGNORE_VERSION Bỏ qua sự khác nhau về phiên bản file của các file đích và file tham chiếu tại thời điểm patch file được tạo ra. PATCH_OPTION_IGNORE_ATTRIBUTES Bỏ qua các thuộc tính file cập nhật khi patch được áp dụng trên hệ thống và thay vào đó, sử dụng các thuộc tính mặc định. PATCH_OPTION_IGNORE_READONLY Bỏ qua thuộc tính read-only khi áp dụng patch file. Nếu file cần cập nhật có thuộc tính này, nó sẽ được loại bỏ. PATCH_OPTION_IGNORE_SIGNATURE Bỏ qua bất kỳ chữ ký điện tử nào được hiển thị. Nếu file cập nhật đã được ký bởi mã xác thực, chữ ký sẽ được xác thực tại thời điểm patch được áp dụng. dwPatchExpires Xác định số ngày patch có thể được áp dụng. Khi ngày hết hạn được đạt tới, patch file sẽ không còn được áp dụng nữa. Giá trị 0 thể hiện patch file không bao giờ hết hạn. 54 lpszPassword Một con trỏ tới xâu password được dùng để bảo mật. Patch file sau khi được tạo ra, sẽ chưa được áp dụng cho đến khi password được cung cấp trong hàm ApplyPatchFile. Nếu không dùng password, tham số này sẽ được đặt là NULL để trỏ tới một xâu rỗng. lpszOldFile Một con trỏ tới một xâu không rỗng xác định tên của file tham chiếu. lpszNewFile Một con trỏ tới một xâu không rỗng xác định tên của file cập nhật. File này sẽ được so sánh lại với file tham chiếu, bất kỳ thay đổi nào cũng sẽ được ghi trong patch file. Các giá trị trả về Nếu hàm CreatePatchFile thành công, nó sẽ trả về một giá trị khác 0. Ngược lại, nếu hàm lỗi, nó sẽ trả về giá trị 0. Để biết các lỗi có thể có, tham khảo thêm hàm GetLastError. Chú ý Để áp dụng patch file trên hệ thống, sử dụng hàm ApplyPatchFile. Khi patch level càng cao, chương trình sẽ thực hiện phân tích các file tham chiếu và file cập nhật càng lâu. Nó cũng sử dụng tới nhiều bộ nhớ hơn. Chú ý rằng, trong một vài trường hợp, tuỳ thuộc vào cấu trúc bên trong của file, patch level lớn nhất có thể sẽ làm tăng kích thước của patch file kết quả. Vì vậy, ta nên sử dụng patch level mặc định. Nếu cả PATCH_OPTION_COMPARE_FILETIME và PATCH_OPTION_IGNORE_FILETIME đều không được thiết lập, thì PATCH_OPTION_COMPARE_FILETIME là mặc định. Nếu cả PATCH_OPTION_COMPARE_FILETIME và PATCH_OPTION_IGNORE_FILETIME đều được thiết lập, thì PATCH_OPTION_IGNORE_FILETIME giành quyền ưu tiên. Nếu cả PATCH_OPTION_COMPARE_VERSION và PATCH_OPTION_IGNORE_VERSION đều không được thiết lập, thì PATCH_OPTION_COMPARE_VERSION là mặc định. Nếu cả 55 PATCH_OPTION_COMPARE_VERSION và PATCH_OPTION_IGNORE_VERSION được thiết lập, thì PATCH_OPTION_IGNORE_VERSION giành quyền ưu tiên. 3.3.2.3.2 Quản lý danh sách chi nhánh Để thực hiện cập nhật tự động đến từng Server chi nhánh, IP của các Server này cần được cung cấp. Chương trình upload tự động sẽ tìm đến các IP này, và tiến hành upload các patch file lên các Server đó. Các mô đun chính của chức năng Quản lý danh sách chi nhánh bao gồm: Hình 3.5: Các chức năng của mô đun Quản lý danh sách chi nhánh Khi có một chi nhánh mới mở trong hệ thống, chi nhánh này cần được cập nhật vào danh sách. Cũng vậy, khi một chi nhánh đóng cửa, chi nhánh này cần được xoá khỏi danh sách. Khi IP máy chủ chi nhánh có thay đổi, hoặc khi tên chi nhánh có thay đổi, các thông tin thay đổi cũng cần được cập nhật trong database tại trung ương. Có như vậy, chương trình upload mới tìm đúng địa chỉ cần upload các patch file. Chức năng Quản lý danh sách chi nhánh thực chất được thực hiện bởi các thao tác Insert, Update, Delete vào bảng brn_list trong database tại server trung ương. Theo đó, chương trình upload sẽ tiến hành thao tác upload patch file lên các IP trong bảng brn_list. Sửa tên chi nhánh Sửa IP chi nhánh Quản lý danh sách chi nhánh Thêm mới chi nhánh Sửa đổi chi nhánh Xoá chi nhánh 56 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 3.3.2.3.3 Quản lý danh sách ứng dụng Chức năng quản lý danh sách ứng dụng nhằm cung cấp đầu vào cho chức năng Quản lý gói cập nhật. Chức năng Quản lý gói cập nhật chỉ thực hiện tạo patch file được cho các ứng dụng nằm trong danh sách ứng dụng do chứ