File nén và phần mềm nén/giải nén hoạt động như thế nào?
Chúng ta hẳn đều đã quá quen thuộc với những file nén mang định dạng như .zip, .rar, .7z … Thông thường khi tải về thì chúng ta sẽ dùng một phần mềm như WinZIP, WinRAR để giải nén lấy file gốc. Thế nhưng có bao giờ bạn thắc mắc là file nén được nén/giải nén như thế nào chưa? Qua ví dụ và lý giải của HowStuffWorks, chúng ta sẽ phần nào hiểu được cách thức hoạt động của file nén hay phần mềm nén.
Hầu hết các dạng file trên máy tính rất phức tạp với các mảng thông tin được lặp lại nhiều lần và các phần mềm nén file sẽ đơn giản hóa sự phức tạp này. Thay vì liệt kê từng mảng thông tin lặp đi lặp lại trong một file, phần mềm nén file sẽ liệt kê các thông tin này một lần và chỉ trả lại tình trạng phức tạp của file gốc một khi giải nén file. Chúng ta có một ví dụ như sau và dạng thông tin được sử dụng là “từ ngữ.”
Năm 1961, J. F. Kennedy trong lễ nhậm chức đã phát biểu rằng:
“Ask not what your country can do for you - ask what you can do for your country.”
Đây là một câu nói rất nổi tiếng của ông nhưng chúng ta sẽ không bàn về mặt ý nghĩa mà là số lượng từ, ký tự trong câu trên. Chúng ta có 17 từ, cấu thành từ 61 ký tự, 16 dấu cách, 1 dấu gạch ngang và 1 dấu chấm. Nếu mỗi ký tự, khoảng trống và dấu câu được xem là một đơn vị bộ nhớ thì chúng ta sẽ có một file có tổng dung lượng gồm 79 đơn vị. Giờ hãy thử liệt kê các từ lặp lại:
“ask” xuất hiện 2 lần;
“what” xuất hiện 2 lần;
“your” xuất hiện 2 lần;
“country” xuất hiện 2 lần;
“can” xuất hiện 2 lần;
“do” xuất hiện 2 lần;
“for” xuất hiện 2 lần;
“you” xuất hiện 2 lần.
Bỏ qua sự khác biệt giữa ký tự viết hoa và viết thường thì hơn 1 nửa câu nói trên được lặp lại. 9 từ gồm “ask, not, what, your, country, can, do, for, you” mang lại hầu như mọi thứ chúng ta cần để hiểu nghĩa câu nói. Để xây dựng nửa câu thứ 2, chúng ta chỉ việc chọn các từ trong nửa câu đầu, sắp xếp lại, thêm dấu cách và dấu chấm câu.
Hệ thống nén file giải quyết tình trạng lặp thông tin này như thế nào? Hầu hết các chương trình nén file sử dụng một phiên bản thuật toán có tên gọi thuật toán tương thích dựa trên từ điển LZ để nén file. LZ viết tắt của Lempel và Ziv - tên 2 nhà phát minh ra thuật toán này và “từ điển” tức là một phương pháp để sắp xếp các mảnh dữ liệu.
Trở lại với ví dụ trên, chúng ta sẽ chọn ra các từ lặp lại và đánh số, sau đó ghi lại các số tương ứng với các từ của câu theo thứ tự.
- ask
- what
- your
- country
- can
- do
- for
- you
Như vậy câu nói của Kenndy nếu được ghi bằng số sẽ là:
“1 not 2 3 4 5 6 7 8 - 1 2 8 5 6 7 3 4”
Nếu bạn biết được hệ thống đánh số thì bạn có thể dễ dàng viết ra được câu nói nguyên gốc chỉ với việc dùng từ điển và vị trí các số. Đây đúng như những gì chương trình nén file trên máy tính thực hiện khi giải nén một file ZIP. Bạn có thể bắt gặp những file nén có thể tự mở. Để tạo ra dạng file này thì các lập trình viên đã tích hợp một chương trình giải nén đơn giản vào file nén. Nó sẽ tự động tái tạo file gốc một khi được tải về và click mở.
Tuy nhiên, có bao nhiêu khoảng trống trên bộ nhớ mà chúng ta có thể tiết kiệm được với hệ thống này? “1 not 2 3 4 5 6 7 8 - 1 2 8 5 6 7 3 4” rõ ràng ngắn hơn nhiều so với cả câu “Ask not what your country can do for you - ask what you can do for your country.” nhưng hãy nhớ rằng chúng ta cần lưu từ điển cùng với file nén để có thể phiên dịch những con số thành từ gốc.
Để giải thích cặn kẽ thì rất phức tạp và mang tính chuyên môn cao nhưng chúng ta có thể hiểu đơn giản với ý tưởng ban đầu là mỗi ký tự và mỗi dấu cách trong câu được xem là một đơn vị bộ nhớ. Với câu nguyên gốc, file sẽ chiếm 79 đơn vị bộ nhớ nhưng với câu đã được nén (câu đã được phiên sang số) thì cả số và dấu cách, dấu câu chỉ chiếm 37 đơn vị bộ nhớ và từ điển (gồm chữ và số) cũng chiếm 37 đơn vị bộ nhớ. Tổng cộng với file chứa câu đã được phiên sang dạng chữ số và tích hợp cả từ điển sẽ chiếm 74 đơn vị bộ nhớ, ít hơn câu nguyên gốc không được nén 5 đơn vị, không nhiều lắm!
Tuy nhiên, đây chỉ là một câu đơn lẻ. Thử tưởng tượng nếu một phần mềm nén file nén toàn bộ các câu nói của Kennedy trong bài diễn văn nhậm chức thì nó sẽ tìm ra được rất nhiều từ lặp đi lặp lại. Do đó, phần mềm sẽ tổ chức một bộ từ điển mới hiệu quả hơn để giải nén file.
Copy toàn bộ nội dung bài viết này lưu vào 1 file .txt. File gốc 10 KB, nén lại còn 4 KB.
Đối với chúng ta thì việc đánh số từng từ là phương pháp đơn giản nhất để soạn từ điển nhưng không phải là phương pháp tối ưu đối với phần mềm nén file. Một phần mềm nén file sẽ có cách nhìn câu nói trên rất khác so với những gì chúng ta nghĩ bởi nó không có khái niệm về những từ riêng biệt. Chúng ta có khái niệm này bởi chúng ta hiểu đâu là một từ, nghĩa của từ đó là gì để đánh số nhưng với phần mềm, nó chỉ dựa vào mẫu vị trí của ký tự hay cụm ký tự. Và để giảm dung lượng file tối đa có thể, phần mềm sẽ chọn ra các cụm từ lặp tốt nhất để đưa vào từ điển.
Nếu sử dụng phương pháp của phần mềm thì chúng ta sẽ có một bộ từ điển hoàn toàn khác biệt. Giờ là phần hại não nhất:
Khi phần mềm quét qua câu nói của Kennedy, nó sẽ phát hiện ra những cụm ký tự lặp như sau. Chẳng hạn như trong đoạn “Ask not what your”, phần mềm phát hiện ra ký tự “t” theo sau là 1 dấu cách trong "not " và "what " lặp lại. Nếu phần mềm soạn từ điển thì nó sẽ đánh số 1 một ký tự “t” và 1 khoảng trống theo sau hay "t ".
Tiếp theo, phần mềm có thể phát hiện ra cụm ký tự “ou” xuất hiện trong “your” và “country”. Nếu đây là một đoạn văn bản dài hơn thì việc chọn cụm ký tự “ou” đưa vào từ điển sẽ tiết kiệm được rất nhiều không gian lưu trữ bởi lẽ “ou” là cụm ký tự rất phổ biến trong tiếng Anh. Tuy nhiên, với câu nói ngắn trên thì phần mềm sẽ tìm ra một cụm ký tự tốt hơn. Không chỉ lặp lại cụm ký tự “ou” mà cả từ “your” và từ “country” cũng lặp lại mà thậm chí là còn lặp lại cùng nhau “your country”. Như vậy, phần mềm sẽ bỏ cụm “ou” trong từ điển để thay bằng “your country”.
Đoạn “can do for” cũng được lặp lại, lần đầu theo sau cụm này là từ “your” và lần tiếp theo là từ “you”, do đó phần mềm sẽ soạn tiếp vào từ điển cụm ký tự “can do for you”. Lúc này, phần mềm sẽ tiếp tục chọn ra cụm từ tối ưu nhất để đưa vào từ điển. Chẳng hạn như: Cụm “can do for you” - 15 ký tự tính cả dấu cách; cụm “your country” - 13 ký tự tính cả dấu cách. Như vậy, phần mềm sẽ chọn “can do for you” để gán cho 1 số, sau đó chọn “r country” gán cho số tiếp theo để đưa vào từ điển.
Phần mềm sẽ xử lý như vậy, chọn ra tất cả các bit thông tin lặp lại vào sau đó tính toán cụm ký tự nào tối ưu nhất để ghi vào từ điển. Đây là khả năng ghi đi ghi lại từ điển của thuật toán tương thích từ điển LZ.
Trở lại với câu nói của Kenndy, nếu sử dụng cách gán số dựa trên cụm ký tự thì chúng ta sẽ có từ điển như sau. Để dễ thấy hơn thì chúng ta sẽ dùng dấu gạch dưới _ tượng trưng cho dấu cách (space).
“Ask not what your country can do for you - ask what you can do for your country.”
- ask_
- what_
- you
- r_country
- _can_do_for_you
Nếu phiên ra số thì câu nói nguyên gốc tương ứng với:
“1not_2345_-_12354”
Bằng cách này, cả câu chỉ chiếm 18 đơn vị bộ nhớ và từ điển cũng chỉ chiếm 41 đơn vị bộ nhớ. Tổng dung lượng do đó đã giảm xuống từ 79 đơn vị còn 59 đơn vị. Đây chỉ là một cách để nén câu nói của Kennedy, nếu bạn có cách nào tối ưu hơn hãy chia sẻ nhé :).
Vậy hệ thống này tốt như thế nào? Tỉ lệ giảm dung lượng file dựa trên rất nhiều yếu tố bao gồm loại file, kích thước file và chế độ nén.
1 file PDF gốc hơn 20 MB sau khi được nén dạng .zip còn 18 MB và .7z còn 17,5 MB.
Trong hầu hết các ngôn ngữ trên thế giới, những ký tự và từ thường xuất hiện cùng nhau theo một mô hình tương tự nhau. Do tỉ lệ lặp lại của từ cao nên các file văn bản thường đạt hiệu quả nén rất tốt. Một file văn bản sau khi được nén có thể giảm đến 50% dung lượng gốc. Ngoài ra, phần lớn các ngôn ngữ lập trình cũng có tỉ lệ lặp cao bởi chúng thường sử dụng một bộ gồm các lệnh được dùng đi dùng lại trong mã code. Tuy nhiên, những tập tin chứa nhiều thông tin đặc trưng chẳng hạn như hình ảnh hay nhạc số định dạng MP3 sẽ không đạt hiệu quả nén tốt nhất từ hệ thống trên bởi chúng không có nhiều mẫu thông tin lặp lại.
Hiệu suất nén cũng phụ thuộc vào loại thuật toán được phần mềm nén file sử dụng. Một số phần mềm thường được tích hợp các thuật toán có thể quét và lọc các mẫu thông tin trùng lặp trong một số dạng file nhất định để nén hiệu quả hơn.
Phương pháp nén file mà chúng ta thảo luận nãy giờ được gọi là lossless compression hay nén không mất chất lượng bởi nó cho phép tái tạo file gốc hoàn chỉnh và chính xác. Tất cả các phương pháp nén lossless đều dựa trên ý tưởng chia file thành nhiều phần nhỏ hơn để truyền tải hoặc lưu trữ, sau đó gộp các phần nhỏ lại với nhau ở đầu kia để file có thể được sử dụng lại.
Chúng ta còn có một phương pháp nén khác là lossy compression hay nén mất chất lượng. Phương pháp này sẽ loại bỏ các bit thông tin “không cần thiết” để khiến file nhỏ hơn và thường được dùng để nén những file hình ảnh như bitmap.
Một phần mềm dùng phương pháp nén lossless sẽ không đạt hiệu quả cao khi nén dạng file hình ảnh. Nếu một tấm ảnh có nhiều phần giống nhau, chẳng hạn như một bầu trời màu xanh thì hầu hết các điểm ảnh có rất ít khác biệt. Để khiến bức ảnh nhỏ hơn mà không làm giảm độ phân giải, bạn sẽ phải thay đổi giá trị màu cho những điểm ảnh giống nhau này. Nếu bức ảnh có phần lớn mảng màu là màu xanh của bầu trời, phần mềm sẽ chọn ra một màu xanh có thể được sử dụng cho mọi điểm ảnh. Sau đó, phần mềm tái tạo file để giá trị màu đã chọn được áp dụng trên toàn bộ các điểm ảnh giống nhau. Nếu phương pháp này hoạt động chính xác, bạn sẽ không nhận ra sự thay đổi trên bức ảnh nhưng kích thước file ảnh sẽ giảm đáng kể.
Dĩ nhiên, với phương pháp nén lossy thì bạn không thể lấy lại file gốc sau khi được nén bởi phần mềm đã tác động đến file gốc. Vì lý do này, bạn không thể dùng phương pháp lossy để nén các file cần được tái tạo chính xác như ứng dụng phần mềm, cơ sở dữ liệu v.v…
