Sertifikat olingYANGIW3Schools ilovasiiOS va AndroidSarguzashtni boshlang

DSA Huffman kodlash

ULASHISH

Huffman kodlash

Huffman kodlash — ma’lumotlarni yo‘qotishsiz siqish uchun ishlatiladigan algoritm.

Huffman kodlash ko‘plab turli siqish algoritmlarida tarkibiy qism sifatida ham ishlatiladi. U zip, gzip va png kabi yo‘qotishsiz siqishlarda, hatto mp3 va jpeg kabi yo‘qotishli siqish algoritmlarida ham tarkibiy qism sifatida qo‘llaniladi.

Matnni Huffman kodlash yordamida qanday siqish mumkinligini ko‘rish uchun quyidagi animatsiyadan foydalaning.

Matn:
{{ el.letter }}
{{inpComment}}
Huffman kodi:
{{ el.code }}
UTF-8:
{{ el.code }}

{{ huffmanBitCount }} bit

{{ utf8BitCount }} bit

Natija Huffman kodi asl hajmning {{compression}}% qismini tashkil qiladi.

Animatsiya matndagi harflar odatda UTF-8 yordamida qanday saqlanishini va Huffman kodlash xuddi shu matnni kamroq bitlar bilan saqlash imkonini qanday berishini ko‘rsatadi.

Qanday ishlaydi:

  1. Har bir ma’lumot bo‘lagi necha marta uchrashini sanang.
  2. Eng kam uchraydigan tugunlardan boshlab ikkilik daraxt quring. Yangi ota tugunning soni uning bola tugunlari sonlari yig‘indisiga teng bo‘ladi.
  3. Ota tugundan chiqadigan qirra chap bola uchun '0', o‘ng bolaga boradigan qirra esa '1' qiymatini oladi.
  4. Tayyor ikkilik daraxtda har bir ma’lumot bo‘lagining yangi Huffman kodini topish uchun ildiz tugundan boshlab qirralar bo‘ylab yuring va har bir tarmoq uchun '0' yoki '1' qo‘shib boring.
  5. Ikkilik daraxt yordamida ma’lumotlarni bo‘lakma-bo‘lak ikkilik kodga o‘girib, Huffman kodini hosil qiling.

Huffman kodlash har bir ma’lumot bo‘lagini ifodalash uchun o‘zgaruvchan uzunlikdagi bitlardan foydalanadi: tez-tez uchraydigan ma’lumot bo‘laklari qisqaroq bitlar bilan ifodalanadi.

Bundan tashqari, Huffman kodlash hech bir kod boshqa kodning prefiksi bo‘lmasligini ta’minlaydi, bu esa siqilgan ma’lumotlarni dekodlashni osonlashtiradi.

Ma’lumotlarni siqish — asl ma’lumotlar hajmi kichraytirilib, axborot esa asosan yoki to‘liq saqlanib qolishi. Masalan, ovoz yoki musiqa fayllari odatda siqilgan formatda saqlanadi: ular asl ma’lumotlar hajmining taxminan atigi 10 foizini egallaydi, lekin axborotning katta qismi saqlanib qoladi.

Yo‘qotishsiz (lossless) siqish ma’lumotlar siqilgandan keyin ham barcha axborot saqlanib qolishini anglatadi. Masalan, siqilgan matnda asl nusxadagi barcha harflar va belgilar saqlanib qoladi.

Yo‘qotishli (lossy) siqish — ma’lumotlarni siqishning boshqa turi bo‘lib, unda ma’lumotlarni yanada ko‘proq siqish uchun asl axborotning bir qismi yo‘qotiladi yoki qurbon qilinadi. Musiqa, tasvirlar va videolar odatda mp3, jpeg va mp4 kabi yo‘qotishli siqish bilan saqlanadi va uzatiladi (streaming).

Huffman kodini qo‘lda yaratish

Huffman kodlash qanday ishlashini yaxshiroq tushunish uchun animatsiyadagi 'lossless' matnidan foydalanib, Huffman kodini qo‘lda yaratamiz.

Kompyuterda matn odatda UTF-8 yordamida saqlanadi, ya’ni 'lossless' so‘zidagi kabi oddiy lotin harflarining har biri 8 bit yordamida saqlanadi. '€' yoki '🦄' kabi boshqa harflar yoki belgilar ko‘proq bit yordamida saqlanadi.

'lossless' matnini Huffman kodlash yordamida siqish uchun avval har bir harfni sanashdan boshlaymiz.

{{ line.label }} {{node.letter}} {{node.freq}} {{ node.code }}

Yuqoridagi tugunlarda ko‘rib turganingizdek, 's' 4 marta, 'l' 2 marta, 'o' va 'e' esa bittadan uchraydi.

Daraxtni eng kam uchraydigan 'o' va 'e' harflaridan qura boshlaymiz, ularning ota tuguni '2' sonini oladi, chunki 'o' va 'e' harflarining sonlari qo‘shiladi.

{{ line.label }} {{node.letter}} {{node.freq}} {{ node.code }}

Yangi ota tugun oladigan keyingi tugunlar — eng kichik soniga ega tugunlar: 'l' hamda 'o' va 'e' ning ota tuguni.

{{ line.label }} {{node.letter}} {{node.freq}} {{ node.code }}

Endi oxirgi 's' tuguni ikkilik daraxtga qo‘shilishi kerak. 's' harf tuguni va soni '4' bo‘lgan ota tugun soni '8' bo‘lgan yangi ota tugunni oladi.

{{ line.label }} {{node.letter}} {{node.freq}} {{ node.code }}

Endi ildiz tugundan qirralar bo‘ylab yurib, 'lossless' so‘zidagi har bir harf uchun Huffman kodini aniqlashimiz mumkin.

{{ line.label }} {{node.letter}} {{node.freq}} {{ node.code }}

Endi har bir harfning Huffman kodini yuqoridagi rasmda har bir harf tuguni ostida ko‘rish mumkin. Huffman kodlashning yaxshi tomoni shundaki, eng ko‘p ishlatiladigan ma’lumot bo‘laklari eng qisqa kodni oladi, shuning uchun 's' harfining kodi shunchaki '0'.

Yuqorida aytilganidek, bunday oddiy lotin harflari odatda UTF-8 bilan saqlanadi, ya’ni ularning har biri 8 bit joy egallaydi. Masalan, 'o' harfi UTF-8 bilan '01101111' ko‘rinishida saqlanadi, ammo 'lossless' so‘zi uchun tuzgan Huffman kodimizda u '110' ko‘rinishida saqlanadi.

Eslatma: UTF-8 da harf har doim bir xil ikkilik kodga ega bo‘ladi, Huffman kodida esa har bir harf (ma’lumot bo‘lagi) uchun ikkilik kod biz siqayotgan matnga (ma’lumotlar to‘plamiga) qarab o‘zgaradi.

Xulosa qilib aytganda, biz 'lossless' so‘zini Huffman kodlash yordamida uning UTF-8 kodidan

01101100 01101111 01110011 01110011 01101100 01100101 01110011 01110011

atigi quyidagi ko‘rinishgacha siqdik:

10 110 0 0 10 111 0 0

Bu juda katta yaxshilanish.

Ammo ma’lumotlar Huffman kodlash bilan 10 110 0 0 10 111 0 0 ko‘rinishida saqlangan bo‘lsa yoki kod bizga yuborilsa, Huffman kodida qanday axborot borligini ko‘rish uchun uni qanday dekodlash mumkin?

Bundan tashqari, ikkilik kod aslida bo‘sh joylarsiz 10110001011100 ko‘rinishida bo‘ladi va har bir ma’lumot bo‘lagi uchun bitlar uzunligi turlicha. Xo‘sh, kompyuter har bir ma’lumot bo‘lagining ikkilik kodi qayerda boshlanib, qayerda tugashini qanday tushunadi?

Huffman kodini dekodlash

Kompyuterlarimiz to‘g‘ri harflarga dekodlay oladigan, UTF-8 ko‘rinishida saqlangan kod kabi, Huffman kodida ham kompyuter qaysi bitlar qaysi ma’lumot bo‘lagini ifodalashini bilishi kerak.

Shuning uchun Huffman kodi bilan birga uni dekodlash mumkin bo‘lishi uchun har bir ma’lumot bo‘lagining Huffman ikkilik kodi qanday ekani haqidagi ma’lumotni o‘z ichiga olgan moslik jadvali ham bo‘lishi kerak.

Demak, ushbu Huffman kodi uchun:

100110110

Ushbu moslik jadvali bilan:

Harf Huffman kodi
a 0
b 10
n 11

Huffman kodini dekodlay olasizmi?

Qanday ishlaydi:

  1. Huffman kodining chap tomonidan boshlang va har bir bitlar ketma-ketligini jadvaldan qidiring.
  2. Har bir kodni unga mos harf bilan moslang.
  3. Butun Huffman kodi dekodlanguncha davom eting.

Birinchi bitdan boshlaymiz:

1
0
0
1
1
0
1
1
0

Jadvalda Huffman kodi faqat 1 bo‘lgan harf yo‘q, shuning uchun davom etamiz va keyingi bitni ham qo‘shamiz.

1
0
0
1
1
0
1
1
0

Jadvaldan 10 bu 'b' ekanini ko‘ramiz, demak, birinchi harfni topdik. Keyingi bitni tekshiramiz:

1
0
0
1
1
0
1
1
0

0 bu 'a' ekanini topamiz, demak, endi Huffman kodida saqlangan dastlabki ikki harf — 'ba' ni oldik.

Jadvaldan Huffman kodlarini qidirishda davom etamiz:

1
0
0
1
1
0
1
1
0

11 kodi — 'n'.

1
0
0
1
1
0
1
1
0

0 kodi — 'a'.

1
0
0
1
1
0
1
1
0

11 kodi — 'n'.

1
0
0
1
1
0
1
1
0

0 kodi — 'a'.

Huffman kodi endi dekodlandi, so‘z esa — 'banana'!

Huffman kodi prefikslari

Huffman kodlash algoritmining qiziqarli va juda foydali jihati shundaki, u hech bir kod boshqa kodning prefiksi bo‘lmasligini ta’minlaydi.

Tasavvur qiling, hozirgina foydalangan moslik jadvalimiz quyidagicha ko‘rinishda bo‘lsa:

Harf Huffman kodi
a 1
b 10
n 11

Agar shunday bo‘lganida, dekodlashning boshidanoq chalkashib qolardik, to‘g‘rimi?

1
0
0
1
1
0
1
1
0

Chunki birinchi bit 1 'a' harfini ifodalaydimi yoki u 'b' yoki 'c' harfining birinchi bitimi, buni qanday bilamiz?

Hech bir kod boshqa kodning prefiksi bo‘lmasligi xususiyati dekodlashni mumkin qiladi. Bu, ayniqsa, bitlar uzunligi o‘zgaruvchan bo‘lgani sababli Huffman kodlashda juda muhim.

Huffman kodlashni amalga oshirish

Ma’lumotlar yoki matn asosida Huffman kodini yaratishning to‘g‘ri nomi "kodlash" (encoding), uning teskarisi, ya’ni asl ma’lumotlar yoki matnni kod asosida qayta tiklash esa "dekodlash" (decoding) deb ataladi.

Quyidagi kod misoli so‘zni, aslida istalgan matnni oladi va uni Huffman kodlash yordamida siqadi.

Misol

Huffman kodlash.

class Node:
    def __init__(self, char=None, freq=0):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

nodes = []

def calculate_frequencies(word):
    frequencies = {}
    for char in word:
        if char not in frequencies:
            freq = word.count(char)
            frequencies[char] = freq
            nodes.append(Node(char, freq))

def build_huffman_tree():
    while len(nodes) > 1:
        nodes.sort(key=lambda x: x.freq)
        left = nodes.pop(0)
        right = nodes.pop(0)
        
        merged = Node(freq=left.freq + right.freq)
        merged.left = left
        merged.right = right
        
        nodes.append(merged)

    return nodes[0]

def generate_huffman_codes(node, current_code, codes):
    if node is None:
        return

    if node.char is not None:
        codes[node.char] = current_code

    generate_huffman_codes(node.left, current_code + '0', codes)
    generate_huffman_codes(node.right, current_code + '1', codes)

def huffman_encoding(word):
    global nodes
    nodes = []
    calculate_frequencies(word)
    root = build_huffman_tree()
    codes = {}
    generate_huffman_codes(root, '', codes)
    return codes

word = "lossless"
codes = huffman_encoding(word)
encoded_word = ''.join(codes[char] for char in word)

print("Word:", word)
print("Huffman code:", encoded_word)
print("Conversion table:", codes)
O‘zingiz sinab ko‘ring »

Huffman dekodlashni amalga oshirish

Ma’lumotlarni Huffman kodlash yordamida kodlashdan tashqari, asl axborotni qayta tiklash uchun ularni dekodlash usuli ham bo‘lishi kerak.

Quyidagi amalga oshirish oldingi kod misoli bilan deyarli bir xil, faqat unda Huffman kodini dekodlash uchun qo‘shimcha funksiya bor.

huffman_decoding funksiyasi Huffman kodini hamda belgilar va ularga mos ikkilik kodlar saqlangan codes Python dictionaryni (hashmap) qabul qiladi. So‘ngra funksiya moslikni teskari aylantiradi va asl matnni qayta tiklash uchun Huffman kodini bitma-bit tekshiradi.

Misol

Huffman dekodlash.

class Node:
    def __init__(self, char=None, freq=0):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

nodes = []

def calculate_frequencies(word):
    frequencies = {}
    for char in word:
        if char not in frequencies:
            freq = word.count(char)
            frequencies[char] = freq
            nodes.append(Node(char, freq))

def build_huffman_tree():
    while len(nodes) > 1:
        nodes.sort(key=lambda x: x.freq)
        left = nodes.pop(0)
        right = nodes.pop(0)
        
        merged = Node(freq=left.freq + right.freq)
        merged.left = left
        merged.right = right
        
        nodes.append(merged)

    return nodes[0]

def generate_huffman_codes(node, current_code, codes):
    if node is None:
        return

    if node.char is not None:
        codes[node.char] = current_code

    generate_huffman_codes(node.left, current_code + '0', codes)
    generate_huffman_codes(node.right, current_code + '1', codes)

def huffman_encoding(word):
    global nodes
    nodes = []
    calculate_frequencies(word)
    root = build_huffman_tree()
    codes = {}
    generate_huffman_codes(root, '', codes)
    return codes

def huffman_decoding(encoded_word, codes):
    current_code = ''
    decoded_chars = []

    # Invert the codes dictionary to get the reverse mapping
    code_to_char = {v: k for k, v in codes.items()}

    for bit in encoded_word:
        current_code += bit
        if current_code in code_to_char:
            decoded_chars.append(code_to_char[current_code])
            current_code = ''

    return ''.join(decoded_chars)

word = "lossless"
codes = huffman_encoding(word)
encoded_word = ''.join(codes[char] for char in word)
decoded_word = huffman_decoding(encoded_word, codes)

print("Initial word:", word)
print("Huffman code:", encoded_word)
print("Conversion table:", codes)
print("Decoded word:", decoded_word)
O‘zingiz sinab ko‘ring »

Endi siz matnni Huffman kodlash yordamida qanday siqish mumkinligini va asl matnni qayta tiklash uchun Huffman kodini qanday dekodlash mumkinligini ko‘rdingiz.

Eslatma: Huffman kodlash nafaqat matnni, balki istalgan turdagi ma’lumotlarni yo‘qotishsiz siqish uchun ishlatilishi mumkin. Huffman kodlash zip kabi boshqa siqish algoritmlarida, hatto jpeg va mp3 kabi yo‘qotishli siqishlarda ham tarkibiy qism sifatida qo‘llaniladi.


‹ OrqagaKeyingisi

W3Schools Pathfinder

Yutuqlaringizni kuzating – bu bepul!

Ro'yxatdan o'tishKirish