BAB II TINJAUAN PUSTAKA
Pada bab ini akan dijelaskan lebih lanjut mengenai hal-hal yang diperlukan untuk pembuatan aplikasi ini. Teori-teori ilmu terkait yang digunakan merupakan penjelasan lebih rinci mengenai tata Bahasa Indonesia, teori Graph, teknik stemming dan stopword removal, algoritma pencarian, dan perangkat yang akan digunakan. Tujuannya
agar
sistem
ini
mempunyai
pijakan
pustaka
yang
dapat
dipertanggungjawabkan.
2.1. Pengertian dan Penulisan Kata Kata adalah rangkaian bunyi terkecil yang memiliki arti dan merupakan unsur kalimat (Badudu & Mohammad Zain, 1994). Suatu bentuk yang memiliki arti atau sering disebut morfem sudah merupakan suatu kata, tetapi sebaiknya konsep tentang kata tidak hanya meliputi morfem bebas melainkan juga semua bentuk gabungan antara morfem bebas dan morfem terikat, atau morfem dasar dengan morfem dasar.
2.1.1. Kata Dasar Kata dasar adalah kata yang merupakan dasar pembentukan kata turunan atau kata berimbuhan (Alwi, 1998). Kata yang berupa kata dasar ditulis sebagai satu kesatuan. Misalnya: a. Saya yakin bahwa engkau mengerti. b. Bus kota penuh sesak. c. Kue ini sangat enak.
5
6
2.1.2. Kata Turunan Kata Turunan adalah perubahan pada kata dasar yang disebabkan karena adanya afiks atau imbuhan baik di awal (prefiks atau awalan), tengah (infiks atau sisipan), maupun akhir (sufiks atau akhiran) kata. a. Imbuhan (awalan, sisipan, akhiran) ditulis serangkaian dengan kata dasarnya. Misalnya: bergeletar, dikelola, penetapan, menengok, mempermainkan. b. Awalan (prefiks) adalah suatu unsur struktural yang dikaitkan di depan sebuah kata dasar. Yang dimaksud di dalam awalan adalah ber-, me-, pe-, di-, ke-, ter-, dan se-. Dalam menambahkan awalan pada kata dasar, ada proses yang terkadang ikut andil di dalamnya, yaitu proses nasalisasi. Proses nasalisasi adalah proses mengubah atau memberi karakter pada kata. Proses nasalisasi inilah yang akan menyebabkan bervariasinya bentuk awalan (alomorf). Bentuk-bentuk alomorf dari imbuhan diatas dapat dilihat pada tabel 2.1. Tabel 2.1: Bentuk-bentuk Alomorf dari Imbuhan No.
Imbuhan
1
be-
2
me-
3
pe-
4
ter-
Alomorf bebelbermememmenmengmengemenypepempenpengpengepenypertetelter-
c. Sisipan (Infiks) adalah semacam morfem terikat yang disisipkan pada sebuah kata antara konsonan pertama dengan vokal pertama. Jenis morfem ini pemakainya
7
terbatas pada beberapa kata saja. Sisipan yang terdapat dalam bahasa Indonesia adalah -el-, -er-, dan -em-. d. Akhiran (Sufiks) adalah semacam morfem terikat yang dilekatkan di belakang suatu morfem dasar. Akhiran yang terdapat dalam bahasa Indonesia adalah -an, kan, dan –i. e. Jika bentuk dasar berupa gabungan kata, awalan, atau akhiran ditulis serangkai dengan kata yang langsung mengikuti atau mendahuluinya. Misalnya: bertepuk tangan, garis bawahi, menganak sungai, sebar luaskan f. Jika bentuk dasar yang berupa gabungan kata, awalan atau akhiran sekaligus, unsur gabungan kata itu ditulis serangkai. Misalnya: menggarisbawahi, menyebarluaskan, dilipatgandakan, penghancurleburan
2.1.3. Kata Ulang Kata ulang adalah kata dasar atau bentuk dasar yang mengalami perulangan baik seluruh maupun sebagian sedangkan kata majemuk adalah gabungan beberapa kata dasar yang berbeda membentuk suatu arti baru. Bentuk ulang ditulis secara lengkap dengan menggunakan tanda hubung. Misalnya: anak-anak, mata-mata, hatihati, kupu-kupu, huru-hara, terus-menerus.
2.2. Pengertian Kalimat Klausa yaitu satuan gramatikal berupa kelompok kata yang mengandung subyek (S) dan predikat (P). Kalimat adalah susunan kata atau kelompok kata (klausa) yang teratur dan mengandung maksud atau pikiran yang jelas. Kalimat adalah satuan bahasa terkecil yang mengungkapkan pikiran yang utuh. Dalam wujud lisan kalimat diucapkan dengan suara naik turun, dengan keras lembut, disela jeda, dan diakhiri dengan intonasi akhir. Dalam wujud tulisan berhuruf latin kalimat dimulai dengan huruf capital dan diakhiri dengan tanda titik (.), tanda tanya (?), dan tanda seru (!).
8
2.2.1. Kalimat Pernyataan (Deklaratif) Kalimat pernyataan dipakai jika penutur ingin menyatakan sesuatu dengan lengkap pada waktu ingin menyampaikan informasi kepada lawan berbahasanya. Biasanya intonasi menurun, tanda baca titik. Misalnya: Positif a. Seorang ayah membelikan putrinya sebuah boneka panda. b. Anak kecil itu memberi sekarung beras kepada sang pengemis. Negatif a. Dalam keramaian, aku tidak mendapat secercah ide untuk menulis puisi. b. Tidak sembarang orang yang dapat memasuki pesta di gedung itu.
2.2.2. Kalimat Pertanyaan (Interogatif) Kalimat pertanyaan dipakai jika penutur ingin memperoleh informasi atau reaksi yang diharapkan. Pertanyaan sering menggunakan kata tanya seperti apakah, dimana, mengapa, kapan, bagaimana. Misalnya: Positif a. Bagaimana proses terbentuknya awan panas gunung Merapi? b. Mengapa daun putri malu menutup ketika disentuh? Negatif a. Mengapa tidak semua anak terlantar di Negara ini dapat dijamin pendidikannya oleh Negara? b. Mengapa sekolah ini dibangun tidak sesuai dengan bahan bangunan yang disepakati?
2.2.3. Kalimat Perintah dan Permintaan (Imperatif) Kalimat perintah dipakai jika penutur ingin “menyuruh” atau “melarang” orang berbuat sesuatu. Misalnya: Positif a. Tolong ambilkan buku tulis di mejaku.
9
b. Sudikah kamu disuruh mengantarkan kue ini ke Bu Halimah! Negatif a. Janganlah kita menjadi orang yang pelit jika sudah tergolong orang mampu. b. Sebaiknya kita tidak membeli daging goreng di pasar.
2.3. Pengertian Paragraf Paragraf adalah bagian wacana yang mengandung satu tema pokok, ditandai dengan permulaan baris yang agak menjorok ke dalam atau spasi yang lebih besar dengan paragraf berikutnya jika digunakan tulisan bentuk lurus (Badudu & Mohammad Zain, 1994). Sebuah paragraf mungkin terdiri atas sebuah kalimat, mungkin terdiri atas dua kalimat, mungkin juga lebih dari dua kalimat. Topik paragraf adalah pikiran utama di dalam sebuah paragraf. Semua pembicaraan dalam paragraf itu terpusat pada pikiran utama ini. Pikiran utama itulah yang menjadi topik persoalan atau pokok pembicaraan. Oleh sebab itu, pikiran utama disebut juga sebagai gagasan pokok di dalam sebuah paragraf. Dengan demikian, apa yang menjadi pokok pembicaraan dalam sebuah paragraf, itulah topik paragraf.
2.3.1. Pembagian Paragraf Menurut Jenisnya Dalam sebuah karangan (komposisi) biasanya terdapat tiga macam paragraf jika dilihat dari segi jenisnya. a. Paragraf Pembuka Paragraf ini merupakan pembuka atau pengantar untuk sampai pada segala pembicaraan yang akan menyusul kemudian. Oleh sebab itu, paragraf pembuka harus dapat menarik minat dan perhatian pembaca kepada masalah yang akan disajikan selanjutnya. Salah satu cara untuk menarik perhatian ini ialah dengan mengutip pernyataan yang memberikan rangsangan dari para orang terkemuka atau orang yang terkenal.
10
b. Paragraf Pengembang Paragraf pengembang ialah paragraph yang terletak antara paragraf pembuka dan paragraf yang terakhir sekali di dalam bab atau anak bab itu. Paragraf ini mengembangkan pokok pembicaraan yang dirancang. Dengan kata lain, paragraf pengembang mengemukakan inti persoalan yang akan dikemukakan. Oleh sebab itu, satu paragraf dan paragraf lain harus memperlihatkan hubungan yang serasi dan logis. Paragraf itu dapat dikembangkan dengan cara ekspositoris, dengan cara deskriptif, dengan cara naratif, atau dengan cara argumentatif. c. Paragraf Penutup Paragraf penutup ialah paragraf yang terdapat pada akhir karangan atau pada akhir suatu kesatuan yang lebih kecil di dalam karangan itu. Biasanya, paragraf penutup berupa simpulan semua pembicaraan yang telah dipaparkan pada bagianbagian sebelumnya.
2.3.2. Struktur Sebuah Paragraf Struktur sebuah paragraf terdiri atas sebuah kalimat topik dan beberapa kalimat penjelas. Dengan kata lain, apabila dalam sebuah paragraf terdapat lebih dari sebuah kalimat topik, paragraf itu tidak termasuk paragraf yang baik. Kalimat-kalimat dalam paragraf itu harus saling mendukung, saling menunjang, kait-berkait satu dengan lainnya. Kalimat topik adalah kalimat yang berisi topik yang dibicarakan pengarang. Pengarang meletakkan inti maksud pembicarannya pada kalimat topik. Karena topik paragraf adalah pikiran utama dalam sebuah paragraf, kalimat topik merupakan kalimat utama dalam paragraf itu. Kalimat utama bersifat umum. Namun apabila paragraf itu diperluas, adakalanya sebuah kalimat yang dianggap umum akan berubah menjadi kalimat khusus.
11
2.3.3. Letak Kalimat Utama Penempatan kalimat utama dalam pengembangan sebuah paragraf bermacammacam. Ada empat cara meletakkan kalimat utama pada paragraf, antara lain: a. Pada awal paragraf Paragraf dimulai dengan mengemukakan persoalan pokok atau kalimat utama. Kemudian diikuti oleh kalimat-kalimat penjelas yang berfungsi menjelaskan kalimat utama. Paragraf ini biasanya disebut paragraf deduktif, yaitu dari yang umum ke khusus. b. Pada akhir paragraf Paragraf ini dimulai dengan mengemukakan penjelasan-penjelasan atau perincian-perincian, kemudian ditutup dengan kalimat utama. Paragraf jenis ini sering disebut paragraf induktif, yaitu dari yang khusus ke umum. c. Pada awal dan akhir paragraf Kalimat utama dapat pula diletakkan pada awal dan akhir paragraf. Fungsi kalimat utama pada akhir paragraf adalah untuk menekankan kembali pikiran utama dengan kalimat yang bervariasi. d. Tanpa kalimat utama Paragraf ini tidak mempunyai kalimat utama. Berarti pikiran utama tersebar di seluruh kalimat yang ada dalam paragraf tersebut. Bentuk ini biasanya digunakan dalam karangan yang berbentuk narasi atau deskripsi. Pikiran utama didukung oleh semua kalimat.
2.4. Ringkasan Ringkasan diartikan sebagai penyajian singkat dari suatu karangan asli tetapi tetap mempertahankan urutan isi dan sudut pandang pengarang asli. Sedangkan perbandingan bagian atau bab dari karangan asli secara proposional tetap dipertahankan dalam bentuknya yang singkat itu (Keraf 1984: 262). Dengan kata lain, ringkasan adalah suatu cara yang efektif untuk menyajikan suatu karangan yang panjang dalam bentuk singkat.
12
Ringkasan
merupakan
penyajian
singkat
tentang
isi
tulisan
dengan
memperlihatkan urutan dari isi atau bab-bab yang terdapat dalam tulisan. Dalam bentuknya yang singkat itu, urutan tentang isi atau bab-bab tulisan disajikan secara proporsional. Pada prinsipnya di dalam ringkasan, gagasan dan pendekatan penulis telah tampak dan problematika berikut upaya pemecahan yang ada dalam tulisan disajikan berurutan sesuai bab-bab yang ada. Adakalanya ilustrasi juga disertakan dalam ringkasan. Bagi orang yang sudah terbiasa membuat ringkasan, mungkin kaidah yang berlaku dalam menyusun ringkasan telah tertanam dalam benaknya. Meski demikian, tentulah perlu diberikan beberapa patokan sebagai pegangan dalam membuat ringkasan terutama bagi mereka yang baru mulai atau belum pernah membuat ringkasan. Berikut ini beberapa pegangan yang dipergunakan untuk membuat ringkasan yang baik dan teratur. a. Membaca Naskah Asli Bacalah naskah asli sekali atau dua kali, kalau perlu berulang kali agar dapat mengetahui kesan umum tentang karangan tersebut secara menyeluruh. Penulis ringkasan juga perlu mengetahui maksud dan sudut pandang penulis naskah asli. b. Mencatat Gagasan Utama Jika sudah menangkap maksud, kesan umum, dan sudut pandang pengarang asli, silakan memperdalam semua hal itu. Bacalah kembali karangan itu bagian demi bagian, alinea demi alinea sambil mencatat semua gagasan yang penting dalam bagian atau alinea itu. Pokok-pokok yang telah dicatat dipakai untuk menyusun sebuah ringkasan. c. Mengadakan Reproduksi Pakailah kesan umum dan hasil pencatatan untuk membuat ringkasan. Urutan isi disesuaikan dengan naskah asli, tapi kalimat-kalimat dalam ringkasan yang dibuat adalah kalimat-kalimat baru yang sekaligus menggambarkan kembali isi dari karangan aslinya.
13
d. Ketentuan Tambahan Setelah melakukan langkah ketiga, terdapat beberapa hal yang perlu diperhatikan agar ringkasan itu diterima sebagai suatu tulisan yang baik. 1. Susunlah ringkasan dalam kalimat tunggal daripada kalimat majemuk. 2. Ringkaskanlah kalimat menjadi frasa, frasa menjadi kata. Jika rangkaian gagasan panjang, gantilah dengan suatu gagasan sentral saja. 3. Besarnya ringkasan tergantung jumlah alinea dan topik utama yang akan dimasukkan dalam ringkasan. Ilustrasi, contoh, deskripsi, dapat dihilangkan, kecuali yang dianggap penting. 4. Pertahankan susunan gagasan dan urutan naskah. Tapi yang sudah dicatat dari karangan asli itulah yang harus dirumuskan kembali dalam kalimat ringkasan. Jagalah juga agar tidak ada hal yang baru yang dimasukkan dalam ringkasan. 5. Dalam
sebuah
meringkaskan
ringkasan suatu
buku
ditentukan yang
pula
tebalnya
panjangnya. 250
Jika
halaman
harus menjadi
sepersepuluhnya, perhitungan yang harus dilakukan adalah sebagai berikut: i.
Panjang karangan asli (berupa kata) adalah: Jumlah halaman x Jumlah baris per halaman x Jumlah kata per baris = 250 x 35 x 9 kata = 78.750 kata.
ii.
Panjang ringkasan berupa jumlah kata adalah: 78.750 : 10 = 7.875 kata. Panjang ringkasan berupa jumlah halaman ketikan adalah: jika kertas yang dipergunakan berukuran kuarto, jarak antar baris dua spasi, tiap baris rata-rata sembilan kata, pada halaman kertas kuarto dapat diketik 25 baris dengan jarak dua spasi, maka: Jumlah kata per halaman adalah: 25 x 9 kata = 225. Jumlah halaman yang diperlukan adalah: 7.875 : 225 = 35 halaman.
2.5. Teori Graph Tahun 1736 seorang matematikawan Swiss, Leonhard Euler, mengungkap misteri Jembatan Konigsburg. Di kota tersebut terdapat sungai Pregel yang mengalir mengitari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai, tujuh buah jembatan yang
14
menghubungkan daratan yang dibelah oleh sungai tersebut. Misteri pada jembatan Konigsberg adalah : Apakah mungkin melalui ketujuh buah jembatan itu masing-masing tepat satu kali dan kembali ke tempat semula? Leonhard Euler berhasil memecahkan dan mempresentasikan masalah ini dalam bentuk graph. Daratan direpresentasikan dalam bentuk titik (vertex) dan jembatan direpresentasikan dalam bentuk garis (edge). Sebuah graph didefinisikan sebagai pasangan himpunan (V,E), dimana V adalah himpunan dari titik-titik (vertex) dan E adalah himpunan garis (edge) yang menghubungkan antara satu titik dengan titik lainnya. Terdapat beberapa macam bentuk dari graph, yaitu: a. Simple graph, adalah graph yang tidak memiliki edge ganda (dalam satu pasangan vertex) b. Null graph, adalah sebuah graph yang tidak memiliki edge c. Digraph atau Directed Graph, adalah sebuah graph dimana pada tiap edge-nya diberi arah.
2.6. Algoritma Pencarian (Searching Algorithm) Algoritma ini merupakan teknik dasar dari searching dimana dicari semua solusi yang memungkinkan. Kemudian semua solusi yang memungkinkan yang telah ditemukan tadi dibandingkan untuk mendapatkan solusi yang terbaik. Metode pencarian dikatakan penting untuk menyelesaikan permasalahan karena setiap state(keadaan) menggambarkan langkah-langkah untuk menyelesaikan permasalahan. Metode pencarian dikatakan penting untuk perencanaan karena dalam sebuah permainan akan menentukan apa yang harus dilakukan, dimana setiap state menggambarkan kemungkinan posisi pada suatu saat. Metode pencarian adalah bagian dari kesimpulan, dimana setiap state menggambarkan hipotesis dalam sebuah rangkaian deduktif. Dalam bab ini akan dipelajari metode pencarian sederhana yang hanya berusaha mencari kemungkinan penyelesaian. Metode yang termasuk pada bagian ini adalah Breadth-First Search, Depth-First Search, Hill Climbing, dan Best-First Search.
15
2.6.1. Pencarian Melebar Pertama (Breadth-First Search) Pada metode Breadth-First Search, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akan terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya demikian pula dari kiri ke kanan sampai ditemukannya solusi. Lihat gambar 2.1.
Gambar 2.1. Tree untuk Breadth-First Search Algoritma 1.
Buat sebuah antrian, inisialisasi node pertama dengan Root dari tree.
2.
Bila node pertama, jika ≠ GOAL, diganti dengan anak-anaknya dan diletakkan di belakang PER LEVEL.
3. Bila node pertama = GOAL, selesai. Lihat gambar 2.2.
Gambar 2.2. Algoritma Breadth-First Search Lintasan yang didapat : S – B – C – E – Z Keuntungan: 1. Tidak akan menemui jalan buntu.
16
2. Jika ada satu solusi, maka breadth-first search akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan. Kelemahan: 1. Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon. 2. Kemungkinan ditemukan optimal lokal, yaitu suatu keadaan yang lebih baik daripada semua tetangganya namun masih belum baik dari suatu keadaan lain yang jauh letaknya darinya.
2.6.2. Pencarian Mendalam Pertama (Depth-First Search) Pada Depth-First Search, proses pencarian akan dilaksanakan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini dilakukan terus hingga ditemukannya solusi.
Gambar 2.3. Tree untuk Depth-First Search Algoritma 1. Buat sebuah antrian, inisialisasi node pertama dengan Root dari tree 2. Bila node pertama, jika ≠ GOAL, node dihapus diganti dengan anak-anaknya dengan urutan LChild 3. Bila node pertama = GOAL, selesai.
17
Gambar 2.4. Algoritma Depth-First Search
Lintasan yang didapat: S – A – B – C – E – Z Keuntungan: 1. Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan. 2. Menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan. Kelemahan: 1. Kemungkinan terjebak dalam optimal lokal. 2. Hanya akan menemukan 1 solusi pada setiap pencarian.
2.6.3. Pencarian dengan Mendaki Bukit (Hill Climbing) Hill Climbing merupakan salah satu metode pencarian untuk mencari kemungkinan penyelesaian. Teknik Hill Climbing dapat digunakan untuk memecahkan persoalan yang memiliki banyak alternatif solusi untuk kemudian memilih solusi yang terbaik.
18
Gambar 2.5. Tree untuk Hill Climbing Cara kerjanya dimulai dengan memilih solusi acak, kemudian dilakukan perubahan sedikit demi sedikit, setiap perubahan menghasilkan solusi yang lebih baik. Saat perubahan yang dilakukan tidak lagi mendapatkan solusi yang lebih baik, algoritma Hill Climbing akan berhenti mencari dan menentukan solusi terakhir sebagai solusi yang optimal. Algoritma 1. Buat solusi usulan pertama, lalu periksa apakah solusi usulan tersebut merupakan sebuah solusi. Jika ya, berhentilah. Jika tidak, lanjutkan ke langkah berikutnya. 2. Dari solusi ini, terapkan sejumlah aturan yang dapat diterapkan untuk membuat sekumpulan solusi usulan yang baru. 3. Kirimkan elemen usulan ini ke fungsi uji. Jika elemen ini merupakan sebuah solusi, berhentilah. Jika tidak, periksa apakah elemen ini merupakan yang terdekat dengan solusi yang telah diuji 4. Ambil elemen terbaik yang ditemukan lalu gunakan sebagai solusi usulan berikutnya. 5. Kembali ke langkah awal.
19
Gambar 2.6. Algoritma Hill Climbing
Sebagai contoh penerapan prosedur Hill Climbing dapat dilihat pada uraian berikut ini. Pertama adalah menentukan usulan solusi pertama yang akan diambil dari nilai bobot-bobot kalimat pada tabel 2.2. Tabel 2.2 Bobot kalimat sebagai usulan solusi Kalimat
Bobot
Memutuskan untuk menyekolahkan anak pada usia yang masih sangat dini saat ini telah menjadi trend di
31
kalangan masyarakat. Dengan alasan ingin sedari dini memberikan berbagai ilmu dan kepandaian kepada sang anak, orang tua rela
47
merogoh kocek dalam-dalam untuk biaya sekolah yang tidak bisa dibilang murah. Bahkan tidak jarang ada bayi usia dibawah satu tahun yang disekolahkan dengan standar internasional
33
Bila dilihat dari sudut pandang psikologis anak, memasukkan mereka ke dalam sekolah pada usia yang
51
sangat dini dipandang belum begitu perlu.
Dari hasil pembobotan diperoleh usulan solusi pertama yaitu (31,47,33,51) dengan nilai jarak = 48. Solusi (goal) yang dtuju adalah urutan bobot dari besar ke kecil (51,47,33,31). Kombinasi yang dapat dihasilkan dari 4 nilai bobot adalah: 4! / 2!(4-
20
2)! = 6 kombinasi. Keenam kombinasi ini akan kita pakai semuanya sebagai operator, yaitu: * Tukar 1, 2 (menukar urutan posisi bobot ke-1 dengan bobot ke-2). * Tukar 1, 3 (menukar urutan posisi bobot ke-1 dengan bobot ke-3). * Tukar 1, 4 (menukar urutan posisi bobot ke-1 dengan bobot ke-4). * Tukar 2, 3 (menukar urutan posisi bobot ke-2 dengan bobot ke-3). * Tukar 2, 4 (menukar urutan posisi bobot ke-2 dengan bobot ke-4). * Tukar 3, 4 (menukar urutan posisi bobot ke-3 dengan bobot ke-4).
Gambar 2.7 Contoh Prosedur Hill Climbing Dari 6 kombinasi kemungkinan solusi, terdapat 2 kombinasi dengan nilai terkecil yang sama yaitu 20, namun yang paling mendekati dengan solusi tujuan (goal) adalah yang menggunakan operator ‘tukar 1,4’. Karena prosedur telah menemukan solusi terbaik, maka proses pencarian berhenti. Secara umum penerapan algoritma Hill Climbing memiliki keuntungan:
21
1. Membutuhkan memori yang lebih relatif kecil, karena hanya node-node pada lintasan aktif saja yang disimpan. 2. Metode Hill Climbing Search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan. Kelemahan: 1. Algoritma akan berhenti kalau mencapai nilai optimum lokal. 2. Perlu menentukan aturan yang tepat.
2.6.4. Pencarian terbaik pertama (Best-First Search) Best-First Search merupakan suatu cara yang menggabungkan kelebihan dari pencarian Breadth-First Search dan Depth-First Search. Pada setiap langkah proses Best-First Search, kita memilih node-node dengan menerapkan fungsi heuristik yang memadai pada setiap node/simpul yang kita pilih dengan menggunakan aturan-aturan tertentu untuk menghasilkan penggantinya.
Gambar 2.7. Tree untuk Best-First Search Algoritma 1. Buat sebuah antrian, inisialisasi node pertama dengan Root dari tree 2. Bila node pertama, jika ≠ GOAL, node dihapus & diganti dengan anakanaknya 3. Bila node pertama = GOAL, selesai.
22
Gambar 2.8. Algoritma Best-First Search
Lintasan yang didapat: S – A – B – C – E – Z Keuntungan 1. Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan 2. Secara kebetulan, metode ini akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keaadaan Kelemahan 1. Algoritma akan berhenti kalau mencapai nilai optimum lokal 2. Tidak diijinkan untuk melihat satupun langkah sebelumnya.
2.7. Proses Pemisahan Kata dan Stemmer Proses pemisahan kata adalah proses penguraian artikel yang semula berupa kumpulan kalimat menjadi kata-kata saja baik itu berupa kata-kata penting maupun kata-kata tidak penting. Tahapan dalam proses ini adalah sebagai berikut: a. Isi artikel akan diuraikan menjadi kata-kata saja baik kata penting maupun kata tidak penting. b. Proses penguraian akan dilakukan sampai isi dari keseluruhan artikel selesai diproses.
23
Proses stemmer adalah proses perubahan bentuk suatu kata menjadi bentuk kata dasarnya. Proses tersebut akan membuang imbuhan yang terkandung dalam suatu kata yang diproses. Proses ini akan mendukung tingkat ketelitian dalam perhitungan daftar keyword pada proses berikutnya. Tahapan dalam proses stemmer antara lain sebagai berikut: a. Daftar kata yang telah dihasilkan dalam proses pemisahan kata akan diproses. b. Setiap kata akan diperiksa keberadaannya di dalam daftar kata dasar. c. Bila kata tersebut terdapat dalam daftar kata dasar maka kata tersebut tidak mengalami perubahan bentuk.
2.8. Proses Stopword Removal Setiap bahasa yang resmi memiliki berbagai kata fungsi dan kata sambung yang hampir selalu muncul dalam penerapannya. Biasanya kata-kata ini tidak memiliki arti yang lebih dalam memenuhi kebutuhan seseorang dalam mencari informasi. Dalam bahasa Inggris, kata-kata tersebut (misalnya a, an, the, on) disebut sebagai stopwords (Chakrabarti, 2003, p 48). Sedangkan dalam bahasa Indonesia stopwords dapat disebut sebagai kata tidak penting misalnya, “di”, “oleh”, “pada”, “sebuah”, “karena”. Sebelum proses stopword removal dilakukan, terlebih dahulu dibuat daftar stopword list (stoplist). Preposisi, kata hubung dan partikel biasanya merupakan kandidat stoplist. Stopword removal adalah proses penghilangan kata tidak penting melalui pengecekan kata-kata hasil stemmer pada abstrak, apakah termasuk dalam daftar kata tidak penting (stoplist) atau tidak. Jika termasuk di dalam stoplist maka kata-kata tersebut akan dihilangkan dari abstrak sehingga kata-kata yang tersisa dianggap sebagai kata penting atau keywords. Tahapan dalam proses stopword removal antara lain sebagai berikut: a. Daftar kata yang dihasilkan pada proses divide to word dan stemmer akan diproses. b. Setiap kata yang dihasilkan akan dibandingkan dengan daftar stoplist.
24
c. Bila kata tersebut ditemukan, maka kata tersebut diasumsikan bukan keyword dari artikel Bila kata tersebut tidak ditemukan dalam daftar stoplist maka kata tersebut diasumsikan sebagai keyword dari artikel yang bersangkutan. Kemudian jumlah dari kata tersebut akan dihitung keberadaannya dalam paragraf yang bersangkutan.
2.9. TF-TDF (Terms Frequency – Inverse Document Frequency) Metode ini merupakan metode untuk menghitung nilai/bobot suatu kalimat terhadap artikel. Metode ini akan mengabaikan kata-kata yang tergolong tidak penting. Oleh sebab itu sebelum menjalankan metode ini, sistem harus melakukan proses stemmer dan stopword removal terlebih dahulu. Metode ini memiliki empat proses yang berbeda untuk perhitungan nilai suatu kalimat (Sjobergh Jonas & Araki Kenji, 2005), antara lain: a. Kecocokan kata-kata dalam kalimat dengan daftar kata kunci/keyword. Idenya adalah semakin suatu kalimat memiliki nilai yang tinggi, maka kalimat tersebut semakin penting keberadaannya di dalam suatu artikel. b. Menghitung frekuensi kata-kata suatu kalimat terhadap keseluruhan artikel dan hasilnya akan dibagi dengan jumlah kata dalam suatu artikel. Alasannya adalah semakin tinggi frekuensi kata tersebut di dalam suatu artikel, maka kalimat yang memiliki kata tersebut semakin penting keberadaannya di dalam suatu artikel. c. Melihat posisi kalimat di dalam suatu artikel. Dalam program ini digunakan konsep metode deduktif induktif seusai kaidah bahasa Indonesia. Kalimat pertama dan terakhir dari setiap paragraf akan diberi nilai 2 sedangkan kalimat yang lain akan diberi nilai 1. d. Bagian ini sangat berhubungan dengan hasil pemetaan artikel karena akan dihitung jumlah relasi (yang disimbolkan dengan edge) suatu kalimat di dalam artikel. Idenya adalah semakin suatu kalimat memiliki relasi yang banyak dengan kalimat lainnya maka kalimat tersebut kemungkinan mendiskusikan topik utama suatu artikel sehingga kalimat tersebut semakin penting keberadannya di dalam artikel tersebut.
25
Kemudian hasil dari empat perhitungan diatas akan dikalikan dan menjadi nilai dari tf, seperti terlihat pada persamaan berikut :
tf = bobot 1 * bobot 2 * bobot 3 * bobot 4
Nilai dari tf akan dikalikan dengan nilai idf seperti pada persamaan dibawah ini (Intan Rolly & Defeng Andrew, 2005):
w = tf x idf w = tf x log N/n
Keterangan : w = bobot kalimat terhadap dokumen tf = jumlah kemunculan kata dalam dokumen N = jumlah semua dokumen yang ada dalam database n = jumlah dokumen yang mengandung kata Berdasarkan rumus diatas, berapapun nilai tf, apabila N = n maka akan didapatkan hasil 0 (nol) untuk perhitungan idf. Untuk itu dapat ditambahkan nilai 1 (satu) pada sisi idf sehingga perhitungan bobotnya menjadi sebagai berikut:
w = tf x (log(N/n)+1) Untuk perhitungan bobot edge akan digunakan persamaan berikut (Sjobergh Jonas & Araki Kenji, 2005):
Cost[i,j] =
(i - j)² Overlap[i,j]*weight[j]
Nilai overlap[i,j] diperoleh dengan menghitung jumlah kata yang sama antara kalimat ke-i dan kalimat ke-j dengan mengabaikan stopword yang ada di dalam
26
kalimat-kalimat tersebut. Kemudian hasil dari kalimat diatas akan digunakan untuk menentukan nilai relasi dari setiap kalimat berdasarkan hasil pemetaan dari artikel.
2.10. Model Pengembangan Perangkat Lunak Pengembangan perangkat lunak ini menggunakan pendekatan model proses Prototype. Tahapan yang dilakukan adalah sebagai berikut: 1. Pengumpulan kebutuhan Mendefinisikan format seluruh perangkat lunak, mengidentifikasikan semua kebutuhan, dan garis besar sistem yang akan dibuat. 2. Membangun prototyping Membuat perancangan sementara yang berfokus pada penyajian kepada pengguna (misalnya dengan membuat input dan format output) 3. Evaluasi prototyping Evaluasi ini dilakukan oleh pengguna apakah prototyping yang sudah dibangun telah sesuai dengan yang diharapkan. Jika sudah maka langkah 4 akan diambil. Jika tidak prototyping akan direvisi dengan mengulang langkah 1, 2, dan 3. 4. Mengkodekan sistem Dalam tahap ini prototyping yang sudah disepakati diterjemahkan ke dalam bahasa pemrograman. 5. Menguji sistem Setelah sistem menjadi suatu perangkat lunak yang siap pakai, harus dites dulu sebelum digunakan. Pengujian ini dilakukan dengan White Box, Black Box, Basis Path, dan lain-lain. 6. Evaluasi sistem Pengguna mengevaluasi apakah sistem yang sudah jadi sesuai dengan yang diharapkan. Jika ya, langkah 7 dilakukan. Jika tidak, ulangi langkah 4 dan 5. 7. Menggunakan sistem Perangkat lunak yang telah diuji dan diterima pengguna siap untuk digunakan.
27
2.11. PHP Pada awalnya PHP merupakan kependekan dari Personal Home Page (Situs Personal). Pada tahun 1997, sebuah perusahaan bernama Zend menulis ulang interpreter PHP menjadi lebih bersih, lebih baik, dan lebih cepat. Kemudian pada Juni 1998, perusahaan tersebut merilis interpreter baru untuk PHP dan meresmikan rilis tersebut sebagai PHP 3.0 dan singkatan PHP dirubah menjadi akronim berulang PHP: Hypertext Preprocessing. Bahasa pemrograman PHP adalah sebuah bahasa script yang tidak melakukan sebuah kompilasi dalam penggunaanya. Fungsi PHP secara umum adalah untuk membuat sebuah web yang interaktif dan dinamis. Untuk dapat menjalankan PHP pada sebuah web server, diperlukan sebuah web server. PHP 4 bukan merupakan versi terakhir yang sudah dikeluarkan oleh PHP, tapi versi ini masih banyak digunakan oleh para programmer website. PHP 5 merupakan kelanjutan dari evolusi yang berjalan pada PHP. PHP 5 menawarkan peningkatan dari fungsionalitas dan penambahan beberapa fitur, antara lain: a. Peningkatan dari kemampuan pemrograman berorientasi obyek. b. Exception handling, yang menstandarisasi logika atas pemberitahuan kesalahan pemrograman. c. Peningkatan terhadap penanganan string. d. Peningkatan dukungan terhadap XML dan Web Service, yang menggunakan libxml2. e. Dukungan terhadap SQLite database server. Berikut adalah beberapa kelebihan PHP dibandingkan dengan bahasa pemrograman web lainnya : 1. Praktis dalam penulisan buat para penggunanya. 2. Cepat dan Powerful. 3. Harga yang murah.
28
4. Cross Platform atau dapat dipakai di hampir semua web server dengan konfigurasi yang relatif mudah untuk dijalankan pada berbagai sistem operasi, seperti Linux, Unix, Windows, dan Mac. 5. Selalu up to date mengikuti perkembangan teknologi internet. Salah satu kelemahan PHP dibandingkan dengan bahasa pemrograman web lainnya adalah PHP memiliki kelemahan pengamanan (security) tertentu apabila programmer tidak jeli dalam melakukan pemrograman dan kurang memperhatikan isu dan konfigurasi PHP.
