An Algorithm that Calculates the Lengths of Codewords Algebraically for Canonical Huffman-like Encoding

Yıl 2019, Cilt: 34 Sayı: 4, 9 - 20, 31.12.2019

Mustafa Oral M. Mustafa Aşşık

https://doi.org/10.21605/cukurovaummfd.702021

Cited By: 2

Öz

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.

Anahtar Kelimeler

Data compression, Encoding, Huffman algorithm, Canonical form, Prefix free codes

Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma

Öz

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.

Anahtar Kelimeler

Veri sıkıştırma, Kodlama, Huffman, Kanonik form, Prefix-free kodlar

Kaynakça

• 1. Huffman, D., 1952. A Method for the Construction of Minimum Redundancy Codes, Proceedings of the IRE, 40(9), 1098-1101.
• 2. Moffat, A., Katajainen, J., 1995. In-place Calculation of Minimum-redundancy Codes, In: Akl S.G., Dehne F., Sack JR., Santoro N. (eds) Algorithms and Data Structures. WADS 1995. Lecture Notes in Computer Science, 955. Springer, Berlin, Heidelberg.
• 3. Moffat, A., Turpin, A., 1998. Efficient Construction of Minimum-redundancy Codes for Large Alphabets, in IEEE Transactions on Information Theory, 44(4), 1650-1657.
• 4. Geldreich, R., lzham-Fyffe Codes.wiki, https://code.google.com/archive/p/lzham/wikis/ FyffeCodes.wiki, Son Erişim: 25.04.2019.
• 5. Polar, A., Non-Huffman Binary Tree, http://www.ezcodesample.com/prefixer/prefixe r_article.html, Last Access 25.04.2019.
• 6. Dubé, D., Beaudoin, V., 2008. Fast Construction of Disposable Prefix-Free Codes, Comptes-rendus du International Colloquium on Signal Processing and its Applications, Kuala Lumpur, Malaisie, 49-54.
• 7. Hosseini, M., 2012. A Survey of Data Compression Algorithms and their Applications, 10.13140/2.1.4360.9924.
• 8. Navarro, G., Ordóñez, A., 2013. Compressing Huffman Models on Large Alphabets, In Proc. 23rd Data Compression Conference (DCC), 381–390.
• 9. Shahbahrami, A., Bahrampour, R., Rostami, M.S., Mobarhan, M.A., 2011. Evaluation of Huffman and Arithmetic Algorithms for Multimedia Compression Standards, International Journal of Computer Science, Engineering and Applications (IJCSEA), 1(4),
• 10. Moffat, A., Turpin, A., 1997. On the Implementation of Minimum Redundancy Prefix Codes, in IEEE Transactions on Communications, 45(10), 1200-1207.
• 11. Leeuwen, J.Van., 1976. On the Construction of Huffman Trees, ICALP, 382-410.
• 12. Barbay, J., 2016. Optimal Prefix Free Codes with Partial Sorting, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) 29, 1–13.
• 13. Chen, Y., Wan, G.C., Xia, Z.W., Tong, M.S., 2017. A Hardware Design Method for Canonical Huffman Code, 2017 Progress in Electromagnetics Research Symposium-Fall (PIERS - FALL), Singapore, 2212-2215.
• 14. Moffat, A., Witten, I.H., Bell, T.C., 1999. Managing Gigabytes: Compressing and Indexing Documents and Images, Second Edition, Academic Press, 36.
• 15. Connell, J.B., 1973. A Huffman-Shannon-Fano Code, in Proceedings of the IEEE, 61(7), 1046-1047.
• 16. Nekritch, Y., 2000. Byte-oriented Decoding of Canonical Huffman Codes, 2000 IEEE International Symposium on Information Theory (Cat. No.00CH37060), Sorrento, 371.
• 17. Chen, Y., Wan, G.C., Xia, Z.W., Tong, M.S., 2017. A Hardware Design Method for Canonical Huffman Code, Progress in Electromagnetics Research Symposium-Fall (PIERS - FALL), Singapore, 2212-2215.
• 18. Shannon, C.E., 1948. A Mathematical Theory of Communication, in the Bell System Technical Journal, 27(4), 623-656.