Algoritma akhiran pohon Ukkonen dalam bahasa Inggris

Saya merasa agak tebal pada saat ini. Saya telah menghabiskan waktu berhari-hari untuk membungkus sepenuhnya kepala saya di sekitar konstruksi pohon suffix, tetapi karena saya tidak memiliki latar belakang matematika, banyak penjelasan yang menghindarkan saya ketika mereka mulai menggunakan simbologi matematika secara berlebihan. Yang paling dekat dengan penjelasan yang baik yang saya temukan adalah Pencarian String Cepat Dengan Suffix Trees , tetapi ia membahas berbagai poin dan beberapa aspek algoritma tetap tidak jelas.

Penjelasan langkah-demi-langkah dari algoritma ini di sini di Stack Overflow akan sangat berharga bagi banyak orang lain selain saya, saya yakin.

Untuk referensi, inilah makalah Ukkonen tentang algoritme: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Pemahaman dasar saya, sejauh ini:

• Saya perlu mengulangi setiap awalan P dari string T yang diberikan
• Saya perlu beralih melalui setiap akhiran S di awalan P dan menambahkannya ke pohon
• Untuk menambahkan akhiran S ke pohon, saya harus mengulangi setiap karakter dalam S, dengan iterasi yang terdiri dari berjalan menuruni cabang yang ada yang dimulai dengan set karakter C yang sama di S dan berpotensi memecah tepi menjadi node yang menurun ketika saya mencapai karakter yang berbeda di akhiran, ATAU jika tidak ada tepi yang cocok untuk berjalan. Ketika tidak ada tepi yang cocok untuk C, tepi daun baru dibuat untuk C.

Algoritma dasar tampaknya O (n ² ), seperti yang ditunjukkan dalam sebagian besar penjelasan, karena kita perlu melangkah melalui semua awalan, maka kita perlu melangkah melalui masing-masing sufiks untuk setiap awalan. Algoritma Ukkonen tampaknya unik karena teknik pointer suffix yang ia gunakan, meskipun saya pikir itulah yang saya kesulitan pahami.

Saya juga kesulitan memahami:

• kapan dan bagaimana "titik aktif" ditetapkan, digunakan, dan diubah
• apa yang terjadi dengan aspek kanonisasi algoritma
• Mengapa implementasi yang saya lihat perlu "memperbaiki" variabel terikat yang mereka gunakan

Berikut adalah kode sumber C # yang lengkap . Ini tidak hanya bekerja dengan benar, tetapi mendukung kanonisasi otomatis dan membuat grafik teks yang lebih bagus dari output. Kode sumber dan output sampel ada di:

https://gist.github.com/2373868

Perbarui 2017-11-04

Setelah bertahun-tahun saya telah menemukan penggunaan baru untuk pohon sufiks, dan telah menerapkan algoritma dalam JavaScript . Intinya di bawah. Itu harus bebas bug. Buang ke file js, npm install chalkdari lokasi yang sama, dan kemudian jalankan dengan node.js untuk melihat beberapa output berwarna. Ada versi yang dilucuti di Gist yang sama, tanpa ada kode debug.

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6

Berikut ini adalah upaya untuk menggambarkan algoritma Ukkonen dengan terlebih dahulu menunjukkan apa yang dilakukannya ketika string sederhana (yaitu tidak mengandung karakter yang berulang), dan kemudian memperluasnya ke algoritma penuh.

Pertama, beberapa pernyataan pendahuluan.

1. Apa yang kami bangun, pada dasarnya seperti pencarian trie. Jadi ada simpul root, ujung keluar dari itu mengarah ke simpul baru, dan ujung lebih lanjut keluar dari itu, dan sebagainya

2. Tetapi : Tidak seperti dalam trie pencarian, label tepi bukan karakter tunggal. Sebagai gantinya, setiap sisi diberi label menggunakan sepasang bilangan bulat [from,to]. Ini adalah petunjuk ke dalam teks. Dalam pengertian ini, setiap sisi membawa label string yang panjangnya sewenang-wenang, tetapi hanya membutuhkan ruang O (1) (dua pointer).

Prinsip dasar

Pertama-tama saya ingin menunjukkan bagaimana membuat pohon sufiks dari string yang sangat sederhana, string tanpa karakter berulang:

abc

Algoritma ini bekerja dalam beberapa langkah, dari kiri ke kanan . Ada satu langkah untuk setiap karakter string . Setiap langkah mungkin melibatkan lebih dari satu operasi individu, tetapi kita akan melihat (lihat pengamatan terakhir di akhir) bahwa jumlah total operasi adalah O (n).

Jadi, kita mulai dari kiri , dan pertama-tama masukkan hanya karakter tunggal adengan membuat tepi dari simpul akar (di sebelah kiri) ke daun, dan memberi label sebagai [0,#], yang berarti tepi mewakili substring mulai dari posisi 0 dan berakhir. di akhir saat ini . Saya menggunakan simbol #untuk maksud akhir saat ini , yang berada di posisi 1 (tepat setelah a).

Jadi kita memiliki pohon awal, yang terlihat seperti ini:

Dan apa artinya ini:

Sekarang kita maju ke posisi 2 (tepat setelah b). Tujuan kami di setiap langkah adalah untuk memasukkan semua sufiks hingga posisi saat ini . Kami melakukan ini dengan

• memperluas batas yang ada akeab
• memasukkan satu tepi baru untuk b

Dalam representasi kami seperti ini

Dan artinya adalah:

Kami mengamati dua hal:

• Tepi representasi untuk abadalah sama seperti dulu berada di pohon awal: [0,#]. Artinya telah berubah secara otomatis karena kami memperbarui posisi saat ini #dari 1 ke 2.
• Setiap tepi mengkonsumsi O (1) ruang, karena hanya terdiri dari dua petunjuk ke dalam teks, terlepas dari berapa banyak karakter yang diwakilinya.

Selanjutnya kita menambah posisi lagi dan memperbarui pohon dengan menambahkan a cke setiap tepi yang ada dan memasukkan satu tepi baru untuk akhiran baru c.

Dalam representasi kami seperti ini

Dan artinya adalah:

Kami mengamati:

• Pohon adalah pohon akhiran yang benar hingga ke posisi saat ini setelah setiap langkah
• Ada banyak langkah sebanyak karakter dalam teks
• Jumlah pekerjaan di setiap langkah adalah O (1), karena semua tepi yang ada diperbarui secara otomatis dengan menambah #, dan memasukkan satu tepi baru untuk karakter akhir dapat dilakukan dalam waktu O (1). Karenanya untuk string dengan panjang n, hanya O (n) waktu yang diperlukan.

Ekstensi pertama: pengulangan sederhana

Tentu saja ini berfungsi dengan baik hanya karena string kami tidak mengandung pengulangan. Kami sekarang melihat string yang lebih realistis:

abcabxabcd

Dimulai dengan abcseperti pada contoh sebelumnya, kemudian abdiulangi dan diikuti oleh x, dan kemudian abcdiulangi diikuti oleh d.

Langkah 1 hingga 3: Setelah 3 langkah pertama kita memiliki pohon dari contoh sebelumnya:

Langkah 4: Kami pindah #ke posisi 4. Ini secara implisit memperbarui semua tepi yang ada ke ini:

dan kita perlu memasukkan akhiran akhir dari langkah saat ini a,, di root.

Sebelum kita melakukan ini, kita memperkenalkan dua variabel lagi (di samping #), yang tentu saja telah ada sepanjang waktu tetapi kita belum menggunakannya sejauh ini:

• Titik aktif , yang merupakan tripel (active_node,active_edge,active_length)
• Itu remainder, yang merupakan bilangan bulat yang menunjukkan berapa banyak sufiks baru yang perlu kita masukkan

Arti yang tepat dari keduanya akan segera menjadi jelas, tetapi untuk sekarang katakan saja:

• Dalam abccontoh sederhana , titik aktif selalu (root,'\0x',0), yaitu active_nodesimpul akar, active_edgeditentukan sebagai karakter nol '\0x', dan active_lengthnol. Efek dari ini adalah bahwa satu tepi baru yang kami masukkan di setiap langkah dimasukkan di simpul akar sebagai tepi yang baru dibuat. Kami akan segera melihat mengapa triple diperlukan untuk mewakili informasi ini.
• Itu remainderselalu diatur ke 1 pada awal setiap langkah. Arti dari ini adalah bahwa jumlah sufiks yang harus kita sisipkan secara aktif pada akhir setiap langkah adalah 1 (selalu hanya karakter akhir).

Sekarang ini akan berubah. Ketika kita memasukkan karakter akhir saat adi akar, kami melihat bahwa sudah ada tepi keluar dimulai dengan a, khususnya: abca. Inilah yang kami lakukan dalam kasus seperti itu:

• Kami tidak memasukkan tepi baru [4,#]di simpul akar. Sebagai gantinya, kami hanya memperhatikan bahwa sufiks asudah ada di pohon kami. Itu berakhir di tengah-tengah tepi yang lebih panjang, tetapi kita tidak terganggu oleh itu. Kami hanya membiarkan hal-hal seperti apa adanya.
• Kami mengatur titik aktif ke (root,'a',1). Itu berarti titik aktif sekarang berada di suatu tempat di tengah tepi keluar dari simpul akar yang dimulai dengan a, khususnya, setelah posisi 1 di tepi itu. Kami perhatikan bahwa edge ditentukan hanya dengan karakter pertama a. Itu sudah cukup karena hanya ada satu sisi dimulai dengan karakter tertentu (pastikan bahwa ini benar setelah membaca seluruh deskripsi).
• Kami juga menambah remainder, jadi pada awal langkah selanjutnya akan menjadi 2.

Pengamatan: Ketika akhiran terakhir yang perlu kita masukkan ternyata sudah ada di pohon , pohon itu sendiri tidak berubah sama sekali (kita hanya memperbarui titik aktif dan remainder). Pohon kemudian bukan representasi akurat dari pohon sufiks hingga posisi saat ini lagi, tetapi mengandung semua sufiks (karena sufiks akhir aterkandung secara implisit ). Oleh karena itu, selain memperbarui variabel (yang semuanya memiliki panjang tetap, jadi ini adalah O (1)), tidak ada pekerjaan yang dilakukan dalam langkah ini.

Langkah 5: Kami memperbarui posisi saat ini #ke 5. Ini secara otomatis memperbarui pohon ke ini:

Dan karena remainder2 , kita perlu memasukkan dua sufiks akhir dari posisi saat ini: abdan b. Ini pada dasarnya karena:

• The aakhiran dari langkah sebelumnya tidak pernah dimasukkan dengan benar. Jadi itu tetap , dan karena kita telah maju satu langkah, sekarang telah berkembang dari ake ab.
• Dan kita perlu memasukkan tepi akhir yang baru b.

Dalam prakteknya ini berarti bahwa kita pergi ke titik aktif (yang menunjuk ke belakang apada apa yang sekarang abcabtepi), dan masukkan karakter terakhir saat ini b. Tetapi: Sekali lagi, ternyata itu bjuga sudah ada di tepi yang sama.

Jadi, sekali lagi, kita tidak mengubah pohon itu. Kami hanya:

• Perbarui titik aktif ke (root,'a',2)(simpul dan tepi yang sama seperti sebelumnya, tapi sekarang kami arahkan ke belakang b)
• Tambahkan remainderke 3 karena kami masih belum memasukkan tepi akhir dengan benar dari langkah sebelumnya, dan kami juga tidak memasukkan tepi akhir saat ini.

Untuk menjadi jelas: Kami harus memasukkan abdan bdalam langkah saat ini, tetapi karena absudah ditemukan, kami memperbarui titik aktif dan bahkan tidak mencoba untuk memasukkan b. Mengapa? Karena jika abada di pohon, setiap sufiksnya (termasuk b) juga harus ada di pohon. Mungkin hanya secara implisit , tetapi pasti ada di sana, karena cara kita membangun pohon sejauh ini.

Kami melanjutkan ke langkah 6 dengan menambah #. Pohon secara otomatis diperbarui ke:

Karena remainder3 , kita harus memasukkan abx, bxdan x. Titik aktif memberitahu kita di mana abujungnya, jadi kita hanya perlu melompat ke sana dan memasukkan x. Memang, xbelum ada di sana, jadi kami membagi abcabxtepi dan memasukkan simpul internal:

Representasi tepi masih pointer ke teks, jadi membelah dan menyisipkan simpul internal dapat dilakukan dalam O (1) waktu.

Jadi kita telah berurusan dengan abxdan mengurangi remainderke 2. Sekarang kita perlu memasukkan akhiran yang tersisa berikutnya bx,. Tetapi sebelum kita melakukan itu kita perlu memperbarui titik aktif. Aturan untuk ini, setelah membelah dan memasukkan tepi, akan disebut Aturan 1 di bawah, dan itu berlaku setiap kali active_noderoot (kita akan belajar aturan 3 untuk kasus-kasus lain lebih lanjut di bawah). Ini aturan 1:

Setelah penyisipan dari root,

• active_node tetap root
• active_edge diatur ke karakter pertama dari suffix baru yang perlu kita masukkan, yaitu b
• active_length berkurang sebesar 1

Oleh karena itu, triple-point aktif baru (root,'b',1)menunjukkan bahwa sisipan berikutnya harus dibuat di bcabxtepi, di belakang 1 karakter, yaitu di belakang b. Kami dapat mengidentifikasi titik penyisipan dalam waktu O (1) dan memeriksa apakah xsudah ada atau belum. Jika itu ada, kita akan mengakhiri langkah saat ini dan meninggalkan semuanya apa adanya. Tetapi x tidak ada, jadi kami menyisipkannya dengan membelah tepi:

Sekali lagi, ini membutuhkan waktu O (1) dan kami memperbarui remainderke 1 dan titik aktif (root,'x',0)sebagai aturan 1 menyatakan.

Tetapi ada satu hal lagi yang perlu kita lakukan. Kami akan menyebut Aturan 2 ini:

Jika kita membagi tepi dan menyisipkan simpul baru, dan jika itu bukan simpul pertama yang dibuat selama langkah saat ini, kita menghubungkan simpul yang sebelumnya dimasukkan dan simpul baru melalui penunjuk khusus, tautan akhiran . Kita nanti akan melihat mengapa itu berguna. Inilah yang kami dapatkan, tautan suffix direpresentasikan sebagai tepi bertitik:

Kita masih harus memasukkan akhiran akhir dari langkah saat ini x,. Karena active_lengthkomponen dari node aktif telah jatuh ke 0, masukkan terakhir dibuat di root secara langsung. Karena tidak ada tepi keluar pada simpul akar dimulai dengan x, kami menyisipkan tepi baru:

Seperti yang bisa kita lihat, pada langkah saat ini semua sisipan yang tersisa dibuat.

Kami melanjutkan ke langkah 7 dengan menetapkan #= 7, yang secara otomatis menambahkan karakter berikutnya a, ke semua tepi daun, seperti biasa. Kemudian kami mencoba untuk memasukkan karakter akhir yang baru ke titik aktif (root), dan ternyata sudah ada. Jadi kami mengakhiri langkah saat ini tanpa memasukkan apa pun dan memperbarui titik aktif ke (root,'a',1).

Pada langkah 8 , #= 8, kami menambahkan b, dan seperti yang terlihat sebelumnya, ini hanya berarti kami memperbarui titik aktif (root,'a',2)dan kenaikan remaindertanpa melakukan hal lain, karena bsudah ada. Namun, kami perhatikan (dalam O (1) waktu) bahwa titik aktif sekarang di ujung suatu tepi. Kami mencerminkan ini dengan mengatur ulang untuk (node1,'\0x',0). Di sini, saya gunakan node1untuk merujuk ke simpul internal yang abujungnya di.

Kemudian, pada langkah #= 9 , kita perlu memasukkan 'c' dan ini akan membantu kita untuk memahami trik terakhir:

Ekstensi kedua: Menggunakan tautan sufiks

Seperti biasa, #pembaruan ditambahkan csecara otomatis ke tepi daun dan kami pergi ke titik aktif untuk melihat apakah kami dapat memasukkan 'c'. Ternyata 'c' sudah ada di tepi itu, jadi kami mengatur titik aktif ke (node1,'c',1), kenaikan remainderdan tidak melakukan hal lain.

Sekarang dalam langkah #= 10 , remainderadalah 4, dan jadi kita pertama-tama harus memasukkan abcd(yang tersisa dari 3 langkah yang lalu) dengan memasukkan dpada titik aktif.

Mencoba memasukkan dpada titik aktif menyebabkan tepi terbelah dalam waktu O (1):

Tanda active_node, dari mana perpecahan dimulai, ditandai dengan warna merah di atas. Inilah aturan terakhir, Aturan 3:

Setelah memisahkan tepi dari active_nodeyang bukan simpul root, kita mengikuti tautan suffix yang keluar dari simpul itu, jika ada, dan mengatur ulang active_nodeke simpul yang ditunjuknya. Jika tidak ada tautan suffix, kami atur active_nodeke root. active_edge dan active_lengthtetap tidak berubah.

Jadi titik aktifnya sekarang (node2,'c',1), dan node2ditandai dengan warna merah di bawah:

Karena penyisipan abcdselesai, kami mengurangi remainderke 3 dan mempertimbangkan akhiran yang tersisa dari langkah saat ini bcd,. Aturan 3 telah mengatur titik aktif ke simpul dan tepi yang tepat sehingga menyisipkan bcddapat dilakukan dengan hanya memasukkan karakter terakhir dpada titik aktif.

Melakukan hal ini menyebabkan pemisahan tepi yang lain, dan karena aturan 2 , kita harus membuat tautan sufiks dari simpul yang sebelumnya dimasukkan ke yang baru:

Kami amati: Tautan sufiks memungkinkan kami untuk mereset titik aktif sehingga kami dapat membuat sisipan berikutnya yang tersisa pada upaya O (1). Lihatlah grafik di atas untuk mengkonfirmasi bahwa memang simpul di label abterhubung ke simpul di b(akhiran), dan simpul di abcterhubung ke bc.

Langkah saat ini belum selesai. remaindersekarang 2, dan kita harus mengikuti aturan 3 untuk mengatur ulang titik aktif lagi. Karena saat ini active_node(merah di atas) tidak memiliki tautan suffix, kami reset ke root. Titik aktifnya sekarang (root,'c',1).

Oleh karena itu insert berikutnya terjadi pada salah satu ujung keluar dari simpul akar yang dimulai label dengan c: cabxabcd, di belakang karakter pertama, yaitu di belakang c. Ini menyebabkan perpecahan lain:

Dan karena ini melibatkan pembuatan simpul internal baru, kami mengikuti aturan 2 dan menetapkan tautan akhiran baru dari simpul internal yang dibuat sebelumnya:

(Saya menggunakan Graphviz Dot untuk grafik kecil ini. Tautan akhiran baru menyebabkan dot untuk mengatur ulang tepi yang ada, jadi periksa dengan hati-hati untuk mengonfirmasi bahwa satu-satunya hal yang dimasukkan di atas adalah tautan akhiran baru.)

Dengan ini, remainderdapat diatur ke 1 dan karena active_noderoot, kami menggunakan aturan 1 untuk memperbarui titik aktif (root,'d',0). Ini berarti sisipan terakhir dari langkah saat ini adalah menyisipkan satu d di root:

Itu adalah langkah terakhir dan kita selesai. Namun ada beberapa pengamatan terakhir :

• Di setiap langkah kita bergerak #maju dengan 1 posisi. Ini secara otomatis memperbarui semua simpul daun dalam waktu O (1).

• Tapi itu tidak berurusan dengan a) sufiks yang tersisa dari langkah sebelumnya, dan b) dengan karakter terakhir dari langkah saat ini.

• remaindermemberi tahu kami berapa banyak sisipan tambahan yang perlu kami buat. Sisipan ini sesuai satu-ke-satu dengan sufiks akhir dari string yang berakhir pada posisi saat ini #. Kami mempertimbangkan satu demi satu dan membuat sisipan. Penting: Setiap penyisipan dilakukan dalam waktu O (1) karena titik aktif memberi tahu kami ke mana harus pergi, dan kami hanya perlu menambahkan satu karakter pada titik aktif. Mengapa? Karena karakter lain terkandung secara implisit (jika tidak, titik aktif tidak akan berada di tempat itu).

• Setelah setiap sisipan seperti itu, kami mengurangi remainderdan mengikuti tautan akhiran jika ada. Jika tidak kita pergi ke root (aturan 3). Jika kita sudah di root, kita memodifikasi titik aktif menggunakan aturan 1. Dalam hal apa pun, hanya butuh O (1) waktu.

• Jika, selama salah satu sisipan ini, kami menemukan bahwa karakter yang ingin kami sisipkan sudah ada di sana, kami tidak melakukan apa pun dan mengakhiri langkah saat ini, bahkan jika remainder> 0. Alasannya adalah bahwa setiap sisipan yang tersisa akan menjadi sufiks dari yang baru saja kami coba buat. Karenanya mereka semua tersirat di pohon saat ini. Fakta bahwa remainder> 0 memastikan kita berurusan dengan sufiks yang tersisa nanti.

• Bagaimana jika di akhir algoritma remainder> 0? Ini akan menjadi kasus setiap kali akhir teks adalah substring yang terjadi di suatu tempat sebelumnya. Dalam hal ini kita harus menambahkan satu karakter tambahan di akhir string yang belum pernah terjadi sebelumnya. Dalam literatur, biasanya tanda dolar $digunakan sebagai simbol untuk itu. Mengapa itu penting? -> Jika nanti kita menggunakan pohon sufiks yang sudah selesai untuk mencari sufiks, kita harus menerima kecocokan hanya jika berakhir dengan selembar daun . Kalau tidak, kita akan mendapatkan banyak korek api palsu, karena ada banyak string yang secara implisit terkandung di dalam pohon yang bukan sufiks aktual dari string utama. Memaksaremaindermenjadi 0 di akhir pada dasarnya adalah cara untuk memastikan bahwa semua sufiks berakhir pada simpul daun. Namun, jika kita ingin menggunakan pohon untuk mencari substring umum , tidak hanya sufiks dari string utama, langkah terakhir ini memang tidak diperlukan, seperti yang disarankan oleh komentar OP di bawah ini.

• Jadi apa kompleksitas dari keseluruhan algoritma? Jika panjang teks n karakter, jelas ada n langkah (atau n +1 jika kita menambahkan tanda dolar). Dalam setiap langkah, kami tidak melakukan apa pun (selain memperbarui variabel), atau kami membuat remaindersisipan, masing-masing mengambil O (1) waktu. Karena remaindermenunjukkan berapa kali kita tidak melakukan apa pun pada langkah sebelumnya, dan dikurangi untuk setiap sisipan yang kita buat sekarang, jumlah total kali kita melakukan sesuatu adalah tepat n (atau n +1). Karenanya, kompleksitas totalnya adalah O (n).

• Namun, ada satu hal kecil yang tidak saya jelaskan dengan benar: Bisa saja kita mengikuti tautan sufiks, memperbarui titik aktif, dan kemudian menemukan bahwa active_lengthkomponennya tidak bekerja dengan baik dengan yang baru active_node. Sebagai contoh, pertimbangkan situasi seperti ini:

(Garis putus-putus menunjukkan sisa pohon. Garis putus-putus adalah tautan sufiks.)

Sekarang biarkan titik aktifnya (red,'d',3), jadi itu menunjuk ke tempat di belakang fdi defgtepi. Sekarang asumsikan kita telah melakukan pembaruan yang diperlukan dan sekarang ikuti tautan akhiran untuk memperbarui titik aktif sesuai aturan 3. Titik aktif baru adalah (green,'d',3). Namun, d-edge yang keluar dari simpul hijau adalah de, sehingga hanya memiliki 2 karakter. Untuk menemukan titik aktif yang benar, kita jelas perlu mengikuti ujung itu ke titik biru dan mengatur ulang ke (blue,'f',1).

Dalam kasus yang sangat buruk, active_lengthbisa sebesar remainder, yang bisa sebesar n. Dan mungkin sekali terjadi bahwa untuk menemukan titik aktif yang benar, kita tidak hanya perlu melompati satu simpul internal, tetapi mungkin banyak, hingga n dalam kasus terburuk. Apakah itu berarti algoritme memiliki kompleksitas O (n ² ) yang tersembunyi , karena pada setiap langkah remainderumumnya O (n), dan penyesuaian pasca ke simpul aktif setelah mengikuti tautan sufiks bisa juga O (n)?

Tidak. Alasannya adalah jika memang kita harus menyesuaikan titik aktif (misalnya dari hijau ke biru seperti di atas), itu membawa kita ke simpul baru yang memiliki tautan sufiks sendiri, dan active_lengthakan dikurangi. Saat kami mengikuti rantai suffix kami membuat sisipan yang tersisa, active_lengthhanya bisa berkurang, dan jumlah penyesuaian titik aktif yang dapat kami buat di jalan tidak bisa lebih besar daripada active_lengthpada waktu tertentu. Karena active_lengthtidak pernah bisa lebih besar dari remainder, dan remainder O (n) tidak hanya di setiap langkah, tetapi jumlah total kenaikan yang pernah dibuat remainderselama seluruh proses adalah O (n) juga, jumlah penyesuaian titik aktif adalah juga dibatasi oleh O (n).

Saya mencoba menerapkan Pohon Sufiks dengan pendekatan yang diberikan dalam jawaban jogojapan, tetapi tidak berhasil untuk beberapa kasus karena kata-kata yang digunakan untuk aturan. Selain itu, saya telah menyebutkan bahwa tidak ada yang berhasil menerapkan pohon sufiks yang benar-benar benar menggunakan pendekatan ini. Di bawah ini saya akan menulis "ikhtisar" dari jawaban jogojapan dengan beberapa modifikasi pada aturan. Saya juga akan menjelaskan kasus ketika kita lupa membuat tautan sufiks yang penting .

Variabel tambahan yang digunakan

1. titik aktif - rangkap tiga (active_node; active_edge; active_length), menunjukkan dari mana kita harus mulai memasukkan akhiran baru.
2. sisanya - menunjukkan jumlah sufiks yang harus kita tambahkan secara eksplisit . Misalnya, jika kata kita adalah 'abcaabca', dan sisanya = 3, itu berarti kita harus memproses 3 sufiks terakhir: bca , ca dan a .

Mari kita gunakan konsep node internal - semua node, kecuali root dan daunnya adalah node internal .

Pengamatan 1

Ketika akhiran terakhir yang perlu kita masukkan ternyata sudah ada di pohon, pohon itu sendiri tidak berubah sama sekali (kita hanya memperbarui active pointdan remainder).

Pengamatan 2

Jika pada titik tertentu active_lengthlebih besar atau sama dengan panjang tepi saat ini ( edge_length), kami bergerak active pointke bawah sampai edge_lengthbenar-benar lebih besar dari active_length.

Sekarang, mari kita mendefinisikan kembali aturan:

Aturan 1

Jika setelah penyisipan dari simpul aktif = root , panjang aktif lebih besar dari 0, maka:

1. simpul aktif tidak berubah
2. panjang aktif dikurangi
3. edge aktif digeser ke kanan (ke karakter pertama dari sufiks berikutnya kita harus memasukkan)

Aturan 2

Jika kami membuat simpul internal baru ATAU membuat inserter dari simpul internal , dan ini bukan simpul internal SUCH pertama pada langkah saat ini, maka kami menautkan simpul SUCH sebelumnya dengan yang INI melalui tautan akhiran .

Definisi Rule 2ini berbeda dengan jogojapan ', karena di sini kita memperhitungkan tidak hanya node internal yang baru dibuat , tetapi juga node internal, dari mana kita membuat insersi.

Aturan 3

Setelah menyisipkan dari simpul aktif yang bukan simpul akar , kita harus mengikuti tautan sufiks dan mengatur simpul aktif ke simpul yang ditunjuknya. Jika tidak ada tautan sufiks, atur simpul aktif ke simpul akar . Either way, tepi aktif dan panjang aktif tetap tidak berubah.

Dalam definisi ini, Rule 3kami juga mempertimbangkan sisipan simpul daun (tidak hanya simpul split).

Dan akhirnya, Pengamatan 3:

Ketika simbol yang ingin kita tambahkan ke pohon sudah ada di tepi, kita, menurut Observation 1, hanya memperbarui active pointdan remainder, membiarkan pohon tidak berubah. TETAPI jika ada simpul internal yang ditandai sebagai membutuhkan tautan sufiks , kita harus menghubungkan simpul itu dengan arus kita active nodemelalui tautan sufiks.

Mari kita lihat contoh pohon sufiks untuk cdddcdc jika kita menambahkan tautan sufiks dalam kasus seperti itu dan jika tidak:

1. Jika kita TIDAK menghubungkan node melalui link suffix:

   • sebelum menambahkan huruf terakhir c :

   

   • setelah menambahkan huruf terakhir c :

   

2. Jika kita DO menghubungkan node melalui link suffix:

   • sebelum menambahkan huruf terakhir c :

   

   • setelah menambahkan huruf terakhir c :

   

Sepertinya tidak ada perbedaan signifikan: dalam kasus kedua ada dua tautan sufiks lagi. Tetapi tautan sufiks ini benar , dan salah satunya - dari titik biru ke titik merah - sangat penting bagi pendekatan kami dengan titik aktif . Masalahnya adalah bahwa jika kita tidak meletakkan tautan akhiran di sini, nanti, ketika kita menambahkan beberapa huruf baru ke pohon, kita mungkin menghilangkan menambahkan beberapa node ke pohon karena Rule 3, karena, menurutnya, jika tidak ada tautan suffix, maka kita harus meletakkannya active_nodeke root.

Ketika kami menambahkan huruf terakhir ke pohon, simpul merah sudah ada sebelum kami membuat sisipan dari simpul biru (tepi diberi label 'c' ). Karena ada sisipan dari simpul biru, kami menandainya membutuhkan tautan sufiks . Kemudian, dengan mengandalkan pendekatan titik aktif , active nodeitu ditetapkan ke simpul merah. Tapi kami tidak membuat sisipan dari simpul merah, karena huruf 'c' sudah ada di tepi. Apakah ini berarti bahwa simpul biru harus dibiarkan tanpa tautan sufiks? Tidak, kita harus menghubungkan simpul biru dengan simpul merah melalui tautan sufiks. Mengapa ini benar? Karena titik aktifpendekatan menjamin bahwa kita sampai ke tempat yang tepat, yaitu, ke tempat berikutnya di mana kita harus memproses sisipan sufiks yang lebih pendek .

Akhirnya, inilah implementasi saya dari Suffix Tree:

1. Jawa
2. C ++

Berharap bahwa "gambaran umum" ini dikombinasikan dengan jawaban terperinci jogojapan akan membantu seseorang untuk mengimplementasikan Pohon Sufiksnya sendiri.

Terima kasih untuk tutorial yang dijelaskan dengan baik oleh @jogojapan , saya menerapkan algoritma dengan Python.

Beberapa masalah kecil yang disebutkan oleh @jogojapan ternyata lebih canggih dari yang saya harapkan, dan perlu diperlakukan dengan sangat hati-hati. Saya perlu beberapa hari untuk mendapatkan implementasi saya cukup kuat (saya kira). Masalah dan solusi tercantum di bawah ini:

1. Akhiri denganRemainder > 0 Ternyata situasi ini juga bisa terjadi selama langkah berlangsung , bukan hanya akhir dari keseluruhan algoritma. Ketika itu terjadi, kita dapat membiarkan sisa, actnode, actedge, dan actlength tidak berubah , mengakhiri langkah unfolding saat ini, dan memulai langkah lain dengan terus melipat atau membuka, tergantung pada apakah arang berikutnya dalam string asli berada di jalur saat ini atau tidak.

2. Leap Over Nodes: Ketika kita mengikuti tautan suffix, perbarui titik aktifnya, dan kemudian temukan bahwa komponen active_length-nya tidak bekerja dengan baik dengan active_node yang baru. Kita harus bergerak maju ke tempat yang tepat untuk membelah, atau menyisipkan daun. Proses ini mungkin tidak semudah itu karena selama memindahkan actlength dan actedge terus berubah sepanjang jalan, ketika Anda harus kembali ke node root , actedge dan actlength bisa salah karena gerakan tersebut. Kami membutuhkan variabel tambahan untuk menyimpan informasi itu.

   

Dua masalah lainnya entah bagaimana telah ditunjukkan oleh @managonov

3. Split Bisa Memburuk Ketika mencoba untuk membagi tepi, kadang-kadang Anda akan menemukan operasi split tepat pada sebuah node. Itu kasus kita hanya perlu menambahkan daun baru ke simpul itu, menganggapnya sebagai operasi split edge standar, yang berarti tautan sufiks jika ada, harus dipertahankan sesuai.

4. Tautan Sufiks Tersembunyi Ada kasus khusus lain yang ditimbulkan oleh masalah 1 dan masalah 2 . Kadang-kadang kita perlu melompati beberapa node ke titik yang tepat untuk split, kita mungkin melampaui titik yang tepat jika kita bergerak dengan membandingkan string sisa dan label path. Jika demikian, tautan sufiks akan diabaikan secara tidak sengaja, jika memang ada. Ini bisa dihindari dengan mengingat titik yang tepat ketika bergerak maju. Tautan suffix harus dipertahankan jika split node sudah ada, atau bahkan masalah 1 terjadi selama langkah unfolding.

Akhirnya, implementasi saya di Python adalah sebagai berikut:

• Python

Tip: Ini mencakup fungsi pencetakan pohon naif dalam kode di atas, yang sangat penting saat debugging . Ini menyelamatkan saya banyak waktu dan nyaman untuk menemukan kasus-kasus khusus.

Mohon maaf jika jawaban saya tampaknya berlebihan, tetapi saya menerapkan algoritma Ukkonen baru-baru ini, dan mendapati diri saya berjuang dengan itu selama berhari-hari; Saya harus membaca beberapa makalah tentang subjek untuk memahami mengapa dan bagaimana beberapa aspek inti dari algoritma.

Saya menemukan pendekatan 'aturan' dari jawaban sebelumnya tidak membantu untuk memahami alasan yang mendasarinya , jadi saya telah menulis semuanya di bawah ini hanya berfokus pada pragmatik. Jika Anda kesulitan mengikuti penjelasan lain, seperti yang saya lakukan, mungkin penjelasan tambahan saya akan membuatnya 'klik' untuk Anda.

Saya menerbitkan implementasi C # saya di sini: https://github.com/baratgabor/SuffixTree

Harap perhatikan bahwa saya bukan ahli dalam hal ini, jadi bagian berikut mungkin mengandung ketidakakuratan (atau lebih buruk). Jika Anda menemukan sesuatu, silakan edit.

Prasyarat

Titik awal dari penjelasan berikut mengasumsikan Anda terbiasa dengan konten dan penggunaan pohon sufiks, dan karakteristik algoritma Ukkonen, misalnya bagaimana Anda memperluas karakter pohon sufiks dengan karakter, dari awal hingga akhir. Pada dasarnya, saya menganggap Anda sudah membaca beberapa penjelasan lainnya.

(Namun, saya memang harus menambahkan beberapa narasi dasar untuk alurnya, sehingga awalnya mungkin terasa berlebihan.)

Bagian yang paling menarik adalah penjelasan tentang perbedaan antara menggunakan tautan sufiks dan pemindaian ulang dari root . Inilah yang memberi saya banyak bug dan sakit kepala dalam implementasi saya.

Node daun terbuka dan keterbatasannya

Saya yakin Anda sudah tahu bahwa 'trik' paling mendasar adalah menyadari bahwa kita bisa membiarkan akhir sufiks 'terbuka', yaitu merujuk panjang string saat ini daripada mengatur akhir ke nilai statis. Dengan cara ini ketika kita menambahkan karakter tambahan, karakter-karakter itu akan ditambahkan secara implisit ke semua label sufiks, tanpa harus mengunjungi dan memperbarui mereka semua.

Namun akhiran sufiks yang terbuka ini - untuk alasan yang jelas - hanya berfungsi untuk simpul yang mewakili ujung string, yaitu simpul daun dalam struktur pohon. Operasi percabangan yang kami jalankan di pohon (penambahan node cabang baru dan node daun) tidak akan menyebar secara otomatis di mana pun mereka perlu.

Ini mungkin elementer, dan tidak perlu disebutkan, bahwa substring berulang tidak muncul secara eksplisit di pohon, karena pohon sudah mengandung ini berdasarkan mereka pengulangan; Namun, ketika substring berulang berakhir dengan menemukan karakter yang tidak berulang, kita perlu membuat percabangan pada titik itu untuk mewakili perbedaan dari titik itu dan seterusnya.

Sebagai contoh dalam kasus string 'ABCXABCY' (lihat di bawah), percabangan ke X dan Y perlu ditambahkan ke tiga sufiks yang berbeda, ABC , BC dan C ; kalau tidak, itu tidak akan menjadi pohon sufiks yang valid, dan kami tidak dapat menemukan semua substring dari string dengan mencocokkan karakter dari root ke bawah.

Sekali lagi, untuk menekankan - operasi apa pun yang kita jalankan pada sufiks di pohon perlu direfleksikan oleh sufiks berturut-turut juga (mis. ABC> BC> C), jika tidak maka sufiks tersebut tidak lagi menjadi sufiks yang valid.

Tetapi bahkan jika kita menerima bahwa kita harus melakukan pembaruan manual ini, bagaimana kita tahu berapa banyak sufiks yang perlu diperbarui? Karena, ketika kita menambahkan karakter berulang A (dan karakter berulang lainnya secara berurutan), kita belum tahu kapan / di mana kita perlu membagi sufiks menjadi dua cabang. Kebutuhan untuk memisahkan dipastikan hanya ketika kita menemukan karakter non-berulang pertama, dalam hal ini Y (bukan X yang sudah ada di pohon).

Apa yang bisa kita lakukan adalah mencocokkan string berulang yang kita bisa, dan menghitung berapa banyak sufiksnya yang perlu kita perbarui nanti. Ini adalah singkatan dari 'sisanya' .

Konsep 'sisa' dan 'pemindaian ulang'

Variabel remaindermemberitahu kita berapa banyak karakter berulang yang kita tambahkan secara implisit, tanpa bercabang; yaitu berapa banyak sufiks yang perlu kita kunjungi untuk mengulang operasi percabangan begitu kita menemukan karakter pertama yang tidak dapat kita cocokkan. Ini pada dasarnya sama dengan berapa banyak karakter 'dalam' kita di pohon dari akarnya.

Jadi, dengan tetap menggunakan contoh sebelumnya dari string ABCXABCY , kami mencocokkan bagian ABC berulang 'secara implisit', bertambah remaindersetiap kali, yang menghasilkan sisa dari 3. Kemudian kita menemukan karakter 'Y' yang tidak berulang . Di sini kita membagi menambahkan sebelumnya ABCX ke ABC -> X dan ABC -> Y . Lalu kami mengurangi remainder3 menjadi 2, karena kami sudah mengurus cabang ABC . Sekarang kita ulangi operasi dengan mencocokkan 2 karakter terakhir - BC - dari root untuk mencapai titik di mana kita perlu membagi, dan kita membagi BCX juga menjadi BC-> X dan BC -> Y . Sekali lagi, kami mengurangi remainderke 1, dan mengulangi operasi; sampai remainderis 0. Terakhir, kita perlu menambahkan karakter saat ini ( Y ) itu sendiri ke root juga.

Operasi ini, mengikuti akhiran berturut-turut dari root hanya untuk mencapai titik di mana kita perlu melakukan operasi adalah apa yang disebut 'rescanning' dalam algoritma Ukkonen, dan biasanya ini adalah bagian paling mahal dari algoritma. Bayangkan string yang lebih panjang di mana Anda perlu 'memindai ulang' substring panjang, di banyak lusinan node (kita akan membahas ini nanti), berpotensi ribuan kali.

Sebagai solusi, kami memperkenalkan apa yang kami sebut 'tautan akhiran' .

Konsep 'tautan akhiran'

Tautan sufiks pada dasarnya menunjuk ke posisi yang biasanya harus kita 'pindai ulang' , jadi alih-alih operasi pemindaian ulang yang mahal, kita dapat langsung beralih ke posisi tertaut, melakukan pekerjaan, melompat ke posisi tertaut berikutnya, dan mengulangi - sampai di sana tidak ada lagi posisi untuk diperbarui.

Tentu saja satu pertanyaan besar adalah bagaimana cara menambahkan tautan ini. Jawaban yang ada adalah bahwa kita dapat menambahkan tautan ketika kita memasukkan node cabang baru, memanfaatkan fakta bahwa, dalam setiap ekstensi pohon, node cabang secara alami dibuat satu demi satu dalam urutan yang tepat yang kita perlukan untuk menghubungkan mereka bersama-sama . Padahal, kita harus menautkan dari simpul cabang yang dibuat terakhir (akhiran terpanjang) ke yang dibuat sebelumnya, jadi kita perlu men-cache yang terakhir kita buat, menghubungkan itu ke yang berikutnya kita buat, dan cache yang baru dibuat.

Salah satu konsekuensinya adalah bahwa kita sebenarnya sering tidak memiliki tautan sufiks untuk diikuti, karena simpul cabang yang diberikan baru saja dibuat. Dalam kasus-kasus ini kita masih harus kembali ke 'pemindaian ulang' dari root. Inilah sebabnya, setelah penyisipan, Anda diperintahkan untuk menggunakan tautan suffix, atau lompat ke root.

(Atau sebagai alternatif, jika Anda menyimpan pointer orangtua di node, Anda dapat mencoba mengikuti orang tua, periksa apakah mereka memiliki tautan, dan menggunakannya. Saya menemukan bahwa ini sangat jarang disebutkan, tetapi penggunaan tautan akhiran tidak diatur dalam batu. Ada beberapa pendekatan yang mungkin, dan jika Anda memahami mekanisme yang mendasarinya Anda dapat menerapkan yang paling sesuai dengan kebutuhan Anda.)

Konsep 'titik aktif'

Sejauh ini kami membahas beberapa alat yang efisien untuk membangun pohon, dan secara samar-samar merujuk melintasi beberapa sisi dan simpul, tetapi belum mengeksplorasi konsekuensi dan kompleksitas yang sesuai.

Konsep 'sisa' yang dijelaskan sebelumnya berguna untuk melacak di mana kita berada di pohon, tetapi kita harus menyadari itu tidak menyimpan informasi yang cukup.

Pertama, kita selalu berada di tepi spesifik node, jadi kita perlu menyimpan informasi edge. Kami akan menyebutnya 'tepi aktif' .

Kedua, bahkan setelah menambahkan informasi tepi, kami masih tidak memiliki cara untuk mengidentifikasi posisi yang lebih jauh di pohon, dan tidak terhubung langsung ke simpul akar . Jadi kita perlu menyimpan node juga. Sebut ini 'simpul aktif' .

Terakhir, kita dapat melihat bahwa 'sisa' tidak memadai untuk mengidentifikasi posisi di tepi yang tidak terhubung langsung ke root, karena 'sisa' adalah panjang dari seluruh rute; dan kami mungkin tidak ingin repot mengingat dan mengurangi panjang dari tepi sebelumnya. Jadi kita perlu representasi yang pada dasarnya adalah sisa di tepi saat ini . Inilah yang kami sebut 'panjang aktif' .

Ini mengarah ke apa yang kita sebut 'titik aktif' - paket tiga variabel yang berisi semua informasi yang perlu kita pertahankan tentang posisi kita di pohon:

Active Point = (Active Node, Active Edge, Active Length)

Anda dapat mengamati pada gambar berikut bagaimana rute yang cocok dari ABCABD terdiri dari 2 karakter di tepi AB (dari root ), ditambah 4 karakter di tepi CABDABCABD (dari node 4) - menghasilkan 'sisa' 6 karakter. Jadi, posisi kami saat ini dapat diidentifikasi sebagai Node 4 Aktif, Tepi Aktif C, Panjang Aktif 4 .

Peran penting lain dari 'titik aktif' adalah memberikan lapisan abstraksi untuk algoritme kami, yang berarti bahwa bagian dari algoritme kami dapat melakukan pekerjaan mereka pada 'titik aktif' , terlepas dari apakah titik aktif itu di root atau di tempat lain . Ini membuatnya mudah untuk menerapkan penggunaan tautan sufiks dalam algoritme kami dengan cara yang bersih dan mudah.

Perbedaan pemindaian ulang vs menggunakan tautan sufiks

Sekarang, bagian yang sulit, sesuatu yang - dalam pengalaman saya - dapat menyebabkan banyak bug dan sakit kepala, dan tidak dijelaskan dengan baik di sebagian besar sumber, adalah perbedaan dalam pemrosesan kasus sambungan sufiks vs kasus pemindaian ulang.

Perhatikan contoh string 'AAAABAAAABAAC' berikut :

Anda dapat mengamati di atas bagaimana 'sisa' dari 7 sesuai dengan jumlah total karakter dari root, sedangkan 'panjang aktif' dari 4 sesuai dengan jumlah karakter yang cocok dari tepi aktif dari simpul aktif.

Sekarang, setelah menjalankan operasi percabangan pada titik aktif, simpul aktif kami mungkin atau mungkin tidak mengandung tautan sufiks.

Jika tautan sufiks ada: Kita hanya perlu memproses bagian 'panjang aktif' . The 'sisanya' tidak relevan, karena simpul mana kita melompat ke melalui link akhiran sudah mengkodekan benar 'sisa' secara implisit , hanya berdasarkan berada di pohon di mana itu.

Jika tautan sufiks TIDAK ada: Kita perlu 'memindai ulang' dari nol / root, yang berarti memproses sufiks keseluruhan dari awal. Untuk tujuan ini kita harus menggunakan seluruh 'sisa' sebagai dasar untuk memindai ulang.

Contoh perbandingan pemrosesan dengan dan tanpa tautan sufiks

Pertimbangkan apa yang terjadi pada langkah selanjutnya dari contoh di atas. Mari kita bandingkan cara mencapai hasil yang sama - yaitu berpindah ke akhiran berikutnya untuk diproses - dengan dan tanpa tautan akhiran.

Menggunakan 'tautan akhiran'

Perhatikan bahwa jika kita menggunakan tautan sufiks, kita secara otomatis 'di tempat yang tepat'. Yang sering tidak sepenuhnya benar karena kenyataan bahwa 'panjang aktif' dapat 'tidak kompatibel' dengan posisi baru.

Dalam kasus di atas, karena 'panjang aktif' adalah 4, kami bekerja dengan sufiks ' ABAA' , mulai dari Node 4. yang ditautkan. Namun setelah menemukan tepi yang sesuai dengan karakter pertama dari akhiran ( 'A' ), kami perhatikan bahwa 'panjang aktif' kami melebihi tepi ini sebanyak 3 karakter. Jadi kita melompati tepi penuh, ke simpul berikutnya, dan mengurangi 'panjang aktif' oleh karakter yang kita konsumsi dengan lompatan.

Kemudian, setelah kami menemukan tepi berikutnya 'B' , sesuai dengan sufiks akhiran 'BAA ', kami akhirnya mencatat bahwa panjang tepi lebih besar daripada 'panjang aktif' tersisa 3, yang berarti kami menemukan tempat yang tepat.

Harap perhatikan bahwa tampaknya operasi ini biasanya tidak disebut sebagai 'pemindaian ulang', meskipun bagi saya tampaknya ini setara langsung dengan pemindaian ulang, hanya dengan panjang yang lebih pendek dan titik awal non-root.

Menggunakan 'pindai ulang'

Perhatikan bahwa jika kita menggunakan operasi 'pindai ulang' tradisional (di sini berpura-pura kita tidak memiliki tautan sufiks), kita mulai di bagian atas pohon, di root, dan kita harus bekerja turun lagi ke tempat yang tepat, mengikuti sepanjang panjang akhiran saat ini.

Panjang akhiran ini adalah 'sisa' yang kita bahas sebelumnya. Kita harus mengkonsumsi keseluruhan dari sisa ini, hingga mencapai nol. Ini mungkin (dan seringkali memang) termasuk melompat melalui beberapa node, pada setiap lompatan mengurangi sisanya pada panjang tepi yang kita lewati. Kemudian akhirnya, kami mencapai tepi yang lebih panjang dari 'sisa' kami yang tersisa ; di sini kita mengatur tepi aktif ke tepi yang diberikan, mengatur 'panjang aktif' untuk sisa 'sisa ', dan kita selesai.

Perhatikan, bagaimanapun, bahwa variabel 'sisa' yang sebenarnya perlu dipertahankan, dan hanya dikurangi setelah setiap penyisipan simpul. Jadi apa yang saya jelaskan di atas diasumsikan menggunakan variabel terpisah diinisialisasi ke 'sisa' .

Catatan tentang tautan suffix & rescans

1) Perhatikan bahwa kedua metode mengarah ke hasil yang sama. Namun, lompatan tautan sufiks secara signifikan lebih cepat dalam banyak kasus; itulah dasar pemikiran di balik tautan sufiks.

2) Implementasi algoritmik yang sebenarnya tidak perlu berbeda. Seperti yang saya sebutkan di atas, bahkan dalam kasus menggunakan tautan suffix, 'panjang aktif' sering tidak kompatibel dengan posisi tertaut, karena cabang pohon itu mungkin mengandung cabang tambahan. Jadi pada dasarnya Anda hanya perlu menggunakan 'panjang aktif' alih-alih 'sisa' , dan jalankan logika pemindaian ulang yang sama sampai Anda menemukan tepi yang lebih pendek dari panjang sufiks yang tersisa.

3) Satu komentar penting yang berkaitan dengan kinerja adalah bahwa tidak perlu memeriksa setiap karakter selama pemindaian ulang. Karena cara pohon sufiks yang valid dibangun, kita dapat dengan aman mengasumsikan bahwa karakternya cocok. Jadi, Anda sebagian besar menghitung panjang, dan satu-satunya kebutuhan untuk pengecekan kesetaraan karakter muncul ketika kita melompat ke tepi baru, karena tepi diidentifikasi oleh karakter pertama mereka (yang selalu unik dalam konteks node yang diberikan). Ini berarti bahwa logika 'rescanning' berbeda dari logika pencocokan string penuh (yaitu mencari substring di pohon).

4) Tautan akhiran asli yang dijelaskan di sini hanyalah salah satu dari pendekatan yang mungkin . Misalnya NJ Larsson et al. menamakan pendekatan ini sebagai Node-Oriented Top-Down , dan membandingkannya dengan Node-Oriented Bottom-Up dan dua varietas Edge-Oriented . Pendekatan yang berbeda memiliki kinerja kasus yang khas dan terburuk, persyaratan, batasan, dll., Tetapi secara umum tampaknya pendekatan Edge-Oriented adalah peningkatan keseluruhan terhadap yang asli.

@jogojapan Anda membawa penjelasan dan visualisasi yang luar biasa. Tetapi seperti @makagonov menyebutkan bahwa ada beberapa aturan tentang pengaturan akhiran tautan sufiks. Ini terlihat dengan cara yang baik ketika akan langkah demi langkah di http://brenden.github.io/ukkonen-animation/ melalui kata 'aabaaabb'. Ketika Anda beralih dari langkah 10 ke langkah 11, tidak ada tautan sufiks dari simpul 5 ke simpul 2 tetapi titik aktif tiba-tiba bergerak ke sana.

@makagonov sejak saya tinggal di dunia Java, saya juga mencoba mengikuti implementasi Anda untuk memahami alur kerja pembangunan ST tetapi sulit bagi saya karena:

• menggabungkan tepi dengan node
• menggunakan pointer indeks, bukan referensi
• melanggar pernyataan;
• melanjutkan pernyataan;

Jadi saya berakhir dengan implementasi seperti itu di Jawa yang saya harap mencerminkan semua langkah dengan cara yang lebih jelas dan akan mengurangi waktu belajar bagi orang Jawa lainnya:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ST {

  public class Node {
    private final int id;
    private final Map<Character, Edge> edges;
    private Node slink;

    public Node(final int id) {
        this.id = id;
        this.edges = new HashMap<>();
    }

    public void setSlink(final Node slink) {
        this.slink = slink;
    }

    public Map<Character, Edge> getEdges() {
        return this.edges;
    }

    public Node getSlink() {
        return this.slink;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"id\"")
                .append(":")
                .append(this.id)
                .append(",")
                .append("\"slink\"")
                .append(":")
                .append(this.slink != null ? this.slink.id : null)
                .append(",")
                .append("\"edges\"")
                .append(":")
                .append(edgesToString(word))
                .append("}")
                .toString();
    }

    private StringBuilder edgesToString(final String word) {
        final StringBuilder edgesStringBuilder = new StringBuilder();
        edgesStringBuilder.append("{");
        for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) {
            edgesStringBuilder.append("\"")
                    .append(entry.getKey())
                    .append("\"")
                    .append(":")
                    .append(entry.getValue().toString(word))
                    .append(",");
        }
        if(!this.edges.isEmpty()) {
            edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1);
        }
        edgesStringBuilder.append("}");
        return edgesStringBuilder;
    }

    public boolean contains(final String word, final String suffix) {
        return !suffix.isEmpty()
                && this.edges.containsKey(suffix.charAt(0))
                && this.edges.get(suffix.charAt(0)).contains(word, suffix);
    }
  }

  public class Edge {
    private final int from;
    private final int to;
    private final Node next;

    public Edge(final int from, final int to, final Node next) {
        this.from = from;
        this.to = to;
        this.next = next;
    }

    public int getFrom() {
        return this.from;
    }

    public int getTo() {
        return this.to;
    }

    public Node getNext() {
        return this.next;
    }

    public int getLength() {
        return this.to - this.from;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"content\"")
                .append(":")
                .append("\"")
                .append(word.substring(this.from, this.to))
                .append("\"")
                .append(",")
                .append("\"next\"")
                .append(":")
                .append(this.next != null ? this.next.toString(word) : null)
                .append("}")
                .toString();
    }

    public boolean contains(final String word, final String suffix) {
        if(this.next == null) {
            return word.substring(this.from, this.to).equals(suffix);
        }
        return suffix.startsWith(word.substring(this.from,
                this.to)) && this.next.contains(word, suffix.substring(this.to - this.from));
    }
  }

  public class ActivePoint {
    private final Node activeNode;
    private final Character activeEdgeFirstCharacter;
    private final int activeLength;

    public ActivePoint(final Node activeNode,
                       final Character activeEdgeFirstCharacter,
                       final int activeLength) {
        this.activeNode = activeNode;
        this.activeEdgeFirstCharacter = activeEdgeFirstCharacter;
        this.activeLength = activeLength;
    }

    private Edge getActiveEdge() {
        return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter);
    }

    public boolean pointsToActiveNode() {
        return this.activeLength == 0;
    }

    public boolean activeNodeIs(final Node node) {
        return this.activeNode == node;
    }

    public boolean activeNodeHasEdgeStartingWith(final char character) {
        return this.activeNode.getEdges().containsKey(character);
    }

    public boolean activeNodeHasSlink() {
        return this.activeNode.getSlink() != null;
    }

    public boolean pointsToOnActiveEdge(final String word, final char character) {
        return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character;
    }

    public boolean pointsToTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() == this.activeLength;
    }

    public boolean pointsAfterTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() < this.activeLength;
    }

    public ActivePoint moveToEdgeStartingWithAndByOne(final char character) {
        return new ActivePoint(this.activeNode, character, 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge() {
        return new ActivePoint(this.getActiveEdge().getNext(), null, 0);
    }

    public ActivePoint moveToSlink() {
        return new ActivePoint(this.activeNode.getSlink(),
                this.activeEdgeFirstCharacter,
                this.activeLength);
    }

    public ActivePoint moveTo(final Node node) {
        return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength);
    }

    public ActivePoint moveByOneCharacter() {
        return new ActivePoint(this.activeNode,
                this.activeEdgeFirstCharacter,
                this.activeLength + 1);
    }

    public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node,
                                                                       final char character) {
        return new ActivePoint(node, character, this.activeLength - 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) {
        return new ActivePoint(this.getActiveEdge().getNext(),
                word.charAt(index - this.activeLength + this.getActiveEdge().getLength()),
                this.activeLength - this.getActiveEdge().getLength());
    }

    public void addEdgeToActiveNode(final char character, final Edge edge) {
        this.activeNode.getEdges().put(character, edge);
    }

    public void splitActiveEdge(final String word,
                                final Node nodeToAdd,
                                final int index,
                                final char character) {
        final Edge activeEdgeToSplit = this.getActiveEdge();
        final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(),
                activeEdgeToSplit.getFrom() + this.activeLength,
                nodeToAdd);
        nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength),
                new Edge(activeEdgeToSplit.getFrom() + this.activeLength,
                        activeEdgeToSplit.getTo(),
                        activeEdgeToSplit.getNext()));
        nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null));
        this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge);
    }

    public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,
                           final Node node) {
        if(previouslyAddedNodeOrAddedEdgeNode != null) {
            previouslyAddedNodeOrAddedEdgeNode.setSlink(node);
        }
        return node;
    }

    public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {
        return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);
    }
  }

  private static int idGenerator;

  private final String word;
  private final Node root;
  private ActivePoint activePoint;
  private int remainder;

  public ST(final String word) {
    this.word = word;
    this.root = new Node(idGenerator++);
    this.activePoint = new ActivePoint(this.root, null, 0);
    this.remainder = 0;
    build();
  }

  private void build() {
    for(int i = 0; i < this.word.length(); i++) {
        add(i, this.word.charAt(i));
    }
  }

  private void add(final int index, final char character) {
    this.remainder++;
    boolean characterFoundInTheTree = false;
    Node previouslyAddedNodeOrAddedEdgeNode = null;
    while(!characterFoundInTheTree && this.remainder > 0) {
        if(this.activePoint.pointsToActiveNode()) {
            if(this.activePoint.activeNodeHasEdgeStartingWith(character)) {
                activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode);
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    rootNodeHasNotEdgeStartingWithCharacter(index, character);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index,
                            character, previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
        else {
            if(this.activePoint.pointsToOnActiveEdge(this.word, character)) {
                activeEdgeHasCharacter();
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
    }
  }

  private void activeNodeHasEdgeStartingWithCharacter(final char character,
                                                    final Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character);
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    this.activePoint = this.activePoint.moveTo(this.root);
    this.remainder--;
    assert this.remainder == 0;
  }

  private Node internalNodeHasNotEdgeStartingWithCharacter(final int index,
                                                         final char character,
                                                         Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private void activeEdgeHasCharacter() {
    this.activePoint = this.activePoint.moveByOneCharacter();
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private Node edgeFromRootNodeHasNotCharacter(final int index,
                                             final char character,
                                             Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root,
            this.word.charAt(index - this.remainder + 2));
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private Node edgeFromInternalNodeHasNotCharacter(final int index,
                                                 final char character,
                                                 Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private ActivePoint walkDown(final int index) {
    while(!this.activePoint.pointsToActiveNode()
            && (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {
        if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index);
        }
        else {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
        }
    }
    return this.activePoint;
  }

  public String toString(final String word) {
    return this.root.toString(word);
  }

  public boolean contains(final String suffix) {
    return this.root.contains(this.word, suffix);
  }

  public static void main(final String[] args) {
    final String[] words = {
            "abcabcabc$",
            "abc$",
            "abcabxabcd$",
            "abcabxabda$",
            "abcabxad$",
            "aabaaabb$",
            "aababcabcd$",
            "ababcabcd$",
            "abccba$",
            "mississipi$",
            "abacabadabacabae$",
            "abcabcd$",
            "00132220$"
    };
    Arrays.stream(words).forEach(word -> {
        System.out.println("Building suffix tree for word: " + word);
        final ST suffixTree = new ST(word);
        System.out.println("Suffix tree: " + suffixTree.toString(word));
        for(int i = 0; i < word.length() - 1; i++) {
            assert suffixTree.contains(word.substring(i)) : word.substring(i);
        }
    });
  }
}

Intuisi saya adalah sebagai berikut:

Setelah k iterasi loop utama Anda telah membangun pohon sufiks yang berisi semua sufiks dari string lengkap yang dimulai dengan karakter k pertama.

Pada awalnya, ini berarti pohon sufiks berisi simpul akar tunggal yang mewakili seluruh string (ini adalah satu-satunya sufiks yang dimulai pada 0).

Setelah len (string) iterasi, Anda memiliki pohon sufiks yang berisi semua sufiks.

Selama loop, kuncinya adalah titik aktif. Dugaan saya adalah bahwa ini merupakan titik terdalam di pohon sufiks yang sesuai dengan sufiks yang tepat dari karakter k pertama dari string. (Saya pikir benar berarti sufiks tidak boleh seluruh string.)

Misalnya, Anda telah melihat karakter 'abcabc'. Titik aktif akan mewakili titik di pohon yang sesuai dengan sufiks 'abc'.

Titik aktif diwakili oleh (asal, pertama, terakhir). Ini berarti bahwa Anda saat ini pada titik di pohon yang Anda dapatkan dengan mulai dari simpul asal dan kemudian memberi makan karakter dalam string [pertama: terakhir]

Ketika Anda menambahkan karakter baru Anda melihat untuk melihat apakah titik aktif masih di pohon yang ada. Jika sudah maka Anda selesai. Kalau tidak, Anda perlu menambahkan simpul baru ke pohon suffix di titik aktif, mundur ke pertandingan terpendek berikutnya, dan periksa lagi.

Catatan 1: Pointer suffix memberikan tautan ke kecocokan terpendek berikutnya untuk setiap node.

Catatan 2: Ketika Anda menambahkan node baru dan mundur Anda menambahkan pointer suffix baru untuk node baru. Tujuan untuk penunjuk sufiks ini adalah simpul pada titik aktif yang disingkat. Node ini akan sudah ada, atau dibuat pada iterasi berikutnya dari fallback loop ini.

Catatan 3: Bagian kanonisasi hanya menghemat waktu dalam memeriksa titik aktif. Misalnya, anggap Anda selalu menggunakan origin = 0, dan baru saja mengubah dulu dan terakhir. Untuk memeriksa titik aktif Anda harus mengikuti pohon akhiran setiap kali sepanjang semua node perantara. Masuk akal untuk men-cache hasil mengikuti jalur ini dengan merekam hanya jarak dari node terakhir.

Bisakah Anda memberikan contoh kode tentang apa yang Anda maksud dengan variabel terikat "fix"?

Peringatan kesehatan: Saya juga menemukan algoritma ini sangat sulit untuk dipahami, jadi harap sadari bahwa intuisi ini cenderung salah dalam semua detail penting ...

Hai Saya telah mencoba menerapkan implementasi yang dijelaskan di atas dalam ruby, silakan periksa. tampaknya berfungsi dengan baik.

satu-satunya perbedaan dalam implementasi adalah bahwa, saya telah mencoba menggunakan objek tepi daripada hanya menggunakan simbol.

itu juga hadir di https://gist.github.com/suchitpuri/9304856

    require 'pry'


class Edge
    attr_accessor :data , :edges , :suffix_link
    def initialize data
        @data = data
        @edges = []
        @suffix_link = nil
    end

    def find_edge element
        self.edges.each do |edge|
            return edge if edge.data.start_with? element
        end
        return nil
    end
end

class SuffixTrees
    attr_accessor :root , :active_point , :remainder , :pending_prefixes , :last_split_edge , :remainder

    def initialize
        @root = Edge.new nil
        @active_point = { active_node: @root , active_edge: nil , active_length: 0}
        @remainder = 0
        @pending_prefixes = []
        @last_split_edge = nil
        @remainder = 1
    end

    def build string
        string.split("").each_with_index do |element , index|


            add_to_edges @root , element        

            update_pending_prefix element                           
            add_pending_elements_to_tree element
            active_length = @active_point[:active_length]

            # if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data[0..active_length-1] ==  @active_point[:active_edge].data[active_length..@active_point[:active_edge].data.length-1])
            #   @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1]
            #   @active_point[:active_edge].edges << Edge.new(@active_point[:active_edge].data)
            # end

            if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data.length == @active_point[:active_length]  )
                @active_point[:active_node] =  @active_point[:active_edge]
                @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0])
                @active_point[:active_length] = 0
            end
        end
    end

    def add_pending_elements_to_tree element

        to_be_deleted = []
        update_active_length = false
        # binding.pry
        if( @active_point[:active_node].find_edge(element[0]) != nil)
            @active_point[:active_length] = @active_point[:active_length] + 1               
            @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil
            @remainder = @remainder + 1
            return
        end



        @pending_prefixes.each_with_index do |pending_prefix , index|

            # binding.pry           

            if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil

                @active_point[:active_node].edges << Edge.new(element)

            else

                @active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge]  == nil

                data = @active_point[:active_edge].data
                data = data.split("")               

                location = @active_point[:active_length]


                # binding.pry
                if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil )                  


                else #tree split    
                    split_edge data , index , element
                end

            end
        end 
    end



    def update_pending_prefix element
        if @active_point[:active_edge] == nil
            @pending_prefixes = [element]
            return

        end

        @pending_prefixes = []

        length = @active_point[:active_edge].data.length
        data = @active_point[:active_edge].data
        @remainder.times do |ctr|
                @pending_prefixes << data[-(ctr+1)..data.length-1]
        end

        @pending_prefixes.reverse!

    end

    def split_edge data , index , element
        location = @active_point[:active_length]
        old_edges = []
        internal_node = (@active_point[:active_edge].edges != nil)

        if (internal_node)
            old_edges = @active_point[:active_edge].edges 
            @active_point[:active_edge].edges = []
        end

        @active_point[:active_edge].data = data[0..location-1].join                 
        @active_point[:active_edge].edges << Edge.new(data[location..data.size].join)


        if internal_node
            @active_point[:active_edge].edges << Edge.new(element)
        else
            @active_point[:active_edge].edges << Edge.new(data.last)        
        end

        if internal_node
            @active_point[:active_edge].edges[0].edges = old_edges
        end


        #setup the suffix link
        if @last_split_edge != nil and @last_split_edge.data.end_with?@active_point[:active_edge].data 

            @last_split_edge.suffix_link = @active_point[:active_edge] 
        end

        @last_split_edge = @active_point[:active_edge]

        update_active_point index

    end


    def update_active_point index
        if(@active_point[:active_node] == @root)
            @active_point[:active_length] = @active_point[:active_length] - 1
            @remainder = @remainder - 1
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1])
        else
            if @active_point[:active_node].suffix_link != nil
                @active_point[:active_node] = @active_point[:active_node].suffix_link               
            else
                @active_point[:active_node] = @root
            end 
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0])
            @remainder = @remainder - 1     
        end
    end

    def add_to_edges root , element     
        return if root == nil
        root.data = root.data + element if(root.data and root.edges.size == 0)
        root.edges.each do |edge|
            add_to_edges edge , element
        end
    end
end

suffix_tree = SuffixTrees.new
suffix_tree.build("abcabxabcd")
binding.pry