Path: Top > S1-Final_Project > Fakultas_Teknik_dan_Ilmu_Komputer > Teknik_Informatika > 2014

Analisis Perbandingan Algoritma Knuth-Morris-Pratt Dengan Algoritma Boyer-Moore Pada Permainan Word Search Puzzle

2014
Undergraduate Theses from JBPTUNIKOMPP / 2014-12-02 15:25:29
By : Asep Rojali NIM.10109411, Perpustakaan UNIKOM (aseprojali@gmail.com)
Created : 2014-12-02, with 12 files

Keyword : Algoritma, Knuth-Morris-Pratt, Boyer-Moore, Word Search Puzzle, String Matching
Url : http://alumni.unikom.ac.id

Permainan word search puzzle adalah permainan berbasis puzzle yang mencari kata-kata yang disusun dalam bentuk array dua dimensi atau yang lebih dikenal dengan matriks. Kata-kata tersebut dapat disusun secara horizontal, vertikal maupun diagonal dan dapat ditulis pada posisi terbalik. Penyelesaian dari permainan word search puzzle ini adalah menemukan semua kata yang tersembunyi di papan permainan yang berbentuk matriks. Permasalahan yang dihadapi adalah bagaimana sistem dapat menemukan semua kata yang tersembunyi di dalam puzzle yang telah tersusun secara random baik secara horizontal, vertikal, maupun diagonal atau sebaliknya. Hasil dari penelitian ini bahwa algoritma Boyer-Moore lebih efisien pada pencarian dengan arah kiri ke kanan, kanan ke kiri , atas ke bawah dan bawah ke atas atau vertikal dan horizontal. Hal ini dikarenakan teks yang diekstrak untuk pencocokan pola dengan arah pencarian vertikal dan horizontal jumlahnya sama panjang, sedangkan algoritma Knuth-Morris-Pratt lebih efisien pada tahap pencarian diagonal dengan arah dari diagonal kiri atas ke kanan bawah, diagonal kanan bawah ke kiri atas, diagonal kanan atas ke kiri bawah dan diagonal kiri bawah ke kanan atas. Hal ini dikarenakan teks yang diekstrak untuk pencocokan pola dengan arah diagonal jumlahnya tidak sama panjang.

Description Alternative :

Word search puzzle games is a game puzzle-based which searching for the words listed in a form of two dimension array or more known as matrix. The words can be compiled horizontally, vertically, or even diagonally also can be written upside down. The completion of the game word search puzzle is finding all the words hidden on the game board in the shape of a matrix. The problem is how the system find all the hiding words in the puzzle which has random compiled whether it is horizontally, vertically, diagonally or otherwise. The result from this research that Boyer-Moore algorithm is more efficient on the search with the direction left to right, right to left, top to bottom and bottom to top or vertical and horizontal. It was because the text extracted for matching pattern to the vertical and horizontal direction search has the same length, where as Knuth-Morris-Pratt algorithm is more efficent in the diagonal search which is diagonally upper left to the lower right, diagonally lower right to the upper left, diagonally upper right to the lower left, and diagonally lower left to the upper right. It was because the text extracted for matching pattern diagonal direction search has not the same length.

Give Comment ?#(0) | Bookmark

PropertyValue
Publisher IDJBPTUNIKOMPP
OrganizationP
Contact Namedyah@unikom.ac.id
AddressJl. Dipati Ukur No.116 Lt.7
CityBandung
RegionWest Java
CountryIndonesia
Phone022-2533825 ext.112
Fax022-2533754
Administrator E-mailperpus@unikom.ac.id
CKO E-mailperpus@unikom.ac.id