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$"

Pohon akhiran di atas dibangun dari T = "GATAGACA$" yang mempunyai 9 akhiran berikut:

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

Sekarang verifikasi bahwa label jalur dari akhiran 7/6/2 adalah "A$"/"CA$"/"TAGACA$", masing-masing (terdapat 6 akhiran lainnya). Simpul internal dengan label jalur "A"/"GA" bercabang menjadi 4 akhiran {7, 5, 3, 1}/2 akhiran {4, 0}, masing-masing (kita mengabaikan simpul internal trivial = simpul akar yang bercabang ke semua 9 akhiran).

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

Dalam visualisasi ini, kami hanya menampilkan Pohon Akhiran yang sepenuhnya terbangun tanpa menjelaskan detail algoritma konstruksi Pohon Akhiran O(n) — ini sedikit terlalu rumit. Pembaca yang tertarik dapat menjelajahinya lebih lanjut.

Kami membatasi input hanya menerima 25 karakter ASCII (atau bahkan Unicode) (tidak bisa terlalu panjang karena ruang gambar yang tersedia — tetapi dalam aplikasi Pohon Akhiran yang sebenarnya, n bisa mencapai ratusan ribu hingga jutaan karakter). Jika Anda tidak menulis simbol terminasi '$' di akhir string input Anda, kami akan melakukannya secara otomatis. Jika Anda meletakkan '$' di tengah string input, mereka akan diabaikan. Dan jika Anda memasukkan string input kosong, kami akan menggunakan default "GATAGACA$".

Untuk kenyamanan, kami menyediakan beberapa string input kasus uji klasik yang biasanya ditemukan dalam kuliah Pohon/Larik Akhiran, tetapi untuk menunjukkan kekuatan alat visualisasi ini, Anda didorong untuk memasukkan string hingga 25 karakter pilihan Anda (diakhiri dengan karakter '$'). Anda bisa menggunakan karakter Bahasa Mandarin (dalam Unicode), seperti "四是四十是十十四不是四十四十不是十四$".

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.