Pohon Akhiran

1. Introduction

A Suffix Tree is a compressed tree containing all the suffixes of the given (usually long) text string T of length n characters (n can be on order of hundred thousands of characters).

The positions of each suffix in the text string T are recorded as integer indices at the leaves of the Suffix Tree whereas the path labels (concatenation of edge labels starting from the root) of the leaves describe the suffixes.

Suffix Tree provides a particularly fast implementation for many important (long) string operations.

This data structure is very related to the Suffix Array data structure. Both data structures are usually studied together.

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:

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 $

In order to ensure that every suffix of the input string T ends in a leaf vertex, we enforce that string T ends with a special terminating symbol '$' that is not used in the original string T and has ASCII value lower than the lowest allowable character in T (which is character 'A' in this visualization). This way, edge label '$' always appears at the leftmost edge of the root vertex of this Suffix Tree visualization.

For the Suffix Tree example above (for T = "GATAGACA$"), if we do not have terminating symbol '$', notice that suffix 7 "A" (without the '$') does NOT end in a leaf vertex and can complicate some operations later.

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

As we have ensured that all suffixes end at a leaf vertex, there are at most n leaves/suffixes in a Suffix Tree. All internal vertices (including the root vertex if it is an internal vertex) are always branching thus there can be at most n-1 such vertices, as shown with one of the extreme test case on the right.

The maximum number of vertices in a Suffix Tree is thus = n (leaves) + (n-1) internal vertices = 2n-1 ∈ O(n) vertices. As Suffix Tree is a tree, the maximum number of edges in a Suffix Tree is also (2n-1)-1 ∈ O(n) edges.

2-4. Pohon Suffiks yang Jauh Lebih Pendek

3. Operasi yang Tersedia

All available operations on the Suffix Tree in this visualization are listed below:

1. Build Suffix Tree (instant/details omitted) — instantly build the Suffix Tree from string T.
2. Search — Find the vertex in Suffix Tree of a (usually longer) string T that has path label containing the (usually (much) shorter) pattern/search string P.
3. Longest Repeated Substring (LRS) — Find the deepest (the one that has the longest path label) internal vertex (as that vertex shares common prefix between two (or more) suffixes of T).
4. Longest Common Substring (LCS) — Find the deepest internal vertex that contains suffixes from two different original strings.

There are a few other possible operations of Suffix Tree that are not included in this visualization.

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 up to 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 character '$' in the middle of the input string, it 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 up-to-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.