..

Huffman algoritmi va zip haqida yuz gram!

Loyihani qo'llab quvvatlash uchub buyerga bosing

• Bosqichlar:
• PHP misolida
• Xulosa

Yaqinda bir loyiha ustida ishlash chog’ida php va c orasida baza fayli almashinishga to’g’ri kelib qoldi. PHPdagi struktura json ustiga qurilgan ammo buni Cda qayta ishlash toza bosh og’riqlardan biri, shu sababli o’zimning strukturamga ega bazani ko’tarishga qaror qildim. Asosiy muammo bu strukturada emas, balkim struktura faylini qisqartirishda edi. Ya’ni mendagi ehtiyoj buyruqlarni qidirish bo’lgani sababli kalit so’zlarni indeksatsiya qilish zarurati bor, bu degani yetarli katta hajmdagi matn fayli hosil bo’ladi. Demak hajmni qisqartirish kerak. Menimcha bunday maqsad uchun huffman algoritmidan yaxshiroq variant bo’lmasa kerak.

Huffman algoritmi: - 1952-yilda David Huffman tomonidan ishlab chiqilgan ushbu algoritm kirish sifatida berilgan ma’lumotni undagi belgilar qatnashish chastotasi yoki o’rniga qarab qisqaroq kodlar bilan belgilashni o’z oldiga maqsad qilib qo’yadi.

Bosqichlar:»

Kirish: “salom dunyo”

1. Chastotani tahlil qilish

Algoritm kirish ma’lumotlaridagi har bir belgining chastotasini tahlil qilishdan boshlanadi.

s: 1
a: 1
l: 1
o: 2
m: 1
(space): 1
d: 1
u: 1
n: 1
y: 1

2. Huffman daraxtini qurish

Bu bosqichda Huffman daraxti deb ataladigan ikki o’lchamlik massivni oziga struktura deb oladigan to’plam quriladi. Daraxt sifatida qaralganda bu yerda har bir barg tugunlari belgi va uning chastotasini ifodalaydi.

Barg tugunlari:

(s:1) (a:1) (l:1) (o:2) (m:1) (space:1) (d:1) (u:1) (n:1) (y:1)

Huffman daraxti:

                (o:2, s:1, a:1)
                   /             \
          (o:2)                 (s:1, a:1)
          /    \                 /          \
    (o:2)     (space:1)    (s:1)           (a:1)
                           /   \           /    \
                      (l:1) (m:1)      (d:1) (u:1, n:1)
                                           \
                                           (y:1)

Kodlarni ajratish:

Har bir belgilar daraxtdagi chap va o’ng harakatlar mos ravishda ikkilik sanoq tizimida belgilab chiqiladi.

s: 010
a: 1101
l: 1111
o: 101
(space): 1100
d: 1110
u: 011
y: 100

Huffman kodlari jadvalini yaratish:

Yakuniy bosqich har bir belgiga tegishli Huffman kodi bilan taqqoslaydigan jadval yaratishni o’z ichiga oladi.

Natija:

0101101111110100011001110011001100101

PHP misolida»

$string = "Salom dunyo";

1. Chastotani hisoblash

$originalString = $string;
$occurrences = array();

while (isset($string[0])) {
    $occurrences[] = array(substr_count($string, $string[0]), $string[0]);
    $string = str_replace($string[0], '', $string);
}

[
    [0] => [1, 's']
    [1] => [1, 'a']
    [2] => [1, 'l']
    [3] => [2, 'o']
    [4] => [1, 'm']
    [5] => [1, ' ']
    [6] => [1, 'd']
    [7] => [1, 'u']
    [8] => [1, 'n']
    [9] => [1, 'y']
]

2. Yuqoridagi natijani chastotaning o’sish darajasiga qarab saralaymiz:

sort($occurrences);

3. Huffman daraxtini yasash

Bu blokda $occurrences massivida faqat bitta element qolguncha davom etadigan sikl mavjud. Har bir iteratsiyada u ikkita eng kichik elementni (belgi yoki belgilar massivi) oladi, ularni hisoblab yig’indisi bilan yangi massivga birlashtiradi va bu yangi massivni yana $occurrences ga qo’shadi. Keyin massiv yana tartiblanadi.

while (count($occurrences) > 1) {
    $row1 = array_shift($occurrences);
    $row2 = array_shift($occurrences);
    $occurrences[] = array(
	    $row1[0] + $row2[0], array($row1, $row2)
	);
    sort($occurrences);
}

Tatija:

[
    [0] => [11, 
        [4, 
            [2, [1, 'm'], [1, 'n']], 
            [7, 
                [3, [1, 'y'], [2, 'o']], 
                [4, 
                    [2, [1, ' '], [1, 'a']], 
                    [2, [1, 'd'], [1, 'l']]
                ]
            ]
        ]
    ]
]

4. Huffman lug’atini to’ldirish

Bu boqichda bo’sh $dictionary massivi ishga tushiriladi. fillDictionary funksiyasi rekursiya orqali Huffman daraxtining har bir belgisi uchun ikkilik kodlarini yaratadi. Huffman daraxti, belgilar massivi yoki ikkita kichik massivni o’z ichiga olgan massiv bo’lishi mumkin.

function fillDictionary(&$dictionary, $data, $value = '') {
    if (!is_array($data[0][1])) {
        $dictionary[$data[0][1]] = $value.'0';
    } else {
        fillDictionary($dictionary, $data[0][1], $value.'0');
    }
    if (isset($data[1])) {
        if (!is_array($data[1][1])) {
            $dictionary[$data[1][1]] = $value.'1';
        } else {
            fillDictionary($dictionary, $data[1][1], $value.'1');
        }
    }
}

$dictionary = [];
fillDictionary($dictionary, is_array($occurrences[0][1]) ? $occurrences[0][1] : $occurrences);

Natija:

[
    [m] => 000
    [n] => 001
    [s] => 010
    [u] => 011
    [y] => 100
    [o] => 101
    [ ] => 1100
    [a] => 1101
    [d] => 1110
    [l] => 1111
]

5. Huffman kodlarini belgilash:

Bu bosqich yaratilgan Huffman kodlari yordamida kirish matnni kodlaydi. U kirish matnidagi har bir belgi boʻylab takrorlanadi va oʻzining tegishli Huffman kodini $encoded satriga qoʻshadi.

$encoded = '';
for ($i = 0; $i < strlen($originalString); $i++) {
    $encoded .= $dictionary[$originalString[$i]];
}

6. Natija

Kirish matni:

Kirilgan matndagi belgilar uchun sarflangan xotirani ASCII jadvalani orqali hisoblashimiz mumkin. ASCII bo’yicha har bir belgi 7 yoki 8 bit bilan ifodalanadi.

Hisoblash:

Belgilar soni * Har bir belgi uchun bit = Umumiy xotira

Demak “Salom dunyo” uchun:

11 ta belgi * 8 bit = 88 bit

Umumiy belgilanga xotira: 88 bit

Huffman kodi:

Ikkilik sondagi har bir 1 yoki 0 bit deyiladi. Bizdagi natija 37 bit. Tejalgan xotira esa 51 bit.

0101101111110100011001110011001100101

To’liq kod: Gihub gist

Xulosa»

Zip haqidagi gaplar qayerda deysizmi? Zip fayli Huffman va LZ77 algoritmlari bilan umumlashtirilgan holda ishlaydi. Shuning o’zi zip haqida yuz gramlik info bo’la olar degan umiddaman.