Permasalahan Pohon Alfabet Optimal
Permasalahan pohon alfabet kelihatan sangat serupa dengan permasalahan Huffman, kecuali bahwa daun-daun dari pohon alfabet (dibaca dari kiri ke kanan) harus di dalam urutan masukan yang asli. Dengan cara yang sama seperti di pengkodean Huffman, pohon biner harus penuh, yaitu masing-masing simpul internal harus mempunyai persisnya dua anak/cabang.
Kesulitan utama adalah kita tidak bisa melokalisir dengan mudah dua item untuk dikombinasikan.
Asumsikan kita mempunyai suatu urutan dari bobot suatu item n, dimana wi adalah bobot yang tidak negatif dari item ith. Dapat kita tulis α = w1…wn. Urutan itu akan berubah selama algoritma ini.
Pohon alfabet diatas, α adalah satu pohon biner T dengan n daun-daun yang diurutkan, dimana daun ith (urutan dari kiri ke kanan) bersesuaian dengan item ith dari pohon alfabet optimal (OAT/Optimal Alphabetic Tree Problem) adalah untuk menemukan satu pohon alfabet dari biaya yang minimum.
Algoritma Garsia-Wachs memecahkan masalah pohon alfabet, algoritma ini merupakan suatu versi dari algoritma yang sebelumnya oleh Hu dan Tucker, lihat pada referensi [18]. Bagian utama dari algoritma ini adalah permutasi atau mengubah susunan α, meskipun demikian pohon yang akhir perlu mempunyai urutan dari daun-daun sama halnya dengan urutan item di dalam urutan yang asli. Kita mengadopsi aturan bahwa item dari α memiliki nama-nama yang unik, dan bahwa nama-nama ini tetap dipakai meskipun item dipindahkan. Ketika memakainya, kita akan berasumsi bahwa nama-nama itu adalah posisi-posisi item didalam daftar, yakni bilangan bulat di dalam [1…n].
Biaya Komputasi/Perhitungan Pohon Alfabet Optimal
Pertama-tama kita menunjukkan bagaimana untuk menghitung hanya biaya keseluruhan pohon, bagaimanapun perhitungan ini tidak memberi secara otomatis satu pohon alfabet optimal, karena kita akan mengubah susunan dari item. Setiap kali kita kombinasikan dua item yang bersebelahan didalam permutasi yang ada, bagaimanapun item ini tidak perlu berdampingan didalam urutan yang asli, jadi di dalam setiap aturan pohon alfabet anak/cabang tidak bisa dari bapak/sumber yang sama.
Pohon alfabet dibangun dengan mengurangi urutan awal dari item ke suatu urutan yang lebih pendek, ini cara yang serupa dengan algoritma Huffman, dengan satu perbedaannya yang penting. Dalam algoritma Huffman, pasangan item yang minimum dikombinasikan, karena itu dapat ditunjukkan bahwa item-item itu adalah saudara kandung dalam pohon optimal. Jika kita bisa mengidentifikasi dua item yang bersebelahan adalah saudara kandung di dalam suatu pohon alfabet optimal, kita bisa kombinasikan mereka dan diproses secara berulang. Sayangnya, tidak ada cara yang dikenal untuk mengidentifikasi pasangan seperti itu. Bahkan suatu pasangan yang minimal mungkin tidak akan saudara kandung. Pertimbangkan urutan bobot (8 7 7 8). Item yang kedua dan yang ketiga bukanlah saudara kandung di dalam pohon alfabet optimal.
Sebagai gantinya, algoritma-algoritma HT dan GW, seperti juga algoritma-algoritma dari [20, 22, 23, 46], dioperasikan dengan mengidentifikasi pasangan suatu item yang mempunyai tingkatan yang sama dalam pohon optimal. Item ini kemudian dikombinasikan ke dalam suatu “paket,” dengan mengurangi banyaknya item dengan satu. Detail bagaimana hasil proses ini berbeda dalam algoritma-algoritma lain. Didefinisikan, untuk 1 ≤ i
TwoSum(i) = wi + wi+1
Sepasang item yang bersebelahan (i, i + 1) adalah suatu pasangan minimal lokal (locally minimal pair atau disingkat lmp) jika:
TwoSum(i - 1) ≥ TwoSum(i) jika i > 1
TwoSum(i) < TwoSum(i + 1) jika i ≤ n-2
Suatu pasangan minimal yang sekarang ini diproses disebut pasangan yang aktif.
Operator Move (Perpindahan). Jika w adalah setiap item didalam daftar π item yang dihargai, didefinisikan dengan RightPos(w) sebagai predecessor yang posisinya dekat dengan nilai sebelah kanan yang lebih besar atau sama dengan w. Didefinisikan RightPos(w) menjadi |π| + 1.
Move (w, π) menjadi suatu operator untuk merubah π oleh pergerakan w. w disisipkan antara posisi-posisi RightPos(w)-1 dan RightPos(w). Sebagai contoh:
Move(7, (2, 5, 7, 2, 4, 9, 3, 4) = (2, 5, 2, 4, 7, 9, 3, 4)
Ketepatan dari algoritma itu adalah suatu persoalan yang sulit. Ada dua pembuktian yang disederhanakan, lihat pada referensi [19, 30] dan kita mengacu pada dokumen tersebut untuk bukti yang terperinci. Di dalam referensi [19] hanya pasangan minimal rightmost/terbesar sebelah kanan dapat diproses setiap kali, sedangkan referensi [30] memberi ketepatan dari algoritma umum ketika setiap pasangan minimal diproses, ini adalah suatu yang penting didalam komputasi/perhitungan paralel, yaitu ketika kita memproses secara serentak banyak pasangan seperti itu. pembuktian dalam referensi [30] menunjukkan bahwa ketepatan adalah segmen-segmen dasar yang dengan baik dibentuk dari pohon-pohon alfabet optimal, ini dinyatakan sebagai suatu teorema struktural dalam referensi [30] yang memberi lebih banyak pengertian yang mendalam ke dalam struktur yang global dari pohon-pohon alfabet optimal.
Untuk j > i+1 ditunjukkan oleh π i,j urutan π dimana unsur-unsur i, i +1 dipindahkan tepat sebelum yang ditinggalkan j.
TEOREMA 1. [Ketepatan dari algoritma GW]
Dimungkinkan (i, i + 1) adalah suatu pasangan minimal dan RightPos(i, i + 1) = j, dan memungkinkan T' adalah suatu pohon dengan urutan π i,j, optimal antar semua pohon dengan π i,j dimana i, i+1 adalah saudara kandung. Kemudian adalah satu pohon alfabet optimal T diatas urutan yang asli π = (1,…n) seperti T≅T'.
Ketepatan dapat juga dinyatakan sebagai kesamaan antara beberapa kelas dari pohon-pohon.
Dua pohon biner T1 dan T2 disebut tingkatan yang sama (ditulis T_1≅T_2) jika T1, dan T2 mempunyai set yang sama dari daun-daun (mungkin di suatu urutan yang berbeda) dan levelT1 =levelT2 (Tingkatan T1 = Tingkatan T2).
Ditunjukkan oleh OPT(i) set dari semua pohon alfabet di atas, urutan daun (1,…n) yang bersifat optimal antar pohon-pohon dimana i dan i+1 adalah tingkatan yang sama. Asumsikan pasangan (i, i+1) adalah minimal lokal. Dimungkinkan OPTmoved(i) adalah set dari semua pohon alfabet diatas, urutan daun π i,j yang bersifat optimal antar semua pohon dimana daun-daun i dan i+1 adalah tingkatan yang sama, dimana j = RightPos(i, i +1).
TEOREMA 2.
Misalkan (i, i + 1) adalah suatu pasangan minimal lokal. Maka :
(1) OPT(i) = OPTmoved(i) .
(2) OPT(i) berisi satu pohon alfabet optimal T.
(3) OPTmoved(i) berisi suatu pohon T' dengan i, i +1 sebagai saudara kandung.
Konstruksi dari Pohon Alfabet Optimal
Algoritma Garsia-Wachs yang penuh pertama menghitung tingkatan. Pohon ini dapat dengan mudah dibangun didalam fungsi GW(π) ketika menghitung biaya pohon alfabet. Setiap kali kita menjumlahkan bobot dari dua item (diciptakan baru atau asli) lalu kita membuat item baru yang bapak/sumber mereka merupakan jumlahan dari bobot dari anak/cabang.
Begitu kita mempunyai suatu tingkatan pohon, pohon alfabet optimal dapat dibangun dengan mudah di dalam waktu yang linier. Gambar 14.6, Gambar 14.7, dan Gambar 14.8 menunjukkan proses konstruksi tingkatan pohon dan konstruksi satu pohon alfabet optimal yang diketahui tingkatan item aslinya.
LEMA 1. Asumsikan kita mengetahui tingkat masing-masing daun dalam satu pohon alfabet optimal. Lalu pohon itu dapat dibangun di dalam waktu yang linier.
Pembuktian tingkatan-tingkatan “bentuk” dari pohon,
Asumsikan l1, l2, l3,…, ln adalah urutan dari tingkatan-tingkatan. Kita melihat/menscan urutan ini dari kiri ke kanan sampai kita menemukan dua tingkat pertama li, li+1 yang merupakan sama. Lalu kita mengetahui bahwa daun-daun i dan i+1 adalah para anak/cabang dari bapak/unsur yang sama, karenanya kita menghubungkan daun-daun ini untuk menciptakan bapak/unsur dan kita menghapus daun-daun ini, di dalam urutan tingkatan, pasangan li, li+1 digantikan oleh suatu tingkatan li - 1. Berikutnya kita memeriksa jika li-1 = li-1, jika tidak kita mencari di sebelah kanan. Kita menyimpan hasil scan/pengamatan tersebut dan menciptakan tingkatan-tingkatan yang baru dalam tumpukan/memori. Waktu total adalah linear.
TEOREMA 3. Pohon alfabet optimal dapat dibangun didalam waktu O(n log n).
Pembuktian kita menyimpan tingkat array/barisan item. Tingkat array/barisan adalah ukuran globalnya (2n -1).
Indeksnya adalah nama-nama dari simpul, yaitu, item n yang asli dan paket simpul-simpul (n - 1) yang diciptakan selama eksekusi algoritma. Algoritma bekerja dalam waktu kwadrat, jika diterapkan di suatu cara yang sederhana. Menggunakan deretan-deretan prioritas, itu bekerja dalam waktu O(n log n).
Mengikuti ketepatan dari Teorema 14.7. secara langsung.
[1] Alok Aggarwal, Baruch Schieber, Takeshi Tokuyama: Finding a Minimum-Weight k-Link Path Graphs with the Concave Monge Property and Applications. Discrete & Computational Geometry 12: 263-280 (1994).
[2] Doris Altenkamp and Kurt Mehlhorn, “Codes: Unequal Probabilities, Unequal Letter Costs,” J. Assoc. Comput. Mach. 27 (3) (July 1980), 412–427.
[3] M. J. Atallah, S. R. Kosaraju, L. L. Larmore, G. L. Miller, and S-H. Teng. Constructing trees in parallel, Proc. 1st ACM Symposium on Parallel Algorithms and Architectures (1989), pp. 499–533.
[4] Julia Abrahams, “Code and Parse Trees for Lossless Source Encoding,” Sequences ’97, (1997).
[5] P. Berman, M. Karpinski, M. Nekrich, Approximating Huffman codes in parallel, Proc. 29th ICALP, LNCS vol. 2380, Springer, 2002, pp. 845-855.
[6] P. Bradford, M. Golin, L. Larmore, W. Rytter, Optimal Prefix-Free Codes for Unequal Letter Costs and Dynamic Programming with the Monge Property, Journal of Algorithms, Vol. 42, No. 2, February 2002, p. 277-303.
[7] A. Aggarwal, M. Klawe, S. Moran, P. Shor, and R. Wilber, Geometric applications of a matrix-searching algorithm, Algorithmica 2 (1987), pp. 195–208.
[8] Serap A. Savari, “Some Notes on Varn Coding,” IEEE Transactions on Information Theory, 40 (1) (Jan. 1994), 181–186.
[9] Siu-Ngan Choi and M. Golin, “Lopsided trees: Algorithms, Analyses and Applications,”Automata, Languages and Programming, Proceedings of the 23rd International Colloquium on Automata, Languages, and Programming (ICALP 96).
[10] N. Cot, “A linear-time ordering procedure with applications to variable length encoding,”Proc. 8th Annual Princeton Conference on Information Sciences and Systems, (1974), pp. 460–463.
[11] A. M. Garsia and M. L. Wachs, A New algorithm for minimal binary search trees, SIAM Journal of Computing 6 (1977), pp. 622–642.
[12] T. C. Hu. A new proof of the T-C algorithm, SIAM Journal of Applied Mathematics 25 (1973), pp. 83–94.
[13] E. N. Gilbert, “Coding with Digits of Unequal Costs,” IEEE Trans. Inform. Theory, 41 (1995).
[14] A. Gibbons, W.Rytter, Efficient parallel algorithms, Cambridge Univ. Press 1997.
[15] M. Golin and G. Rote, “A Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes for Unequal Letter Costs,”Proceedings of the 22nd International Colloquium on Automata Languages and Programming (ICALP ’95), (July 1995) 256-267.
[16] D. S. Hirschberg and L. L. Larmore, The Least weight subsequence problem, Proc. 26th IEEE Symp. on Foundations of Computer Science Portland Oregon (Oct. 1985), pp. 137–143. Reprinted in SIAM Journal on Computing 16 (1987), pp. 628–638.
[17] D. A. Huffman. A Method for the constructing of minimum redundancy codes, Proc. IRE 40 (1952), pp. 1098–1101.
[18] T. C. Hu and A. C. Tucker, Optimal computer search trees and variable length alphabetic codes, SIAM Journal of Applied Mathematics 21 (1971), pp. 514–532.
[19] J. H. Kingston, A new proof of the Garsia-Wachs algorithm, Journal of Algorithms 9 (1988) pp. 129–136.
[20] M. M. Klawe and B. Mumey, Upper and Lower Bounds on Constructing Alphabetic Binary Trees, Proceedings of the 4 th ACM-SIAM Symposium on Discrete Algorithms (1993), pp. 185–193.
[21] L. L. Larmore and D. S. Hirschberg, A fast algorithm for optimal length–limited Huffman codes, Journal of the ACM 37 (1990), pp. 464–473.
[22] L. L. Larmore and T. M. Przytycka, The optimal alphabetic tree problem revisited, Proceedings of the 21 st International Colloquium, ICALP’94, Jerusalem, LNCS 820, Springer-Verlag, (1994), pp. 251–262.
[23] L. L. Larmore, T. M. Przytycka, and W. Rytter, Parallel construction of optimal alphabetic trees, Proceedings of the 5 th ACM Symposium on Parallel Algorithms and Architectures (1993), pp. 214–223.
[24] M. Golin and G. Rote, “A Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes for Uneq ual Letter Costs,” Proceedings of the 22nd International Colloquium on Automata Languages and Progr amming (ICALP ’95),(July 1995) 256-267. Expanded version to appear in IEEE Trans. Inform. Theory.
[25] R. G¨uttler, K. Mehlhorn and W. Schneider. Binary search trees: average and worst case behavior, Electron. Informationsverarb Kybernet, 16 (1980) pp. 41–61.
[26] Sanjiv Kapoor and Edward Reingold, “Optimum Lopsided Binary Trees,” Journal of the Association for Computing Machinery 36 (3) (July 1989), 573–590.
[27] R. M. Karp, “Minimum-Redundancy Coding for the Discrete Noiseless Channel,”IRE Transactions on Information Theory, 7 (1961) 27-39.
[28] M. Karpinski, L. Larmore, Yakov Nekrich, A work efficient algorithm for the construction of length-limited Huffman codes, to appear in Parallel Processing Letters.
[29] M. Karpinski, L. Larmore and W. Rytter, Sequential and parallel subquadratic work constructions of approximately optimal binary search trees, the 7th ACM Symposium on Discrete Algorithms, SODA’96.
[30] Marek Karpinski, Lawrence L. Larmore, and Wojciech Rytter. Correctness of constructing optimal alphabetic trees revisited. Theoretical Computer Science, 180(1-2):309-324, 10 June 1997.
[31] M. Karpinski, W. Rytter, On a Sublinear Time Parallel Construction of Optimal Binary Search Trees, Parallel Processing Letters, Volume 8 - Number 3, 1998.
[32] D. G. Kirkpatrick and T. M. Przytycka, Parallel construction of binary trees with almost optimal weighted path length, Proc. 2nd Symp. on Parallel Algorithms and Architectures (1990).
[33] D. G. Kirkpatrick and T. M. Przytycka, An optimal parallel minimax tree algorithm, Proc. 2nd IEEE Symp. of Parallel and Distributed Processing (1990), pp. 293–300.
[34] D. E. Knuth, Optimum binary search trees, Acta Informatica 1 (1971) pp. 14–25.
[35] D. E. Knuth. The Art of computer programming, Addison–Wesley (1973).
[36] L. L. Larmore, and T. M. Przytycka, Parallel construction of trees with optimal weighted path length, Proc. 3rd ACM Symposium on Parallel Algorithms and Architectures (1991), pp. 71–80.
[37] L. L. Larmore, and T. M. Przytycka, Constructing Huffman trees in parallel, SIAM J. Computing 24(6), (1995) pp. 1163-1169.
[38] L.Larmore, W. Rytter, Optimal parallel algorithms for some dynamic programming problems, IPL 52 (1994) 31-34.
[39] Ch. Levcopulos, T. Przytycka, A work-time trade-off in parallel computation of Huffman trees and concave least weight subsequence problem, Parallel Processing Letters 4(1-2) (1994) pp. 37-43.
[40] Ruy Luiz Milidiu, Eduardo Laber, The warm-up algorithm:a Lagrangian construction of length limited Huffman codes, SIAM J. Comput. 30(5): 1405-1426 (2000).
[41] Ruy Luiz Milidi, Eduardo Sany Laber: Linear Time Recognition of Optimal LRestricted Prefix Codes (Extended Abstract). LATIN 2000: 227-236.
[42] Ruy LuizMilidi, Eduardo Sany Laber: Bounding the Inefficiency of Length-Restricted Prefix Codes. Algorithmica 31(4): 513-529 (2001).
[43] W. Rytter, Efficient parallel computations for some dynamic programming problems, Theo. Comp. Sci. 59 (1988), pp. 297–307.
[44] K. Mehlhorn, Data structures and algorithms, vol. 1, Springer 1984.
[45] Y. Perl, M. R. Garey, and S. Even, “Efficient generation of optimal prefix code: Equiprobable words using unequal cost letters,” Journal of the Association for Computing Machinery 22 (2) (April 1975), pp 202–214.
[46] P. Ramanan, Testing the optimality of alphabetic trees, Theoretical Computer Science 93 (1992), pp. 279–301.
[47] W. Rytter, The space complexity of the unique decipherability problem, IPL 16 (4) 1983.
[48] Fast parallel computations for some dynamic programming problems, Theoretical Computer Science (1988).
[49] Baruch Schieber, Computing a Minimum Weight k-Link Path in Graphs with the Concave Monge Property. 204-222.
[50] J. S. Vitter, “Dynamic Huffman Coding,” ACM Trans. Math. Software 15 (June 1989), pp 158–167.
[51] R. Wilber, The Concave least weight subsequence problem revisited, Journal of Algorithms 9 (1988), pp. 418–425.
[52] F. F. Yao, Efficient dynamic programming using quadrangle inequalities, Proceedings of the 12 th ACM Symposium on Theory of Computing (1980), pp. 429–435.
[53] Rinaldi Munir, Algoritma & Pemrograman : Dalam Bahasa Pascal dan C, Penerbit Informatika Bandung, 2007.
[54] Suarga, Algoritma Pemrograman, penerbit Andi Yogyakarta, 2006.
[55] Intan Yuniar Purbasari, Desain & Analisis Algoritma, Penerbit Graha Ilmu Yogyakarta, 2007.
[56] Eko Budi Purwanto, Perancangan & Analisis Algoritma, Penerbit Graha Ilmu Yogyakarta, 2008.
Permasalahan pohon alfabet kelihatan sangat serupa dengan permasalahan Huffman, kecuali bahwa daun-daun dari pohon alfabet (dibaca dari kiri ke kanan) harus di dalam urutan masukan yang asli. Dengan cara yang sama seperti di pengkodean Huffman, pohon biner harus penuh, yaitu masing-masing simpul internal harus mempunyai persisnya dua anak/cabang.
Kesulitan utama adalah kita tidak bisa melokalisir dengan mudah dua item untuk dikombinasikan.
Asumsikan kita mempunyai suatu urutan dari bobot suatu item n, dimana wi adalah bobot yang tidak negatif dari item ith. Dapat kita tulis α = w1…wn. Urutan itu akan berubah selama algoritma ini.
Pohon alfabet diatas, α adalah satu pohon biner T dengan n daun-daun yang diurutkan, dimana daun ith (urutan dari kiri ke kanan) bersesuaian dengan item ith dari pohon alfabet optimal (OAT/Optimal Alphabetic Tree Problem) adalah untuk menemukan satu pohon alfabet dari biaya yang minimum.
Algoritma Garsia-Wachs memecahkan masalah pohon alfabet, algoritma ini merupakan suatu versi dari algoritma yang sebelumnya oleh Hu dan Tucker, lihat pada referensi [18]. Bagian utama dari algoritma ini adalah permutasi atau mengubah susunan α, meskipun demikian pohon yang akhir perlu mempunyai urutan dari daun-daun sama halnya dengan urutan item di dalam urutan yang asli. Kita mengadopsi aturan bahwa item dari α memiliki nama-nama yang unik, dan bahwa nama-nama ini tetap dipakai meskipun item dipindahkan. Ketika memakainya, kita akan berasumsi bahwa nama-nama itu adalah posisi-posisi item didalam daftar, yakni bilangan bulat di dalam [1…n].
Biaya Komputasi/Perhitungan Pohon Alfabet Optimal
Pertama-tama kita menunjukkan bagaimana untuk menghitung hanya biaya keseluruhan pohon, bagaimanapun perhitungan ini tidak memberi secara otomatis satu pohon alfabet optimal, karena kita akan mengubah susunan dari item. Setiap kali kita kombinasikan dua item yang bersebelahan didalam permutasi yang ada, bagaimanapun item ini tidak perlu berdampingan didalam urutan yang asli, jadi di dalam setiap aturan pohon alfabet anak/cabang tidak bisa dari bapak/sumber yang sama.
Pohon alfabet dibangun dengan mengurangi urutan awal dari item ke suatu urutan yang lebih pendek, ini cara yang serupa dengan algoritma Huffman, dengan satu perbedaannya yang penting. Dalam algoritma Huffman, pasangan item yang minimum dikombinasikan, karena itu dapat ditunjukkan bahwa item-item itu adalah saudara kandung dalam pohon optimal. Jika kita bisa mengidentifikasi dua item yang bersebelahan adalah saudara kandung di dalam suatu pohon alfabet optimal, kita bisa kombinasikan mereka dan diproses secara berulang. Sayangnya, tidak ada cara yang dikenal untuk mengidentifikasi pasangan seperti itu. Bahkan suatu pasangan yang minimal mungkin tidak akan saudara kandung. Pertimbangkan urutan bobot (8 7 7 8). Item yang kedua dan yang ketiga bukanlah saudara kandung di dalam pohon alfabet optimal.
Sebagai gantinya, algoritma-algoritma HT dan GW, seperti juga algoritma-algoritma dari [20, 22, 23, 46], dioperasikan dengan mengidentifikasi pasangan suatu item yang mempunyai tingkatan yang sama dalam pohon optimal. Item ini kemudian dikombinasikan ke dalam suatu “paket,” dengan mengurangi banyaknya item dengan satu. Detail bagaimana hasil proses ini berbeda dalam algoritma-algoritma lain. Didefinisikan, untuk 1 ≤ i
TwoSum(i) = wi + wi+1
Sepasang item yang bersebelahan (i, i + 1) adalah suatu pasangan minimal lokal (locally minimal pair atau disingkat lmp) jika:
TwoSum(i - 1) ≥ TwoSum(i) jika i > 1
TwoSum(i) < TwoSum(i + 1) jika i ≤ n-2
Suatu pasangan minimal yang sekarang ini diproses disebut pasangan yang aktif.
Operator Move (Perpindahan). Jika w adalah setiap item didalam daftar π item yang dihargai, didefinisikan dengan RightPos(w) sebagai predecessor yang posisinya dekat dengan nilai sebelah kanan yang lebih besar atau sama dengan w. Didefinisikan RightPos(w) menjadi |π| + 1.
Move (w, π) menjadi suatu operator untuk merubah π oleh pergerakan w. w disisipkan antara posisi-posisi RightPos(w)-1 dan RightPos(w). Sebagai contoh:
Move(7, (2, 5, 7, 2, 4, 9, 3, 4) = (2, 5, 2, 4, 7, 9, 3, 4)
Ketepatan dari algoritma itu adalah suatu persoalan yang sulit. Ada dua pembuktian yang disederhanakan, lihat pada referensi [19, 30] dan kita mengacu pada dokumen tersebut untuk bukti yang terperinci. Di dalam referensi [19] hanya pasangan minimal rightmost/terbesar sebelah kanan dapat diproses setiap kali, sedangkan referensi [30] memberi ketepatan dari algoritma umum ketika setiap pasangan minimal diproses, ini adalah suatu yang penting didalam komputasi/perhitungan paralel, yaitu ketika kita memproses secara serentak banyak pasangan seperti itu. pembuktian dalam referensi [30] menunjukkan bahwa ketepatan adalah segmen-segmen dasar yang dengan baik dibentuk dari pohon-pohon alfabet optimal, ini dinyatakan sebagai suatu teorema struktural dalam referensi [30] yang memberi lebih banyak pengertian yang mendalam ke dalam struktur yang global dari pohon-pohon alfabet optimal.
Untuk j > i+1 ditunjukkan oleh π i,j urutan π dimana unsur-unsur i, i +1 dipindahkan tepat sebelum yang ditinggalkan j.
TEOREMA 1. [Ketepatan dari algoritma GW]
Dimungkinkan (i, i + 1) adalah suatu pasangan minimal dan RightPos(i, i + 1) = j, dan memungkinkan T' adalah suatu pohon dengan urutan π i,j, optimal antar semua pohon dengan π i,j dimana i, i+1 adalah saudara kandung. Kemudian adalah satu pohon alfabet optimal T diatas urutan yang asli π = (1,…n) seperti T≅T'.
Ketepatan dapat juga dinyatakan sebagai kesamaan antara beberapa kelas dari pohon-pohon.
Dua pohon biner T1 dan T2 disebut tingkatan yang sama (ditulis T_1≅T_2) jika T1, dan T2 mempunyai set yang sama dari daun-daun (mungkin di suatu urutan yang berbeda) dan levelT1 =levelT2 (Tingkatan T1 = Tingkatan T2).
Ditunjukkan oleh OPT(i) set dari semua pohon alfabet di atas, urutan daun (1,…n) yang bersifat optimal antar pohon-pohon dimana i dan i+1 adalah tingkatan yang sama. Asumsikan pasangan (i, i+1) adalah minimal lokal. Dimungkinkan OPTmoved(i) adalah set dari semua pohon alfabet diatas, urutan daun π i,j yang bersifat optimal antar semua pohon dimana daun-daun i dan i+1 adalah tingkatan yang sama, dimana j = RightPos(i, i +1).
TEOREMA 2.
Misalkan (i, i + 1) adalah suatu pasangan minimal lokal. Maka :
(1) OPT(i) = OPTmoved(i) .
(2) OPT(i) berisi satu pohon alfabet optimal T.
(3) OPTmoved(i) berisi suatu pohon T' dengan i, i +1 sebagai saudara kandung.
Konstruksi dari Pohon Alfabet Optimal
Algoritma Garsia-Wachs yang penuh pertama menghitung tingkatan. Pohon ini dapat dengan mudah dibangun didalam fungsi GW(π) ketika menghitung biaya pohon alfabet. Setiap kali kita menjumlahkan bobot dari dua item (diciptakan baru atau asli) lalu kita membuat item baru yang bapak/sumber mereka merupakan jumlahan dari bobot dari anak/cabang.
Begitu kita mempunyai suatu tingkatan pohon, pohon alfabet optimal dapat dibangun dengan mudah di dalam waktu yang linier. Gambar 14.6, Gambar 14.7, dan Gambar 14.8 menunjukkan proses konstruksi tingkatan pohon dan konstruksi satu pohon alfabet optimal yang diketahui tingkatan item aslinya.
LEMA 1. Asumsikan kita mengetahui tingkat masing-masing daun dalam satu pohon alfabet optimal. Lalu pohon itu dapat dibangun di dalam waktu yang linier.
Pembuktian tingkatan-tingkatan “bentuk” dari pohon,
Asumsikan l1, l2, l3,…, ln adalah urutan dari tingkatan-tingkatan. Kita melihat/menscan urutan ini dari kiri ke kanan sampai kita menemukan dua tingkat pertama li, li+1 yang merupakan sama. Lalu kita mengetahui bahwa daun-daun i dan i+1 adalah para anak/cabang dari bapak/unsur yang sama, karenanya kita menghubungkan daun-daun ini untuk menciptakan bapak/unsur dan kita menghapus daun-daun ini, di dalam urutan tingkatan, pasangan li, li+1 digantikan oleh suatu tingkatan li - 1. Berikutnya kita memeriksa jika li-1 = li-1, jika tidak kita mencari di sebelah kanan. Kita menyimpan hasil scan/pengamatan tersebut dan menciptakan tingkatan-tingkatan yang baru dalam tumpukan/memori. Waktu total adalah linear.
TEOREMA 3. Pohon alfabet optimal dapat dibangun didalam waktu O(n log n).
Pembuktian kita menyimpan tingkat array/barisan item. Tingkat array/barisan adalah ukuran globalnya (2n -1).
Indeksnya adalah nama-nama dari simpul, yaitu, item n yang asli dan paket simpul-simpul (n - 1) yang diciptakan selama eksekusi algoritma. Algoritma bekerja dalam waktu kwadrat, jika diterapkan di suatu cara yang sederhana. Menggunakan deretan-deretan prioritas, itu bekerja dalam waktu O(n log n).
Mengikuti ketepatan dari Teorema 14.7. secara langsung.
DAFTAR PUSTAKA / REFERENSI
[1] Alok Aggarwal, Baruch Schieber, Takeshi Tokuyama: Finding a Minimum-Weight k-Link Path Graphs with the Concave Monge Property and Applications. Discrete & Computational Geometry 12: 263-280 (1994).
[2] Doris Altenkamp and Kurt Mehlhorn, “Codes: Unequal Probabilities, Unequal Letter Costs,” J. Assoc. Comput. Mach. 27 (3) (July 1980), 412–427.
[3] M. J. Atallah, S. R. Kosaraju, L. L. Larmore, G. L. Miller, and S-H. Teng. Constructing trees in parallel, Proc. 1st ACM Symposium on Parallel Algorithms and Architectures (1989), pp. 499–533.
[4] Julia Abrahams, “Code and Parse Trees for Lossless Source Encoding,” Sequences ’97, (1997).
[5] P. Berman, M. Karpinski, M. Nekrich, Approximating Huffman codes in parallel, Proc. 29th ICALP, LNCS vol. 2380, Springer, 2002, pp. 845-855.
[6] P. Bradford, M. Golin, L. Larmore, W. Rytter, Optimal Prefix-Free Codes for Unequal Letter Costs and Dynamic Programming with the Monge Property, Journal of Algorithms, Vol. 42, No. 2, February 2002, p. 277-303.
[7] A. Aggarwal, M. Klawe, S. Moran, P. Shor, and R. Wilber, Geometric applications of a matrix-searching algorithm, Algorithmica 2 (1987), pp. 195–208.
[8] Serap A. Savari, “Some Notes on Varn Coding,” IEEE Transactions on Information Theory, 40 (1) (Jan. 1994), 181–186.
[9] Siu-Ngan Choi and M. Golin, “Lopsided trees: Algorithms, Analyses and Applications,”Automata, Languages and Programming, Proceedings of the 23rd International Colloquium on Automata, Languages, and Programming (ICALP 96).
[10] N. Cot, “A linear-time ordering procedure with applications to variable length encoding,”Proc. 8th Annual Princeton Conference on Information Sciences and Systems, (1974), pp. 460–463.
[11] A. M. Garsia and M. L. Wachs, A New algorithm for minimal binary search trees, SIAM Journal of Computing 6 (1977), pp. 622–642.
[12] T. C. Hu. A new proof of the T-C algorithm, SIAM Journal of Applied Mathematics 25 (1973), pp. 83–94.
[13] E. N. Gilbert, “Coding with Digits of Unequal Costs,” IEEE Trans. Inform. Theory, 41 (1995).
[14] A. Gibbons, W.Rytter, Efficient parallel algorithms, Cambridge Univ. Press 1997.
[15] M. Golin and G. Rote, “A Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes for Unequal Letter Costs,”Proceedings of the 22nd International Colloquium on Automata Languages and Programming (ICALP ’95), (July 1995) 256-267.
[16] D. S. Hirschberg and L. L. Larmore, The Least weight subsequence problem, Proc. 26th IEEE Symp. on Foundations of Computer Science Portland Oregon (Oct. 1985), pp. 137–143. Reprinted in SIAM Journal on Computing 16 (1987), pp. 628–638.
[17] D. A. Huffman. A Method for the constructing of minimum redundancy codes, Proc. IRE 40 (1952), pp. 1098–1101.
[18] T. C. Hu and A. C. Tucker, Optimal computer search trees and variable length alphabetic codes, SIAM Journal of Applied Mathematics 21 (1971), pp. 514–532.
[19] J. H. Kingston, A new proof of the Garsia-Wachs algorithm, Journal of Algorithms 9 (1988) pp. 129–136.
[20] M. M. Klawe and B. Mumey, Upper and Lower Bounds on Constructing Alphabetic Binary Trees, Proceedings of the 4 th ACM-SIAM Symposium on Discrete Algorithms (1993), pp. 185–193.
[21] L. L. Larmore and D. S. Hirschberg, A fast algorithm for optimal length–limited Huffman codes, Journal of the ACM 37 (1990), pp. 464–473.
[22] L. L. Larmore and T. M. Przytycka, The optimal alphabetic tree problem revisited, Proceedings of the 21 st International Colloquium, ICALP’94, Jerusalem, LNCS 820, Springer-Verlag, (1994), pp. 251–262.
[23] L. L. Larmore, T. M. Przytycka, and W. Rytter, Parallel construction of optimal alphabetic trees, Proceedings of the 5 th ACM Symposium on Parallel Algorithms and Architectures (1993), pp. 214–223.
[24] M. Golin and G. Rote, “A Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes for Uneq ual Letter Costs,” Proceedings of the 22nd International Colloquium on Automata Languages and Progr amming (ICALP ’95),(July 1995) 256-267. Expanded version to appear in IEEE Trans. Inform. Theory.
[25] R. G¨uttler, K. Mehlhorn and W. Schneider. Binary search trees: average and worst case behavior, Electron. Informationsverarb Kybernet, 16 (1980) pp. 41–61.
[26] Sanjiv Kapoor and Edward Reingold, “Optimum Lopsided Binary Trees,” Journal of the Association for Computing Machinery 36 (3) (July 1989), 573–590.
[27] R. M. Karp, “Minimum-Redundancy Coding for the Discrete Noiseless Channel,”IRE Transactions on Information Theory, 7 (1961) 27-39.
[28] M. Karpinski, L. Larmore, Yakov Nekrich, A work efficient algorithm for the construction of length-limited Huffman codes, to appear in Parallel Processing Letters.
[29] M. Karpinski, L. Larmore and W. Rytter, Sequential and parallel subquadratic work constructions of approximately optimal binary search trees, the 7th ACM Symposium on Discrete Algorithms, SODA’96.
[30] Marek Karpinski, Lawrence L. Larmore, and Wojciech Rytter. Correctness of constructing optimal alphabetic trees revisited. Theoretical Computer Science, 180(1-2):309-324, 10 June 1997.
[31] M. Karpinski, W. Rytter, On a Sublinear Time Parallel Construction of Optimal Binary Search Trees, Parallel Processing Letters, Volume 8 - Number 3, 1998.
[32] D. G. Kirkpatrick and T. M. Przytycka, Parallel construction of binary trees with almost optimal weighted path length, Proc. 2nd Symp. on Parallel Algorithms and Architectures (1990).
[33] D. G. Kirkpatrick and T. M. Przytycka, An optimal parallel minimax tree algorithm, Proc. 2nd IEEE Symp. of Parallel and Distributed Processing (1990), pp. 293–300.
[34] D. E. Knuth, Optimum binary search trees, Acta Informatica 1 (1971) pp. 14–25.
[35] D. E. Knuth. The Art of computer programming, Addison–Wesley (1973).
[36] L. L. Larmore, and T. M. Przytycka, Parallel construction of trees with optimal weighted path length, Proc. 3rd ACM Symposium on Parallel Algorithms and Architectures (1991), pp. 71–80.
[37] L. L. Larmore, and T. M. Przytycka, Constructing Huffman trees in parallel, SIAM J. Computing 24(6), (1995) pp. 1163-1169.
[38] L.Larmore, W. Rytter, Optimal parallel algorithms for some dynamic programming problems, IPL 52 (1994) 31-34.
[39] Ch. Levcopulos, T. Przytycka, A work-time trade-off in parallel computation of Huffman trees and concave least weight subsequence problem, Parallel Processing Letters 4(1-2) (1994) pp. 37-43.
[40] Ruy Luiz Milidiu, Eduardo Laber, The warm-up algorithm:a Lagrangian construction of length limited Huffman codes, SIAM J. Comput. 30(5): 1405-1426 (2000).
[41] Ruy Luiz Milidi, Eduardo Sany Laber: Linear Time Recognition of Optimal LRestricted Prefix Codes (Extended Abstract). LATIN 2000: 227-236.
[42] Ruy LuizMilidi, Eduardo Sany Laber: Bounding the Inefficiency of Length-Restricted Prefix Codes. Algorithmica 31(4): 513-529 (2001).
[43] W. Rytter, Efficient parallel computations for some dynamic programming problems, Theo. Comp. Sci. 59 (1988), pp. 297–307.
[44] K. Mehlhorn, Data structures and algorithms, vol. 1, Springer 1984.
[45] Y. Perl, M. R. Garey, and S. Even, “Efficient generation of optimal prefix code: Equiprobable words using unequal cost letters,” Journal of the Association for Computing Machinery 22 (2) (April 1975), pp 202–214.
[46] P. Ramanan, Testing the optimality of alphabetic trees, Theoretical Computer Science 93 (1992), pp. 279–301.
[47] W. Rytter, The space complexity of the unique decipherability problem, IPL 16 (4) 1983.
[48] Fast parallel computations for some dynamic programming problems, Theoretical Computer Science (1988).
[49] Baruch Schieber, Computing a Minimum Weight k-Link Path in Graphs with the Concave Monge Property. 204-222.
[50] J. S. Vitter, “Dynamic Huffman Coding,” ACM Trans. Math. Software 15 (June 1989), pp 158–167.
[51] R. Wilber, The Concave least weight subsequence problem revisited, Journal of Algorithms 9 (1988), pp. 418–425.
[52] F. F. Yao, Efficient dynamic programming using quadrangle inequalities, Proceedings of the 12 th ACM Symposium on Theory of Computing (1980), pp. 429–435.
[53] Rinaldi Munir, Algoritma & Pemrograman : Dalam Bahasa Pascal dan C, Penerbit Informatika Bandung, 2007.
[54] Suarga, Algoritma Pemrograman, penerbit Andi Yogyakarta, 2006.
[55] Intan Yuniar Purbasari, Desain & Analisis Algoritma, Penerbit Graha Ilmu Yogyakarta, 2007.
[56] Eko Budi Purwanto, Perancangan & Analisis Algoritma, Penerbit Graha Ilmu Yogyakarta, 2008.
Tidak ada komentar:
Posting Komentar