Penggunaan Ternary Search Tree Dalam Melakukan
Penggunaan Ternary Search Tree dalam MelakukanAutocompleteTimotius Kevin Levandi 13510056Program Studi Teknik InformatikaSekolah Teknik Elektro dan InformatikaInstitut Teknologi Bandung, Jl. Ganesha 10 Bandung 40132, Indonesiakevin levandi@students.itb.ac.idAbstrak—Autocomplete atau kadang disebut jugaAutosuggest merupakan fitur yang melibatkan prediksiterhadap pengetikan sebuah kata atau frase oleh penggunatanpa harus mengetiknya secara lengkap berdasarkan hurufatau frase awal yang telah dimasukkan oleh penggunatersebut. Fitur ini sering terdapat dalam sebuah searchengine, web browser, e-mail program, source code editor,database query tool, word processors, dan command lineinterpreter. Fitur ini sangat mempermudah pengguna,misalnya untuk mempercepat pengetikan terutama bilamenyangkut penulisan fungsi yang komponen hurufnyapanjang dan case sensitive pada suatu source code editor,atau untuk mempercepat pencarian alamat email tujuandalam email program tanpa harus menghapal seluruh alamatemail yang kebanyakan panjang-panjang.Makalah ini akan membahas pengaplikasian TernarySearch Tree (TST) sebagai salah satu metode yang cukupdianggap efektif untuk melakukan autocomplete secaraumum terhadap masukan teks oleh pengguna.Kata kunci—autocomplete, Ternary Search Tree (TST).I. PENDAHULUANSejak lebih dari beberapa dekade yang lalu, manusiasudah banyak mendapat kemudahan dalam melakukanaktivitas hidup kita melalui komputer dan jaringaninternet. Sejak mulai keluar dan populernya searchengine, kita tidak perlu lagi kerepotan mencari suatu situssebagai untuk mencari informasi atau referensi. Denganhanya mengetikkan beberapa kata kunci pada search boxdan menekan Enter atau meng-click tombol Go. Semuasitus yang memiliki keterkaitan dengan masukan kitaditampilkan mulai dari prioritas paling tinggi.Kemudahan itu sekarang sudah lebih disempurnakan.Yang menarik sekarang adalah, selama pengetikanberlangsung, biarpun kata yang kita ketik belum selesai,sebuah daftar yang berisi saran mengenai kemungkinankata bahkan frase atau kalimat yang akan kita ketik akanotomatis muncul. Selanjutnya kita dapat memilih langsungdi antara daftar tersebut untuk memasukkan teks yang kitakehendaki dalam search box itu tanpa harus repot-repotmenyelesaikan suatu pengetikan kalimat yang panjang.Bila kita perhatikan, fenomena ini bukan hanya terdapatpada search engine. Hal ini juga sering terjadi di sourcecode editor ketika kita melakukan gunakan suatu built-in function, sebuah daftar yangberisi saran kemungkinan fungsi tersebut ditampilkan.Kita jadi tidak perlu lagi menyelesaikan pengetikan,terutama pada fungsi-fungsi yang tersusun oleh banyakhuruf dan case sensitive yang biasanya banyak terdapatpada pemrograman berbasis obyek. Kita cukup memilihsalah satu isi daftar tersebut sesuai kehendak kitasebelumnya. Kasus sama juga terjadi dalam pengisianalamat email tujuan saat akan mengirim email, atau saatkita memakai word processor dan hendak mengetikkannama hari atau nama bulan. Hal ini, enyempurnaan/penyelesaian otomatis).Autocomplete merupakan fitur yang membantu kitadalam menyelesaikan pengetikan secara cepat dengan caramenyajikan pilihan kata, frase, atau kalimat yang mungkinmerupakan kelanjutan dari apa yang sudah kita ketik. Bilapengetikan dilakukan lebih lanjut, maka ada kemungkinanbeberapa pilihan yang telah disajikan tadi hilang dandigantikan dengan pilihan baru. Ini terjadi apabila kata,frase, atau kalimat dalam pilihan tersebut sudah tidaksesuai lagi dengan pengetikan beberapa karakter lanjutanyang baru saja dilakukan. Hal ini menjadi semacampencarian sekaligus penyaringan daftar pilihan yangmuncul dengan acuannya adalah posisi kursor dankesamaan karakter yang telah ditulis sebelum kursortersebut. Selanjutnya kita bisa memilih untukmemasukkan salah satu pilihan tersebut tanpa harusmenyelesaikan pengetikan yang panjang.Ada beberapa metode yang digunakan dalammerealisasikan autocomplete seperti menggunakan BinarySearch Tree (BST), Multiway Tree (Trie), atau TernarySearch Tree (TST). Pada makalah ini kita akanmemfokuskan pembahasan pada Ternary Search Treeyang bisa dibilang menggabungkan sifat-sifat Binary Treedan Multiway Tree.II. DASAR TEORIII.ATERNARY SEARCH TREETernary Search Tree (TST) atau 3-ary Search TreeMakalah II2092 Probabilitas dan Statistik – Sem. I Tahun 2010/2011
adalah struktur data pohon dengan tiap simpulnyamemiliki paling banyak tiga simpul anak, biasanyadiistilahkan sebagai “kiri”, “tengah” dan “kanan”. Simpulyang memiliki anak disebut sebagai simpul orangtua dansimpul anak bisa memiliki penunjuk ke orangtuanya. Diluar pohon sering dibuat suatu penunjuk terhadap simpul“akar” (leluhur semua simpul) bila memang ada. Simpulmanapun dalam struktur data bisa diakses denganmemulai dari simpul akar dan secara berulang-ulangmengikuti penunjuk ke salah satu anak kiri, tengah ataukanan.TST merupakan suatu struktur data Trie di mana simpulanak suatu struktur data Trie standar disusun seperti padaBinary Search Tree (BST). Pencarian sebuah string padaTST terdiri atas sederet pencarian biner, satu untuk tiapkarakter dalam suatu string. Karakter saat ini dalam suatustring dibandingkan dengan karakter pada simpul saat ini.Peraturannya demikian: Jika lebih kecil, pencarian berlanjut ke simpul anaksebelah kiri. Jika lebih besar, pencarian berlanjut ke simpul anaksebelah kanan. Jika sama, pencarian berlanjut ke simpul anak tengahdan perbandingan dilanjutkan untuk karakterselanjutnya dalam string tersebut.Multiway Tree (Trie) adalah suatu pohon n-ary, yaitupohon berakar yang setiap simpul cabangnya mempunyaipaling banyak n buah anak. Misalnya untuk masukan datastring standar dengan anggota himpunannya hanya hurufalfabet dari A sampai Z, maka pencarian simulai darisimpul akar yang mewakili string dengan panjang nol,yang kemudian memiliki 26 anak, di mana setiap anakmemiliki 26 anak, dan seterusnya. Sistem ini memakanruang sangat banyak untuk setiap penambahan ketinggianpohonnya, yaitu untuk setiap perbandingan karakterberikutnya (bila ada) dalam string tersebut. Hal ini bukansesuatu yang jarang terjadi, karena suatu string pastinyamemiliki banyak karakter.Gambar 2: Contoh Multiway Tree, setiap simpul memiliki 26 anaklagi yang merupakan karakter A sampai ZBinary Search Tree (BST) mirip seperti Multiway Treedengan setiap simpul cabangnya mempunyai palingbanyak dua buah anak. Semua simpul pada anak sebelahkiri akan memiliki nilai lebih kecil, sedangkan semuasimpul pada anak sebelah kanan memiliki nilai lebih besaruntuk semua simpul. Pencarian dimulai dari simpul akar.Pada perbandingan string menggunakan metode BST, kitamungkin harus langsung membandingkan banyak karakterpada suatu simpul. Setiap simpul mengandung sebuahstring secara keseluruhan.Gambar 1: Contoh TST dengan string “as”, “at”,“cup”, “cute”, “he”, “i”, dan “us”Untuk menghitung jumlah simpul pada ternary treedapat diketahui sebagai berikut:Misalkan h adalah tinggi ternary tree dan M(h) adalahjumlah maksimum simpul pada ternary tree denganketinggian h, maka:hM (h) 1 3 9 . 3h 3iGambar 3: Contoh BST dengan 12 kata berhuruf duai 0atauM ( h) II.B3h 12MULTIWAY TREE DAN BINARY SEARCH TREESelanjutnya karena istilah Multiway Tree (Trie) danBinary Search Tree (BST) akan banyak disebut sebagaipembanding TST, maka berikut diberikan secara singkatdefinisi dari masing-masing struktur pohon tersebut.III. ANALISIS TERHADAP KEMANGKUSAN TERNARYSEARCH TREE DALAM APLIKASI AUTOCOMPLETESistem TST merupakan gabungan dari Multiway Treedan BST, serta disinyalir memiliki kemangkusan yanglebih baik bila dibandingkan kesua sistem lainnya itu bilaberdiri sendiri.III.A PERBANDINGAN TERNARY SEARCH TREE DAN BINARYSEARCH TREEMakalah II2092 Probabilitas dan Statistik – Sem. I Tahun 2010/2011
Seperti yang sudah dikatakan sebelumnya, BST dalampenyusunan string pada setiap simpulnya diharuskansesuai aturan yaitu simpul anak kiri memiliki nilai lebihkecil dari orangtua yang sekarang, dan simpul sebelahkanan memiliki nilai yang lebih besar. Ini menyebabkanproses memasukkan suatu kata kunci baru pada suatu saatke dalam pohon (memasukkan simpul baru) harus benarbenar memperhatikan keterurutan nilai string pada simpulsimpul dalam pohon, oleh karena itu perlu menggunakanpengurutan (sorting). Sedangkan pada TST pengurutantidak sesensitif pada BST.TST memakan lebih banyak alokasi ruang daripadaBST, dan menggunakan algoritma yang lebih rumit karenabanyaknya simpul yang dimilikinya. Walaupun begitukeuntungan-keuntungan sebagai berikut didapat: Simpul-simpul TST lebih sederhana karena berisikarakter, sedangkan simpul BST berisi suatu datastring. Proses perbandingan pada TST menjadi lebihsederhana. Alasannya sama seperti sebelumnya.Membandingkan satu karakter tentu lebih mudahdaripada membandingkan deretan karakter dalamdata string Redundansi prefiks secara otomatis dihilangkan.Prefiks bisa diibaratkan sebagai kumpulan orangtuaorangtua terdahulu, yaitu dalam pengetikan adalahhuruf-huruf di sebelah kiri kursor. Pada contohgambar BST sebelumnya bisa kita lihat bahwapendefinisian potongan kata “foo” pada string “foo”dan “foobar” dilakukan lebih dari satu kali. Inidisebut redundansi. Pada TST redundansidihilangkan karena untuk hasil pencarian “foobar”akan diteruskan dari penelusuran “foo” denganmengambil cabang ke simpul kiri untuk mencarihuruf „b‟. Tidak perlu dereferensi ganda. Mirip sepertipenjelasan redundansi di atas, hanya saja dereferensiadalah mengenai penunjukan terhadap simpulorangtua, yaitu dalam pengetikan adalah bila kitamenghapus huruf-huruf yang sudah kita ketik.Misalnya pada BST yang mengandung string“resep”, “resep kue”, dan “resep masakan”.Dereferensi “resep masakan” ke “resep” harusmelewati “resep kue” dulu sebagai orangtua “resepmasakan” (“resep masakan” adalah simpul anaksebelah kanan “resep kue”). Pada TST hal ini tidakperlu terjadi.Dari sini bisa dilihat bahwa TST menawarkan performayang lebih baik daripada BST walaupun cakupan alokasiruang yang dibutuhkan lebih banyak.III.B PERBANDINGAN TERNARY SEARCH TREE DANMULTIWAY TREEBila dibandingkan dengan sistem Multiway Tree, sistemTST membantu kita terhindar dari kebutuhan ruang yangtidak perlu. Bila Multiway Tree memiliki sekitar2NRpenunjuk dan TST memiliki sekitar 3N Rlog( R)penunjuk. Ketika nilai R kecil Multiway Tree dan TSTmemiliki jumlah pointer yang mirip. Ketika semakinbesar, jumlah pointer pada Multiway Tree meledakdibandingkan dengan TST. Karena itu perumusan TSTakan menjadi jauh lebih mangkus dalam hal alokasi ruangdalam kasus terburuk dibandingkan perumusanMultiwayTree.Gambar 4: 3D Plot yang menunjukkan hubungan Multiway Tree vs.TST dalam hal banyaknya alokasi ruang yang diperlukanHarga yang harus dibayar untuk kemangkusan iniadalah bila Multiway Tree kita harus mengunjungi(traverse) paling banyak sejumlah panjang kata yangdicari, pada TST kita melakukan sampai tiga kalinyapaling banyak pada kasus terburuk.Namun kasus seperti ini jarang terjadi dan rata-rata bisaditangani lewat beberapa peningkatan yang diberlakukanpada struktur dasarnya.III.C PENINGKATANTREEKEMANGKUSAN TERNARY SEARCHKebutuhan TST yang lumayan besar dalam hal alokasiruang dapat ditekan sehingga kemangkusannya dapatditingkatkan dengan beberapa cara sebagai berikut.Cara pertama melibatkan pemampatan simpul daunyang ada. Simpul daun dalam sebuah pohon adalah simpulMakalah II2092 Probabilitas dan Statistik – Sem. I Tahun 2010/2011
berderajat nol (tidak mempunyai anak). Dengan demikianalih-alih membiarkan rantai panjang simpul-simpul padasimpul daun, kita dapat memampatkannya menjadi satusimpul saja sehingga pemeriksaan akhir terhadap stringyang ditemukan dapat dilakukan dengan lebih mangkus.(a)(a)(b)(b)Gambar 5: (a) TST dengan struktur dasar awal; (b) TST setelahdilakukan peningkatan dengan melakukan pemampatan pada simpuldaunnyaCara kedua menggabungkan kebaikan Multiway Treedan TST. Caranya adalah dengan mengganti struktur akarmenjadi seperti Multiway Tree dengan simpul sejumlah R.Kemudian sisa pohonnya menggunakan TST denganpemampatan pada simpul daun. Dalam praktiknyapeningkatan ini menghasilkan penambahan kecepatanyang sangat signifikan. Teorinya menurut Sedgewick,peningkatan ini memotong jumlah perbandingan yangdiperlukan sampai setengahnya.Cara ketiga dilakukan hampir sama dengan carapertama, yaitu melibatkan pemampatan simpul. Namunalih-alih memampatkan simpul daun, simpul dalam yangdimampatkan. Simpul dalam adalah simpul yangmempunyai anak. Cara ini dilakukan untuk menghematjumlah percabangan dan perbandingan karakter bila sudahjelas terdapat batasan kemungkinan untuk suatu rantaikarakter yang menghasilkan suatu kata kunci. Dengandemikian sedikit mirip BST, kita melakukan perbandinganstring pada beberapa simpul dalam.Untuk lebih jelasnya, misalnya terdapat Ternary Treesebagai berikut.Gambar 6: (a) TST dengan struktur data awal; (b) TST setelahdilakukan peningkatan dengan melakukan pemampatan pada simpuldalamnyaDari gambar kita bisa melihat adanya rantai panjangpenunjuk dari „o‟ yang tidak punya cabang ke karakterlain selain ke „o‟ selanjutnya. Untuk mempermudahpengertian, anggap karakter „o‟ yang ditunjuk f sebagai„o1‟ dan karakter „o‟ yang ditunjuk „o1‟ sebagai „o2‟Alih alih membiarkan rantai seperti ini menambahalokasi ruang, kita dapat menggabungkannya menjadistring “oo” dalam satu simpul saja. Pemampatan initentunya dilakukan bila memang tidak ada string katakunci yang menggunakan karakter lain setelah karakter„o1‟ selain karakter „o‟. Sebagai contoh, misalkan tidakada string kata kunci seperti “foe”, “foam”, atau “fog”;yang ada hanya “foobar”, “footage”, atau “fool”. Dengandemikian keputusan untuk menjadikan „o‟ dan „o‟ satustring “oo” dalam sebuah simpul adalah tepat, dan akanmeningkatkan kemangkusan TST dalam autocomplete.Cara keempat untuk meningkatan kemangkusanpencarian dalam TST, kita tidak perlu misalkan,menggunakan penunjuk ke semua karakter alfabet.Karakter yang tidak terdaftar atau jarang sekali digunakansetelah karakter tertentu dalam suatu string tidak perludimasukkan sebagai simpul anaknya.Sebagai contoh, karakter „p‟ dapat menunjuk karakter„r‟ yang kemudian dapat menunjuk beberapakemungkinan karakter lain dalam suatu search engineyang akan mengarah pada beberapa kemungkinan stringkata kunci seperti “premonition”, “profile”, atau“premier”. Namun tidak ada string kata kunci yang akandihasilkan ataupun diteruskan sedemikian bila karakterMakalah II2092 Probabilitas dan Statistik – Sem. I Tahun 2010/2011
yang ditunjuk setelah „r‟ adalah „m‟. Oleh karena itu diantara simpul-simpul kiri „r‟ tidak perlu dialokasikansuatu simpul untuk menampung karakter „m‟.Cara kelima adalah dengan melakukan analisisterhadap kata-kata kunci yang lebih banyak digunakanoleh orang-orang dibandingkan kata-kata kunci lainnyadengan prefiks yang sama. Kemudian kata-kata kunciyang lebih populer ini diletakkan dan diatur sedemikianrupa sehingga sebisa mungkin lebih dekat ke akar. Iniakan menyebabkan kemungkinan pencarian danperbandingan dapat dilakukan lebih cepat tanpa harusmelewati banyak percabangan-percabangan yang kurangperlu akibat salah diletakkannya kata kunci yang anditampilkannya hasil pencarian. Kita bisa membatasiberapa pilihan hasil tampilan yang sementara ituditampilkan. Bila jumlah pilihan yang ingin ditampilkanbanyak, maka akan perlu waktu lebih lama untukmencapai daun-daun berisi sring kata kunci denganprefiks seperti yang dimasukkan pengguna. Namun terlalusedikit pilihan juga tidak akan membantu pengguna. Olehkarena itu hendaknya ditetapkan jumlah tampilan pilihandalam daftar yang cukup beralasan.bahasa pemrograman. Berikut adalah contoh sederhanaimplementasi TST dalam C#.IV. TERNARY SEARCH TREE DALAM PELADENDi dalam jaringan (web), sejumlah pekerjaanmelakukan autocomplete dilakukan oleh peladen (server).Kadang kumpulan dari kemungkinan-kemungkinanpenyempurnaan dari kata yang dimasukkan sangatlahbanyak, jadi bukanlah ide bagus untuk melakukanpengunduhan semuanya kepada klien. Alih-alih ternarytree disimpan di dalam peladen dan klien akan mengirimprefiks permintaan kepada peladen.VI. KESIMPULANGambar 7: Ilustrasi menunjukkan bagaimana autocomplete dilakukanoleh peladen berdasarkan masukan prefiks permintaan dari penggunaV. IMPLEMENTASI TERNARY SEARCH TREETerdapat banyak implementasi TST dalam berbagaiDari pembahasan di atas dapat disimpulkan hal-halsebagai berikut. Fitur autocomplete dapat dijalankan dengan baikmenggunakan pencarian dalam struktur data pohon. Ternary Search Tree merupakan sistem struktur datapohon termangkus yang dapat digunakan untukmelakukan autocomplete yang menggabungkankebaikan Binary Search Tree dan Multiway Tree. Ternary Search Tree menggunakan alokasi ruangyang lebih banyak daripada Binary Search Tree,namun dengan sistem perbandingan yang lebihsederhana. Ternary Search Tree menggunakan alokasi ruangyang lebih sedikit daripada Multiway Tree, namundengan sistem perbandingan yang lebih rumit.Makalah II2092 Probabilitas dan Statistik – Sem. I Tahun 2010/2011
VII. REFERENSI[1][2][3][4][5][6][7]Munir, Rinaldi. Struktur Diskrit, edisi keempat. 2008. Bandung:Penerbit Autocomplete, 10 Desember /wiki/Ternary search tree, 10 Desember2011. Ternary Tree. From http://en.goldenmap.com/Ternary tree,10 Desember 2011.Adam Berger et al. (2007). Ternary Search Tree. Fromhttp://c2.com/cgi/wiki?TernarySearchTree, 10 Desember 2011.Igor Ostrovsky (2009). Efficient auto-complete with ternarysearchtree. From th-a-ternary-search-tree/, 11 Desember 2011.Tim Henderson (2011). Ternary Search Tries for Fast FlexibleString Search : Part 1. From r-fast-flexible-string#!/, 11 Desember 2011.PERNYATAANDengan ini saya menyatakan bahwa makalah yang sayatulis ini adalah tulisan saya sendiri, bukan saduran, atauterjemahan dari makalah orang lain, dan bukan plagiasi.Bandung, 11 Desember 2011Timotius Kevin Levandi 13510056Makalah II2092 Probabilitas dan Statistik – Sem. I Tahun 2010/2011
Search Tree (BST), Multiway Tree (Trie), atau Ternary Search Tree (TST). Pada makalah ini kita akan memfokuskan pembahasan pada Ternary Search Tree yang bisa dibilang menggabungkan sifat-sifat Binary Tree dan Multiway Tree. . II. DASAR TEORI II.A TERNARY SEARCH TREE Ternary Search Tr
Ternary AND & NAND Gates Generally, AND gate operation is defined as Y Min (A, B) i.e., where Y is an output and A, B are the inputs. . ADDERS USING TERNARY LOGIC TERNARY HALF ADDER (THA) Ternary half adder is a circuit for the addition of two ternary inputs. The circuit does not consider a
Civic Style - Marker Symbols Ü Star 4 û Street Light 1 ú Street Light 2 ý Tag g Taxi Æb Train Station Þ Tree 1 òñðTree 2 õôóTree 3 Ý Tree 4 d Truck ëWreck Tree, Columnar Tree, Columnar Trunk Tree, Columnar Crown @ Tree, Vase-Shaped A Tree, Vase-Shaped Trunk B Tree, Vase-Shaped Crown C Tree, Conical D Tree, Conical Trunk E Tree, Conical Crown F Tree, Globe-Shaped G Tree, Globe .
dalam penggunaan ICT demi memantapkan pengajaran dan pembelajaran. Dengan kajian ini juga masalah- masalah yang dihadapi oleh para guru dalam penggunaan ICT akan dapat dikenalpasti. Ini untuk meningkatkan motivasi para guru dalam penggunaan ICT pada masa akan datang. OBJEKTIF KAJIAN Kajian ini bertujuan untuk mengkaji : 1.
melalui komunikasi verbal, nonverbal, dan atau paralinguistic. Strategi pesan . abel 21 Penggunaan Bahasa Jawa Dalam April 2011 79 abel 22 Penggunaan Bahasa Prokem Dalam disi April 2011 80 abel 23 Penggunaan Bahasa Asing Dalam " Edisi April 2011 80 abel 24 Penggunaan Bahasa Serapan Dalam .
future, we will design full adder, SRAM etc using ternary logic based CNTFET. 6. Conclusion . The ternary inverters, NAND, NOR and Half adder design simulation is performed using Hspice. The simulation shows high performance at low power voltage supply. The power dissipation across ternary half adder is 0.32µW and the delay
Ternary blends are used with a synthetic alkylbenzene lubricant. 4. What is the difference between a ternary blend and an azeotropic blend? a) Ternary blends are three-part mixtures. They are common types of refrigerant blends that contain HCFCs. Ternary
3. Apakah kepercayaan memiliki pengaruh terhadap minat penggunaan pada aplikasi OVO? 1.2 Tujuan Penelitian Tujuan yang diharapkan dalam penelitian ini adalah 1. Untuk mengetahui pengaruh persepsi manfaat terhadap minat penggunaan pada aplikasi OVO. 2. Untuk mengetahui pengaruh kemudahan penggunaan terhadap minat penggunaan pada aplikasi OVO. 3.
American Revolution American colonies broke away from Great Britain Followed the ideas of John Locke –they believed Britain wasn’t protecting the citizen’s rights 1st time in modern history ended a monarchy’s control and created a republic Became a model for others French Revolution Peasants tired of King Louis XVI taxing them and not the rich nobles Revolted and .
