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).
Struktur data ini berkaitan erat dengan struktur data Larik Akhiran data structure. Kedua struktur data tersebut biasa dipelajari secara bersamaan.
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
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.
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
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.
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
Pohon akhiran di atas dibangun dari T = "GATAGACA$" yang mempunyai 9 akhiran berikut:
| i | Akhiran |
|---|---|
| 0 | GATAGACA$ |
| 1 | ATAGACA$ |
| 2 | TAGACA$ |
| 3 | AGACA$ |
| 4 | GACA$ |
| 5 | ACA$ |
| 6 | CA$ |
| 7 | A$ |
| 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).
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
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.
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.
Seluruh operasi pada pohon akhiran yang tersedia adalah:
- Bangun Pohon Akhiran (rincian diabaikan) — membangun secara langsung pohon akhiran dari string T.
- 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).
- 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).
- Substring Persekutuan Terpanjang (LCS / Longest Common Substring) — mencari simpul internal terdalam yang memiliki akhiran dari dua string original berbeda.
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 "四是四十是十十四不是四十四十不是十四$".
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:
- P adalah kecocokan penuh dengan label jalur dari simpul x:
, kemunculan = {7, 5, 3, 1} atau , kemunculan = {4, 0} - P adalah kecocokan sebagian dengan label jalur dari simpul x:
, kemunculan = {2} atau , kemunculan = {0} - P tidak ditemukan dalam T:
, kemunculan = {NIL}
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 . Kita memiliki LRS = "GA".
Dimungkinkan bahwa T mengandung lebih dari satu LRS, misalnya, coba .
Kita memiliki LRS = "ANA" (sebenarnya tumpang tindih) atau "BAN" (tanpa tumpang tindih).
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 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".
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.
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
Bangun Pohon Akhiran
Cari
Substring Berulang Terpanjang
Substring Persekutuan Terpanjang