Algoritma Suffix Tree


Algoritma Suffix Tree adalah salah satu algoritma yang dapat digunakan untuk mencari dimana sebuah string (dalam kasus ini dinamakan sebagai pola) apakah ditemukan di dalam kumpulan string lain dengan ukuran yang lebih besar. Contoh yang dibahas kali ini adalah mengenai pencarian kata dari sebuah input teks.


Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan teks yang digunakan sebagai input
Diasumsikan data input adalah sebagai berikut:
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.

2. Tentukan pola yang digunakan dalam pencarian
Diasumsikan pola adalah sebagai berikut
labor

3. Lakukan inisialisasi variabel yang dibutuhkan oleh algoritma ini (poin 3a – 3l)

* Skrip tersebut akan melakukan inisialisasi pada Class SuffixTree. Class ini berisi tentang beberapa fungsi dan properti, dengan 2 fungsi utama adalah untuk membuat struktur pohon dan melakukan pencarian pola berdasarkan struktur pohon. Selain ini, diperlukan 2 class tambahan, yaitu Class Titik dan Class Garis yang digunakan untuk menampung data titik dan semua garis yang menghubungkan titik tersebut. Deklarasi ketiga class tersebut adalah sebagai berikut:

Selanjutnya adalah proses pembuatan struktur pohon yang dijelaskan pada fungsi BuatTree

* Lakukan perhitungan pada semua karakter teks

* Gunakan fungsi ini untuk mengupdate jarak minimal yang indeks yang sedang dihitung
Pastikan jarak obyek ini selalu berada dalam batas minimum yang memenuhi persamaan
lastBranchIdx >= i + activeLen + minDist

3b. Cari obyek selanjutnya dari titik terpilih

* Gunakan fungsi ini untuk mencari jalur selanjutnya yang dimulai dari titik yang terpilih
Cari garis yang dimulai dari titik terpilih
Jika garis tidak ditemukan maka jalur tidak ditemukan
Jika panjang jalur hanya ada 1 maka nilai pengembalian adalah titik akhir dan garis tersebut
Selain itu maka nilai pengembalian adalah hanya garis tersebut

* Gunakan fungsi ini untuk mencari garis yang dimulai dari indeks tertentu
Jika indeks posisi sudah melebihi kedalaman pohon, maka garis tidak ditemukan
Jika tidak ada garis yang mengandung karakter pada indeks terpilih, maka garis tidak ditemukan

3c. Jika semua karakter sudah diproses dan tidak ditemukan obyek selanjutnya, maka proses perhitungan sudah selesai

3d. Jika tidak ditemukan obyek selanjutnya, maka tambahkan titik ini ke dalam tree

* Gunakan fungsi ini untuk menambahkan titik ke dalam tree

3e. Dapatkan obyek titik dan garis dari titik terpilih
Jika obyek garis tidak ditemukan, maka gunakan obyek titik tersebut sebagai titik terpilih dan ulangi perhitungan dari awal
Jika obyek titik ditemukan, maka gunakan obyek titik tersebut sebagai titik terpilih dan ulangi perhitungan dari awal

3f. Dengan menggunakan obyek garis yang ditemukan, maka lakukan penelurusan menuju titik selanjutnya
dan dapatkan dimana jalur suffix mulai bercabang

* Gunakan fungsi ini untuk melakukan perbandingan pada teks input dimulai dari posisi i dengan semua obyek yang terdapat dalam garis

* Gunakan fungsi ini untuk melakukan penelusuran pada garis dan melakukan pengecekan apakah cocok dengan pola (suffix) yang dicari

3g. Dapatkan obyek garis berikutnya dan panjang jalur yang dilewati
Jika semua garis pada jalur sudah dilewati, maka gunakan titik terakhir sebagai titik terpilih dan ulangi perhitungan dari awal

* Memasuki perhitungan untuk membuat titik cabang yang baru

3h. Dapatkan jarak minimal dan indeks titik cabang yang terpilih
Jika indeks titik cabang sudah melebihi panjang input, maka ulangi pencarian dari awal
tetapi dengan syarat pencarian berikutnya masih harus mengikuti titik suffix sebelumnya

3i. Tambahkan titik cabang yang baru dengan cara melakukan split pada indeks mulai ditambah panjang jalur

* Gunakan fungsi ini untuk melakukan split garis menjadi sebuah percabangan dengan 2 garis baru

3j. Jika cabang ini berasal dari jalur yang hanya memiliki 1 karakter,
maka beri status pointer yaitu titik yang telah dipilih sebelumnya

3k. Jika sebelumnya sudah ditemukan titik cabang tetapi tidak memiliki status pointer
maka beri status pointer pada titik cabang tersebut yaitu adalah titik cabang yang baru

3l. Tambahkan titik cabang yang baru ke dalam tree

4. Lakukan pencarian pola menggunakan algoritma ini (poin 4a – 4c)

Memasuki perhitungan pada fungsi Cari

4a. Lakukan perhitungan pada semua karakter dalam pola (atau suffix) (poin 4a1 – 4a5)

4a1. Dapatkan garis yang menghubungkan antara titik sekarang dan suffix yang terpilih
Jika tidak ditemukan garis penghubung, maka hentikan pencarian karena suffix tidak ditemukan

4a2. Lakukan penelusuran garis dengan cara melompati titik suffix dan titik setelahnya karena sudah digunakan pada garis ini

4a3. Jika panjang garis pada jalur sudah melebihi jumlah karater suffix, maka hentikan perulangan
tetapi apabila panjang garis sudah tidak mencapai panjang jalur sebenarnya, maka catat posisi dimana indeks karakter tersebut selesai ditemukan

4a4. Jika panjang garis sudah tidak mencapai panjang jalur sebenarnya maka hentikan pencarian karena suffix tidak ditemukan

4a5. Gunakan titik akhir dari garis sebagai titik awal dari perulangan selanjutnya

4b. Jika kondisi selesai pada perulangan diatas terpenuhi, maka cari posisi dimana indeks karakter terakhir ditemukan

* Gunakan fungsi ini untuk memvalidasi indeks selesai dari posisi terpilih

4c. Lakukan perhitungan mundur sebanyak jumlah karakter suffix untuk mendapatkan posisi awal


Hasil akhir adalah: (klik untuk perbesar gambar)


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *