Video Malumotlarni Yo’qotishsiz Siqish Usullari

Hufman algoritmi

• Misol: Xolmuminov Yusuf Xolbuta o’g’li.
• Ushbu matnni Huffman algoritmi yordamida siqishmi ko’rib chiqamiz.
• Har bir harf va bo’sh joyimiz 1 bayt ya’ni 8 bit hajmga ega, yuqoridagi axborotimiz 31x8=248 bit hajmga ega. Uning takororlanish chastotalarini aniqlaymiz.

Chastotasi	Гц	Chastotasi	Гц
X	2	s	1
o	4	f	1
l	3	b	1
m	2	t	1
u	4	a	1
i	2	g	1
n	1	_	3
v	1	‘	2
Y	1

Huffman algoritmi

• Birinchi o’rinda berilgan ma’lumotlarni ASCII kodiga convert qilinishimiz kerak.
• X 1011000 u 1110101 o 1101111
• o 1101111 s 1110011 ‘ 0100111
• l 1101100 u 1110101 g 1100111
• m 1101101 f 1100110 ‘ 0100111
• u 1110101 _ 1011111 l 1101001
• m 1101101 X 1011000 i 1110001
• i 1101001 o 1101111
• n 1101110 l 1101100
• o 1101111 b 1100010
• v 1110110 u 1110101
• _ 1011111 t 1110100
• Y 1011001 a 1000001
• _ 1011111

217 bit

Huffman algoritmi

• Yuqorida takrorlanuvchi harflarni binary usulida daraxt shakliga keltirib olamiz.

i	a	t	_	u	r	n	z	o	s
4	4	3	3	2	2	2	2	2	1

2
l
y
2
e
u
2
k
q
1
1
1
1
1
1

Huffman algoritmi

i	a	t	_	u	r	n	z
4	4	3	3	2	2	2	2

3
2
2
2
o
s
l
y
e
u
k
q
2
1
1
1
1
1
1
1

Huffman algoritmi

8
i
a
6
t
_
4
u
r
4
n
z
3
o
s
2
l
y
2
e
v
2
k
q
2
2
2
2
2
1
1
1
1
1
1
3
3
4
4
1

Huffman algoritmi

14
8
31
i
a
6
t
_
17
9
8
4
4
u
r
n
z
5
4
3
2
o
s
l
y
2
2
e
v
k
q
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0