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)
1 2 | Dim tree As New SuffixTree(input) tree.BuatTree() |
* 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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 | Public Class SuffixTree Private titikTerpilih As Titik Private titikCabangTerakhir As Titik 'Untuk menambahkan pointer suffix Private kedalamanTitikTerpilih As Integer = 0 'Kedalaman titik dari akar utama Private idxCabangTerakhir As Integer = 0 'titik cabang terakhir yang dilalui Private labelTitik As UInteger = 0 'label titik saat penambahan / split Private minJarak As Integer = 0 'Jarak minimal Private m_akarTitik As Titik 'Titik utama dari semua cabang-cabang dibawahnya Private Shared m_teks As String 'input Friend Property akarTitik() As Titik Get Return m_akarTitik End Get Private Set(value As Titik) m_akarTitik = value End Set End Property Public Shared Property teks() As String Get Return m_teks End Get Private Set(value As String) m_teks = value End Set End Property Public Sub New(input As String) If String.IsNullOrWhiteSpace(input) Then Throw New ArgumentNullException(input) End If teks = input titikTerpilih = New Titik(labelTitik) akarTitik = titikTerpilih End Sub . . . End Class Public Class Titik Private m_Label As UInteger Private m_daftarGaris As Dictionary(Of Char, Garis) Private m_PointerSuffix As Titik Friend Property Label() As UInteger Get Return m_Label End Get Set(value As UInteger) m_Label = value End Set End Property Friend Property daftarGaris() As Dictionary(Of Char, Garis) Get Return m_daftarGaris End Get Private Set(value As Dictionary(Of Char, Garis)) m_daftarGaris = Value End Set End Property Friend Property PointerSuffix() As Titik Get Return m_PointerSuffix End Get Set(value As Titik) m_PointerSuffix = Value End Set End Property Public Sub New(label As UInteger) Me.Label = label Me.daftarGaris = New Dictionary(Of Char, Garis)() Me.PointerSuffix = Nothing End Sub . . . End Class Public Class Garis Private m_titikAkhir As Titik Private m_idxMulai As Integer Private m_idxSelesai As Integer Friend Property titikAkhir() As Titik Get Return m_titikAkhir End Get Private Set(value As Titik) m_titikAkhir = value End Set End Property Friend Property idxMulai() As Integer Get Return m_idxMulai End Get Private Set(value As Integer) m_idxMulai = value End Set End Property Friend Property idxSelesai() As Integer Get Return m_idxSelesai End Get Private Set(value As Integer) m_idxSelesai = value End Set End Property Friend ReadOnly Property jalur() As String Get Dim panjang As Integer = IIf(Me.idxSelesai < 0, SuffixTree.teks.Length - Me.idxMulai, Me.idxSelesai - Me.idxMulai + 1) Return SuffixTree.teks.Substring(Me.idxMulai, panjang) End Get End Property Public Sub New(titik As Titik, idxMulai As Integer, Optional idxSelesai As Integer = -1) If titik Is Nothing Then Throw New ArgumentNullException("titik tidak ditemukan") End If If idxMulai < 0 Then Throw New ArgumentOutOfRangeException("idxMulai", "indeks tidak dapat bernilai negatif") End If If idxMulai > CUInt(idxSelesai) Then Throw New ArgumentOutOfRangeException("idxMulai", "tidak dapat memulai pencarian setelah indeks terakhir") End If If idxSelesai < 0 Then idxSelesai = -1 End If Me.idxMulai = idxMulai Me.idxSelesai = idxSelesai Me.titikAkhir = titik End Sub . . . End Class |
Selanjutnya adalah proses pembuatan struktur pohon yang dijelaskan pada fungsi BuatTree
* Lakukan perhitungan pada semua karakter teks
1 2 3 | Dim i As Integer = 0 While i < teks.Length . . . |
* 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
1 2 3 4 5 | Private Sub updateMinJarak(idx As Integer) If idxCabangTerakhir < kedalamanTitikTerpilih + minJarak + idx Then minJarak = Math.Max(0, idxCabangTerakhir - kedalamanTitikTerpilih - idx) End If End Sub |
3b. Cari obyek selanjutnya dari titik terpilih
1 | Dim obj = titikTerpilih.cariJalurSelanjutnya(i + kedalamanTitikTerpilih, isMengikutiTitikSuffix) |
* 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | Friend Function cariJalurSelanjutnya(idxMulai As Integer, isMengikutiTitikSuffix As Boolean) As Tuple(Of Titik, Garis) If isMengikutiTitikSuffix AndAlso PointerSuffix IsNot Nothing Then Return New Tuple(Of Titik, Garis)(PointerSuffix, Nothing) End If Dim garis = CariGaris(idxMulai) If garis Is Nothing Then Return Nothing End If If garis.jalur.Length = 1 Then Return New Tuple(Of Titik, Garis)(garis.titikAkhir, garis) End If Return New Tuple(Of Titik, Garis)(Nothing, garis) End Function |
* 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | Friend Function CariGaris(idxMulai As Integer) As Garis If idxMulai >= SuffixTree.teks.Length Then Return Nothing End If Return cariGaris(SuffixTree.teks(idxMulai)) End Function Friend Function cariGaris(karakter As Char) As Garis If Not Me.daftarGaris.ContainsKey(karakter) Then Return Nothing End If Return Me.daftarGaris(karakter) End Function |
3c. Jika semua karakter sudah diproses dan tidak ditemukan obyek selanjutnya, maka proses perhitungan sudah selesai
1 2 3 | If i + kedalamanTitikTerpilih >= teks.Length AndAlso obj Is Nothing Then Exit While End If |
3d. Jika tidak ditemukan obyek selanjutnya, maka tambahkan titik ini ke dalam tree
1 2 3 4 5 6 7 8 | If obj Is Nothing Then titikTerpilih.tambahTitik(labelTitik, i + kedalamanTitikTerpilih) labelTitik += 1 idxCabangTerakhir = i + kedalamanTitikTerpilih i += 1 isMengikutiTitikSuffix = True Continue While End If |
* Gunakan fungsi ini untuk menambahkan titik ke dalam tree
1 2 3 4 5 | Friend Sub tambahTitik(label As UInteger, idxMulai As Integer, Optional idxSelesai As Integer = -1) Dim titik = New Titik(label) Dim garis = New Garis(titik, idxMulai, idxSelesai) Me.daftarGaris.Add(garis.jalur(0), garis) End Sub |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | Dim objTitik = obj.Item1 Dim objGaris = obj.Item2 If objGaris Is Nothing Then titikTerpilih = objTitik kedalamanTitikTerpilih -= 1 isMengikutiTitikSuffix = False Continue While ElseIf objTitik IsNot Nothing Then titikTerpilih = objTitik kedalamanTitikTerpilih += 1 isMengikutiTitikSuffix = False Continue While End If |
3f. Dengan menggunakan obyek garis yang ditemukan, maka lakukan penelurusan menuju titik selanjutnya
dan dapatkan dimana jalur suffix mulai bercabang
1 | Dim obj2 = objGaris.TelusuriJalur(i, kedalamanTitikTerpilih, minJarak, titikTerpilih) |
* Gunakan fungsi ini untuk melakukan perbandingan pada teks input dimulai dari posisi i dengan semua obyek yang terdapat dalam garis
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | Friend Function TelusuriJalur(i As Integer, ByRef kedalamanTitikTerpilih As Integer, ByRef minJarak As Integer, ByRef titikTerpilih As Titik) As Tuple(Of Garis, Integer) Dim teks As String = SuffixTree.teks Dim skipKarakter As Integer = minJarak Dim idxMulai As Integer = i + kedalamanTitikTerpilih If skipKarakter >= Me.jalur.Length Then Dim edge = Me.titikAkhir.CariGaris(i + Me.jalur.Length) kedalamanTitikTerpilih += Me.jalur.Length minJarak -= Me.jalur.Length titikTerpilih = Me.titikAkhir Return edge.TelusuriJalur(i, kedalamanTitikTerpilih, minJarak, titikTerpilih) End If Dim j As Integer = TelusuriGaris(teks, idxMulai, skipKarakter) Return New Tuple(Of Garis, Integer)(Me, j) End Function |
* Gunakan fungsi ini untuk melakukan penelusuran pada garis dan melakukan pengecekan apakah cocok dengan pola (suffix) yang dicari
1 2 3 4 5 6 7 8 9 10 11 12 13 | Friend Function TelusuriGaris(suffix As String, idxMulai As Integer, Optional skip As Integer = 0) As Integer Dim skipKarakter As Integer = skip idxMulai += skipKarakter While skipKarakter < jalur.Length AndAlso idxMulai < suffix.Length If jalur(skipKarakter) <> suffix(idxMulai) Then Exit While End If skipKarakter += 1 idxMulai += 1 End While Return skipKarakter End Function |
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
1 2 3 4 5 6 7 8 9 | objGaris = obj2.Item1 Dim panjangJalur As Integer = obj2.Item2 If panjangJalur = objGaris.jalur.Length Then titikTerpilih = objGaris.titikAkhir kedalamanTitikTerpilih += objGaris.jalur.Length isMengikutiTitikSuffix = False Continue While End If |
* 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
1 2 3 4 5 6 7 8 | minJarak = panjangJalur idxCabangTerakhir = i + panjangJalur + kedalamanTitikTerpilih If idxCabangTerakhir >= teks.Length Then i += 1 isMengikutiTitikSuffix = True Continue While End If |
3i. Tambahkan titik cabang yang baru dengan cara melakukan split pada indeks mulai ditambah panjang jalur
1 2 | Dim titikCabangBaru = objGaris.Split(objGaris.idxMulai + panjangJalur - 1, labelTitik) labelTitik += 1 |
* Gunakan fungsi ini untuk melakukan split garis menjadi sebuah percabangan dengan 2 garis baru
1 2 3 4 5 6 7 8 9 10 11 12 | Friend Function Split(idxSelesai As Integer, nomorTitik As UInteger) As Titik Dim idxMulaiBerikutnya As Integer = idxSelesai + 1 Dim titikSebelumnya = Me.titikAkhir Dim garis = New Garis(titikSebelumnya, idxMulaiBerikutnya, Me.idxSelesai) Dim titik As New Titik(nomorTitik) Me.idxSelesai = idxSelesai Me.titikAkhir = titik titik.daftarGaris.Add(garis.jalur(0), garis) Return titik End Function |
3j. Jika cabang ini berasal dari jalur yang hanya memiliki 1 karakter,
maka beri status pointer yaitu titik yang telah dipilih sebelumnya
1 2 3 | If objGaris.jalur.Length = 1 Then titikCabangBaru.PointerSuffix = titikTerpilih End If |
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
1 2 3 | If titikCabangTerakhir IsNot Nothing AndAlso titikCabangTerakhir.PointerSuffix Is Nothing Then titikCabangTerakhir.PointerSuffix = titikCabangBaru End If |
3l. Tambahkan titik cabang yang baru ke dalam tree
1 2 3 4 5 | titikCabangBaru.tambahTitik(labelTitik, idxCabangTerakhir) labelTitik += 1 titikCabangTerakhir = titikCabangBaru i += 1 isMengikutiTitikSuffix = True |
4. Lakukan pencarian pola menggunakan algoritma ini (poin 4a – 4c)
1 2 3 4 5 6 7 | Dim idxMulai As Integer = -1 Dim idxSelesai As Integer = -1 If tree.Cari(pola, idxMulai, idxSelesai) Then Console.WriteLine("Pola ditemukan pada indeks ke " & idxMulai & " dan berakhir pada " & idxSelesai) Else Console.WriteLine("Pola tidak ditemukan") End If |
Memasuki perhitungan pada fungsi Cari
4a. Lakukan perhitungan pada semua karakter dalam pola (atau suffix) (poin 4a1 – 4a5)
1 2 3 | Dim i As Integer = 0 While i < suffix.Length . . . |
4a1. Dapatkan garis yang menghubungkan antara titik sekarang dan suffix yang terpilih
Jika tidak ditemukan garis penghubung, maka hentikan pencarian karena suffix tidak ditemukan
1 2 3 4 | garis = titik.CariGaris(suffix(i)) If garis Is Nothing Then Return False End If |
4a2. Lakukan penelusuran garis dengan cara melompati titik suffix dan titik setelahnya karena sudah digunakan pada garis ini
1 2 | Dim j As Integer = garis.TelusuriGaris(suffix, i, 1) i += j |
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
1 2 3 4 5 6 7 | If i >= suffix.Length Then If j < garis.jalur.Length Then idxSelesai = cariIdxSelesai(garis.idxSelesai) - (garis.jalur.Length - j) isSelesai = False End If Exit While End If |
4a4. Jika panjang garis sudah tidak mencapai panjang jalur sebenarnya maka hentikan pencarian karena suffix tidak ditemukan
1 2 3 | If j < garis.jalur.Length Then Return False End If |
4a5. Gunakan titik akhir dari garis sebagai titik awal dari perulangan selanjutnya
1 | titik = garis.titikAkhir |
4b. Jika kondisi selesai pada perulangan diatas terpenuhi, maka cari posisi dimana indeks karakter terakhir ditemukan
1 2 3 | If isSelesai Then idxSelesai = cariIdxSelesai(garis.idxSelesai) End If |
* Gunakan fungsi ini untuk memvalidasi indeks selesai dari posisi terpilih
1 2 3 4 5 6 7 | Private Function cariIdxSelesai(idxSelesai As Integer) As Integer If idxSelesai < 0 Then Return teks.Length - 1 End If Return idxSelesai End Function |
4c. Lakukan perhitungan mundur sebanyak jumlah karakter suffix untuk mendapatkan posisi awal
1 | idxMulai = idxSelesai - suffix.Length + 1 |
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.
