Gesaan dan masa ia terpakai
Tatasusunan akhiran (suffix array) menyimpan indeks permulaan bagi setiap akhiran, disusun mengikut tertib leksikografi. Apabila satu teks tetap menerima banyak pertanyaan corak, indeks ini mencari padanan tanpa mengimbas semula dari awal. Stanford CS166 meminta calon untuk melaksanakan searchFor, mengembalikan setiap padanan, dan mengambil kira saiz output; di sini m ialah panjang corak, n ialah panjang teks, dan z ialah bilangan hasil.
Perkara yang diuji oleh penemu duga
- Menjelaskan bahawa kemunculan corak ialah akhiran yang awalan (prefix) nya sama dengan corak tersebut.
- Mencari sempadan kiri dan kanan dengan batas bawah (lower bounds) dan bukannya berhenti pada satu padanan.
- Memisahkan kos pembinaan sekali sahaja daripada kos setiap pertanyaan dan mengenakan O(z) untuk output.
- Mengendalikan corak kosong, sentinel, akhiran pendua, dan kos perbandingan aksara.
Penjelasan untuk ditanya terlebih dahulu
- Adakah teks itu tetap dan ditanya berkali-kali? Jika ia sering berubah, membina semula tatasusunan akhiran mungkin tidak sesuai.
- Patutkah jawapan mengembalikan semua permulaan, hanya bilangan, atau sekadar kewujudan?
- Adakah huruf besar/kecil, penormalan Unicode, dan susunan peringkat bait ditakrifkan? Pembanding mestilah sepadan dengan kontrak.
- Adakah tatasusunan akhiran dibekalkan, atau mesti dibina? Jika pembinaan diperlukan, adakah isihan pengajaran boleh diterima atau pembinaan masa linear dijangkakan?
Jawapan 30 saat
"Akhiran diisih, jadi semua akhiran yang bermula dengan pattern membentuk satu selang yang berterusan. Saya membandingkan corak dengan text[sa[i]:] mengikut awalan, menggunakan satu carian binari untuk akhiran pertama yang tidak lebih kecil daripada corak dan satu lagi untuk akhiran pertama yang benar-benar melebihi awalan tersebut. Setiap nilai sa dalam selang adalah padanan, jadi pelaporan menelan belanja O(z) dan pertanyaan ialah O(m log n + z). Mengikut kelaziman, corak kosong mengembalikan n+1 kedudukan."
Penyelesaian langkah demi langkah
Langkah 1: Takrifkan maksud tatasusunan akhiran
Untuk banana, permulaan akhiran dalam susunan leksikografi ialah [5, 3, 1, 0, 4, 2]. Tatasusunan menyimpan integer permulaan, bukan salinan rentetan akhiran. Nota MIT menerangkan dengan tepat indeks leksikografi ini dan penggunaan carian binari.
Langkah 2: Tukar pemadanan kepada selang
Semua akhiran yang bermula dengan ana adalah bersebelahan, jadi jawapannya ialah selang separuh terbuka [left, right). Pembanding memerlukan tiga hasil: awalan akhiran berada di bawah, sama dengan, atau di atas corak. Kesamaan masih perlu mencari ke kiri dan ke kanan untuk menangkap setiap kemunculan.
Langkah 3: Laksanakan dua batas bawah (lower bounds)
Batas bawah pertama meminta awalan akhiran pertama yang tidak berada di bawah corak. Batas bawah kedua meminta awalan akhiran pertama yang secara tegas di atasnya, atau mencari hujung kanan julat yang sama. Membandingkan corak dengan akhiran yang lengkap adalah salah: akhiran yang lebih pendek yang merupakan awalan corak mesti dibandingkan sebagai lebih kecil.
Langkah 4: Pilihan kerumitan dan pembinaan
Dengan tatasusunan akhiran yang dibekalkan, setiap perbandingan memeriksa paling banyak m aksara dan carian binari melakukan O(log n) perbandingan, jadi pertanyaan adalah O(m log n + z). Stanford secara eksplisit memisahkan kos pelaporan O(z). Binaan pengajaran boleh mengisih hirisan (slices) akhiran, tetapi ia menyalin data dan perlahan; pengeluaran harus menggunakan penggandaan awalan (prefix doubling), SA-IS, atau pustaka yang disahkan. Bahan MIT dan Stanford meletakkan tatasusunan akhiran sebagai indeks teks tetap yang menjimatkan ruang penunjuk yang besar berbanding pokok akhiran (suffix tree).
Pelaksanaan Python yang boleh dilaksanakan
def build_suffix_array(text):
# Teaching build for verification, not a production complexity claim.
return sorted(range(len(text)), key=lambda start: text[start:])
def compare_suffix_prefix(text, start, pattern):
suffix = text[start:]
prefix = suffix[:len(pattern)]
if prefix < pattern:
return -1
if prefix > pattern:
return 1
if len(suffix) < len(pattern):
return -1
return 0
def search_with_suffix_array(text, suffix_array, pattern):
if pattern == "":
return list(range(len(text) + 1))
def lower_bound(strict):
lo, hi = 0, len(suffix_array)
while lo < hi:
mid = (lo + hi) // 2
cmp = compare_suffix_prefix(text, suffix_array[mid], pattern)
take_right = cmp < 0 or (strict and cmp == 0)
if take_right:
lo = mid + 1
else:
hi = mid
return lo
left = lower_bound(strict=False)
right = lower_bound(strict=True)
return sorted(suffix_array[left:right])Kod ini memisahkan pembinaan dan pertanyaan. Isihan akhir mengembalikan permulaan mengikut susunan teks; abaikan jika susunan tatasusunan akhiran ialah kontrak API. Teks kosong, corak kosong, tiada padanan, dan padanan berulang adalah kes ujian langsung.
Contoh jawapan berkualiti tinggi
"Saya terlebih dahulu mengesahkan bahawa teks adalah tetap dan menerima banyak corak, kemudian menyimpan setiap permulaan akhiran dalam susunan leksikografi. Memandangkan satu corak ialah awalan sepunya bagi akhiran yang sepadan, semua jawapan menduduki julat yang berterusan. Dua batas bawah mencari julat tersebut; perbandingan hanya memeriksa panjang corak dan menganggap akhiran yang lebih pendek sebagai lebih kecil. Diberi tatasusunan, pertanyaan ialah O(m log n + z), dengan z ialah output. Pembinaan pendidikan boleh menggunakan pengisihan, tetapi indeks yang besar memerlukan penggandaan awalan, SA-IS, atau pelaksanaan yang disahkan, dengan dasar penormalan aksara yang ditetapkan."
Kesilapan biasa
- Mengembalikan padanan pertama → kemunculan bersebelahan terlepas → carian binari kedua-dua sempadan.
- Membandingkan rentetan akhiran lengkap dengan corak → sempadan akhiran pendek salah → takrifkan perbandingan awalan dan peraturan akhiran yang lebih pendek.
- Mengenakan kos pembinaan pada setiap pertanyaan → senario teks tetap tidak dijelaskan → laporkan binaan sekali sahaja dan kos setiap pertanyaan secara berasingan.
- Memanggil selang tatasusunan akhiran sebagai susunan teks → pemanggil melihat susunan yang tidak stabil → isih permulaan apabila diperlukan atau dokumentasikan susunannya.
- Melupakan kedudukan n+1 bagi corak kosong → kontrak yang dinyatakan dilanggar → kendalikan corak kosong terlebih dahulu.
Soalan susulan dan respons yang mantap
Bagaimanakah anda mengurangkan perbandingan aksara berulang untuk corak yang panjang?
Tambah maklumat LCP (Longest Common Prefix) untuk akhiran berjiran dan gunakan semula awalan sepunya yang diketahui semasa carian binari. Ini boleh mendekati O(m + log n), tetapi ia memerlukan keadaan LCP tambahan dan invarian yang lebih kukuh; tanpanya, nyatakan O(m log n) dengan jujur.
Adakah anda akan menggunakan tatasusunan akhiran jika teks sering berubah?
Bukan sebagai satu indeks statik. Pembinaan semula secara kelompok (batch rebuilds), indeks peringkat segmen dengan cantuman kemudian, atau pemadan dalam talian (online matcher) mungkin lebih sesuai. Pilih berdasarkan kadar kemas kini, volum pertanyaan, dan kelewatan pembinaan semula yang boleh diterima.
Bagaimanakah anda menguji bahawa sempadan carian binari adalah betul?
Bandingkan dengan imbasan brute-force pada teks dan corak kecil rawak. Sertakan corak kosong, aksara berulang, corak lebih panjang daripada teks, tiada padanan, dan setiap kedudukan sepadan. Pastikan (assert) bahawa kedudukan berjiran di luar julat gagal dalam predikat awalan.
Mengapa tidak menggunakan KMP secara terus?
Untuk satu corak dan satu laluan ke atas teks, KMP lebih mudah pada O(n+m). Tatasusunan akhiran memberi manfaat untuk banyak corak pada teks tetap dan untuk operasi luar talian yang melibatkan subrentetan berulang, LCP, atau BWT.