Cari Blog Ini

Senin, Juni 25, 2007

Simple Search Word Aplikasi

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:

gaLz mengatakan...

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

vanma mengatakan...

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 :)

Translate

Formulir Kontak

Nama

Email *

Pesan *