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

Aşşık, M. Mustafa; Oral, Mustafa

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

Mustafa ORAL, (Çukurova Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Adana, Türkiye)

M. Mustafa AŞŞIK (Çukurova Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Adana, Türkiye)

Çukurova Üniversitesi Mühendislik-Mimarlik Fakültesi Dergisi

2 1

Yıl: 2019 Cilt: 24 Sayı: 4 Sayfa Aralığı: 9 - 20 Metin Dili: Türkçe İndeks Tarihi: 18-10-2020

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 “prefixfree”özelliğine sahip değişken uzunluklu kanonik kodların üretilmesine temel olacak uzunlukları cebirselyöntemle tek aşamada hesaplayacak bir algoritma önerilmektedir. Ancak, elde edilen kodların “sembolbaşına ortalama bit uzunluğu” genellikle optimum olmayıp, optimuma benzerlerinden daha yakındır. Koduzunlukları, 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, koduzunluklarını li= round (log(ei/pi)) formülüne göre hesaplar. Son olarak, kanonik formdaki kodlarhesaplanan uzunluklardan elde edilir. Tüm süreç ϴ(n) zamanda tamamlanır ve ϴ(n) kelime uzunluğundahafıza kullanılır.

Anahtar Kelime:

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

Ö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 Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

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.

APA	Oral M, Aşşık M (2019). Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma. , 9 - 20.
Chicago	Oral Mustafa,Aşşık M. Mustafa Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma. (2019): 9 - 20.
MLA	Oral Mustafa,Aşşık M. Mustafa Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma. , 2019, ss.9 - 20.
AMA	Oral M,Aşşık M Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma. . 2019; 9 - 20.
Vancouver	Oral M,Aşşık M Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma. . 2019; 9 - 20.
IEEE	Oral M,Aşşık M "Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma." , ss.9 - 20, 2019.
ISNAD	Oral, Mustafa - Aşşık, M. Mustafa. "Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma". (2019), 9-20.

APA	Oral M, Aşşık M (2019). Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma. Çukurova Üniversitesi Mühendislik-Mimarlik Fakültesi Dergisi, 24(4), 9 - 20.
Chicago	Oral Mustafa,Aşşık M. Mustafa Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma. Çukurova Üniversitesi Mühendislik-Mimarlik Fakültesi Dergisi 24, no.4 (2019): 9 - 20.
MLA	Oral Mustafa,Aşşık M. Mustafa Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma. Çukurova Üniversitesi Mühendislik-Mimarlik Fakültesi Dergisi, vol.24, no.4, 2019, ss.9 - 20.
AMA	Oral M,Aşşık M Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma. Çukurova Üniversitesi Mühendislik-Mimarlik Fakültesi Dergisi. 2019; 24(4): 9 - 20.
Vancouver	Oral M,Aşşık M Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma. Çukurova Üniversitesi Mühendislik-Mimarlik Fakültesi Dergisi. 2019; 24(4): 9 - 20.
IEEE	Oral M,Aşşık M "Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma." Çukurova Üniversitesi Mühendislik-Mimarlik Fakültesi Dergisi, 24, ss.9 - 20, 2019.
ISNAD	Oral, Mustafa - Aşşık, M. Mustafa. "Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma". Çukurova Üniversitesi Mühendislik-Mimarlik Fakültesi Dergisi 24/4 (2019), 9-20.