Ini aplikasi tugas kuliah aku, tapi berhubung ga jadi di kumpulin sama temen2 aku, ya sudah aku posting aja deh :)
Aplikasi ini akan mencari suatu kata (pattern) di dalam sebuah file yang berbasis teks (mis:*.txt,*.xml,*.sql,*.java,dll)
Nah, algoritma yang aku pake disini brute force, tapi dengan sedikit modifikasi (tapi aku kurang tau apakah udah ada algoritma seperti ini atau belum, soalnya blum baca textbook nya :D).
Nah modifikasi yang aku pake disini adalah yang dinamakan tahap preprosessing:
umpamanya:
text: saya makan es kelapa kemaren sore
pattern: makan
Nah, sebelum kita cari, kita lakukan deh tahap preprosessing itu, dengan:
- Hitung banyaknya setiap huruf berbeda yang muncul. (pattern tersebut akan menghasilkan: m=1 ; a=2 ; k=1 ; n=1)
- lalu kita ambil deh huruf yang paling sedikit muncul. Jika ternyata ada lebih dari satu, maka huruf yang diambil adalah huruf yang posisinya yg paling kiri (Disini: m)
- Jadi huruf yang akan kita ambil adalah m
Setelah itu ayo kita memasuki intinya. Yaitu:
- Banding huruf tersebut (baca: m) dengan setiap huruf yang ada pada text, jika ternyata sama baru deh kita bandingkan dengan sisi pattern. Disini akan terjadi "dua kali pembandingan isi pattern".
- Begitu deh sampai habis isi textnya.
Oh iya, Algoritma ini dapat menghandle kasus terburuk dari algoritma brute force yang:
text: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
pattern: aaaaab
Dengan pakai cara ini, jika menemukan kasus seperti ini, tidak perlu dikuartirkan akan kompleksitas algoritmanya deh :)
Aku udah coba bikin formatnya exe tanpa perlu JVM di komputer lokal, but, sayangnya aku belum berhasil juga neh :(
2 komentar:
waw, DAA!!
kl bruteforce itu emang algo bikinan sendiri kan yah..
emm kl untuk kasus
kata : sapi ato pisa
itu gmn ma? kan jumlah tiap hurufny sama.. apa hasilny ntar kluar dua²ny?
hehe.. just cek² :p
Menanggapi komentar nya galih neh ya, Saya akan jawab,
- kalo sapi maka huruf yang akan diambil untuk dibandingkan jadinya s
- sedangkan kalo pisa huruf yang akan diambil jaidnya p
Kan seduai dengan sebelumnya, kalo jumlah huruf yang paling sedikit lebih dari satu, maka huruf yang diambil yaitu yang posisinya paling kiri :)
Posting Komentar