Implementasi Algoritma Pencarian Substring dalam String Horspool dalam Bahasa Pemrograman Java: Program Pencarian Nama Bahasa Pemrograman

Pada artikel Algoritma Pencarian Substring dalam String Horspool : Pengertian, Konsep Dasar, Soal, dan Cara Kerja yang telah penulis terbitkan sebelumnya, penulis telah membahas tentang pengertian, Konsep Dasar, Soal, dan Cara Kerja dari algortima Horspool. Pada artikel ini penulis akan berfokus membahas tentang penerapan algoritma Horspool dalam bahasa pemrograman Java. 

    Sebelumnya penulis menganjurkan kepada para pembaca yang belum membaca artikel tersebut untuk sebaiknya membacanya terlebih dahulu sebagai pendahuluan agar pembahasan pada artikel ini dapat lebih mudah untuk dipahami oleh para pembaca yang budiman.

    Adapun tulisan ini pula sebenarnya penulis maksudkan untuk digabungkan bersama dengan artikel algoritma Horspool yang sebelumnya sudah penulis terbikan. Namun, agar fokus pembahasan pada artikel tersebut tidak terpisah, akhirnya penulis memutuskan untuk membuat artikel baru dengan fokus pembahasan yang baru pula yaitu membahas penerapan algoritma Horspool dalam bahasa pemrograman Java.

    Baiklah, saatnya memulai tahapan pertama dalam penerapan algoritma Horspool ke dalam bahasa pemrograman Java. Pertama-tama yang perlu dilakukan adalah mengimport libraries yang dibutuhkan untuk menerapkan algoritma ini. Adapun libraries yang diperlukan adalah sebagai berikut:

import java.util.Arraylist;
import java.util.Hashmap;
import java.util.Scanner;

public class HorspoolAlgorithm {

}

Langkah selanjutnya adalah membuat sebuah function yang akan digunakan untuk mendapatkan value dari setiap char yang ada pada pattern, value untuk setiap char ini akan dihimpun ke dalam sebuah objek Hashmap, Berikut adalah bagian source code yang berisi function yang akan digunakan untuk menghimpun values untuk setiap char pada pattern:

...

    private static HashMap<Character, Integer> getShiftTable(String pattern) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        int len = pattern.length();

        for (int i = 0; i < len - 1; i++)
            hashMap.put(pattern.charAt(i), len - 1 - i);
        return hashMap;
    }

...

    Pada source code diatas terdapat sebuah function bernama getShiftTable. Pada function tersebut pula penulis mendeklarasikan sebuah objek HashMap bernama values dan juga sebuah integer bernama len yang mengembalikan panjang pattern atau jumlah huruf yang ada pada pattern.

    Pada bagian selanjutnya terdapat sebuah perulangan dimana setiap char akan mendapatkan value masing-masing. Setelah proses perulangan, function getShiftTable pun akan mengembalikan sebuah objek HashMap yang pada awal pendeklarasiannya masih belum memiliki nilai menjadi berisi data-data char bersama pula dengan value masing-masing.

    Setelah membuat function getShiftTable, maka tahapan selanjutnya adalah membuat baris kode algoritma Horspool itu sendiri yang direpresentasikan dalam fungsi yang dibuat dalam source code sebagai berikut:

...

public static int horspoolPatternMatching(String text, String pattern) {
        HashMap<Character, Integer> hashMap = getShiftTable(pattern);

        int patternLength = pattern.length();
        int textLength = text.length();

        int i, j;
        Integer shift;

        for (i = patternLength - 1; i < textLength; shift = hashMap.get(text.charAt(i)), i             += shift != null ? shift: patternLength) {

            for (j = 0; (j < patternLength) && (text.charAt(i - j) == pattern
                .charAt(patternLength - 1 - j)); j++)
                ;

            if (j == patternLength)
                return i - patternLength + 1;
        }

        return -1;
    }

...

    Pada baris pertama dalam function diatas, penulis mendeklarasikan sebuah objek HashMap bernama values yang nilai-nilainyanya berasal dari nilai return dari function getShiftTable. Adapun function ini mengembalikan value dari setiap char pada pattern. Pada baris selanjutnya terdapat tiga variabel int sebagai tipe data primitif dan sebuah variabel Integer bernama shift sebagai objek.

    Baris selanjutnya terdapat sebuah nested loop (perulangan di dalam perulangan), pada perulangan paling luar dapat dilihat bahwa penulis melakukan perubahan pada nilai variabel shift pada bagian iteration, tepatnya pada kode shift = values.get(text.charAt(i)). 

    Pada bagian selanjutnya terdapat sebuah ternary operation. Ternary operation ini dilakukan untuk melakukan pengecekan kembali pada nilai shift yang sebelumnya telah dideklarasikan.  Apabila nilai shift tersedia maka nilai shift akan tetap bernilai dengan nilai yang sebelumnya telah diberikan. 

    Adapun jika nilai shift bernilai null atau nilai value untuk suatu char dalam teks tidak ditemukan dalam objek Hashmap (representasi dari BMT), maka nilai yang akan dikembalikan pada shift adalah adalah panjang dari pattern, hal ini dapat dilihat pada bagian kode  i += shift != null ? shift : patternLength 

    Adapun pada function horspoolPatternMatching diatas terdapat dua kemungkinan nilai yang akan dikembalikan. Kemungkinan pertama adalah nilai return yang terdapat dalam sintaks if yang hanya dapat tercapai apabila pattern ditemukan di dalam string atau teks, dalam kondisi ini nilai j akan terus bertambah sampai menjadi sama dengan panjang pattern.

    Adapun saat pattern tidak ditemukan di dalam teks, maka itu berarti nilai j tidak bertambah sampai dengan panjang pattern sehingga nilai yang akan dikembalikan oleh fungsi horspoolPatternMatching adalah -1 atau pattern tidak ditemukan di dalam teks.

   Tahapan selanjutnya adalah menggunakan function algoritma Horspool yang telah dibuat pada tahapan sebelumnya. Adapun pada artikel ini, penulis akan menggunakan kasus pencarian data bahasa pemrograman. Berikut adalah source code dari penerapan function algoritma Horspool yang telah dibuat sebelumnya:

...

public static void main(String[] args) {
        ArrayList<String> programmingLanguages = new ArrayList<>();

        programmingLanguages.add("C");
        programmingLanguages.add("C++");
        programmingLanguages.add("C#");
        programmingLanguages.add("GDScript");
        programmingLanguages.add("Java");
        programmingLanguages.add("JavaScript");
        programmingLanguages.add("Kotlin");
        programmingLanguages.add("PHP");
        programmingLanguages.add("Python");
        programmingLanguages.add("R");

        System.out.print("Cari bahasa pemrograman : ");
        String pattern = new Scanner(System.in).nextLine();

        for (int i = 0; i < programmingLanguages.size(); i++) {
            String text = programmingLanguages.get(i).toLowerCase();
            int position = horspoolPatternMatching(text, pattern);

            if (position != -1)
                System.out.println(programmingLanguages.get(i));
        }
    }

...

  Pada main function tahapan pertama adalah membuat sebuah objek ArrayList bernama programmingLanguages. Adapun objek ArrayList ini berfungsi untuk menampung data-data string atau teks. Setelah objek ArrayList dideklarasikan, selanjutnya adalah menambahkan data-data string kedalam objek Arraylist.

       Setelah semua data telah disiapkan, tahapan selanjutnya adalah mendeklarasikan sebuah string bernama pattern yang nilainya akan diambil dari input yang dilakukan oleh user. Setelah data-data teks dan data pattern telah siap, selanjutnya adalah tahapan terakhir yaitu melakukan pengecekan dengan perulangan. Variabel int position akan mendapatkan value dari function horspoolPatternMatching sehingga program akan melakukan pengecekan satu persatu apakah pada tiap-tiap teks yang terdapat pada objek Arraylist programmingLanguages terdapat pattern yang sedang dicari atau tidak. Adapun bagian-bagian source code yang telah dituliskan pada tahapan-tahapan sebeleumnya, apabila digabungkan akan menjadi sebagai berikut:

import java.util.Arraylist;
import java.util.Hashmap;
import java.util.Scanner;

public class HorspoolAlgorithm {

private static HashMap<Character, Integer> getShiftTable(String pattern) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        int len = pattern.length();

        for (int i = 0; i < len - 1; i++)
            hashMap.put(pattern.charAt(i), len - 1 - i);
        return hashMap;
    }

}

Penulis akan mencoba mencari pattern s c r i p t . Berikut adalah input beserta output yang dihasilkan apabila pattern atau substring yang dicari adalah s c r i p t:

Cari Pemain : script
GDScript  
JavaScript

    Pada input dan output diatas dapat dilihat bahwa saat user mencari pattern script, maka terdapat dua data yang muncul dari sepuluh data yang ada, yaitu GDScript dan juga JavaScript yang keduanya sama-sama mengandung pattern atau substring script. 

Share :