BAB 2 LANDASAN TEORI
2.1. Pengertian Hadits Menurut pendapat muhaddihin muta’akhirin, di antaranya dikemukakan oleh ibn Salah (w. 643 H/1245 M) dalam muqaddimah-nya. “Hadits shahih adalah hadits yang bersambung sanadnya, diriwayatkan oleh periwayat yang adil dan dabit sampai akhir sanad-nya, tidak terdapat kejanggalan (shadh) dan cacat (‘illah)” (Arifin, 2012).
2.2. Pengertian Aplikasi Istilah aplikasi berasal dari bahasa inggris “application” yang berarti penerapan, lamaran atau penggunaan. Aplikasi adalah penggunaan atau penerapan suatu konsep yang menjadi pokok pembahasan. Aplikasi dapat diartikan juga sebagai program komputer yang dibuat untuk menolong manusia dalam melaksanakan tugas tertentu (Sarumaha, 2013).
2.3. Pengertian Android
Android merupakan sistem operasi untuk mobile device yang awalnya dikembangkan oleh android inc. Perusahaan ini kemudian oleh Google pada tahun 2005. Kemudian untuk mengembangkan Android dibentuklah Open Handset Alliance yang merupakan gabungan dari 34 perusahaan peranti keras, lunak dan telekomunikasi termasuk Google, HTC, Intel, Motorola, Qualcomm, T-mobile dan Nvidia. Android dibuat menggunakan kernel Linux yang dimodifikasi. Aplikasi Android ditulis dengan bahasa Java, menggunakan Java Core Libraries. Aplikasi Android dijalankan di atas VM bernama Dalvik Virtual Machine. Android menyediakan platform terbuka bagi para
Universitas Sumatera Utara
6
pengembang untuk menciptakan aplikasi mereka sendiri sehingga dapat digunakan oleh bermacam peranti penggerak. Pada saat perilisan perdana Android pada tanggal 5 November 2007, Android bersama Open Handset Alliance lalu menyatakan mendukung pengembangan standar terbuka Programming pada perangkat seluler (Sarumaha, 2013). Pada tahun 2007, Google dan beberapa perusahaan yang tergabung dalam Open Handset Alliance (Intel, Nvidia, Texas Instrument) mengembangkan sistem operasi Android dan resmi menjadi open source. Google menginginkan agar Android bersifat terbuka dan gratis, oleh karena itu hampir setiap kode program Android diluncurkan berdasarkan lisensi open-source Apache yang berarti bahwa semua orang yang ingin menggunakan Android dapat men-download penuh source code-nya. Di samping itu produsen perangkat keras juga dapat menambahkan extension-nya sendiri ke dalam Android sesuai kebutuhan produk mereka. Pada tahun 2008, Android SDK 1.0 diluncurkan dan phone G1 yang diproduksi oleh HTC menggunakan sistem operasi tersebut. Pada tahun 2010, Android menjadi sistem operasi Blackberry dan menjadi sistem operasi terbaik pada platform smart-phone. Versi 2.2 (Froyo) diluncurkan dan lebih dari 60 gadget menggunakannya (Muttaqin, 2014).
2.4. Pengertian Algoritma Algoritma adalah urutan langkah-langkah logis penyelesaian masalah yang disusun secara sistematis (Munir, 1999). Algoritma merupakan salah satu cabang ilmu komputer yang membahas prosedur penyelesaian suatu permasalahan. Dengan algoritma yang baik maka komputer bisa menyelesaikan perhitungan dengan cepat dan benar. Sebaliknya jika algoritma kurang baik maka penyelesaian lambat dan bahkan tidak didapat solusi yang diharapkan. Suatu algoritma akan memerlukan masukan (input) tertentu untuk memulainya, dan akan menghasilkan keluaran (output) tertentu pada akhirnya. Hal-hal yang perlu diperhatikan dalam algoritma adalah mencari langkah-langkah yang paling sesuai untuk penyelesaian suatu masalah, karena setiap algoritma memiliki karakteristik tertentu yang memiliki kelebihan dan kekurangan. Beberapa hal yang harus dipahami dalam mencari algoritma antara lain (Nugraha, 2011): 1. Masalah seperti apa yang hendak diselesaikan. 2. Gagasan apa yang ada pada algoritma tersebut.
Universitas Sumatera Utara
7
3. Berapa lama yang diperlukan untuk menyelesaikan masalah. 4. Berapa jumlah data yang dapat ditangani oleh suatu algoritma.
2.4.1. Algoritma String Matching (pencocokan string) String adalah rangkaian karakter atas ∑ alfabet yang terbatas. Misalnya, ATCTAGAGA adalah string atas ∑ = {A, C, G, T} (Navarro & Raffinot, 2002). Pengertian string menurut Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology (NIST) adalah susunan dari karakterkarakter(angka,alfabet atau karakter yang lain) dan biasanya direpresentasikan sebagai struktur dan array. String dapat berupa kata, frase, atau kalimat. Pencocokan string (string matching) merupakan bagian penting dari sebuah proses pencarian string(string searching) dalam sebuah dokumen. Hasil dari sebuah pencarian string dalam dokumen tergantung dari teknik dan cara pencocokan string yang digunakan (Buulolo, 2013).
2.4.2. Algoritma Apostolico-Crochemore
Algoritma Apostolico-Crochemore menggunakan tabel fungsi pinggiran kmpNext yang berasal dari Algoritma Knuth-Morris-Pratt untuk menghitung fungsi pinggiran yang mengindikasikan pergeseran x terbesar yang mungkin terjadi pada pattern x sebelum melakukan proses pencarian pada teks y. Diketahui l = 0 jika x adalah karakter tunggal yang dipangkatkan (x = cm dengan c di dalam ) dan l adalah posisi karakter pertama dari x yang berbeda dari x[0] (x = albu untuk a, b di dalam , u di dalam , dan a ≠b). Setiap pembandingan dilakukan dengan posisi yang berpola dengan urutan sebagai berikut : l , l +1, ..., m-2, m-1, 0, 1, ..., l -1. Selama fase pencarian, kita mempertimbangkan (i, j, k) di mana: i, j dan k adalah indeks l adalah posisi karakter pertama dari x yang berbeda jendela karakter diposisikan pada teks y[j .. j+m-1]; 0 k l dan x[0 .. k-1] = y[j .. j+k-1];
Universitas Sumatera Utara
8
l i < m dan x[ l ..i-1] = y[j+ l .. i+j-1]. (lihat gambar 2.1.) Inisialisasi awal dari (i, j, k) adalah ( l , 0, 0).
Gambar
2.1.
Pembandingan
dengan
algoritma
Apostolico-Crochemore
memperhatikan (i, j, k).
Komputasi
(perhitungan)
untuk
menentukan
(i,
j,
k)
berikutnya
mempertimbangkan tiga kasus yang bergantung pada nilai i, yaitu sebagai berikut: 1. i = l Jika x[i] = y[i+j] maka (i, j, k) berikutnya adalah (i+1, j, k). Jika x[i] y[i+j] maka (i, j, k) berikutnya adalah ( l , j+1, max{0, k-1}). 2. l < i < m Jika x[i] = y[i+j] maka (i, j, k) berikutnya adalah (i+1, j, k). Jika x[i] ≠ y[i+j] maka ada dua kasus yang muncul yang bergantung pada nilai kmpNext[i] : kmpNext[i] l maka (i, j, k) berikutnya ( l , i+j-kmpNext[i], max{0, kmpNext[i]}). kmpNext[i] > l maka (i, j, k) berikutnya (kmpNext[i], i+j-kmpNext[i], kmpNext[i] l ). 3. i = m Jika k < l dan x[k] = y[j+k] maka (i, j, k) berikutnya adalah (i, j, k+1). Sebaliknya salah satu dari k < l dan x[k] ≠y[j+k], atau k = l. Jika k = l kemunculan x diberitahukan. Pada kedua kasus tersebut perhitungan (i, j, k) berikutnya sama seperti perhitungan pada kasus l < i < m (Charras dan Lecroq, 1997).
Berikut ini adalah contoh cara kerja algoritma Apostolico-Crochemore. Teks y
:GCATCGCAGAGAGTATACAG
Pattern x
:GCAGAGAG
Universitas Sumatera Utara
9
1. Fase Proses Awal Tabel 2.1. Fungsi pinggiran kmpNext i
0
1
2
3
4
5
6
7
8
x[i]
G
C
A
G
A
G
A
G
kmpNext[i]
-1
0
0
-1
1
-1
1
-1
1
l=1 2. Fase Pencarian String Tahap 1 Perbandingan perkarakter dimulai dari indeks ke-1. G
G
C
A
T
1
2
3
C
A
G
C
G
C
A
A
G
A
G
G
A
G
A
G
T
A
T
A
C
A
G
A
T
A
C
A
G
A
T
A
C
A
G
Pattern x digeser sebanyak : 3-kmpNext[3] = 3- -1 = 4 karakter Tahap 2 G
C
A
T
C
G
C
A
G
A
G
A
A
G
A
G
A
G
G
T
1 G
C
Pattern x digeser sebanyak : 1-kmpNext[1] = 1-0 = 1 karakter Tahap 3 G
C
A
T
C
G
C
A
G
A
G
A
G
8
1
2
3
4
5
6
7
G
C
A
G
A
G
A
G
T
Pada tahap 3, pattern x sudah ditemukan di dalam teks y. Jumlah perbandingan yang dilakukan untuk mencari pattern x dilakukan sebanyak 12 kali. Jika pencarian string terus dilakukan sampai teks habis maka pattern x digeser sebanyak : 8-kmpNext[8] = 8-1 = 7 karakter. Tahap 4 G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
A
G
A
G
A
G
1 G
C
Pada tahap 4, seluruh teks sudah habis dicari. Maka total perbandingan yang dilakukan seluruhnya sampai teks habis adalah 13 kali (Charras dan Lecroq, 1997).
Universitas Sumatera Utara
10
2.5.
Penelitian Yang Relevan
Berikut ini beberapa penelitian yang terkait dengan algoritma ApostolicoCrochemore: 1. Nababan, A.A. (2015) dalam penelitiannya melakukan perancangan fitur pencari saran hasil terdekat dengan pencarian menggunakan algoritma pencocokan string Brute Force dan Knuth Morris-Pratt(KMP). Hasil penelitian tersebut ditemukan bahwa algoritma Knuth Morris-Pratt(KMP) melakukan pergeseran lebih jauh (tidak hanya bergeser satu karakter seperti dalam Brute Force). Dengan ini penggunaan algoritma Knuth-Morris-Pratt (KMP) dapat mempersingkat waktu dengan hasil rata-rata runtime 0,42717 ms dibandingkan dengan algoritma Brute Force yang memiliki hasil rata-rata runtime 0,44683 ms dalam pencocokan stringnya. 2. Suntoro, M. (2015) dalam penelitiannya melakukan implementasi algoritma pencocokan string Boyer-Moore dalam pembuatan contact manager pada platform Android. Algoritma Boyer-Moore menerapkan prinsip good suffix dimana karakter yang dicari sejajar dengan karakter yang menyerupainya serta prinsip bad character dimana jika karakter tidak memiliki kemiripan maka langsung dieliminasi. Field yang dipakai dalam pencarian contact manager adalah nama contact, dengan memasukan nama sebagai inputannya dalam pencarian. Hasil dari aplikasi ini menampilkan keseluruhan pattern yang match dengan teks, dengan kecepatan pencarian 0,9 detik. 3. Rizal (2015) dalam penelitiannya melakukan implementasi algoritma pencocokan string Turbo Boyer-Moore dalam pembuatan permainan tebak kata bahasa Aceh. Dalam penelitian tersebut ditemukan bahwa algoritma Turbo Boyer-Moore berhasil diterapkan dan menghasilkan pencocokan yang sesuai dengan yang diharapkan. Algoritma Turbo Boyer-Moore melakukan pencocokan dengan sangat cepat. Dari hasil penelitian juga ditemukan bahwa permainan tersebut menambah pembendaharaan kosa kata bahasa Aceh bagi siapa saja yang ingin belajar atau merasa kurang akan kosakata bahasa Aceh. Terbukti dari penelitian yang dilakukan, yaitu melalui hasil pretest, lalu percobaan pada game dan test. 4. Rochmawati, Y. & Kusumaningrum R. (2015) dalam penelitiannya melakukan perbandingan algoritma pencarian string dalam metode Approximate String Matching untuk identifikasi kesalahan pengetikan teks. Hasil penelitian tersebut ditemukan bahwa perbandingan algoritma pencarian string dalam metode Approximate String Matching menunjukkan bahwa algoritma Jaro Winkler Distance memiliki nilai tertinggi dibandingkan ketiga algoritma yang lain dengan nilai MAP 0,87 yang terbagi ke dalam empat jenis kesalahan penulisan yaitu jenis kesalahan penghapusan huruf 0,92, jenis kesalahan penambahan huruf 0,90, jenis kesalahan penggantian huruf 0,70 dan jenis kesalahan penukaran huruf 0,95.
Universitas Sumatera Utara
