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

g 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". Điểm mấu chốt này được gọi là “zero - frequency problem”. Vấn đề này cho đến nay vẫn đang được tìm hiểu và chưa được chứng minh. - Thuật toán nén động 1. Thống kê các ký tự có trong văn bản để tạo mô hình mới. 2. Nén mô hình mới vừa xây dựng ở bước một. 3. Lặp lại bước một và bước hai cho đến hết. Tóm lại, trên thực tế những kỹ thuật tiếp cận tổng thể (kỹ thuật thống kê) được áp dụng rất ít do các thuật toán chạy chậm vì các chương trình viết theo kỹ thuật trên phải thực hiện một số lượng lớn các phép tính toán và mặt khác hiệu quả nén lại không cao. b. Cách tiếp cận đi từ chi tiết: Cách tiếp cận này dựa vào những nhận xét phụ thuộc ở thời điểm hiện tại cũng tương tự một thời điểm nào đó trong quá khứ. Nói theo một cách khác thì cách tiếp cận này dựa vào những qui luật nhất định. Các qui luật gộp lại thành từ điển nên ta có thể gọi cách tiếp cận này là phương pháp từ điển mà chúng ta có thể xem xét kỹ hơn ở phần sau. 3.4. KỸ THUẬT TỪ ĐIỂN Kỹ thuật này đã được 1 bài báo xuất bản vào năm 1967 khẳng định: "Phương pháp nén tốt nhất có thể đạt được đó là việc thay thế các xâu ký tự thường xuyên lặp đi, lặp lại nhiều lần bằng chỉ số mà nó đã xảy ra trong quá khứ". Phương pháp thay một đoạn ký tự bằng vị trí một đoạn giống hệt nó trong quá khứ được gọi là Ziv - Lempel do 2 nhà bác học Jacob Zib và Abraham Lempel phát triển năm 1977. Như vậy ta có: Kỹ thuật từ điển là kỹ thuật sử dụng phương pháp phân đoạn văn bản thành các đoạn nhỏ hơn sao cho nó đạt được độ dài nhất có thể được mà nó đã xuất hiện ở trong quá khứ. Định nghĩa (phân đoạn văn bản) Phân đoạn văn bản A là chia nó ra thành các đoạn nhỏ hơn. Mỗi đoạn được gọi là một phân đoạn. Giả sử chúng ta có từ điển D thì tồn tại một ánh xạ f: D -> W trong đó W là tập các đoạn bit 0/1. Việc nén sẽ tối ưu khi chúng ta phân được đoạn văn bản có độ dài lớn nhất mà sao cho khi đi tìm trong quá khứ thì chúng ta được đoạn 0/1 trong W là nhỏ nhất. Trong kỹ thuật từ điển, tương tự như kỹ thuật thống kê, ta cũng có hai phương án sau: + Mã tĩnh (từ điển tĩnh). + Mã động (từ điển động). 3.4.1. Từ điển tĩnh: Mã có từ điển cố định được gọi là mã tĩnh hay nói cách khác là từ điển tĩnh. Một số những nhược điểm của từ điển tĩnh: + Kích thước của từ điển tĩnh không thể mở rộng ra, để cập nhật các thông tin mới so với các loại dữ liệu khác. + Quá trình nghiên cứu thiết kế từ điển đòi hỏi nhiều công sức. + Các thuật toán sử dụng từ điển tĩnh chạy tương đối chậm. + Tốn không gian lưu trữ dữ liệu. Tuy nhiên bên cạnh những nhược điểm này thì từ điển tĩnh cũng có ưu điểm là: Thiết kế các thuật toán áp dụng cho việc tìm kiếm trên từ điển tĩnh đơn giản tốn ít thời gian. Do những đặc tính hạn chế của từ điển tĩnh, kết hợp với những đặc điểm nổi bật của thuật toán nén là "sự cứng nhắc" đã làm cho người dùng chương trình để tiết kiệm bộ nhớ nhàm chán không thích sử dụng các chương trình nén nữa. Vậy phải có cách để khắc phục những hạn chế đó và làm cho chương trình nén dữ liệu trở nên mềm dẻo hơn. Chính vì vậy những thuật toán nén chỉ đạt hiệu quả cao nếu chúng ta xử lý tốt "từ điển" được sử dụng trong các thuật toán nói chung. 3.4.2. Từ điển động: Để khắc phục những hạn chế của từ điển tĩnh, biện pháp được xét đến là: Chúng ta không thiết kế một từ điển sẵn mà " từ điển" đó được xây dựng trong quá trình chạy chương trình. Một từ điển như vậy người ta gọi là từ điển động. Những đặc điểm chính của từ điển động: + Kích thước của từ điển có thể thay đổi tuỳ theo kích thước của tập tin. + Không tốn thời gian lưu trữ từ điển. + Thời gian thực hiên quá trình nén nhanh. + Từ điển không phụ thuộc vào kiểu dữ liệu. + Thời gian thực hiện quá trình giải nén chậm. Với từ điển động thì không những làm cho thuật toán nén đạt hiệu quả cao hơn, khắc phục được sự cứng nhắc của thuật toán nén, góp phần làm cho thuật toán trở nên mềm dẻo hơn. Nhưng kích thước cảu từ điển tăng lên rất nhanh khi các tập tin đem nén mà độ dư thừa của chúng không cao. Vậy để tăng kích thước của từ điển và không làm cho chúng lớn quá mức bộ nhớ mà máy tính có thì chúng ta phải thực hiện xử lý từ điển sao cho lượng thông tin mà từ điển đó đem lại nén đạt hiệu quả cao và cải thiện sự cứng nhắc của thuật toán nén. Như chúng ta đều biết, việc nén dữ liệu chẳng qua là việc mã các thông tin thương xuyên xuất hiện bằng một từ mã ngắn và thông tin ít xuất hiện bằng từ mã dài và được lưu trữ trong một từ điển. Vậy chúng ta có một số phương án sau: + Sử dụng loại mã có chiều dài cố định: Trong phương án này, số bits cần nén dữ liệu cần được quyết định trước khi tiến hành nén. Nén sử dụng số bits ít thì từ điển sẽ nhanh chóng bị đầy do đó hiệu quả nén không cao. Ngược lại nếu chúng ta sử dụng số bits quá lớn thì sẽ gây lãng phí và cũng dẫn đến không có hiệu quả cao trong việc nén. + Sử dụng loại mã có chiều dài thay đổi: Phương án này nảy sinh một vấn đễ là chiều dài mã là bao nhiêu hay nói cách khác đó là kích thước của mảng làm từ điển có phạm vi bao nhiêu là phù hợp?. Nếu kích thước của từ điển nhỏ thì có ưu điểm trong việc tìm kiếm trên từ điển vì vậy thuật toán chạy nhanh khắc phục được một hạn chế của thuật toán nén là thời gian. Ngược lại nếu chúng ta sử dụng một từ điển có kích thước lớn thì làm cho thuật toán chạy chậm. Do vậy chúng ta phải tìm ra kích thước của từ điển sao cho phù hợp để đảm bảo thời gian thực hiện chương trình không quá lâu mà vẫn đạt hiệu quả nén cao. Để đạt được những yêu cầu trên người ta sử dụng loại mã có chiều dài thay đổi từ 8 đến 13 bit. Có nghĩa là khi bộ nén dùng hết mã 8 bits thì nó sẽ dùng mã 9 bits, 10 bits,... Tuy nhiên nếu dùng hết số bits cho phép mà nguồn thông tin vẫn còn thì chúng ta lại có cách giải quyết sau: * Dừng quá trình thêm các đoạn mới vào từ điển, tiến hành xoá từ điển hiện tại và bắt đầu xây dựng lại từ điển cho dữ liệu mới. Theo cách nói trên thì phương pháp nén khá mềm dẻo nhưng hiệu quả nén lại không cao do chúng ta không tận dụng được thông tin trên từ điển cũ. Tóm lại, mã có từ điển cố định được gọi là mã tĩnh và ngược lại nếu từ điển biến đổi thì ta gọi đó là mã động. Để tiến hành nén theo kỹ thuật từ điển ta có thuật toán phân đoạn. Đây chính là tiền đề cho hệ thống mã thuộc họ LZ. Thuật toán phân đoạn bao gồm 3 giai đoạn sau: + Bước 1: Phân đoạn văn bản theo một nguyên lý nào đó. + Bước 2: Mã hoá các đoạn văn bản đó. + Bước 3: Sử dụng một tập phân tích để nén. Không thể có một cơ sở lý luận chắc chắn nào cho phép tìm thuật toán phân đoạn tốt nhất. Chúng ta cho rằng nếu xuất phát từ việc tìm lại sự tương tự trong quá khứ thì nén tìm sự tương tự nào gần giống nhất. Chính vì thế mà các khúc khi phần ra từ văn bản nguồn nên được tính toán sao cho chúng là các phần dài nhất có thể lặp lại được trong quá khứ. Nguyên lý như trên được gọi là nguyên lý kinh nghiệm. 3.4.3. Mã LZ với từ điển tĩnh Trước hết chúng ta định nghĩa lại khái niệm từ điển tĩnh. Định nghĩa từ điển tĩnh: Từ điển tĩnh là từ điển đã được xây dựng từ trước, nó là kết quả của việc nghiên cứu rất lớn các văn bản. Định lý LZ: Giả sử ta có từ điển S gồm n chuỗi ký tự và một luồng thông tin Z có cùng phân số. Giả sử l là độ dài xâu lớn nhất mà có thể lấy được từ điển S tại một thời điểm k nào đó thì khi đó l là một đại lượng ngẫu nhiên mà giá trị của nó chính bằng log2n/H trong đó H là entropy của Z. Tuy nhiên, người ta cũng thấy được những hạn chế của kỹ thuật từ điển tĩnh. Đó là: + Thời gian thực hiện chương trình lâu. + Quá trình xây dựng 1 từ điển tốn nhiều thời gian. + Hiệu quả nén không cao do từ điển không tương ứng với các dữ liệu được tiến hành nén. Từ những hạn chế trên, người ta đã đề ra một phương án khác tối ưu hơn và phương án này được là phương án từ điển động. 3.4.4. Mã LZ với từ điển động Như chúng ta đã biết mã LZ với từ điển tĩnh thì hạn chế nổi bật của phương án tĩnh đó là từ điển có kích thước cố định dẫn tới hiệu quả nén không cao. Do vậy nếu chúng ta mở rộng kích thước của từ điển thì khả năng bao quát được những dữ liệu hơn do đó nâng cao hiệu quả nén. Vì vậy mã LZ động khẳng định rằng nếu chúng ta tăng kích thước từ điển lên thì chúng ta sẽ có thể đọc được những đoạn thay thế có độ dài là log2n/H. Khi độ dài đoạn thay thế lớn thì dẫn tới khả năng nén đạt hiệu quả cao. Những ưu điểm nổi bật của phương án nén với từ điển động là: + Thời gian chạy chương trình giảm so với chương trình cùng kiểu viết theo phơng án từ điển tĩnh. + Quá trình xây dựng từ điển đơn giản không mất nhiều thời gian và một phần nào đó nó làm cho thuật toán trở nên khá mềm dẻo. + Nén bằng phương án từ điển động thì trực quan. NHỮNG PHƯƠNG PHÁP CƠ BẢN VỀ NÉN DỮ LIỆU Có rất nhiều phương pháp về nén dữ liệu và dưới đây là một số phương pháp : 3.5 - PHƯƠNG PHÁP LOẠI TRỪ NHỮNG Ô TRỐNG Phương pháp loại trừ những ô trống được sử dụng lần đầu tiên trong việc truyền tin của IBM. Phương pháp này là nguồn gốc của các phương pháp nén dữ liệu khác. Mục đích của phương pháp là duyệt tệp văn bản và tìm dãy những ô trống. Khi gặp dãy ô trống, dãy này sẽ được thay bằng hai ký tự : ký tự thứ nhất là ký tự đặc biệt mang thông tin lặp lại (trong quá trình gỡ nén, khi gặp ký tự này sẽ hiểu là bắt đầu của một dãy ô trống), ký tự thứ hai chính là số ô trống có trong dãy. Phương pháp loại trừ những ô trống chỉ áp dụng đối với tệp văn bản và đạt tỷ lệ nén 30 - 50% tuy nhiên phương pháp này chỉ có hiệu quả khi dãy có không dưới 3 ô trống. Nhược điểm của phương pháp này là khó chọn ra những ký tự đặc biệt. Để phân biệt được ký tự đặc biệt này với các ký tự khác trong quá trình gỡ nén, đòi hỏi ký tự này không được nằm trong văn bản. Gỡ nén : Đọc lần lượt các ký tự trong tệp đã nén. Khi gặp ký tự đặc biệt nó sẽ đưa ra ô trống đầu tiên, nó sẽ ghi ra số ô trống bằng mã lặp sẽ đọc được sau ký tự đặc biệt đó. Thuật toán loại trừ các ô trống: Tệp dữ liệu nguồn : f Ký tự đặc biệt mang thông tin lặp : db Số ô trống trong dãy (mã lặp) : dem dem = 0 db = 255 while not eof(f) do begin Đọc ký tự trong f là kt; If kt là ô trống then dem = dem + 1; If dem = 255 then begin In db; In dem; dem = 0; end;end else If dem > 2 then begin In dh; In dem; dem = 0;end else If dem = 2 then in ra 2 ô trống; If dem = 1 then in ra 1 ô trống; end; In kt; End; End; 3.6 - BIỂU DIỄN THEO KIỂU TÔPÔ Phương pháp này có hiệu quả kế hoạch trong tệp nguồn có một ký tự nào đó được xuất hiện nhiều lần. Thực chất của phương pháp này là chia tệp dữ liệu thành từng đoạn 8 ký tự. Trước mỗi đoạn sẽ dùng thêm 8 bits gồm các số 0 và số 1 để ghi các vị trí tương ứng. Vị trí tương ứng = 1 nếu ký tự tương ứng là ký tự. = 0 nếu ký tự tương ứng là ô trống. Ví dụ: Nguồn : X1 __ X2 __ X3 __ X3X4X5 ® chuỗi bị nén 10100111X1X2X3X4X5 ® tiết kiệm được 2 bytes Thuật toán biểu diễn theo kiểu Tôpô: Bảng chữ cái : ch [] Số ký tự : dem dem = 0 byte = 0 tr = 0 Đọc ký tự - kt do dem = dem + 1; If kt không phải là ô trống then begin m = 1; for i = 1 to dem-1 do begin dịch chuyển sang trái 1 bit; byte = byte or m; tr = tr + 1; ch[tr] = kt; End; If dem = 8 then begin In byte; for i : = 1 to tr do In ch[i]; dem = tr = byte = 0; End; Đọc ký tự tiếp theo; while eof (f) do begin if dem ¹ 0 then begin In byte; for : = 1 to tr do In ch[i] End; End; End; 3.7 - NÉN NỬA BYTE Phương pháp nén nửa byte dựa vào cấu trúc của các ký tự có trong tệp dữ liệu. Phương pháp này được dùng để nén khi dãy ký tự có 4 bits đầu như nhau trong biểu diễn nhị phân. Khi đó sẽ dùng một ký tự đặc biệt để thông báo tin này, 4 bits (hoặc 8 bits) tiếp theo ghi số ký tự của dãy được mã hoá, cuối cùng là dãy các 4 bits ghi các nửa còn lại của ký tự. Với dãy ký tự có 4 bits đầu như nhau, 4 bits còn lại lần lượt là N1, N2, N3, ... thì khi mã hoá sẽ có dạng : CsCpN1N2N3... trong đó : Cs là ký tự đặc biệt Cp số ký tự của dãy được mã hoá Nếu dùng 4 bits để ghi độ dài của dãy (ghi Cp) thì có thể nén được tối đa 24 - 1 = 15 ký tự. Cs CpN1 N2N3 N4N5 ................ N14N15  Trong trường hợp dùng 8 bits để ghi độ dài của dãy (ghi Cp) thì có thể nén được tối đa 28 - 1 = 255 ký tự. Cs Cp N1N2 N3N4 ................ N255  Việc giải mã đối với phương pháp này là tương đối đơn giản. Trước tiên cần tìm ký tự đặc biệt chỉ định nén = 1/2 byte. Tiếp sau đọc số ký tự của dãy được nén để xác dịnh các phần 4 bits còn lại (N1, N2...). 3.8 - CÁC PHƯƠNG PHÁP KHÁC Ngoài những phương pháp nén đã nêu ra ở trên, có một số thuật toán khác đơn giản hơn, nhưng sử dụng cho tệp dữ liệu là chuỗi. Trong mỗi ngôn ngữ lập trình, luôn chỉ dùng 1 số hỗn hợp các từ khoá, vì thế có thể sử dụng ký tự riêng để mã hoá. Phương pháp mã hoá tương đối được sử dụng trong trường hợp gặp một dãy số là độ đo. Thực hiện phương pháp này chỉ cần nhập giá trị đầu tiên, sau đó nhập độ lệch so với giá trị kề trước. Chương IV GIỚI THIỆU VỀ MỘT SỐ THUẬT TOÁN NÉN DỮ LIỆU Hiện nay có rất nhiều các thuật toán nén dữ liệu khác nhau mà mỗi thuật toán lại có những ưu, nhược điểm của nó. Chúng ta phân loại chúng ra thành các nhóm sau: 4.1. THUẬT TOÁN NÉN CÓ MÔ HÌNH NGUỒN: + Thuật toán Fano - Shanon. + Thuật toán Huffman, Huffman động. 4.2. THUẬT TOÁN ÁP DỤNG VỚI KỸ THUẬT TỪ ĐIỂN: Có rất nhiều thuật toán áp dụng kỹ thuật này như LZ77, LZK, LZSS, LZH... nhưng trong nội dung quyển luận án này, chúng ta chỉ đề cập đến hai thuật toán chính là: + Thuật toán LZ78. + Thuật toán LZW. 4.1.1 - Thuật toán Fano - Shannon Thực chất thuật toán Fano - Shannon là phương pháp mã hoá trên cơ sở thống kê tần số xuất hiện của các ký hiệu trong tệp dữ liệu. Thuật toán này nhằm mục đích tạo ra cây Fano - Shannon theo các bước sau: a. Thiết lập bảng tần số xuất hiện của từng ký hiệu trong tệp nguồn. b. Sắp xếp bảng tần số theo thứ tự giảm dần của tần số xuất hiện, ký hiệu xuất hiện nhiều nhất sẽ đứng đầu bảng, ký hiệu xuất hiện ít nhất sẽ đứng cuối bảng. c. Chia bảng ra thành 2 phần sao cho tổng tần số của nưẻa trên và tổng tần số của nửa dưới gần nhau nhất. d. Nửa trên được gán bởi số 0, nửa dưới được gán bởi số 1. Điều đó có nghĩa là mã của các ký hiệu thuộc nửa trên bắt đầu bằng bit 0, mã của các ký hiệu thuộc nửa dưới bắt đầu bằng bit 1. e. Mỗi nửa lại tiếp tục chia làm 2 phần theo cách trên. Sau mỗi lần như vậy lại thêm 0 hoặc 1 vào đằng sau mã mẹ. Quá trình trên được thực hiện cho đến khi mỗi nhóm chỉ còn duy nhất 1 ký tự. Ví dụ minh hoạ: Cho 1 nguồn có các trạng thái {e, a, i, o, ô} với các xác suất tương ứng (e, o3); (a, 0.2); i,0.2); (0.0,1); u,0.1); (ô,0.1) => Ký tự Tần xuất Mã A 0.2 01 E 0.3 00 I 0.1 101 O 0.2 100 U 0.1 110 ô 0.1 111 Cách nhóm như sau: Mã E 0.3 0.3 00 A 0.2 0.5 0.2 01 O 0.2 0.2 100 I 0.1 0.3 0.1 101 U 0.1 0.5 0.1 110 Ô 0.1 0.2 0.1 111 Để nén một tệp dữ liệu bằng phương pháp Fano - Shannon, công việc đầu tiên là phải đọc tệp nguồn để thống kê tần số xuất hiẹn của mỗi ký hiệu. Sau khi đã thống kê xong, người ta sắp xếp bảng tần số theo thứ tự giảm dần của tần số xuất hiện. Bảng mã tương ứng của các ký hiệu được gởi tới cho chương trình gỡ nén như sau: Mỗi ký hiệu dùng 3 bytes, byte thứ nhất mang ký tự để chuyển mã, 4 bits tiếp theo (4 bits đầu của byte thứ hai) mang độ dài của mã, phần còn lại mang mã tối đa của ký hiệu. Trong quá trình gỡ nén phải sử dụng bảng mã nhận được từ thuật toán nén. đồng thời để giải mã cần phải dựa vào nhận xét: không một mã nào là phần đầu của mã khác. Đánh giá:Vì những lý do trên nên thuật toán Fano - Shannon được xếp trong danh sách những thuật toán thống kê. Tuy nhiên, nhìn chung đây là một phương pháp kém hiệu quả và ít được sử dụng. 4.1.2 - Thuật toán Huffman. 4.1.2.1. Nguyên lý: Nguyên lý của phương pháp Huffman là mã hoá các bytes trong tệp dữ liệu nguồn bằng biến nhị phân. Nó tạo mã độ dài biến thiên là một tập hợp các bits. Đây cũng là một phương pháp nén kiểu thống kê, những ký tự xuất hiện nhiều hơn sẽ có mã ngắn hơn. Mã Huffman có một tính chất quan trọng: mã của một ký hiệu này không thể là phần đầu của mã một ký hiệu khác. Nếu như một ký hiệu được mã hoá bằng tổ hợp nhị phân 101 thì tổ hợp 10110 không thể là mã của một ký hiệu khác trong tệp nguồn. Do đó khi giải mã cần phải đọc lần lượt các bit cho đến khi gặp mã của ký hiệu nào đó. 4.1.2.2. Thuật toán. Việc xây dựng cây mã hoá Huffman được tiến hành bởi một thuật toán khác với thuật toán Fano - Shannon. Nếu như cây Fano - Shannon được xây dựng từ trên xuống dưới bằng cách chia đôi và gán cho mỗi phần 1 bít, công việc kết thúc khi không thể tiến hành phân chia tiếp thì cây Huffman lại được thiết kế từ dưới lên, bắt đầu từ các lá của cây và công việc kết thúc tại điểm gốc. Ví dụ : Cho mô hình nguồn có các trạng thái và tần suất tương ứng như sau: (A, 0.2); (E, 0.3); (I, 0.1), (0. 0,2); (U, 0.1); (Ô, 0.1) ta có: 0 1 0 1 0 1 0 1 e a o 0 1 i u ô Ký tự Tần xuất Mã 0 1 A 0.2 10 E 0.3 01 I 0.1 001 O 0.2 11 U 0.1 0000 Ô 0.1 0001 Bước1: Nhóm 2 chữ cái có tần suất nhỏ nhất tạo ra chữ cái kép. Sau mỗi l