analisis dan perbandingan algoritma colussi dan algoritma

ANALISIS DAN PERBANDINGAN ALGORITMA COLUSSI

DAN ALGORITMA SIMON DALAM PENCARIAN

KATA PADA JURNAL

SKRIPSI

IQBAL HABIBIE

141421083

PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER

DEPARTEMEN ILMU KOMPUTER

FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI

UNIVERSITAS SUMATERA UTARA

MEDAN

2016

Universitas Sumatera Utara

ANALISIS DAN PERBANDINGAN ALGORITMA COLUSSI

DAN ALGORITMA SIMON DALAM PENCARIAN

KATA PADA JURNAL

SKRIPSI

Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah

Sarjana Ilmu Komputer

IQBAL HABIBIE

141421083

PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER

DEPARTEMEN ILMU KOMPUTER

FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI


MEDAN

2016


PERSETUJUAN

Judul : ANALISIS DAN PERBANDINGAN ALGORITMA

COLUSSI DAN ALGORITMA SIMON DALAM

PENCARIAN KATA PADA JURNAL

Kategori : SKRIPSI

Nama : IQBAL HABIBIE

Nomor Induk Mahasiswa : 141421083

Program Studi : EKSTENSI (S1) ILMU KOMPUTER

Fakultas : FAKULTAS ILMU KOMPUTER DAN

TEKNOLOGI INFORMASI


Komisi Pembimbing :

Pembimbing 2 Pembimbing 1

Amer Sharif, S.Si., M.Kom Drs. Agus Salim Harahap, M.Si

NIP. NIP. 195408281981011004

Disetujui oleh

Departemen Ilmu Komputer

Ketua,

Dr. Poltak Sihombing, M.Kom

196203171991031001


PERNYATAAN

ANALISIS DAN PERBANDINGAN ALGORITMA COLUSSI DAN ALGORITMA

SIMON DALAM PENCARIAN KATA PADA JURNAL

SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa

kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.

Medan, Juli 2016

IQBAL HABIBIE

141421083


PENGHARGAAN

Alhamdulilah untuk segalanya yang diberikan oleh Allah SWT kepada penulis pada

setiap kesempatan, waktu, kesehatan, kebahagiaan, ujian hidup selama ini sehingga

penulis dapat menyusun dan menyelesaikan skripsi ini dengan baik sebagai salah satu

syarat untuk memperoleh gelar Sarjana Ilmu Komputer di Fakultas Ilmu Komputer

dan Teknologi Informasi Universitas Sumatera Utara.

Terimakasih untuk semua pihak yang membantu penulis dalam pengerjaan

skripsi ini, yang telah memberikan penulis dukungan, semangat, waktu untuk

membantu. Penulis ingin mengucapkan terimakasih sebesar-besarnya kepada:

1. Bapak Prof. Dr. Runtung Sitepu, M.H. sebagai Rektor Univesitas Sumatera Utara

2. Bapak Prof. Dr. Opim Salim Sitompul, M.Sc sebagai Dekan Fakultas Ilmu

Komputer dan TI Universitas Sumatera Utara.

3. Bapak Dr. Poltak Sihombing, M.Kom sebagai Ketua Program Studi S1 Ilmu

Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas

Sumatera Utara sekaligus sebagai Dosen Pembanding 1 yang memberikan saran

kepada penulis agar menyusun skripsi dengan sebaik-baiknya.

4. Ibu Maya Silvi Lydia, B.Sc., M.Sc Sebagai Sekretaris Program Studi S1 Ilmu

Komputer Universitas Sumatera Utara.

5. Bapak Drs. Agus Salim Harahap, M.Si sebagai Dosen Pembimbing 1 yang

banyak membantu penulis untu mempercepat penyusunan skripsi.

6. Bapak Amer Sharif, S.Si., M.Kom sebagai Dosen Pembimbing 2 yang telah

banyak memberikan masukan kepada penulis untuk memperkaya isi dan

mengemban penulis untuk mengerjakan skripsi yang dapat dianggap layak

sebagai penelitian.


7. Ibu Dian Rachmawati, S.Si., M.Kom sebagai Dosen Pembanding 2 yang telah

banyak membantu penulis untuk diskusi pada awal penelitian sampai

penyelesaian penelitian.

8. Dosen dan pegawai di S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi

Informasi Universitas Sumatera Utara.

9. Untuk keluarga terutama Mama, Abang, Kak Tuti, Mbak Femmy, Jihan yang

paling penulis sayangi.

10. Teman-teman mahasiswa Ekstensi S1 Ilmu Komputer angkatan 2014 terutama

Ahmad Roy, Agus, Dea, Dendy, Dhea Agie, Dwi Suciani, Fauziah Rosi, Ira, Irvi,

Kevin, Ogi, Rifwan, Sri Enggal, dan banyak lagi yang tidak dapat disebutkan satu

persatu.

Penulis sadar akan keterbatasan dan kukurangan dalam skripsi ini. Mohon

untuk memberikan kritik dan saran yang membangun dalam penyempurnaan skripsi

ini, sehingga dapat dimanfaatkan untuk kedepannya.

Medan, 27 Juli 2016

Penulis,

(Iqbal Habibie)


ABSTRAK

Mendapatkan informasi dapat dilakukan dengan berbagai cara, dapat dilakukan

dengan cara manual yaitu dengan media kertas sebagai sumber informasi dan dapat

dilakukan dengan media elektronik. Dengan media kertas cukup menghabiskan waktu

yang relatif lama tergantung seberapa banyak informasi yang ingin diketahui, akan

tetapi dengan media elektronik, dapat mempersingkat waktu pencarian informasi.

Informasi bisa didapatkan melalui buku, koran, majalah maupun jurnal elektronik

untuk pendidikan tinggi. Jurnal umumnya diperlukan untuk mempublikasikan hasil

penelitian seseorang, apabila jurnal dibaca dengan perlahan akan menghabiskan waktu

yang juga lama, jika jurnal tersebut merupakan jurnal cetak, lain halnya jika jurnal

berbasis elektronik yang umumnya berekstensi .pdf. Dalam hal ini dibutuhkan cara

untuk mendapatkan informasi secara cepat dan tepat berbasis elektronik, dengan

sistem pencarian kata pada jurnal berekstensi .pdf menggunakan algoritma Colussi

yang fase pencariannya dilakukan dari kiri ke kanan dengan tahapan awal menentukan

beberapa fungsi seperti inisialisasi i, kmin[i], h[i], next[i], shift[i], hmax[i], rmin[i] dan

ndh[0] untuk melakukan pencocokan. Pada algoritma Simon fase pencarian dilakukan

dari kiri ke kanan pada string dengan melakukan inisialisasi indeks yang nilainya

dimulai dari -1 untuk keadaan tidak cocok dan terminal pada indeks terakhir pada pola

yang diberikan. Dengan penelitian ini diharapkan dapat membantu mendapatkan

informasi tentang hasil penelitian seseorang. Penulis mendapatkan hasil pada

penelitian ini bahwa algoritma Colussi lebih cepat dalam proses pencarian dengan

memperoleh waktu rata-rata 0,2848 ms dibanding algoritma Simon yang mendapatkan

waktu proses rata-rata yaitu 0,9005 ms.

Kata Kunci: Jurnal, String Matching, Elektronik.


ANALYSIS AND COMPARISON OF COLUSSI ALGORITHM AND SIMON

ALGORITHM TO SEARCH A WORDS ON JOURNAL

ABSTRACT

Getting the information can be done in many ways, can be manually by paper media a

source of informations and can be done in an electronic of media. The paper of media

spend a relatively long time depending on how a lot of information they want to know,

however with an electronic of media, may shorten search time of information.

Information can be found through books, a newspaper, magazines and an electronic

journal on university. Journals generally required to publish the results of the study, if

a journal read by slowly will spend also a long time, it is different if based an

electronic journals is generally .pdf extension. In this case needed the way to get

information quickly and correct with an electronics based, the search words system on

a journal with .pdf extension, the search phase using Colussi algorithm is done from

left to right with the pre-processing of determining some functions such as

initialization i, kmin[i], h[i], next [i] shift[i], hmax[i], rmin[i] and ndh[0] to do the

matching. In the search phase of Simon algorithm performed from left to right on

string by initializing an index whose value starts from -1 is mismatch and terminal on

the last index on patterns are given. To this research expected to help get information

about the public results. Author get results in this study that the Colussi algorithm

faster in the search process by obtaining an average of 0,2848 ms than Simon

algorithm that gets the average processing time is 0,9005 ms.

Keywords: Journal, String Matching, Electronic.


DAFTAR ISI

halaman

Persetujuan i

Pernyataan ii

Penghargaan iii

Abstrak v

Abstract vi

Daftar Isi vii

Daftar Tabel ix

Daftar Gambar x

BAB 1 PENDAHULUAN 1

1.1 Latar Belakang 1

1.2 Rumusan Masalah 3

1.3 Ruang Lingkup Masalah 4

1.4 Tujuan Penelitian 4

1.5 Manfaat Penelitian 5

1.6 Metode Penelitian 5

1.7 Sistematika Penulisan 6

BAB 2 LANDASAN TEORI 8

2.1 Algoritma 8

2.2 Algoritma String Matching 9

2.2.1 Algoritma Colussi 10

2.2.1.1 Ilustrasi Pencarian dengan Algoritma Colussi 11

2.2.1.2 Contoh Kasus dengan Algoritma Colussi 13

2.2.2 Algoritma Simon 14

2.2.2.1 Ilustrasi Pencarian dengan Algoritma Colussi 15

2.2.2.2 Contoh Kasus dengan Algoritma Simon 17

2.3 Analisis Algoritma 20

2.3.1 Big-O 20

BAB 3 ANALISIS DAN PERANCANGAN SISTEM 22

3.1 Analisis Sistem 22

3.2 Analisis Kebutuhan 24

3.2.1 Kebutuhan Fungsional 24

3.2.2 Kebutuhan Non-Fungsional 24

3.3 Pemodelan Sistem 25

3.3.1 Diagram Use Case 25

3.3.2 Diagram Activity 27

3.3.3 Diagram Sequence 28

3.4 Perancangan Sistem 29

3.4.1 Perancangan Halaman Awal 30


3.4.2 Perancangan Halaman Proses Pemilihan Dokumen 31

3.4.3 Perancangan Halaman Pengambilan String pada Jurnal 32

3.4.4 Perancangan Halaman Hasil Pencarian 33

3.5 Flowchart 34

3.5.1 Flowchart Sistem 34

3.5.2 Flowchart Algoritma Colussi 36

3.5.3 Flowchart Algoritma Simon 42

3.6 Hasil Analisis Algoritma Colussi dan Algoritma Simon

dalam Pencarian Kata pada Jurnal 42

3.6.1 Alasan Melakukan Analisis Sistem 43

3.6.2 Permasalahan Dalam Mencari Informasi Secara Manual 43

3.6.3 Identifikasi Penyebab Masalah 43

3.6.4 Hasil Analisis 43

BAB 4 IMPLEMENTASI DAN PENGUJIAN 44

4.1 Implementasi Pencarian Kata dengan Algoritma Colussi 44

4.1.1 Hasil Implementasi dengan Algoritma Colussi 47

4.2 Implementasi Pencarian Kata dengan Algoritma Simon 48

4.2.1 Hasil Implementasi dengan Algoritma Simon 50

4.3 Proses Pengambilan Teks pada Dokumen Jurnal 51

4.3.1 Pseudocode Pengambilan Teks Dokumen .pdf 52

4.3.2 Pseudocode Library PDF To Text 53

4.3.3 Pseudocode Session Array 54

4.4 Analisis Data dan Pengujian Algoritma Colussi dan

Algoritma Simon 55

4.4.1 Kompleksitas Algoritma Colussi 69

4.4.2 Kompleksitas Algoritma Simon 70

BAB 5 PENUTUP 71

5.1 Kesimpulan 71

5.2 Saran 71

DAFTAR PUSTAKA 72

LAMPIRAN A1


DAFTAR TABEL

halaman

Tabel 3.1 Narasi Use Case Pencarian Kata Pada Jurnal 26

Tabel 3.2 Keterangan Rancangan Antarmuka Kepada User 30

Tabel 3.3 Keterangan Rancangan Interface Pemrosesan Sistem Pengguna 31

Tabel 3.4 Keterangan Halaman Pengambilan Teks Pada Dokumen Jurnal 33

Tabel 3.5 Keterangan Halaman Hasil Pencarian Dan Waktu Proses Algoritma 34

Tabel 4.1 Tabel Tahap Preprocessing Algoritma Colussi 44

Tabel 4.2 Inisialisasi Algoritma Colussi Tahap Pertama 44

Tabel 4.3 Inisialisasi Algoritma Colussi Tahap Kedua 45

Tabel 4.4 Inisialisasi Pada Algoritma Simon 48

Tabel 4.5 Data Jurnal 55

Tabel 4.6 Contoh Satu Kata Dalam Pengujian 60

Tabel 4.7 Analisis Hasil Pencarian dan Waktu Proses Algoritma Satu Kata 63

Tabel 4.8 Contoh Dua Kata Dalam Pengujian 64

Tabel 4.9 Analisis Hasil Pencarian dan Waktu Proses Algoritma Dua Kata 67

Tabel 4.10 Kompleksitas Waktu Algoritma Colussi Dengan Big-O(n) 69

Tabel 4.11 Kompleksitas Waktu Algoritma Simon Dengan Big-O(n) 70


DAFTAR GAMBAR

halaman

Gambar 2.1 Konsep Algoritma 9

Gambar 2.2 Fase Pencarian Dengan Algoritma Simon 14

Gambar 2.3 Analisis Algoritma Dengan Notasi-O 21

Gambar 3.1 Diagram Fishbone (Ishikawa) Dalam Analisis Masalah 23

Gambar 3.2 Diagram Use Case 26

Gambar 3.3 Diagram Activity 27

Gambar 3.4 Diagram Sequence 28

Gambar 3.5 Rancangan Antarmuka Kepada User 30

Gambar 3.6 Rancangan Interface Pemrosesan Sistem Pada Pengguna 31

Gambar 3.7 Perancangan Halaman Pengambilan Teks Pada Dokumen Jurnal 32

Gambar 3.8 Perancangan Hasil Pencarian Dan Waktu Proses Dengan Algoritma 33

Gambar 3.9 Flowchart Sistem Pencarian Kata Pada Jurnal 35

Gambar 3.10 Flowchart Algoritma Colussi 36

Gambar 3.11 Flowchart Menentukan Fungsi kmin 37

Gambar 3.12 Flowchart Menentukan h 38

Gambar 3.13 Flowchart Menentukan Fungsi shift 39

Gambar 3.14 Flowchart Menentukan hmax 40

Gambar 3.15 Flowchart Menentukan Fungsi rmin 41

Gambar 3.16 Flowchart Algoritma Simon 42

Gambar 4.1 Implementasi Halaman Pemilihan Dokumen Jurnal 47

Gambar 4.2 Implementasi Halaman Pengambilan String Pada Jurnal 47

Gambar 4.3 Implementasi Halaman Pemilihan Dokumen Jurnal 50

Gambar 4.4 Implementasi Halaman Pengambilan String Pada Jurnal 51

Gambar 4.5 Proses Pengambilan Teks pada Dokumen 52

Gambar 4.6 Hasil Pencarian Dengan Algoritma Colussi Dan Algoritma Simon 59

Gambar 4.7 Pengujian Kata “Citra” 60

Gambar 4.8 Pengujian Kata “Data” 61

Gambar 4.9 Pengujian Kata “Proses” 61

Gambar 4.10 Pengujian Kata “Analisis” 62

Gambar 4.11 Pengujian Kata “Informasi” 62

Gambar 4.12 Grafik Hasil Waktu Proses Algoritma Colussi & Algoritma Simon 63

Gambar 4.13 Pengujian Kata “Perangkat lunak” 65

Gambar 4.14 Pengujian Kata “Perancangan sistem” 65

Gambar 4.15 Pengujian Kata “Ilmu komputer” 66

Gambar 4.16 Pengujian Kata “Perbandingan hasil” 66

Gambar 4.17 Pengujian Kata “Penelitian ini” 67

Gambar 4.18 Grafik Hasil Waktu Proses Dua Kata Algoritma Colussi &

Algoritma Simon 68


BAB 1

PENDAHULUAN

1.1 Latar Belakang

Manusia sering menghabiskan waktu yang lama untuk memperoleh suatu informasi,

terlebih lagi informasi yang harus dicari dilakukan secara manual dan masih

menggunakan kertas sebagai media pencarian informasi. Informasi merupakan

perkembangan suatu fakta yang diolah menjadi data kemudian di kelola menjadi suatu

informasi.

Masyarakat informasi telah menjadi idaman para pakar, yaitu sebuah

masyarakat yang berbasiskan ilmu pengetahuan, dimana informasi menjadi

komoditas yang sangat menentukan keberhasilan suatu usaha atau persaingan bisnis.

Dukungan atas kehadiran masyarakat informasi adalah tersedianya sarana untuk

menyalurkan informasi itu secara cepat, efektif, efisien dan murah, serta dapat

diakses dari mana saja, dimana saja dan kapan saja. (Sutabri, 2013). Pada sekarang

ini banyak metode yang sudah dipakai untuk memperoleh sebuah informasi yang

diciptakan untuk membantu manusia, informasi yang diperoleh baik berupa file teks

maupun file yang berekstensi .pdf maupun .doc.

Informasi serta pengetahuan tidak hanya didapatkan dari buku, majalah dan

media cetak lainnya, dalam kalangan pendidikan tinggi (universitas) jurnal

merupakan salah satu gudang pengetahuan dalam hal penelitian (research).

Umumnya, jurnal merupakan suatu file dokumen cetak yang berisi hasil penelitian

seseorang, dimana jurnal merupakan salah satu cara untuk berbagi penelitian kepada

orang banyak, serta memiliki manfaat untuk pembaca jurnal tersebut. Saat ini, jurnal

sudah banyak tersebar dalam bentuk softcopy, salah satu bentuk softcopy adalah

dokumen jurnal berekstensi pdf (portable document format).


Dalam penelitian ini, penulis menentukan dokumen jurnal berekstensi .pdf yang

dijadikan acuan pemikiran untuk menganalisis dan membandingkan algoritma string

matching yaitu algoritma Colussi dan algoritma Simon dalam pencarian kata pada

jurnal, hal ini diharapkan dapat membantu mahasiswa dan tenaga pengajar untuk

mendapatkan informasi secara cepat tanpa harus membaca perlahan-lahan untuk

setiap informasi yang ingin dicari.

Algoritma adalah prosedur untuk melakukan satu tugas spesifik. Algoritma

merupakan gagasan di balik suatu program komputer. Satu algoritma harus

menyelesaikan satu persoalan yang dispesifikasi dengan bagus. Satu persoalan

algoritma dispesifikasi dengan mendeskripsi kumpulan lengkap instan dimana

algoritma harus bekerja dan juga dinyatakan mengenai properti-properti keluaran

yang harus dimiliki sebagai hasil dari menjalankan pada instan-instan itu. Algoritma

adalah satu prosedur yang masukannya suatu instan masukan yang mungkin dan

mentransformasi menjadi keluaran yang dikehendaki. (Hariyanto, 2008).

String matching adalah suatu pemrosesan string dimana menjadi kebutuhan

utama dalam memperoleh informasi pada teks yang membantu manusia menemukan

infomasi lebih cepat karena memiliki algoritma untuk pencarian string tersebut. Ada

beberapa langkah untuk pencocokan string yaitu diberikan string yang panjangnya n

karakter, lalu diberikan pola string dengan panjang karakter (m<n) yang akan

diproses atau dicari pada teks.

Pada penelitian terdahulu Nababan (2015) pada penelitiannya yang berjudul

implementasi algoritma Brute Force dan algoritma Knuth-Morris-Pratt dalam

pencarian word suggestion yang telah mendapatkan hasil yang cukup baik yaitu

untuk KMP dengan hasil rata-rata 0,42717 ms dan untuk Brute Force 0,44683 ms

dalam string matching.

Nasution (2015) dengan judul penelitian sistem pencarian kata pada media

massa online menggunakan algoritma Rabin-Karp yang telah memiliki kesimpulan

bahwa semakin besar jumlah kemiripannya maka akan semakin besar kemungkinan

berita tersebut berhubungan dengan keyword yang dimasukkan.


Sagita dan Prasetiyowati (2013) dalam penelitiannya berjudul studi perbandingan

Boyer-Moore, Turbo Boyer-Moore, dan Tuned Boyer-Moore dalam pencarian string

mendapatkan hasil dari penelitiannya bahwa algoritma Boyer-Moore adalah

algoritma yang paling cepat dalam pencarian serta dalam pengubah kata (replace),

highlight kata yang dicari, dan pemberian informasi waktu yang dibutuhkan masing-

masing algoritma dan algoritma mana yang membutuhkan waktu paling sedikit untuk

pencarian.

Hajar (2015) pada penelitiannya yang berjudul implementasi algoritma

levenshtein distance dan Boyer Moore untuk fitur autocomplete dan autocorrect

pada aplikasi katalog perpustakaan daerah Aceh Timur mendapatkan hasil yang baik

dalam penelitiannya untuk penggunaan algoritma Boyer Moore pada proses string

matching dan untuk autocorrect yaitu algoritma Levenshtein Distance mengeluarkan

hasil yang berupa prediksi judul buku yang diketikkan oleh pengguna.

Dengan membandingkan suatu algoritma string matching akan di peroleh

suatu hasil manakah yang terbaik dalam pencocokan string dengan algoritma, dimana

algoritma yang akan dibandingkan adalah algoritma Colussi dan algoritma Simon

untuk mendapatkan hasil yang terbaik dalam pencocokan string (string matching).

1.2 Rumusan Masalah

Rumusan masalah yang akan dibahas adalah sebagai berikut:

a. Menganalisis bagaimana algoritma Colussi dan algoritma Simon bekerja untuk

string matching.

b. Mengukur kemampuan penerapan dalam perbandingan algoritma Colussi dan

algoritma Simon dengan kata yang akan diberikan oleh pengguna.

c. Melihat keakuratan perbandingan algoritma Colussi dan algoritma Simon dalam

string matching.


1.3 Ruang Lingkup Masalah

Agar penelitian tidak meluas, diberikan batasan sebagai berikut:

a. Membandingkan algoritma string matching yaitu algoritma Colussi dan algoritma

Simon yang dibangun menggunakan perangkat lunak komputer bebasis web yaitu

dengan PHP.

b. Dokumen jurnal yang dapat digunakan adalah jurnal Alkhawarizimi yaitu

kumpulan jurnal online yang berasal dari program studi S1 Ilmu Komputer

Fasilkom-TI USU.

c. Data masukan yang diberikan oleh pengguna berupa teks yang pada sebelumnya

pengguna telah meng-input data berupa dokumen jurnal berekstensi .pdf yang

tidak terkunci (not secured) dokumen.

d. Menghitung kompleksitas ukuran Big-O dengan fase pencarian dapat dilakukan

dengan kompleksitas waktu O(n).

e. Data keluaran berupa hasil perbandingan, rekomendasi kata yang berhubungan

dengan string yang di input oleh pengguna, serta hasil dari running time

calculation dari tiap-tiap dokumen jurnal yang telah di upload ke dalam sistem

dengan menerapkan algoritma tersebut.

1.4 Tujuan Penelitian

Adapun tujuan penelitian perbandingan algoritma Colussi dan algoritma Simon

adalah sebagai berikut:

a. Menemukan string yang tepat yang diinginkan oleh pengguna untuk membantu

pengguna memperoleh informasi secara cepat.

b. Membandingkan seberapa baik algoritma string matching diterapkan dan apakah

tepat sasaran dengan apa yang diinginkan oleh pengguna.

c. Menghemat waktu dalam memperoleh informasi secara elektronik melalui

desktop berbasis web.


http://id.portalgaruda.org/?ref=browse&mod=viewjournal&journal=4147&issue=%20Vol%201,%20No%201%20(2012):%20Jurnal%20Alkhawarizimi

1.5 Manfaat Penelitian

Dengan penelitian ini, penulis mengharapkan agar tepat terhadap sasaran pengguna

yaitu mahasiswa, tenaga pengajar serta orang-orang yang membutuhkan cara yang

cepat untuk menemukan informasi yang berupa dokumen jurnal berekstensi .pdf.

1.6 Metode Penelitian

Dalam metode penelitian akan digunakan beberapa tahapan dalam peneletian ini yaitu

sebagai berikut:

1. Studi Pustaka

Pada studi pustaka, penulis mempelajari dari sumber-sumber seperti buku dalam

perpustakaan, dengan sumber-sumber yang berhubungan dengan algoritma string

matching seperti Knuth-Morris-Pratt yang merupakan awal mulanya algoritma Colussi

ada.

2. Analisis dan Perancangan Sistem

Pada tahapan analisis dan perancangan sistem, penulis akan membuat pemodelan

sistem dengan Unified Modeling Language (UML) yang berfungsi untuk

memudahkan pengguna untuk mengerti bagaimana sistem berjalan dengan

memanfaatkan use case diagram, activity diagram dan sequence diagram.

3. Implementasi

Hasil dari analisis dan peracangan sistem di implementasikan ke dalam bahasa

pemrograman dengan menggunakan PHP (Pre-Hyper Processor) untuk menjalankan

sistem yang merupakan hasil dari penelitian penulis.


4. Pengujian

Tahapan pengujian merupakan tahapan yang penting dalam suatu pembangunan suatu

sistem yaitu melihat seberapa baik pengimplementasiannya dan apakah tepat dengan

tujuan penelitian.

5. Dokumentasi

Tahap dokumentasi merupakan tahap akhir pada penelitian, tahapan ini dimulai dari

analisis sampai dengan pengujian dalam bentuk penelitian (skripsi).

1.7 Sistematika Penulisan

Beberapa bagian utama dalam sistematika penulisan skripsi ini adalah sebagai berikut:

BAB 1 PENDAHULUAN

Dalam bagian ini mengemukakan latar belakang penelitian penulis yang berjudul

“Analisis dan perbandingan algoritma Colussi dan algoritma Simon dalam pencarian

kata pada jurnal”, rumusan masalah, ruang lingkup masalah, tujuan penelitian,

manfaat penelitian, metode penelitan serta sistematika penulisan.

BAB 2 LANDASAN TEORI

Pada bagian landasan teori, mengemukakan teori apa saja yang berkaitan dengan

ruang lingkup penelitian, berupa teori algoritma, analisis algoritma, algoritma Colussi

dan algoritma Simon serta teori pendukung dalam implementasi ke dalam bahasa

pemrograman.

BAB 3 ANALISIS DAN PERANCANGAN SISTEM

Bagian ini berisi tentang analisis algoritma bekerja untuk string matching, pemodelan

sistem yang terdiri dari flowchart dan UML (Unified Modeling Language) serta

desain interface untuk pengguna.


BAB 4 IMPLEMENTASI DAN PENGUJIAN

Untuk pembuktian, diperlukan implementasi dari penelitian, dalam implementasi dan

pengujian terdapat hasil analisis dan perancangan sistem apakah sesuai dengan tujuan

penelitian.

BAB 5 PENUTUP

Kesimpulan dan saran merupakan bagian terakhir dalam penelitian, kesimpulan yang

diperoleh dari hasil penelitian dan saran yang dikemukakan untuk perbaikan dalam

penelitian yang berikutnya.


BAB 2

LANDASAN TEORI

2.1 Algoritma

Dalam pembuatan sebuah program ada beberapa faktor yang harus dipertimbangkan,

yaitu sintaksis, semantik, dan kebenaran logika. Sintaksis dapat diartikan sebagai tata

bahasa yang digunakan dalam program. Semantik adalah maksud yang dikandung

pada setiap pernyataan di dalam program. Sementara kebenaran logika berhubungan

dengan benar-tidaknya urutan pernyataan serta prosedur yang ada dalam program,

atau yang biasa disebut algoritma.

Dalam matematika dan komputasi, algoritma merupakan kumpulan perintah

yang saling berkaitan untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat

diterjemahkan secara bertahap dari awal hingga akhir. Dalam penyusunannya

diperlukan urutan serta logika agar algoritma yang dihasilkan sesuai dengan yang

diharapkan. Algoritma merupakan bagian terpenting dan tidak dapat dipisahkan dari

pemrograman. Meskipun sintaksis dan semantik yang dibuat benar adanya, dengan

algoritma yang keliru, permasalahan yang ingin dipecahkan dengan teknik

pemrograman tidak akan berhasil. Oleh karena itu, sebelum membuat suatu program

aplikasi, hal pertama yang harus kita pahami adalah algoritma atau prosedur

pemecahannya. Hal ini bertujuan agar program yang telah dibuat dapat sesuai dengan

yang diharapkan. Berikut beberapa hal yang harus dipertimbangkan untuk membuat

sebuah algoritma. (Ramadhani, 2015).

a. Algoritma yang dibuat haruslah benar. Artinya, algoritma harus memberikan

output yang bagus. Dengan algoritma yang benar, hasil yang diharapkan dapat

dicapai.


masalah

algoritma

“komputer” input output

b. Selain benar, algoritma juga harus efektif. Maksudnya, seberapa baik algoritma

yang digunakan mendekati hasil yang diharapkan. Hal ini sangatlah penting

terutama jika permasalahan yang dihadapi cukup rumit dan memerlukan

perkiraan hasil sedekat mungkin.

c. Algoritma yang digunakan harus efisien. Efisiensi sebuah algoritma dapat ditinjau

dari efisiensi waktu dan memori yang digunakan. Meskipun algoritma yang kita

gunakan mendekati hasil yang diharapkan, namun jika membutuhkan waktu yang

sangat lama, bahkan berjam-jam, biasanya algoritma itu akan jarang dipakai.

Suatu algoritma adalah suatu urutan instruksi yang tidak ambigu untuk

menyelesaikan suatu masalah, yaitu untuk mendapatkan hasil yang disyaratkan untuk

setiap input logis dalm suatu jangka waktu tertentu. (Levitin, 2010).

Gambar 2.1 yaitu mengenai konsep algoritma yang memberikan ilustrasi

bagaimana algoritma menyelesaikan suatu masalah, dengan komputer sebagai media

input dan output.

Gambar 2.1 Konsep algoritma


2.2 Algoritma String Matching

Algoritma pencocokan string merupakan komponen dasar dalam pengimplementasian

berbagai perangkat lunak praktis yang sudah ada. String matching digunakan untuk

menemukan satu atau lebih string yang disebut dengan pattern (string yang akan

dicocokkan ke dalam text) dalam string yang disebut dengan text (string yang di-

input). (Charras dan Lecroq, 1997).

2.2.1 Algoritma Colussi

Algoritma Colussi adalah modifikasi dari algoritma Knuth-Morris-Pratt (KMP), pada

algoritma Knuth-Morris-Pratt sendiri adalah algoritma pencocokan string dengan cara

memelihara informasi karakter-karakter sebelumnya untuk melakukan jumlah

pergeseran yang lebih jauh. Pada algoritma Colussi sendiri, himpunan dari posisi pola

dibagi menjadi dua sub-himpunan terpisah. Lalu percobaan pencocokan berlangsung

selama dua fase:

a. Fase pertama: Perbandingan dilakukan dari kiri ke kanan pada teks yang terletak

pada posisi yang sama dengan posisi pola dimana nilai dari fungsi algoritma

Knuth-Morris-Pratt adalah sedikit lebih besar dari -1. Posisi-posisi ini dinamakan

no-hole(s).

b. Fase kedua: Membandingkan posisi-posisi yang tersisa (nama lainnya adalah

hole(s)) dari arah kiri ke kanan.

Strategi ini memberikan dua kelebihan, yaitu:

a. Ketika terjadi ketidakcocokan pada fase pertama, maka setelah terjadi pergeseran

tidak perlu untuk membandingkan teks dengan noholes yang dibandingkan pada

percobaan sebelumnya.

b. Ketika ketidakcocokan terjadi pada fase kedua yang berarti ada suffix dari pola

yang sama dengan bagian di dalam teks, maka setelah terjadi pergeseran bagian

prefix dari pola akan tetap sama dengan bagian dari teks tersebut, sehingga tidak

diperlukan pembandingan kembali.


2.2.1.1 Ilustrasi Pencarian dengan Algoritma Colussi

Percobaan pertama:

Pergeseran dari 3

Percobaan kedua:

Pergeseran dari 2

Percobaan ketiga:

Pergeseran dari 7

Percobaan keempat:

Pergeseran dari 1


Percobaan kelima:

Pergeseran dari 1

Percobaan keenam:

Pergeseran dari 1

Percobaan ketujuh:

Pergeseran dari 1

Percobaan kedelapan:

Pergeseran dari 3


Algoritma Colussi menampilkan 20 karakter teks perbandingan dalam contoh

ilustrasi.

2.2.1.2 Contoh Kasus dengan Algoritma Colussi

Pattern: gori

String : algoritma

h:

0 1 2 3

g o r i

1 2 3 0

o o o o

next:

0 1 2 3 4

o o o o o

1 2 3 4 4

o r i

Percobaaan ke-1:

a l g o r i t m a

. o . . . . . . .

Percobaan ke-2:

a l g o r i t m a

. . o . . . . . .

Percobaan ke-3:


a l g o r i t m a

. . g o r i . . .

Panjang string: 9

Panjang pola: 4

Pergeseran: 4

Perbandingan karakter: 6

2.2.2 Algoritma Simon

Algoritma Simon merupakan peningkatan yang sedikit lebih jauh dari algoritma

Knuth-Morris-Pratt. Algoritma Simon memeriksa apakah y merupakan awalan setelah

u didalam P, yang merupakan karakter x setelah u didalam T. Jika tidak, algoritma ini

akan meneruskan fase pencariannya lebih lanjut. Proses string matching untuk

algoritma Simon diperlihatkan pada gambar 2.2.

Gambar 2.2 Fase pencarian algoritma Simon

T

T

P

u

uu

P

u

u

x

y

x

y


2.2.2.1 Ilustrasi Pencarian dengan Algoritma Simon

Keadaan awal adalah lebih besari dari -1


Algoritma Simon menampilkan 24 karakter teks perbandingan dalam contoh

ilustasi.

2.2.2.2 Contoh Kasus dengan Algoritma Simon

Pattern: gori

String : algoritma

Inisialisasi dimulai dari -1

Keadaan : -1 { g → 0 }

Keadaan : 0 { g → 0 o → 1 }

Keadaan : 1 { g → 0 r → 2 }

Keadaan : 2 { g → 0 i → 3 }

Keadaan : 3 { }

Berhenti di keadaan 3


Percobaan 1

a l g o r i t m a

↑ . . . . . . . .

Tidak cocok karena tidak sesuai dengan keadaan -1.a diberi nilai -1 yaitu mismatch

Percobaan 2

a l g o r i t m a

. ↑ . . . . . . .

Tidak cocok karena tidak sesuai dengan keadaan -1.l diberi nilai -1 yaitu mismatch

Percobaan 3

a l G o r i t m a

. . ↑ . . . . . .

Cocok karena sesuai dengan keadaan -1.g diberi nilai 0 yaitu match

Percobaan 4

a l G o r i t m a

. . . ↑ . . . . .

Cocok karena sesuai dengan keadaan 0.o diberi nilai 1 yaitu match

Percobaan 5

a l G O r i t m a

. . . . ↑ . . . .

Cocok karena sesuai dengan keadaan 1.r diberi nilai 2 yaitu match


Percobaan 6

a l G O R i t m a

. . . . . ↑ . . .

Cocok karena sesuai dengan keadaan 2.i diberi nilai 3 yaitu match

Percobaan 7

a l G O R I t m a

. . . . . . ↑ . .

Tidak cocok karena tidak sesuai dengan keadaan -1.t diberi nilai -1 yaitu mismatch

Percobaan 8

a l g o r i t m a

. . . . . . . ↑ .

Tidak cocok karena tidak sesuai dengan keadaan -1.m diberi nilai -1 yaitu

mismatch

Percobaan 9

a l g o r i t m a

. . . . . . . . ↑

Tidak cocok karena tidak sesuai dengan keadaan -1.a diberi nilai -1 yaitu mismatch

Hasil akhir yaitu didapatkan string sesuai dengan pola yang diberikan pada kasus

a l G O R I t m a

Panjang string: 9

Panjang pola: 4

Perbandingan inspeksi: 9


2.3 Analisis Algoritma

Terdapat dua jenis efisiensi algoritma yaitu efisiensi waktu dan efisiensi ruang.

Efisiensi waktu menunjukkan seberapa cepat algoritma berfungsi, sedangkan efisiensi

ruang menunjukkan berapa banyak memori yang dibutuhkan algoritma tersebut.

Karakteristik lain yang diharapkan dari suatu algoritma adalah kesederhanaan.

Tidak seperti efisiensi yang dapat dengan tepat didefinisikan dan diinvestigasi dengan

kekakuan matematis, kesederhanaan, seperti halnya keindahan, bergantung pada

pandangan setiap orang. (Levitin, 2010).

2.3.1 Big-O

Pada penelitian ini, penulis akan membahas bagaimana algoritma Colussi dan

algoritma Simon bekerja dan menghasilkan output jika diberikan notasi O(Big-oh).

Sebuah fungsi t(n) dikatakan bagaian dari O(g(n)) yang dilambangkan dengan t(n) ϵ

O(g(n)), jika t(n) batas atasnya adalah beberapa konstanta g(n) untuk semua n besar,

jika terdapat konstanta c positif dan beberapa bilangan bulat non-negatif n0 seperti:

t(n) ≤ cg(n) untuk semua n ≥ n0

Sebagai contoh: 100n + 5 ϵ O(n2).

100n + 5 ≤ 100n + n (untuk semua n ≥ 5) = 101n ≤ 101n2.

Jadi, karena nilai-nilai konstatnta c dan n0 diperlukan sebagai definisi, kita bisa

mengambil masing-masing 101 dan 5. Perhatikan bahwa definisi tersebut memberi

kita banyak kebebasan dalam memilih nilai-nilai tertentu untuk konstatnta c dan n0.

Sebagai contoh kita dapat juga beralasan bahwa

100n + 5 ≤ 100n + 5n (untuk semua n ≥ 1) = 105n


Untuk melengkapi pembuktian dengan c = 105 dan n0 = 1.

Ilustrasi Big-O pada gambar 2.3 yang menerapkan notasi Big-O sebagai analisis

algoritma.

Gambar 2.3 Analisis algoritma dengan notasi-O

tidak jadi

masalah

n0 n

cg(n)

t(n)


BAB 3

ANALISIS DAN PERANCANGAN SISTEM

3.1 Analisis Sistem

Analisis sistem merupakan sebuah teknik pemecahan masalah yang menguraikan

sebuah sistem menjadi bagian-bagian komponen dengan tujuan mempelajari seberapa

bagus bagian-bagian komponen tersebut bekerja dan berinteraksi untuk meraih tujuan

mereka. Analisis sistem ditujukan untuk menyediakan tim proyek dengan pemahaman

yang lebih menyeluruh terhadap masalah-masalah dalam kebutuhan-kebutuhan yang

memicu proyek. Analisis sistem perlu bekerja dengan pengguna sistem untuk secara

jelas mendefinisikan persyaratan dan harapan bisnis untuk sistem baru apapun yang

akan dibeli atau dikembangkan. (Whitten, Bentley dan Dittman, 2004).

Menurut Jogiyanto (2005) yang berpendapat bahwa analisis sistem merupakan

penguraian dari suatu sistem informasi yang utuh ke dalam bagian-bagian

komponennya dengan maksud untuk mengidentifikasikan dan mengevaluasi

permasalahan-permasalahan, kesempatan-kesempatan, hambatan-hambatan yang

terjadi dan kebutuhan-kebutuhan yang diharapkan sehingga dapat diusulkan

perbaikan-perbaikannya.

Analisis dan perancangan sistem akan membahas bagaimana algoritma Colussi

dan algoritma Simon menyelesaikan masalah dalam pencarian kata pada jurnal,

dengan tahapan awal adalah perancangan sistem, merancang pemodelan visual dengan

UML (Unified Modeling Language) dan Flowchart lalu memahami konsep algoritma

Colussi dan algoritma Simon dan mengimplementasikannya ke dalam bahasa

pemrograman.


Pada Gambar 3.1 dibawah ini merupakan diagram fishbone (Ishikawa) yang

diperlukan untuk menganalisis sistem yaitu dengan menguraikan sebuah sistem

menjadi komponen-komponen dengan tujuan yaitu untuk mempelajari bagaimana

menganalisis sistem yang baik.

Gambar 3.1 Diagram fishbone (Ishikawa) dalam analisis masalah

Diagram Ishikawa pada gambar 3.1 diatas menjelaskan bahwa manusia cukup

sulit untuk mendapatkan informasi jika masih menggunakan media kertas sebagai

sumber informasinya, lalu diperlukan cara lain untuk mempermudah manusia

mendapatkan informasinya yang sebelumnya jika menggunakan media kertas

membutuhkan waktu yang relatif lama tergantung pada informasi apa yang ingin

dicari. Dengan masalah tersebut, dibutuhkan jurnal sebagai sumber informasi dengan

dokumen berekstensi .pdf untuk sistem pencarian kata pada jurnal yang menggunakan

algoritma Colussi dan algoritma Simon untuk menyelesaikan masalah tersebut.

MAN MATERIAL

METHOD MACHINE

Mencari informasi

dengan input kata

pada jurnal

berekstensi .pdf

Memerlukan cara yang

manual untuk memperoleh

informasi dengan waktu

yang relatif lama

Cukup sulit untuk

mendapatkan informasi

jika menggunakan

media kertas

Bagaimana algoritma

string matching yaitu

Colussi dan Simon

menemukan string

yang tepat dalam jurnal

berekstensi .pdf Dibutuhkan suatu

sistem untuk mencari

informasi dalam jurnal

berkestensi .pdf


3.2 Analisis Kebutuhan

Dalam analisis kebutuhan, perlu untuk mencari solusi alternatif, khususnya dalam

solusi teknik. Analisis kebutuhan juga memastikan sistem bekerja secara teknis dan

melakukan apa yang dibutuhkan oleh sistem baik secara fungsional maupun non-

fungsional. Tugas awal dalam fase analisis kebutuhan adalah mengidentifikasi dan

menyatakan kebutuhan.

3.2.1 Kebutuhan Fungsional

Kebutuhan fungsional adalah mengenai aktifitas dan layanan yang harus diberikan

atau disediakan oleh sebuah sistem. Kebutuhan fungsional tersebut adalah sebagai

berikut:

1. Pengguna meng-input data berupa dokumen jurnal berekstensi .pdf.

2. Sistem mengambil tiap-tiap string pada dokumen .pdf

3. Sistem menampilkan kembali string yang telah diambil pada dokumen jurnal.

4. Sistem harus menampilkan string yang di input atau dicari oleh pengguna.

3.2.2 Kebutuhan Non-Fungsional

Kebutuhan non-fungsional mendeskripsikan mengenai fitur, karakteristik, dan batasan

lainnya yang menentukan apakah sistem memuaskan atau tidak. Beberapa kebutuhan

non-fungsional dalam analisis kebutuhan adalah sebagai berikut:

1. Sistem menampilkan hasil perbandingan running time kedua algoritma string

matching yaitu algoritma Colussi dan algoritma Simon.

2. Sistem dapat digunakan dengan mudah oleh mahasiswa serta tenaga pengajar

yang membutuhkan informasi yang ada pada jurnal.

3. Jika kata yang di input oleh pengguna tidak tersedia pada dokumen jurnal, sistem

harus memberikan pesan not found atau data = 0 kepada pengguna (user).

4. Sistem yang digunakan hanya memerlukan web browser untuk mengeksekusi

program.


3.3 Pemodelan Sistem

Pemodelan dapat dibuat pada sistem yang ada sebagai cara untuk memahami sistem

tersebut dengan lebih baik atau untuk sistem yang sedang diusulkan sebagai cara

mendokumentasikan persyaratan atau perancangan teknis. (Whitten, Bentley dan

Dittman, 2004).

UML (Unified Modeling Language) merupakan suatu kumpulan konvensi

pemodelan yang digunakan untuk menentukan atau menggambarkan sebuah sistem

software yang terkait dengan objek. (Whitten, Bentley dan Dittman, 2004). Menurut

Sugrue J. (2009) Tujuan pemanfaatan UML adalah sebagai berikut:

1. Menyediakan bagi pengguna (analisis dan desain sistem) suatu bahasa pemodelan

visual yang ekspresif sehingga mereka dapat mengembangkan dan melakukan

pertukaran model data yang bermakna.

2. Menyediakan mekanisme yang spesialisasi untuk memperluas konsep inti.

3. Karena merupakan bahasa pemodelan visual dalam proses pengembangannya

maka UML bersifat independen terhadap bahasa pemrograman tertentu.

4. Memberikan dasar formal untuk pemahaman bahasa pemodelan.

5. Mendorong pertumbuhan pasar terhadap penggunaan alat desain sistem yang

berorientasi objek (OO).

6. Mendukung konsep pembangunan tingkat yang lebih tinggi seperti kolaborasi,

kerangka pola dan komponen terhadap suatu sistem.

7. Memiliki integritas praktik terbaik.

3.3.1 Diagram Use Case

Diagram use case mengidentifikasi dan menggambarkan fungsi-fungsi sistem dengan

menggunakan alat yang disebut use case, use case menggambarkan fungsi-fungsi

sistem dari sudut pandangan pengguna eksternal dan dalam sebuah cara dan

terminologi yang mereka pahami. Use case merupakan hasil penyusunan kembali

lingkup fungsionalitas menjadi banyak pernyataan fungsionalitas sistem yang lebih

kecil. (Whitten, Bentley dan Dittman, 2004).


Gambar 3.2 Diagram use case

Pada gambar 3.2 diagram use case, actor (pelaku) dapat menjalankan sistem jika

awalnya actor meng-input dokumen jurnal berekstensi .pdf, lalu sitem mengambil

tiap-tiap string kemudian string tersebut ditampilkan pada interface, jika sistem telah

menampilkan string, actor mencari kata yang ia ingin cari dan sistem mengeluarkan

hasil serta rekomendasi kata yang berhubungan dengan string yang di-input oleh actor

dan juga hasil perbandingan algoritma string matching.

Tabel 3.1 Narasi Use Case pencarian kata pada jurnal

Nama Pencarian Kata pada Jurnal

Aktor User yang telah ditentukan

Deskripsi Dalam pencarian kata pada jurnal dengan membandingkan

algoritma Colussi dan algoritma Simon

Alur Dasar Sistem membutuhkan data berupa dokumen jurnal .pdf untuk

mengeksekusi program

Alur Alternatif User meng-input string yang ingin dicari

Pra Kondisi User meng-input dokumen jurnal .pdf

Pasca Kondisi User mendapatkan string sesuai yang dicari dan running

time dalam pencarian kata dengan perbandingan algoritma


3.3.2 Diagram Activity

Diagram activity secara grafis digunakan untuk menggambarkan rangkaian aliran

aktifitas baik proses bisnis atau use case. Diagram ini juga dapat digunakan untuk

memodelkan action yang akan dilakukan saat sebuah operasi dieksekusi, dan

memodelkan hasi dari action tersebut.

Dengan diagram activity pada gambar 3.3 pengguna dapat mengetahui secara

detail bagaimana proses dan action yang terjadi saat pengguna mengeksekusi sistem.

Gambar 3.3 Diagram activity pencarian kata pada jurnal

Pada gambar 3.3 diagram activity, pengguna harus meng-input dokumen .pdf

lalu teks pada dokumen diambil kemudian ditampilkan kembali ke interface

pengguna, setelah teks ditampilkan, pengguna mulai meng-input kata yang ingin

dicari, lalu pengguna menekan tombol proses untuk melakukan pencarian yang


dilakukan oleh sistem, setelah sistem memproses, sistem memberikan hasil kepada

pengguna lewat interface dan menampilkan hasil dari pencarian kata masing-masing

algoritma yaitu algoritma Colussi dan algoritma Simon.

3.3.3 Diagram Sequence

Menurut Whitten, Bentley dan Dittman (2004) Diagram sequence secara grafis

menggambarkan bagaimana objek berinteraksi dengan satu sama lain melalui pesan

pada eksekusi sebuah use case atau operasi. Diagram ini mengilustrasikan bagaimana

pesan terkirim dan diterima di antara objek dan dalam sekuensi apa.

Pada gambar 3.4 yaitu merupakan diagram sequence yang menjelaskan urutan

proses berdasarkan waktu.

Gambar 3.4 Diagram sequence

3.4 Perancangan Sistem

Menurut Jogiyanto (2005) yang mengutarakan bahwa tahap perancangan sistem

mempunyai dua maksud atau tujuan utama yaitu:

1. Untuk memenuhi kebutuhan kepada pemakai sistem.


2. Untuk memberikan gambaran yang jelas dan rancang bangun yang lengkap

kepada pemrogram komputer dan ahli-ahli teknik lainnya yang terlibat.

Tujuan kedua ini lebih condong pada desain sistem yang terinci, yaitu

pembuatan rancang bangun yang jelas dan lengkap untuk nantinya digunakan untuk

pembuatan program komputernya. Untuk mencapai tujuan ini, analisis sistem harus

dapat mencapai sasaran-sasaran sebagai berikut ini.

1. Desain sistem harus berguna, mudah dipahami dan nantinya mudah digunakan.

Ini berarti bahwa data harus mudah ditangkap, metode-metode harus mudah

diterapkan dan informasi harus mudah dihasilkan serta mudah dipahami dan

digunakan.

2. Desain sistem harus dapat mendukung tujuan utama perusahaan sesuai dengan

yang telah didefiniskan pada tahap perencanaan sistem yang dilanjutkan pada

tahap analisis sistem.

3. Desain sistem harus efisien dan eefktif untuk dapat mendukung pengolahan

transaksi, pelaporan manajemen dan mendukung keputusan yang akan dilakukan

oleh manajemen, termasuk tugas-tugas yang lainnya yang tidak dilakukan oleh

komputer.

4. Desain sistem harus dapat mempersiapkan rancang bangun yang terinci untuk

masing-masing komponen dari sistem informasi yang meliputi data dan

informasi, simpanan data, metode-metode, prosedur-prosedur, orang-orang,

perangkat keras, perangkat lunak dan pengendalian sistem.

Antarmuka (interface) dapat disebut juga sebagai wajah dari suatu aplikasi,

sehingga ketika seorang user atau pengguna pertama kali mengakses suatu aplikasi,

maka bagian pertama yang akan muncul adalah antarmuka (interface). (Nababan,

2015). Dengan interface, seorang pengguna dapat berinteraksi dan mendapatkan

kebutuhannya dalam hal mengambil maupun memberi informasi terhadap sistem

tanpa harus mengetahui program yang ada didalamnya.


3.4.1 Perancangan Halaman Awal

Pada halaman awal antarmuka gambar 3.5 user diberikan tampilan yang didalamnya

terdapat beberapa menu yaitu menu beranda, proses dan tentang sistem tersebut.

Gambar 3.5 Rancangan antarmuka kepada user

Tabel 3.2 Keterangan rancangan antarmuka kepada user

No. Keterangan

1. Header awal untuk interface kepada pengguna yang dapat berupa simbol

maupun title.

2. Menu navigasi yang dapat berisi tentang informasi sistem dan menu proses

3. Badan (isi) tampilan

4. Footer halaman interface

1

3

2

4


3.4.2 Perancangan Halaman Proses Pemilihan Dokumen

Pada perancangan halaman proses pemilihan dokumen gambar 3.6, pengguna

diwajibkan untuk menambahkan dokumen jurnal untuk pencarian kata, dokumen ini

merupakan kebutuhan untuk menjalankan sistem, diperlukan data berupa dokumen

jurnal untuk kemudian diolah.

Gambar 3.6 Rancangan interface pemrosesan sistem pada pengguna

Tabel 3.3 Keterangan rancangan interface pemrosesan sistem pada pengguna

No. Keterangan

1. Tombol untuk meng-input dokumen jurnal (.pdf)

2. Indikator pada rancangan interface menunjukkan tidak ada file yang dipilih

pengguna

1 2


3.4.3 Perancangan Halaman Pengambilan String pada Jurnal

Setelah melewati tahap pemilihan dokumen, pengguna akan diberikan interface pada

gambar 3.7, sistem hanya mengambil setiap teks atau string yang ada pada jurnal dan

di tampilkan lalu pengguna harus meng-input kata yang akan dicari.

Tahapan pengambilan teks pada dokumen jurnal menggunakan library PDF

To Text yang pada awalnya pengguna harus meng-input beberapa dokumen jurnal

berekstensi .pdf untuk kemudian sistem memproses dengan library PDF To Text

dimana sistem mengambil semua teks pada dokumen, teks tersebut disimpan ke dalam

array, selanjutnya teks di tampilkan sementara pada interface pengguna, ketika

pengguna memulai untuk mencari kata dengan menekan tombol pencarian, sistem

akan melakukan tahapan pencarian menggunakan algoritma Colussi dan algoritma

Simon pada session array, dengan session array, pola yang diberikan oleh pengguna

dapat ditemukan string yang sesuai.

Gambar 3.7 Perancangan halaman pengambilan teks pada dokumen jurnal

1

2

3


Tabel 3.4 Keterangan halaman pengambilan teks pada dokumen jurnal

No. Keterangan

1 Textarea yang berisi setiap teks yang di ambil pada dokumen jurnal

2 Kolom pencarian untuk meng-input kata

3 Tombol untuk memulai proses pencarian

3.4.4 Perancangan Halaman Hasil Pencarian

Setelah pengguna meng-input kata, sistem akan memproses dengan algoritma Colussi

dan algoritma Simon lalu menampilkan hasil pencarian dan waktu proses pencarian

kata pada dokumen jurnal seperti yang terlihat pada halaman peracangan hasil

pencarian pada gambar 3.8.

Gambar 3.8 Perancangan hasil pencarian dan waktu proses dengan algoritma.

3 2

1


Tabel 3.5 Keterangan halaman hasil pencarian dan waktu proses algoritma

No. Keterangan

1 Kata yang sebelumnya telah di input oleh pengguna

2 Waktu proses dengan algoritma Colussi

3 Waktu proses dengan algoritma Simon

3.5 Flowchart

Flowchart adalah suatu representasi dari sebuah alur proses pada sistem secara logika.

3.5.1 Flowchart Sistem

Pada flowchart sistem, pengguna mula-mula memilih dan meng-input suatu dokumen

jurnal berekstensi .pdf, sistem memberikan respon dengan mengambil semua teks

pada dokumen jurnal, lalu sistem menampilkan teks yang telah diambil.

Sesaat setelah teks ditampilkan ke user interface, user mulai memberikan

input sebuah kata yang akan dicari oleh sistem. Dalam hal pemrosesan, sistem akan

melakukan pencarian dengan algoritma Colussi dan algoritma Simon. Setelah

mendapatkan hasil pencarian, sistem akan memberikan respon ke user interface

dimana user dapat mengetahui ada atau tidaknya kata yang di-input oleh pengguna

pada jurnal dan mengetahui waktu proses dalam fase pencarian, kemudian sistem

mengurutkan berdasarkan dokumen yang memiliki kata terbanyak sesuai yang di input

dan menampilkan dokumen yang dipilh oleh pengguna. Diperlihatkan pada gambar

3.9.


Mulai

Input Dokumen Jurnal

.pdf

Ambil Teks Dari Dokumen

Input Kata Yang

Dicari

Proses Matching Dengan

Algoritma Colussi dan

Algoritma Simon

Tampilkan Hasil Pencarian

Dengan Dokumen Dan Waktu

Pada Algoritma Colussi Dan

Algoritma Simon

Buka Dokumen Jurnal yang

Dipilih

Tampilkan Pemilihan

Dokumen Berdasarkan

Pengurutan

Selesai

Gambar 3.9 Flowchart sistem pencarian kata pada jurnal


3.5.2 Flowchart Algoritma Colussi

Mulai

input i, m, n,

j, nd

nd =

preColussi(x, m,

h, next, shift)

i = j = 0

last = -1

j <= n - m

i < m && last < j + h[i] &&

x[h[i]] == y[j + h[i]]

TRUE

i ++

TRUE

A

i >= m || last >= j + h[i]

j

TRUE

i = m

i > nd

last = j + m = 1

TRUE

j += shift[i]

i = next[i]

Selesai

A

FALSE

FALSE

FALSE

FALSE

Gambar 3.10 Flowchart algoritma Colussi


Start

for (i = m, i >= 1, --i)

hmax[i] < m

kmin[hmax[i]] = i

TRUE

Selesai

kmin[hmax[i]] = 0FALSE

Gambar 3.11 Flowchart menentukan fungsi kmin


Mulai

s := -1

r := m

for (i = 0

i < m

++i)

kmin[i] = 0 h[++s] := iFALSE

h[--r] := i

TRUE

Selesai

Gambar 3.12 Flowchart menentukan h


Mulai

for i := 0,

i <= nd,

i++)

shift[i] := kmin[i[h]]

for (i :=

nd + 1, i

< m, ++i)

shift[i] := rmin[0]

shift[m] := rmin[0]

Selesai

Gambar 3.13 Flowchart perhitungan shift


Mulai

i = k = 1

x[i] == x[i - k]

i++

hmax[k] = i

q = k + 1

k <= m

j = k

k == j + j

q++

hmax[q > k] + k < j

hmax[q] = hmax [q > k] + kk > qFALSE

Selesai

FALSE

FALSE

TRUE

A

A

Gambar 3.14 Flowchart menentukan hmax


Mulai

for (i = m – 1,

i >= 0, --i)

hmax[i + 1] == m

r = i + 1

TRUE

kmin[i] == 0

rmin[i] = r

TRUE

Selesai

rmin[i] = 0FALSE

FALSE

Gambar 3.15 Flowchart menentukan rmin


3.5.3 Flowchart Algoritma Simon

Mulai

pattern, text,

x = split pattern,

y = split text

m = jumlah x

n = jumlah y

i = 0

i < mlist [i] = null

i++TRUE ell = -1FALSE i < m

k = ell

cell = list [k]

ell = -1

TRUE

x [i] = x [k + i]ell = k+1

i++TRUE

cell [element] = q

cell [next] = list [p]

list [p] = cell

i++

FALSE

j < n, state = -1

FALSE

p < m – 1 && x [p + 1] == c

state = p + 1

TRUE

x(cell[element = c]

xell = [element]

state = -1)

FALSE

result = j – m + 1

state = ell

TRUE

SelesaiFALSE

Gambar 3.16 Flowchart algoritma Simon

3.6 Hasil Analisis Algoritma Colussi dan Algoritma Simon dalam Pencarian

Kata pada Jurnal

Pada tahap analisis dan perancangan sistem diperlukan hasil dari tahapan ini, layak

atau tidaknya algoritma diimplementasikan. Dengan pengamatan penulis yang

mengambil kesimpulan dengan melakukan beberapa tahapan untuk mendapatkan hasil

analisis seperti alasan melakukan analisis, permasalahan yang terjadi jika masih

menggunakan media kertas sebagai sumber informasi dan mengidentifikasi penyebab

masalah tersebut, dengan tahapan-tahapan inilah penulis mendapatkan hasil dari

analisis.


3.6.1 Alasan Melakukan Analisis Sistem

Pada penelitian ini, penulis mencoba untuk menyelesaikan permasalahan yang di

alami oleh pengguna apabila masih mencari informasi dengan cara manual yang

tergolong lama untuk mendapatkan informasi tersebut. Permalahan ini membuat

pengguna menghabiskan cukup banyak waktu untuk mencari informasi, terlebih

apabila pengguna ingin menghemat waktunya untuk keperluannya yang lain.

3.6.2 Permasalahan dalam Mencari Informasi Secara Manual

Pada tahapan analisis kebutuhan telah diberikan penjelasan bahwa dibutuhkan solusi

untuk menyelesaikan masalah-masalah dibawah ini:

a. Pengguna harus menyisihkan banyak waktu apabila menggunakan media kertas

untuk mencari informasi.

b. Pengguna harus lebih teliti dan perlahan-lahan dalam membaca untuk

mendapatkan informasi.

3.6.3 Identifikasi Penyebab Masalah

Penyebab masalah menjadi alasan penulis untuk mengidentifikasi masalah yaitu:

a. Media cetak seperti buku, majalah, dan jurnal menjadi penyebab pengguna

menghabiskan cukup banyak waktu.

b. Waktu yang seharusnya dapat dipergunakan untuk keperluan yang lain digunakan

untuk menambah waktu mencari informasi dengan media cetak.

c. Untuk mendapatkan informasi pengguna harus membaca secara perlahan pada

media cetak.

3.6.4 Hasil Analisis

Berdasarkan pengamatan penulis yang melakukan beberapa tahapan untuk

mendapatkan hasil analisis bahwa algoritma Colussi dan algoritma Simon dapat

digunakan untuk mencari kata pada dokumen jurnal berekstensi .pdf yang dapat

dimanfaatkan untuk mencari informasi secara cepat dan akurat.


BAB 4

IMPLEMENTASI SISTEM DAN PENGUJIAN

4.1 Implementasi Pencarian Kata dengan Algoritma Colussi

Pada tahap implementasi, diperlukan analisis yang benar untuk mendapatkan hasil

yang tepat. Algoritma Colussi diharapkan dapat di implementasikan untuk proses

pencarian kata pada dokumen jurnal. Diberikan pola dan string untuk tahap analisis

agar pengujian nantinya dapat sesuai dengan yang diharapkan, dengan pola

merupakan kata yang di input oleh pengguna, sedangkan string merupakan teks yang

ada pada dokumen jurnal. Untuk mengetahui tahap pre-processing diperlihatkan pada

tabel 4.1

Pola: p u t e r

String: k o m p u t e r

Tabel 4.1 Tahap preprocessing algoritma Colussi

i 0 1 2 3 4 5

x[i] P U T E R

kmin[i] 0 1 2 3 3

h[i] 1 2 3 4 0

next[i] 0 0 0 0 0

shift[i] 1 2 3 4 5 5

hmax[i] 0 1 2 3 4 5

rmin[i] 5 0 0 0 0

ndh0[i] 0 0 1 2 3

Tabel 4.2 Inisialisasi algoritma Colussi tahap pertama

0 = p 1 = u 2 = t 3 = e 4 = r

1 = u 2 = t 3 = e 4 =r 0 = p


Setelah dilakukan tahapan perubahan inisialisasi pada tabel 4.2, yaitu dengan

mengubah indeks 0 yang berisi “p” menjadi indeks 1 berisi “u” adalah tahapan

selanjutnya untuk proses pencarian dengan bergeser ke indeks selanjutnya untuk

mencari string yang tepat.

Tabel 4.3 yaitu merupakan inisialisasi tahapan kedua untuk merubah indeks

pada tabel 4.2 menjadi indeks 0 = “u” dan menambah indeks kosong agar dapat

dilakukan pergeseran ke indeks berikutnya.

Tabel 4.3 Inisialisasi algoritma Colussi tahap kedua

0 = u 1 = t 2 = e 3 = r 4 = 5 =

0 = u 0 = u 0 = u 0 = u 0 = u 0 = u

Cara kerja pencarian pada algoritma Colussi dilakukan dengan menggunakan

indeks kedua untuk melakukan proses pencarian dengan bergeser ke indeks

selanjutnya, dimana indeks kedua yaitu “u” pada pola “puter” yang mengubah semua

indeks menjadi berisi “u”.

Pada percobaan pencocokan pola terhadap string diberikan ilustrasi sebagai berikut:

Percobaan 1

k o m p u t e r

. u . . . . . .

Percobaan 2

k o m p u t e r

. . u . . . . .


Percobaan 3

k o m p u t e r

. . . u . . . .

Percobaan 4

k o m p u t e r

. . . . u . . .

Percobaan 5

k o m p u t e r

. . . . U . . .

Percobaan 6

k o m p u t e r

. . . . . T . .

Percobaan 7

k o m p u t e r

. . . . . . E .

Percobaan 8

k o m p u t e r

. . . . . . . R

Hasil

k o m p u t e r

. . . P U T E R


4.1.1 Hasil Implementasi dengan Algoritma Colussi

Pada gambar 4.1 yaitu hasil dari perancangan pemilihan dokumen jurnal (.pdf),

dimana pengguna wajib memilih dokumen berekstensi .pdf sebagai langkah awal

untuk pencarian kata yang diinginkan.

Gambar 4.1 Implementasi halaman pemilihan dokumen jurnal

Setelah memilih dokumen, lalu sistem memproses dokumen yang telah di upload dan

sistem hanya akan mengambil tiap-tiap string pada dokumen, selanjutnya sistem akan

menampilkan string tersebut ke interface pengguna. Diperlihatkan pada gambar 4.2.


Gambar 4.2 Implementasi halaman pengambilan string pada jurnal

4.2 Implementasi Pencarian Kata dengan Algoritma Simon

Berbeda dengan cara kerja dari algoritma Colussi, algoritma Simon memiliki cara

tersendiri untuk melakukan proses pencarian string. Dengan cara pada umumnya

adalah menginisialisasi setiap indeks pada pola dan string yang diberikan oleh

pengguna, sama halnya dengan algoritma Colussi, pola merupakan kata yang di input

oleh pengguna, sedangkan string merupakan teks yang ada pada dokumen jurnal.

Pola: p u t e r

String: k o m p u t e r

Pada algoritma Simon, inisialisasi dilakukan dengan pemberian indeks awal adalah -1.

Berikut inisialisasi pada tabel 4.4.

Tabel 4.4 Inisialisasi pada algoritma Simon

State Indeks State Perubahan Indeks Inisialisasi State

-1 p Menjadi → 0

0 p Menjadi → 0 u 1

1 p Menjadi → 0 t 2

2 e Menjadi → 3 p 0


3 p Menjadi → 0 r 4

4

State 4 merupakan proses terminal dari inisialisasi.

Percobaan 1

k o m p u t e r

↑ . . . . . . .

Mismatch (tidak sesuai pola yang diberikan) = -1

Percobaan 2

k o m p u t e r

. ↑ . . . . . .


Percobaan 3

k o m p u t e r

. . ↑ . . . . .


Percobaan 4

k o m p u t e r

. . . ↑ . . . .

Match (sesuai pola yang diberikan) = 0

Percobaan 5

k o m P u t e r

. . . . ↑ . . .



Percobaan 6

k o m P U t e r

. . . . . ↑ . .


Percobaan 7

k o m P U T e r

. . . . . . ↑ .


Percobaan 8

k o m P U T E r

. . . . . . . ↑


Hasil

k o m P U T E R

. . . P U T E R

4.2.1 Hasil Implementasi dengan Algoritma Simon

Halaman pemilihan dokumen pada sistem ini tidak memiliki 2 interface yang berbeda,

algoritma Colussi maupun algoritma Simon sama-sama menggunakan interface yang

sama, terlihat pada gambar 4.3.


Gambar 4.3 Implementasi halaman pemilihan dokumen jurnal

Pada gambar 4.4 implementasi pengambilan string pada dokumen jurnal juga

tidak berbeda dengan gambar 4.2, hanya saja penulis ingin membedakan rujukan

gambar pada algoritma Simon.

Gambar 4.4 Implementasi halaman pengambilan string pada jurnal


4.3 Proses Pengambilan Teks pada Dokumen Jurnal

Tahapan awal pengambilan teks pada dokumen diperlukan untuk memproses

pencarian kata selanjutnya. Setelah teks di ambil pada dokumen berekstensi .pdf, teks

tersebut disimpan ke dalam session array, lalu teks ditampilkan ke interface pengguna

dengan menggunakan session array tersebut.

Pada tahapan pencarian, pengguna meng-input teks yang ingin dicari, lalu

sistem menggunakan session array kembali untuk melakukan pencarian dengan

algoritma Colussi dan algoritma Simon untuk mendapatkan hasil pencarian, kemudian

hasil pencarian ditampilkan ke interface pengguna dan sistem mengurutkan dokumen

yang memiliki teks terbanyak sesuai input yang diberikan oleh pengguna.

Diperlihatkan diagram proses pengambilan teks pada gambar 4.5.

Pilih Dokumen

Proses Dengan Library

PDF2TEXT

Simpan Teks pada

Session Array

Tampilkan Teks ke Interface

Berdasarkan Dokumen

Pencarian dengan Algoritma

Colussi dan Algoritma Simon

Hasil Pencarian

Tampilkan Dokumen yang

Dipilih Berdasarkan Hasil

Terbanyak

Gambar 4.5 Proses pengambilan teks pada dokumen


4.3.1 Pseudocode Pengambilan Teks Dokumen .pdf

<?php

session_start();

include 'PDF2Text.php';

@$arrayLokasiUpload = array();

if (@$_POST['upload']) {

$file_ary = reArrayFiles($_FILES['file']);

$counterfile = 0;

foreach ($file_ary as $file) {

$allowed_ext = array('pdf');

$file_name = strtolower($file['name']);

if (in_array($file_ext, $allowed_ext) === true) {

if ($file_size < 1044070) {

$lokasi = 'files/file' . $file_name;

function reArrayFiles(&$file_post) {

$file_ary = array();

for ($i = 0; $i < $file_count; $i++) {

foreach ($file_keys as $key) {

$file_ary[$i][$key] = $file_post[$key][$i];

}

}

return $file_ary;

}

$count = 1;

$arrayIsiTeks = array();

foreach ($arrayLokasiUpload as $key => $value) {

$a->setFilename($value);

$a->decodePDF();

$arrayIsiTeks[] = $a->output();

}

echo count($arrayIsiTeks);

$_SESSION['nama_file'] = $nama_file;

$_SESSION['teks'] = $arrayIsiTeks;

?>


4.3.2 Pseudocode Library PDF To Text

<?php

function decodePDF() {

$infile = @file_get_contents($this->filename, FILE_BINARY);

if (empty($infile))

return "";

$transformations = array();

$texts = array();

$objects = @$objects[1];

for ($i = 0; $i < count($objects); $i++) {

$currentObject = $objects[$i];

if

(preg_match("#stream[\n|\r](.*)endstream[\n|\r]#ismU

",

$currentObject, $stream)) {

$stream = ltrim($stream[1]);

$options = $this->getObjectOptions($currentObject);

if (!(empty($options["Length1"])

&&

empty($options["Type"])

&& empty($options["Subtype"])))

continue;

unset($options["Length"]);

$data = $this->getDecodedStream($stream, $options);

if (strlen($data)) {

if (preg_match_all("#BT[\n|\r](.*)ET[\n|\r]#ismU",

$data,

$textContainers)) {

$textContainers = @$textContainers[1];

$this->getDirtyTexts($texts, $textContainers);

} else

$this->getCharTransformations($transformations,

$data);

}

}

}

$this->decodedtext = $this->getTextUsingTransformations($texts,

$transformations);

}

?>


4.3.3 Pseudocode Session Array

<?php

error_reporting(0);

$pattern = $_POST['pattern'];

session_start();

$arrayTeks = $_SESSION['teks'];

$nama_file = $_SESSION['nama_file'];

function urutkan($a, $b) {

if ($a['jumlah_colussi'] == $b['jumlah_colussi']) {

return 0;

}

return ($a['jumlah_colussi'] < $b['jumlah_colussi']) ? 1 :

-1;

}

@$nama_file = $_SESSION['nama_file'];

$count = 1;

foreach ($arrayTeks as $key => $value) {

$simonStart = microtime(true);

$hasilposisiSimon = simonFindAll($pattern, strtolower($value));

$simonEnd = microtime(true);

$waktuSimon = $simonEnd - $simonStart;

$colussiStart = microtime(true);

$hasilposisiColussi = colussiFindAll($pattern,

strtolower($value));

$colussiEnd = microtime(true);

$waktuColussi = $colussiEnd - $colussiStart;

$hasil[] = array("id" => $key,

"teks" => $value,

"nama_file" => $nama_file[$key],

"waktu_simon" => $waktuSimon,

"waktu_colussi" => $waktuColussi,

"hasil_posisi_colussi" => $hasilposisiColussi,

"hasil_posisi_simon" => $hasilposisiSimon,

"jumlah_colussi" => count($hasilposisiColussi),

"jumlah_simon" => count($hasilposisiSimon));

}

4.4 Analisis Data dan Pengujian Algoritma Colussi dan Algoritma Simon

Analisis data sangat penting untuk menjalankan sistem ini, karena data merupakan

input yang dibutuhkan untuk mengeluarkan output yaitu berupa kata yang sesuai


dengan yang diinginkan atau dicari oleh pengguna. Data yang digunakan adalah

dokumen jurnal Al-Khawarizmi S1 Ilmu Komputer USU yang umumnya berekstensi

.pdf pada situs online http://jurnal.usu.ac.id/index.php/alkhawarizmi yang dapat

diakses secara bebas, akan tetapi dokumen yang dapat dibaca oleh sistem hanya 9

dokumen jurnal. Untuk penjelasan lebih lengkap, penulis melakukan pengambilan

data sebagai salah satu kebutuhan untuk penelitian pada tabel 4.5 sebagai berikut.

Tabel 4.5 Data jurnal

No. Judul Jurnal Pengarang Tahun Terbit Bahasa Konsentrasi

1 Perancangan

Error

Detection

System and

Error

Correction

System

Menggunakan

Metode

Hamming

Code pada

Pengiriman

Data Text.

Ahmad Alfi

Albar Lubis, Dr.

Poltak

Sihombing,

M.Kom dan Ir.

Arman Sani,

M.T.

2012 Indonesia Kecerdasan

Buatan

2 Sistem

Perpakiran

Secara Visual

Map Berbasis

Local Area

Network.

Alpiriyandi, Dr.

Poltak

Sihombing,

M.Kom dan Drs.

Dahlan

Sitompul,

M.Eng.

2012 Indonesia Jaringan


http://jurnal.usu.ac.id/index.php/alkhawarizmi

3 Analisis dan

Implementasi

Kompresi File

Audio dengan

Menggunakan

Algoritma

Run Length

Encoding.

Aditya Rahandi,

Dian

Rachmawati,

S.Si., M.Kom

dan Sajadin

Sembiring, S.Si.,

M.Comp.Sc.

2012 Indonesia Kompresi

4 Perbandingan

Algoritma

Arithmetic

dengan

Geometric

Mean Filter

untuk Reduksi

Noise pada

Citra,

Wili Yana, Drs.

Marihat

Situmorang,

M.Kom dan Drs.

James Piter

Marbun,

M.Kom.

2012 Indonesia Pengolahan

Citra

5 Implementasi

Sistem

Keamanan

Data dengan

Menggunakan

Teknik

Steganografi

End of File

(EOF) dan

Rabin Public

Key

Cryptosystem.

Henny

Wandayani,

Muhammad

Andri Budiman,

S.T.,

M.Comp.Sc.,

M.E.M dan

Amer Sharif,

S.Si., M.Kom.

2012 Indonesia Kriptografi


6 Analisis dan

Perancangan

Perangkat

Lunak

Kompresi

Citra

Menggunakan

Algoritma

Fast Fourier

Transform

(FTT)

Rima Lestari,

Drs. Marihat

Situmorang,

M.Kom dan

Maya Silvi

Lidya, B.Sc.,

M.Sc


7 Implementasi

Kompresi

Teks

Menggunakan

Metode

Huffman

untuk

Menghemat

Karakter pada

Short Message

Service

Evi Mariani

Harahap, Dian

Rachmawati,

S.Si., M.Kom

dan Herriyance,

S.T., M.Kom


8 Implementasi

Perbandingan

Firewall

Security

Menggunakan

Mikrotik dan

M0n0wall

Hendra H.

Sinaga, Prof. Dr.

Opim Salim

Stiompul dan M.

Umar Salet,

S.T., M.T

2012 Indonesia Jaringan


Pada Local

Area Network

9 Pengolahan

File dan

Pedektesian

File yang

Dicurigai

Adanya Virus

dengan

Metode Mime

Type

Emilia Santi

Flora Ginting,

Dr. Poltak

Sihombing,

M.Kom dan Drs.

Agus Salim

Harahap, M.Si

2012 Indonesia Keamanan

Data

10 Perancangan

Aplikasi

Pengisian

Pulsa dengan

Java Mobile

Ummi Fauziyah,

Dr. Poltak

Sihombing,

M.Kom dan

Handrizal, S.Si.,

M.Comp.Sc

2012 Indonesia Pemrograma

n Mobile

Setelah pengguna diberikan tampilan yang berisi teks pada dokumen, lalu pengguna

juga harus meng-input kata yang ingin dicari. Sebagai contoh pengguna memberikan

input-an kata yaitu: “algoritma”, lalu sistem akan memulai proses pencarian dengan

algoritma Colussi maupun dengan algoritma Simon. Diperlihatkan pada gambar 4.6.


Gambar 4.6 Hasil pencarian dengan algoritma Colussi dan algoritma Simon

Didapatkan hasil dari pencarian kata “algoritma” yaitu untuk algoritma Colussi

membutuhkan waktu 0,09878 ms dan algoritma Simon 0,17638 ms.

Untuk memperjelas hasil pengujian diberikan beberapa contoh kata yang di

uji. Pada tabel 4.6, penulis memberikan contoh dengan satu kata dalam pengujian.

Tabel 4.6 Contoh satu kata dalam pengujian

No. Kata

1 Citra

2 Data

3 Proses

4 Analisis

5 Informasi


Diperlihatkan pada gambar 4.7 untuk membuktikan hasil pengujian dalam mencari

kata “dan”

Gambar 4.7 Pengujian kata “citra”

Pada gambar 4.8 dibuktikan hasil pengujian dalam mencari kata “data”

Gambar 4.8 Pengujian kata “data”


Gambar 4.9 diperlihatkan untuk membuktikan hasil pengujian dalam kata “proses”.

Gambar 4.9 Pengujian kata “proses”

Gambar 4.10 membuktikan hasil pengujian dalam mencari kata “analisis”

Gambar 4.10 Pengujian kata “analisis”


Untuk membuktikan hasil pengujian dalam mencari kata “informasi” diperjelas pada

gambar 4.11.

Gambar 4.11 Pengujian kata “informasi”

Berdasarkan hasil pengujian didapatkan hasil pencarian dan waktu proses pada

algoritma Colussi dan algoritma Simon pada tabel 4.7

Tabel 4.7 Analisis hasil pencarian dan waktu proses algoritma Colussi dan

Simon satu kata

No. Kata Jumlah Kata

Ditemukan

Waktu Algoritma

Colussi

Waktu Algoritma

Simon

1 Citra 136 0,12106 ms 0,26063 ms

2 Data 101 0,07873 ms 0,12742 ms

3 Proses 34 0,05325 ms 0,08686 ms

4 Analisis 14 0,12972 ms 0,27027 ms

5 Informasi 21 0,11549 ms 0,25053 ms

Rata-rata 0,49825 ms 0,99571 ms


Gambar 4.12 Grafik hasil waktu proses satu kata dengan algoritma Colussi dan

algoritma Simon

Pada gambar 4.12 yaitu grafik hasil waktu proses satu kata dengan algoritma

Colussi diberikan tanda garis berwarna biru dan untuk algoritma Simon berwarna

merah. Pada sumbu x yaitu garis bilangan yang posisinya horisontal menyatakan kata

yang di uji, sedangkan sumbu y adalah garis bilangan yang posisinya tegak atau

vertikal merupakan waktu yang dibutuhkan algoritma Colussi dan algoritma Simon

melakukan pencarian kata.

Berdasarkan grafik diatas, untuk hasil pencarian dan waktu proses dengan

algoritma Colussi, semakin banyak karakter yang di input semakin banyak waktu yang

dibutuhkan algoritma Colussi untuk pencarian, tetapi jumlah teks yang cocok juga

mempengaruhi waktu proses pencarian. Untuk algoritma Simon, semakin banyak teks

yang cocok pada dokumen, akan semakin banyak waktu yang diperlukan oleh

algoritma Simon dalam proses pencarian.

Pada tabel 4.8, penulis memberikan contoh dengan dua kata dalam pengujian

untuk kebutuhan dalam penelitian dan pengujian. Kata yang diberikan penulis

0

0,05

0,1

0,15

0,2

0,25

0,3

0 1 2 3 4 5 6

Colussi

Simon


bersinggungan dengan isi jurnal Alkhawarizimi yaitu jurnal Program Studi S1 Ilmu

Komputer Universitas Sumatera Utara.

Tabel 4.8 Contoh dua kata dalam pengujian

No. Kata

1. Perangkat lunak

2. Perancangan sistem

3. Ilmu komputer

4. Perbandingan hasil

5. Penelitian ini

Pada gambar 4.13 diperlihatkan hasil pengujian dari kata “perangkat lunak”

dengan jumlah kata yang terbanyak berada di dokumen pertama sesuai pengurutan

memiliki jumlah kata ditemukan yaitu 7 kata dengan waktu proses pada algoritma

Colussi 0,06083 ms dan waktu proses algoritma Simon 0,10191 ms.

Gambar 4.13 Pengujian kata “perangkat lunak”


Gambar 4.14 dengan pengujian kata “perancangan sistem” mendapatkan hasil

dengan jumlah kata yang ditemukan adalah 2 kata dengan waktu proses masing-

masing algoritma Colussi 0,11794 ms dan Simon 0,24188 ms.

Gambar 4.14 Pengujian kata “perancangan sistem”

Pengujian “ilmu komputer” pada gambar 4.15 diperlihatkan hasilnya sebagai berikut

Gambar 4.15 Pengujian kata “ilmu komputer”


Pada gambar 4.16 dengan pengujian “perbandingan hasil” diperlihatkan pengujian

sebagai berikut

Gambar 4.16 Pengujian kata “perbandingan hasil”

Pengujian kata “penelitian ini” diperlihatkan pada gambar 4.17

Gambar 4.17 Pengujian kata “penelitian ini”


Dengan hasil pengujian dengan dua kata didapatkan hasil pencarian dan waktu proses

pada algoritma Colussi dan algoritma Simon pada tabel 4.9

Tabel 4.9 Analisis hasil pencarian dan waktu proses algoritma Colussi dan

Simon dengan dua kata.

No. Kata Jumlah Kata

ditemukan

Waktu Algoritma

Colussi

Waktu Algoritma

Simon

1 Perangkat lunak 7 0,06083 ms 0,10191 ms

2 Perancangan sistem 2 0,11794 ms 0,24188 ms

3 Ilmu komputer 2 0,16054 ms 0,24562 ms

4 Perbandingan hasil 1 0,12420 ms 0,27245 ms

5 Penelitian ini 9 0,11508 ms 0,25920 ms

Rata-rata 0,57849 ms 1,12106 ms

Diperlihatkan grafik untuk hasil dari waktu proses pencarian kata pada gambar 4.17

Gambar 4.18 Grafik hasil waktu proses dua kata dengan algoritma Colussi dan

algoritma Simon

0

0,05

0,1

0,15

0,2

0,25

0,3

0 1 2 3 4 5 6

Colussi

Simon


Pada gambar 4.18 yaitu grafik hasil waktu proses dua kata dengan algoritma Colussi

diberikan tanda garis berwarna biru dan untuk algoritma Simon berwarna merah. Pada

sumbu x yaitu garis bilangan yang posisinya horizontal menyatakan kata yang di uji,

sedangkan sumbu y adalah garis bilangan yang posisinya tegak atau vertikal

merupakan waktu yang dibutuhkan algoritma Colussi dan algoritma Simon melakukan

pencarian kata.

Berdasarkan gambar 4.18 semakin banyak karakter yang di input semakin

banyak waktu yang dibutuhkan algoritma Colussi untuk pencarian, tetapi jumlah teks

yang cocok juga mempengaruhi waktu proses pencarian. Untuk algoritma Simon,

semakin banyak teks yang cocok pada dokumen, akan semakin banyak waktu yang

diperlukan oleh algoritma Simon dalam proses pencarian.

4.4.1 Kompleksitas Algoritma Colussi

Kompleksitas waktu yang digunakan untuk algoritma Colussi adalah notasi Big-O(n)

yaitu notasi asimtotik linear dapat dilihat pada tabel 4.10.

Tabel 4.10 Kompleksitas algoritma Colussi waktu dengan big-O(n)

PHP Code C # C# function colussiFindAll($pattern, $source) { C1 1 C1 $ptrn = str_split($pattern); C2 1 C2 $y = str_split($source); C3 1 C3 $x = str_split($pattern); C4 1 C4 array_push($x, null); C5 2 2C5 $m = count($ptrn); C6 1 C6 $n = count($y); C7 1 C7 for ($i1 = 0; $i1 < $m + 1; $i1++) { C8 n n(C8) $h[$i1] = 0; C9 n n(C9) $next[$i1] = 0; C10 n n(C10) $shift[$i1] = 0;

} C11 n n(C11)

/* Processing */

$nd = preColussi($x, $h, $next, $shift); C12 n n(C12)

/* Searching */

$i = $j = 0; C8 4 4(C8)

$last = -1; C13 2 2(C13) $result = array(); C5 1 C5 while ($j <= $n - $m) { C14 n n(C14)


while ($i < $m && $last < $j + $h[$i] &&

$x[$h[$i]] == $y[$j + $h[$i]]) { C14 n n(C14)

$i++;

} C8 n n(C8)

if ($i >= $m || $last >= $j + $h[$i]) { C15 n n(C15) array_push($result, $j); C5 n n(C5) $i = $m;

} C8 n n(C8)

if ($i > $nd) { C15 n n(C15) $last = $j + $m - 1;

} C13 n n(C13)

$j+= $shift[$i]; C16 n n(C16) $i = $next[$i];

} C8 n n(C8)

return $result;

} C17 n n(C17)

O(n)

4.4.2 Kompleksitas Algoritma Simon

Kompleksitas waktu yang digunakan untuk algoritma Simon adalah notasi Big-O(n)

yaitu notasi asimtotik linear dapat dilihat pada tabel 4.11.

Tabel 4.11 Kompleksitas waktu algoritma Simon dengan big-O(n)

PHP Code C # C# function simonFindAll($pattern, $source) { C1 1 C1 $x = str_split($pattern); C2 1 C2 $y = str_split($source); C3 1 C3 $m = count($x); C4 1 C4 $n = count($y); C5 1 C5 for ($i = 0; $i < count($x); $i++) { C6 n nC6 $list[$i] = null;

} C7 n nC7

$ell = preSimon($x, @$list); C8 1 C8 $result = array(); C9 1 C9 for ($state = -1, $j = 0; $j < $n; ++$j) { C6 n nC6 $state = getTransition($x, $state, $list,

$y[$j]); C10 n nC10

if ($state >= $m - 1) { C11 n nC11 array_push($result, $j - $m + 1); C12 n nC12 $state = $ell;

}

}

C10 n nC10

return $result;

} C13 1 C13

O(n)


BAB 5

PENUTUP

5.1 Kesimpulan

Berdasarkan pengamatan dari analisis dan perancangan sistem penulis mendapat hasil

yaitu:

1. Algoritma Colussi maupun algoritma Simon dapat di implementasikan sebagai

cara untuk mencari kata dengan tepat.

2. Algoritma Colussi memiliki beberapa tahap sebelum pemrosesan yaitu dengan

menggunakan fungsi x[i], kmin[i], h[i], next[i], shift[i], hmax[i], rmin[i] dan juga

ndh0[i] sedangkan algoritma Simon hanya menggunakan inisialisasi untuk

memberikan indeks pada tiap pola dan inisialisasi setiap state pada pola

3. Untuk kompleksitas waktu pada algoritma Colussi dan algoritma Simon dengan

kompleksitas ukuran big-O(n).

4. Hasil waktu proses dari algoritma Colussi lebih cepat dengan hasil rata-rata

0,2848 ms dibanding algoritma Simon dengan waktu proses adalah 0,9005 ms.

5.2 Saran

Untuk penelitian selanjutnya penulis mengharapkan beberapa pengembangan yaitu:

1. Penambahan algoritma string matching diharapkan dapat diterapkan untuk

pencarian kata dalam dokumen jurnal berekstensi .pdf agar nantinya dapat

diketahui algoritma string matching mana yang paling cepat dalam waktu

pencarian.

2. Dalam hal pengembangan perangkat lunak, diharapkan dapat digunakan disemua

platform dan memiliki user interface yang baik agar memudahkan pengguna

menggunakan sistem pencarian kata pada jurnal.


DAFTAR PUSTAKA

Charras, C. & Lecroq, T. 1997. Exact String Matching Algorithms. Universite de

Rouen. France.

Hajar, T.I. 2015. Implementasi algoritma Levenshtein Distance dan Boyer Moore

untuk fitur autocomplete dan autorcorrect pada aplikasi katalog perpustakaan

daerah Aceh Timur. Skripsi. Universitas Sumatera Utara.

Hariyanto, B. 2008. Dasar Informatika & Ilmu Komputer. Graha Ilmu: Yogyakarta.

Haviluddin. 2011. Memahami Penggunaan UML (Unified Modeling Language).

Jurnal Informatika Mulawarman, 6(1): 1-15. (Online)

https://informatikamulawarman.files.wordpress.com/2011/10/01-jurnal

informatika-mulawarman-feb-2011.pdf (14 Desember 2015).

Jogiyanto. 2005. Analisis & Desain Sistem Informasi Pendekatan Terstruktur Teori

dan Praktek Aplikasi Bisnis. Penerbit ANDI: Yogyakarta.

Kadir, A. 2013. From Zero to a Pro – Javascript & JQuery. Penerbit ANDI:

Yogyakarta.

Levitin, A. 2010. Pengantar Desain dan Analisis Algoritma. Penerbit Salembo Infotek:

Jakarta.

Nababan, A.A. 2015. Implementasi algoritma Brute Force dan algoritma Knuth-

Morris-Pratt (KMP) dalam pencarian word suggestion. Skripsi. Universitas

Sumatera Utara.

Nasution, A.B. 2015. Sistem pencarian kata pada media massa online

menggunakan algoritma Rabin-Karp. Skripsi. Universitas Sumatera Utara.

Ramadhani, C. 2015.Dasar Algoritma dan Struktur Data dengan Bahasa Java.

Penerbit ANDI: Yogyakarta.

Sagita, V. & Prasetiyowati, M.I. 2013. Studi Perbandingan Implementasi Algoritma

Boyer-Moore, Turbo Boyer-Moore, dan Tuned Boyer-Moore dalam

Pencarian String. Jurnal ULTIMATICS, Vol. IV (1). (Online

http://library.umn.ac.id/jurnal/public/uploads/papers/pdf/81979372227d0a5e23

0a9c2afde78f68.pdf (3 Maret 2016)


https://informatikamulawarman.files.wordpress.com/2011/10/01-jurnalinformatika-mulawarman-feb-2011.pdf%20(14

https://informatikamulawarman.files.wordpress.com/2011/10/01-jurnalinformatika-mulawarman-feb-2011.pdf%20(14

http://library.umn.ac.id/jurnal/

Shelly, G. B & Rosenblatt, H. J. 2011. Systems Analysis And Design. Course

Technology: Boston.

Siswanto. 2010. Algoritma & Struktur Data Linear Dengan Java. Graha Ilmu:

Yogyakarta.

Sutabri, T. 2013. Komputer dan Masyarakat. Penerbit ANDI: Yogyakarta

Whitten, J. L., Bentley, L. D & Dittman, K. C. 2004. Metode Desain dan Analisis

Sistem. Penerbit ANDI: Yogyakarta


LISTING PROGRAM

index.php

<?php

?>

<!DOCTYPE html >

<html>

<head>

<title>Colussi dan Simon </title>

<meta http-equiv="Content-Type" content="text/html;

charset=iso-8859-1" />

<link rel="stylesheet" href="images/SimpleBlog.css"

type="text/css" />

</head>

<body>

<div id="wrap">

<?php include 'inc/nav.php'; ?>

<div id="content-wrap">

<div id="main">

<br></br><br></br><br></br><br></br><br></br>

Sistem ini memungkinkan Anda untuk mencari informasi yang ingin

dicari dengan mudah dan cepat. Quick & Easy!



</div>

</div>

<?php include 'inc/footer.php'; ?>

</div>

</body>

</html>

tentang.php <?php

?>

<!DOCTYPE html >

<html >

<head>

<title>Colussi dan Simon</title>

<meta http-equiv="Content-Type" content="text/html;

charset=iso-8859-1" />

<link rel="stylesheet"

href="images/SimpleBlog.css" type="text/css" />

A-1


</head>

<body>

<div id="wrap">



<div id="main">


Sistem ini dibangun oleh penulis untuk membantu pengguna

menyelesaikan permasalahan dalam mencari informasi dengan waktu

yang singkat dan tepat.Faces your time so easily.


<br></br><br></br><br></br><br></br><br>

</div>

</div>


</div>

</body>

</html>

pilih_file.php

<?php

session_start();

session_destroy();

?>

<!DOCTYPE html >

<html >

<head>



type="text/css" />

</head>

<body>

<div id="wrap">



<div id="main">

<form action="baca_file.php"

method="post" enctype="multipart/form-data">

<table >

<?php

$jumlahFile = 5;

A-2


for ($i = 0; $i < $jumlahFile; $i++) {

?>

<tr><td>

<b>Silahkan pilih dokumen jurnal berekstensi (.pdf) <?php echo

$i + 1; ?></b></td><td><b>:</b></td><td><input type="file"

name="file[]" required /></td></tr>

<?php } ?>

<tr><td> </td><td> </td><td><input type="submit"

name="upload" value="Upload" /></td></tr>

</table>

</form>

<br></br><br></br><br></br><br></br>

<br></br><br></br><br></br>

</div>

</div>


</div>

</body>

</html>

search.php

<?php

error_reporting(0);

$pattern = $_POST['pattern'];

session_start();

$arrayTeks = $_SESSION['teks'];

$nama_file = $_SESSION['nama_file'];

function urutkan($a, $b) {

if ($a['jumlah_colussi'] == $b['jumlah_colussi']) {

return 0;

}

return ($a['jumlah_colussi'] < $b['jumlah_colussi']) ? 1 :

-1;

}

?>

<!DOCTYPE html >

<html >

<head>



type="text/css" />

A-3


</head>

<body>

<div id="wrap">



<div id="main">

<?php

$count = 1;

foreach ($arrayTeks AS $key => $value) {

?>

<div><h3><br/><?php echo $nama_file[$key]; ?></h3></div>

<div>

<textarea style="width: 100%; height: 300px;;" ><?php

echo $value;

?>

</textarea>

</div>

<?php

}

?>

<br/>

<h3>Pencarian</h3>

<div style="background-color: lightblue; width: 100%; padding:

5px;">

<form action="" method="POST">

Cari Kata:<input type="text" name="pattern" style="width :100%;

padding: 3px;" placeholder="Masukkan kata yang dicari di sini"

value="<?php echo @$pattern; ?>"/><br/><br/>

<input type="submit" name="operasi" value="Cari" style="width:

100px; height: 40px;"/>

</form>

</div>

<?php

@$operasi = strtolower($_POST['operasi']);

if ($operasi == "cari") {

include 'colussi.php';

include 'Simon.php';

?>

<style>

th{

padding: 3px;

font-size: large;

}

td{

padding: 5px;

}

A-4


</style>

<?php

@$nama_file = $_SESSION['nama_file'];

$count = 1;

foreach ($arrayTeks as $key => $value) {

$simonStart = microtime(true);

$hasilposisiSimon = simonFindAll($pattern,


$simonEnd = microtime(true);

$waktuSimon = $simonEnd - $simonStart;

$colussiStart = microtime(true);

$hasilposisiColussi = colussiFindAll($pattern,


$colussiEnd = microtime(true);

$waktuColussi = $colussiEnd - $colussiStart;

$hasil[] = array("id" => $key, "teks" => $value, "nama_file" =>

$nama_file[$key], "waktu_simon" => $waktuSimon, "waktu_colussi"

=> $waktuColussi, "hasil_posisi_colussi" =>

$hasilposisiColussi, "hasil_posisi_simon" => $hasilposisiSimon,

"jumlah_colussi" => count($hasilposisiColussi), "jumlah_simon"

=> count($hasilposisiSimon));

}

?>

<table border="1" style="padding: 3px;">

<thead>

<th colspan="2"></th>

<th>Simon</th>

<th>Colussi</th>

</thead>

<?php

uasort($hasil, 'urutkan');

$_SESSION['hasil_cari'] = $hasil;

foreach ($hasil as $key => $value) {

?>

<tr>

<td><a href="selengkapnya.php?pattern=

<?php echo $pattern;

?>&id=<?php echo $value['id'] ?>">

<?php echo $value['nama_file']; ?></a></td>

<td>Waktu Proses (ms)</td>

<td><?php echo $value['waktu_simon']; ?></td>

<td><?php echo $value['waktu_colussi']; ?></td>

</tr>

A-5


<tr>

<td></td>

<td>Jumlah Kata Ditemukan</td>

<td><?php echo $value['jumlah_colussi']; ?></td>

<td><?php echo $value['jumlah_simon']; ?></td>

</tr>

<?php

}

}

?>

</table>

</div>

</div>


</div>

</body>

</html>

colussi.php

<?php

main();

function main() {

}

$h = array();

$next = array();

$shift = array();

$x = array();

function preColussi($x, &$h, &$next, &$shift) {

$r = 0;

$m = count($x) - 1;

for ($i = 0; $i < count($x); $i++) {

$hmax[$i] = 0;

$kmin[$i] = 0;

$nhd0[$i] = 0;

$rmin[$i] = 0;

}

/* Computation of hmax */

A-6


$i = $k = 1;

do {

while ($x[$i] == $x[$i - $k]) {

$i++;

}

$hmax[$k] = $i;

$q = $k + 1;

while ($hmax[$q - $k] + $k < $i) {

$hmax[$q] = $hmax[$q - $k] + $k;

$q++;

}

$k = $q;

if ($k == $i + 1) {

$i = $k;

}

} while ($k <= $m);

/* Computation of kmin */

for ($i = 0; $i < $m; $i++) {

$kmin[$i] = 0;

}

for ($i = $m; $i >= 1; --$i) {

if ($hmax[$i] < $m) {

$kmin[$hmax[$i]] = $i;

}

}

/* Computation of rmin */

for ($i = $m - 1; $i >= 0; --$i) {

if ($hmax[$i + 1] == $m) {

$r = $i + 1;

}

if ($kmin[$i] == 0) {

$rmin[$i] = $r;

} else {

$rmin[$i] = 0;

}

}

/* Computation of h */

$s = -1;

$r = $m;

for ($i = 0; $i < $m; ++$i) {

if ($kmin[$i] == 0) {

$h[--$r] = $i;

} else {

$h[++$s] = $i;

A-7


}

}

$nd = $s;

/* Computation of shift */

for ($i = 0; $i <= $nd; ++$i) {

$shift[$i] = $kmin[$h[$i]];

}

for ($i = $nd + 1; $i < $m; ++$i) {

$shift[$i] = $rmin[$h[$i]];

}

$shift[$m] = $rmin[0];

/* Computation of nhd0 */

$s = 0;

for ($i = 0; $i < $m; ++$i) {

$nhd0[$i] = $s;

if ($kmin[$i] > 0) {

++$s;

}

}

/* Computation of next */

for ($i = 0; $i <= $nd; ++$i) {

$next[$i] = $nhd0[$h[$i] - $kmin[$h[$i]]];

}

for ($i = $nd + 1; $i < $m; ++$i) {

$next[$i] = $nhd0[$m - $rmin[$h[$i]]];

}

$next[$m] = $nhd0[$m - $rmin[$h[$m - 1]]];

return ($nd);

}

function colussiFindAll($pattern, $source) {

$ptrn = str_split($pattern);

$y = str_split($source);

$x = str_split($pattern);

array_push($x, null);

$m = count($ptrn);

$n = count($y);

A-8


/* Processing */

$nd = preColussi($x, $h, $next, $shift);

/* Searching */

$i = $j = 0;

$last = -1;

while ($i < $m && $last < $j + $h[$i] && $x[$h[$i]] ==

$y[$j + $h[$i]]) {

$i++;

}

if ($i >= $m || $last >= $j + $h[$i]) {

array_push($result, $j);

$i = $m;

}

if ($i > $nd) {

$last = $j + $m - 1;

}

$j+= $shift[$i];

$i = $next[$i];

}

return $result;

}

?>

simon.php

<?php

@$cell['elemet'];

@$cell['next'];

function preSimon($x, $list) {

$m = count($x);

for ($i = 0; $i < $m - 2; $i++) {

$list[$i] = Null;

}

$ell = -1;

for ($i = 1; $i < $m; ++$i) {

A-9


$k = $ell;

$cell = ($ell == -1 ? null : $list[$k]);

$ell = -1;

if ($x[$i] == $x[$k + 1]) {

$ell = $k + 1;

} else {

setTransition($i - 1, $k + 1, $list);

}

while ($cell != null) {

$k = $cell . $element;

if ($x[$i] == $x[$k]) {

$ell = $k;

} else {

setTransition($i - 1, $k, $list);

}

$cell = $cell['next'];

}

}

return $ell;

}

function setTransition($p, $q, $list) {

$cell['element'] = $q;

$cell['next'] = $list[$p];

$list[$p] = $cell;

}

function simonFindAll($pattern, $source) {

$x = str_split($pattern);

$y = str_split($source);

$m = count($x);

$n = count($y);

for ($i = 0; $i < count($x); $i++) {

$list[$i] = null;

}

$result = array();

for ($state = -1, $j = 0; $j < $n; ++$j) {

$state = getTransition($x, $state, $list, $y[$j]);

if ($state >= $m - 1) {

array_push($result, $j - $m + 1);

$state = $ell;

}

}

A-10


return $result;

}

function getTransition($x, $p, $lst, $c) {

$m = count($x);

return ($p + 1);

} else if ($p > -1) {

$cell = $lst[$p];

while ($cell != null) {

if ($x[$cell['element']] == $c) {

return ($cell['element']);

} else {

$cell = $cell['next'];

}

}

return (-1);

} else {

return (-1);

}

}

?>

selengkapnya.php

<?php

session_start();

$pattern = $_GET['pattern'];

$id = $_GET['id'];

function Bold($teks, $pattern) {

$pattern = "/" . $pattern . "/i";

$replacePattern = "<b style='color:blue;'>$0</b>";

return preg_replace($pattern, $replacePattern, $teks);

}

?>

<!DOCTYPE html >

<html >

<head>

<title>Colussi dan Simon</title>


type="text/css" />

</head>

A-11

A-11


<body>

<div id="wrap">



<div id="main">

<div>

<h3>Hasil Pencarian Untuk Kata "<?php

echo $pattern; ?>"</h3>

<?php

$hasil = $_SESSION['hasil_cari'][$id];

echo Bold($hasil['teks'], $pattern);

?>

</div>

</div>

</div>


</div>

</body>

</html>

A-12


CURRICULUM VITAE

[ D a f t a r R i w a y a t H i d u p ]

Data Pribadi

Nama Iqbal Habibie, A.Md

Tempat / Tgl Lahir Medan / 26 September 1994

Jenis Kelamin Laki-laki

Kewarganegaraan Indonesia

Agama Islam

Alamat Jl. Pelajar No. 117 A Medan

E-mail [email protected]

No HP 08116401124

Alamat Orang Tua Jl. Pelajar No. 117 A Medan

No HP Orang Tua 082161205209

Pendidikan

1999-2005 SD Negeri 064957 Medan

2005-2008 SMP Negeri 3 Medan

2008-2011 SMA Negeri 5 Medan

2011-2014 D-3 Teknik Informatika, Universitas Sumatera Utara

2014-sekarang S1-Ekstensi Ilmu Komputer, Universitas Sumatera Utara

Kemampuan

Pemrograman Web, Java dan Java Android

Database MySQL, MS SQL Server

Bahasa Indonesia, Inggris


mailto:[email protected]

analisis dan perbandingan algoritma colussi dan algoritma

Documents