Larik Akhiran (Suffix Array) adalah sebuah array terurut dari semua akhiran (sufiks) sebuah string T dengan panjang n (n dapat mencapai ratusan ribu karakter).
Struktur data ini sederhana namun bermanfaat besar yang digunakan, diantara struktur data lainnya, dalam mengindeks teks secara keseluruhan, algoritma kompresi data, dan dalam bidang bioinformatika.
Struktur data ini berkaitan erat dengan struktur data Pohon Akhiran (Suffix Tree). Kedua struktur data biasanya dipelajari 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.
→
🕑
Visualisasi dari Larik Akhiran hanyalah sebuah tabel di mana tiap baris merepresentasikan sebuah akhiran dan setiap kolom merepresentasikan atribut dari akhiran-akhiran tersebut.
Empat atribut (dasar) untuk setiap baris i adalah:
indeks i, merentang dari 0 ke n-1,
SA[i]: akhiran leksikografis terkecil ke-i dari T merupakan akhiran ke-SA[i].
LCP[i]: Awalan Persekutuan Terpanjang (Longest Common Prefix) antara akhiran terkecil ke-i dan akhiran terkecil ke-(i-1) secara leksikografis dari T adalah LCP[i] (kita akan melihat aplikasi dari atribut ini nanti), dan
Akhiran T[SA[i]:] - akhiran terkecil ke-i secara leksikografis dari T dimulai dari indeks SA[i] hingga akhir (indeks n-1).
Beberapa operasi mungkin menambahkan lebih banyak atribut ke setiap baris dan dijelaskan saat operasi tersebut dibahas.
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.
←
→
🕑
Seluruh operasi pada larik akhiran yang tersedia adalah:
Buat Larik Akhiran (SA) adalah algoritma konstruksi larik akhiran O(n log n) berdasarkan ide dari Karp, Miller, & Rosenberg (1972) yang mengurutkan awalan dari akhiran berdasarkan panjang yang bertambah besar (1, 2, 4, 8, ...).
Cari memanfaatkan fakta bahwa akhiran dalam Larik Akhiran (SA) sudah terurutkan dan memanggil dua pencarian biner dalam waktu O(m log n) untuk menemukan kemunculan pertama dan terakhir dari string dengan pola P dan panjang m.
Awalan Persekutuan Terpanjang (LCP / Longest Common Prefix) antara dua akhiran berurutan (selain akhiran pertama) dapat dihitung dalam waktu O(n) menggunakan teorema Permuted LCP (PLCP).
Substring Berulang Terpanjang (LRS / Longest Repeated Substring) adalah algoritma sederhana untuk menemukan akhiran dengan nilai LCP terbesar dalam waktu O(n).
Substring Persekutuan Terpanjang (LCS / Longest Common Substring) adalah algoritma sederhana untuk menemukan akhiran dengan nilai LCP terbesar yang berasal dari dua string berbeda dalam waktu O(n).
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.
←
→
🕑
Dalam visualisasi ini, kami menunjukkan konstruksi Larik Akhiran yang tepat O(n log n) berdasarkan ide Karp, Miller, & Rosenberg (1972) yang men-sort awalan dari akhiran dalam urutan panjang yang meningkat (1, 2, 4, 8, ...), yang dikenal sebagai algoritma Prefix Doubling.
Kami membatasi input hanya menerima 12 karakter huruf BESAR (tidak boleh terlalu panjang karena ruang gambar yang tersedia — tetapi dalam aplikasi nyata Pohon Akhiran, n bisa mencapai ratusan ribu hingga jutaan karakter) dan simbol terminasi khusus '$' (yaitu, [A-Z$]). Jika Anda tidak menulis simbol terminasi '$' di belakang string input Anda, kami akan melakukannya secara otomatis. Jika Anda menempatkan '$' di tengah string input, simbol tersebut 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 dianjurkan untuk memasukkan string 12 karakter pilihan Anda (diakhiri dengan karakter '$').
Perlu dicatat bahwa kolom Larik LCP tetap kosong dalam operasi ini. Mereka harus dihitung secara terpisah melalui operasi Awalan Persekutuan Terpanjang.
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.
←
→
🕑
Algoritma Prefix Doubling ini berjalan dalam O(log n) iterasi, di mana untuk setiap iterasi, ia membandingkan substring T[SA[i]:SA[i+k]] dengan T[SA[i+k]:SA[i+2k]], yaitu pertama membandingkan dua pasang karakter, kemudian membandingkan dua karakter pertama dengan dua berikutnya, kemudian membandingkan empat karakter pertama dengan empat berikutnya, dan seterusnya.
Algoritma ini paling baik dieksplorasi melalui visualisasi, lihat ConstructSA("GATAGACA$") dalam aksi.
Kompleksitas waktu: Terdapat O(log n) iterasi Prefix Doubling, dan setiap iterasi kita memanggil Radix Sort O(n), sehingga berjalan dalam O(n log n) — cukup baik untuk menangani hingga n ≤ 200K karakter dalam masalah kompetisi pemrograman yang melibatkan string panjang
←
→
🕑
Setelah kita membangun Larik Akhiran dari T dalam O(n log n), kita dapat mencari kemunculan string Pola P dalam O(m log n) dengan melakukan pencarian biner pada sufiks-sufiks yang diurutkan untuk menemukan posisi batas bawah (kemunculan pertama P sebagai awalan dari sufiks mana pun dari T) dan posisi batas atas (kemunculan terakhir P sebagai awalan dari sufiks mana pun dari T).
Kompleksitas waktu: O(m log n) dan akan mengembalikan interval dengan ukuran k di mana k adalah jumlah total kemunculan.
Sebagai contoh, pada Array Sufiks dari T = "GATAGACA$" di atas, coba skenario berikut:
P mengembalikan rentang baris: Search("GA"), kemunculan = {4, 0} P mengembalikan satu baris saja: Search("CA"), kemunculan = {2} P tidak ditemukan dalam T: Search("WONKA"), kemunculan = {NIL}
←
→
🕑
Kita dapat menghitung Awalan Umum Terpanjang (LCP) dari dua akhiran yang berdekatan (dalam urutan Larik Akhiran) dalam waktu O(n) menggunakan tiga fase algoritma Kasai. Algoritma ini memanfaatkan bahwa jika kita memiliki LCP yang panjang antara dua akhiran yang berdekatan (dalam urutan Larik Akhiran), LCP panjang tersebut memiliki banyak tumpang tindih dengan akhiran lain dalam urutan posisi ketika karakter pertama dihapus.
Fase pertama: Menghitung nilai Phi[], di mana Phi[SA[i]] = SA[i-1] dalam waktu O(n). Ini untuk membantu algoritma mengetahui dalam waktu O(1) akhiran mana yang berada di belakang Akhiran-SA[i] dalam urutan Larik Akhiran.
Fase kedua: Menghitung nilai PLCP[] antara Akhiran-i dalam urutan posisi dengan Akhiran-Phi[i] (yang berada di belakang Akhiran-i dalam urutan Larik Akhiran). Ketika kita maju ke indeks berikutnya i+1 dalam urutan posisi, kita akan menghapus karakter terdepan dari akhiran, tetapi mungkin mempertahankan banyak nilai LCP antara Akhiran-(i+1) dan Akhiran-Phi[(i+1)]. Teorema PLCP (tidak terbukti) menunjukkan bahwa nilai LCP hanya bisa ditingkatkan hingga n kali, dan dengan demikian hanya bisa dikurangi paling banyak n kali juga, sehingga kompleksitas keseluruhan fase kedua juga O(n).
Fase ketiga: Kami menghitung nilai LCP[], di mana LCP[i] = PLCP[SA[i]] dalam O(n). Nilai LCP ini adalah yang kami gunakan untuk aplikasi Larik Akhiran lainnya nanti.
Kompleksitas waktu: Algoritma Kasai memanfaatkan teorema PLCP di mana jumlah total operasi peningkatan (dan penurunan) nilai LCP paling banyak adalah O(n). Dengan demikian, algoritma Kasai berjalan dalam O(n) secara keseluruhan. Jadi, kombinasi dari konstruksi Larik Akhiran O(n log n) (melalui algoritma Prefix Doubling) dan perhitungan O(n) dari Larik LCP menggunakan algoritma Kasai ini cukup baik untuk menangani hingga n ≤ 200K karakter dalam masalah kompetisi pemrograman yang melibatkan string panjang.
←
→
🕑
Setelah kita membangun Suffix Array dari T dalam O(n log n) dan menghitung larik LCP dalam O(n), kita dapat menemukan Longest Repeated Substring (LRS) dalam T dengan cukup mengiterasi semua nilai LCP dan melaporkan yang terbesar.
Ini karena setiap nilai LCP[i] pada LCP Array berarti prefix terpanjang yang sama antara dua suffix yang berdekatan secara leksikografis: Suffix-i dan Suffix-(i-1). Ini berkaitan dengan simpul internal dari Suffix Tree yang setara dari T yang bercabang ke setidaknya dua (atau lebih) suffix, sehingga prefix yang sama dari suffix yang berdekatan ini berulang.
←
→
🕑
Setelah ita membangun larik akhiran untuk dari penggabungan kedua string T1$T2# dengan panjang n = n1+n2 dalam O(n log n) dan menghitung larik LCPnya dalam O(n), kita bisa mencari Substring Terulang Terpanjang (LRS) dalam T dengan cara mengiterasi semua nilai LCP dan keluarkan nilai terbesar yang muncul dari dua string berbeda.
Cobalah LCS("GATAGACA$", "CATA#") pada larik akhiran dari string T1 = "GATAGACA$" dan T2 = "CATA#". Kita punya LCS = "ATA".
←
→
🕑
Anda dapat menggunakan/memodifikasi kode implementasi kita untuk algoritma cepat Larik Akhiran + LCP: sa_lcp.cpp | py | java | ml untuk menyelesaikan soal kontes pemrograman yang memerlukannya.
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.
←
🕑
X Tutup
Please rotate your device to landscape mode for a better user experience
Please make the window wider for a better user experience
VisuAlgo digagas pada tahun 2011 oleh Associate Professor Steven Halim sebagai alat untuk membantu murid-muridnya mengerti struktur-struktur data dan algoritma-algoritma, dengan memampukan mereka untuk mempelajari dasar-dasarnya secara otodidak dan dengan kecepatan mereka sendiri.
VisuAlgo mempunya banyak algoritma-algoritma tingkat lanjut yang dibahas didalam buku Dr. Steven Halim ('Competitive Programming', yang ditulis bersama adiknya Dr. Felix Halim dan temannya Dr. Suhendry Effendy) dan lebih lagi. Hari ini, beberapa dari visualisasi/animasi algoritma-algoritma tingkat lanjut ini hanya ditemukan di VisuAlgo.
Meskipun pada khususnya didesain untuk murid-murid National University of Singapore (NUS) yang mengambil berbagai kelas-kelas struktur data dan algoritma (contoh: CS1010/setara, CS2040/setara (termasuk IT5003), CS3230, CS3233, dan CS4234), sebagai pendukung pembelajaran online, kami berharap bahwa orang-orang di berbagai belahan dunia menemukan visualisasi-visualisasi di website ini berguna bagi mereka juga.
VisuAlgo tidak didesain untuk layar sentuh kecil (seperti smartphones) dari awalnya karena kami harus membuat banyak visualisasi-visualisasi algoritma kompleks yang membutuhkan banyak pixels dan gestur klik-dan-tarik untuk interaksinya. Resolusi layar minimum untuk pengalaman pengguna yang lumayan adalah 1366x768 dan hanya halaman utama VisuAlgo yang secara relatif lebih ramah dengan layar kecil. Tetapi, kami sedang bereksperimen dengan versi mobil (kecil) dari VisuAlgo yang akan siap pada April 2022.
VisuAlgo adalah proyek yang sedang terus berlangsung dan visualisasi-visualisasi yang lebih kompleks sedang dibuat. Pada saat ini, platform ini mempunyai 24 modul visualisasi.
Perkembangan yang paling menarik adalah pembuatan pertanyaan otomatis (sistem kuis online) yang bisa dipakai oleh murid-murid untuk menguji pengetahuan mereka tentang dasar struktur-struktur data dan algoritma-algoritma. Pertanyaan-pertanyaan dibuat secara acak dengan semacam rumus dan jawaban-jawaban murid-murid dinilai secara instan setelah dikirim ke server penilai kami. Sistem kuis online ini, saat sudah diadopsi oleh banyak dosen Ilmu Komputer diseluruh dunia, seharusnya bisa menghapuskan pertanyaan-pertanyaan dasar tentang struktur data dan algoritma dari ujian-ujian di banyak Universitas. Dengan memberikan bobot kecil (tapi tidak kosong) supaya murid-murid mengerjakan kuis online ini, seorang dosen Ilmu Komputer dapat dengan signifikan meningkatkan penguasaan materi dari murid-muridnya tentang pertanyaan-pertanyaan dasar ini karena murid-murid mempunyai kesempatan untuk menjawab pertanyaan-pertanyaan ini yang bisa dinilai secara instan sebelum mereka mengambil kuis online yang resmi. Mode latihan saat ini mempunyai pertanyaan-pertanyaan untuk 12 modul visualisasi. Kami akan segera menambahkan pertanyaan-pertanyaan untuk 12 modul visualisasi yang lainnya sehingga setiap setiap modul visualisasi di VisuAlgo mempunyai komponen kuis online.
Kami telah menerjemahkan halaman-halaman VisuALgo ke tiga bahasa-bahasa utama: Inggris, Mandarin, dan Indonesia. Saat ini, kami juga telah menulis catatan-catatan publik tentang VisuAlgo dalam berbagai bahasa, termasuk Bahasa Indonesia, Korea, Vietnam, dan Thai:
Pemimpin & Penasihat Proyek (Jul 2011-sekarang) Associate Professor Steven Halim, School of Computing (SoC), National University of Singapore (NUS) Dr Felix Halim, Senior Software Engineer, Google (Mountain View)
Murid-Murid S1 Peniliti 1 CDTL TEG 1: Jul 2011-Apr 2012: Koh Zi Chun, Victor Loh Bo Huai
Murid-Murid Proyek Tahun Terakhir/UROP 1 Jul 2012-Dec 2013: Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy Jun 2013-Apr 2014Rose Marie Tan Zhao Yun, Ivan Reinaldo
Murid-Murid S1 Peniliti 2 CDTL TEG 2: May 2014-Jul 2014: Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu
Murid-Murid Proyek Tahun Terakhir/UROP 2 Jun 2014-Apr 2015: Erin Teo Yi Ling, Wang Zi Jun 2016-Dec 2017: Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir Aug 2021-Apr 2023: Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long, Ting Xiao, Lim Dewen Aloysius
Murid-Murid S1 Peniliti 3 Optiver: Aug 2023-Oct 2023: Bui Hong Duc, Oleh Naver, Tay Ngan Lin
Murid-Murid Proyek Tahun Terakhir/UROP 3 Aug 2023-Apr 2024: Xiong Jingya, Radian Krisno, Ng Wee Han, Tan Chee Heng Aug 2024-Apr 2025: Edbert Geraldy Cangdinata, Huang Xing Chen, Nicholas Patrick
List of translators who have contributed ≥ 100 translations can be found at statistics page.
Ucapan Terima Kasih
Proyek ini dimungkinkan karena Hibah Pengembangan Pengajaran dari NUS Centre for Development of Teaching and Learning (CDTL).
Syarat Guna
✕
VisuAlgo bebas biaya untuk komunitas Ilmu Komputer di dunia. Jika anda menyukai VisuAlgo, satu-satunya "pembayaran" yang kami minta dari anda adalah agar anda menceritakan keberadaan VisuAlgo kepada murid-murid/dosen-dosen Ilmu Komputer. Anda dapat menceritakan tentang VisuAlgo melewati media sosial yang anda tahu lewat postingan Facebook/Twitter/Instagram/TikTok, situs mata kuliah, ulasan di blog, email-email, dsb.
Mahasiswa dan pengajar Struktur Data dan Algoritma (DSA) dipersilakan untuk menggunakan situs web ini langsung untuk kelas mereka. Jika Anda mengambil tangkapan layar atau video dari situs ini, Anda dapat menggunakannya di tempat lain, asalkan mencantumkan URL situs web ini (https://visualgo.net) dan/atau daftar publikasi di bawah sebagai referensi. Namun, harap hindari mengunduh file sisi-klien VisuAlgo dan menghostingnya di situs web Anda, karena ini dianggap sebagai plagiarisme. Saat ini, kami tidak mengizinkan orang lain untuk melakukan fork proyek ini atau membuat varian VisuAlgo. Penggunaan pribadi salinan offline dari sisi-klien VisuAlgo diperbolehkan.
Harap diperhatikan bahwa komponen kuis online VisuAlgo memiliki elemen sisi-server yang substansial, dan tidak mudah menyimpan skrip dan basis data sisi-server secara lokal. Saat ini, publik umum hanya dapat mengakses sistem kuis online melalui 'mode latihan.' 'Mode uji' menawarkan lingkungan yang lebih terkontrol untuk menggunakan pertanyaan yang dihasilkan secara acak dan verifikasi otomatis dalam ujian-ujian nyata di NUS.
Daftar Publikasi
Karya ini telah dipresentasikan singkat pada CLI Workshop sewaktu ACM ICPC World Finals 2012 (Poland, Warsaw) dan pada IOI Conference di IOI 2012 (Sirmione-Montichiari, Italy). Anda bisa mengklik link ini untuk membaca makalah kami tahun 2012 tentang sistem ini (yang belum disebut sebagai VisuAlgo pada tahun 2012 tersebut).
Laporan Bug atau Permintaan Fitur Baru
VisuAlgo bukanlah proyek yang sudah selesai. Associate Professor Steven Halim masih aktif dalam mengembangkan VisuAlgo. Jika anda adalah pengguna VisuAlgo dan menemukan bug di halaman visualisasi/sistem kuis online atau jika anda mau meminta fitur baru, silahkan hubungi Associate Professor Steven Halim. Alamat emailnya adalah gabungan dari namanya dan tambahkan gmail titik com.
Kebijakan Privasi
✕
Versi 1.2 (Dimutakhirkan Jum, 18 Aug 2023). Sejak Jumat, 18 Aug 2023, kami tidak lagi menggunakan Google Analytics. Semua cookie yang kami gunakan sekarang hanya untuk operasi situs web ini. Popup persetujuan cookie yang mengganggu sekarang dimatikan bahkan untuk pengunjung pertama kali. Sejak Jumat, 07 Jun 2023, berkat sumbangan yang murah hati dari Optiver, siapa pun di dunia bisa membuat akun VisuAlgo sendiri untuk menyimpan beberapa pengaturan kustomisasi (seperti mode layout, bahasa default, kecepatan pemutaran, dll). Selain itu, untuk mahasiswa NUS, dengan menggunakan akun VisuAlgo (sebuah tupel dari alamat email NUS resmi, nama murid resmi NUS seperti dalam daftar kelas, dan sebuah kata sandi yang dienkripsi pada sisi server — tidak ada data personal lainnya yang disimpan), anda memberikan ijin kepada dosen modul anda untuk melacak pembacaan slide-slide kuliah maya dan kemajuan latihan kuis online yang dibutuhkan untuk menjalankan modul tersebut dengan lancar. Akun VisuAlgo anda akan juga dibutuhkan untuk mengambil kuis-kuis VisuAlgo online resmi sehingga memberikan kredensial akun anda ke orang lain untuk mengerjakan Kuis Online sebagai anda adalah pelanggaran akademis. Akun pengguna anda akan dihapus setelah modul tersebut selesai kecuali anda memilih untuk menyimpan akun anda (OPT-IN). Akses ke basis data lengkap dari VisuAlgo (dengan kata-kata sandi terenkripsi) dibatasi kepada Prof Halim saja. Untuk dosen-dosen Ilmu Komputer di seluruh dunia yang telah menulis kepada Steven, sebuah akun VisuAlgo (alamat email (bukan-NUS), anda dapat menggunakan nama panggilan apapun, dan kata sandi terenkripsi) dibutuhkan untuk membedakan kredensial online anda dibandingkan dengan orang-orang lain di dunia. Akun anda akan dilacak seperti seorang murid NUS biasa diatas tetapi akun anda akan mempunya fitur-fiture spesifik untuk dosen-dosen Ilmu Komputer, yaitu kemampuan untuk melihat slide-slide tersembunyi yang berisi jawaban-jawaban (menarik) dari pertanyaan-pertanyaan yang dipresentasikan di slide-slide sebelumnya sebelum slide-slide tersembunyi tersebut. Anda juga dapat mengakses setingan Susah dari Kuis-Kuis Online VisuAlgo. Anda dapat dengan bebas menggunakan materi-materia untuk memperkaya kelas-kelas struktur-struktur data dan algoritma-algoritma anda. Catat bahwa mungkin ada fitur-fitur khusus tambahan untuk dosen Ilmu Komputer di masa mendatang. Untuk siapapun dengan akun VisuAlgo, anda dapat membuang akun anda sendiri bila anda tidak mau lagi diasosiasikan dengan tool VisuAlgo ini.
