Nén file như thế nào ?

Nếu tải nhiều chương trình và những File trên Internet , bạn sẽ gặp những file đã được nén trước đó
Bạn phải giải nén những file này để trước khi sử dụng . Những file nén có kích thước nhỏ hơn so với file sau khi giải nén .

 Khi nhìn lần đầu tiên dường như là đang ẩn chứa những điều bí hiểm . Làm thế nào để giảm số Bit và Byte và sau đó thêm vào những Bit hoặc Byte phụ sau này để kích thước fiel sau khi nén giảm đi .

 Hầu hết những kiểu file của máy tính là rườm rà , chúng một danh sách những lệnh , những thông tin và được dùng đi dùng lại . Chương trình nén file đơn giản là giải phóng sự rườm rà này . Thay thế vào đó là những thông tin được lặp đi lặp lại được lưu vào một danh sách và chúng được khôi phục trạng thái ban đầu từ danh sách đó sau khi giải nén .

 Ví dụ trích dẫn câu nói nổi tiếng của John F. Kennedy năm 1961

 "Ask not what your country can do for you -- ask what you can do for your country." - 

 ( Đừng hỏi đất nước có thể  làm gì cho bạn mà hãy hỏi bạn có thể  làm được gì cho đất nước của bạn .)

 Trong câu trích dẫn trên có 17 từ , 61 chữ cái ,16 khoảng trống , một dấu chấm và một dấu gạch ngang . Nếu mỗi một chữ cái , khoảng trống  hoặc những đánh dấu câu là một đơn vị nhớ thì chúng ta có tổng cộng 79 đơn vị . Chúng ta chú ý rằng

·        “ask “ xuất hiện hai lần

·        “what” xuất hiện hai lần

·        “your” xuất hiện hai lần

·        “country” xuất hiện hai lần

·        “can” xuất hiện hai lần

·        “do” xuất hiện hai lần

·        “for” xuất hiện hai lần

·        “you” xuất hiện hai lần

 Chúng ta loại trừ sự khác nhau giữa chữ thường và chữ hoa thì một nửa trong số chúng có thể được loại bỏ . 9 từ “ ask, not, what, your, country, can, do, for, you” cho chúng ta  biết hầu hết nội dung của câu . Để tạo thành một nửa thứ hai câu chúng ta phải chỉ những từ trong nửa đầu tiên và chèn chúng trong những khỏng trống và những dấu câu .

             Hầu hết mọi chương trình nén file dùng phương án “ Thuật toán dựa trên  từ điển thích nghi LZ “ để nén file .

            LZ được viết tắt từ “ Lempel and Ziv“ những người tạo nên thuật toán và “từ điển” là phương pháp tạo đoạn danh mục của dữ liệu .

 Hệ thống cho một dãy những từ điển thay đổi , đơn giản nó là một danh sách số . Khi chúng ta quay lại lời trích dẫn của Kenedy chúng ta có một từ điển như sau :

 

 

1.      ask

2.      what

3.      your

4.      country

5.      can

6.      do

7.      for

8.      you

Câu của chúng ta sẽ được ghi như sau :

 

"1 not 2 3 4 5 6 7 8 -- 1 2 8 5 6 7 3 4"

 

Nếu trong hệ thống mới bạn có thể dễ dàng tạo lại câu ban đầu từ từ điển của nó . Đó chính là nguyên nhân tại sao những file sau khi nén muốn sử dụng thì phải được giải nén trước đó . Bao nhiêu khoảng trống bạn đã tiết kiệm "1 not 2 3 4 5 6 7 8 -- 1 2 8 5 6 7 3 4" rõ ràng là ngắn hơn so với "Ask not what your country can do for you; ask what you can do for your country;" , nhưng nên nhớ rằng chúng ta cần lưu từ điển này cùng với file nén .

Với ví dụ kiểu quy định trên , mọi lí tự thì chứa một đơn vị nhớ thì câu đầu chưa nén dùng 79 đơn vị . Câu nén và cả khoảng trống là 37 đơn vị , kèm theo từ điển cũng dùng 37 đơn vị . Như thế sau khi nén sẽ dùng 74 đơn vị , như thế kích thước file sau khi nén không giảm nhiều .

Nhưng điều đó chỉ có một câu , bạn có thể xem một hình ảnh nén file có nhiều câu , trong đó chúng có nhiều phần được lặp đi lặp lại .

 Tìm kiếm những mẫu

  

\"\"       \"\"

 
           Trong ví dụ trên , chúng ta lấy ra tất cả những từ lặp lại và đưa chúng vào trong một từ điển để dùng , đó là cách tất nhiên để ghi vào trong từ điển Nhưng chương trình nén tìm nó hoàn toàn khác . Nó không có bất kì khái niệm những từ tách rời – nó chỉ tìm kiếm những mẫu . Để giảm thiểu kích thước file nhiều nhất có thể được , nó rất cẩn thận chọn những mẫu được lưu trong từ điển .

Nếu chương trình nén quét cụm từ của Kenedy , đầu tiên nó sẽ đi qua những cặp từ . Trong “ask not what your," có mẫu được lặp lại của chữ cái “t” với dấu trống trong từ “not” và “what” . Nếu chương trình nén viết từ này vào trong từ điển , nó có thể ghi “1” là “t” kèm theo dấu trống . Nhưng trong cụm từ ngắn , mẫu này xảy ra không thường xuyên đủ để ghi nó thành một từ trong từ điển do vậy chương trình sẽ ghi đè lên mẫu này.

Tiếp theo chương trình có thể lưu ý tới từ “ou” mà nó xảy ra trong từ “your" và “country” . Nếu từ này có trong tài liệu dài hơn , nó ghi mẫu này tới từ điển để tiết kiệm nhiều chỗ trống – “ou” cũng khá hay xảy ra đối với sự kết hợp từ trong tiếng Anh . Nhưng chúng ta đang xét tới chương trình nén trong câu trên , nó nhanh chóng phát hiện ra lựa chọn tốt nhất cho ghi vào từ điển : Không chỉ có :”ou” được lặp lại , nhưng những từ “your” và “country” cũng được lặp lại . Trong trường hợp đó chương trình sẽ ghi đè vào từ điển từ”ou” bằng "your country."

Cụm từ "can do for" cũng được lặp lại  , một lần đi theo với”your” và một lần khác theo với “you” cho chúng ta mẫu lặp lại "can do for you." . Điều này cho phép chúng ta ghi 15 kí tự  bao gồm cả khoảng trống bằng một giá trị số , trong khi "your country" chỉ dùng 13 kí tự bao gồm cả khoảng trống cũng bằng một giá trị số  . Do đó chương trình sẽ ghi đè lên mẫu "your country" bằng mẫu của “r country”  và sau đó viết tách với “ "can do for you." . Chương trình chấp nhận cách như vậy , lấy tất cả những Bit thông tin được lặp lại và sau đó tính toán những mẫu này và ghi chúng vào trong từ điển . Khả năng ghi lại và ghi đè lên những mẫu trong từ điển gọi là “thích nghi” ( Adaptive ) là một phần trong “Thuật toán dựa trên từ điển thích nghi LZ” .

Không có vấn đề đối với những phương pháp mà bạn dùng cụ thể , hệ thống tìm kiếm những mẫu ghi trong từ điển càng sâu thì hiệu suất nén file của bạn càng hiệu quả . Đối với vi dụ trên chúng ta có những mẫu sau kèm theo cả khoảng trống

 

 

1.      ask__

2.      what__

3.      you

4.      r__country

5.      __can__do__for__you

Và chúng ta được câu nén như sau :

 

"1not__2345__--__12354"

 

 

Câu trên dùng 18 đơn vị nhớ , và từ điển của chúng ta dùng 41 đơn vị nhớ . Do đó chúng ta nén tổng dung lượng file từ 79 đơn vị xuống còn 59 đơn vị . Đó là một phương pháp để nén cụm từ .

Hệ thống nén file như thế nào thì được cho là tốt ? Tỉ lệ nén file phụ thuộc vào một số nhân tố như : kiểu file , kích thước file và kế hoạch nén .

Hầu hết những ngôn ngữ trên thế giới , những chữ cái và những từ thường xuất hiện trong cùng một mẫu . Bởi vì tỉ lệ nén file cao đối với những file dạng văn bản . Những file văn bản kích thước giản 50% thì được gọi là tốt .Đa số ngôn ngữ lập trình cũng có tỉ lệ nén file cao là vì chúng có tập hợp những lệnh lặp đi lặp lại . Những file bao gồm chứa nhiều thông tin riêng biệt như đồ hoạ hoặc MP3 nên không thể có tỉ lệ nén nhiều với những file này bởi vì chúng không có nhiều mẫu được lặp đi lặp lại .

Nếu file có nhiều mẫu được lặp lại thì tỉ lệ nén sẽ tăng lên cùng với kích thước của file .

Hiệu quả của tỉ lệ nén file phụ thuộc nhiều vào thuật toán sử dụng trong chương trình nén . Một vài chương trình có những từ ghép đặc biệt để lấy những mẫu này trong những kiểu file nào đó và do vậy chúng có thể nén được file có tỉ lệ nén cao hơn . Một vài chương trình khác lại có từ điển bên trong từ điển để tăng hiệu suất với file có kích thước ban đầu lớn mà không phù hợp với file có kích thước ban đầu nhỏ ... Những người lập trình đang cố gắng tạo ra những thuật toán , những chương trình nén với hiệu suất cao hơn .

 Kiểu nén mà chúng ta bàn trong ví dụ trên được gọi là nén bảo toàn , bởi vì file tạo lại sau khi giải nén là chính xác so với file gốc ban đầu . Tất cả sự nén bảo toàn dựa trên ý tưởng tạo một file có kích thước nhỏ hơn để truyền hoặc lưu trữ file và nó quay trở lại trạng thái y hệt với file gốc ban đầu để sử dụng .

Kiểu nén suy hao làm việc hoàn toàn khác . Những chương trình như vậy đơn giản là loại bỏ những Bit thông tin không cần thiết để file có kích thước nhỏ hơn . Kiểu nén này dùng để giảm kích thước file hình ảnh Bitmap có dung lượng lớn .

Chương trình nén file bảo toàn không thể nén nhiều đối với kiểu file hình ảnh . Trong khi phần lớn của hình ảnh nhìn trông có thể tương tự nhau như : tất cả bầu trời là Xanh da trời hầu hết những Pixel riêng biệt chỉ khác nhau một chút . Để cho bức tranh có kích thước nhỏ hơn mà không ảnh hưởng nhiều tới độ phân giải , bạn phải thay đổi giá trị màu của những Pixel . Nếu bức ảnh có nhiều vùng bầu trời xanh , chương trình sẽ dùng một màu xanh cho mọi Pixel để hiển thị vùng bầu trời . Sau đó chương trình sẽ ghi lại file đó . Nếu thuật toán nén được gọi là tốt nếu như chúng ta không nhận biết được sự thay đổi mà kích thước của file cũng giảm đi đáng kể .

  

\"\"\"\"