Mã hóa Shanon fano - Huffman

lại. Ta muốn nói rằng chuỗi này gồm bốn chữ A theo sau bởi ba chữ B rồi lại theo sau bởi hai chữ A, rồi lại theo sau bởi năm chữ B... 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 như sau: 4A3BAA5B8CDABCB3A4B3CD Ở đây "4A" có nghĩa là "bốn chữ A"... Chú ý là không đáng để mã hoá các loạt chạy có độ dài 1 hoặc 2 vì cần đến hai kí tự để mã hoá. Ðối với các tập tin nhị phân 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"QDABBBAABQHCDABCBAAAQDBCCCDTổ 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. 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. 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. Mô hình từ điển Thuật toán LZ78 Thay vì thông báo vị trí đoạn văn lặp lại trong quá khứ, mã LZ78 đánh số tất cả các đoạn văn sao cho mỗi đoạn ghi nhận số hiệu đoạn văn lặp lại trong quá khứ cộng với một ký tự mà nó làm cho đoạn đó khác với đoạn trong quá khứ. Như vậy mỗi đoạn mới là một đoạn ký tự trong quá khứ cộng với một ký tự trong quá khứ. Chính vì thế đoạn mới khác với đoạn cũ trong quá khứ. Ví dụ: Giả sứ ta có đoạn văn bản sau:” aaabbabaabaaabab” Theo thuật toán LZ78 thì chúng được phân đoạn như sau: Input A Aa b Ba baa baaa bab Đoạn 1 2 3 4 5 6 7 output 0+a 1+a 0+b 3+a 4+a 5+a 4+b Như vậy bản nén của chúng ta là: (0,a); (1,a); (0,b); (3,a); (4,a); (5,a); (4,b) Thuật toán nén: Bước 1: Đọc một ký tự -> ch, đoạn được gán bằng 1, kết nạp ký tự đó vào từ điển, w=ch; Bước 2: While not eof(f) do Begin Đọc tiếp ký tự tiếp theo w:= ww+ch; If w thuộc từ điển then ww:=w; Else begin Code(w,j); Ghi j và ch vào tệp nén. Thêm w vào từ điển. End; End; Bước 3: Dừng chương trình. Thuật toán giải nén Bước 1: Đọc thông tin về từ điển đã được lưu trong tệp nén, tl:=false; Bước 2: while not eof(f) do Begin Đọc byte tiếp theo -> b Decode(b,s,t); If tl=false then w:=w+s Else w:=ww+s; TIMCHU(w,t); If t=false then Begin Ghi s ra tệp giải nén Thêm s vào từ điển End Else Begin ww:=s; End; End; Bước 3: Dừng chương trình. Đánh giá: Nói chung thuật toán LZ78 là một thuật toán nén văn bản khá tốt, có thời gian chạy chương trình tương đối nhanh tuy nhiên khả năng tiết kiệm chưa được khai thác. Thuật toán LZW Giải thuật nén LZW xây dựng một từ điển lưu các mẫu có tần suất xuất hiện cao trong ảnh. Từ điển là tập hợp những cặp từ vựng và nghĩa của nó. Trong đó, từ vựng sẽ là các từ mã được sắp xếp theo thứ tự nhất định. Nghĩa là một chuỗi con trong dữ liệu ảnh. Từ điển được xây dựng đồng thời với quá trình đọc dữ liệu. Sự có mặt của một chuỗi con trong từ điển khẳng định rằng chuỗi đó đã từng xuất hiện trong phần dữ liệu đã đọc. Thuật toán liên tục “tra cứu” và cập nhật từ điển sau mỗi lần đọc một ký tự dữ liệu đầu vào. Do kích thước bộ nhớ không phải vô hạn và để đảm bảo tốc độ tìm kiếm, từ điển chỉ giới hạn 4096 ở phần tử dùng để lưu lớn nhất là 4096 giá trị của các từ mã. Như vậy độ dài lớn nhất của từ mã là 12 bits (4096 = 212 ). Cấu trúc từ điển như sau. 0 0 … … 255 255 256 256| Clear Code 257 257| End of Information 258 Chuỗi mới … … 4095 Chuỗi mới 256:Mã xoá CC để khắc phục tình trạng mẫu lặp lớn hơn 4096, nếu mẫu lặp lớn hơn 4096 thì gởi CC để xây dựng từ điển cho phần tiếp theo. Eoi: Báo hiệu hết một phần nén. 256 từ mã đầu tiên theo thứ tự từ 0…255 chứa các số nguyên từ 0…255. Đây là mã của 256 ký tự cơ bản trong bảng mã ASCII. Từ mã thứ 256 chứa một mã đặc biệt là “mã xoá” (CC- Clear Code). Mục đích việc dùng mã xoá nhằm khắc phục tình trạng số mẫu lặp trong ảnh lớn hơn 4096. Khi đó một ảnh được quan niệm là nhiều mảnh ảnh, và từ điển là một bộ từ điển gồm nhiều từ điển con. Cứ hêt một mảnh ảnh người ta lại gửi một mã xoá để báo hiệu kết thúc mảnh ảnh cũ, bắt đầu mảnh ảnh mới đồng thời khởi tạo lại từ điển cho mảnh ảnh mới. Mã xoá có giá trị là 256. Từ mã thứ 257 chứa mã kết thúc thông tin (EOI – End of information). Mã này có giá trị là 257. Như chúng ta đã biết, một file ảnh GIF có thể có chứa nhiều ảnh.Mỗi một ảnh sẽ được mã hoá riêng.Chương trình giải mã sẽ lặp lại thao tác giải mã từng ảnh cho đến khi gặp mã kết thúc thông tin thì dừng lại. Các từ mã còn lại (từ 258 đến 4095) chứa các mẫu thường lặp lại trong ảnh. 512 phần tử đầu tiên của từ điển biểu diễn bằng 9 bit. Các từ mã từ 512 đến 1023 biểu diễn bởi 10 bit, từ 1024 đến 2047 biểu diễn bởi 11 bit và từ 2048 đến 4095 biểu diễn bởi 12 bit. 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. Quá trình nén: LZW bắt đầu bởi 1 từ điển 256 kí tự (trong trường hợp sử dụng bảng mã 8 bits) và sử dụng chúng như tập kí tự chuẩn. Sau đó mỗi lần đọc nó đọc 8 bits (ví dụ 't', 'r', ...) và mã hóa thành con số tương ứng với chỉ mục của kí tự đó trong từ điển. Mỗi khi LZW đi qua 1 chuỗi con mới (giả sử "tr") thì nó thêm chuỗi con đó vào từ điển; Mỗi khi nó đi qua 1 chuỗi con mà nó đã thấy trước đó, nó chỉ đọc thêm 1 kí tự mới nữa và cộng với chuỗi con đã biết để tạo ra 1 chuỗi con mới. Lần tiếp theo LZW bắt gặp một chuỗi con đã có, nó chỉ có việc sử dụng số chỉ mục tương ứng trong từ điển. Thường thì người ta sẽ định sẵn số lượng lớn nhất các từ trong từ điển (giả sử 4096), vì thế việc nén LZW không làm tiêu tốn hết toàn bộ bộ nhớ. Vì vậy mã của các chuỗi con trong ví dụ này là 12 bits (2 ^ 12 = 4096). Cần thiết phải lập mã dài hơn số bits của một kí tự (12 vs 8 bits), do đo khi rất nhiều chuỗi con lặp lại sẽ được thay thế bởi một mã duy nhất thì việc nén được thực hiện. Ví dụ: Các bước để mã hoá chuỗi "ABCBCABCABCD" như sau: Các bước thực hiện. Bươc 1: w = NIL; Bước 2: Trong khi đọc được ký tự thứ k trong chuỗi: Bước 3: Nếu wk đã tồn tại trong từ điển thì w=wk Bước 4: Còn không thì thêm wk vào trong từ điển, mã hoá ngõ ra cho w,w=k k=k+1 Count W K wk symbol index output 0 Nil A A 1 A B AB AB 258 65 2 B C BC BC 259 66 3 C B CB CB 260 67 4 B C BC 5 BC A BCA BCA 261 259 6 A B AB 7 AB C ABC ABC 262 258 8 C A CA CA 263 67 9 A B AB 10 AB C ABC 11 ABC D ABCD ABCD 264 262 12 D NIL D 68 Chuỗi ra: 65- 66- 67- 259 -258- 67 (output) Đầu vào kích thước: 12 x 8 = 96 bits. Đầu ra kích thước là: 5 x 8 + 3 x 9 = 67 bits Tỉ lệ nén là: 96 /67 =1.43 PHUƠNG PHÁP NÉN TỔN HAO Phương pháp nén ảnh MPEG. MPEG (Moving Picture Expert Group) được ra đời vào năm 1988 nhằm mục đích chuẩn hoá cho nén tín hiệu âm thanh và video. MPEG - 1 có thể nén tín hiệu video tới 1.5Mbit/s với chất lượng VHS và âm thanh lập thể (stereo audio) với tốc độ 192 bit/s. Nó được dùng để lưu trữ video và âm thanh trên CD-ROM. Vào những năm 1990, MPEG-2 đã ra đời nhằm đáp ứng các tiêu chuẩn nén video cho truyền hình. MPEG-2 có khả năng mã hoá tín hiệu truyền hình ở tốc độ 3-15Mbit/s và truyền hình độ nét cao ở tốc độ tới 15-30Mbit/s. MPEG-2 cho phép mã hoá tín hiệu video với nhiều mức độ phân giải khác nhau, chúng có khả năng đáp ứng cho nhiều ứng dụng khác nhau. Nhiều thuật toán tương ứng với nhiều các ứng dụng khác nhau đã phát triển và được tập hợp lại thành một bộ tiêu chuẩn đầy đủ của MPEG. Việc áp dụng toàn bộ các đặc điểm của chuẩn MPEG-2 trong tất cả các bộ mã hoá và giải mã là không cần thiết do sự phức tạp của thiết bị cũng như sự tốn kém về dải thông của đường truyền Vì vậy trong hầu hết các trường hợp ta chỉ sử dụng một phần nhất định trong toàn bộ các đặc điểm của chuẩn MPEG-2, chúng thường được gọi là profiles và levels. Một profile sẽ xác định một thuật toán (điều chỉnh bitstream và độ phân giải màu) và một level sẽ xác định một số tiêu chí bắt buộc cho các tham số của bức ảnh (ví dụ như kích thứơc ảnh và số lượng bit). 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...) vào năm 1999. Ngày nay, 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. MPEG không phải là một công cụ nén đơn lẻ mà ưu điểm của nén ảnh dùng MPEG chính là ở chỗ MPEG có một tập hợp các công cụ mã hoá chuẩn, chúng có thể được kết hợp vói nhau một cách linh động để phục vụ cho một loạt các ứng dụng khác nhau. Nén MPEG là sự kết hợp hài hoà của bốn kỹ thuật cơ bản: Tiền xử lý (Preprocessing), đoán trước sự chuyển động của các frame ở bộ mã hoá (temporal prediction), bù chuyển động ở bộ giải mã (motion compensation) và mã lượng tử hoá (quatisation coding). Các bộ lọc tiền xử lý sẽ lọc ra những thông tin không cần thiết từ tín hiệu video và những thông tin khó mã hoá nhưng không quan trọng cho sự cảm thụ của mắt người. Kỹ thuật đoán chuyển động dựa trên nguyên tắc là các ảnh trong chuỗi video dường như có liên quan mật thiết với nhau theo thời gian: Mỗi frame tại một thời điểm nhất định sẽ có nhiều khả năng giống với các frame đứng ngay phía trước và ngay phía sau nó. Các bộ mã hoá sẽ tiến hành quét lần lượt từng phần nhỏ trong mỗi frame gọi là macro blocks, sau đó nó sẽ phát hiện macro block nào không thay đổi từ frame này tới frame khác. Bộ mã hoá sẽ tiên đoán trước sự xuất hiện của các macro blocks khi biết vị trí và hướng chuyển động của nó. Do đó chỉ những sự thay đổi giữa các khối trong frame hiện tại (motion compesated residual) và các khối được tiên đoán mới được truyền tới bên phía thu. Phía bên thu tức bộ giải mã đã lưu trữ sẵn những thông tin mà không thay đổi từ frame này tới frame khác trong bộ nhớ đệm của nó và chúng được dùng để điền thêm một cách đều đặn vào các vị trí trống trong ảnh được khôi phục. Như chúng ta đều biết, nén tín hiệu video được thực hiện nhờ việc loại bỏ cả sự dư thừa về không gian (spatial coding) và thời gian (temporal coding). Trong MPEG, việc loại bỏ dư thừa về thời gian (nén liên ảnh) được thực hiện trước hết nhờ sử dụng các tính chất giống nhau giữa các ảnh liên tiếp (Inter-frame techniques). Chúng ta có thể sử dụng tính chất này để tạo ra các bức ảnh mới nhờ vào những thông tin từ những ảnh đã gửi trước nó (“predicted”). Do vậy ở phía bộ mã hoá, ta chỉ cần gửi những bức ảnh có thay đổi so với những ảnh trước, sau đó ta lại dùng phương pháp nén về không gian để loại bỏ sự dư thừa về không gian trong chính bức ảnh sai khác này. Nén về không gian dựa trên nguyên tắc là phát hiện sự giống nhau của các điểm ảnh (pixels) lân cận nhau (Intra-frame coding techniques). JPEG chỉ áp dụng phương pháp nén theo không gian vì nó được thiết kế để xử lý và truyền các ảnh tĩnh. Tuy nhiên nén tín hiệu theo phương pháp của JPEG cũng có thể được dùng để nén các bức ảnh một cách độc lập trong dãy tín hiệu video. ứng dụng này thường được gọi là JPEG động (Motion JPEG). Trong một chu kỳ gửi một dãy các bức ảnh theo kiểu JPEG động, ảnh đầu tiên được nén nhờ sự loại bỏ độ dư thừa về không gian, sau đó các ảnh tiếp theo được nén nhờ sự loại bỏ độ dư thừa về thời gian (nén liên ảnh). Quá trình được lặp đi lặp lại cho một dãy các bức ảnh trong tín hiệu video. Thuật toán nén MPEG cũng dựa trên phép biến đổi DCT cho các khối ảnh 8x8 picxels để tìm ra sự thừa về không gian một cách có hiệu quả giữa các điểm ảnh trong cùng một bức ảnh. Tuy nhiên, trong trường hợp có mối tương quan chặt chẽ giữa các điểm ảnh trong các bức ảnh kế tiếp nhau tức là trong trường hợp hai bức ảnh liên tiếp có nội dung trùng nhau, kỹ thuật Inter-frame coding techniques sẽ được dùng cùng với việc tiên đoán sự dư thừa về không gian để tạo thành kỹ thuật tiên đoán bù chuyển động giữa các bức ảnh (Motion compesated prediction between frames). Trong nhiều sơ đồ nén MPEG, người ta thường kết hợp cả việc tiên đoán bù chuyển động theo thời gian và phép biến đổi thông tin theo không gian để đạt hiệu quả nén cao (Hybrid DPCM/DCT coding of video). Hầu hết các sơ đồ nén MPEG đều dùng kỹ thuật lấy mẫu bổ xung (Subsampling) và lượng tử hoá (Quantization) trước khi mã hoá. Lấy mẫu bổ xung nhằm mục đích để làm giảm kích thước bức ảnh đầu vào theo cả theo chiều ngang và chiều dọc, như vậy sẽ giảm số lượng các điểm ảnh trước mã hoá. Cũng nên nhớ rằng trong một số trường hợp người ta còn lấy mẫu bổ xung theo thời gian để làm giảm số lượng các bức ảnh trong dãy ảnh trước khi mã hoá. Đây được xem như là một kỹ thuật rất cơ bản nhằm loại bỏ sự dư thừa dựa vào khả năng lưu ảnh của mắt người cảm thụ. Thường thường, chúng ta có thể phân biệt sự thay đổi về độ sáng của ảnh (changes in Brightness) tốt hơn so với sự thay đổi về màu (Chromaticity changes). Do đó trước hết các sơ đồ nén MPEG sẽ tiến hành chia bức ảnh thành các thành phần Y (Luminance hay brightness plane) và UV (Chrominance hay color planes) tức là một thành phần về độ sáng và hai thành phần về độ màu. Các tín hiệu video thành phần này sẽ được lấy mẫu (samples) và số hoá (digitised) để tạo nên các điểm ảnh rời rạc theo tỷ lệ 4 : 2 : 2 và 4 : 2 : 0. Kỹ thuật tiên đoán bù chuyển động được sử dụng như là một trong những công cụ mạnh để làm giảm sự dư thừa về không gian giữa các bức ảnh. Khái niệm về bù chuyển động là dựa trên sự phán đoán hướng chuyển động của các bức ảnh tức là các ảnh thành phần trong dãy video sẽ được thay thế gần đúng. Kỹ thuật tiên đoán bù chuyển động giữa các bức ảnh được xem như là biện pháp để hạn chế bớt các thông số của chuyển động bởi việc dùng các vector chuyển động để mô tả sự dịch chuyển của các điểm ảnh. Kết quả tiên đoán tốt nhất của một điểm ảnh là dựa trên sự tiên đoán bù chuyển động từ một bức ảnh đã mã hoá được truyền phía trước của nó. Cả hai thông số, sai số chuyển động (biên độ) và các vectors chuyển động (hướng chuyển động) đều được truyền tới phía bên nhận. Tuy nhiên do có mối quan hệ tương quan chặt chẽ giữa các điểm ảnh về không gian (trùng về không gian), một vector chuyển động có thể được dùng cho một khối các điểm ảnh gồm các pixels lân cận nhau (MPEG -1 và MPEG -2 dùng các khối 16 x16 pixels). Trong MPEG-2, có nhiều phương pháp để tiên đoán sự chuyển động. Ví dụ một khối ảnh có thể được tiên đoán xuôi từ những ảnh đã được truyền trước nó (Forward Predicted), có thể đoán ngược từ những ảnh truyền sau nó (Backward Predicted) hoặc theo cả hai chiều (Bidirectionally Predicted). Các phương pháp dùng để tiên đoán các khối trong cùng một ảnh cũng có thể không giống nhau, chúng có thể thay đổi từ khối nọ sang khối kia. Hơn nữa, hai trường (fields) trong cùng một khối cũng có thể được tiên đoán theo hai cách khác nhau dùng các vector độc lập nhau hoặc chúng có thể dùng chung một vector. Đối với mỗi khối ảnh, bộ mã hoá sẽ chọn các phương pháp tiên đoán thích hợp, cố gắng đảm bảo chất lượng ảnh tốt nhất khi được giải mã trong điều kiện yêu cầu khắt khe về số bit. Các thông số liên quan tới chọn phương pháp tiên đoán cũng được truyền tới bộ giải mã cùng với dự đoán sai số nhằm khôi phục gần chính xác ảnh gốc. Trong MPEG, có 3 kiểu ảnh khác nhau được dùng để mã hoá cho các khối ảnh. Kiểu ảnh ‘Intra’ (I-pictures) là ảnh được mã hoá một cách độc lập mà không cần tham khảo tới các ảnh khác. Hiệu quả nén tín hiệu đạt được do loại bỏ sự thừa về không gian mà không có yếu tố thời gian tham gia vào quá trình. I-pictures được dùng một cách tuần hoàn để tạo thành các điểm tựa cho dòng dữ liệu trong quá trình giải mã. Ảnh ‘Predictive’ (P-pictures) có thể sử dụng các ảnh I hoặc P ngay sát phía trước nó để bù chuyển động và chính nó cũng có thể được dùng để tham khảo cho việc tiên đoán các ảnh khác tiếp theo. Mỗi khối ảnh trong P-picture có thể hoặc được mã theo kiểu tiên đoán (predicted) hoặc được mã một cách độc lập (intra-coded). Do sử dụng cả nén theo không gian và thời gian, hiệu quả nén của P-pictures được tăng lên một cách đáng kể so với I-pictures. Ảnh ‘Bidirectionally-Predictive’ pictures hay B- Pictures có thể sử dụng các ảnh I hoặc P phía trước hoặc phía sau nó cho việc bù chuyển động và do vậy cho kết quả nén cao nhất. Mỗi khối trong B-pictures có thể được tiên đoán theo chiều ngược, xuôi, cả hai hướng hoặc được mã một cách độc lập. Để có thể tiên đoán ngược từ một bức ảnh phía sau nó, bộ mã hoá sẽ tiến hành sắp xếp lại các bức ảnh từ thứ tự xuất hiện một cách tự nhiên sang một thứ tự khác của các ảnh trên đường truyền. Do vậy từ đầu ra của bộ mã hoá, B-pictures được truyền sau các ảnh dùng để tham khảo ở phía trước và phía sau của nó. Điều này sẽ tạo ra độ trễ do phải sắp xếp lại thông tin, độ trễ này lớn hay nhỏ là tuỳ thuộc vào số các bức ảnh B-pictures liên tiếp nhau được truyền. Các ảnh I, P, B-pictures thường xuất hiện theo một thứ tự lặp đi lặp lại một cách tuần hoàn, do đó ta có khái niệm về nhóm các bức ảnh GOP (Group of Pictures). Một ví dụ của GOP ở dạng ảnh tự nhiên xuất hiện theo thứ tự như sau: B1 B2 I3 B4 B5 B7 B8 P9 B10 B11 P12 Thứ tự xuất hiện của chúng trên đường truyền bị thay đổi do sự sắp xếp lại của bộ mã hoá như sau: I3 B1 B2 P6 B4 B5 P9 B7 B8 P12 B10 B11 Cấu trúc của một GOP có thể được mô tả bởi hai tham số: N là số các ảnh trong GOP và M là khoảng cách giữa các ảnh P-pictures. Nhóm GOP này được miêu tả như N = 12 và M = 3. SƠ ĐỒ CỦA BỘ MÃ HOÁ VÀ GIẢI MÃ DÙNG MPEG-2 Hình 1. Sơ đồ bộ mã hoá và giải mã dùng MPEG Mã hoá MPEG-2 Quá trình mã hoá cho P pictures và B pictures được giải thích như sau: Dữ liệu từ các khối ảnh (macroblocks) cần được mã hoá sẽ được đưa đến cả bộ trừ (Subtractor) và bộ đoán chuyển động (Motion Estimator). Bộ đoán chuyển động sẽ so sánh các khối ảnh mới được đưa vào này với các khối ảnh đã được đưa vào trước đó và được lưu lại như là các ảnh dùng để tham khảo (Reference Picture). Kết quả là bộ đoán chuyển động sẽ tìm ra các khối ảnh trong ảnh tham khảo gần giống nhất với khối ảnh mới này. Bộ đoán chuyển động sau đó sẽ tính toán vector chuyển động (Motion Vector), vector này sẽ đặc trưng cho sự dịch chuyển theo cả hai chiều dọc và ngang của khối ảnh mới cần mã hoá so với ảnh tham khảo. Chúng ta lưu ý rằng vector chuyển động có độ phân giải bằng một nửa do thực hiện quét xen kẽ. Bộ đoán chuyển động cũng đồng thời gửi các khối ảnh tham khảo này mà chúng thường được gọi là các khối tiên đoán (Predicted macroblock) tới bộ trừ để trừ với khối ảnh mới cần mã hoá (thực hiện trừ từng điểm ảnh tương ứng tức là Pixel by pixel). Kết quả là ta sẽ được các sai số tiên đoán (Error Prediction) hoặc tín hiệu dư, chúng sẽ đặc trưng cho sự sai khác giữa khối ảnh cần tiên đoán và khối ảnh thực tế cần mã hoá. Tín hiệu dư hay sai số tiên đoán này sẽ được biến đổi DCT, các hệ số nhận được sau biến đổi DCT sẽ được lượng tử hoá để làm giảm số lượng các bits cần truyền. Các hệ số này sẽ được đưa tới bộ mã hoá Huffman, tại đây số bits đặc trưng cho các hệ số tiếp tục được làm giảm đi một cách đáng kể. Dữ liệu từ đầu ra của mã hoá Huffman sẽ được kết hợp với vector chuyển động và các thông tin khác (thông tin về I, P, B pictures) để gửi tới bộ giải mã. Đối với trường hợp P-pictures, các hệ số DCT cũng được đưa đến bộ giải mã nội bộ (nằm ngay trong bộ mã hoá). Tín hiệu dư hay sai số tiên đoán được biến đổi ngược lại dùng phép biến đổi IDCT và được cộng thêm vào ảnh đứng trước để tạo nên ảnh tham khảo (ảnh tiên đoán). Vì dữ liệu ảnh trong bộ mã hoá được giải mã luôn nhờ vào bộ giải mã nội bộ ngay chính bên trong bộ mã hoá, do đó ta có thể thực hiện thay đổi thứ tự các bức ảnh và dùng các phương pháp tiên đoán như đã trình bày ở trên. Giải mã MPEG-2 Quá trình khôi phục lại ảnh tại bộ giải mã là hoàn toàn ngược lại. Từ luồng dữ liệu nhận được ở đầu vào, vector chuyển động được tách ra và đưa vào bộ bù chuyển động (Motion Compensator), các hệ số DCT được đưa vào bộ biến đổi ngược IDCT để biến tín hiệu từ miền tần số thành tín hiệu ở miền không gian. Đối với P pictures và B pictures, vector chuyển động sẽ được kết hợp với các khối tiên đoán (predicted macroblock) để tạo thành các ảnh tham khảo. Phương pháp nén âm thanh Mục đích:   Biểu diễn chuỗi số ngắn gọn. Tốc độ bit thấp. Chất lượng cao Động cơ: Giảm tốc độ dữ liệu. Giảm chi phí truyền dẫn (BW). Giảm các yêu cầu lưu trữ. Các yêu cầu: Cảm nhận trong suốt. Độc lập nguồn. Có khả năng đa kênh. Độ trễ hợp lý. Kỹ thuật nén MPEG1: MPEG-1 Lớp I Lớp II Lớp III Mono và Stereo 32, 44.1, 48kHz Hình 2. Phân lớp mã hóa MPEG 1 Giới thiệu Được phát triển trên cơ sở phối hợp chuẩn ISO/IEC 11172. Sử dụng tần số lấy mẫu của CD-DA, với fs=32;44.1;48kHz, mã hoá 16bits/mẫu tín hiệu. Tốc độ bít: 32 - 768 kbps/channel. Các kiểu: Mono, dual-mono, dual-stereo, joint-stereo. Xác định các tham số khác nhau về tốc độ, dòng số sau khi nén, số mẫu trong header cho một kênh, cấu trúc thời gian khung, phương pháp mã hoá dự đoán và các chế độ làm việc. Đặc tính: Lớp I Lớp II Lớp III Dùng cho thiết bị dân dụng Dùng cho thiết bị chuyên dụng, đa môi trường Dùng cho thiết bị chuyên dụng, đa môi trường Tốc độ dòng số liệu từ 32-448kbps Tốc độ dòng số liệu từ 32-384kbps Tốc độ dòng số liệu từ 32-320kbps 384mẫu/khung/kênh 1152mẫu/khung/kênh 1152mẫu/khung/kênh 32 băng con đều nhau, mỗi băng con gồm block 12 mẫu 32 băng con đều nhau, mỗi băng con gồm block 36 mẫu 32 băng con tới hạnthành 18 MDCT Chu kỳ một khung 8ms cho kênh có fs=48kHz Chu kỳ một khung 24ms cho kênh có fs=48kHz Chu kỳ một khung 24ms cho kênh có fs=48kHz Hệ số tỷ lệ 6 bits/băng, phân phối bit theo phương thức ứng trước. Hệ số tỷ lệ 6 bits/băng, phân phối bit theo phương thức ứng trước. Hệ số tỷ lệ 6 bits/băng, phân phối bit theo phương thức ứng trước. Lọc băng con 0 Lọc băng con 1 Lọc băng con 31 Lọc băng con 2 … Các mẫu Audio ngõ vào 12 mẫu 12 mẫu 12 mẫu 12 mẫu 12 mẫu 12 mẫu 12 mẫu 12 mẫu 12 mẫu 12 mẫu 12 mẫu 12 mẫu Khung lớp I Khung lớp II và lớp III Hình 3. Các mẫu Audio Khung lớp I : 12x32 =384. Khung lớp II, III: 12x32x3=1152. Kiến trúc: Băng lọc phân tích đa pha 32 kênh Lýợng tử hoá Mã hoá MU X FFT LI: 512 LII: 1024 Phân tích tâm sinh lý âm học Phân phối bit động 32 Dữ liệu Thông tin thêm 32 s(n) Băng lọc phân tích đa pha 32 kênh MDCT MUX FFT Phân tích tâm sinh lý âm học SMR 32 s(n) kênh Vòng lặp chỉ định bit Lýợng tử hoá Mã hoá Huffman Mã thông tin thêm ¯32 MPEG1 lớp1,2 MPEG1 lớp3 SMR (Signal Mark Rate): Tỷ số tín hiệu/ngưỡng che Hình 4. Kiến trúc 3 lớp của MPEG-1 Thuật toán cơ bản Tiến hành chia ngõ vào thành 32 băng con bởi các băng lọc. Lấy 32 mẫu PCM trong cùng một thời điểm, kết quả là 32 hệ số tần số ở ngõ ra. Trong MPEG-1 lớp I thì tập 32 giá trị PCM được kết hợp vào trong khối gồm 12 nhóm 32 mẫu này. MPEG-1 lớp II và lớp III thì gồm 3 khối 12 nhóm này. Phân bố bit đảm bảo rằng mọi nhiễu lượng tử nằm ở dưới các ngưỡng che. Với mỗi băng con, xác định mức biên độ và mức nhiễu bằng mô hình tâm sinh lý nghe. SMR (signal-mask rate) được sử dụng để xác định số bit cho quá trình lượng tử hoá đối với mỗi băng con với mục đích giảm thiểu dung lượng. Phân phối bit Là thủ tục xác định số bit cho mỗi băng con. Dựa vào thông tin vào từ mô hình tâm sinh lý nghe Ví dụ: Sau khi phân tích, mức của 16 băng con đầu là: Band 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Level (db) 0 8 12 10 6 2 10 60 35 20 15 2 3 5 3 1 Nếu mức của băng con thứ 8 là 60 thì nó che 12 dB ở băng con thứ 7 và 15 dB ở băng con thứ 9. Băng con 7 có mức 10dB15dB: gởi đi. Chỉ có các mức lớn hơn mức che là được gởi đi thay vì dùng 6 bits để mã hoá, ta chỉ dùng 4 bits. MPEG-Layer I: Bộ lọc DCT 1 khung và tần số bằng phẳng trong mỗi băng con. Mô hình tâm sinh lý nghe sử dụng che tần số. MPEG-Layer II: Có 3 khung trong bộ lọc (trước, hiện tại và kế), tổng là 1125 mẫu. Sử dụng vài bits để che thời gian. MPEG-Layer III: Sử dụng bộ lọc tới hạn để đáp ứng tốt hơn. Mô hình tâm sinh lý nghe sử dụng che thời gian, che tần số, tính toán độ dư thừa stereo và mã hoá Huffman. Cấu trúc khung: Hình 5. Cấu trúc khung MPEG Header: Gồm 12 bits đồng bộ; 20 bis thông tin hệ thống chỉ thị tốc độ bit CRC với đa thức sinh x16+x15+x2+1. Side Info: Gồm phân bố bit: lớp 1 với 4 bits tuyến tính cho các băng con, lớp II 4 bits cho các băng con tần thấp, 3 bit tần trung và 2 bits tần cao; hệ số tỷ lệ là 6 bits/băng con kết hợp với phân bố bits và các bits mã hóa cho băng con đó để xác định giá trị, lớp III mã hóa âm thanh nổi. Bit Reservoir: Bit cung cấp, các mẫu dữ liệu từ 1 hoặc 2 khung trước. Samples: 32x12 mẫu đối với lớp I và 32x36 mẫu đối với lớp II và lớp III. Ancillary Data: Dữ liệu bổ sung Kỹ thuật nén MPEG2: Mở rộng MPEG-1 cho các ứng dụng mới. Có khả năng áp dụng nhiều tốc độ khác nhau, từ 32 đến 1066kbps. Tần số lấy mẫu có thể giảm 1 nửa so với MPEG-1 (16; 22,05; 24kHz). Khả năng đa kênh, tốc độ bits mở rộng có thể lên đến 1 Mbps cho các ứng dụng tốc độ cao. Cho phép nén đồng thời nhiều kênh. Chất lượng âm thanh tuỳ thuộc ứng dụng. Hỗ trợ khả năng lồng tiếng, bình luận nhiều ngôn ngữ trong phần bits mở rộng (7 kênh). MPEG-2 sử dụng mã hoá cường độ cao, giảm xuyên âm, mã hoá dự đoán liên kênh và mã hoá ảo ảnh kênh trung tâm để nhận được tốc độ bit kết hợp 384 kbps. Khung MPEG-2 được chia thành 2 phần, phần đầu là MPEG-1stereo, phần mở rộng MPEG-2 chứa tất cả những dữ liệu surround khác. Mono-stereo MPEG-1 32;44.1;48kHz MPEG-2 Layer I Layer II Layer III Mono-stereo MPEG-2 16;22,05;24kHz Layer I Layer II Layer III 5 channels MPEG-2 multi channel 32;44.1;48kHz Layer I Layer II Layer III Hình 6. Cấu trúc khung MPEG 2 Mã hóa và giải mã MPEG2: Matrix MPEG-1 encoder MPEG-2 Extension encoder L C R LS RS L0 R0 T3 T4 T5 + MPEG-1 decoder MPEG-2 Extension decoder L0’ R0’ T3’ T4’ T5’ Inverse Matrix L’ C’ R’ LS’ RS’ channel Hình 7. Sơ đồ mã hóa và giải mã MPEG 2 CHƯƠNG 3 XÂY DỰNG CHƯƠNG TRÌNH NÉN DỮ LIỆU BẰNG MÃ SHANNON-FANO VÀ HUFFMAN ĐẶC ĐIỂM CỦA CÁC THUẬT TOÁN NÉN DỮ LIỆU Trong giới hạn tìm hiểu nén dữ liệu dưới dạng một tập tin em nhận thấy các phương pháp nén được dùng phổ biến trên có những đặc điểm đáng chú ý: thuật toán nén độ dài loạt (Runlength) không thể áp dụng cho nhiều loại tập tin được, ví dụ như tập tin chương trình, tập tin cơ sở dữ liệu... vì ở đó các loạt chạy là rất ngắn, do đó nếu áp dụng thuật toán này không những không làm bé tập tin mà còn làm phình to chúng. Thuật toán nén LZW có các ưu điểm là hệ số nén tương đối cao, trong tập tin nén không cần phải chứa bảng mã. Nhược điểm của thuật toán này là tốn nhiều bộ nhớ, khó thực hiện dựa trên các mảng đơn giản (bé hơn 64KB). Các thuật toán khác như Huffman, Shannon-Fano, LZ77 và LZW… đều có thể áp dụng được để nén nhiều loại tập tin trên các máy vi tính. Thuật toán Shannon-Fano có hệ số nén tương đối tốt với các file dạng text nhưng do đặc tính của thuật toán và yêu cầu khá phức tạp nên hiếm khi được sử dụng. Thuật toán Huffman có ưu điểm là hệ số nén tương đối cao, phương pháp thực hiện tương đối đơn giản, đòi hỏi ít bộ nhớ, có thể xây dựng dựa trên các mảng bé hơn 64KB. Thường được sử dụng trong các công đoạn cuối cuản nén âm thanh, hình ảnh và video. Từ các đặc tính thuật toán của các loại mã nén trên, em nhận thấy rằng thuật toán mã hóa của Shannon-Fano và Huffman có nét tương đồng. Tuy nhiên sự khác nhau về thuật toán làm cho hiệu suất nén (hệ số entropy) của Huffman và Shannon-Fano khác nhau. Do vậy, em sẽ tập trung nghiên cứu, xây dựng mô phỏng và đánh giá 2 loại mã nén này để làm rõ ưu và nhược của 2 loại mã nén trên. PHÂN TÍCH THUẬT TOÁN Thuật toán Shannon-Fano: Mã Shannon-Fano là một thuật toán mã hóa dùng để nén dữ liệu. Nó dựa trên bảng tần suất xuất hiện các kí tự cần mã hóa để xây dựng một bộ mã nhị phân cho các kí tự đó sao cho dung lượng (số bít) sau khi mã hóa là nhỏ nhất. 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 bits. 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: "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:0000100010100100000100011000010010000001000101001000001Ðể 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 ? - Bước đầu tiên trong việc xây dựng mã Shannon-Fano là đếm số lần xuất hiện của mỗi kí tự trong tập tin sẽ được mã hoá (trong phần này chỉ ví dụ hạn chế một số ký tự). - Bước tiếp theo là xây dựng bảng mã dựa vào thuật toán Shannon-Fano. Thuật toán này được thực hiện bằng các bước sau: Bước 1: Sắp xếp thứ tự các lớp tin tăng (hay giảm), nguồn tin được thống kê từ tập tin cần thực hiện mã hóa. Bước 2: Chia tổng nguồn tin ra làm 2 nhóm sao cho tổng của mỗi nhóm xấp xỉ bằng nhau (hiệu của 2 nhóm là nhỏ nhất). Bước 3: Gán cho mỗi nhóm ký hiệu là 0 hay 1. Bước 4: Lặp lại bước 2 cho đến khi chỉ còn lại 1 nhóm tin. Sau khi có bảng mã Shannon-Fano, ta có thể mã hóa các gói tin. Ưu điểm của phương pháp mã hoá Shannon-Fano là đạt được hệ số nén tương đối cao (Hệ số nén tuỳ thuộc vào cấu trúc của các tập tin). Nhược điểm của phương pháp này là 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. Để giải mã gói tin, như đã nói ở trên ta phải có bảng mã. Lần lượt ta so sánh từng nhóm tin, nếu trùng với bảng mã thì ta có được gói tin như ban đầu. Chương trình mã hóa nguồn dùng mã Shannon-Fano là chương trình dùng thuật toán Shannon-Fano (có trong lý thuyết truyền tin hay kỹ thuật truyền số liệu) để giải quyết bài toán mã hóa theo xác suất xuất hiện của các ký tự có trong bảng mã ASCII. Sau đó, dựa vào bảng mã này ta có thể mã hóa các chuỗi ký tự hay dòng văn bản ra thành mã máy tính gồm các ký tự 0 và 1. Các ký tự được mã hóa sẽ có độ dài khác nhau, tuy nhiên xét về tổng thể thì độ dài của chuỗi hay của văn bản đã được mã hóa sẽ ngắn hơn khi ta chưa mã hóa. Như vậy, khi lưu trữ sẽ ít tốn bộ nhớ hơn cũng như khi truyền tin sẽ chiếm ít băng thông hơn. Các chức năng của hệ thống/chương trình : Tổng thể cấu trúc của chương trình lần lượt sẽ thực hiện như sau : Khai báo các hằng, biến toàn cục, các cấu trúc sẽ thực hiện trong suốt chương trình. typedef struct Node { char kytu; float xacsuat; char code[32]; }; Node a[256]; // bảng mã ASCII gồm 256 ký tự, biến a chứa mảng các ký tự trong bảng mã, là biến toàn cục. Khai báo các chương trình con hay cấu trúc của các chương trình con : Hàm read: đọc file và thống kê xác suất hiện của nó : Ta tiến hành đọc các ký tự từ file rồi tăng số lần xuất hiện lên, lưu vào trong mảng a. Mảng a là nơi để lưu trữ số lần xuất hiện của ký tự có trong file, vị trí trong mảng a là mã ASCII của ký tự đó. Hàm sapxeptang : Để sắp xếp theo số lần xuất hiện của ký tự trong mảng a theo hướng tăng dần. Hàm mahoa : Hàm này sẽ mã hóa nguồn dùng mã Shannon-Fano các ký tự có số lần xuất hiện lớn hơn 0 trong file. Mỗi ký tự đều có 1 mã bằng nhị phân riêng. Hàm giaima: Giải mã file đã mã hóa theo bảng mã. Hàm insapxep: In các ký tự sau khi đã sắp xếp theo xác suất xuất hiện ra màn hình để tiện theo dõi. Hàm thuchien: Đây là hàm làm công việc chính của chương trình. Hàm này sẽ thực hiện công việc mã hóa file rồi lưu vào file khác mã của chương trình nén. Hàm main: chứa các thông tin cần thiết của đề tài và thực hiện gọi các chương trình con. Ví dụ : cho nguồn tin gồm 10 lớp tin như sau : X A B C H N U G O M I Px 0.20 0.11 0.08 0.10 0.07 0.09 0.13 0.06 0.12 0.04 Hàm sắp xếp : Hàm này sẽ tiến hành sắp xếp lại các ký tự theo xác suất xuất hiện đã có ở trên theo thứ tự giảm dần nhằm phục cho quá trình mã hóa các ký tự này theo thuật toán Shannon-Fano. X A G M B H U C N O I Px 0.20 0.13 0.12 0.11 0.10 0.09 0.08 0.07 0.06 0.04 Hàm mã hóa : Hàm này có nhiệm vụ tối quan trọng đối với bài toán này. Hàm sẽ mã hóa các ký tự đã nhập hay cho trước sao cho các mã này không được trùng nhau. Các bước thực hiện như sau : Bước 1 : Dựa vào thứ tự đã sắp xếp ở trên chia mảng a ra làm 2 phần. Điều kiện là hiệu của tổng các xác suất có trong từng phần sẽ là nhỏ nhất. Bước 2 : Gán cho mỗi ký tự của nhóm đầu giá trị 0 vào trong phần code của nó (ký tự) và nhóm thứ 2 giá trị 1. Bước 3 : Làm lại bước 1 với nhóm thứ nhất sau đó là với nhóm thứ 2. Điều kiện để dừng là không thể chia nhỏ được nữa (mảng chỉ còn 1 phần tử). Như vậy, sau khi hoàn tất các bước trên, ta có được 1 bảng mã với các chữ cái được gắn với một mã tương ứng nhất định, các mã này sẽ không trùng nhau. Ví dụ : Bảng mã sau khi được mã hóa : X A G M B H U C N O I Px 0.20 0.13 0.12 0.11 0.10 0.09 0.08 0.07 0.06 0.04 Code 00 010 011 100 1010 1011 1100 1101 1110 1111 Trình tự cách phân chia như sau : X Px Code A 0.20 0 0 G 0.13 0 1 0 M 0.12 0 1 1 B 0.11 1 0 0 H 0.10 1 0 1 0 U 0.09 1 0 1 1 C 0.08 1 1 0 0 N 0.07 1 1 0 1 O 0.06 1 1 1 0 I 0.04 1 1 1 1 Hàm giải mã : Hàm này sẽ dựa vào bảng mã ở trên để giải mã một chuỗi gồm các ký tự 0 và 1. Hàm có kiểm tra xem có phải dữ liệu nhập vào có đúng như yêu cầu không và các ký tự đó phải có trong bảng mã đã thống kê ở trên. Trình tự các bước như sau : Bước 1 : Kiểm tra xem ký tự đầu tiên có trong bảng mã hay không. Nếu có thì lưu vào trong mảng d và tiếp tục làm bước 1 nhưng vị trí đầu tiên là vị trí kế tiếp (chưa kiểm tra) , nếu không có thì tiếp tục bước 2. Bước 2 : Kiểm tra cặp ký tự đầu tiên và ký tự thứ 2 xem có trong bảng mã hay không. Nếu có thì lưu vào trong mảng d, và quay lại bước 1 với ký tự đầu tiên là ký tự kế tiếp, nếu không có thì làm lại bước 2 với 3, 4,…,n (số phần tử của chuỗi nhập vào) vị trí kế tiếp. Bước 3 : Kiểm tra xem nếu kiểm tra đến phần tử cuối cùng mà không thấy trùng với phần tử nào trong bảng mã thì phát thông báo “ Dữ liệu nhập vào bị lỗi”. Làm đến khi không còn phần tử nào trong mảng thì dừng. Bước 4 : in các ký tự vừa được giải mã hoặc thông báo lỗi lên màn hình. Hàm main : Hàm này hiển thị thông tin người thực hiện đề tài…. Các lựa chọn mã hóa file hay giải mã. Hiện lên màn hình thông báo để người sử dụng biết đã thực hiện mã hóa hay giải mã xong chưa, file mã hóa hay giải mã được lưu ở đâu. Thuật toán Huffman: Thành lập cây nhị phân từ tập hợp các kí hiệu trong thông báo, mỗi kí hiệu là một nút lá của cây. Cách thành lập cây như sau : Chọn hai nút a,b có xác suất nhỏ nhất trong tập hợp các nút, giả sử xác suất nút a nhỏ hơn hoặc bằng xác suất nút b. Thành lập cây nhị phân có nút gốc x, con trái là a, con phải là b. Nút x có xác suất bằng tổng xác suất của a và b. Tập hợp các nút bây giờ là các nút còn lại (đã loại bỏ a, và nút x. Lặp lại một cách đệ qui quá trình trên tập hợp đang xét cho đến khi tập này chỉ còn lại một nút. Mã của a, b sẽ tìm được bằng cách lấy mã của x nối thêm 0 cho a và 1 cho b. Mã của nút gốc là rỗng. Như vậy thực chất quá trình trên là ta xây dựng một cây nhị phân từ tập hợp các ký tự muốn mã hoá, cuối cùng ta được một cây nhị phân có lá là các ký tự đó. Mã của một ký tự là một đường đi trên cây từ gốc đến lá chứa kí tự, với 0 đi sang trái còn 1 đi sang phải. Ý tưởng của giải thuật mã hoá cũng hết sức đơn giản, ta tìm bộ mã cho các kí tự sao cho các kí tự có tần suất xuất hiện cao (xác suất xuất hiện là lớn) sẽ được mã ngắn (gần với gốc) để độ dài trung bình để mã hoá một kí tự là nhỏ nhất. Ví dụ: Cho bảng tần suất của 5 chữ cái A,B,C,D,E như sau tương ứng là 0.10; 0.15; 0.30; 0.16; 0.29. A B C D E 0.10 0.15 0.30 0.16 0.29 Quá trình xây dựng cây Huffman diễn ra như sau: Hình 8. Bước 1 và Bước 2 Hình 9. Bước 3 và Bước 4 Hình 10. Bước 5 Như vậy bộ mã tối ưu tương ứng là: A B C D E 010 011 11 00 10 - Đọc file văn bản, lưu vào mảng a. - Xây dựng cây Huffman để giải mã dòng văn bản - Hiển thị cây Huffman và bảng mã Huffman ra màn hình - Thực hiện mã hóa dòng văn bản và dải mã - Mở rộng mã hóa và giải mã một file văn bản. Kết quả giải mã và mã hóa được ghi vào 2 file văn bản khác. Cấu trúc chương trình: - File huffman.cpp dùng để cài đặt cây huffman. Nó bao gồm các hàm: - mahoa_chuoi(): Mã hóa chuỗi. - giaima_chuoi(): Giải mã chuỗi. - general(): Cài đặt cây Huffman, được sử dụng trong các hàm trên. - make_table(): Tạo bảng mã cho các ký tự, được sử dụng trong các hàm mã hóa. - quit(): Các thao tác cuối cùng trước khi return. Các vấn đề chung trong xây dựng chương trình: Các cấu trúc dữ liệu sử dụng trong chương trình: Code:typedef struct { char kytu; int tansuat; char code[MAXBITS]; }hlist;  - Kiểu dữ liệu của mảng a[] chứa tập ký tự (a[i].kytu), tần số tương ứng a[i].tansuat) và chuỗi mã hóa ký tự đó (a[i].code) Code: typedef struct{ char kytu; int contrai,conphai,nutcha; int tansuat; int isleft; }hnode;- Kiểu dữ liệu của mảng node[] dùng để cài đặt cây Huffman. Các node tương ứng với ký tự (node[i].kytu nếu có). Node.contrai, node.conphai, node.nutcha tương ứng là chỉ số của nút con trái, con phải, và nút cha (Nếu không có thì có giá trị là -1). Node.tansuat chứa tổng tần số các nút lá thuộc nhánh của nó. Node.isleft bằng 1 nếu nút đó là con trái của cha nó, bằng 0 nếu là con phải, bằng -1 nếu là nút gốc (goc). Cài đặt cây Huffman từ tập ký tự đọc từ file: - Thủ tục general() - Sắp xếp lại các a[i] - Khởi tạo các node[i] (i=0 đến n-1), node[i].kytu và node[i].tansuat tương ứng với a[i].kytu và a[i].tansuat sau khi đã sắp xếp. Các thành phần còn lại có giá trị là –1 (chưa xác định). - Tạo cây Huffman bằng cách chèn thêm nút mới đồng thời sắp xếp lại theo thứ tự tần số tăng dần. Các vấn đề khác cần giải quyết: 1. Lập bộ ký tự (a[i].kytu) và tần số tương ứng (a[i].tansuat) từ một xâu ký tự (s):- Đọc ký tự đầu tiên của xâu cho vào a[0].kytu tương ứng là a[0].tansuat bằng 1.- Duyệt từng ký tự còn lại của xâu, nếu gặp ký tự nào đã có trong mảng a[i].kytu thì tăng a[i].tansuat lên 1, nếu chưa có ký tự đó thì thêm phần tử mới vào mảng và cho tần số tương ứng bằng 1. 2. Lập tập ký tự trong file text và tần số tương ứng: (Tương tự với xâu ký tự) 3. Xây dựng bảng mã Huffman (lưu trong a[i].code): Thủ tục make_table() - Duyệt tất cả các node[i] (i từ 0 tới 2*n-2) - Nếu gặp node nào có chứa ký tự (node[i].kytu khác NULL) thì duyệt lên tới root để được xâu mã hóa (a[i].code) viết theo chiều ngược lại. - Đảo ngược a[i].code bằng hàm strrev(), ta được xâu mã hóa của ký tự tương ứng. 4. Mã hóa: - Đọc từng ký tự của chuỗi (hoặc file), gặp phần tử nào thì hiển thị xâu mã hóa tương ứng hoặc ghi thêm xâu mã hóa tương ứng của ký tự đó vào file đã mã hóa (fileout). 5. Giải mã: - Goc trỏ vào node gốc (goc=2*n-2) - Duyệt cây Huffman từ trên xuống, gặp 0 thì nhảy xuống con trái, gặp 1 thì nhảy xuống con phải, cho tới khi gặp node có thành phần kytu khác -1. - Nếu gặp node có thành phần kytu khác -1 thì hiển thị ký tự của node đó và nhảy về gốc (goc=2*n-2). Lưu đồ thuật toán : Lưu đồ chương trình mô phỏng thuật toán Shannon-Fano: Begin Lưu đồ thuật toán hàm main: Giới thiệu đề tài File lỗi Nhập tên file cần mã hóa File tốt Gọi hàm “read” để đọc dữ liệu trong file và thống kê nguồn tin Gọi hàm “sapxeptang” để sắp xếp nguồn tin theo tần suất xuất hiện. Gọi hàm “insapxep” để mã hóa nguồn tin và in bảng mã ra màn hình End Gọi hàm “thuchien” để thực hiện mã hóa nguồn tin, đưa ra tỉ lệ nén T Lưu đồ thuật toán mã hóa Shannon-Fano. T F F T F T Begin Mảng a (nguồn tin đã thống kê) Phân mảng a ra thành 2 phần (phần đầu từ 0đến i, phần sau từ i+1đến n-1 )với tổng xác suất của mỗi phần có hiệu là nhỏ nhất Gán giá trị 0 vào phần code cho phần đầu và 1 cho phần sau Phần đầu chỉ còn 1 giá trị Phần sau chỉ còn 1 giá trị Cho mảng a chạy từ 0 đến k-1 Cho mảng a chạy từ k đến n-1 Mảng chỉ có 1 ptử Gán giá trị 0 vào phần code cho phần tử đó End II.3.2.3.2 Chương trình mô phỏng thuật toán Huffman: Lưu đồ thuật toán hàm main:Begin Giới thiệu đề tài Nhấn 1 Thực hiện chương trình mã hóa Nhấn 2 F T Thực hiện chương trình giải mã T F Nhấn 3 Không thực hiện chương trình nào Nhấn ESC T F F End T T Lưu đồ thuật toán mã hóa Huffman : Begin Nhập chuỗi lấy từ file Đếm số lần xuất hiện mỗi ký tự trong chuỗi Lưu vào 1 file chứa dữ liệu là ký tự và tần suất xuất hiện tương ứng Sắp xếp các ký tự theo thứ tự tần suất tăng dần (hàm general) Tạo bảng mã các ký tự dùng cây Huffman (hàm make_table) Xuất chuỗi đã được mã hóa End CHƯƠNG 4 KẾT QUẢ THỬ NGHIỆM VÀ NHẬN XÉT II.4.1 KẾT QUẢ MÔ PHỎNG Hình11. màn hình mô phỏng mã Shannon-Fano với ví dụ 1 Hình 12. Thống kê tần suất xuất hiện và bảng mã của Shannon-Fano trong ví dụ 1 Hình 13. Hiển thị tỉ lệ nén của mã Shannon-Fano trong ví dụ 1 Hình 14. Giới thiệu đề tài dùng mã Huffman Hình 15. Menu điều khiển chương trình nén mã Huffman Hình 16. Hiển thị trực quan thông tin nén của mã Huffman trong ví dụ 1 Hình 17. Màn hình giới thiệu nén file vidu7.txt với mã Shannon-Fano Hình 18. Thống kê dữ liệu trong ví dụ 7 Hình 19. Kết quả nén Shannon-Fano với ví dụ 7 Hình 20. Giao diện chương trình nén mã Huffman với ví dụ 7 Hình 21. Thống kê dữ liệu trong ví dụ 7 của mã Huffman Hình 22.Kết quả chương trình nén mã Huffman trong ví dụ 7 II.4.2 CÁC KẾT QUẢ Hình 23. Thống kê tỉ lệ nén Shannon-Fano và Huffman với 10 ví dụ khác nhau II.4.3 NHẬN XÉT VÀ ĐÁNH GIÁ Series1 : Mã Shannon-Fano (cột màu nhạt) Series2 : Mã Huffman (Cột màu đậm) Hình 24. Biểu đồ so sánh tỉ lệ nén của Shannon-Fano và Huffman Ưu điểm, nhược điểm của phương pháp mã hoá Shannon-Fano và Huffman Ưu điểm: Thuật toán nén Shannon-Fano và Huffman là thuật toán nén không tổn hao. Do vậy, dữ liệu sau khi giải nén là nguyên vẹn. Hai thuật toán nén trên đều sử dụng phương pháp nén dữ liệu bằng cách mã hóa các ký tự sao cho số lần xuất hiện của ký tự tỉ lệ nghịch với số bits được mã hóa, làm cho dữ liệu được lưu trữ hay truyền đi có kích thước nhỏ hơn rất nhiều so với ban đầu. Tốc độ nén nhanh do việc xây dựng bảng mã không phải mất nhiều thời gian. Sử dụng hai thuật toán nén trên không làm tốn bộ nhớ nhiều, việc lưu trữ dễ dàng. Nhìn vào bảng thống kê và biểu đồ, ta có thể thấy được tỉ lệ nén file text của 2 mã nén này là rất tốt, file có kích thước càng lớn thì tỉ lệ nén càng cao (nhất là mã nén Huffman). Nhược điểm: Việc nén dữ liệu là tương đối tốt đối với các loại file văn bản, tuy nhiên nó không hiệu quả đối với các loại file khác. Bảng mã luôn phải đi kèm với dữ liệu nên phải mất một khoảng vùng nhớ cho nó. Luôn luôn phải duyệt thông tin đến 2 lần. Một lần đọc dữ liệu để tạo bảng mã và một lần để mã hóa. Việc mã hóa file có kích thước nhỏ thường không cho tỉ lệ nén tốt so với file có kích thước lớn hơn. Đánh giá tính hiệu quả của phương pháp Shannon-Fano và Huffman : Với file text có dung lượng nhỏ và vừa thì tỉ lệ nén chênh lệch của 2 mã này là không cao, thường thì mã Huffman có tỉ lệ nén cao hơn Shannon-Fano nhưng không đáng kể. Với những file text có nhiều ký tự giống nhau thì tỉ lệ nén là tương đương nhau. Với những file text có dung lượng tương đối lớn trở lên thì chúng ta có thể nhìn thấy rằng mã nén Huffman vượt trội về khả năng nén dữ liệu do thuật toán nén của Huffman giảm được lượng tin tốt hơn. Vì vậy, để mã hóa file text có dung lượng lớn thì nên chọn mã nén Huffman để cho tỉ lệ nén tốt hơn rất nhiều so với mã Shannon-Fano. PHẦN 3 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Với phần mô phỏng thuật toán nén dữ liệu với mã Shannon-Fano và Huffman, em đã phần nào đúc kết được ưu và nhược điểm của 2 thuật toán này qua việc so sánh thuật toán và tỉ lệ nén của nó. Em cũng đã tìm hiểu, thống kê được một số thuật toán nén khác với các dữ liệu khác nhau như file văn bản, file audio và video...Sau đây là những mặt đã làm được và những mặt còn hạn chế của đề tài này: Những mặt đã làm được : Mô phỏng thành công 2 loại mã nén Shannon-Fano và Huffman bằng chương trình C. Đưa ra được tỉ lệ nén của từng loại, so sánh 2 mã nén này và đưa ra được kết luận. Tìm hiểu, nghiên cứu các thuật toán nén khác. Nén thành công với những file text có kích thước lớn. Những mặt còn hạn chế : Chưa thực hiện được nén dữ liệu lớn hơn 8 bits như mã tiếng Việt (có dấu) hoặc các ký tự đặc biệt. Chưa thực hiện nén được với các file dữ liệu khác ngoài file text. Chưa thực hiện được việc so sánh một cách tổng quát và trực quan của tất cả các loại mã nén hiện nay, dẫn đến việc chưa đua ra được kết luận loại mã nén nào là tối ưu, mã nén nào là thông dụng nhất hiện nay. Chưa thực hiện được việc nén các loại dữ liệu khác như nén folder… Hướng phát triển của đề tài: Trong thời gian thực hiện đồ án theo quy định, em đã thực hiện được các công việc như đã nêu ở các phần trên. Một số nội dung trong phần hạn chế em sẽ tiếp tục hoàn thành trong thời gian tới như nén dữ liệu với nhiều dạng file khác, nén dữ liệu với folder và nghiên cứu, cải tiến thuật toán nén nhanh hơn, có giao diện đẹp mắt hơn và dễ sử dụng vào thực tế hơn. TÀI LIỆU THAM KHẢO [1]. Thuật toán trong tin học – Vũ Đức Thi – NXB KHKT [2] Giáo trình lý thuyết mã – Nguyễn Lê Anh, Nguyễn Văn Xuất, Phạm Thế Long – Trường ĐHDL Đông Đô – 1997 [3] The Data Compression Book 2nd edition - Mark Nelson and Jean-loup Gailly [4]. Ngôn ngữ lập trình C - Quách Tuấn Ngọc. [5]. Ngôn ngữ lập trình C++ - Nhóm Ngọc Anh Thư Press [6]. Giáo trình Multimedia – GV Nguyễn Duy Nhất Viễn (Lưu hành nội bộ) [7]. Các nguồn từ Internet.