Algoritma Rabin Karp merupakan algoritma pencocokan string yang akan menggunakan fungsi hash sebagai pembanding antara string yang dicari (m) dengan substring pada teks (n).
Artinya jika hash value keduanya adalah sama maka akan dilakukan perbandingan sekali lagi terhadap karakter-karakternya. Apabila hasil keduanya tidak sama, maka substring akan bergeser ke kanan. Pergeseran dilakukan sebanyak (n-m) kali. Perhitungan nilai hash yang efisien pada saat pergeseran akan mempengaruhi performa dari algoritma ini. (David Indra Lesmana, 2012).
Langkah-langkah dalam algortima Rabin Karp :
1. Normalisasi text : Lowertext + Stopword (menghilangkan tanda baca, spasi, angka) + Stemming (mengubah ke kata dasar).
2. Membagi teks kedalam gram-gram yang ditentukan nilai k-gramnya
3. Mencari nilai hash dengan fungsi hash dari tiap kata yang terbentuk
4. Mencari nilai hash yang sama antara dua tek
Parsing k-gram adalahmembentuk pola kata pada teks dengan memecah kata menjadi potongan-potongan dimana setiap potongan mengandung karakter sebanyak k.K-grammerupakansebuah metode yang diaplikasikan untuk pembangkitan kata ataukarakter.Metode k-grams ini digunakan untuk mengambil potongan-potongankarakter huruf sejumlah k dari sebuah kata yang secara kontinuitas dibaca dari teks sumber hingga akhir dari dokumen.
Setelah melakukan Parsing K-gram maka langkah selanjutnya adalah hashing terhadap seluruh pecahan string hasil dari proses parsing k-gram. Hashing itu sendiri adalah suatu cara untuk mentransformasi string menjadi suatu nilai yang unik (hash value)dengan panjang tertentu (fixed-length) yang berfungsi sebagai penanda string tersebut. Pada sistem ini proses hashing memanfaatkan tabel ascii dengan rumus Hash (Diana dkk,2011):
Keterangan :
c = Nilai ascii karakter (desimal)
k = Banyak karakter (indeks karakter)
b = Basis Bilangan (nilai dari basis bilangan harus bilangan prima).
Alasan kenapa Basis bilangan (b) harus dipilih bilangan prima yang cukup besar, adalah untuk mengurangi kemungkinan adanya dua hash value yang sama.
Penampakan Hasilnya:
Dan hasil akumulasi akurasinya adalah sbb:
Dengan Script PHP Rabin Karp sbb:
<?php
$time_start = microtime_float();
ini_set('memory_limit', '256M');
$tanggal=WKT(date("Y-m-d"));
$gram=7;
$base=5;
if(isset($_POST["Proses"])){
$gram=strip_tags($_POST["gram"]);
$base=strip_tags($_POST["base"]);
$judul=strip_tags($_POST["judul"]);
$abstrak=strip_tags($_POST["abstrak"]);
$id_pengujian=strip_tags($_POST["q"]);
}
$sql="select * from `$tbpengujian` order by `id_pengujian` desc";
if(isset($_GET["q"])){
$id_pengujian=$_GET["q"];
$sql="select * from `$tbpengujian` where `id_pengujian`='$id_pengujian'";
}
$d=getField($conn,$sql);
$id_pengujian=$d["id_pengujian"];
$judul=$d["judul"];
$abstrak=$d["abstrak"];
$rekapitulasi=$d["rekapitulasi"];
$id_user=$d["id_user"];
$kategori=$d["kategori"];
$keterangan=$d["keterangan"];
$norm=$d["normalisasi"];
?>
<link rel="stylesheet" href="jsacordeon/jquery-ui.css">
<link rel="stylesheet" href="resources/demos/style.css">
<script src="jsacordeon/jquery-1.12.4.js"></script>
<script src="jsacordeon/jquery-ui.js"></script>
<script>
$( function() {
$( "#accordion" ).accordion({
collapsible: true
});
} );
</script>
</head>
<body>
<div id="accordion">
<h3>Form Uji</h3>
<div>
<form action="" method="post" enctype="multipart/form-data">
<table border="1" width="90%" class="table table-hover rable-striped table-bordered" >
<tr>
<td>Judul
<td>:
<td>
<textarea name="judul" class="form-control" required cols="55" rows="2"><?php echo $judul;?></textarea>
</tr>
<tr>
<td>Abstrak
<td>:
<td>
<textarea name="abstrak" class="form-control" cols="55" rows="3"><?php echo $abstrak;?></textarea>
</tr>
<tr>
<td>
Konfigurasi
<td>:
<td>
<label>N-gram</label>
<select name="gram" id="gram" required />
<option <?php if($gram=="choose"){echo"selected";}?>>Pilih Angka</option>
<option value="3" <?php if($gram=="3"){echo"selected";}?>>3</option>
<option value="4" <?php if($gram=="4"){echo"selected";}?>>4</option>
<option value="5" <?php if($gram=="5"){echo"selected";}?>>5</option>
<option value="6" <?php if($gram=="6"){echo"selected";}?>>6</option>
<option value="7" <?php if($gram=="7"){echo"selected";}?>>7</option>
<option value="8" <?php if($gram=="8"){echo"selected";}?>>8</option>
<option value="9" <?php if($gram=="9"){echo"selected";}?>>9</option>
<option value="10" <?php if($gram=="10"){echo"selected";}?>>10</option>
</select>
<label>Base</label>
<select name="base" id="base" required />
<option <?php if($base=="choose"){echo"selected";}?>>Angka Prima</option>
<option value="2" <?php if($base=="2"){echo"selected";}?>>2</option>
<option value="3" <?php if($base=="3"){echo"selected";}?>>3</option>
<option value="5" <?php if($base=="5"){echo"selected";}?>>5</option>
<option value="7" <?php if($base=="7"){echo"selected";}?>>7</option>
<option value="11" <?php if($base=="11"){echo"selected";}?>>11</option>
<option value="13" <?php if($base=="13"){echo"selected";}?>>13</option>
<option value="17" <?php if($base=="17"){echo"selected";}?>>17</option>
</select>
</tr>
<tr>
<td>
<td colspan="2">
<input name="q" type="hidden" id="q" value="<?php echo $id_pengujian;?>" />
<input name="Proses" type="submit" id="Proses" value="Analisa" />
<a href="?mnu=rk"><input name="Batal" type="button" id="Batal" value="Clear" /></a>
</td>
</tr>
</table>
</form>
<?php
if(isset($_POST["Proses"])){
$gram=strip_tags($_POST["gram"]);
$base=strip_tags($_POST["base"]);
$judul=strip_tags($_POST["judul"]);
$abstrak=strip_tags($_POST["abstrak"]);
$gab="$judul $abstrak";
$norm=getNorm($gab);
}
echo"<b>Judul Uji:</b>";
echo "<h1><font color='#ffAA08'>$norm</font></h1>";
echo "<h3><font color='#AA08ff'>Ngram: $gram, Base: $base</font></h3><hr>";
$nom=0;
$maxkemiripan=0;
$idmax=0;
$rekapitulasimax="";
$id_crawlingmax=0;
$ketmax="";
$array = prosesRK($norm,$gram,$base);
$ars1 = $array[0];
$arv1 = $array[1];
$nom=0;
$sql="select * from `$tbcrawling` order by `id_crawling` asc";
$jum=getJum($conn,$sql);
if($jum > 0){
$arr=getData($conn,$sql);
foreach($arr as $d) {
$id_crawling=$d["id_crawling"];
$judul=ucwords($d["judul"]);
$abstrak=$d["abstrak"];
$normalisasi=$d["normalisasi"];
$kategori=$d["kategori"];
$keterangan=$d["keterangan"];
$nom++;
echo "<b><font color='green'>".$nom. ".".$judul."</font></b><br>";
echo "<i><small><font color='magenta'>$normalisasi</font></small><br>";
$array = prosesRK($normalisasi,$gram,$base);
$ars2 = $array[0];
$arv2 = $array[1];
$sama=0;
$gabs="";
$gabv="";
$H1=count($arv1);
$H2=count($arv2);
for($i=0;$i<$H1;$i++){
for($j=0;$j<$H2;$j++){
if($arv1[$i]==$arv2[$j]){
$sama=$sama+1;
$gabv.="{".$arv2[$j]."} ";
$gabs.="{".$ars2[$j]."} ";
break;
}
}
}
$PN=($H1+$H2-$sama);
if($PN<$sama){
$hmin=$H1;
if($H2<$H1){$hmin=$H2;}
$sama=$hmin;
$PN=($H1+$H2-$sama);
$sim=$sama/$PN * 100;
$sim=round($sim,3);
$ssim="$sama/($H1+$H2-$sama) x 100%";
}
else{
$sim=$sama/$PN * 100;
$sim=round($sim,3);
$ssim="$sama/($H1+$H2-$sama) x 100%";
}
$rekapitulasi= "Jumlah Hash DataUji : $H1<br>";
$rekapitulasi.= "Jumlah Hash Datalatih : $H2<br>";
$rekapitulasi.= "Fingerprint Sama: $gabv<br>";
$rekapitulasi.= "Fingerprint Sama: $gabs<br>";
$rekapitulasi.= "<font color=\"red\"><b>Kemiripan : $ssim = $sim %</b></font>";
echo"<hr>";
echo $rekapitulasi;
echo"<hr>";
if($maxkemiripan<$sim){
$maxkemiripan=$sim;
$idmax=$id_crawling;
$rekapitulasimax=$rekapitulasi;
$id_crawlingmax=$id_crawling;
$ketmax="$ssim = $sim %";
}
}//foreach
}//jum foreach
$kategori="Tidak Plagiarism";
if($maxkemiripan>50){$kategori="Plagiarism Tinggi";}
else if($maxkemiripan>30){$kategori="Plagiarism Sedang";}
else if($maxkemiripan>20){$kategori="Plagiarism Rendah";}
$time_end = microtime_float();
$waktu = $time_end - $time_start;
$sql="update `$tbpengujian` set
`window`='$window',`ngram`='$gram',`id_crawling`='$id_crawlingmax',
`rekapitulasi`='$rekapitulasimax',`waktu`='$waktu',`prosentase`='$maxkemiripan',
`base`='$base',`kategori`='$kategori',`keterangan`='$ketmax' where `id_pengujian`='$id_pengujian'";
//$ubah=process($conn,$sql);
echo "<font color='blue'><b><h1>Kategori $kategori : $maxkemiripan %</h1><br>lama proses: $waktu ms</b></font>";
?>
</div>
</div>
Dan sbb adalah tabel yang digunakan:
Tidak ada komentar:
Posting Komentar