Dergiler / Çukurova Üniversitesi Mühendislik Fakültesi dergisi / 2019 / Cilt: 34 Sayı: 4
Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma
- Sayfa
- 9–20
- DOI
- —
Özet
Kanonik Huffman kodları için gerekli olan kod uzunlukları iki aşamada üretilir. Bu makalede “prefix-free” özelliğine sahip değişken uzunluklu kanonik kodların üretilmesine temel olacak uzunlukları cebirsel yöntemle tek aşamada hesaplayacak bir algoritma önerilmektedir. Ancak, elde edilen kodların “sembol başına ortalama bit uzunluğu” genellikle optimum olmayıp, optimuma benzerlerinden daha yakındır. Kod uzunlukları, ağırlık dizisinin sıralı olması şartıyla, en sık kullanılan sembolden başlayarak hesaplanır. Önerilen algoritma; pi, i. sembolün olasılığı ve ei de kalan olasılıkların toplamı olmak üzere, kod uzunluklarını li= round (log(ei/pi)) formülüne göre hesaplar. Son olarak, kanonik formdaki kodlar hesaplanan uzunluklardan elde edilir. Tüm süreç ϴ(n) zamanda tamamlanır ve ϴ(n) kelime uzunluğunda hafıza kullanılır.
Abstract
The lengths of codewords required for canonical Huffman codes are produced in two stages. An algorithm that calculate the lengths required for the production of prefix-free canonical codes in single stage by algebraic method is proposed in this paper. The “average bit length per symbol” of the resulting code is usually not optimal, but it is closer to optimal than similar ones. The lengths of the codewords are calculated starting from the most frequently used symbol, provided that the weight array is ordered. The proposed algorithm calculates the lengths of the codewords using the formula li= round (log(ei/pi)) where pi is the probability of i-th symbol and ei is the sum of the remaining probabilities. Finally, the codes in the canonical form are obtained from the calculated lengths. The whole process is completed in ϴ(n) time and uses ϴ(n) words memory, where n is the number of symbols.