Matnni siqish algoritmini ishlab chiqish va amalga oshirish
![Misol (Oddiy Tushuntirish)
Tasavvur qiling, siqmoqchi bo‘lgan matn: ABABABA
1. Dastlabki lug‘at:
Belgilar Kod
A 65
B 66
2. Kodlash jarayoni:
1. A — Lug‘atda mavjud, kod 65.
2. B — Lug‘atda mavjud, kod 66.
3. AB — Lug‘atda yo‘q, lug‘atga qo‘shiladi, yangi kod 67.
4. A — Lug‘atda mavjud, kod 65.
5. BA — Lug‘atda yo‘q, lug‘atga qo‘shiladi, yangi kod 68.
Natijada siqilgan kodlar: [65, 66, 67, 65, 68]
3.Huffman Kodlash Usuli
Huffman kodlash usuli statistik siqishga asoslanib, tez-tez uchraydigan
simvollar uchun qisqa kodlar, kam uchraydiganlari uchun esa uzunroq
kodlar belgilaydi. U optimal kodlash algoritmlaridan biri hisoblanadi va
ma'lumot uzatishda keng qo‘llaniladi. Huffman kodlash — ma'lumotlarni
yo‘qotishsiz siqish uchun ishlatiladigan optimal kodlash algoritmidir. U
David A. Huffman tomonidan 1952-yilda ishlab chiqilgan bo‘lib, tez-tez
uchraydigan belgilarni qisqa kodlar, kam uchraydigan belgilarni esa uzunroq
kodlar bilan almashtirish tamoyiliga asoslangan.](https://docx.uz/documents/d3464bf6-ec4b-4b02-9648-eaf8287666df/page_6.png?v=1)
![Python dasturlash tili yordamida amalda qanday qo‘llash mumkinligi haqida
tushuncha beriladi. Ushbu bo‘limda har bir algoritm uchun siqish va qayta
tiklash jarayonlarini ko‘rsatadigan oddiy dasturiy misollar keltiriladi.
1. LZW Algoritmini Amalda Qo‘llash
LZW algoritmi matnni ixchamlashtirish uchun ishlatiladi. Quyidagi kod
matnni siqish va qayta tiklash jarayonlarini amalga oshiradi.
Python kod:
def lzw_compress(data):
# Lug‘atni boshlang‘ich belgilar bilan yaratish
dictionary = {chr(i): i for i in range(256)}
current_string = ""
compressed_data = []
code = 256
for char in data:
new_string = current_string + char
if new_string in dictionary:
current_string = new_string
else:
compressed_data.append(dictionary[current_string])
dictionary[new_string] = code
code += 1
current_string = char
if current_string:
compressed_data.append(dictionary[current_string])
return compressed_data](https://docx.uz/documents/d3464bf6-ec4b-4b02-9648-eaf8287666df/page_10.png?v=1)
![def lzw_decompress(compressed_data):
# Lug‘atni boshlang‘ich belgilar bilan yaratish
dictionary = {i: chr(i) for i in range(256)}
code = 256
current_string = dictionary[compressed_data.pop(0)]
decompressed_data = current_string
for code_value in compressed_data:
if code_value in dictionary:
entry = dictionary[code_value]
elif code_value == code:
entry = current_string + current_string[0]
else:
raise ValueError("Kodlash xatoligi!")
decompressed_data += entry
dictionary[code] = current_string + entry[0]
code += 1
current_string = entry
return decompressed_data
# Sinov uchun:
text = "ABABABA"
compressed = lzw_compress(text)
decompressed = lzw_decompress(compressed)
print("Asl matn:", text)
print("Siqilgan:", compressed)](https://docx.uz/documents/d3464bf6-ec4b-4b02-9648-eaf8287666df/page_11.png?v=1)
![print("Tiklangan:", decompressed)
Natija:
Asl matn: ABABABA
Siqilgan: [65, 66, 256, 258]
Tiklangan: ABABABA
2. Huffman Algoritmini Amalda Qo‘llash
Huffman algoritmi belgilar chastotasiga asoslangan kodlashni amalga
oshiradi. Quyidagi dastur chastotalarni hisoblaydi, daraxt yaratadi va matnni
siqadi.
Python kod:
from heapq import heappush, heappop, heapify
from collections import defaultdict
def huffman_encode(data):
# Belgilar chastotasini hisoblash
freq = defaultdict(int)
for char in data:
freq[char] += 1
# Min-qator yaratish
heap = [[weight, [char, ""]] for char, weight in freq.items()]
heapify(heap)
while len(heap) > 1:
low = heappop(heap)
high = heappop(heap)
for pair in low[1:]:](https://docx.uz/documents/d3464bf6-ec4b-4b02-9648-eaf8287666df/page_12.png?v=1)
![pair[1] = '0' + pair[1]
for pair in high[1:]:
pair[1] = '1' + pair[1]
heappush(heap, [low[0] + high[0]] + low[1:] + high[1:])
huffman_codes = sorted(heappop(heap)[1:], key=lambda p: (len(p[-1]),
p))
return {char: code for char, code in huffman_codes}
def huffman_compress(data, huffman_codes):
return "".join(huffman_codes[char] for char in data)
def huffman_decompress(compressed_data, huffman_codes):
reverse_codes = {v: k for k, v in huffman_codes.items()}
decoded = ""
current_code = ""
for bit in compressed_data:
current_code += bit
if current_code in reverse_codes:
decoded += reverse_codes[current_code]
current_code = ""
return decoded
# Sinov uchun:
text = "ABACCDA"
huffman_codes = huffman_encode(text)
compressed = huffman_compress(text, huffman_codes)
decompressed = huffman_decompress(compressed, huffman_codes)
print("Asl matn:", text)](https://docx.uz/documents/d3464bf6-ec4b-4b02-9648-eaf8287666df/page_13.png?v=1)
![LZW Algoritmi:
Lug‘at:
Belgilar Kod
A 65
B 66
AB 256
ABA 257
BAB 258
Siqilgan natija: [65, 66, 256, 256, 256]
Asl matn uzunligi: 22 bayt
Siqilgan matn uzunligi: 5 ta kod (10 bayt)
Siqish darajasi:
Siqish darajasi=Asl uzunlik−Siqilgan uzunlikAsl uzunlik×100=22−10
22×100≈54.55%\text{Siqish darajasi} = \frac{\text{Asl uzunlik} - \
text{Siqilgan uzunlik}}{\text{Asl uzunlik}} \times 100 = \frac{22 -
10}{22} \times 100 \approx 54.55\%
Huffman Algoritmi:
Belgilar chastotasi:
Belgilar Chastota Kod
A 11 0
B 11 1
Siqilgan natija: 01010101010101010101](https://docx.uz/documents/d3464bf6-ec4b-4b02-9648-eaf8287666df/page_16.png?v=1)
Matnni siqish algoritmini ishlab chiqish va amalga oshirish