Chắc hẳn nhiều bạn đã sử dụng phần mềm nén dữ liệu như WinRAR, WinZip, 7-Zip rồi đúng không. Nhưng các bạn thực sự hiểu bản chất nén dữ liệu là gì chưa, nguyên lý hoạt động như thế nào. Chúng ta sẽ cùng tìm hiểu trong bài viết này nhé.
Nén dữ liệu là gì?
Trong công nghệ thông tin, Nén dữ liệu (tiếng Anh: Data compression) là việc chuyển định dạng thông tin sử dụng ít bit hơn cách thể hiện ở dữ liệu gốc. Tùy theo dữ liệu có bị thay đổi trước và sau khi giải nén không, người ta chia nén thành hai loại: Nguyên vẹn (lossless) và bị mất dữ liệu (lossy). Nén mất dữ liệu giảm số lượng bit bằng cách xác định các thông tin không cần thiết và loại bỏ chúng.
Nén dữ liệu là cần thiết vì giảm được nguồn tài nguyên cũng như dung lượng lưu trữ hay băng thông đường truyền. Tuy nhiên, vì dữ liệu nén cần được giải nén nên sẽ đòi hỏi nhiều phần cứng và xử lý.
Tác dụng của nén dữ liệu
– Để giảm dung lượng file gốc, tiết kiệm bộ nhớ cho thiết bị lưu trữ
– Thuận tiện cho việc chia sẻ file, gửi file qua internet
– Giảm thời gian download, upload file trên mạng internet
– Bảo mật file dữ liệu bằng cách nén có mật khẩu
Các thuật toán nén không mất dữ liệu thường dựa trên giả thuyết dư thừa trong dữ liệu và thể hiện dữ liệu chính xác hơn mà không mất các thông tin. Nén mà không làm mất dữ liệu là khả thi vì tất cả các dữ liệu thực tế đều có dư thừa. Ví dụ một hình ảnh có thể có các vùng màu sắc không thay đổi trong nhiều pixel. Thay vì ghi nhận từng pixel như đỏ, đỏ, đỏ… dữ liệu có thể được ghi là 279 điểm ảnh đỏ liên tiếp. Đây là một ví dụ về run-length encoding; ngoài ra còn có rất nhiều giải thuật khác.
Dựa theo mức áp dụng thuật toán nén người ta chia nén thành các dạng sau:
– Nén tệp tin: Đây là dạng thức nén truyền thống và thuật toán nén được áp dụng cho từng tệp tin riêng lẻ. Tuy vậy nếu 2 tệp tin giống nhau thì vẫn được nén 2 lần và được ghi 2 lần. Chỉ các byte trùng lắp trong 1 file được loại trừ để giảm kích thước. Tùy dữ liệu nhưng thông thường khả năng giảm sau khi nén chỉ từ 2-3 lần.
– Loại trừ trùng lắp file: Đây là dạng thức nén mà thuật toán nén được áp dụng cho nhiều tập tin. Các file giống hệt nhau sẽ chỉ được lưu một lần. Ví dụ một thư điện tử có tệp tin đính kèm được gửi cho 1000 người. Chỉ có một bản đính kèm được lưu và vì vậy có thể giảm khá nhiều. Thông thường có thể giảm từ 5-10 lần so với dữ liệu gốc.
– Loại trừ trùng lắp ở mức sub-file: Đây là một dạng thức kết hợp cả nén tệp tin và loại trừ trùng lắp
Nén có mất dữ liệu
Chuẩn nén tín hiệu số gồm có các chuẩn sau:
Chuẩn MJPEG:
Đây là một trong những chuẩn cổ nhất mà hiện nay vẫn sử dụng. MJPEG (Morgan JPEG). Chuẩn này hiện chỉ sử dụng trong các thiết bị DVR rẻ tiền, chất lượng thấp. Không những chất lượng hình ảnh kém, tốn tài nguyên xử lý, cần nhiều dung lượng ổ chứa, và còn hay làm lỗi đường truyền.
Chuẩn MPEG2:
Chuẩn MPEG là một chuẩn thông dụng. Đã được sử dụng rộng rãi trong hơn một thập kỉ qua. Tuy nhiên, kích thước file lớn so với những chuẩn mới xuất hiện gần đây, và có thể gây khó khăn cho việc truyền dữ liệu.
Ví dụ như trong MPEG-2, nơi mà nội dung được tạo ra từ nhiều nguồn như video ảnh động, đồ họa, văn bản… và được tổ hợp thành chuỗi các khung hình phẳng, mỗi khung hình (bao gồm các đối tượng như người, đồ vật, âm thanh, nền khung hình…) được chia thành các phần tử ảnh pixels và xử lý đồng thời, giống như cảm nhận của con người thông qua các giác quan trong thực tế. Các pixels này được mã hoá như thể tất cả chúng đều là các phần tử ảnh video ảnh động. Tại phía thu của người sử dụng, quá trình giải mã diễn ra ngược với quá trình mã hoá không khó khăn. Vì vậy có thể coi MPEG-2 là một công cụ hiển thị tĩnh, và nếu một nhà truyền thông truyền phát lại chương trình của một nhà truyền thông khác về một sự kiện, thì logo của nhà sản xuất chương trình này không thể loại bỏ được. Với MPEG-2, bạn có thể bổ sung thêm các phần tử đồ hoạ và văn bản vào chương trình hiển thị cuối cùng (theo phương thức chồng lớp), nhưng không thể xoá bớt các đồ hoạ và văn bản có trong chương trình gốc.
Chuẩn MPEG-4:
Mpeg-4 là chuẩn cho các ứng dụng MultiMedia. Mpeg-4 trở thành một tiêu chuẩn cho nén ảnh kỹ thuật truyền hình số, các ứng dụng về đồ hoạ và Video tương tác hai chiều (Games, Videoconferencing) và các ứng dụng Multimedia tương tác hai chiều (World Wide Web hoặc các ứng dụng nhằm phân phát dữ liệu Video như truyền hình cáp, Internet Video…). Mpeg-4 đã trở thành một tiêu chuẩn công nghệ trong quá trình sản xuất, phân phối và truy cập vào các hệ thống Video. Nó đã góp phần giải quyết vấn đề về dung lượng cho các thiết bị lưu trữ, giải quyết vấn đề về băng thông của đường truyền tín hiệu Video hoặc kết hợp cả hai vấn đề trên.
Với MPEG-4, các đối tượng khác nhau trong một khung hình có thể được mô tả, mã hoá và truyền đi một cách riêng biệt đến bộ giải mã trong các dòng cơ bản ES (Elementary Stream) khác nhau. Cũng nhờ xác định, tách và xử lý riêng các đối tượng (như nhạc nền, âm thanh xa gần, đồ vật, đối tượng ảnh video như con người hay động vật, nền khung hình …), nên người sử dụng có thể loại bỏ riêng từng đối tượng khỏi khuôn hình. Sự tổ hợp lại thành khung hình chỉ được thực hiện sau khi giải mã các đối tượng này.
H.264
H.264 (MPEG-4 AVC hay MPEG-4 part 10), hiện đang là phương thức tiên tiến nhất trong lĩnh vực nén video. H.264 cho chất lượng hình ảnh tốt nhất khi có cùng dung lượng so với các chuẩn nén khác.
H.264 cũng được ứng dụng như thuật nén chính trong video độ phân giải cao (HD)
1. Mã hóa độ dài hàng 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ụ, mình có chuỗi: “AAAAAABBBAAAAABBBBB”
Chuỗi này gồm 6 chữ A, 3 chữ B rồi lại đến 5 chữ A, tiếp theo là 5 chữ B
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.
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 là: 6A3B5A5B
Nếu chỉ có 1 – 2 ký tự thì không cần thiết phải mã hóa, vì mã hóa cũng phải tốn 2 ký tự.
Ðối với các tập tin nhị phân (0 – 1) 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 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.
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.
“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:
00001000101001000001000110000100100000010001010010 00001
Ðể 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á.
– 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: đạ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).
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ự.
– 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.
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.
Ưu điểm: tiết kiệm đáng kể dung lượng file sau khi nén, dùng được cho các đoạn bit dài.
Nhược điểm: không thể dùng được cho mọi loại tập tin.
2. Huffman
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 bit. 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:
-Nhược điểm: 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.
3. LZW (Lempel-Zip & Welch)
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ã.
Ưu điểm: 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.
Ưu điểm: vẫn giữ nguyên giá trị gốc không thay đổi, chỉ hoán vị.
Nhược điểm: do chỉ hoán vị, giữ nguyên giá trị gốc nên kích thước giảm không nhiều.
5. Chuẩn H.264/MPEG-4
Ưu điểm: nén được các file đa dạng, chất lượng video tốt hơn mà vẫn tiết kiệm, có thể xuất ra các cấu hình khác nhau.
100 lần tự tìm hiểu cũng không bằng 1 lần được tư vấn