Implementasi algoritma depth first search pada sistem pencarian dokumen sangat diperlukan oleh pihak tertentu yang membutuhkan data di dalam dokumen tersebut. Pencarian Kembali terhadap data di dalam dokumen menggunakan Algoritma Depth First Search menjadi fokus dalam pembahasan. Pembahasan ini bertujuan untuk menghasilkan aplikasi pencarian yang relevan terhadap kata kunci pencarian yang diharapkan meningkatkan efisiensi waktu bagi pengguna. Metode pengembangan sistem yang digunakan adalah Waterfall yang terdiri dari beberapa tahapan diantaranya, Analysis, Design, Code, Testing, dan Maintenance. Dengan menggunakan alat bantu flowchart untuk membuat rancangan sistem yang akan dibangun.
Pendahuluan
Perkembangan teknologi dewasa ini khususnya internet berkembang sangat pesat. Hal ini diiringi juga dengan semakin berkembangnya Teknologi Informasi yang dibutuhkan oleh pengguna sehingga mengakibatkan munculnya suatu cabang ilmu baru dalam teknologi informasi, yaitu pencarian informasi (information retrieval). Sejalan dengan perkembangan teknologi, maka perkembangan peralatan juga ikut mengambil andil yang besar untuk mendukung perkembangan pertukaran informasi yang semakin hari semakin canggih. Hampir semua kecanggihan teknologi yang memberikan kemudahan kepada user dalam menemukan apa yang diinginkannya. Salah satu kemudahan yang diberikan adalah menyediakan fasilitas searching yang digunakan untuk memberikan kemudahan mendapatkan lebih banyak informasi yang berbentuk dokumen. Pencarian informasi yang tepat dan sesuai kebutuhan menjadi sangat penting dengan semakin mudahnya memperoleh informasi dari seluruh dunia sebagai akibat perkembanga teknologi informasi dan komunikasi yang semakin pesat. Oleh karena itu, teknik untuk memperoleh dokumen dengan isi yang sesuai dengan kebutuhan informasi sangat diperlukan. Dalam penelitian ini digunakan sebuah cara untuk melakukan pencarian kembali dokumen dengan menggunakan Algoritma Depth First Search.
Masalah yang dihadapi
1. Searching dokumen ini tidak membuat pencarian berdasarkan kombinasi katakata penggolongan AND, OR, dan NOT serta penggunaannya yang tidak menggunakan case sensitive
2. Dokumen yang digunakan sebagai data dalam proses pencarian ini berupa beberapa dokumen teks yaitu rtf, doc, pdf dan txt
3. Tidak membahas semantic kata
4. Jumlah kata merupakan penjumlahan kata yang relevan dengan kata kunci di dalam dokumen
Cara menyelesaikan masalah
Dalam penelitian ini digunakan sebuah cara untuk melakukan pencarian kembali dokumen dengan menggunakan Algoritma Depth First Search.
Penjelasan algoritma
Depth First Search adalah salah satu algoritma yang digunakan untuk pencarian jalur. Algoritma ini mirip dengan algoritma BFS (Breadth First Search). Jika algoritma BFS melakukan perhitungan secara terurut, dari urutan pertama sampai urutan terakhir, maka algoritma ini melakukan kebalikannya, yaitu melakukan perhitungan secara terurut dari urutan terakhir, barulah mundur ke titik sebelumnya sampai pada titik pertama.
Alur algoritma yang digunakan
1.1. Information Retrieval
Model sistem IR menentukan detail sistem IR yaitu, meliputi:
1 Representasi dokumen dan query.
2 Fungsi pencarian.
3 Notasi kesesuaian (relevance notation) dokumen terhadap query.
Yang dimaksud dengan fungsi pencarian adalah bagaimana mesin mengolah pertanyaan untuk dicocokkan dengan dokumen, lalu mengambil dokumen yang relevan. Bagian ini terbagi menjadi beberapa bagian, yaitu:
1 Cara memilih kata (term) untuk indeks.
2 Cara menindeks kata.
3 Cara membobot kata.
Bagian yang paling signifikan pengaruhnya adalah pembobotan kata. Cara pembobotan kata mencirikan bagaimana sebuah sistem temu kembali informasi di bangun. Sistem temu kembali informasi digunakan untuk menemukan kembali informasi informasi yang relevan terhadap kebutuhan pengguna dari suatu kumpulan informasi secara otomatis. Kerangka dari sistem temu-kembali informasi sederhana terbagi menjadi dua bagian. Bagian yang pertama adalah bagian si pencari informasi atau pengguna dari sistem. Pengguna dari sistem temu-kembali informasi harus menerjemahkan informasi yang dicarinya agar dapat diproses oleh sistem dengan cara memasukkan kata kunci. Kata kunci tersebut nanti diproses menjadi sebuah query yang dapat dimengerti oleh komputer. Bagian yang kedua adalah bagian dari dokumen. Pada bagian ini dokumen-dokumen direpresentasikan dalam bentuk indeks. Nanti query dari pengguna akan diproses melalui fungsi kesamaan untuk membandingkan query dengan indeks dari dokumen untuk mendapatkan dokumen yang relevan.
pada Gambar 1. memperlihatkan bahwa terdapat dua buah alur operasi pada sistem temu kembali informasi. Alur pertama dimulai dari koleksi dokumen dan alur kedua dimulai dari query pengguna. Alur pertama yaitu pemrosesan terhadap koleksi dokumen menjadi pangkalan data indeks dan tidak tergantung pada alur kedua. Sedangkan alur kedua tergantung dari keberadaan pangkalan data indeks yang dihasilkan pada alur pertama.
1.2.Pencarian
Searching berusaha meminta content yang akan menjadi patokan pencarian sebuah dokumen dengan kriteria yang spesifik (biasanya yang berisi kata atau frasa yang kita tentukan) dan memperoleh daftar file yang memenuhi kriteria tersebut. Searching biasanya menggunakan indeks untuk mencari dokumen setelah pengguna memasukkan kriteria pencarian. Metode searching umum akan mencari kata kunci yang Anda masukkan ke semua informasi dalam katalog dan naskah data Pencarian dapat dibagi 2 bagian, yaitu:
1. Pencarian internal adalah pencarian terhadap sekumpulan data yang disimpan di dalam memori utama.
2. Pencarian eksternal adalah pencarian terhadap sekumpulan data yang disimpan di dalam memori sekunder, seperti disk.
1.3.Text Input Stream
Untuk membaca teks dari sebuah file, maka perlu dibuat objek TextInputStream. TextInputStreams memiliki metode yang memungkinkan untuk membaca dari sebuah file yang dimiliki Xojo dan fitur close setelah selesai pada akhir pembacaan file. File yang tidak mendukung UTF-8, maka harus diatur nilai properti Encoding. Ketika membaca sebuah file teks yang berasal dari sistem operasi lain atau dalam bahasa lain (atau campuran bahasa), mungkin perlu untuk menetapkan pengkodean teks yang digunakan ketika file tersebut ditulis. Jika tahu pengkodean, menggunakan modul Encodings untuk mendapatkan encoding dan menggunakannya untuk mengatur nilai properti. Berikut adalah contoh Encoding objek TextInputStream untuk membaca sebuah file teks yang menggunakan pengkodean.
MacRoman:
Dim f As FolderItem =
GetOpenFolderItem("text")
If f <> Nil Then
If f.Exists Then
Dim t As TextInputStream
Try
t = TextInputStream.Open(f)
t.Encoding =
Encodings.MacRoman
TextArea1.Text = t.ReadAll
Catch e As IOException
t.Close
MsgBox("Error accessing file.")
End Try
End If
End If
Seperti kita lihat, variabel f dideklarasikan ke dalam tipe FolderItem dan t sebagai TextInputStream. “t = TextInputStream.Open(f)” menunjukkan bahwa modul TextInputStream untuk membuka file text yang telah disimpan di variabel f. Kemudian di encoding : t.Encoding = Encodings.MacRoman.
1.4. Depth Depth Search
Menurut Erwin [2], Pencarian dengan metode ini dilakukan dari node awal secara mendalam hingga yang paling akhir (deadend) atau sampai ditemukan. Dengan kata lain, simpul cabang atau anak yang terlebih dahulu dikunjungi. Sebagai ilustrasinya dapat dilihat
Berdasarkan Gambar 2., proses pencarian dilakukan dengan mengunjungi cabang terlebih dahulu hingga tiba di simpul terakhir. Jika tujuan yang diinginkan belum tercapai maka pencarian dilanjutkan ke cabang sebelumnya, turun ke bawah jika memang masih ada cabangnya. Begitu seterusnya hingga diperoleh tujuan akhir (goal).
1.5.Waterfall
Metode pengembangan sistem yang digunakan dalam perancangan sistem ini menggunakan Model Waterfall, dikarenakan metode ini mempunyai tahapan-tahapan yang jelas, nyata dan praktis. Setiap tahapan harus diselesaikan terlebih dahulu untuk menghindari terjadinya pengulangan dalam tahapan sehingga pengembangan sistem yang dilakukan dapat memperoleh hasil yang diinginkan.
1.6.Flowchart
flowchart adalah suatu bagan alir yang digunakan untuk menunjukkan arus pekerjaan atau proses secara menyeluruh dari bagian sistem dimana bagan ini menjelaskan urutan prosedur-prosedur yang ada dalam sistem.
HASIL DAN PEMBAHASAN Hasil rancangan sistem/aplikasi menggunakan flowchart
1. Flowchart Program
Gambar 4. Flowchart Program merupakan diagaram alir Program dengan menu pilihan Pencarian, Kontak, dan Keluar. Pada menu pencarian terdapat pilihan memasukkan kata kunci yang selanjutnya dilakukan pencarian DFS pada tiap sub folder dan pencarian teks pada tiap dokumen yang ditemukan.
2. Flowchart DFS
Pada Gambar 5. Merupakan flowchart dimana proses diawali dengan pemilihan pencarian apakah pencarian cukup di folder akar atau pilihan ke sub foolder. Jika hanya di folder akar maka dilanjutkan langsung dengan pemrosesan file teks dan menampilkan hasilnya. Dan jika memilih pencarian ke sub folder maka dilakukan penelusuran lokasi, yaitu pemeriksaan kepada setiap folder hingga didapatkan folder terakhir. Pada saat posisi di folder terakhir inilah dilakukan pemrosesan file yaitu pencarian kemiripan kata antara kata kunci dan kata pada dokumen, dilanjutkan pencarian kembali pada lokasi berdampingan. Proses pencarian berhenti ketika lokasi folder telah berada pada akar lokasi.
3. Flowchart REGEX
Pada gambar 6 merupakan flowchart dari proses pencarian kata menggunakan Regex. Teks yang terdapat di dalam dokumen dimasukkan ke dalam variabel textInput menggunakan perintah TextInputStream, yaitu syntac dari Xojo yang berfungsi membaca string/teks dari dokumen. Untuk menghindari kesalahan bentuk tulisan maka diperlukan textInput.encoding yaitu fungsi untuk merubah ke format MacRoman. Teks yang ditemukan dirangking berdasar jumlah teks yang ditemukan. Pencarian teks berhenti sampai akhir dokumen dan diakhiri dengan menampilkan hasil. Berdasarkan analisis dan perancangan menghasilkan sistem/aplikasi sebagai berikut :
1. Form Pencarian
Pada form pencarian terdapat satu textfiled untuk memasukkan kata kunci, sebuah tombol pencarian, dan sebuah listbox untuk menampilkan hasil. Kata kunci dimasukkan di textfield, kata kunci yang dimasukkan berupa kata tunggal atau kalimat. Untuk mengoptimalkan pencarian dapat digunakan fungsi Regex. Pencarian akan dilakukan di dalam folder terpilih, jika di dalam folder terpilih terdapat folder lagi maka tidak dilakukan pencarian ke dalam folder tersebut. Hasil pencarian kata berupa dokumen teks akan ditampilkan pada listbox. Dapat kita lihat pada gambar 7, pada listbox terdiri dari kolom file, lokasi, jumlah dan kata. Kolom File yaitu berisi nama file beserta ekstensinya. Sedangkan Lokasi file menunjukkan posisi keberadaan file tersebut di dalam folder. Untuk Jumlah, yaitu hasil rangking kata yang ditemukan di dalam dokumen.
Kesimpulan
Aplikasi pencarian sangat diperlukan terutama instansi pemerintah yang selalu berhubungan dengan arsip dokumen, kecepatan pecarian tergantung jumlah dokumen, besar dukumen, dan spesifikasi komputer, Pencarian menggunakan RegEx sehingga fungsi-fungsi syntax RegEx dapat digunakan untuk pilihan bantuan agar pencarian kata lebih relevan dan aplikasi ini dapat digunakan oleh orang yang awam fungsi RegEx sekalipun.
Daftar Pustaka
Lailiyah, S., Yusnita, A., & Panotogomo, T. A. (2017). Penerapan Algoritma Depth First Search Pada Sistem Pencarian Dokumen. Snitt, 174–179.
Terimakasih sangat membantu
BalasHapus