Jaringan Distribusi Listrik

Sistem distribusi merupakan bagian dari sistem tenaga listrik. Sistem distribusi ini berguna untuk menyalurkan tenaga listrik dari sumber daya listrik besar (bulk power source) sampai ke konsumen.         

Jadi fungsi distribusi listrik adalah:

1.    Pembagian atau penyaluran tenaga listrik ke beberapa tempat (pelanggan).

2.      Merupakan sub sistem tenaga listrik yang langsung berhubungan dengan pelanggan, karena catu daya pada pusat-pusat beban (pelanggan) dilayani langsung melalui jaringan distribusi.

Tenaga listrik yang dihasilkan oleh pembangkit listrik besar dengan tegangan dari 11 KV sampai 24 KV dinaikkan tegangannya oleh gardu induk dengan transformator penaik tegangan menjadi 70 KV, 154 KV, 220 KV atau 500 KV kemudian disalurkan melalui saluran transmisi. Tujuan menaikkan tegangan adalah untuk memperkecil kerugian daya listrik pada saluran transmisi, dimana dalam hal ini kerugian daya adalah sebanding dengan kuadrat arus yang mengalir. Dengan daya yang sama bila nilai tegangannya diperbesar, maka arus yang mengalir semakin kecil sehingga kerugian daya juga akan kecil pula.

Dari saluran transmisi, tegangan diturunkan lagi menjadi 20 KV dengan transformator penurun tegangan pada gardu induk distribusi, kemudian dengan sistem tegangan tersebut penyaluran tenaga listrik dilakukan oleh saluran distribusi primer. Dari saluran distribusi primer inilah gardu-gardu distribusi mengambil tegangan untuk diturunkan tegangannya dengan trafo distribusi menjadi sistem tegangan rendah, yaitu 220/380 Volt. Selanjutnya disalurkan oleh saluran distribusi sekunder ke konsumen-konsumen. Dengan ini jelas bahwa sistem distribusi merupakan bagian yang penting dalam sistem tenaga listrik secara keseluruhan. Konfigurasi sistem tenaga listrik dapat dilihat pada gambar berikut.

Berdasarkan gambar di atas, maka dapat dikelompokkan dalam beberapa pembagian sebagai berikut:

1.      Daerah I     :  bagian pembangkitan (generation).

2.      Daerah II    :  bagian penyaluran (transmission) bertegangan tinggi (HV, UHV, dan EHV).

3.      Daerah III   :  bagian distribusi primer bertegangan menengah (6, 12, atau 20 KV).

4.      Daerah IV   :  bagian distribusi sekunder bertegangan rendah.

Berdasarkan pembagian tersebut, maka diketahui bahwa sistem distribusi listrik terdapat pada daerah III dan IV, yang pada dasarnya dapat diklasifikasikan menurut beberapa cara, bergantung dari segi apa klasifikasi itu dibuat. Dengan demikian ruang lingkup jaringan distribusi adalah sebagai berikut:

1.     SUTM, terdiri dari tiang dan peralatan kelengkapannya, konduktor dan peralatan perlengkapannya, serta peralatan pengaman dan pemutus.

2.      SKTM, terdiri dari kabel tanah, terminasi dalam dan luar ruangan, dan lain-lain.

3.  Gardu trafo, terdiri dari transformator, tiang, pondasi tiang, rangka tempat trafo, panel, pipa-pipa pelindung, arrester, kabel-kabel, pengikat transformator, peralatan pertanahan, dan lain-lain.

4.   SUTR dan SKTR, sama dengan perlengkapan/material pada SUTM dan SKTM, yang membedakan hanya dimensinya.

Menurut nilai tegangannya, saluran tenaga listrik atau saluran distribusi dapat diklasifikasikan sebagai berikut:

1.      Saluran distribusi primer, terletak pada sisi primer trafo distribusi, yaitu antara titik sekunder trafo cabang (gardu induk) dengan titik primer trafo distribusi. Saluran ini bertegangan menengah 20 KV. Jaringan listrik 70 KV atau 150 KV, jika langsung melayani pelanggan, bisa disebut jaringan distribusi.

Sistem distribusi primer digunakan untuk menyalurkan tenaga listrik dari gardu induk distribusi ke pusat-pusat beban. Sistem ini dapat menggunakan kabel udara maupun kabel tanah sesuai dengan tingkat keandalan yang diinginkan dan kondisi serta situasi lingkungan. Saluran distribusi ini direntangkan sepanjang daerah yang akan disuplai tenaga listrik sampai ke pusat beban.

Terdapat bermacam-macam bentuk rangkaian jaringan distribusi primer, yaitu:

a.       Jaringan distribusi radial.

b.      Jaringan distribusi ring (loop), dengan model: bentuk lingkaran terbuka dan bentuk lingkaran tertutup.

c.       Jaringan distribusi jaring-jaring (network).

d.      Jaringan distribusi spindel.

e.       Saluran radial interkoneksi.

2.      Saluran distribusi sekunder, terletak pada sisi sekunder trafo distribusi, yaitu antara titik sekunder dengan titik cabang menuju beban.

Sistem distribusi sekunder digunakan untuk menyalurkan tenaga listrik dari gardu distribusi ke beban-beban yang ada di konsumen. Pada sistem distribusi sekunder bentuk saluran yang paling banyak digunakan ialah sistem radial. Sistem ini dapat menggunakan kabel yang berisolasi maupun konduktor tanpa isolasi. Sistem ini biasanya disebut sistem tegangan rendah yang langsung akan dihubungkan kepada konsumen/pemakai tenaga listrik dengan melalui peralatan-peralatan sebagai berikut:

a.       Papan pembagi pada trafo distribusi.

b.      Hantaran tegangan rendah (saluran distribusi sekunder).

c.       Saluran Layanan Pelanggan (SLP) ke konsumen/pemakai.

d.      Alat Pembatas dan pengukur daya (KWH meter) serta fuse atau pengaman pada pelanggan.

Komponen sistem distribusi dapat digambarkan pada gambar berikut:

Jaringan distribusi listrik secara umum dibedakan menjadi empat bagian utama:

1.    Jaringan Tegangan Menengah (JTM), yang berfungsi sebagai penyulang (feeder) tegangan menengah yang keluar dari gardu induk (GI) untuk kemudian mensuplai gardu-gardu distribusi.

2.     Trafo distribusi (gardu distribusi), yang berfungsi sebagai penurun tegangan dari tegangan menengah ke tegangan rendah.

3.      Jaringan Tegangan Rendah (JTR), yaitu penyulang tegangan rendah setelah keluar dari gardu distribusi.

4.     Sambungan Rumah (SR) & Alat Pembatas dan Pengukur (APP), yaitu sambungan pelayanan dari JTR ke setiap rumah sampai dengan APP.

Dalam sistem distribusi, masalah yang utama adalah mengatasi gangguan karena jumlah gangguan dalam sistem distribusi adalah relatif lebih banyak dibandingkan dengan jumlah gangguan pada bagian sistem yang lain. Di samping itu masalah tegangan, bagian-bagian instalasi yang berbeban lebih dan rugi-rugi daya dalam jaringan merupakan masalah yang perlu dicatat dan dianalisa secara terus menerus, untuk dijadikan masukan bagi perencanaan pengembangan sistem dan juga untuk melakukan tindakan-tindakan penyempurnaan pemeliharaan dan penyempurnaan operasi sistem distribusi.

DAFTAR PUSTAKA / REFERENSI

Hage, (2008), Dunia Listrik: Sistem Distribusi Tenaga Listrik, http://dunia-listrik.blogspot.com/2008/12/sistem-distribusi-tenaga-listrik.html,

[3 Maret 2009].

Kadir, A., (2006), Distribusi dan Utilisasi Tenaga Listrik, Universitas Indonesia Press, Jakarta.

Marsudi, D., (2006), Operasi Sistem Tenaga Listrik, Graha Ilmu, Yogyakarta.

Algoritma Sollin

Algoritma Sollin menentukan pohon merentang minimum dengan cara melakukan penghapusan sisi yang tidak menyebabkan graf menjadi tidak terhubung atau membentuk sirkuit. Penghapusan tersebut dimulai dari sisi yang memiliki bobot terbesar hingga terkecil. Penghapusan dilakukan setelah sebelumnya sisi-sisi pada graf diurutkan berdasarkan bobotnya dari besar ke kecil.

Langkah-langkah dalam algoritma Sollin adalah sebagai berikut:

1.      Urutkan sisi pada graf berdasarkan bobotnya dari besar ke kecil.

2.      Lakukan penghapusan setiap sisi dimulai dari bobot yang terbesar yang tidak menyebabkan graf menjadi tidak terhubung.

3.   Ulangi langkah 2 sampai pohon merentang minimum terbentuk, yaitu ketika sisi di dalam pohon merentang minimum berjumlah n-1 (n adalah jumlah simpul di graf).

Berdasarkan gambar di atas, maka pengurutan sisi pada graf mulai dari sisi dengan bobot terbesar sampai bobot terkecil dapat dilihat pada tabel berikut:

Bobot	Sisi
50	(E,G)
48	(E,F)
45	(C,E)
40	(A,B)
35	(A,D)
30	(D,E)
25	(B,E)
20	(D,H)
15	(A,C)
14	(G,H)
10	(F,G)

Untuk lebih memahami cara kerja algoritma Sollin, maka dari gambar di atas dapat dicari pohon merentang minimumnya dengan menggunakan algoritma tersebut. Langkah-langkah pembentukan pohon merentang minimumnya dapat dilihat pada gambar berikut:

DAFTAR PUSTAKA / REFERENSI

Gloor, P. A., Johnson, D. B., Makedon, F., Metaxas, P., (1993), A Visualization System for Correctness Proofs of Graph Algorithms, http://www.wellesley.edu/CS/pmetaxas/visual_proofs.pdf, Computer Science Education, [19 Maret 2010].

Greenberg, H. J., (1998), Greedy Algorithm for Minimum Spanning Tree, http://glossary.computing.society.informs.org/notes/spanningtree.pdf, University of Colorado, Denver, [19 Maret 2010].

Kristanto, A., (2008), Perancangan Sistem Informasi dan Aplikasinya, Gava Media, Yogyakarta.

Mehta, D. P., Sahni, S., (2005), Handbook of Data Structures and Applications, Chapman & Hall/CRC Computer and Information Science Series, United States of America.

Munir, R., (2009), Matematika Diskrit, Edisi 3, Informatika, Bandung.

Oetomo, B. S., (2002), Perencanaan dan Pembangunan Sistem Informasi, Andi, Yogyakarta.

Purbasari, I. Y., (2007), Desain Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Purwanto, E. B., (2008), Perancangan Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Zakaria, T. M., Prijono, A., (2006), Konsep Dan Implementasi Struktur Data, Informatika, Bandung.

Algoritma Kruskal

Algoritma Kruskal adalah algoritma untuk mencari pohon merentang minimum secara langsung didasarkan pada algoritma MST (Minimum Spanning Tree) umum. Pada algoritma Kruskal sisi-sisi di dalam graf diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar. Sisi yang dimasukkan ke dalam himpunan T adalah sisi graf G sedemikian sehingga T adalah pohon. Pada keadaan awal, sisi-sisi sudah diurut berdasarkan bobot membentuk hutan (forest). Hutan tersebut dinamakan hutan merentang (spanning forest). Sisi dari graf G ditambahkan ke T jika tidak membentuk sirkuit di T.

Perbedaan prinsip antara algoritma Prim dan Kruskal adalah jika pada algoritma Prim sisi yang dimasukkan ke dalam T harus bersisian dengan sebuah simpul di T, maka pada algoritma Kruskal sisi yang dipilih tidak perlu bersisian dengan simpul di T asalkan penambahan sisi tersebut tidak membentuk sirkuit.

Langkah-langkah dalam algoritma Kruskal adalah sebagai berikut:

1.   Lakukan pengurutan terhadap setiap sisi di graf mulai dari sisi dengan bobot terkecil sampai terbesar.

2.  Pilih sisi yang mempunyai bobot minimum yang tidak membentuk sirkuit di pohon. Tambahkan sisi tersebut ke dalam pohon.

3.  Ulangi langkah 2 sampai pohon merentang minimum terbentuk, yaitu ketika sisi di dalam pohon merentang minimum berjumlah n-1 (n adalah jumlah simpul di graf).

Berdasarkan gambar di atas, maka dilakukan pengurutan sisi pada graf mulai dari sisi dengan bobot terkecil sampai terbesar dapat dilihat pada tabel berikut:

Bobot	Sisi
10	(F,G)
14	(G,H)
15	(A,C)
20	(D,H)
25	(B,E)
30	(D,E)
35	(A,D)
40	(A,B)
45	(C,E)
48	(E,F)
50	(E,G)

Untuk lebih memahami perbedaan algoritma Prim dan algoritma Kruskal yang keduanya merupakan algoritma untuk pohon merentang minimum, maka dari gambar di atas dapat dicari pohon merentang minimumnya dengan menggunakan kedua algoritma tersebut. Langkah-langkah pembentukan pohon merentang minimumnya dapat dilihat pada gambar berikut ini:

DAFTAR PUSTAKA / REFERENSI

Gloor, P. A., Johnson, D. B., Makedon, F., Metaxas, P., (1993), A Visualization System for Correctness Proofs of Graph Algorithms, http://www.wellesley.edu/CS/pmetaxas/visual_proofs.pdf, Computer Science Education, [19 Maret 2010].

Greenberg, H. J., (1998), Greedy Algorithm for Minimum Spanning Tree, http://glossary.computing.society.informs.org/notes/spanningtree.pdf, University of Colorado, Denver, [19 Maret 2010].

Kristanto, A., (2008), Perancangan Sistem Informasi dan Aplikasinya, Gava Media, Yogyakarta.

Mehta, D. P., Sahni, S., (2005), Handbook of Data Structures and Applications, Chapman & Hall/CRC Computer and Information Science Series, United States of America.

Munir, R., (2009), Matematika Diskrit, Edisi 3, Informatika, Bandung.

Oetomo, B. S., (2002), Perencanaan dan Pembangunan Sistem Informasi, Andi, Yogyakarta.

Purbasari, I. Y., (2007), Desain Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Purwanto, E. B., (2008), Perancangan Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Zakaria, T. M., Prijono, A., (2006), Konsep Dan Implementasi Struktur Data, Informatika, Bandung.

Algoritma Dijkstra

Algoritma Dijkstra merupakan algoritma lintasan terpendek yang paling terkenal. Algoritma ini diterapkan untuk mencari lintasan terpendek (shortest path) pada graf berarah. Algoritma Dijkstra menyelesaikan permasalahan jalur terpendek dengan sumber tunggal (the single-source shortest-path problem) apabila semua simpul tidak negatif (≥ 0). Algoritma ini adalah algoritma Greedy yang mirip dengan algoritma Prim. Algoritma berawal dari simpul sumber S untuk membangun pohon T, dan semua simpul dapat dicapai dari S. Nilai simpul ditambahkan ke T (nilai jalur), kemudian ditambah nilai simpul berikutnya, dan begitu seterusnya.

Secara umum kriteria yang harus dipenuhi untuk mendapatkan  solusi optimum dari jalur terpendek (shortest path) hampir sama dengan kriteria permasalahan pada pohon merentang minimum. Perbedaan mendasar adalah pada jalur terpendek berupa graf berarah, sehingga kriteria yang harus dipenuhi adalah:

1.   Setiap sisi pada graf harus mempunyai nilai (bobot).

2.   Setiap sisi pada graf tidak harus terhubung.

3.   Setiap sisi pada graf harus mempunyai arah.

Proses untuk mendapatkan solusi optimum jalur terpendek adalah dengan menghitung jarak satu per satu sesuai dengan arah yang ditunjukkan oleh tiap-tiap sisi. Perhitungan dilakukan terhadap sisi graf yang memiliki jalur awal dan jalur akhir. Contoh pada gambar di bawah ini akan memberikan gambaran yang lebih mudah dipahami. Misalkan akan ditentukan jalur terpendek dari graf dibawah ini.

Langkah-langkah penyelesaiannya adalah sebagai berikut:

1.   Perhatikan terlebih dahulu proses simpul yang mempunyai awal dan mempunyai simpul akhir atau simpul tujuan. Dalam kasus ini simpul A sebagai simpul awal dan berdasarkan graf di atas maka gambaran jalur yang bisa ditempuh adalah: A – B, A – C, A – D, dan A – E.

2.   Mencari jalur terpendek tiap-tiap proses dari keempat jalur tersebut dengan menghitung panjang tiap-tiap jalurnya.

3.   Dengan demikian dapat diketahui jalur terpendek dari simpul awal ke simpul tujuan adalah: A – C = 10, A – C – D = 25, A – C – D – B = 45, dan A – E = 45.

DAFTAR PUSTAKA / REFERENSI

Gloor, P. A., Johnson, D. B., Makedon, F., Metaxas, P., (1993), A Visualization System for Correctness Proofs of Graph Algorithms, http://www.wellesley.edu/CS/pmetaxas/visual_proofs.pdf, Computer Science Education, [19 Maret 2010].

Greenberg, H. J., (1998), Greedy Algorithm for Minimum Spanning Tree, http://glossary.computing.society.informs.org/notes/spanningtree.pdf, University of Colorado, Denver, [19 Maret 2010].

Kristanto, A., (2008), Perancangan Sistem Informasi dan Aplikasinya, Gava Media, Yogyakarta.

Mehta, D. P., Sahni, S., (2005), Handbook of Data Structures and Applications, Chapman & Hall/CRC Computer and Information Science Series, United States of America.

Munir, R., (2009), Matematika Diskrit, Edisi 3, Informatika, Bandung.

Oetomo, B. S., (2002), Perencanaan dan Pembangunan Sistem Informasi, Andi, Yogyakarta.

Purbasari, I. Y., (2007), Desain Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Purwanto, E. B., (2008), Perancangan Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Zakaria, T. M., Prijono, A., (2006), Konsep Dan Implementasi Struktur Data, Informatika, Bandung.

Algoritma Prim

Algoritma ini dimulai dari simpul yang berubah-ubah di setiap tingkatnya, diperbolehkan menambah cabang baru untuk membuat susunan pohon baru. Algoritma ini akan tertahan ketika simpul yang sedang dieksplorasi pada graf sudah sampai pada simpul yang dituju. Strategi yang digunakan adalah strategi Greedy dengan menganggap bahwa pada setiap langkah dari pohon merentangnya adalah augmented dan dipilih simpul yang nilainya paling kecil dari semua simpul yang ada.

Metode Greedy merupakan salah satu metode untuk merancang dan mendesain suatu algoritma. Metoda Greedy membangun suatu pohon merentang minimum dengan memeriksa garis demi garis untuk memilih garis dengan bobot kecil dan membuang garis dengan bobot besar, sehingga terbentuk suatu pohon merentang minimum. Metode ini digunakan untuk mendapatkan solusi yang optimal dari suatu permasalahan.

Beberapa peneliti yang menggunakan metode Greedy diantaranya adalah, yang pertama Borůvka tahun 1926, selanjutnya dengan metoda yang sama, penelitiannya ditinjau ulang oleh Choquet tahun 1938, Lukasziewicz, Florek, Perkal, Steinhaus dan Zubrzycki tahun 1951. Algoritma Borůvka dimulai dari n titik terasing dari graf (graf semula tanpa garis), kemudian dari masing-masing titik dipilih garis dengan bobot terkecil yang berhubungan dengan titik tersebut. Karena setiap garis mempunyai dua titik, maka dimungkinkan ada garis yang diperiksa dua kali.

Peneliti selanjutnya adalah Kruskal tahun 1956, yang menyusun garis-garis dalam urutan tidak menurun (non decreasing) dari bobotnya. Langkah awal adalah memilih garis dengan bobot terkecil diantara semua garis. Selanjutnya memilih garis dengan bobot terkecil berikutnya diantara sisa garis, dengan garis tersebut menghubungkan titik di dalam pohon bagian yang sudah dipilih dengan titik diluar pohon bagian.

Matematikawan Vojtěch Jarník tahun 1930 mengenalkan suatu metoda penentuan pohon merentang, yang selanjutnya diteliti kembali oleh Robert C. Prim tahun 1957 dan Dijkstra tahun 1959 sehingga menghasilkan suatu algoritma yang dikenal dengan nama algoritma Prim.

Algoritma Prim menitikberatkan pada pemilihan bobot minimum berdasarkan simpul yang diambil. Dan karena tidak perlu mengurutkan terlebih dahulu, algoritma Prim cocok untuk pohon dengan jumlah simpul banyak. Algoritma Prim akan selalu berhasil menemukan pohon merentang minimum tetapi pohon merentang yang dihasilkan tidak selalu unik.

Langkah-langkah dalam algoritma Prim adalah sebagai berikut:

·         Buat sebuah pohon yang terdiri dari satu simpul (node), dipilih secara acak dari graf.

·         Buat sebuah himpunan yang berisi semua cabang di graf.

·         Ulangi sampai semua cabang di dalam himpunan menghubungkan dua simpul di pohon

o    Hapus dari himpunan satu cabang dengan bobot terkecil yang menghubungkan satu simpul di pohon dengan satu simpul di luar pohon.

o    Hubungkan cabang tersebut ke pohon.

Algoritma Prim dalam pseudocode yaitu:

Procedure Prim(input G:graf, output T:pohon)

{    Membentuk pohon merentang minimum T dari graf terhubung G.

Masukan: graf-berbobot terhubung G = (V, E), yang mana |V| = n

Keluaran: pohon merentang minimum T = (V, E’)

}

Deklarasi

i, p, q, u, v : integer

Algoritma

Cari sisi (p,q) dari E yang berbobot terkecil

T ← {(p,q)}

for i ← 1 to n-1 do

Pilih sisi (u,v) dari E yang bobotnya terkecil namun bersisian dengan suatu simpul didalam T

T ← T U {(u,v)}

Endfor

 Keterangan :

G       =   graf.

T       =   pohon.

V       =   himpunan simpul-simpul.

E       =   himpunan sisi-sisi yang menghubungkan simpul di graf.

E’      =   himpunan sisi-sisi yang menghubungkan simpul-simpul yang ada di pohon.

(p,q)  =   pasangan simpul-simpul yang ada di graf yang membentuk sisi.

(u,v)  =    pasangan simpul-simpul yang ada di pohon yang membentuk sisi dengan bobot terkecil.

DAFTAR PUSTAKA / REFERENSI

Gloor, P. A., Johnson, D. B., Makedon, F., Metaxas, P., (1993), A Visualization System for Correctness Proofs of Graph Algorithms, http://www.wellesley.edu/CS/pmetaxas/visual_proofs.pdf, Computer Science Education, [19 Maret 2010].

Greenberg, H. J., (1998), Greedy Algorithm for Minimum Spanning Tree, http://glossary.computing.society.informs.org/notes/spanningtree.pdf, University of Colorado, Denver, [19 Maret 2010].

Kristanto, A., (2008), Perancangan Sistem Informasi dan Aplikasinya, Gava Media, Yogyakarta.

Mehta, D. P., Sahni, S., (2005), Handbook of Data Structures and Applications, Chapman & Hall/CRC Computer and Information Science Series, United States of America.

Munir, R., (2009), Matematika Diskrit, Edisi 3, Informatika, Bandung.

Oetomo, B. S., (2002), Perencanaan dan Pembangunan Sistem Informasi, Andi, Yogyakarta.

Purbasari, I. Y., (2007), Desain Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Purwanto, E. B., (2008), Perancangan Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Zakaria, T. M., Prijono, A., (2006), Konsep Dan Implementasi Struktur Data, Informatika, Bandung.

Integrasi Data (Data Integration)

PENDAHULUAN

Banyak database, khususnya database tingkat perusahaan, dibuat dengan menggabungkan data dari sumber data internal dan eksternal yang sudah ada, memungkinkan juga dengan data baru untuk mendukung aplikasi baru. Hampir semua organisasi memiliki database yang berbeda-beda untuk tujuan yang berbeda pula.

Penerapan database pada perusahaan misalnya beberapa untuk proses transaksi dalam bagian yang berbeda dari perusahaan (contohnya: perencanaan produksi dan kontrol, dan memasukkan order/pesanan); beberapa untuk kepentingan lokal, taktis, atau pembuatan keputusan strategis (contohnya: kalkulasi harga produk dan ramalan penjualan); dan beberapa untuk koordinasi perusahaan luas dan membuat keputusan (contohnya: untuk manajemen hubungan dengan konsumen dan manajemen rangkaian persediaan). Organisasi-organisasi giat bekerja untuk memecahkan gudang/sumber data, namun membolehkan beberapa tingkat untuk otonomi lokal. Untuk mencapai koordinasi ini, disaat yang sama data harus diintegrasi melalui sumber data yang berbeda.

Tidak mengapa anda mengatakan tidak bisa menghindari berhubungan dengan integrasi data. Sebagai database profesional atau bahkan pengguna dari database yang dibuat dari sumber data lain yang sudah ada, disana banyak konsep integrasi data yang harus anda pahami untuk mengerjakan pekerjaan anda atau untuk memahami masalah yang mungkin akan anda hadapi. Inilah tujuan dari bagian selanjutnya pada bab ini.

Penggudangan data membuat data disimpan untuk mendukung pembuatan keputusan dan inteligensi bisnis. Kita akan meninjau dalam bagian selanjutnya bagaimana data dibawa bersama melalui proses extract-transform-load (ETL): ekstrak-perubahan-pemuatan, yang disebut di bab 11 sebagai lapisan data yang digabungkan dari pendekatan penggudangan data menjadi integrasi data. Tapi sebelum kita menggali lebih detail ke dalam pendekatan ini, sangat membantu untuk meninjau dua pendekatan umum lainnya (tidak termasuk ETL) yang bisa digunakan untuk integrasi data, masing-masing memiliki tujuan berbeda dan masing-masing pendekatan ideal dibawah lingkungan yang berbeda.


PEMBAHASAN

Integrasi data merupakan proses mengkombinasikan dua atau lebih set data agar mempermudah dalam berbagi dan analisis, dalam rangka mendukung manajemen informasi di dalam sebuah lingkungan kerja. Integrasi data menggabungkan data dari berbagai sumber database yang berbeda ke dalam sebuah penyimpanan seperti gudang data (data warehouse).
Alasan perlunya dilakukan integrasi data adalah:

• Data yang sama (misalnya: data penduduk) dapat dipakai bersama antar bagian organisasi (antar instansi).

• Data suatu instansi dapat dipakai bersama oleh instansi-instansi lain yang memerlukan (tidak perlu ada duplikasi data dalam suatu lingkungan organisasi).

• Meskipun fokus integrasi adalah data, tapi perlu juga integrasi hal-hal lain yang terkait.

• Integrasi data perlu dilakukan secara cermat karena kesalahan pada integrasi data bisa menghasilkan ouput/keluaran yang menyimpang dan bahkan menyesatkan pengambilan keputusan nantinya.

Syarat integrasi data dapat dipenuhi dengan berbagai cara seperti konsisten dalam penamaan variabel, konsisten dalam ukuran variabel, konsisten dalam struktur pengkodean dan konsisten dalam atribut fisik dari data. Masalah-masalah yang ada pada integrasi data yaitu heterogenitas data, otonomi sumber data, kebenaran dan kinerja query/permintaan.
Integrasi data membuat penyatuan pandangan dari data bisnis. Pandangan ini bisa dibuat dengan bermacam teknik, yang akan kita paparkan selanjutnya. Bagaimanapun juga, integrasi data bukanlah jalan satu-satunya untuk data bisa digabungkan melalui sebuah perusahaan. Cara lain untuk menggabungkan data adalah dengan:

• Integrasi Aplikasi (Aplication Integration)

Dicapai dengan mengkoordinasikan aliran kejadian informasi antara aplikasi bisnis (arsitektur yang berorientasi pada pelayanan dapat memfasilitasi integrasi aplikasi).

• Integrasi Proses Bisnis (Business Process Integration)

Dicapai oleh perapatan koordinasi aktivitas melalui proses bisnis (contoh: penjualan dan penagihan), jadi aplikasi dapat dibagi dan terlebih lagi integrasi aplikasi dapat terlaksana.

• Integrasi Interaksi Pengguna (User Interaction Integration)

Dicapai oleh pembuatan antar muka pengguna yang memberikan sistem data yang berbeda (contoh: menggunakan pintu keluar perusahaan untuk berinteraksi dengan data dan sistem inteligensi bisnis yang berbeda).

Pusat dari metode integrasi data adalah teknik untuk menangkap perubahan data (Changed Data Capture atau CDC). CDC merupakan teknik untuk menunjukkan data yang telah berubah sejak terakhir aktivitas integrasi data. Jadi hanya data yang telah berubah yang butuh direfres (penyegaran) oleh metode integrasi. Data yang berubah dapat diidentifikasi oleh tanda atau tanggal dari update/perubahaan terakhir. Alternatif lain, catatan transaksi dapat dianalisis untuk melihat data yang telah diperbarui.

Tiga teknik bentuk blok bangunan pendekatan integrasi data yaitu: konsolidasi/penggabungan data, federasi/persekutuan data, dan penyebaran data. Penggabungan data telah diberikan contohnya oleh proses ETL yang digunakan untuk penggudangan data. Kita sediakan bagian selanjutnya dari bab ini yaitu pada penjelasan lebih lanjut dari pendekatan ini. Dua pendekatan lainnya ditinjau sebagai berikut ini.


Federasi/Persekutuan Data (Data Federation)

Federasi data menyediakan pandangan nyata dari data yang terintegrasi (seperti jika semua dalam satu database) tanpa membawa semua data menjadi satu bentuk, sentralisasi database. Federasi data merupakan suatu teknik untuk integrasi data yang menyediakan tampilan sesungguhnya dari data terpadu tanpa membuat satu database terpusat yang sebenarnya. Ketika suatu aplikasi menginginkan data, mesin federasi menerima data yang relevan dari sumber yang aktual (dalam waktu nyata) dan mengirim hasilnya ke aplikasi yang meminta (sehingga terlihat seperti mesin federasi suatu database untuk aplikasi yang meminta). Transformasi data telah selesai secara dinamis seperti yang dibutuhkan. Integrasi Informasi perusahaan (Enterprise Information Integration atau EII) adalah satu syarat yang biasa digunakan untuk masuk ke pendekatan federasi data. XML (Extensible Markup Language) sering digunakan sebagai sarana untuk mentransfer data dan metadata antara sumber data dan server aplikasi.

Keuntungan utama dari pendekatan federasi adalah akses pada data yang sedang berlangsung (tidak ada penundaan karena jarangnya refres/penyegaran dari gabungan data yang tersimpan). Keuntungan lainnya adalah pendekatan ini menyembunyikan detail dari aplikasi lain dan bagaimana data disimpan didalamnya dengan memberikan query/permintaan atau aplikasi. Tetapi, hal ini memberatkan data dalam jumlah besar atau aplikasi yang membutuhkan aktivitas integrasi data yang terus menerus. Federasi membutuhkan beberapa bentuk dari distribusi query/permintaan untuk diciptakan dan dijalankan, tetapi teknologi EII akan menyembunyikan ini dari penulis query/permintaan atau pengembang aplikasi. Federasi bekerja paling baik untuk aplikasi query/permintaan dan laporan (hanya baca), dan ketika keamanan dari data yang bisa dikonsentrasikan pada sumber data dalam keadaan sangat penting. Pendekatan federasi juga digunakan sebagai teknik pembatas-berhenti sampai database yang terintegrasi dan aplikasi yang lebih kuat bisa dibuat.


Penyebaran Data (Data Propagation)

Pendekatan ini menduplikat data melalui database, biasanya dengan penundaan yang mendekati waktu sebenarnya. Data didorong untuk menduplikat tempat ketika update/perubahan berlangsung (yang disebut penyebaran event-driven: jalan-kejadian). Perubahan ini bisa diselaraskan/sinkron atau tidak diselaraskan/tidak sinkron, yang memisahkan update/perubahan ke salinan yang jauh. Teknik Integrasi aplikasi perusahaan (Enterprise Application Integration atau EAI) dan Replikasi Data Perusahaan (Enterprise Data Replication atau EDR) digunakan untuk penyebaran data.

Keuntungan utama dari pendekatan penyebaran data pada integrasi data adalah mendekati waktu nyata/sebenarnya menyelesaikan perubahan data melalui organisasi. Teknologi yang spesial sangat dibutuhkan untuk penyebaran data agar mencapai performa tinggi dan untuk mengatasi update/perubahan yang terus menerus. Waktu nyata aplikasi penggudangan data, memerlukan penyebaran data (yang sering disebut “aliran produksi” dalam penggudangan data).


Manajemen Master Data

Walaupun beberapa aplikasi membutuhkan pandangan yang terintegrasi dari semua data perusahaan, kategori data tertentu diterangkan lebih sering melalui perusahaan dalam sistem operasional dan analisa. Hampir semua sistem informasi dan database umumnya mengarah pada subyek area dari data (orang, benda, tempat) dan seringkali menambahkan data tadi dengan data lokal (transaksi) yang relevan hanya pada aplikasi atau database itu saja. Master data (kadang disebut sumber/referensi data) adalah sesuatu/entitas yang kuat di dalam diagram E-R (Entity-Relationship). Semua aplikasi yang menggunakan data umum dari area-area ini, seperti konsumen, produk, pegawai, tagihan/faktur, dan fasilitas harus mengarah pada harga-harga/nilai-nilai yang sama atau bagian lain dari organisasi tidak dapat berhubungan satu sama lain tanpa kesalahan/kekacauan. Manajemen Master Data (Master Data Management atau MDM) mengarah pada disiplin, teknologi, dan metode untuk memastikan nilai, maksud, dan kualitas dari sumber/referensi data dengan dan melalui berbagai subyek area (White dan Imhoff, 2006). MDM memastikan bahwa setiap orang mengetahui deskripsi yang ada dari produk, gaji yang ada dari pegawai, dan alamat tagihan yang ada untuk konsumen. Master data dapat menjadi simpel sebagai daftar yang diterima seperti nama kota dan singkatan. MDM tidak mengalamatkan data transaksi yang terbagi, seperti pembelian konsumen.

Satu sistem sumber umumnya mengandung “catatan penting” dari seluruh fakta relevan mengenai subyek data. Contohnya, master data konsumen mungkin terintegrasi dari manajemen hubungan konsumen, tagihan, ERP (Enterprise Resource Planning), dan sumber-sumber data pembelian. MDM menentukan sumber terbaik dari setiap satuan data (contoh: alamat atau nama konsumen) dan memastikan bahwa semua aplikasi bersumber dari “catatan penting” yang sesungguhnya. MDM juga menyediakan analisis dan layanan laporan untuk menginformasikan manajer kualitas data tentang kualitas dari master data melalui database (contohnya: persentase dari data kota yang tersimpan di masing-masing database yang memenuhi nilai-nilai master kota).

MDM menjadi makin umum karena gabungan dan akuisisi yang aktif dan untuk memenuhi peraturan, seperti penetapan Sarbanes-Oxley (Sarbanes-Oxley adalah hukum federal Amerika Serikat yang ditetapkan pada 30 Juli 2002. Perundang-undangan ini menetapkan suatu standar baru dan lebih baik bagi semua dewan dan manajemen perusahaan publik serta kantor akuntan publik walaupun tidak berlaku bagi perusahaan tertutup. Akta ini terdiri dari 11 judul atau bagian yang menetapkan hal-hal mulai dari tanggung jawab tambahan dewan perusahaan hingga hukuman pidana). Banyak vendor (konsultan dan penyuplai teknologi) yang ada untuk menyediakan pendekatan dan teknologi MDM.

Ada tiga arsitektur terkenal untuk manajemen master data yaitu: register (registry) identitas, pusat (hub) integrasi, dan tetap (persistent). Di dalam pendekatan register identitas, master data masih dalam sistem sumbernya, dan aplikasi-aplikasi yang mengacu pada register untuk menentukan bagian mana yang disetujui dari keberadaan beberapa sumber data (seperti alamat konsumen). Register membantu masing-masing sistem mencocokkan catatan utamanya dengan catatan utama yang cocok di sistem sumber yang lain dengan menggunakan identitas global untuk setiap instansi dari subyek area. Register menjaga daftar lengkap dari semua elemen master data dan mengetahui sistem sumber mana yang dapat diakses untuk nilai yang terbaik untuk setiap atribut. Jadi, sebuah aplikasi dibolehkan mengakses beberapa database untuk menerima semua data yang dibutuhkannya, dan database mengizinkan lebih banyak aplikasi untuk mengaksesnya. Ini sama seperti gaya federasi pada integrasi data.

Dalam pendekatan pusat integrasi, perubahan data disiarkan (khususnya bersifat asinkron) melalui layanan pusat untuk semua database yang berlangganan/berhubungan. Data yang berlebihan (redundant) di simpan, tapi ada mekanisme-mekanisme untuk memastikan kekonsistenan, akan tetapi setiap aplikasi tidak harus mengumpulkan dan menjaga semua data yang dibutuhkannya. Ketika pusat integrasi ini dibuat, ia bertindak seperti bentuk penyebaran integrasi data. Tetapi dalam beberapa kasus, pusat penyimpanan master data juga dibuat untuk beberapa master data, jadi mungkin ini adalah kombinasi dari penyebaran dan penggabungan. Bagaimanapun juga, bahkan dengan penggabungan, sistem pencatat atau pemasukan (sistem transaksi yang didistribusikan) masih mengatur databasenya sendiri termasuk data lokal dan data yang disebarkan sesuai yang mereka butuhkan untuk hampir seluruh proses.

Dalam pendekatan tetap, satu catatan gabungan diatur dan semua aplikasi menggambarkan satu “catatan penting” aktual untuk data umum. Jadi, pekerjaan cukup penting untuk mendorong semua data yang ditangkap dalam setiap aplikasi kepada catatan yang tetap yang menyebabkan hal itu mengandung nilai-nilai yang baru dan menuju pada catatan penting ketika sistem manapun membutuhkan data umum. Ada kemungkinan terjadi kelebihan (redundancy) data dengan pendekatan yang tetap karena setiap database aplikasi bisa juga mengatur versi lokal dari elemen-elemen data dalam keleluasaannya, bahkan mengatur dalam tabel penggabungan yang tetap. Ini adalah pendekatan penggabungan integrasi data murni untuk master data.
Penting untuk menegaskan bahwa manajemen master data adalah bagian dari integrasi data karena hanya master data yang diintegrasikan. Master data tidak hanya merupakan bagian dari tabel pada setiap database (tabel untuk subyek besar dari pelanggan, produk, fasilitas, karyawan/pegawai, dan lain-lain) tetapi hanya elemen-elemen data itu yang terbagi melalui perusahaan. Data yang hanya untuk penggunaan lokal dan data yang harus diamankan oleh sistem lokal, tidak termasuk dari arsitektur integrasi data bahkan untuk catatan master data.

Ada beberapa bentuk spesialisasi dari MDM. Satu yang paling didiskusikan adalah Integrasi Data Konsumen (Costumer Data Integration atau CDI), yang mana MDM hanya fokus pada data konsumen (Dyche dan Levy, 2006). Selain itu adalah Integrasi Data Produk (Product Data Integration atau PDI). Bentuk apapun dari MDM tidak dimaksudkan untuk menggantikan gudang data, terutama karena hanya master data dan biasanya hanya master data yang sedang berjalan yang diintegrasi, dimana gudang data membutuhkan pandangan asal usul dari master dan transaksi data. Tetapi sebuah gudang data, bisa jadi (dan sering kali) salah satu dari sistem yang menggunakan master data, apakah sebagai sumber untuk menyuplai gudang atau sebagai perluasan dari gudang untuk hampir setiap data ketika pengguna gudang ingin masuk lewat sumber data. MDM melakukan pembersihan data, seperti apa yang dilakukan dengan penggudangan data. Dengan alasan ini, MDM juga bukan sebuah tempat penyimpanan data operasional (lihat bab 11 untuk deskripsi dari sebuah ODS). MDM juga dipertimbangkan oleh banyak orang sebagai bagian dari infrastruktur data dari organisasi, dimana sebuah ODS (Operational Data Store) dan bahkan penggudangan data, dianggap sebagai landasan aplikasi.

Sebuah model data untuk MDM secara nyata benar-benar simpel. Masing-masing subyek area cirinya dikelilingi oleh MDM karena disana tidak ada data transaksi yang terhubung dengan kategori master yang berbeda. Masing-masing tabel master data intinya adalah sebuah file datar (flat file), bahkan tanpa hubungan hirarki. MDM dengan tegas mengambil satu pandangan dari data tentang setiap instansi dari setiap tipe master data. Karena master data adalah “catatan penting”, tidak ada satupun aplikasi yang memiliki master data. Agaknya, master data adalah benar-benar aset perusahaan, dan manajer bisnis harus mengambil tanggung jawab untuk kualitas master data. Pelayanan data dan pemerintahan data yang kuat sangat penting sekali untuk sebuah program MDM menjadi efektif.

Pohon Alfabet Optimal (Analisis Algoritma)

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.

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.