Algoritma Suffix Tree 2

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)

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:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

If titikCabangTerakhir IsNot Nothing AndAlso titikCabangTerakhir.PointerSuffix Is Nothing Then
	titikCabangTerakhir.PointerSuffix = titikCabangBaru
End If

3l. Tambahkan titik cabang yang baru ke dalam tree

titikCabangBaru.tambahTitik(labelTitik, idxCabangTerakhir)
labelTitik += 1
titikCabangTerakhir = titikCabangBaru
i += 1
isMengikutiTitikSuffix = True

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

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)

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

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

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

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

If j < garis.jalur.Length Then
	Return False
End If

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

titik = garis.titikAkhir

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

If isSelesai Then
	idxSelesai = cariIdxSelesai(garis.idxSelesai)
End If

* Gunakan fungsi ini untuk memvalidasi indeks selesai dari posisi terpilih

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

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.