slide presentation final project (s1)
DESCRIPTION
ANALYZING COMPARISON BETWEEN KNUTH-MORRIS-PRATT ALGORITHM WITH BOYER-MOORE ALGORITHM IN WORD SEARCH PUZZLE GAMES.TRANSCRIPT
ANALISIS PERBANDINGAN ALGORITMA KNUTH-MORRIS-PRATT
DENGAN ALGORITMA BOYER-MOORE PADA PERMAINAN WORD SEARCH
PUZZLE
OLEH :ASEP ROJALI (10109411)
LATAR BELAKANG MASALAH
PERMAINAN WORD SEARCH PUZZLE
*
• Sistem dapat menemukan semua kata yang tersembunyi di dalam puzzle yang tersusun secara random
• Penelitian sebelumnya– Algoritma Knuth-Morris-Pratt (word search puzzle)– Perbandingan Algoritma Knuth-Morris-Pratt dan
Algoritma Boyer-Moore
PERUMUSAN MASALAH
Implementasi algoritma Boyer-Moore pada permainan word search puzzle tidak hanya untuk satu arah, disesuaikan
dengan karakteristik pencarian pada permainan word search puzzle
MAKSUD DAN TUJUAN
Algoritma Knuth-Morris-PrattVS
Algoritma Boyer-MoorePermainan word search puzzle
MAKSUD
Algoritma Boyer-Moore lebih baik dari Algoritma Knuth-Morris-Pratt pada permainan word search puzzle
pada panjang bidang papan permainan, panjang kata dan posisi kata
TUJUAN
BATASAN MASALAH
•Algoritma Knuth-Morris-Pratt VS Algoritma Boyer-Moore•Bidang papan permainan memiliki bentuk matriks n x n•Ukuran panjang bidang papan permainan dinamis •Pengujian menggunakan beberapa pola kata dari beberapa panjang kalimat yaitu 3-10 karakter dan menggunakan 8 sampel dengan posisi random•Pengujian kata-kata diambil dari nama-nama hewan dalam Bahasa Indonesia.
METODOLOGI PENELITIAN
*
Metode Penelitian Eksperimental
– Tahap Pengumpulan Data
– Tahap Analisis Algoritma
*
INISIALISASI PAPAN PERMAINAN
*
*
PENCARIAN KATA PADA PAPAN PERMAINAN
PENCARIAN KATA PADA PERMAINAN1. Kiri ke kanan, jika tidak ketemu ubah
cara baca2. Kanan ke kiri, jika tidak ketemu ubah
cara baca3. Atas ke bawah, jika tidak ketemu
ubah cara baca4. Bawah ke atas, jika tidak ketemu
ubah cara baca5. Secara diagonal dari kiri atas ke
kanan bawah, jika tidak ketemu ubah cara baca
6. Secara diagonal dari kanan bawah ke kiri atas, jika tidak ketemu ubah cara baca
7. Secara diagonal dari kanan atas ke kiri bawah, jika tidak ketemu ubah cara baca
8. Secara diagonal dari kiri bawah ke kanan atas, , jika tidak ketemu ubah cara baca
ANALISIS ALGORITMA
*
•Fungsi pinggiran untuk pergeseran•Memiliki kompleksitas O(M+N)•Arah pencocokan dari kiri ke kanan
ALGORITMA KNUTH-MORRIS-PRATT
•Fungsi bad-character shift dan good-suffix shift untuk pergeseran•Memiliki kompleksitas O(N/M)•Arah pencocokan dari kanan ke kiri
ALGORITMA BOYER-MOOR
*
PSEUDECODE ALGORITMADENGAN NOTASI Big-O
*
ALGORITMA KNUTH-MORRIS-PRATT(1)
Hasil dari notasi Big-O hitung nilai pinggiran :O(1) + O(1) + O(1) + O(M) + O(1) + O(1) + O(1) +
O(1) + O(1) = 7 + 1M kali = O(M)
Pseudocode Hitung Pinggiran :
*
ALGORITMA KNUTH-MORRIS-PRATT(2)
Hasil dari notasi Big-O hitung nilai pinggiran :O(M) + O(1) + O(1) + O(1) + O(N) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) +
O(1) + O(1) + O(1) = 10 + 1M kali + 1N kali = O(M+N)
Pseudocode Pencarian Kata :
*
ALGORITMA BOYER-MOORE(1)
Hasil dari notasi Big-O hitung nilai pinggiran :O(M) + O(M) + O(1) + O(1) + O(N) + O(1) +
O(1) + O(1) + O(1) = 6N+1N+2M kali = O(N/M)
Pseudocode Pencarian Kata :
ANALISIS ALGORITMA PADA PERMAINAN
*
*
*
1
2
*
1
2
ANALISIS ALGORITMA TERHADAP KASUS
CONTOH KASUS
YHXBFLAMINGOHZV
SMKOBXTHRABAXZ
JHAEENHNLMMND
JIKBKATDKSBH
ATIBDZTBTEINUSWNQYETU
GPEMZCRTYKKRZBBBG
RAIEKMV
ILBFLT
KAUAHTJYFMAC
MMX
TEXT
1.Tahap Preprocessing (Menghitung nilai pinggiran)
2.Tahap Pencarian Kata
PENCARIAN MENGGUNAKAN ALGORITMA KNUTH-MORRIS-PRATT
FLOWCHART ALGORITMA KNUTH-MORRIS-PRATT
* *
PENCARIAN MENGGUNAKAN ALGORITMA KNUTH-MORRIS-PRATT(1)
F L A M I N G O
0 0 1 0 0 0 0 0
Substring Pattern Prefix dan Suffix
Nilai Pinggiran
PENCARIAN MENGGUNAKAN ALGORITMA KNUTH-MORRIS-PRATT(2)
Tahap Pencarian Kata :
F L A M I N G O
0 0 0 0 0 0 0 0
Teks : Y H X B F L A M I N G O H Z V
Pattern : F L A M I N G O
1)
2)
Tidak terjadi ketidakcocokan, maka pattern digeser sejumlah 1 karakter
Tidak terjadi ketidakcocokan, maka pattern digeser sejumlah 1 karakter
Teks : Y H X B F L A M I N G O H Z V
Pattern : F L A M I N G O
F L A M I N G O
0 0 0 0 0 0 0 0
F L A M I N G O
0 0 0 0 0 0 0 0
Teks : Y H X B F L A M I N G O H Z V
Pattern : F L A M I N G O
3)
Tidak terjadi ketidakcocokan, maka pattern digeser sejumlah 1 karakter
PENCARIAN MENGGUNAKAN ALGORITMA KNUTH-MORRIS-PRATT(3)
Tahap Pencarian Kata :
4)
Tidak terjadi ketidakcocokan, maka pattern digeser sejumlah 1 karakter
Teks : Y H X B F L A M I N G O H Z V
Pattern : F L A M I N G O
F L A M I N G O
0 0 0 0 0 0 0 0
F L A M I N G O
0 0 0 0 0 0 0 0
Teks : Y H X B F L A M I N G O H Z V
Pattern : F L A M I N G O
5)
Tahap pencarian dengan algoritma Knuth-Morris-Pratt selesai setelah melakukan sebanyak 4 iterasi
1.Tahap Preprocessing (Menghitung nilai bad-character shift dan good-suffix shift)
2.Tahap Pencarian Kata
PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE
FLOWCHART ALGORITMA BOYER-MOORE
* *
PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE BAD-CHARACTER SHIFT(1)
Mulai : Index = Panjang (pattern)-2F L A M I N G O
Pindah = 1
Bandingkan “G” dengan “Null HasilBmBc(sebelum) BmBc(sesudah)
Karakter Null Karakter GNilai OH Null Nilai OH 1
1)
Tabel comparator BmBc
Mulai : Index = Panjang (pattern)-3F L A M I N G O
Pindah = 2
Bandingkan “N” dengan “G" HasilBmBc(sebelum) BmBc(sesudah)
Karakter G Karakter N GNilai OH 1 Nilai OH 2 1
2)
Tabel comparator BmBc
* *
PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE BAD-CHARACTER SHIFT(2)
Mulai : Index = Panjang (pattern)-4F L A M I N G O
Pindah = 3
Bandingkan “I” dengan “G“,”N” Hasil
BmBc(sebelum) BmBc(sesudah)Karakter G N Karakter I N GNilai OH 1 2 Nilai OH 3 2 1
3)
Tabel comparator BmBc
Mulai : Index = Panjang (pattern)-5
F L A M I N G O
Pindah = 4
Bandingkan “M” dengan “G“,”N”,”I” Hasil
BmBc(sebelum) BmBc(sesudah)Karakter G N I Karakter M I N GNilai OH 1 2 3 Nilai OH 4 3 2 1
4)
Tabel comparator BmBc
* *
PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE BAD-CHARACTER SHIFT(3)
Mulai : Index = Panjang (pattern)-6F L A M I N G O
Pindah = 5
5)
Tabel comparator BmBc
Mulai : Index = Panjang (pattern)-7F L A M I N G O
Pindah = 6
6)
Tabel comparator BmBc
Bandingkan “A” dengan “G“,”N”,”I”,”M” Hasil
BmBc(sebelum) BmBc(sesudah)Karakter G N I M Karakter A M I N GNilai OH 1 2 3 4 Nilai OH 5 4 3 2 1
Bandingkan “L” dengan “G“,”N”,”I”,”M”,”A” Hasil
BmBc(sebelum) BmBc(sesudah)Karakter G N I M A Karakter L A M I N GNilai OH 1 2 3 4 5 Nilai OH 6 5 4 3 2 1
* *
PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE BAD-CHARACTER SHIFT(4)
Mulai : Index = Panjang (pattern)-1F L A M I N G O
Pindah = 7
7)
Tabel comparator BmBc
Mulai : Index = Panjang (pattern)-1F L A M I N G O
Pindah = 8
8)
Tabel comparator BmBc
Bandingkan “O” dengan “G“,”N”,”I”,”M”,”A”,”L”,”F” Hasil
BmBc(sebelum) BmBc(sesudah)Karakter G N I M A L F Karakter F L A M I N G 0Nilai OH 1 2 3 4 5 6 7 Nilai OH 7 6 5 4 3 2 1 0
Bandingkan “F” dengan “G“,”N”,”I”,”M”,”A”,”L” Hasil
BmBc(sebelum) BmBc(sesudah)Karakter G N I M A L Karakter F L A M I N GNilai OH 1 2 3 4 5 6 Nilai OH 7 6 5 4 3 2 1
* *
PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE GOOD-SUFFIX SHIFT(5)
* *
PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE GOOD-SUFFIX SHIFT(6)
* *
PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE GOOD-SUFFIX SHIFT(7)
Index 0 1 2 3 4 5 6 7
Karakter F L A M I N G O
Nilai MH 8 1
SuffixIndex 7
MovePrefix OSuffix NULL
Suffix comparator
FLAMING 1FLAMIN 2FLAMI 3FLAM 4FLA 5FL 6F 7
NULL 8MH value ?
1) 2) SuffixIndex 6
MovePrefix GSuffix O
Suffix comparator
FLAMING 1FLAMIN 2FLAMI 3FLAM 4FLA 5FL 6F 7
NULL 8MH value ?
Index 0 1 2 3 4 5 6 7
Karakter F L A M I N G O
Nilai MH 8 1
* *
PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE GOOD-SUFFIX SHIFT(8)
Index 0 1 2 3 4 5 6 7
Karakter F L A M I N G O
Nilai MH 8 8 1
SuffixIndex 5
MovePrefix NSuffix GO
Suffix comparator
FLAMING 1FLAMIN 2FLAMI 3FLAM 4FLA 5FL 6F 7
NULL 8MH value ?
3) 4) SuffixIndex 4
MovePrefix ISuffix NGO
Suffix comparator
FLAMING 1FLAMIN 2FLAMI 3FLAM 4FLA 5FL 6F 7
NULL 8MH value ?
Index 0 1 2 3 4 5 6 7
Karakter F L A M I N G O
Nilai MH 8 8 8 1
* *
PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE GOOD-SUFFIX SHIFT(9)
Index 0 1 2 3 4 5 6 7
Karakter F L A M I N G O
Nilai MH 8 8 8 8 1
SuffixIndex 3
MovePrefix MSuffix INGO
Suffix comparator
FLAMING 1FLAMIN 2FLAMI 3FLAM 4FLA 5FL 6F 7
NULL 8MH value ?
5) 6) SuffixIndex 2
MovePrefix ASuffix MINGO
Suffix comparator
FLAMING 1FLAMIN 2FLAMI 3FLAM 4FLA 5FL 6F 7
NULL 8MH value ?
Index 0 1 2 3 4 5 6 7
Karakter F L A M I N G O
Nilai MH 8 8 8 8 8 1
* *
PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE GOOD-SUFFIX SHIFT(10)
Index 0 1 2 3 4 5 6 7
Karakter F L A M I N G O
Nilai MH 8 8 8 8 8 8 1
SuffixIndex 1
MovePrefix LSuffix AMINGO
Suffix comparator
FLAMING 1FLAMIN 2FLAMI 3FLAM 4FLA 5FL 6F 7
NULL 8MH value ?
7) 8) SuffixIndex 0
MovePrefix FSuffix LAMINGO
Suffix comparator
FLAMING 1FLAMIN 2FLAMI 3FLAM 4FLA 5FL 6F 7
NULL 8MH value ?
Index 0 1 2 3 4 5 6 7
Karakter F L A M I N G O
Nilai MH 8 8 8 8 8 8 8 1
* *
PENCARIAN MENGGUNAKAN ALGORITMA BOYER-MOORE (11)
1)
BmGs [7] = BmBc[M] -7 + 7 atau Max (1 = 4 - 7 + 7 ) = 4
2)
BmBc & BmGs Index 0 1 2 3 4 5 6 7Karakter F L A M I N G ONilai OH 7 6 5 4 3 2 1 0Nilai MH 8 8 8 8 8 8 8 1
Teks : Y H X B F L A M I N G O H Z V
Pattern : F L A M I N G O
Teks : Y H X B F L A M I N G O H Z V
Pattern : F L A M I N G O
Tahap pencarian dengan algoritma Boyer-Moore diatas pencarian selesai setelah melakukan sebanyak 1 iterasi.
* *
IMPLEMENTASI SISTEM
*
IMPLEMENTASI ANTAR MUKA PERMAINAN(1)
Papan Permainan
*
IMPLEMENTASI ANTAR MUKA PERMAINAN(2)
Set Papan Permainan
*
IMPLEMENTASI ANTAR MUKA PERMAINAN(3)
Pencarian Menggunakan Algoritma Knuth-Morris-Pratt
*
IMPLEMENTASI ANTAR MUKA PERMAINAN(4)
Pencarian Menggunakan Algoritma Boyer-Moore
*
PENGUJIAN
*
PENGUJIAN PADA PANJANG PAPAN(1)
Kondisi dengan bidang papan 20x20, 30x30,40x40 dan 50x50
Jumlah kata terdapat 8 kata dengan panjang 3-10 karakter dengan posisi random
Pengujian akan dilakukan 4 kali sesuai dengan bidang papan dengan kondisi pola kata random
*
PENGUJIAN PADA PANJANG PAPAN(2)
* *
PENGUJIAN PADA PANJANG PAPAN(3)
* *
PENGUJIAN PADA POSISI POLA 20x20(1)
Kondisi dengan bidang papan 20x20
Jumlah kata terdapat 8 kata dengan panjang 3-10 karakter dengan posisi random
Pengujian akan dilakukan 8 kali sesuai dengan banyak kata dengan kondisi posisi pola terpenuhi semua.
*
PENGUJIAN PADA POSISI POLA 20x20(2)
* *
PENGUJIAN PADA POSISI POLA 20x20(3)
* *
PENGUJIAN PADA POSISI POLA 30x30(1)
Kondisi dengan bidang papan 30x30
Jumlah kata terdapat 8 kata dengan panjang 3-10 karakter dengan posisi random
Pengujian akan dilakukan 8 kali sesuai dengan banyak kata dengan kondisi posisi pola terpenuhi semua.
*
PENGUJIAN PADA POSISI POLA 30x30(2)
* *
PENGUJIAN PADA POSISI POLA 30x30(3)
* *
PENGUJIAN PADA POSISI POLA 40x40(1)
Kondisi dengan bidang papan 40x40
Jumlah kata terdapat 8 kata dengan panjang 3-10 karakter dengan posisi random
Pengujian akan dilakukan 8 kali sesuai dengan banyak kata dengan kondisi posisi pola terpenuhi semua.
*
PENGUJIAN PADA POSISI POLA 40x40(2)
* *
PENGUJIAN PADA POSISI POLA 40x40(3)
* *
PENGUJIAN PADA POSISI POLA 50x50(1)
Kondisi dengan bidang papan 50x50
Jumlah kata terdapat 8 kata dengan panjang 3-10 karakter dengan posisi random
Pengujian akan dilakukan 8 kali sesuai dengan banyak kata dengan kondisi posisi pola terpenuhi semua.
*
PENGUJIAN PADA POSISI POLA 50x50(2)
* *
PENGUJIAN PADA POSISI POLA 50x50(3)
* *
KESIMPULAN
*
Secara umum algoritma Boyer-Moore lebih efisien daripada algoritma Knuth-Morris-Pratt.
Pencarian pada posisi diagonal dapat menambah waktu pencarian pada kedua algoritma Knuth-Morris-Pratt dan algoritma Boyer-Moore
Parameter seperti panjang papan, posisi pola dan panjang kata dapat mempengaruhi efisiensi algoritma pencarian string pada algoritma Knuth-Morris-Pratt
*
SARAN
*
Algoritma Boyer-Moore pada word search puzzle dapat diterapkan pada aplikasi game sesungguhnya
*
DEMO SIMULASI
*
TERIMA KASIH