Implementasi Algoritma Smith Waterman Dengan PHP

Khairu Aqsara Sudirman

Khairu Aqsara Sudirman

Apr 12, 2021 — 7 mins read

Beberapa waktu lalu saya mendapatkan pekerjaan yang mengharuskan saya menggunakan beberapa implementasi dari Pencocokan String, Terutama dalam hal pencarian, salah satunya Algoritma Smith Waterman, Dimana logaritma ini bertugas untuk melakukan pencocokan dari sebuah string yang dicari, dan saya ingin berbagi dengan teman-teman semua, siapa tau ada yang membutuhkan referensi atau hanya sebagai bahan pembelajaran untuk menambah pengetahuan.

String (String Matching) merupakan komponen dasar dalam pengimplementasian berbagai kebutuhan, String Matching digunakan untuk menemukan suatu atau lebih string dengan pattern tertentu.

Teknik utama dalam algoritma string matching adalah exact matching dimana hasil pencocokanya mengandung string yang sama persis salah satunya yaitu algoritma Smith Waterman, berbeda dengan algoritma dimana hasil pencocokanya tidak harus sama persis dengan string yang dicari misalnya algoritma Rabin Karp atau Fuzzy, tetapi pada tulisan ini saya mencoba fokus pada Algoritma Smith Waterman.

Algoritma Smith Waterman

Algoritma ini pertama kali ditemukan oleh Temple F. Smith dan Michel S. Waterman pada tahun 1981, Algoritma ini melakukan penjajaran Sekuens Local dengan memberikan batas-batas diantara 2 skuens, dan perlu diketahui juga algoritma ini menggunakan algoritma Needleman-Wunsch sebagai fondasi dari cara kerjanya. Algoritma ini digunakan secara luas dalam pencarian near-matches, atau yang biasa disebut dengan local alignments

Cara kerja dari logaritma ini cukup simple secara teori, misalkan saja terdapat string X dan string Y, langkah pertama dari proses algoritma ini adalah mencari panjang string dari string m(x) dan string n(Y), kemudian akan dicari bagian-bagian string X yang disejajarkan dengan string Y yang kemudian di presentasikan sebagai skor yang menunjukan "Goodness of fit" antara string X dan string Y.

Text Similarity

Sebelum kita jauh melangkah kedalam algoritma Smith Waterman ini, sebaiknya kita berkenalan dulu dengan fungsi-fungsi yang sebenarnya sudah ada dalam PHP, tetapi terkadang hasil dari fungsi-fungsi tersebut menghasilkan output yang tidak sesuai dengan yang diharapkan, pada intinya pada tulisan ini kita akan sedikit belajar pencocokan string atau Text Similarity atau nyari text yang paling cocok dengan input yang diberikan.

Similar_text()

Fungsi ini akan menghitung tingkat kecocokan dua buah string, hasil outputnya berupa jumlah karakter yang cocok atau fungsi ini akan menghitung seberapa banyak karakter yang sama dan ada di kedua string tersebut, fungsi ini menerima 3 parameter, parameter ketiga bersifat opsional, dan yang perlu diperhatikan adalah fungsi ini case-sensitive artinya string A tidak sama dengan string a, contoh penggunaanya.

similar_text($string1, $string2, $percent)

Contoh penggunaanya

<?php 
$str_1 = 'Hello World';
$str_2 = 'Hello Kuli';
echo similar_text($str_1, $str_2);
// Output : 7 

dari hasil kode tersebut kita bisa melihat jika hasilnya adalah 7, karena terdapat 7 string yang sama dari kedua string tersebut. Tetapi kita juga bisa mendapatkan hasil berupa persentase perbandingan, misalnya

<?php  
$str_1 = 'Hello World';
$str_2 = 'Hello Kuli';
similar_text($str_1, $str_2, $percent);
echo $percent;
// Output : 66.666666666667

hasilnya 66,6 %, menurut teman-teman sesuaikah kecocokan kedua string tersebut ? jawabanya saya serahkan kepada teman-teman, keterbatasan fungsi ini ada pada kecepatan pemrosesan jika digunakan untuk membandingkan string yang panjang.

levenshtein()

fungsi ini tidak jauh berbeda dengan similar_text() yang sudah kita coba sebelumnya, tetapi dari segi peformance fungsi ini lebih baik dibandingkan dengan fungsi similar_text()

cara kerja fungsi ini menganut prinsip levenshtein distance antara dua buah string, teman-teman bisa membaca tentang algoritma ini di google, pada tulisan ini saya tidak akan membahas panjang lebar tentang cara kerjanya, hanya sebagai pembanding saja dengan Algoritma Smith Waterman, contoh penggunaanya 

<?php 
//levenshtein(string1, string2, insert, replace, delete)
$str_1 = 'Hello World';
$str_2 = 'Hello Kuli';
$distance = levenshtein($str_1, $str_2);
echo $distance;
// Output : 4

dari sini teman-teman bisa mengambil kesimpulan kan ? antara similar_text() dan levenshtein() jika diterapkan dalam kasus-kasus pencarian yang sesuai kebutuhan.

Smith Waterman 

Seperti penjelasan sebelumnya, algoritma ini menggunakan prinsip Dynamic Programming Algorithm yang menggunakan dasar perhitungan matrix dan mencari gap scoring dari dua buah string yang diberikan.

Cara kerjanya cukup simple menurut saya, pertama kita harus mencari panjang masing-masing string yang diberikan, kemudian memecahnya dalam bentuk matrix, setelah matrixnya ditemukan kita harus mencari kecocokan dan ketidak cocokan dari kedua string tersebut.

Disini saya menggunaakn PSR 4 sebagai Autoloader nya, teman-teman bisa memodifikasinya jika tidak ingin menggunakan PSR 4, pertama-tama kita buat dulu project structurnya menggunakan composer.

mkdir text-similarity
cd text-similarity && composer init
composer install

kemudian isi sesuai dengan deskripsi yang teman-teman inginkan, berikut isi dari file composer.json yang saya miliki, isinya mungkin berbeda-beda, tergantung dari inputan yang teman-teman berikan.

{
    "name": "ezadev/smithwaterman",
    "description": "Text Similarity using Smith Waterman Algorithm",
    "authors": [
        {
            "name": "Khairu Aqsara",
            "email": "khairu.aqsara@hotmail.com"
        }
    ],
    "require": {}
}

kemudian selanjutnya kita harus menambahkan key autoload dengan value PSR4 pada file composer.json sehingga bentuk akhirnya seperti berikut.

{
    "name": "ezadev/smithwaterman",
    "description": "Text Similarity using Smith Waterman Algorithm",
    "authors": [
        {
            "name": "Khairu Aqsara",
            "email": "khairu.aqsara@hotmail.com"
        }
    ],
    "require": {},
    "autoload": {
        "psr-4": {
            "Ezadev\\SmithWaterman\\" : "src/"
        }
    }
}

kemudian kita buat sebuah file dengan nama Algorithm.php pada folder src dan isikan script berikut.

<?php 
namespace Ezadev\SmithWaterman;

class Algorithm
{
    private $nilai_cocok;
    private $nilai_tidak_cocok;

    public function __construct($nilai_cocok, $nilai_tidak_cocok)
    {
        if($nilai_cocok <= $nilai_tidak_cocok) throw new Exception("Nilai Cocok harus lebih besar dari Nilai tidak Cocok");
        $this->nilai_cocok = $nilai_cocok;
        $this->nilai_tidak_cocok = $nilai_tidak_cocok;
    }

    public function bandingkan($a, $aIndex, $b, $bIndex)
    {
        try{
            return @($a[$aIndex] === $b[$bIndex] ? $this->nilai_cocok : $this->nilai_tidak_cocok);
        }catch(Exception $e){
            throw new Exception($e);
        }
    }

    public function max()
    {
        return $this->nilai_cocok;
    }

    public function min()
    {
        return $this->nilai_tidak_cocok;
    }
}

kemudian buat satu file lagi dengan nama Matrix.php dan isikan kode berikut.

<?php 
namespace Ezadev\SmithWaterman;

class Matrix
{
    private $gap;
    private $subsitusi;

    public function __construct($gap=-0.5, $subsitusi=null)
    {
        if($gap > 0.0) throw new Exception("Gap harus lebih kecil dari 0");
        if(empty($subsitusi)){
            $this->subsitusi = new Algorithm(1.0, -2.0);
        }else{
            $this->subsitusi = $subsitusi;
        }
        $this->gap = $gap;
    }

    public function perbandingan($a, $b)
    {
        if(empty($a) && empty($b))
        {
            return 1.0;
        }


        if(empty($a) || empty($b))
        {
            return 0.0;
        }

        $max_distance = min(mb_strlen($a), mb_strlen($b)) * max($this->subsitusi->max(), $this->gap);
        return ($this->generate_matrix($a, $b) / $max_distance) * 100; 
    }

    public function generate_matrix($s, $t)
    {
        $v0 = [];
        $v1 = [];
        $t_len = mb_strlen($t);
        $max = $v0[0] = max(0, $this->gap, $this->subsitusi->bandingkan($s, 0, $t, 0));


        for($j=1; $j<=$t_len; $j++)
        {
            $v0[$j] = max(0, $v0[$j - 1] + $this->gap, $this->subsitusi->bandingkan($s, 0, $t, $j));
            $max = max($max, $v0[$j]);
        }

        for($i=1; $i< mb_strlen($s); $i++)
        {
            $v1[0] = max(0, $v0[0] + $this->gap, $this->subsitusi->bandingkan($s, $i, $t, 0));
            $max = max($max, $v1[0]);
            for($j=1; $j < $t_len; $j++)
            {
                $v1[$j] = max(0, $v0[$j] + $this->gap, $v1[$j - 1] + $this->gap, $v0[$j - 1] + $this->subsitusi->bandingkan($s, $i, $t, $j));
                $max = max($max, $v1[$j]);
            }

            for($j=0; $j<$t_len;$j++)
            {
                $v0[$j] = $v1[$j];
            }
        }
        return $max;
    }
}

kemudian kita tes hasil dari algoritma tersebut, dengan membuat sebuah script dengan nama index.php diluar folder src

<?php
require_once("vendor/autoload.php");
use Ezadev\SmithWaterman\Matrix;

$testing = new Matrix();
$string1 = "Nama saya Kurosaki";
$string2 = "saya punya nama Ichigo Kurosaki";

$string3 = "Hello World";
$string4 = "Hello Kuli";

echo $testing->perbandingan($string1, $string2)."\n";
echo $testing->perbandingan($string3, $string4)."\n";

// Output : 50
// Output : 60

Dari hasil diatas, kita bisa melihat hasil dari perbandingan kedua buah string, menghasilkan 50% text matching dan 60% text matching, teman-teman bisa mengembangkan algoritma ini unukt menyesuaikan kebutuhan teman-teman.

programming php
Read More

Writeup CTFR Nama-Nama Ikan

Diberikan sebuah service pada alamat 103.157.96.13 dengan port 7782, service tersebut memungkinkan kita untuk menginputkan nama-nama ikan, berdasarkan binary file dan source code yang diberikan, challenge ini terbilang cukup sulit, karena harus memanfaatkan fungsi plt untuk mendapatkan shell, jika dilihat dari source code yang diberikan

Read More

Memahami Reflection Class pada PHP

dari arti-nya saja teman-teman mungkin sudah bisa menebak maksudnya, ya sederhananya dalam bahasa indonesia refleksi, tetapi dalam dunia pemrograman refleksi ini bisa kita sebut sebagai kemampuan sebuah program untuk mengidentifikasi dirinya sendiri, maksudnya dengan adanya fitur ini sebuah class dapat melihat method dan property apa saja yang dimilikinya.