Penerapan Algoritma Breadth-first Search

Penerapan Algoritma Breadth-first Search Pada FTP Search Engine

Breadth-first Search

1.    Pengertian Breadth First Search

Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpul- simpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1.

Algoritma ini memerluka-n sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpul- simpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungu masuk ke dalam antrian hanya satu kali.

Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali

 

2.    Metode Pencarian

Salah   satu     contoh kakas  pencarian        yang menggunakan metode BFS adalah WebCrawler.

WebCrawler adalah suatu kakas yang membuat indeks isi dari suatu dokumen di Web yang selanjutnya akan dimanfaatkan oleh mesin pencari. Terdapat tiga langkah yang dilakukan oleh WebCrawler ini ketika mengunjungi dokumen, yaitu menandai bahwa suatu dokumen telah dikunjungi, mengenali link yang terdapat pada dokumen tersebut, kemudian isinya didaftarkan pada daftar indeks.

Pada akhirnya, WebCrawler akan menampilkan file yang paling banyak berkaitan dengan kata kunci.

Contoh hasil pencarian dengan WebCrawler

Kata kunci : "molecular biology human genome project"

Hasil pencarian :

1000 Guide to Molecular Biology Databases 0754 Guide to Molecular Biology Databases 0562 Biology Links

0469 bionet newsgroups

0412 Motif BioInformatics Server

0405 LBL Catalog of Research Abstracts (1993) 0329 Molecular Biology Databases

0324 GenomeNet WWW server

0317 DOE White Paper on Bio-Informatics 0292 Molecular biology

0277 Oxford University Molecular Biology Data Centre Home Page

0262 Biology Internet Connections

0244 Harvard Biological Laboratories - Genome Research

0223 About the GenomeNet 0207 Biology Index

 

Algoritma BFS yang diterapkan pada WebCrawler ini adalah mendaftarkan setiap link yang ada dan menyimpannya dalam data base kemudian mengunjunginya satu persatu sambil mencatat link yang berhubungan

 

3.    Metode Pencarian

Algoritma DFS yang diterapkan pada mesin pencari dalam melakukan pengindeksan adalah mengunjungi suatu server kemudian menyimpan semua link yang berhubungan dengan server tersebut baru kemudian mengunjungi server lain.

Salah satu yang menerapkan algoritma DFS pada mesin pencarian adalah FTPSearch. FTPSearch akan menampilkan daftar hasil pencarian berdasarkan server. File-file yang tersimpan pada suatu server akan ditampilkan terlebih dahulu kemudian baru berpindah pada server lain. FTPSearch tidak memperhatikan file mana yang lebih berkaitan dengan kata kunci karena FTPSearch tidak melakukan observasi sampai pada isi dokumen tapi hanya melihat judul dokumen.

 

4.    Hasil Eksperimen

Pada eksperimen yang dilakukan oleh penelitian yang dilakukan oleh Kerstin Klockner, Nadine Wirshum, Anthony Jameson, empat puluh satu subjek diberi waktu sepuluh menit untuk mendapatkan informasi tentang “Assessment centers” dengan cara membuka dokumen yang relevan yang dikembalikan oleh Google sebagai respon pencarian. Sebuah daftar hasil pencarian terdiri dari 25 hasil telah disiapkan sebelumnya dan disajikan dalam sebuah halaman web. Subjek harus menggulung layer untuk dapat melihat keseluruhan halaman. Gerakan mata para subjek dan aksi klik tetikus direkam dengan bantuan pendeteksi ASL

Berdasarkan rekaman video yang dibuat melalui pendeteksi itu, pemrosesan hasil pencarian yang dilakukan para subjek dianalisis. Tiga kategori diidentifikasi : Sebagian besar subjek (65%) mengaplikasikan strategi DFS. Kebalikannya, minoritas subjek mengaplikasikan pola strategi BFS yang ekstrim, melihat ke seluruh daftar hasil pencarian sebelum membuka sebuah dokemen. Pola BFS yang parsial ditunjukkan oleh sisa 20% subjek, yang terkadang melihat ke beberapa entri berikutnya sebelum memilih dokumen yang akan dibuka.

Pada eksperimen dua, dua puluh tujuh subjek diminta untuk melakukan dua aktivitas yang sama dengan eksperimen satu, dengan waktu 5 menit untuk masing-masing aktivitas. Untuk menciptakan situasi yang membuat BFS terlihat relative menarik, kita memperbolehkan subjek untuk membuka maksimal sepuluh dari 25 dokumen yang di daftar, memberi penghargaan kepada mereka untuk setiap penemuan dokumen yang relevan (hamper setengah dari dokumen relevan). Di sini, strategi yang berlawanan ditemukan lagi : 52% subjek tidak menunjukkan niat untuk melihat keseluruhan daftar. Minoritas subjek sebanyak 11% menggunakan strategi BFS yang ekstrim, melihat ke seluruh daftar sebelum membuka sebuah dokumen; sisanya sebanyak 37% mengaplikasikan strategi campuran, melihat dulu ke dua sampai enam dokumen berikutnya dalam daftar.

 

5.    Analisis

Berdasarkan penelitian yang dilakukan oleh Kerstin Klockner, Nadine Wirshum, Anthony Jameson pada makalahnya yang berjudul “Depth- and Breadth-First Processing of Search Result” kita dapat menyimpulkan bahwa pengguna cenderung melakukan pencarian secara strictly depth-first strategy . Yaitu melihat suatu link yang paling atas dari hasil pencarian kemudian mengaksesnya dan terus menelusuri link yang terdapat pada document tersebut yang berkaitan dengan kata kunci yang dicari.

Sehingga agar pencarian oleh FTP search lebih efektif perlu ada penyesuaian dengan algoritma mesin pencari. Algoritma yang menurut kami paling sesuai adalah algoritma BFS pada mesin pencari yang akan menampilkan daftar file yang paling dekat relefansinya dengan kata kunci.

Metode FTP search melakukan hal yang sama dengan WebCrawler yaitu mengunjungi setiap server, mencatat link file dan memasukkannya ke dalam basis data. Sehingga file yang paling relevan ditempatkan di bagian paling atas daftar hasil pencarian. Perbedaan dengan web crawler ftp search akan mengelompokkan file-file tersebut berdasarkan server.

Kelebihan metode baru ini bagi pengguna FTP search adalah pengguna akan dapat langsung melihat file yang paling relevan pada bagian atas daftar hasil pencarian dan meminimalisasi pengaksesan lintas server.

 

6.    Kesimpulan

Berdasarkan analisis yang dilakukan maka algoritma BFS pada mesin pencarian dengan memperhatikan kebiasaan pengguna dalam membuka file daftar hasil pencarian akan mengefektifkan pencarian file di ftp search. Sehingga daftar hasil pencarian FTP search dapat lebih memudahkan pengguna dalam melakukan pencarian.

 

Sumber Referensi :   

[1]     informatika.stei.itb.ac.id › Makalah › MakalahStmik33

[2]     Pinkerton    Brian.1994.”Finding    What    People   Want:   Experiences   with   the   WebCrawler”

[3]     Kl ̈ockner  Kerstin.  2005  “Depth-  and  Breadth-First    Processing    of    Search    Result  Lists:  An  Example  Paper  in  the  SIGCHI Style”

[4]     Salter Richard http://www.cs.oberlin.edu/classes/dragn/labs/graphs/graphs5.html.           Diakses           tanggal 17 Mei 2005 [

[5]     Munir   Rinaldi.   2005.   ”Diktat   Kuliah   Strategi Algoritmik”