Luận văn Nén và xử lý dữ liệu

Chương I PHẦN MỞ ĐẦU - TẠI SAO PHẢI NÉN DỮ LIỆU 1.1.1 Khái niệm về dữ liệu Trong một bài toán, dữ liệu bao gồm một tập các phần tử cơ sở mà ta gọi là dữ liệu nguyên tử (atoms). Nó có thể là một chữ số, một ký tự... nhưng cũng có thể là một con số, hay một từ..., điều đó tuỳ thuộc vào từng bài toán. 1.1.2. Mục đích của việc nén dữ liệu Một trong những chức năng chính của máy tính là xử lý dữ liệu và lưu trữ. Bên cạnh việc xử lý nhanh, người ta còn quan tâm đến việc lưu trữ được nhiều dữ liệu nhưng lại tiết kiệm được vùng nhớ và giảm chi phí lưu trữ. Về mặt lý thuyết thì các thiết bị lưu trữ là không có giới hạn nhưng ngày nay do nhu cầu xử lý nhiều tập tin, nhiều loại dữ liệu trong cùng một tệp do vậy mà kích thước tệp trở nên khá lớn. Trong nhiều năm gần đây, mạng máy tính đã trở nên phổ biến trên thế giới. Sự ra đời của mạng đã thực hiện được ước mơ chinh phục khoảng cách giữa con người. Những lợi ích mà mạng cung cấp rất đa dạng và phong phú trên các lĩnh vực khác nhau của xã hội như cung cấp, trao đổi thông tin giữa các máy tính, giữa máy tính với server hoặc giữa các server với nhau. Điều này dẫn đến phải làm như thế nào để giảm thiểu thời gian, chi phí sử dụng để trao đổi dữ liệu trên mạng. Nó cũng đồng nghĩa với việc bên cạnh nâng cao chất lượng của các thiết bị truyền dữ liệu trên mạng thì mặt khác chúng ta phải nghĩ ra một phương pháp nào không để sao cho việc truyền dữ liệu có hiệu quả hơn. Tất cả những vấn đề trên nảy sinh ra khái niệm nén dữ liệu. Một trong những hình thức nén dữ liệu đầu tiên là hệ chữ Braille, là một hệ chữ dùng phương pháp mã hoá ký hiệu cho người mù có thể đọc và viết. Ngày nay, nén dữ liệu mang lại rất nhiều lợi ích khác nhau mà điển hình là : + Đối với việc tìm kiếm thì đôi khi ta tìm kiếm thông tin trên dữ liệu nén lại nhanh hơn so với việc tìm kiếm thông tin trên dữ liệu không nén vì do dữ liệu lưu trữ ít nên số phép toán để tìm kiếm giảm và lượng thông tin cao. + Nén dữ liệu đặc biệt hiệu quả với việc truyền dữ liệu trên mạng. Khi nén dữ liệu thì chi phí cho việc truyền dữ liệu trên mạng sẽ giảm mặt khác tốc độ đường truyền sẽ tăng lên bởi vì cùng một lượng thông tin đó thời gian truyền dữ liệu sẽ giảm. Với những ưu điểm trên thì do đó, nén dữ liệu là giải pháp hợp lý nhất nhằm mục đích giảm chi phí cho người sử dụng. Tóm lại những lợi ích mà nén dữ liệu mang lại xoay quanh vấn đề tiết kiệm tối đa chi phí cho việc mua các thiết bị lưu trữ dữ liệu và cho việc luân chuyển thông tin trên mạng. * Một số vấn đề gặp phải khi nén dữ liệu là : + Các thuật toán thực hiện trước hết phải giảm chi phí lưu trữ. + Các thuật toán được thực hiện nhanh, hiệu quả. Với nhiều loại thông tin khác nhau mà ta có các kỹ thuật nén khác nhau, có hiệu quả khác nhau, ví dụ như nén tệp văn bản thường tiết kiệm 20% - 50%, còn đối với tập tin nhị phân khoảng 50% - 90% tuy nhiên đối với các tập tin ngẫu nhiên thì lượng không gian tiết kiệm được rất ít hoặc hầu như không tiết kiệm được (chẳng hạn như tệp *.exe, ...). Do các dữ liệu có độ dư thừa khác nhau nên mỗi phương pháp nén nếu áp dụng đúng sẽ trở nên không cần thiết, không có độ linh hoạt. I.2- NÉN BẢO TOÀN Đó là mô hình nén dữ liệu mà nó cho phép người sử dụng bảo toàn thông tin trong suốt quá trình nén. Điều này được giải thích như sau: Giả sử ta có dữ liệu nguồn là D và dữ liệu nén là D'. Sau khi ta giải nén D' thì được tập D'' mà tập D'' hoàn toàn giống với tập D ban đầu khi được giải nén. Thông thường, kỹ thuật này được áp dụng với các loại dữ liệu như văn bản vì độ chính xác của văn bản. Nếu hiểu theo ngôn ngữ toán học thì đó là một ánh xạ 1 - 1 từ 1 tập X -> Y mà ở đó mỗi phần tử Xi Î X tương ứng với một phần tử Yi Î Y. 1.3 - NÉN KHÔNG BẢO TOÀN Trong kỹ thuật nén, bên cạnh nén bảo toàn thì người ta còn đưa ra khái niệm nén không bảo toàn. Nén không bảo toàn là mô hình nén dữ liệu mà tính bảo toàn của dữ liệu không được coi trọng. Nó có nghĩa là nếu ta có tập dữ liệu D, tập nén D' thì sau khi giải nén ta thu được tập D'' khác tập D ban đầu. Kỹ thuật này thường áp dụng cho việc nén dữ liệu là các loại tệp ảnh vì nói chung nó cũng không ảnh hưởng gì nhiều đến hình dạng ảnh. Nếu biểu diễn bằng toán học, chúng có mô hình sau: F(x) ® { y1, y2, ...} 1.4 - QUÁ TRÌNH NÉN VÀ GIẢI NÉN Quá trình nén dữ liệu là một quá trình gồm 2 công đoạn: 1) Công đoạn nén. 2) Công đoạn giải nén. Chúng ta có thể minh hoạ như sau: a) Công đoạn nén: Dữ liệu ® Mã hoá ® Đóng gói ® Dữ liệu nén. b) Công đoạn giải nén: Dữ liệu nén ® Giải mã ® Mã hoá ® Dữ liệu gốc. Hai công đoạn trên là 2 điển hình trái ngược nhau. Đối với tiến trình nén thì module mã hoá thực hiện việc cắt văn bản nguồn thành các đoạn và gán cho chúng ký hiệu để xác định chúng. Ngược lại đối với tiến trình giải nén thì module giải mã sẽ dựa vào các mã mà module mã hoá ở tiến trình nén sinh ra để tìm đoạn tương ứng. Quá trình tìm đoạn tương ứng đó được thực hiện trên rất nhiều đoạn trong tiến trình nén, giải nén sinh ra. Tập hợp các đoạn đó chúng ta gọi là từ điển. Chương II NHỮNG KHÁI NIỆM VỀ MÔ HÌNH NGUỒN Khi nói đến nén dữ liệu thì tất cả chúng ta đều biết dữ liệu phải được sinh ra ở đâu hay nói nôm na là dữ liệu có nguồn nào đó. Trong nội dung chương này, chúng ta sẽ tìm hiểu một mô hình sinh ra dữ liệu và các đặc tính của chúng. 2.1 - ĐẶT VẤN ĐỀ Trong cuộc sống hàng ngày luôn luôn có sự giao tiếp gữa con người với các sự vật và sự kiện xung quanh chúng ta, các hoạt động này diễn ra với tần suất cao, các hoạt động đó được thể hiện chủ yếu qua các thông tin. Vậy các thông tin đó có từ đâu và cách thức sinh tin như thế nào ? Ví dụ : Trong cuộc sống thì tiếng nói hay văn bản đều được sinh ra từ một bảng chữ cái nào đó. Đối với Việt Nam thì bảng chữ cái đó là bảng chữ cái Tiếng Việt do cha cố Alexsander người Pháp nghĩ ra bao gồm : a á ả ạ à ã ắ ... Như vậy thông tin được sinh ra từ một bảng chữ cái nào đó mà chúng ta có thể gọi là mô hình sinh tin. Ở đây bài toán mô hình hoá nguồn tin mà trong đó mô hình hoá ngôn ngữ tự nhiên là một mong muốn của các chuyên gia dịch máy tự động. Mô hình nguồn là một cơ chế sinh tin, còn luồng tin là dãy các sự kiện sinh ra từ mô hình nguồn. Dưới đây chúng ta có thể xét một vài loại mô hình mà theo đó có thể sinh ra tin. 2.2. MÔ HÌNH PHỤ THUỘC GẦN Nếu chúng ta đo nhiệt độ trong ngày theo một khoảng thời gian nhất định thì ta có một dãy các con số mà khi biết các giá trị liên tiếp thì có thể đoán được giá trị của nhiệt độ tức thời khá chính xác. Hay khi ta viết một cuốn truyện nào đó, nếu từ nào trong đoạn ta cảm thấy không thích thì ta có thể tìm một từ hay hơn thay thế và rõ ràng sự thay đổi này không làm ảnh hưởng đến nội dung cốt truyện mà nó chỉ ảnh hưởng tới một vài câu gần đó mà thôi. 2.3. MÔ HÌNH PHỤ THUỘC XA Một chương trình máy tính được viết bằng một ngôn ngữ lập trình nào đó là một ví dụ về phụ thuộc xa. Với ngôn ngữ Pascal câu lệnh đầu tiên "begin" và câu lệnh cuối "End" có mối liên quan trực tiếp đến nhau. 2.4. MÔ HÌNH PHÂN CẤP Để minh hoạ cho mô hình này, chúng ta có thể thấy trong các kinh bản của phim. Sự vận động của các nhân vật tuân thủ theo các quy luật về không gian, thời gian, tâm lý, nhân quả... là một khái niệm phụ thuộc gần theo kiểu nào đó và cũng chỉ là mục đích thể hiện 1 ý tưởng nào đó của tác giả. Ý tưởng của các lập trình viên cũng là một ví dụ về mô hình phân cấp. Định nghĩa mô hình nguồn. Một bảng mã M được gọi là mô hình nguồn nếu nó thoả mãn các điều kiện sau : + Nó phải là 1 hệ thống tín hiệu. + Phải tồn tại các quy tắc sinh tin. + Phải có quy tắc khởi đầu và kết thúc. Hay nói cách khác 1 mô hình nguồn là tập hợp của 4 thành phần sau trong đó : å, D ¹ F ; å, D không giao nhau. + Tập å được gọi là từ điển cơ bản, mỗi phần tử của nó là phần tử kết thúc. + Tập D được gọi là từ điển hỗ trợ. + Ký hiệu I Î D được gọi là ký hiệu ban đầu + R là tập các quy tắc sinh tin. Trong kỹ thuật nén dữ liệu nếu chúng ta biết được mô hình nguồn sinh tin thì chúng ta sẽ có được những thuật toán phù hợp dể đạt được hiệu quả nén cao. Mặt khác 1 văn bản có thể được sinh ra từ nhiều mô hình nguồn khác nhau, nếu không tìm được mô hình tốt thì hiệu quả nén sẽ cao vì hiệu quả nén phụ thuộc rất nhiều vào entropy của mô hình nguồn sinh tin đó. Tóm lại, để nén dữ liệu đạt hiệu quả cao thì bên cạnh việc khai thác tối đa độ dư thừa của dữ liệu, chúng ta còn cần phải tìm ra mô hình nguồn sinh ra và thông tin đó sao cho entropy của mô hình đó là nhỏ nhất có thể đạt được. 2.5 - MỘT SỐ MÔ HÌNH 2.5.1. Mô hình context Mô hình này dựa vào đặc trưng của ký tự tại thời điểm hiện tại được xác định thông qua một số nào đó của ký tự trước. Một đoạn như vậy được gọi là đoạn. * Định nghĩa mô hình context Mô hình context bao gồm 1 bảng chữ cái và 1 từ điển chứa 1 số hữu hạn các đoạn có tần suất xuất hiện riêng. Mỗi đoạn xác định xác suất hiệu ký tự tiếp theo đoạn. 2.5.2. Mô hình ngữ pháp Mô hình ngữ pháp là một mô hình sinh tin bằng một số hữu hạn các quy tắc nào đó. * Định nghĩa : Mô hình ngữ pháp là một tập hợp hữu hạn các ký tự và quy tắc để xây dựng thông tin, các quy tắc đó được sử dụng với tần suất nhất định. Mô hình ngữ pháp được áp dụng phổ biến trong các loại chương trình dịch hoặc ngôn ngữ lập trình như TP, TC... bởi vì các chương trình mà chúng ta viết để cho máy hiểu đều phải tuân theo một quy tắc nhất định nào đó tùy thuộc vào từng loại ngôn ngữ khác nhau. Ví dụ : trong ngôn ngữ Pascal : Program { tên chương trình } Uses { các unit sử dụng } Var { khai báo biến và thủ tục } Begin { chương trình chính } ............... End. { kết thúc chương trình } 2.5.3. Mô hình state : Do A.A.Markov (1856-1922) đưa ra. * Định nghĩa : Mô hình state là một đồ thị định hướng mà mỗi một cạnh có một nhãn và một trọng số là xác suất chuyển trạng thái đọc theo hướng đó, tổng các xác suất chuyển trạng thái để ra khỏi một đỉnh bất kỳ của đồ thị luôn luôn = 1. Ví dụ: Với mô hình trên, ta có thể có các chuỗi văn bản khác nhau như vậy với một chuỗi văn bản bất kỳ thì luồng thông tin sinh ra từ mô hình trên đó là một chu trình nào đó. Mô hình state được gọi là xác định nếu có một số nguyên B đủ lớn sao cho mọi dãy tên các cạnh do mô hình state sinh ra có độ dài lớn hơn B xác định duy nhất một dãy các đỉnh các cạnh mà nó đi qua. Như thế luồng tin đủ dài sẽ tương ứng với một chu trình nào đó đi qua dọc các đỉnh và các cạnh. Entropy của luồng tin khi đó được định nghĩa thông qua entropy của chu trình. Vậy entropy là gì ? Chúng ta tiếp tục xem xét khái niệm về entropy. Định nghĩa entropy: Entropy là độ khó trung bình để đoán nhận 1 thông tin trạng thái được sinh ra từ mô hình nguồn. Công thức tính entropy : - Cách tính : 1. Xác định số trạng thái. 2. Tìm ma trận xác suất chuyển trạng thái. 3. Tìm vector riêng 4. Tính entropy của mỗi trạng thái. 5. Tìm entropy nguồn bằng cách lấy tổng các tích xác suất xuất hiện của trạng thái với entropy của riêng nó. Ví dụ : Giả sử có mô hình sau : Bước 1 : Số trạng thái = 2 Bước 2 : Ma trận chuyển a11 = ; a21 = = a12 = = 1 ; a22 = 0 P = Bước 3: Giá trị riêng là No của phương trình. det = 0 Khai triển ra ta có phương trình sau : nghiệm là : l1 = 1 ; l2 = - Vì trong đó X1 và X2 là xác suất xuất hiện của trạng thái 1 và 2 nên l ³ 0 do đó ta chọn l = l1 =1. Giải hệ phương trình trên với l = 1 do X1 + X2 = 1 => có No: X1 = ; X2 = Bước 4 : Tính entropy cả từng trạng thái. - Trạng thái 1 : E1 = + = 1.80096 - Trạng thái 2 : E2 = = 0.84036 Bước 5 : E = X1E1 + X2E2 = = 1.55368 Kết luận : Vậy entropy của nguồn là : 1.55368 Chương III MỘT SỐ PHƯƠNG PHÁP VÀ KỸ THUẬT CƠ BẢN VỀ NÉN DỮ LIỆU MỘT SỐ KỸ THUẬT NÉN DỮ LIỆU 3.I. ĐỊNH NGHĨA NÉN DỮ LIỆU Nén dữ liệu thực chất là một hình thức mã hoá dữ liệu để ghi lại dòng dữ liệu sao cho tốn ít bộ nhớ hơn mà lại cho phép chúng ta khôi phục lại dữ liệu ban đầu. 3.2.MỘT SỐ LOẠI MÃ A- Mã ký hiệu: Định nghĩa : Đó là một hệ thống quy ước các mã được sử dụng để nhận ra 1 chuỗi các sự kiện khác nhau thì được gọi là ký hiệu. Mã ký hiệu là 1 hình thức của phương pháp nén dữ liệu. Mã ký hiệu xuất hiện hàng ngày xung quanh chúng ta. Ví dụ : Trong văn bản Nhà nước thường có cụm từ : CV ® công văn ; QĐ ® quyết định TTCP ® Thủ tướng Chính phủ ... Với các nước phát triển, hệ thống chuẩn hoá ký hiệu cho phép dùng chúng một cách dễ dàng và tiết kiệm như trong lĩnh vực điện tín, telex, thư điện tử, ... Xét về các mặt khác nhau mà mã ký hiệu được áp dụng thì mã ký hiệu cung cấp thông tin cho chúng ta đầy đủ hơn, nó dễ dàng gợi nhớ trí nhớ của mọi người do vậy lưọng thông tin từ mã ký hiệu sinh ra là rất lớn. Một số đặc điểm của mã ký hiệu: + Tiết kiệm bộ nhớ, tiết kiệm thời gian. + Tính nguyên thủy của mã. + Tính tương đối của hệ thống mã. Nhờ những đặc điểm trên mà mã ký hiệu được sử dụng nhiều trong lĩnh vực như quản lý dữ liệu, quản lý dân sự, quản lý việc mua bán hàng hoá... * Tính nguyên thuỷ của mã được xem xét như sau: Một trong những lĩnh vực sử dụng mã ký hiệu nhiều nhất là quản trị dữ liệu. Dữ liệu là đặc tính của đối tượng quản lý và được chia ra làm 2 đặc tính sau: * Quản lý sự vật: Sự vật là các chủ thể mà chúng ta gọi nó là các thực thể. * Quản lý sự việc : Sự việc các hoạt động biên nhận ghi lại sự tương tác của các sự vật được gọi là các form. Chính mã ký hiệu sẽ là địa chỉ dùng để truy cập kho dữ liệu. Đồng thời mã hoá ký hiệu đưa ra một số tính chất duy nhất của một đối tượng nào đó thoả mãn mà thôi. Như vậy tính nguyên thuỷ của mã ký hiệu chính là cách ghi nhận các sự vật hay sự việc. + Tính tương đối: Để tra cứu một thông tin nào đó trong CSDL, chúng ta dựa vào các khoá để xem xét đặc điểm của thông tin nhưng việc tìm kiếm này không thể chứng minh được rằng CSDL chỉ có duy nhất thông tin có khoá đó mà nó còn có thể có các thông tin khác cùng có khoá như vậy. Đây chính là tính tương đối của mã ký hiệu. Chính vì vậy mà tính tương đối của mã ký hiệu cũng nảy sinh ra một số vấn đề. Ví dụ : - Hệ thống chuẩn mã Tiếng Việt trên PC ở nước ta do các nhà làm mã quá lạm dụng tính tương đối của mã ký hiệu để tạo ra bảng chữ cái chuẩn cho máy tính nên ở Việt Nam có tới 3 hệ thống mã Tiếng Việt khác nhau cho 3 khu vực khác nhau như : Khu vực phía Bắc - ABC ; miền Trung - Vietware ; miền Nam – VNI. - Hệ thống điện tín (telex) do Moorse phát minh ra. Trong hệ thống này chỉ gồm 2 ký tự chấm và gạch. Giữa cách dấu chấm và gạch được ngăn cách bằng các khoảng cách. B. Mã đóng gói Là một phương pháp nén dữ liệu trong mọi phương pháp mã bao giờ cũng có một khâu đóng gói. Thông thường chúng ta hay ghi các byte gồm 8 bit 0/1 cho nên đóng gói ở đây là cách thức tạo ra các byte từ dãy các bit 0/1. Đa số các thuật toán mà chúng ta sử dụng để mô phỏng thuật toán nén d/l đều cho ra dãy các bit 0/1 sau đó là bước đóng gói các byte 0/1 ấy lại. Ví dụ: Đóng gói các chữ "abcdu" thành u byte. a b c d u 100 10001 01 001 0010111010011010101 Trong hình thức này chúng ta có các kỹ thuật đóng gói khác nhau nhưng phổ biến vẫn là kỹ thuật đóng gói định lượng. + Khái niệm đóng gói định lượng: Đóng gói định lượng là cách thức chúng ta qui định số byte dành cho các ký tự được ghi trong tệp nén. Đặc điểm của mã đóng gói định lượng: + Phương pháp nén không mềm dẻo. + Hiệu quả nén chưa cao. + Thời gian chạy nhanh. Ví dụ: Chúng ta xét đầu ra của thuật toán L778 của 1 xâu ký tự "aaabbabaabaaabab" là: (0+a) (10 + b) (3 + a) (4 + a) (5 + a) (4 + b). Nếu ta ghi mỗi ký tự là 1 byte thì sẽ dẫn tới kích thước của tệp nén có thể to hơn kích thước cuả tệp trước khi nén đồng thời chúng ta cũng sẽ gặp một số khó khăn trong việc giải nén. Vì vậy đóng gối cũng là một khâu quan trọng trong việc nén dữ liệu. Trong phương pháp định lượng chúng ta phải có một số qui ước nhất định để đóng gói các ký tự đó sao cho tốn ít bộ nhớ nhất. Như ở ví dụ trên nếu chúng ta đóng gói các con số nằm trong khoảng 1- 2 byte và các ký tự chúng ta cố định rất nhiều do vậy mà hiệu quả nén cao. Với qui nước trên, chúng ta có đầu ra là: 0a1a3a4a5a4b. Bên cạnh khái niệm đóng gói định lượng thì ta cũng có khái niệm đóng gói tự động. *Định nghĩa: Đóng gói tự động là hình thức chương trình tự tạo ra các byte theo một số tiêu chuẩn nhất định nào đó. Kỹ thuật đóng gói tự động được áp dụng nhiều trong thuật toán nén Huffman. Một số đặc điểm của mã đóng gói tự động: + Phương pháp nén trở nên mềm dẻo + Hiệu quả nén cao + Thời gian chạy tương đối chậm. C. Mã gần đúng Mã gần đúng được sử dụng phổ biến trong lĩnh vực ảnh và âm thanh. Một trong những ứng dụng phổ biến nhất của mã gần đúng là điện thoại di động. Điện thoại di động truyền thông tin đi sau khi đã nén. Như thế chúng tá không truyền âm thah tiếng nói đi mà truyền "cấu tạo của một cái miệng" nó sẽ phát lại cho chúng ta nghe lại. Hiệu quả của phương pháp này cho phép chúng nén tín hiệu tiếng nói từ 8000 byte/giây xuống 50 byte/giây. Tương tự kỹ thuật này cũng được áp dụng cho các loại điện thoại hình. D. Mã theo độ dài (RLE) Trong số các phương pháp dùng để nén dữ liệu thì phương pháp đơn giản nhất là phương pháp mã hoá theo độ dài. + Nguyên tắc mã: Nguyên tắc cơ bản của phương pháp này là phát hiện một ký tự có số lần xuất hiện liên tiếp vượt qua một ngưỡng cố định nào đó. Trong trường hợp này dãy sẽ được thay thế bằng 3 ký tự. Ký tự thứ nhất là ký tự đặc biệt, thông báo dãy tiếp là dãy đặc biệt. Ký thự thứ hai chỉ số lần lặp. Ký tự thứ ba chỉ ký tự lặp Như vậy, tư tưởng của phương pháp này là thay thế một dãy bằng một dãy khác ngắn hơn tuân theo một ngưỡng nào đó, và thông thường ngưỡng có giá trị là 4. +Ví dụ: Dãy nguồn: ..SSOOOOONNNLLLLLLAAANNN.. Dãy nhận được sau khi nén: .... HH CS S O NNN CS 6L AAAN... Tuy nhiên phương pháp này cũng có nhiều khuyết điểm. Trước hết là ký tự đặc biệt không được phép xuất hiện trong tệp dữ liệu nguồn. Nếu ký tự đó xuất hiện với tư cách là dữ liệu thì khi gỡ nén nó sẽ dẫn đến tình trạng nhập nhằng. Ngoài ra người ta còn chú ý đến chỉ số lặp. Nếu chỉ số lặp được lưu trữ trên 1 byte thì số lần lặp của một ký tự không vượt qua 255. Khi số lần lặp của một ký tự vượt quá 255 thì chỉ số lặp sẽ được lưu trữ trên 2 byte. Trong trường hợp này, chỉ số lặp tối đa sẽ được nâng lên thành 65535. Tuy nhiên trong thực tế sẽ số lần lặp của một ký tự thường £ 255 -> quá trình nén sẽ chiếm 1 byte vô ích. Dựa vào những đặc điểm trên ta thấy phương pháp mã hoá theo độ dài không được lợi nhiều trong việc nén tệp văn bản. Nhưng đối với những tệp hình ảnh thì phương pháp này lại có hiệu quả cao vì ảnh đen trắng là dãy các số 0 (điểm đen) và các số 1 (điểm trắng) đan xen nhau. Trong trường hợp này việc đếm số lần xuất hiện liên tiếp của các số 0 và số 1 tương đối dễ dàng và khi mã hoá không cần ký tự đặc biệt cũng như không cần phải chỉ rõ ký tự lặp là ký tự nào mà chỉ cần ghi số lần xen kẽ. + Ví dụ: Nguồn: 0000000000 11111111 00000 111111 => sẽ có mã: 10 8 5 6 N... với hình ảnh mà điểm đầu tiên không phải là điểm đen như ví dụ trên thì phải bắt đầu dãy mã bằng 1 số 0. + Ví dụ: Nguồn: ... 00 .. 0 11111100 ... 280 lần Nén: ... 2550 25 52 ... Đối với ảnh màu thì mỗi màu sắc được hiểu thị bằng một số nguyên. Để phân biệt được sự khác nhau trong lặp mầu người ta phải xen vào một ký tự đặc biệt và tiếp theo sau sẽ là chỉ số lặp và ký tự được lặp. Có nghĩa là để mã hoá ảnh màu có thể dùng một cặp, ký tự đầu là lần lặp lại, ký tự sau là một màu và dùng một ký tự đặc biệt (ví dụ như #) để báo hiệu sẽ xuất hiện các cập nhật. +Ví dụ: Nguồn: 11111122223344444444 Nén: #61 # 42 # 23 # 84 Đối với những màu là duy nhất (ký tự có chỉ số lặp là 1) thì màu đó không cần đi với ký tự đặc biệt. + Thuật toán mã theo độ dài: * Nén: Tệp nguồn: f Ký tự đặc biệt: db Số lần lặp: dem db = 255 dem = 1 Đọc ký tự đầu tiên trong f là ktlap While not eof (f) do begin - Đọc ký tự tiếp theo -kt; if kt := kt lặp then dem = dem + 1 else if dem > 3 then begin In db; In dem; In ktlap; End;end; for |:= 1 to dem do In ktlap End; Dem: = 1 ktlap := kt End; * Giải nén: Tệp nén: f Ký tự đặc biệt: db Số lần lặp: dem db = 255 While not eof (f) do begin Đọc ký tự trong f là kt; If kt:=db then begin Đọc ký tự tiếp - dem; Đọc ký tự tiếp - ktlap; for | = 1 to dem do In ktlap else Đọc ký tự tiếp; end; End ; Trong phương pháp này, người ta sử dụng ký tự đặc biệt với tư cách là ký tự không bao giờ xuất hiện trong tệp dữ liệu nguồn. Đây là tư tưởng không chuẩn mực bởi vì tệp dữ liệu nguồn có thể chứa tất cả các ký tự của bảng mã ASCII. Do đó phương pháp này được sử dụng nhiều nhất trong việc nén hình ảnh. E. Mã hoá thích nghi dần của tần số (AFE) Phương pháp này là phương pháp mã hoá thích nghi dần của từng ký tự theo tần số xuất hiện. Khởi đầu của việc nén, nếu một ký tự được mã hoá trên 5 bits thì nó cũng có thể được mã hoá bằng 1 hay 9 bits tuỳ thuộc vào sự xuất hiện của nó là nhiều hay ít. Trong phương pháp này, việc nén và gỡ nén phải tiến hành song song. Mỗi modul sẽ có chung bảng mã ban đầu cho 1 byte truyền đi. Nhưng chúng sẽ phụ thuộc vào tần số xuất hiện của ký tự và tuân theo qui tắc cải biến. Với mục đích như vậy, phải lập mã cho mỗi byte và lưu trữ chúng trong một bảng tham khảo hay là trong một từ điển. Bảng này dùng làm cơ sở cho sự lập mà của mỗi ký tự, có mặt tổng hai modul nén và gỡ nén. Mã của mỗi byte bao gồm 2 phần: Phần đầu (Header) và phần thân (Body). Phần đầu thường gồm 3 bits và phần thân có 1 - 8 bits, tuỳ thuộc vào byte để lập mã và nhất là tần số xuất hiện của mã. Phần đầu chỉ ra độ dài của thân mã. Khi giải mã không cần xử lý từng bit để phân biệt các byte đã truyền như trong phương pháp Huffman. Để giải mã chỉ cần đọc 3 bits đầu để xác định độ dài n của thân mã, sau đó đọc n bits tiếp theo để khôi phục lại mã đã truyền đi. 3.3- MÔ HÌNH NÉN Chúng ta có thể có thuật toán nén tốt khi biết được mô hình sinh ra nguồn tin. Song việc tìm ra mô hình sinh ra dữ liệu đó là không thể. Vậy có cách nào nén được mà không biết mô hình sinh nguồn tin. Chúng ta có 2 phương pháp sau: - Mô hình tĩnh: Đó là mô hình tìm được thông qua nghiên cứu các đặc trưng thống kê của văn bản rồi sau đó sử dụng chúng. - Mô hình thích ứng: Mô hình thích ứng có xuất phát điểm là một mô hình tổng quát nào đó sau đó hiệu chỉnh dần. Đặc điểm của mô hình thích ứng: + Mô hình thích ứng dựa vào thống kê của một số rất lớn các văn bản cùng loại và áp dụng cho văn bản mới. Ưu điểm của phương pháp này là trình nén dãn chạy nhanh. + Dựa vào mô hình nén giả định để chúng ta tính giá trị các trọng tải và tiến hành nén. 3.3.1. Nén dữ liệu có mô hình nguồn Một trong những đặc điểm của việc nén dữ liệu này là cả người nén cùng biết nguồn sinh ra tin. Những thuật toán nén dữ liệu đặc trưng cho việc nén dữ liệu có mô hình nguồn này là: + Thuật toán Fano - Shannon + Thuật toán Huffman. 3.3.2. Nén dữ liệu chưa có mô hình nguồn Một trong những ví dụ điển hình về nén chưa có mô hình nguồn là ngôn ngữ tự nhiên. Chúng ta luôn rơi vào tình trạng có văn bản mà không có mô hình nguồn. Để tìm ra một thuật toán nén tốt nhất thì chúng ta phải tìm ra qui luật của chúng. Qua nghiên cứu có thể rút ra được hai cách tiếp cận sau: a. Cách tiếp cận tổng thể: Cách tiếp cận này còn được gọi là phương pháp thống kê. Cách này dựa vào nhận xét tinh tế, đó là những gì đã xảy ra trong quá khứ thì sẽ xảy ra trong tương lai. Điều này cũng đã được thừa nhận trên thực tế mà đặc trưng là những câu tục ngữ của cha ông chúng ta được đúc kết từ nhiều đời nay như: "Đêm tháng 5 chưa nằm đã sáng, ngày tháng 10 chưa cười đã tối", ... Như vậy, để có mô hình luồng tin, chúng ta phải tìm ra một số điều kiện cho luồng tin. Ở đây chúng ta chỉ xét mô hình sinh tin là ngẫu nhiên nhận hữu hạn các giá trị từ một ngùôn tin bất kỳ sao cho sự xuất hiện của thông tin sau phụ thuộc vào giá trị của lượng thông tin đứng trước nó. Cách tiếp cận này gồm hai phương pháp sau: + Phương án tĩnh. + Phương án động. Phương án tĩnh được tiến hành mà theo 2 bước: 1. Tìm mô hình thích hợp dựa vào thống kê. 2. Tiến hành mã nén theo phương án đã có mô hình. Phương án động: Đặc trưng chính trong phương án động là các thuật toán, dựa vào sự cảm nhận sau. Đặt giả sử chúng ta tiến hành nén dẽ liệu trong khi chưa biết rõ ký tự nào sẽ xuất hiện tiếp theo. Nhưng nếu chúng ta biết được xác suất xuất hiện của một chữ tiếp theo là gì thì trên thực tế chúng ta có thể biết được mô hình nén và sẽ có thuật toán để nén dữ liệu. Tuy nhiên ở đây lại nảy sinh ra vấn đề là làm thế nào để dự đoán ký tự nào sẽ xuất hiện, xuất hiện ít hay xuất hiện nhiều nếu chúng ta chỉ dựa vào ký tự đã xuất hiện. Xét ví dụ sau đây: Giả sử chúng ta có một văn bản gồm "aabbababab... bbaaba". Tất nhiên, nếu văn bản chưa kết thúc thì ta không thể khẳng định là văn bản chỉ gồm 2 ký tự "a" & "b" thì chưa chắc chắn vì có thể có 1 ký tự bất kỳ xuất hiện như "s", "t"... Do vậy trong phương án động ta luôn phải có phương án dự phòng. Vậy xác xuất xuất hiện của ký tự chưa xuất hiện đó là bao nhiêu? Ta có thể nói rằng "xác suất của một ký tự nào đó chưa xuất hiện tuy rất nhỏ nhưng vẫn phải lớn hơn 0