Chương 1 đã cho ta thấy được tổng quan về các phương pháp nén. Mỗi phương pháp nén đề có ưu nhược điểm riêng. Chương 2 sẽ trình bày chi tiết về phương pháp nén theo Delta. Là một trong những phương pháp nén tốt nhất hiện nay được sử dụng.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn download by : skknchat@gmail.com 17 CHƯƠNG 2 CÔNG NGHỆ NÉN DELTA Công nghệ nén Delta được tập đoàn Microsoft phát triển, nó là một công nghệ nén khác biệt. Chủ yếu sử dụng cho các chương trình ứng dụng của Microsoft như Windows Update hay cho lập trình giao diện API. Quá trình nén dựa trên sự sai khác giữa 2 file, do đó tạo ra một file có kích thước nhỏ hơn đáng kể trước khi truyền qua mạng so với các phương pháp nén khác. Giới thiệu về công nghệ nén Delta 2.
Khái niệm về nén 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[9]. 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'. Bộ nén dữ liệu thông thường Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn download by : skknchat@gmail. Bộ nén Delta Bộ nén Delta 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[8], 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, chấp nhận Delta cùng với file cơ sở, và xây dựng lại file đích (target file). 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 F-F' cùng với phần dữ liệu cơ sở F, để xây dựng dữ liệu đích F' như hình vẽ. Bộ nén Delta 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ể Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn download by : skknchat@gmail.
khi cần update hoặc 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ùng một file[6]. Quá trình tạo này cần 2 file là input. Kích thước của file Delta tùy thuộc vào sự giống nhau giữa hai file này.
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 như file EXE hoặc DLL. Nói riêng, các dạng file có thể thực thi được kế để chạy trên dòng Intel 32 bit I386 sẽ có cách đối xử riêng. Khi file basic 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%. Nền tảng chung Trong vấn đề bộ nén Delta chúng ta có hai 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 [8].
Trước đây, ta có nhiều nghiên cứu trong phạm vi sự biến đổi 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 [5]. Tuy nhiên, vấn đề đó 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 [2].
Một sự di chuyển khối lại được định nghĩa qua một bộ ba (p,q,l) trong đó f old [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ư Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn download by : skknchat@gmail.com 20 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 f new[i] cũng xuất hiện trong fold sẽ không được chứa trong 1 khối di chuyển [3]. 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 [4]. Đ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ố [3]. 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 tác liên quan đến việc thay thế một tiền tố của string đang được mã hóa bởi một sự tham chiếu tới một substring y hệt đã được mã hóa trước đó. Như vậy, nén Delta có thể được xem một cahcs đơn giản như sự thi hành của LZ77 với fold đại diện cho text đã mã hóa 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. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn download by : skknchat@gmail.com 21 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ế. 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 Lempel - Ziv[1]. Một trong các tool đó và vdelta và sự biến thể của nó vcdiff, xdelta được dùng trong XDFS, và công cụ zdelta Zdeta (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 bổ sung thêm vào đó. Ai đã quen thuộc với zlib, gzib 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ã hóa 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ã hóa một phần file hiện thời. Để nhận biết sự phù hợp trong khi mã hóa, chúng ta duy trì 2 bảng, một 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á f new. 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ó[7]. 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ã hóa như sau ( giải mã thì có thể suy ra từ việc mã hóa). Tiền xử lý file tham chiếu Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn download by : skknchat@gmail. Tính , giá trị băm của 3 ký tự đầu tiên bắt đầu vị trí thứ i trong 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 , 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). + Insert một con trỏ tới vị trí j trong bảng băm hj của Tnew.
+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 f new, 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ó.
+ 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ự f new- [j] và tăng j lên 1. 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.