Apa kompleksitas komputasi kode bebas awalan yang optimal, ketika frekuensinya serupa?

Sudah diketahui bahwa ada algoritma optimal kasus terburuk untuk menghitung kode Huffman dalam waktu . Ini ditingkatkan dalam dua cara ortogonal:$\theta(n\lg n)$

1. Kode bebas awalan yang optimal dapat dihitung lebih cepat jika rangkaian frekuensi yang berbeda kecil (misalnya ukuran ): mengurutkan frekuensi menggunakan [Munro dan Spira, 1976] sehingga untuk mengambil keuntungan dari nilai kecil σ , dan menghitung Huffman pohon dalam waktu linier dari frekuensi yang diurutkan. Ini menghasilkan solusi dalam O ( n lg σ $\sigma$$\sigma$$O(n\lg\sigma)$

2. Ada algoritma untuk menghitung kode yang setara di mana k adalah jumlah panjang codeword yang berbeda [Belal dan Elmasry].$O(n 16^k)$$k$

Apakah ada cara untuk menggabungkan teknik-teknik itu, untuk meningkatkan kompleksitas terbaik saat ini ( n min { 16 k , lg σ } ) ?$O(n\min\{16^k,\lg\sigma\})$

THE HASIL DARI STACS 2006 TAMPAK SALAH$O(nk)$ , Elmasry diterbitkan pada ARXIV pada 2010 (http://arxiv.org/abs/cs/0509015) versi yang mengumumkan - operasi pada input yang tidak disortir dan - O ( 9 k log 2 k - 1 n ) operasi pada input yang diurutkan$O(16^kn)$$O(9^k \log^{2k-1} n)$

1. Saya melihat analogi dengan kompleksitas komputasi planar convex hull, di mana algoritma dalam (berdasarkan penyortiran, sebagai algoritma O ( n lg n ) untuk kode Huffman) dan dalam O ( n h ) (pembungkus kado) ) digantikan oleh algoritma Kirkpatrick dan Seidel dalam O ( n lg h ) (kemudian terbukti optimal dengan kompleksitas bentuk O ( n H ( n 1 , … , n $O(n\lg n)$$O(n\lg n)$$O(nh)$$O(n\lg h)$ ). Dalam kasus kode Prefix Free, O ( n lg n ) versus O ( n k ) menunjukkan kemungkinan suatu algoritma dengan kompleksitas O ( n lg k ) , atau bahkan O ( n H ( n 1 , ... , n k ) di mana n i adalah jumlah codeword panjang i , menggunakan analogi dari tepi cembung cembung yang meliputi n $O(nH(n_1,\ldots,n_k)$$O(n\lg n)$$O(nk)$$O(n\lg k)$$O(nH(n_1,\ldots,n_k)$$n_i$$i$$n_i$menunjuk ke panjang kode yang mencakup simbol .$n_i$

2. Contoh sederhana menunjukkan bahwa mengurutkan nilai-nilai logaritmik (bulat) dari frekuensi (dalam waktu linier dalam model RAM kata ) tidak memberikan kode bebas awalan yang optimal dalam waktu linier: $\theta(\lg n)$

   • Untuk , f 1 = 1 / 2 - ε dan f 2 = f 3 = 1 / 4 + $n=3$$f_1=1/2-\varepsilon$$f_2=f_3=1/4+\varepsilon$
   • jadi penyortiran log tidak mengubah urutan$\lceil\lg f_i\rceil=2$
   • namun dua kode dari tiga biaya bit lebih dari optimal.$n/4$

3. $k$

   • $k=n$$\theta(\lg n)$$n^2$

Butuh beberapa tahun (lima!), Tetapi di sini ada sebagian jawaban untuk pertanyaan:

http://arxiv.org/abs/1602.00023

Kode Gratis Awalan Optimal Dengan Pengurutan Sebagian Jérémy Barbay (Diserahkan pada 29 Jan 2016)

Kami menggambarkan suatu algoritma yang menghitung kode bebas awalan yang optimal untuk n bobot positif yang tidak disortir dalam waktu dalam O (n (1 + lgα)) ⊆O (nlgn), di mana pergantian α∈ [1..n − 1] mengukur jumlah penyortiran diperlukan oleh perhitungan. Kompleksitas asimptotik ini berada dalam faktor konstan yang optimal dalam model perhitungan pohon keputusan aljabar, dalam kasus terburuk atas semua contoh ukuran n dan alternasi α. Hasil seperti itu memperbaiki keadaan kompleksitas seni Θ (nlgn) dalam kasus terburuk dibandingkan contoh ukuran n dalam model komputasi yang sama, tengara dalam kompresi dan pengkodean sejak 1952, dengan hanya kombinasi algoritma van Leeuwen untuk menghitung awalan optimal kode gratis dari bobot yang diurutkan (dikenal sejak 1976), dengan Struktur Data yang Ditangguhkan untuk mengurutkan sebagian multiset tergantung pada kueri di atasnya (dikenal sejak 1988).