Hai sobat blogger. sekarang saya mau belajar tentang Algoritma yang digunakan pada string dan array nih.. apa aja sih macamnya? dan bagaaimana sih contoh penggunaanya dalam java?
okee... mari kita bahas satu persatu ya..
Algoritma pencarian string atau sering disebut juga pencocokan string adalah algoritma untuk melakukan pencarian semua kemunculan string pendek pattern[0..n-1] yang disebut pattern di string yang lebih panjang teks[0..m-1] yang disebut teks.
Pencocokkan string merupakan permasalahan paling sederhana dari semua permasalahan string lainnya, dan dianggap sebagai bagian dari pemrosesan data, pengkompresian data, analisis leksikal, dan temu balik informasi. Teknik untuk menyelesaikan permasalahan pencocokkan string biasanya akan menghasilkan implikasi langsung ke aplikasi string lainnya.
Contoh algoritma pencocokan string
Algoritma-algoritma pencocokkan string dapat diklasifikasikan menjadi tiga bagian menurut arah pencariannya.
Tiga kategori itu adalah :
1. Dari arah yang paling alami, dari kiri ke kanan, yang merupakan arah untuk membaca, algoritma yang termasuk kategori ini adalah:
- Algoritma Brute Force
- Algoritma dari Morris dan Pratt, yang kemudian dikembangkan oleh Knuth, Morris, dan Pratt
2. Dari kanan ke kiri, arah yang biasanya menghasilkan hasil terbaik secara praktikal, contohnya adalah:
- Algoritma dari Boyer dan Moore, yang kemudian banyak dikembangkan, menjadi Algoritma turbo Boyer-Moore, Algoritma tuned Boyer-Moore, dan Algoritma Zhu-Takaoka;
3. Dan kategori terakhir, dari arah yang ditentukan secara spesifik oleh algoritma tersebut, arah ini menghasilkan hasil terbaik secara teoritis, algoritma yang termasuk kategori ini adalah:
- Algoritma Colussi
- Algoritma Crochemore-Perrin
- salah satunya algoritma SUSAN
A. Algoritma brute force dalam pencarian string.
Algoritma brute force merupakan algoritma pencocokan string yang ditulis tanpa memikirkan peningkatan performa. Algoritma ini sangat jarang dipakai dalam praktik, namun berguna dalam studi pembanding dan studi-studi lainnya.
Cara kerja:
Secara sistematis, langkah-langkah yang dilakukan algoritma brute force pada saat mencocokkan string adalah:
1. Algoritma brute force mulai mencocokkan pattern pada awal teks.
2. Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
- Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
- Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
3. Algoritma kemudian terus menggeser pattern sebesar satu ke kanan, dan mengulangi langkah ke-2 sampai pattern berada di ujung teks.
Berikut adalah Algoritma brute force yang sedang bekerja mencari string:
procedure BruteForceSearch(
input m, n : integer,
input P : array[0..n-1] of char,
input T : array[0..m-1] of char,
output ketemu : array[0..m-1] of boolean
)
Deklarasi:
i, j: integer
Algoritma:
for (i:=0 to m-n) do
j:=0
while (j < n and T[i+j] = P[j]) do
j:=j+1
endwhile
if(j >= n) then
ketemu[i]:=true;
endif
endfor
B. Algoritma Boyer-Moroe
Algoritma Boyer-Moore adalah salah satu algoritma pencarian string, dipublikasikan oleh Robert S. Boyer, dan J. Strother Moore pada tahun 1977.
Algoritma ini dianggap sebagai algoritma yang paling efisien pada aplikasi umum. Tidak seperti algoritma pencarian string yang ditemukan sebelumnya, algoritma Boyer-Moore mulai mencocokkan karakter dari sebelah kanan pattern. Ide di balik algoritma ini adalah bahwa dengan memulai pencocokan karakter dari kanan, dan bukan dari kiri, maka akan lebih banyak informasi yang didapat.
Cara kerja:
Misalnya ada sebuah usaha pencocokan yang terjadi pada teks[i..i+n-1], dan anggap ketidakcocokan pertama terjadi di antara teks[i+j] dan pattern[j], dengan 0 < j < n. Berarti, teks[i+j+1..i+n-1] = pattern[j+1..n-1] dan a=teks[i+j] tidak sama dengan b=pattern[j] . Jika u adalah akhiran dari pattern sebelum b dan v adalah sebuah awalan dari pattern, maka penggeseran-penggeseran yang mungkin adalah:
- Penggeseran good-suffix yang terdiri dari menyejajarkan potongan teks[i+j+1..i+n-1] = pattern[j+1..n-1] dengan kemunculannya paling kanan di pattern yang didahului oleh karakter yang berbeda dengan pattern[j]. Jika tidak ada potongan seperti itu, maka algoritma akan menyejajarkan akhiran v dari teks[i+j+1..i+n-1] dengan awalan dari pattern yang sama.
- Penggeseran bad-character yang terdiri dari menyejajarkan teks[i+j] dengan kemunculan paling kanan karakter tersebut di pattern. Bila karakter tersebut tidak ada di pattern, maka pattern akan disejajarkan dengan teks[i+n+1].
Secara sistematis, langkah-langkah yang dilakukan algoritma Boyer-Moore pada saat mencocokkan string adalah:
1. Algoritma Boyer-Moore mulai mencocokkan pattern pada awal teks.
2. Dari kanan ke kiri, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
a. Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
b. Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
3. Algoritma kemudian menggeser pattern dengan memaksimalkan nilai penggeseran good-suffix dan penggeseran bad-character, lalu mengulangi langkah 2 sampai pattern berada di ujung teks.
Berikut adalah pseudocode algoritma Boyer-Moore pada fase pra-pencarian:
procedure preBmBc(
input P : array[0..n-1] of char,
input n : integer,
input/output bmBc : array[0..n-1] of integer
)
Deklarasi:
i: integer
Algoritma:
for (i := 0 to ASIZE-1)
bmBc[i] := m;
endfor
for (i := 0 to m - 2)
bmBc[P[i]] := m - i - 1;
endfor
procedure preSuffixes(
input P : array[0..n-1] of char,
input n : integer,
input/output suff : array[0..n-1] of integer
)
Deklarasi:
f, g, i: integer
Algoritma:
suff[n - 1] := n;
g := n - 1;
for (i := n - 2 downto 0) {
if (i > g and (suff[i + n - 1 - f] < i - g))
suff[i] := suff[i + n - 1 - f];
else
if (i < g)
g := i;
endif
f := i;
while (g >= 0 and P[g] = P[g + n - 1 - f])
--g;
endwhile
suff[i] = f - g;
endif
endfor
procedure preBmGs(
input P : array[0..n-1] of char,
input n : integer,
input/output bmBc : array[0..n-1] of integer
)
Deklarasi:
i, j: integer
suff: array [0..RuangAlpabet] of integer
preSuffixes(x, n, suff);
for (i := 0 to m-1)
bmGs[i] := n
endfor
j := 0
for (i := n - 1 downto 0)
if (suff[i] = i + 1)
for (j:=j to n - 2 - i)
if (bmGs[j] = n)
bmGs[j] := n - 1 - i
endif
endfor
endif
endfor
for (i = 0 to n - 2)
bmGs[n - 1 - suff[i]] := n - 1 - i;
endfor
Dan berikut adalah pseudocode algoritma Boyer-Moore pada fase pencarian:
procedure BoyerMooreSearch(
input m, n : integer,
input P : array[0..n-1] of char,
input T : array[0..m-1] of char,
output ketemu : array[0..m-1] of boolean
)
Deklarasi:
i, j, shift, bmBcShift, bmGsShift: integer
BmBc : array[0..255] of interger
BmGs : array[0..n-1] of interger
Algoritma:
preBmBc(n, P, BmBc)
preBmGs(n, P, BmGs)
i:=0
while (i<= m-n) do
j:=n-1
while (j >=0 n and T[i+j] = P[j]) do
j:=j-1
endwhile
if(j < 0) then
ketemu[i]:=true;
endif
bmBcShift:= BmBc[chartoint(T[i+j])]-n+j+1
bmGsShift:= BmGs[j]
shift:= max(bmBcShift, bmGsShift)
i:= i+shift
C. Algoritma Divide and Conquer
Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan.
Langkah-langkah umum algoritma Divide and Conquer :
- Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).
- Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).
- Combine : Menggabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.
Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap rupa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif.
Sesuai dengan karakteristik pembagian dan pemecahan masalah tersebut, maka algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif ( perulangan dengan memanggil dirinya sendiri ). Dengan demikian, algoritma ini dapat diimplementasikan dengan cara iteratif ( perulangan biasa ), karena pada prinsipnya iteratif hampir sama dengan rekursif.
Salah satu penggunaan algoritma ini yang paling populer adalah dalam hal pengolahan data yang bertipe array ( elemen larik ). Mengapa ? Karena pengolahan array pada umumnya selalu menggunakan prinsip rekursif atau iteratif. Penggunaan secara spesifik adalah untuk mencari nilai minimal dan maksimal serta untuk mengurutkan elemen array. Dalam hal pengurutan ini ada empat macam algoritma pengurutan yang berdasar pada algoritma Divide and Conquer, yaitu merge sort, insert sort, quick sort, dan selection sort. Merge sort dan Quick sort mempunyai kompleksitas algoritma O(n ²log n). Hal ini lebih baik jika dibandingkan dengan pengurutan biasa dengan menggunakan algoritma brute force.
Contoh penerapannya :
Pemecahan Masalah Convex Hull dengan Algoritma Divide and Conquer, hal ini dapat dipandang
sebagai generalisasi dari algoritma pengurutan merge sort. Berikut ini merupakan garis besar gambaran dari algoritmanya:
- Pertama-tama lakukan pengurutan terhadap titik-titik dari himpunan S yang diberikan berdasarkan koordinat absis-X, dengan kompleksitas waktu O(n log n).
- Jika |S| ≤ 3, maka lakukan pencarian convex hull secara brute-force dengan kompleksitas waktu O(1). (Basis).
- Jika tidak, partisi himpunan titik-titik pada S menjadi 2 buah himpunan A dan B, dimana A terdiri dari setengah jumlah dari |S| dan titik dengan koordinat absix-X yang terendah dan B terdiri dari setengah dari jumlah |S| dan titik dengan koordinat absis-X terbesar.
- Secara rekursif lakukan penghitungan terhadap HA = conv(A) dan HB = conv(B).
- Lakukan penggabungan (merge) terhadap kedua hull tersebut menjadi convex hull, H, dengan menghitung dan mencari upper dan lower tangents untuk HA dan HB dengan mengabaikan semua titik yang berada diantara dua buah tangen ini.
Pada algoritma di atas, dapat dilihat bahwa terdapat prosedur untuk mencari lower tangen dan upper tangen. Algoritmanya merupakan suatu algoritma berjalan yang biasa. Pada kasus ini, a diinisialisasi sebagai titik paling kanan dari HA dan b merupakan titik paling kiri dari HB. Jika pasangan ab belum merupakan lower tangen untuk HA dan HB , maka “nailkkan” a menjadi suksesor dari a dan “turunkan” b menjadi predesesor dari b, sesuai dengan kaidah arah jarum jam.
Berikut adalah gambaran umum dalam pencarian lower tangen dari HA dan HB : LowerTangen(HA, HB):
- Misalkan a merupakan titik terkanan dari HA
- Misalkan b merupakan titik terkanan dari HB
- While (ab bukan merupakan lower tangen dari HA dan HB)do - While(ab bukan merupakan lower tangen dari HA) do a -> a.predesesor - While(ab bukan merupakan lower tangen dari HA) do b-> b.suksesor
- Return ab.
Algoritma Divide and Conquer merupakan salah satu solusi dalam penyelesaian masalah convex hull. Algoritma ini ternyata memiliki kompleksitas waktu yang cukup kecil dan efektif dalam menyelesaikan permasalahan ini (jika dibandingkan algoritma lain). Selain itu juga, algoritma ini dapat digeneralisasi untuk permasalahan convex hull yang berdimensi lebih dari 3.
Contoh kasus
Persoalan : Misalnya diketahui table A yang berukuran n elemen sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam table tersebut.
Misalkan tabel A berisi elemen-elemen sebagai berikut :
3-10-20-5-17-1-31-2-19
Lalu algoritma melakukan divide seperti berikut :
3-10-20-5 & 17-1-31-2-19
Lalu algoritma melakukan solve seperti berikut :
dari 3-10-19-5 diketahui min=3;maks=20 , dan dari 17-1-31-2-20 diketahui min=1;maks=20.
Setelah melakukan solve, algoritma kemudian menggabungkan kedua data tersebut dan menentukan nilai min dan maks berdasarkan dari kedua data yang didapat, sehingga didapatlah min=1 maks=20.
Ilustrasi dari contoh kasus diatas bisa dilihat seperti gambar dibawah ini :
Berikut adalah sourcecode:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;
public class DivideConquer
{
public DivideConquer()
{
System.out.println("Divide and Conquer: maximum subarray");
System.out.println("Enter number of elements in the array");
int array_elements = 2;
try
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
array_elements = Integer.parseInt(reader.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
if (array_elements < 2)
{
System.out.println("Number of elements in the array should be greater or equal 2");
}
else
{
Random random = new Random();
int[] A = new int[array_elements];
for (int i = 0; i < A.length; i++)
A[i] = random.nextInt(1000) - 500;
System.out.println("Original array");
for (int i : A)
{
System.out.print(String.format("%5d", i));
}
System.out.println();
int[] result = find_maximum_subarray(A, 0, A.length-1);
System.out.println("Maximum sub-array");
System.out.println("Low " + result [0]);
System.out.println("High " + result [1]);
System.out.println("Sum " + result [2]);
}
}
private int[] find_maximum_subarray(int[] A, int low, int high)
{
if( high == low)
{
int[] result = {low, high, A[low]}; //base case: only one element
return result;
}
else
{
int mid = (low + high) /2;
int[] result1 = find_maximum_subarray (A, low, mid);
int[] result2 = find_maximum_subarray (A, mid+1, high);
int[] result3 = find_max_crossing_subarray(A, low, mid, high);
if( result1[2] >= result2[2] && result1[2] >= result3[2] )
{
return result1;
}
else if (result2[2] >= result1[2] && result2[2] >= result3[2])
{
return result2;
}
else
{
return result3;
}
}
}
private int[] find_max_crossing_subarray(int[] A, int low, int mid, int high)
{
int left_sum = Integer.MIN_VALUE;
int sum = 0;
int max_left = -1;
int max_right = -1;
for(int i = mid; i > low; i--)
{
sum += A[i];
if (sum > left_sum)
{
left_sum = sum;
max_left = i;
}
}
int right_sum = Integer.MIN_VALUE;
sum = 0;
for(int j = mid+1; j < high; j++)
{
sum += A[j];
if (sum > right_sum)
{
right_sum = sum;
max_left = j;
}
}
int[] result = {max_left, max_right, left_sum + right_sum};
return result;
}
}
okeee Terimakasih sudah membaca blog saya,, semoga bermanfaat ya..
Terimakasi :-D
Tidak ada komentar:
Posting Komentar