Haffman ağacı

Nisbi olaraq sadə məlumat sıxlaşdırma metodu fayl üçün "Huffman ağacları" qurmaq və onu sıxlaşdırmaq və sonra açmaq üçün istifadə olunur. Əksər hallarda, binary (ikilik) Huffman ağacları istifadə olunur (yəni, hər düyün ya yarpaqdır, ya da tam iki alt-düyünü var). Lakin, istənilən sayda alt-ağacı olan Huffman ağacları da qurmaq olar (məsələn, üçüncü - tərnər və ümumi halda $N$-lik ağaclar).

$Z$ müxtəlif simvollardan ibarət fayl üçün Huffman ağacının $Z$ yarpağı var. Kökdən konkret simvolu təyin edən yarpağa gedən yol onun kodlaşdırmasını müəyyən edir; hər bir addımda ($0$, $1$, ..., N-1 ola bilər) kodlaşdırma simvolu verilir. Tez-tez rast gəlinən simvolları kökə yaxın, az rast gəlinənləri isə kökdən uzaq yerləşdirməklə, arzu edilən sıxlaşdırma əldə edilir. Dəqiq desək, belə ağac yalnız o zaman Huffman ağacıdır ki, kodlaşdırmanın nəticəsində verilmiş faylın kodlaşdırılması üçün minimal sayda $N$-lik simvoldan istifadə edilir.

Bu məsələdə yalnız o ağaclara baxılır ki, hər bir düyün ya daxili düyün, ya da simvol kodlaşdıran yarpaqdır; simvolu kodlaşdırmayan yarpaq yoxdur.

Aşağıdakı şəkildə nümunə üçün üçüncü dərəcəli (tərnər) Huffman ağacı verilib. 'a' və 'e' simvolları tək bir üçüncü dərəcəli simvolla kodlaşdırılır; 's' və 'p' az rast gəlinən simvollar iki üçüncü dərəcəli simvolla kodlaşdırılır; ən az rast gəlinən 'x', 'q' və 'y' simvolları isə hər biri üç üçüncü dərəcəli simvolla kodlaşdırılır.

Əlbəttə ki, biz daha sonra $N$-lik simvollar siyahısını geri açmaq istədikdə, hansı ağacdan istifadə olunduğunu bilməliyik. Bu, bir neçə üsulla mümkündür. Bu məsələdə biz növbəti üsuldan istifadə edirik: verilən simvollar ardıcıllığı əvvəlcədən, faylda leksikoqrafik qaydada başlıqda ardıcıl kodlaşdırılır.

$Z$ daxil simvollarının sayı, $N$ (Huffman ağacının arlığı) və başlıq verilib. Mənbə simvollarının kodlaşdırılmış ardıcıllarını bərpa edin.