Huffman dan oshib: Asymmetric Numeral Systems qanday mukammal siqishga erishadi

Veb-xizmatlaringiz millionlab so'rovlarni qayta ishlasa, har bir bayt bandvich muhim. CDN xarajatlari, baza saqlash va API javoblari barcha siqish sifatiga bog'liq. Ko'pchilik dasturchi gzip yoki brotli ishlatadi, lekin bu matematikani tushunmaydi. Agar ma'lumotni nazariy chegaraga yaqin siqish mumkin bo'lsa-chi?

Ma'lumotlar nazariyasi muammosi

Har qanday ma'lumotda belgilar turlicha tez-tez uchraydi. Shennon teoremasiga ko'ra, har bir belgi uning ehtimolligiga qarab ma'lumot "narxiga" ega.

Masalan:

• 50% uchraydigan belgi 1 bit turadi
• 25% uchraydigan 2 bit
• 37.5% uchraydigan taxminan 1.415 bit

Huffman kodi bu yerda zaif. U belgilarga qat'iy o'lchamli kodlar beradi – 1.415 bit ajratolmaysiz. Yuqoriga yaxlitlaydi, 2 bit sarflaysiz va samarasizlik paydo bo'ladi.

Arifmetik kodlash: Yangi yondashuv

Huffman o'rniga arifmetik kodlash butun belgi ketma-ketligini bit oqimi emas, bitta butun songa aylantiradi. Bu qaytariladigan matematik o'zgarish – ma'lumotni zichroq joylashtiradi.

rANS (range Asymmetric Numeral Systems) shu usulning eng chiroyli shakli. Zich siqish kutubxonalari va oqim ilovalarida ishlatiladi.

rANS qanday ishlaydi

Asosiy g'oya oddiy: "holatni" ifodalovchi bitta son x saqlaysiz. Har belgi kodlashda x ni maxsus amal orqali o'zgartirasiz. Bu amal to'liq qaytarilishi kerak – dekoder eski belgi va holatni tiklaydi.

rANS formulasi shunday:

x′ = ⌊x/f_s⌋ × M + c_s + (x mod f_s)

Bu yerda:

• f_s – belgi s chastotasi
• c_s – undan oldingi belgilarga jamlanma chastota
• M – barcha belgilarga umumiy chastota

Misol uchun, uch belgi bilan siqamiz:

| Belgi | Chastota | Jamlanma | |-------|----------|----------| | A | 4 | 0 | | B | 3 | 4 | | C | 1 | 7 |

M = 8. "ABC" ketma-ketligini 13 dan boshlab kodlaymiz:

A kodlash (f=4, c=0):

x′ = ⌊13/4⌋ × 8 + 0 + (13 mod 4) = 3 × 8 + 0 + 1 = 25

B kodlash (f=3, c=4):

x′ = ⌊25/3⌋ × 8 + 4 + (25 mod 3) = 8 × 8 + 4 + 1 = 69

69 son butun "ABC" ni saqlaydi. Dekoder teskari amallar bilan belgilarni tiklaydi. Hech qanday yo'qotish yo'q.

Nima uchun zamonaviy tizimlarda muhim

Foydalari katta:

Yaxshi siqish: rANS Shennon chegarasiga yaqinlashadi. Oddiy ma'lumotlarda Huffmandan 5-15% yaxshi.

Oqim va real vaqtda: Holat soni bo'lgani uchun butun fayl kutish shart emas.

Protsessor samarasi: Eski arifmetik usullarga qaraganda CPU ga qulay. Oddiy butun son amallari.

Amaliyotda: Facebook Zstandard (zstd) da ANS variantlari bor. Apple rasmlarda ishlatadi. Tez tizimlarning asosi.

Qaytarish muammosi va yechimi

Holati qancha kodlanganini qanday bilasiz? Yechim: holatni ma'lum oralig'ida ushlab turasiz. Katta bo'lsa, bitlarni chiqarib, davom ettirasiz. Dekoderda bitlarni qo'shib oralikka kiritasiz.

Bu o'z-o'zidan sinxronlash rANS ni mashhur qildi.

Dasturchilar uchun amaliy maslahat

NameOcean hostingidagi veb-ilovangizda siqishni tushunish foydali. API javoblarini, baza zaxiralarini yoki Vibe Hosting da saqlashni optimallashtirsangiz, Huffman va rANS farqi tezlik va xarajatlarda ko'rinadi.

Python da zstandard, JavaScript da ham tayyor kutubxonalar bor. Tadqiqot tugagan, kod sinovdan o'tgan – ilovalaringizni tezlashtiring.

Kengroq ko'rinish

rANS informatikaning muhim namunasidir: yangi g'oya emas, balki arifmetik kodlashni sodda matematika va kam resurs bilan amalga oshirish. Shennon 1948 yilda chegarani aytgan edi. rANS shu chegaraga yetkazuvchi yutuq – nazariya va amaliyot birligi.

Keyingi safar siqish kutubxonasi tez ishlasa, orqada ANS ishlayotgan bo'lishi mumkin.