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


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

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

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


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

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

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

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.

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à <100h> đượ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

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

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 f
new
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 đó f
old
[p,…,p+l-1]= f
new
[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 f
old
và f
new
. Cho trước f
old
và
f
new
, 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 f
new
[i] cũng xuất hiện trong f

, thuật toán di chuyển khối dựa trên thuật toán copy, trong đó f
new
như
một chuỗi tối thiểu của thao tác copy từ f
old
.

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
f
old
đạ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 f
new
đã 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

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 (f
old
) -3:
(a) Tính h
i
= h ( f
old
[i, i+2] ), giá trị băm của 3 ký tự đầu tiên bắt đầu vị trí
thứ i trong f
old

(b) Insert 1 con trỏ vào vị trí i trong bảng băm h
i
của

T
old
2. Mã hoá file hiện thời

new
(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 f
new
).
(c) Insert một con trỏ tới vị trí j trong bảng băm h
j
của T
new.

(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 f
new,
và
tương ứng với một trong các con trỏ p
i
nếu sự phù hợp trong f
old.
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 f
new
hoặc tới một trong các con trỏ trong f
old.
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ỏ p
i
nếu có.

27288

-

27326

-

Gzip 7479

24/30

8191

26/35

Xdelta 461

20

2131

29

Vcdiff 289

33

1821


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 .