Bài giảng Multimedia - Chương 1: Tổng quan

1MULTIMEDIAI I Page 2 TÀI LIỆU THAM KHẢO • CMPT 365 Course Contents, Spring 2000, Website: • “Principles of Digital Audio”, Ken C.Pohmanm Fourth Edition McGraw-Hill. • “Digital Video processing”, A. Murat Tekalp, University of Rochester, Prentice Hall PTR. • “Multimedia processing”, Andrew Calway, COMS72200. • “Fundamentals of Digital Image Processing”., Anil.K.Jan, Prentice Hall, 1996. • MPEG Home Page, • “Emerging Wireless Multimedia Services and Technologies”, JohnWileySons, Aug 2005 • “Multimedia Content and the Semantic Web Standards Methods and Tools”, John Wiley Sons, Jun 2005 • “Introduction To Digital Audio Signal Processing”, Davide Rocchesso, 2003 Page 3 NỘI DUNG • TỔNG QUAN • KỸ THUẬT AUDIO • KỸ THUẬT VIDEO 4 TỔNG QUAN Page 5 TỔNG QUAN • TỔNG QUAN VỀ MULTIMEDIA • KHÁI NIỆM CHUNG VỀ AUDIO VÀ VIDEO • HỆ THỐNG AUDIO-VIDEO • MỘT SỐ VẤN ðỀ VỀ TÍN HIỆU Page 6 TỔNG QUAN VỀ MULTIMEDIA • Lịch sử phát triển của hệ thống ña môi trường – Báo, tạp chí - môi trường: văn bản, ñồ hoạ và hình ảnh. – Cáp ñồng: môi trường truyền tải tín hiệu ñiện. – 1895, Guglemo Marconi phát minh ra máy radio ở Pontechio – Ý, môi trường chuyển tải tín hiệu audio quảng bá hiện nay. – Truyền hình, môi trường truyền thông của thế kỷ 20, truyền hình ảnh và âm thanh ñến mọi nơi. – Các hệ thống máy tính tích hợp nhiều dạng môi trường số khác nhau, khả năng biểu diễn, tương tác với các dạng thông tin, tiềm năng lớn phục vụ nhu cầu trao ñổi thông tin chất lượng cao. – Các hệ thống ña môi trường trở nên phong phú, kết hợp các công nghệ khác nhau với khả năng di ñộng, liên lạc từ xa dưới nhiều hình thức. Page 7 TỔNG QUAN VỀ MULTIMEDIA Văn bản thường (tuyến tính) Siêu văn bản Âm thanh Video ðồ hoạ Siêu môi trường Hình 1-1 Hypertext, Hypermedia Siêu văn bản Page 8 TỔNG QUAN VỀ MULTIMEDIA • Siêu môi trường và ña môi trường (hypermedia – multimedia) – Hypertext: “Siêu văn bản là một tài liệu không tuyến tính, bằng cách kích vào một ñiểm nóng nào ñó trên văn bản, nó có thể chuyển ñến một tài liệu hay một văn bản khác, rồi có thể quay về, thuận tiện cho người ñọc trong việc duyệt văn bản hoặc muốn tổng quan một văn bản từ phần mục lục”. (Ted Nelson ,1965) – Hypermedia: Bao gồm nhiều môi trường truyền thông khác nhau như ñồ thị, hình ảnh, âm thanh, hoạt hình và ảnh ñộng. (Ted Nelson). – Multimedia: thông tin máy tính có thể ñược mô tả bằng audio, video hay hoạt hình ngoài những môi trường truyền thống. Page 9 TỔNG QUAN VỀ MULTIMEDIA • Ví dụ một số ứng dụng multimedia: • Hệ thống xây dựng và soạn thảo video số. • Tạp chí ñiện tử. • Trò chơi. • Thương mại ñiện tử. • Truyền hình tương tác iTV. • Truyền hình hội nghị. • Truyền hình theo yêu cầu. • Thực tế ảo. • ... Page 10 TỔNG QUAN VỀ MULTIMEDIA • Các dạng môi trường và tín hiệu: audio video animation graphictextimages dạng môi trường gốc tín hiệu tổng hợpthu nhận rời rạc liên tục Hình 1-2 Dạng môi trường Page 11 TỔNG QUAN VỀ MULTIMEDIA Hình 1-3 Thu nhận và tổng hợp Page 12 TỔNG QUAN VỀ MULTIMEDIA • Âm thanh (audio) • Âm thanh: Là dao ñộng sóng âm gây ra áp lực làm dịch chuyển các hạt vật chất trong môi trường ñàn hồi làm tai người cảm nhận ñược các dao ñộng này. Tai người có thể nghe ñược trong khoảng tần số từ 20Hz ñến 20kHz. • Âm thanh tự nhiên: Là sự kết hợp phức giữa các sóng âm có tần số và dạng sóng khác nhau. • Dải ñộng của tai: Giới hạn bởi ngường nghe thấy (0dB) ñến ngưỡng ñau (120dB) của người. • Ngưỡng nghe tối thiểu: Mức thấp nhất của biên ñộ mà tai người có thể cảm nhận ñược âm thanh tuỳ thuộc vào từng người, mức áp lực và tần số của âm thanh. Page 13 TỔNG QUAN VỀ MULTIMEDIA • Hiệu ứng che khuất âm thanh: Hiện tượng âm thanh mà tại ñó ngưỡng nghe của một âm tăng lên trong khi có mặt của một âm khác (khó nghe hơn). ðược sử dụng trong kỹ thuật nén. • Hướng âm thanh: Tai và não có thể giúp ta xác ñịnh hướng âm thanh, ñiều này có thể ứng dụng ñể tạo các hiệu ứng âm thanh như stereo, surround. • Vang và trễ: Vang là hiện tượng kép dài âm thanh sau khi nguồn âm ñã tắt. Trễ là thời gian τ âm thanh phản xạ ñến ñích so với âm thanh trực tiếp. Nếu τ>50ms thì trễ ñó gọi là tiếng vọng. Biên ñộ của âm thanh cứ sau 1 lần phản xạ thì bị suy giảm. • Âm nhạc: Là âm thanh có chu kỳ ở những tần số mà tai người cảm nhận một cách dễ chịu, êm ái, ñược kết hợp một cách phù hợp. Âm nhạc gồm cao ñộ, âm sắc và nhịp ñiệu. Page 14 TỔNG QUAN VỀ MULTIMEDIA • Video • Tín hiệu video: Là sự tái tạo ảnh tự nhiên với những khoảng cách về không gian, thời gian hoặc cả hai. • Ảnh tự nhiên: ñược tạo nên từ các nguồn sáng mặt trời hay ánh sáng nhân tạo phản xạ lên các vật thể mà ta có thể nhìn thấy ñược. • Ảnh: Là một ma trận các ñiểm ảnh mang thông tin về ñộ chói và màu sắc. • Sự lưu ảnh: Khả năng lưu hình của mắt trong một giây. Mắt có thể lưu ñược 24 hình trong một giây. Chọn số hình trong một giây của ảnh ñộng phù hợp Page 15 TỔNG QUAN VỀ MULTIMEDIA • ðộ chói: Là biên ñộ của thành phần trong ảnh (pixel). • Ví dụ tín hiệu chói Y ñược tổng hợp bởi các tín hiệu RGB theo công thức: • EY=0,299ER+0,587EG+0,114EB (1-2) • Thông tin màu ñược xác ñịnh: • EB-EY=0,587EG+0,889EB+0,229ER • ER-EY=0,587EG+0,114EB+0,701ER (1-3) • ðộ tương phản: Tỷ số của ñộ chói thành phần sáng nhất so với ñộ chói của thành phần tối nhất. Page 16 TỔNG QUAN VỀ MULTIMEDIA • Hệ thống audio tương tự Hình 1-4 Hệ thống audio tương tự N gu ồn âm T iề n kh uế ch ñạ i X ử lý K hu ếc h ñạ i Lưu trữ X uấ t Page 17 HỆ THỐNG AUDIO-VIDEO • Hệ thống video tương tự Hình 1-5 Hệ thống Video tương tự Mắt người Ảnh tái tạo Cảnh tự nhiên Ống kính Chuyển ñổi ảnh- tín hiệu Xử lý tín hiệu Tạo xung ñồng bộ Chuyển ñổi tín hiệu - ảnh Xử lý tín hiệu Tách xung ñồng bộ Lưu trữ hoặc truyền dẫn Page 18 HỆ THỐNG AUDIO-VIDEO • Hệ thống audio-video số: Nguồn tín hiệu (Analog) Chuyển ñổi Analog - Digital Xử lý, Lưu trữ, Truyền dẫn (Digital) Chuyển ñổi Digital - Analog Xuất âm, hiển thị (Analog) Hình 1-6 Hệ thống audio-video số Page 19 HỆ THỐNG AUDIO-VIDEO • Các thành phần của hệ thống: – Bộ phận thu: Micro và Camera thu và chuyển tín hiệu (âm thanh hoặc ảnh) sang tín hiệu ñiện tương tự. ðối với các hệ thống số phải thực hiện việc chuyển ñổi tương tự sang số. – Lưu trữ: Thiết bị lưu trữ là băng từ hoặc ñĩa từ. Có thể là các thiết bị riêng biệt sử dụng với muc ñích thuận tiện và yêu cầu một chất lượng nào ñó. – Xử lý tín hiệu: ðiều chỉnh ñặc tuyến tần số, màu sắc, tạo hiệu ứng.. – Truyền dẫn: Truyền tín hiệu từ vị trí này sang vị trí khác với một khoảng cách không gian nào ñó qua một môi trường truyền dẫn nào ñó. Page 20 HỆ THỐNG AUDIO-VIDEO • Phân loại các hệ thống Audio-Video: Toàn bộMáy tính cá nhân Chất lượng, linh họat Sản xuất hậu kỳ Cơ ñộng, dễ sử dụng Sản xuất chương trình ngoài trời Chất lượng, linh họat Sản xuất studio Khả năng lưu trữ Phân phối video Nén videoCầu hội thảo Chất lượng, giáBán chuyên nghiệp Giá, dễ sử dụngA-V gia ñình Yếu tố quan trọng nhất Khả năng mở rộng Linh hoạt Dễ sử dụng Chất lượng GiáLớp hệ thống Page 21 HỆ THỐNG AUDIO-VIDEO • Hệ thống Audio – Video dân dụng: – Xây dựng hoặc tạo lại một số chương trình nhất ñịnh – Ghi, lưu trữ những sự kiện cá nhân. – Hầu hết các chương trình ñược thu và tạo ra tại chỗ. – Hệ thống ñáp ứng nhu cầu giá thành thấp, dễ sử dụng ñể phổ biến rộng rãi. – Sử dụng phương pháp sản xuất hậu kỳ với chất lượng giới hạn nhất ñịnh. – ða hệ và tương thích với mọi tiêu chuẩn. – Mối quan tâm của các nhà sản xuất. Page 22 HỆ THỐNG AUDIO-VIDEO • Hệ thống Audio-Video dân dụng Interface cardCamera VCR, VCD, DVD PAL, NTSC Hình 1-7 Hệ thống Audio – Video dân dụng Page 23 HỆ THỐNG AUDIO-VIDEO • Hệ thống Audio – Video bán chuyên dụng Interface card Camera VCR, VCD, DVD PAL, NTSC Hình 1-8 Hệ thống Audio – Video bán chuyên dụng VCR, VCD, DVD Băng, ñĩa Băng, ñĩa Tới khách hàng Page 24 HỆ THỐNG AUDIO-VIDEO • Hệ thống phân phối: – Tập hợp chương trình thành một dòng dữ liệu ñể phát quảng bá, truyền hình cáp hay vệ tinh. – Khả năng chuyển tải ñến người xem thông qua máy phát, mạng hay một phương thức nào ñó. – Máy chủ phải ñáp ứng khả năng lưu trữ ñối với tín hiệu nhằm tạo ñường truyền thông suốt giữa các chương trình. – Yêu cầu tự ñộng cao, giảm chi phí nhân công. – Truyền hình tương tác yêu cầu khả năng xử lý và chất lượng ñường truyền khá cao, ñồng thời hệ thống phải có khả năng phát các chương trình khác nhau trong cùng thời ñiểm. Page 25 HỆ THỐNG AUDIO-VIDEO • Hệ thống Audio – Video studio sản xuất chương trình Camera1 Camera2 Camera3 Camera4 Bộ tạo kỹ xảo ðầu ra video Cam1 Cam2 Cam3 Cam4 VCR1 VCR2 VCR3 EFF LINE VCR1 VCR2 VCR3 E F F 1 E F F 2 Hình 1-9 Hệ thống Audio – Video studio sản xuất chương trình LINEVCR1 VCR2 VCR3 Page 26 HỆ THỐNG AUDIO-VIDEO • Hệ thống sản xuất chương trình ngoài trời: – ðược sử dụng ñể thu các bản tin hay một chương trình nào ñó mà không cần nhiều người thực hiện, thường sử dụng các thiết bị cầm tay. – Các chương trình truyền trực tiếp thì hệ thống có thể là các hệ thống cố ñịnh nhưng với quy mô nhỏ và chất lượng thấp hơn. – Yêu cầu tính cơ ñộng cao. – Camera ñược nối với máy ghi riêng mà khôg sử dụng ma trận chuyển mạch. – Máy ghi âm ña ñường ñược sử dụng ñể thuận tiện trong hậu kỳ âm thanh nhưng phải yêu cầu ñồng bộ với hình. Page 27 HỆ THỐNG AUDIO-VIDEO • Hệ thống sản xuất hậu kỳ Bộ tạo tiêu ñề Camera copy Kỹ xảo A TITL1 GRPH1 Cam1 VCR1 VCR2 VCR3 E F F B 1 VCR1 VCR2 VCR3 E F F A 1 E F F A 2 Bộ tạo ñồ họa Kỹ xảo B EFFA EFFB E F F B 2 BỘ ðIỀU KHIỂN DỰNG Hình 1-10 Hệ thống Audio – Video sản xuất hậu kỳ Page 28 HỆ THỐNG AUDIO-VIDEO • Hệ thống cầu hội thảo Monitor Camera Micro Audio Máy chiếu Bộ xử lý và ñiều khiển số Monitor Camera Micro Audio Máy chiếu Bộ xử lý và ñiều khiển số Vị trí A Vị trí B Hình 1-11 Hệ thống cầu hội thảo Page 29 HỆ THỐNG AUDIO-VIDEO • Hệ thống audio video trong PC – PC dùng ñể trình diễn, lưu trữ, xử lý âm thanh, hình ảnh. – ðiều khiển bằng phần mềm chuyên dụng kết hợp với các card ñồ họa, xử lý kỷ xảo. – ða dạng về tiêu chuẩn dẫn ñến khó tương thích. – Có thể yêu cầu nhiều dạng card thích ứng khác nhau và có thể sử dụng hơn một màn hình ñể hiển thị. – Dữ liệu có thể yêu cầu nén và giải nén vì phạm vi ứng dụng khả rộng. Page 30 MỘT SỐ VẤN ðỀ VỀ TÍN HIỆU • Tín hiệu và hàm – Tín hiệu tương tự là hàm theo thời gian. – Biên ñộ âm thanh ñược biểu diễn bằng mức ñộ âm thanh tại thời ñiểm ñã cho. – Tín hiệu ñược biểu diễn bằng hàm f(t). • Tín hiệu có chu kỳ – Sự lặp lại trong một khoảng thời gian ngắn nhất không ñổi của tín hiệu gọi là chu kỳ T. – Tần số là nghịch ñảo của chu kỳ: u=1/T. Biên ñộ Thời gian t f(t0) t0 Hình 1-7 Biểu diễn biên ñộ-thời gian Page 31 MỘT SỐ VẤN ðỀ VỀ TÍN HIỆU • Phân tích Fourier – Trong thực tế, rất ít khi ta có ñược một tín hiệu ñơn tần, mà thông thường là các tín hiệu phức tạp, kết hợp bởi nhiều tần số và các hài của nó. – Việc phân tích Fourier cho kết quả là tổng của các hàm sin và cosin của các tần số khác nhau. • Phân tích Fourier một chiều: 2( ) ( ) j utF u f t e dtπ ∞ − −∞ = ∫ 2( ) ( ) j utf t F u e duπ ∞ −∞ = ∫ F(u)=FR(u)+jFI(u) 2 2( ) ( ) ( )R IF u F u F u= + ) )( )( arctan()( uF uF u R I=θ )()()()()( ujIR euFujFuFuF θ=+= Page 32 MỘT SỐ VẤN ðỀ VỀ TÍN HIỆU • Phổ tần số – Sự phân bố của |F(u)| gọi là phổ tần của tín hiệu. – Tín hiệu biến thiên chậm thì phổ tần tập trung ở tần số thấp và ngược lại. Từ ñó hình thành tín hiệu tần số thấp và tần số cao. Biên ñộ phổ |Fu| Tần số (u) Page 33 MỘT SỐ VẤN ðỀ VỀ TÍN HIỆU • Tín hiệu Audio và Video – Tín hiệu âm thanh thường là tín hiệu một chiều. – Tín hiệu ảnh là tín hiệu hai chiều. – Tín hiệu Video là tín hiệu 3 chiều. – Với các chiều khác nhau, ta sẽ có số biến khác nhau tương ứng. • Chuyển ñổi Fourier 2 chiều ∫ ∫ ∞ ∞− ∞ ∞− +−= dxdyeyxfvuF vyuxj )(2),(),( π ∫ ∫ ∞ ∞− ∞ ∞− += dudvevuFyxf vyuxj )(2),(),( π vyjuxjvyuxj eee πππ 22)(2 −−+− = Page 34 MỘT SỐ VẤN ðỀ VỀ TÍN HIỆU • Mằu sắc – Việc kết hợp các màu khác nhau tạo nên một màu mới. Thông thường, chọn các màu cơ bản ñể kết hợp, ví dụ RGB Red BlueGreen Yellow Magenta White Hình 1-8 Lý thuyết 3 màu RGB Page 35 MỘT SỐ VẤN ðỀ VỀ TÍN HIỆU • Không gian cảm quan màu 3 chiều: – Con người cảm quan màu sắc ở các khía cạnh sau: brightness: ñộ sáng như thế nào. hue: màu nào. saturation: sự tinh khiết – Sự cảm quan này ñối với mỗi người là mỗi khác biệt, do ñó, không thể so ñược giữa người này với người kia. Hình 1-9 Cảm quan 3 chiều Page 36 NÉN DỮ LIỆU • ðại lượng ño thông tin – Lượng thông tin trong tín hiệu có thể không bằng lượng dữ liệu của nó mà quan hệ mật thiết với xác suất xuất hiện của nó. • Tự-thông tin (lượng tin) – Thông tin ñược mang bởi một biến cố A có xác suất xuất hiện P[A] là: – Thông tin không (lượng tin =0): • Mặt trời mọc ñằng ñông. – Lượng tin ít • Máy ñiện thoại di ñộng trong tương lai ñều có khả năng multimedia – Lượng tin nhiều: • Trường ðKBK ðN ñược xếp hạng nhất trên thế giới về ðTVT [ ] [ ]2 2 1 log logAI P AP A = = − IA P[A] 10 Page 37 NÉN DỮ LIỆU • Entropy – Lượng tin trung bình của nguồn tin, một cách gần ñúng, là số bit trung bình của thông tin yêu cầu ñể biểu diễn các ký hiệu của nguồn tin. – Với nguồn N ký hiệu Xi thì entropy ñược ñịnh nghĩa như sau: • H(S)≥0; ñối với mã hoá nhị phân, H(S) thể hiện mã hoá với số bít/ký hiệu tối thiểu. • Ví dụ: Trong một ảnh phân bố ñều ở thang xám (256 mức): pi=1/256, số bit mã hoá cho mức xám là log2256=8bits.
Entropy của ảnh này là H(S)=Σpilog2(1/pi)=8bits/ký hiệu. Vậy, trong trường hợp phân bố ñều này, mã hoá ñộ dài cố ñịnh sẽ ñạt ñược số bit tối thiểu. Trong trường hợp tổng quan thì mã hóa ñộ dài cố ñịnh sẽ không hiệu quả. [ ] [ ]2 1 ( ) log N i i i H S P X P X = = −∑ Page 38 NÉN DỮ LIỆU • Mã hoá ñộ dài cố ñịnh FLC (Fixed-Length Code) – ðặc ñiểm: • Sử dụng số bit cố ñịnh ñể biểu diễn mọi ký hiệu của nguồn. • ðơn giản trong quá trình mã hoá/giải mã. – Ví dụ • Mã ASCII (American Standard Code for Information Interchange) sử dụng 8 bits ñể mã hoá các ký tự. – Truyền chuỗi: DTVT: 68 84 86 84: 01101000 10000100 10000110 10000100 – Nhược ñiểm: • Không hiệu quả Page 39 NÉN DỮ LIỆU • Mã hoá ñộ dài thay ñổi VLC (Variable-Length Code) – ðặc ñiểm • Sử dụng số bit khác nhau ñể biểu diễn các ký tự khác nhau. • Các ký tự có xác suất xuất hiện cao ñược phân bố bởi từ mã ngắn và ngược lại. • Hiệu quả trong việc biểu diễn hơn, nén tốt hơn. – Ví dụ: • Mã Morse. • Shannon-Fano. • Huffman. • Mã hoá loạt dài (RLC). Page 40 NÉN DỮ LIỆU • Thuật toán Shannon-Fano • Ví dụ mô tả thuật toán: • Mã hoá theo thuật toán Shannon-Fano: - Sắp xếp các ký tự theo thứ tự giảm dần của tần suất xuất hiện. - Tính xác suất. - ðệ quy làm hai phần, mỗi phần có tổng xác suất gần bằng nhau. Mã hoá phần trên bằng bit 0 (hoặc bit 1), phần dưới bằng bit 1 (hoặc bit 0). - Vẽ sơ ñồ cây. - Tính Entropy, số bits mã hoá trung bình và số bit mã hoá thông thường. - Nhận xét. 656715Số lầ xuất hiện EDCBAKý hiệu Page 41 NÉN DỮ LIỆU • Entropy của nguồn: • Số bits sử dụng trung bình: • Số bít mã hoá thông thường: log25=3bits • Nhận xét: Số bits sử dụng trung bình gần H(S) thì bộ mã càng hiệu quả. Gốc A B C E D 0 0 1 1 1 10 0 2 1 15 7 6 6 5 ( ) log .1.38 .2.48 2.7 2.7 2.96 39 39 39 39 39 ( ) 2.19. E i i A i H S p p H s = = = + + + + = ∑ 30 14 12 18 15 2.28 its 39 R b + + + + =
Tổng bitsMãLog2(1/pi)PiðếmKý hiệu 15 18 12 14 30001.3815/3915A 1112.965/395D 0112.76/396E 012.76/396C 102.487/397B Page 42 NÉN DỮ LIỆU • Mã hoá Huffman – Nguyên tắc: Dựa vào mô hình thống kê của dữ liệu gốc, ký tự có xác suất càng cao thì mã hoá với từ mã càng ngắn. – Thuật toán: - Tính tần suất xuất hiện trong dữ liệu gốc, sắp xếp theo thú tự giảm dần. - Xét từ dưới lên trên, bắt ñầu từ hai ký tự có xác suất bé nhất, quy ñinh mỗi nhánh là 0 (hoặc 1) hợp lại với nhau thành nút có xác suất bằng tổng hai xác suất hợp thành. - Lặp lại cho ñến hết. Page 43 NÉN DỮ LIỆU – Xét ví dụ trên – Số bít trung bình: 87/39=2.23 (<2.28) – Hiệu quả hơn Shannon – Fano. 150115/39D 180106/39E 180016/39C 210007/39B 15115/39A Tổng bitMãXác suấtKý hiệu 0 1 0 1 0 1 11/39 13/39 0 1 24/39 Page 44 NÉN DỮ LIỆU • Mã hoá loạt dài RLC (Run-Length Coding) – Nguyên lý • Mã hoá loạt ký hiệu bằng chiều dài và ký hiệu của loạt ñó. – ðặc ñiểm • Mã hoá không tổn hao • Mã hoá liên ký tự. • Hiệu quả với một số nguồn tín hiệu, nhất là sau phép chuyển ñổi. – Ví dụ • 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 15: (11,13)3 (9,13)15 • mã: (11,3) (9,15) Bit thôRun-length Loạt 0 dài side số bit cần mã hoá Cần 4 bits mã hoáCần 2 bits mã hoá Page 45 NÉN DỮ LIỆU • Mã hoá Lempel-Zip-Welch: – Nén từ ñiển ñược Jacob Lampel và Abraham Ziv ñề xuất năm 1977, phát triển thành họ LZ, LZ77, LZ78. – Năm 1984, Terry Welch cải tiến thành LZW. – Nguyên tắc: Dựa vào việc xây dựng một từ ñiển lưu các chuỗi ký tự có tần suất cao và thay thế bằng một từ mã mới. – LZW tổ chức từ ñiển tốt hơn nên nâng cao tỷ lệ nén. – Ví dụ: Xét từ ñiển có ñộ lớn bằng 4096 giá trị từ mã, vậy ñộ dài lớn nhất của từ mã là 12 bits (212=4096). – Xét chuỗi vào ABCBCABCABCD. 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. Chuỗi mới4095 Chuỗi mới258 257 | End of Information257 256 | Clear Code256 255255 00 Page 46 NÉN DỮ LIỆU • Thuật toán: - w = NIL; - trong khi ñọc ñược ký tự thứ k trong chuối - nếu wk ñã tồn tại trong từ ñiển thì w = wk - 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; • Chuỗi ra: 65 66 67 259 258 67 262 68 • ðầu vào 12ktx8bits=96 bits. • ðầu ra : 5ktx8+3ktx9=67bits. • Tỷ lệ nén: 96/67=1.43 68 ABCD264262DABC CAB BA CA26367AC ABC262258CB BA BCA261259ABC CB CB26067BC BC25966CB AB25865BA ANil SymbolIndexOutputKW Page 47 NÉN DỮ LIỆU • Lưu ñồ Start w=nil count=0 k=str[count] k=nil? wk in dict? w=wk count++ Output(w) index++ Symbol=dict[index]= wk. Output(w). w=k End Y N Y N