<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

<b>TRƯỜNG ĐẠI HỌC M HÀ NỞ ỘI </b>

KHOA CÔNG NGHỆ THÔNG TIN ---

<b>BÀI TẬP LỚN </b>

<b>MƠN: CƠNG NGHỆ ĐA PHƯƠNG TIỆN ĐỀ 2 </b>

<b>Tìm hiểu thuật tốn nén số học, cho ví d minh hoụ ạ </b>

<b> Giảng viên hư ng d n: Tr n Duy Hùngớẫầ Sinh viên thực hiện. : Vũ Đức Thọ Lớp : 1910A05 </b>

<b>Hà Nội – 2023</b>

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

<b>MỤC LỤC </b>

<b>I. GIỚI THIỆU V NÉN DỀ Ữ ỆU LI... 3 </b>

<b>II. PHÂN LOẠI NÉN DỮ ỆU LI... 3 </b>

<b>5. Đơn vị đo thông tin(Entropy) và đ dài trung bình cộ ủa từ mã ... 5 </b>

<b>IV. THUẬT TOÁN NÉN SỐ HỌC ... 5 </b>

<b>1. Sơ lược về thuật toán nén số học ... 5 </b>

<b>2. Ý tưởng thuật toán ... 5 </b>

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

<b>I. GIỚI THIỆU V NÉN DỀ Ữ ỆU LI</b>

Cùng với sự hoà nh p cậ ủa tin h c vớọ i các lĩnh vực trong đ i sống hi n ờ ệ đại ngày nay thì việc xử lý các lo i tạ ập tin với các kiểu file khác nhau là điều tất yếu, và cá loại tập tin này thư ng có kích thườ ớc lớn nên nhi u khi ề nó gây khó khăn trong công tác truy n gề ửi và lưu tr . Vì vữ ậy, khi lưu trữ hay truy n gề ửi ngư i ta mong muờ ốn giảm đến. mức thấp nhất dung lượng bộ ớ nh mà các tập tin này chiếm dụng để dễ dàng t chức, quản lý và tiết ổ kiệm kinh phí.

Để đáp ng các yêu c u trên ngưứ ầ ời ta đã nghĩ ra các phương pháp làm cho các thông tin đó chiếm ít dung lượng hơn b ng cách nén chúng. Hiằ ểu đơn gi n thì đó là quá trình giả ảm dung lượng nhớ cần thiết cho các tập tin mà vẫn bi u diể ễn cùng một lượng thông tin như trước.

Đã có rất nhi u phương pháp nén đưề ợc cho ra đời. M t trong sộ ố đó là

<b>thuật toán nén số học. </b>

Thuật toán nén số học đư c sợ ử dụng đ nénể dữ liệu b ng cách sằ ử dụng mã hoá entropy. Thuật toán này được đề xuất lần đ u tiên vào năm 1976 ầ bởi nhà toán học người Mỹ Robert M. Fano. Thuật toán này sử dụng phép tính số học đ mã hố các ký tể ự trong chu i dỗ ữ liệu.

<b>II. PHÂN LOẠI NÉN DỮ ỆU LI</b>

Nén dữ liệu chia thành 2 dạng là nén t n thổ ất và nén không tổn thất

<b>1. Nén tổn thất </b>

- Nén tổn thất là kỹ thu t nén chậ ấp nh n mậ ất mát m t lượng thông tin ộ nhất đinh để đạt được hiểu qu nén cao, nén t n thả ổ ất thích hợp với các tập tin hình nh, âm thanh đã đưả ợc số hoá. Theo b n chả ất việc biểu di n thông tin tương tễ ự ới dạng s ngay tdư ố ừ đầu đã chứa các sai số. Hầu hết các kỹ thuật nén tổn thất đều có thể diều ch nh đỉ ể cân

</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4">

bằng giữa độ chính xác và hiệu quả nén, Đối v i các thông tin bớ ị mất mát không phải là vấn đ quan tr ng bề ọ ởi vì nó có thể được khơi ph c ụ lại, Do đó ở đây chúng ta ch quan tâmỉ đến hi u quệ ả nén mà thôi.

<b>2. Nén không tổn thất </b>

- Nén không tổn thất là phương pháp nén đảm bảo không mất mát thông tin sau quá trình mã hố và gi i mã. Sau khi nén và gi i nén ả ả thì nó ph i tả ạo ra một bản sao chính xác so với lúc đầu. Kỹ thuật này sử dụng đ lưu tr và truy n cá cơ sể ữ ề ở dữ liệu, các b ng tính đi n tả ệ ử, cá văn bản… vì với vavs t p tin này thì việậ c mất mát dù chỉ 1 bit thông tin cũng là điều không thể chấp nh n đưậ ợc.

<b>III. CÁC KHÁI NIỆM LIÊN QUAN 1. Nén dữ ệu li</b>

- Nén dữ liệu là quá trình giảm dung lượng thông tin “dư thừa” trong dữ liệu gốc và làm cho lượng thông tin thu được sau nén thường nhỏ hơn dữ liệu gốc rất nhiều. Do vậy, ti t kiệm được bộ nhớ ế và giảm thời gian trao đổi dữ ệu trên, mang lạli i thông tin mà l i cho phép ạ chúng ta khôi phục lạ ữ ệu i d li ban đầu.

<b>2. Sự phân b ký tố ự </b>

- Một số ký t (Pixel) xuấự t hiện vớ ần xuấ ớn hơn so với t t l i các ký tự khác t ng dỏ ữ liệu gốc(ảnh,..). Ta có thể thay th nhữế ng ký t này ự bằng từ mã nhị phân nhi u bit hơn và các ký tề ự xuất hiện ít hơn b ng ằ mã nhị phân ít bit hơn.

<b>3. Sự lặp lại cá ký tc ự </b>

- Một chu i cá ký tỗ ự (bit 1 hoặc 0) đư c lợ ặp lại nhiều l n. Ta có thầ ể mã hố chuỗi lặp đó b ng it bit hơn.ằ

<b>4. Độ dư thừa </b>

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

- Nếu nh ng ký t nào đó xuữ ự ất hiện ở một v trí mà ta có thị ể đốn trước đư c khi mã hố ta có thợ ể giữ vị trí mà ký tự đó xuất hiện thay vì lưu trữ các ký t đó. ự

<b>5. Đơn vị đo thơng tin(Entropy) và độ dài trung bình của từ mã</b>

- Lý thuyết thông tin sử dụng thuật ngữ Entropy là đơn vị đo thông tin được mã hố trong một thơng điệp. Entropy của một thơng điệp càng cao thì thơng tin nó chứa đựng càng nhiều.

- Độ dài trung bình của từ mã là giá trị trung bình của tất cả các từ mã trong m t bộ ộ mã. Đ dài trung bình của t mã khơng th nào nhộ ừ ể ỏ hơn entropy của nguồn số liệu được mã hố và do đó một bộ mã t i ố ưu là một bộ mã có độ dài trung bình cảu từ mã gần với entropy của nguồn dữ liệ u.

<b>IV. THUẬT TOÁN NÉN SỐ HỌC 1. Sơ lược về thuật toán nén số học </b>

- Nén số học là một trong những phương pháp nén không t n hao tuy ổ nhiên ngay t khi ra đừ ời, phương pháp này khơng mang tính khả thi vì nó phức tạp về mặt khái niệm lẫn việc th c hiự ện trong thực tế. Khi thực hiện phương pháp này nó yêu c u bộ nhớ ầ có dung lượng l n, ớ thời gian thực hiện lâu nên trong một th i gian dài nó vờ ẫn chỉ mang tính thử nghiệm ở trong các cuộc thí nghiệm và nghiên cứu. Cho đ n ế khi có sự phát tri n cể ủa t c đố ộ tính tốn cũng như dung lượng bộ nhớ các máy tính thì phương pháp này mới được người ta chú ý đến nhi u ề hơn. Khi đó người ta m i nghĩ đến viớ ệc áp dụng phương pháp này vào trong thực tế.

<b>2. Ý tưởng thuật toán </b>

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

Thuật toán nén số học áp dụng cho rất nhiều việc như nén hình ảnh, văn bản, dữ liệu,… Dưới đây là chi ti t thu t toán nén văn bế ậ ản.

<b>2.1 Mã hố </b>

- Khơng thay thế cá ký tự đầu vào b ng cá tằ ừ mã riêng biệt mà thay th luế ồng ký hi u đ u vào b ng mệ ầ ằ ột từ mã duy nhất ở đầu ra. Đ u ra ầ là m t sộ ố lớ<b>n hơn 0 và nh hơn 1. </b>ỏ

- Phân chia khoảng giữa 0 và 1 d a vào sự ự phân b xác suố ất của kí hiệu trong mơ hình đax xây d ng đự ể bắt đầu hoạt động. Kho ng này ả được tính lại sau khi có m t ký tộ <b>ự ợc mã hố. </b>đư

- Giả sử chúng ta có một thông điệp bao g m các ký t khác nhau ồ ự thuộc bảng chữ cái alphabet có độ lớn giới hạn. Cũng giả sử rằng chúng ta biết xác su t xu t hiấ ấ ện của mỗi ký tự là khác nhau, và ta tìm cách diễn tả lại thơng điệp đó mà dùng một số bit nhỏ nhất có th . ể Với thu t toán nén sậ ố học nó khơng tạo ra t ng từ ừ mã riêng biệt cho từng ký tự mà nó chỉ tạo ra một từ mã duy nhất cho toàn bộ nguồn số liệu. T mã này sừ ẽ bị thay đổi trong q trình mã hố m i khi có ỗ thêm m t ký tộ ự được mã hố. Do đó t mã ừ ở đầu ra khơng cịn là một số ngun các bit nữa mà là một số lẻ các bit. Vì vậy nó g n vầ ới entropy hơn mà mang lại hiệu qu nén tả ốt nhất.

<b>2.2 Giải mã </b>

- Để giải mã ta tìm ký tự đầu tiên của thơng điệp b ng cáh tìm xem ằ giá trị củ ừ a t mã mà b mã hoá gưộ ở đến là bao nhiêu và nằm trong khoảng nào và nó tương đương với ký tự nào và xu<b>ất nó ra. 3. Thuật tốn </b>

<b>3.1 Mã hoá </b>

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

- Bước mã hoá cơ sở của bộ mã hoá được th c hiự ện bới arithmetic_encode(l,h,t) trong đó l và h l n lưầ ợt là mức thấp và mức cao c a biủ ến đ m trước khi tích luỹ số tầế n s trong ngữ cảnh của các ố ký tự tương ứng, hàm này mã hoá 1 ký tự giả sử ngầm định nó xuất hiện h - l lần trong t ng sổ ố t lần, và nó chỉ định vùng xác suất là [ l/h, h/t ]. Tr ng thái nạ ội t i cạ ủa bộ mã hoá được cho bởi 2 giá tr là R và ị L, trong đó L là mức thấp hi n t i và R là vùng củệ ạ a đoạn đang mã hoá, và tại m i giai đoỗ ạn thì thơng đi p có thệ ể được diễ ả bất kì n t giai đo n nào trong đo n [ L, ạ ạ L+R ]. Giá trị L và R được th hiệể n thông qua b bit, L được kh i tạở o là 0 và nó có giá trị nằm giữa 0 và (2^b) – [2^(b-2)], R được khởi to là 2^(b ạ -1) và có giá trị nằm giữa 2^(b-2) + 1 và 2^(b 1). Cho 0 1 h - £ £ £ t và t là tổng t n sầ ố của tất cả ký t khác nhau đư c chự ợ ỉ định trong ngữ cảnh, t phải tho mãn ả điều ki n t ệ £ 2^f với f là s bit đã dùng đố ể giữ tần số của ký t cà có ự thể khơng vượt quá giá tr điều khi n bị ể ởi lựa chọn của b và kích thước máy đang dùng.

<b>Đầu vào là các bi n thành ph n l, h, tếầĐầu ra là các bit bi u di n kí tểễự đó </b>

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

- Hoạt động cơ sở của b mã hoá, trong các bước 1, 2 và 3 là làm nhỏ ộ khoảng [L, L + R ) thành các kho ng nh hơn đả ỏ ể biểu di n cá ký tễ ự mới [ l/t, h/t ], mang l i m t vùng m i là [L + R.l/t, L+ R.h/t]. Giá trạ ộ ớ ị của L và R được cập nhật để phản ánh vùng mới này. Vùng này phải chuẩn hoá l i thành các giai đo n đ ngăn c n nó trạ ạ ể ả ở thành các khoảng quá nhỏ để ễn t dùng b bit cdi ả ủa giá trị này.

- Để giảm tối đa sự mất mát hiệu qu nén bả ởi sự chia không chính xác của khơng gian mã, R nên được gi a ữ ở giá trị lớn n u có thế ể và trong hoạt động hi n tệ ại, nó pahir có độ rộng tối thiểu cũng như t. Đi u này ề được th c hiự ện b ng cách duy trì trong kho ng 2^(b 2) < R < 2^(bằ ả - -1) trước mỗi bước mã hoá và khẳng đ nh r ng t ị ằ £ 2^f với f £ b-2. Đó là R ph i đưả ợc chuẩn hoá một cánh định kỳ với m t hoộ ặc nhiều hơn cá bit ở đầu ra. Chi tiết của quá trình chuẩn hoá này phù h p vợ ới sự chuẩn hoá l i của L, R và chu n hoá l i R là m t bưạ ẩ ạ ộ ớc c a ủ arithmetic_encode().

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

- Trong thuật toán chuẩn hoá lại R trong bộ mã hoá, khi L và L+R đều £ 2^(b-1), bit 0 có thể là đầu ra và L, R nên đi u ch nh cho đúng. ề ỉ Tương tự, k t quế ả đầu ra có thể là bit 1 khi cả 2 đ u l n hoen 2^(bề ớ -1). Khi R £ 2^(b-2) và cả 2 trư ng h p trên khôgn ch p nh n, kho ng ờ ợ ấ ậ ả [L, L+R) phải thuộc 2^(b-1). Trong trường h p th 3 thì biợ ứ ến bit_outstanding được tăng, đây là biến lưu trữ tấ ả t c các bit biểu di n ễ ký tự đầu vào, do đó bit 0 hoặc 1 c a đủ ầu ra s đi theo sau bẽ ởi m t ộ hoặc nhi u bit đề ối lập với nó. Hàm bit_plus_follow() kiểm tra vị tí có sự tồn tại các bit ngư c nhau c a các bit tợ ủ ại th i gian mà nó đườ ợc gọi là trên đầu ra với m t bit khác đã biộ ết.

- Hàm big_plus_follow(x): Ghi bit x có giá trị 0 hahy 1 vào dãy bit đầu ra. C ng vào bộ ất kỳ một bit tự do nào vồ sau cá bit đó n u biế ết được rằng nó ngư c nhau: ợ

big_plus_follow(x) {

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

Giá trị mới của L và R sẽ ể th hiện việc thay đổi trạng thái mã hoá các thơng tin cịn lại của ký tự.

<b>3.2 Giải mã </b>

- Với V là của sổ hiện tại mở rọng với b bit vào luồng bit đã nén. 2 hàm decode_target(t) và arithmetic_decode(l,h,t) tương đương với 2 bước cơ bản được yêu cầu để ải mã m t ký t . Giá tr target() dgi ộ ự ị ựa trên V và giá tị của t đã dùng trong mã hoá tương đương, nó đáp ứng cho q trình tìm kiếm c u trúc dấ ữ liệu và xác đ nh ký tị ự s, tìm ký tự với 1 target £ £ h. Rồ ọi g i hàm aritthmetic_decode() thay đ i giá ổ trị của cá biến L và R để ể th hiện sự thay đ i tương đương trong bổ ộ mã hoá khi gọi hàm arithmetic_encode().

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

Cho tần số xuất hiện ký tự A là 1/4 và tần số xuất hiện ký tự B là 3/4. Xét việc mã hóa trong trường hợp chuỗi mã hóa là hợp thành của 2 ký tự một

pA=1/4, pB=3/4, pAA = pA x pA = 1/16 , pAB = pA x pB = 3/16, pBA = pB x pA = 3/16 , pBB = pB x pB = 9/16

Sau khi đã chia được các khoảng cho mỗi ký tự đơn, tiếp tục chia các khoảng của bước trước cho 2 ký tự ghép. Cụ thể là khoảng [0, 1/ 4) của A

</div><span class="text_page_counter">Trang 12</span><div class="page_container" data-page="12">

được chia thành hai khoảng cho AA, AB dựa vào tần số xuất hiện của chúng.

</div><span class="text_page_counter">Trang 13</span><div class="page_container" data-page="13">

<b>VI. TÀI LIỆU THAM KHẢO </b>

<b>[1]- data-</b>

<b>-compression-using-arithmetic-encoding-in python--and- -itsapplications- -in deep learning -[2]- coding</b>

</div>