Dapatkah pohon Suffix digunakan untuk menemukan semua substring yang umum?

Saya mencoba menggunakan pohon sufiks untuk membandingkan urutan string. Saya telah menemukan implementasi / teori untuk masalah sub string umum terpanjang menggunakan pohon suffix. Namun, apa yang saya cari adalah diskusi tentang masalah terkait - "semua substring umum". Secara khusus, saya memiliki masalah di mana saya harus terlebih dahulu menemukan substring umum terpanjang, kemudian menemukan substring umum terpanjang berikutnya yang tidak termasuk indeks lcs yang sudah ditemukan, dan seterusnya hingga panjang minimum. Apakah masalah ini dapat diselesaikan dengan membangun pohon sufiks Generalized (GST) hanya sekali untuk dua urutan. Saya tahu ini bisa diselesaikan dengan berulang kali membangun GST setelah setiap iterasi untuk menemukan dan menghapus LCS. Tapi, saya bertanya-tanya apakah saya melewatkan trik rapi di mana di GST dibangun hanya sekali.

Ya, pohon sufiks dapat digunakan untuk menemukan semua substring umum. Saya akan mengatakan untuk menggunakan array sufiks sebagai gantinya, tetapi jika Anda sudah memiliki pohon sufiks, membangun array sufiks dari pohon sufiks membutuhkan waktu linier oleh DFS. Jadi sisa jawaban saya akan menganggap kita bekerja dengan array suffix.

Diberikan teks , array suffix untuk adalah array bilangan bulat dari hingga menentukan urutan leksikografis dari sufiks dari string $ S 0 n n + 1 $S = s_1 , ..., s_n$$S$$0$$n$$n+1$$S$

Kami ingin memasangkan susunan sufiks dengan , awalan umum terpanjang. Kita dapat membuat susunan dalam waktu linier seperti yang disebutkan dalam makalah oleh Kasai et al . Susunan sufiks dan susunan lcp mereka berbaris bersama-sama dengan cara yang memberikan indeks ke dalam susunan lcp, katakan mana adalah nomor indeks, maka akan menjadi awal dari satu instance dari substring umum dan akan menjadi indeks awal dari instance kedua. Panjangnya tentu saja nilai dalam lcp array.L C P s l c p [ k ] k s a [ k ] s a [ k - 1 $LCPs$$LCPs$$lcp[k]$$k$$sa[k]$$sa[k-1]$

Saya punya ide yang mungkin berhasil. Kita mulai dengan pohon akhiran umum untuk urutan dan . Setiap node internal dengan akhiran dan dalam subtreenya sesuai dengan beberapa substring umum dari urutan. Mari kita sebut simpul seperti itu non-sepele. Substring yang umum adalah maksimal, jika simpul yang sesuai tidak memiliki anak yang tidak sepele. Jika simpul adalah non-trivial, kami menyimpan kedalaman string terbesar dari simpul non-trivial di subtree-nya sebagai . Jika adalah akar, maka adalah panjang substring umum terpanjang dan .T S T V l c s ( v ) r l c s ( r ) S $S$$T$$S$$T$$v$$lcs(v)$$r$$lcs(r)$$S$$T$

Memperbarui pohon setelah menghapus substring dari salah satu urutan seharusnya tidak terlalu sulit. Kami terlebih dahulu menghapus daun yang sesuai dengan sufiks yang dihapus, memperbarui leluhur mereka bila diperlukan. Kemudian kami mulai memproses sufiks sebelum substring yang dihapus. Biarkan menjadi leluhur non-sepele terendah dari daun saat ini. Jika panjang akhiran adalah (kita adalah langkah dari penghapusan) dan , kita harus memindahkan akhiran ke posisi yang tepat di pohon, memperbarui leluhur saat diperlukan. Jika , kita selesai, karena kita tidak tertarik pada subpohon dengan akar sepele.k k k < l c s ( v ) k ≥ l c s ( v $v$$k$$k$$k < lcs(v)$$k \ge lcs(v)$

Algoritma keseluruhan berulang kali menemukan substring umum terpanjang dari dan dan menghapus salah satu kemunculannya dari kedua sekuens, selama panjang LCS cukup besar.$S$$T$

Ada beberapa hal teknis, tetapi ide umumnya harus bekerja.

Mulailah dengan teks bersambung S $ T , di mana $ terjadi tempat di * atau T . Bangun pohon akhiran / array dari teks ini. Sangat mudah sekarang untuk menelusuri struktur data akhiran ini untuk mengumpulkan semua pengulangan maksimal yang tepat. Dengan memeriksa konteks kiri, filter keluar pengulangan maksimal non-kiri. Pemfilteran ke kiri ini dapat diimplementasikan menggunakan tabel Burrows-Wheeler seperti pada Abouelhoda et al, meskipun saya tidak percaya bahwa ini perlu. Pengulangan hanya terjadi di S atau hanya di Tharusnya dihilangkan pada saat ini. Pengulangan yang belum dihilangkan kemudian dimasukkan ke dalam antrian prioritas, dengan prioritas ditentukan oleh panjang. Setelah traversal, karena pengulangan yang direkam dihapus dari prioritas, pemfilteran akhir (untuk penahanan substring) dapat dilakukan. Mengingat penggunaan frasa maksimal, bagaimanapun, saya menduga bahwa sangat sedikit penyaringan ini diperlukan.

Algoritma ini adalah penemuan saya sendiri. Saya tidak akan menggolongkannya sebagai sangat pintar, tetapi harus berhasil.

Solusi yang sangat sederhana: Bangun pohon suffix untuk string pertama, , dan beri anotasi semua node dengan . Kemudian masukkan semua akhiran dari string kedua, . Buat anotasi node yang Anda lewati atau ciptakan dengan . Label jalur untuk setiap node yang dijelaskan dengan baik dan adalah substring dari kedua dan . (Lihat, misalnya, catatan kuliah ini pencarian web cepat muncul.)s T t s t S $S$$s$$T$$t$$s$$t$$S$$T$