Pohon Akhiran

1. Introduction

Sebuah Pohon Akhiran adalah sebuah pohon terkompres yang memiliki semua akhiran dari sebauh teks T (yang biasanya panjang) dengan n karakter (n dapat sampai ratus ribuan karakter).

Posisi dari setiap akhiran pada teks string T disimpan sebagai indeks bilangan bulat pada daun-daun dari Pohon Akhiran dan jalur label (gabungan dari sisi label mulai dari akar) dari daun-daun tersebut merupakan akhiran dari string tersebut.
Pohon Akhiran menyediakan sebuah implementasi yang cepat dari banyak operasi penting string.

Struktur data ini berkaitan erat dengan struktur data Larik Akhiran data structure. Kedua struktur data tersebut biasa dipelajari secara bersamaan.

1-1. Akhiran dari String T

Akhiran (ke-)i dari string teks T (biasanya panjang) adalah 'kasus khusus' dari substring yang dimulai dari karakter ke-i dari string hingga karakter terakhirnya.


Sebagai contoh, jika T = "STEVEN$", maka akhiran 0 dari T adalah "STEVEN$" (indeks mulai dari 0), akhiran 2 dari T adalah "EVEN$", akhiran 4 dari T adalah "EN$", dst.

2. Visualisasi Pohon Suffiks

Visualisasi Pohon Akhiran dari sebuah string T pada dasarnya adalah sebuah pohon berakar di mana label jalur (penggabungan label sisi) dari akar ke setiap daun menggambarkan sebuah akhiran dari T. Setiap simpul daun adalah sebuah akhiran dan nilai bilangan bulat yang ditulis di dalam simpul daun (kita memastikan properti ini dengan simbol penutup $) adalah nomor akhiran.


Sebuah simpul internal akan bercabang ke lebih dari satu simpul anak, sehingga terdapat lebih dari satu akhiran dari akar ke daun melalui simpul internal ini. Label jalur dari sebuah simpul internal adalah awalan persekutuan di antara akhiran-akhiran tersebut.

2-1. Contoh dengan T = "GATAGACA$"

The Suffix Tree above is built from string T = "GATAGACA$" that have these 9 suffixes:

iSuffix
0GATAGACA$
1ATAGACA$
2TAGACA$
3AGACA$
4GACA$
5ACA$
6CA$
7A$
8$

Now verify that the path labels of suffix 7/6/2 are "A$"/"CA$"/"TAGACA$", respectively (there are 6 other suffixes). The internal vertices with path label "A"/"GA" branch out to 4 suffixes {7, 5, 3, 1}/2 suffixes {4, 0}, respectively. Root vertex branches out to all 9 suffixes.

2-2. Simbol Perhentian $

Untuk memastikan bahwa setiap akhiran dari string input T berakhir di simpul daun, kita mewajibkan string T diakhiri dengan simbol penutup khusus '$' yang tidak digunakan dalam string asli T dan memiliki nilai ASCII lebih rendah daripada karakter terendah yang diperbolehkan dalam T (yaitu karakter 'A' dalam visualisasi ini). Dengan cara ini, label sisi '$' selalu muncul di sisi paling kiri dari simpul akar pada visualisasi Pohon Akhiran ini.


Untuk contoh Pohon Akhiran di atas (untuk T = "GATAGACA$"), jika kita tidak memiliki simbol penutup '$', perhatikan bahwa akhiran 7 "A" (tanpa '$') TIDAK berakhir di simpul daun dan dapat mempersulit beberapa operasi selanjutnya.

2-3. Pohon Suffiks memiliki O(n) Simpul-Simpul

Karena kita telah memastikan bahwa semua akhiran berakhir di simpul daun, terdapat paling banyak n daun/akhiran dalam Pohon Akhiran. Semua simpul internal (termasuk simpul akar jika merupakan simpul internal) selalu bercabang sehingga bisa ada paling banyak n-1 simpul seperti itu, seperti yang ditunjukkan dengan salah satu kasus uji ekstrim di sebelah kanan.

Jumlah maksimum simpul dalam Pohon Akhiran adalah: n (daun) + (n-1) simpul internal = 2n-1 = O(n) simpul. Karena Pohon Akhiran adalah sebuah pohon, jumlah maksimum sisi dalam Pohon Akhiran juga (2n-1)-1 = O(n) sisi.

2-4. Pohon Suffiks yang Jauh Lebih Pendek

Pada saat semua karakter string T berbeda (contoh, T = "ABCDE$"), kita bisa mempunyai Pohon Akhiran yang sangat pendek dengan tepat n+1 simpul (+1 dari simpul akar).

3. Operasi yang Tersedia

Seluruh operasi pada pohon akhiran yang tersedia adalah:

  1. Bangun Pohon Akhiran (rincian diabaikan) — membangun secara langsung pohon akhiran dari string T.
  2. Cari — mencari simpul pada pohon akhiran dari sebuah string T (biasanya lebih panjang) yang memiliki label jalur yang memiliki pola sama dari string P (biasanya lebih pendek).
  3. Substring Berulang Terpanjang (LRS / Longest Repeated Substring) — mencari simpul internal terdalam (karena simpul tersebut memiliki awalan yang sama dengan dua atau lebih akhiran dari T).
  4. Substring Persekutuan Terpanjang (LCS / Longest Common Substring) — mencari simpul internal terdalam yang memiliki akhiran dari dua string original berbeda.
Terdapat beberapa kemungkinan operasi lainnya pada pohon akhiran yang tidak termasuk dalam visualisasi ini.

3-1. Membangun Pohon Akhiran

In this visualization, we only show the fully constructed Suffix Tree without describing the details of the O(n) Suffix Tree construction algorithm — it is a bit too complicated. Interested readers can explore this instead.


We limit the input to only accept 25 (cannot be too long due to the available drawing space — but in the real application of Suffix Tree, n can be in order of hundred thousand to million characters) ASCII (or even Unicode) characters. If you do not write a terminating symbol '$' at the back of your input string, we will automatically do so. If you place a '$' in the middle of the input string, they will be ignored. And if you enter an empty input string, we will resort to the default "GATAGACA$".


For convenience, we provide a few classic test case input strings usually found in Suffix Tree/Array lectures, but to showcase the strength of this visualization tool, you are encouraged to enter any 25-characters string of your choice (ending with character '$'). You can use Chinese characters, e.g., "四是四十是十十四不是四十四十不是十四$".

3-2. Pencarian

Dengan asumsi bahwa Pohon Akhiran dari string T (biasanya lebih panjang dengan panjang n) telah dibangun, kita ingin menemukan semua kemunculan dari pola/string pencarian P (dengan panjang m).

Untuk melakukan ini, kita mencari simpul x di Pohon Akhiran T yang memiliki label jalur (penggabungan label sisi dari akar ke x) di mana P adalah awalan dari label jalur tersebut. Setelah kita menemukan simpul x ini, semua daun dalam subtree yang berakar di x adalah kemunculannya.

Kompleksitas waktu: O(m+k) di mana k adalah jumlah total kemunculan.

Sebagai contoh, pada Pohon Akhiran dari T = "GATAGACA$" di atas, coba skenario berikut ini:

  1. P adalah kecocokan penuh dengan label jalur dari simpul x:
    Search("A"), kemunculan = {7, 5, 3, 1} atau Search("GA"), kemunculan = {4, 0}
  2. P adalah kecocokan sebagian dengan label jalur dari simpul x:
    Search("T"), kemunculan = {2} atau Search("GAT"), kemunculan = {0}
  3. P tidak ditemukan dalam T:
    Search("WALDO"), kemunculan = {NIL}

3-3. Substring Berulang Terpanjang (Longest Repeated Substring, LRS)

Dengan asumsi bahwa Pohon Akhiran dari string T (biasanya lebih panjang dengan panjang n) telah dibangun, kita dapat menemukan Substring Berulang Terpanjang (Longest Repeated Substring/LRS) dalam T dengan menemukan simpul internal terdalam (yang memiliki label jalur terpanjang) dari Pohon Akhiran T.

Hal ini karena setiap simpul internal dari Pohon Akhiran T bercabang ke setidaknya dua (atau lebih) akhiran, yaitu label jalur (awalan umum dari akhiran-akhiran ini) berulang.

Simpul internal terdalam (yang memiliki label jalur terpanjang) adalah jawaban yang dibutuhkan, yang dapat ditemukan dalam O(n) dengan traversal pohon sederhana.

Tanpa berlama-lama lagi, coba LRS("GATAGACA$"). Kita memiliki LRS = "GA".

Dimungkinkan bahwa T mengandung lebih dari satu LRS, misalnya, coba LRS("BANANABAN$").
Kita memiliki LRS = "ANA" (sebenarnya tumpang tindih) atau "BAN" (tanpa tumpang tindih).

3-4. Substring Persekutuan Terpanjang (Longest Common Substring, LCS)

Kali ini, kita membutuhkan dua string input T1 dan T2 yang berakhir dengan simbol '$'/'#', masing-masing. Kemudian kita membuat Pohon Akhiran general dari dua string ini T1+T2 dalam O(n) di mana n = n1+n2 (jumlah panjang dari dua string tersebut). Kita dapat menemukan Substring Persekutuan Terpanjang (Longest Common Substring/LCS) dari dua string tersebut T1 dan T2 dengan menemukan simpul internal terdalam dan valid dari Pohon Akhiran umum dari T1+T2.

Untuk menjadi simpul internal valid yang dipertimbangkan sebagai kandidat LCS, sebuah simpul internal harus mewakili akhiran dari kedua string, yaitu, substring persekutuan yang ditemukan di T1 dan T2.

Kemudian, karena simpul internal dari Pohon Akhiran T bercabang ke setidaknya dua (atau lebih) akhiran, yaitu label jalur (awalan umum dari akhiran-akhiran ini) berulang. Jika simpul internal tersebut juga valid, maka itu adalah substring persekutuan yang berulang.

Simpul internal valid dan terdalam (yang memiliki label jalur terpanjang) adalah jawaban yang dibutuhkan, yang dapat ditemukan dalam O(n) dengan traversal pohon sederhana.

Tanpa berlama-lama lagi, coba LCS(T1,T2) pada Pohon Akhiran umum dari string T1 = "GATAGACA$" dan T2 = "CATA#" (perhatikan bahwa UI akan berubah menjadi versi Pohon Akhiran umum). Kita memiliki LCS = "ATA".

4. Tambahan-Tambahan

Ada beberapa hal lain yang bisa kita lakukan dengan Pohon Akhiran seperti "Menemukan Substring Terulang Terpanjang tanpa tumpang tindih", "Menemukan Substring Umum Terpanjang dari ≥ 2 string", dll, tapi kita akan menyimpannya untuk nanti.


Kita akan melanjutkan diskusi tentang struktur data khusus string ini dengan struktur data Larik Akhiran yang lebih serbaguna.