Pertanyaan Algoritma pohon akhiran Ukkonen dalam bahasa Inggris biasa


Saya merasa agak tebal pada titik ini. Saya telah menghabiskan berhari-hari mencoba untuk sepenuhnya membungkus kepala saya di sekitar konstruksi pohon suffix, tetapi karena saya tidak memiliki latar belakang matematika, banyak penjelasan yang menghindari saya ketika mereka mulai menggunakan simbologi matematika secara berlebihan. Yang paling dekat dengan penjelasan yang bagus yang saya temukan adalah Pencarian String Cepat Dengan Pohon Akhiran, tetapi dia glosses atas berbagai titik dan beberapa aspek dari 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 iterasi melalui setiap awalan P dari string yang diberikan T
  • Saya perlu mengulang setiap sufiks S di awalan P dan menambahkannya ke pohon
  • Untuk menambahkan akhiran S ke pohon, saya perlu iterasi melalui setiap karakter dalam S, dengan iterasi yang terdiri dari berjalan di cabang yang sudah ada yang dimulai dengan set karakter C yang sama dalam S dan berpotensi membelah tepi menjadi node descendent ketika saya mencapai karakter yang berbeda di akhiran, ATAU jika tidak ada tepi yang cocok untuk berjalan ke bawah. Ketika tidak ada tepi yang cocok ditemukan untuk berjalan ke C, tepi daun baru dibuat untuk C.

Algoritma dasar tampaknya O (n2), seperti yang ditunjukkan di sebagian besar penjelasan, karena kita perlu melangkah melalui semua awalan, maka kita perlu melangkah melalui masing-masing akhiran untuk setiap awalan. Algoritma Ukkonen tampaknya unik karena teknik penunjuk suffix yang dia gunakan, meskipun saya pikir bahwa adalah apa yang saya mengalami kesulitan memahami.

Saya juga kesulitan memahami:

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

Di sini sudah selesai C # Kode sumber. Ini tidak hanya berfungsi dengan benar, tetapi mendukung kanonisasi otomatis dan membuat grafik teks keluaran yang lebih bagus. Kode sumber dan output sampel berada di:

https://gist.github.com/2373868


Pembaruan 2017-11-04

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

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


949
2018-02-26 11:30


asal


Jawaban:


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

Pertama, beberapa pernyataan awal.

  1. Apa yang sedang kita bangun, adalah pada dasarnya seperti pencarian trie. Jadi disana adalah node root, ujungnya akan mengarah ke node baru, dan lebih jauh keluar dari itu, dan seterusnya

  2. Tapi: Tidak seperti di pencarian trie, label tepi tidak tunggal karakter. Sebaliknya, setiap sisi diberi label menggunakan sepasang bilangan bulat [from,to]. Ini adalah pointer ke dalam teks. Dalam pengertian ini, masing-masing tepi membawa label string panjang sewenang-wenang, tetapi hanya mengambil O (1) ruang (dua pointer).

Prinsip dasar

Saya ingin mendemonstrasikan cara membuat pohon akhiran a khususnya string sederhana, string tanpa karakter berulang:

abc

Algoritme berfungsi secara bertahap, 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 akhir di akhir) bahwa jumlah total operasi adalah O (n).

Jadi, kita mulai dari kiri, dan pertama-tama masukkan hanya karakter tunggal a dengan membuat tepi dari simpul akar (di kiri) ke daun, dan memberi label sebagai [0,#], yang berarti ujung mewakili substring mulai dari posisi 0 dan berakhir pada ujung saat ini. saya gunakan simbolnya # berarti ujung saat ini, yang ada 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 itu b). Tujuan kami di setiap langkah adalah menyisipkan semua sufiks hingga posisi saat ini. Kami melakukan ini oleh

  • memperluas yang ada a-menjadi ke ab
  • memasukkan satu tepi baru untuk b

Dalam representasi kami ini terlihat seperti

enter image description here

Dan apa artinya adalah:

Kami amati dua hal:

  • Representasi tepi untuk ab aku s sama seperti dulu di pohon awal: [0,#]. Maknanya telah berubah secara otomatis karena kami memperbarui posisi saat ini # dari 1 ke 2.
  • Setiap sisi mengkonsumsi ruang O (1), karena hanya terdiri dari dua pointer ke dalam teks, terlepas dari berapa banyak karakternya mewakili.

Selanjutnya kita menaikkan posisi lagi dan memperbarui pohon dengan menambahkan Sebuah c ke setiap tepi yang ada dan memasukkan satu tepi baru untuk yang baru akhiran c.

Dalam representasi kami ini terlihat seperti

Dan apa artinya adalah:

Kami mengamati:

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

Ekstensi pertama: Pengulangan sederhana

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

abcabxabcd

Itu dimulai dengan abc seperti pada contoh sebelumnya, lalu ab diulang dan diikuti oleh x, lalu abc diulang diikuti oleh d.

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

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

dan kita perlu memasukkan akhiran terakhir dari langkah saat ini, a, di akar.

Sebelum kita melakukan ini, kami perkenalkan dua variabel lagi (sebagai tambahannya #), yang tentu saja sudah ada di sana sepanjang waktu tetapi kami belum pernah menggunakannya mereka sejauh ini:

  • Itu titik aktif, yang merupakan triple (active_node,active_edge,active_length)
  • Itu remainder, yang merupakan bilangan bulat yang menunjukkan berapa banyak sufiks baru kita perlu memasukkan

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

  • Secara sederhana abc contoh, titik aktif selalu (root,'\0x',0), i.e. active_node adalah simpul root, active_edge ditentukan sebagai karakter null '\0x', dan active_length adalah nol. Efek dari ini adalah bahwa satu sisi baru itu kami masukkan di setiap langkah dimasukkan ke simpul akar sebagai tepi yang baru dibuat. Kami akan segera melihat mengapa perlu triple mewakili informasi ini.
  • Itu remainder selalu diatur ke 1 di awal masing-masing langkah. Arti dari ini adalah jumlah akhiran yang kita miliki aktif menyisipkan pada akhir setiap langkah adalah 1 (selalu saja karakter terakhir).

Sekarang ini akan berubah. Saat kami memasukkan final saat ini karakter a pada akarnya, kita perhatikan bahwa sudah ada yang keluar ujung dimulai dengan a, khususnya: abca. Ini yang kami lakukan kasus seperti itu:

  • Kita tidak sisipkan tepi baru [4,#] di simpul akar. Sebaliknya kami cukup perhatikan bahwa sufiks a sudah ada di kami pohon. Itu berakhir di tengah tepi yang lebih panjang, tetapi kita tidak terganggu oleh itu. Kami hanya meninggalkan hal-hal sebagaimana adanya.
  • Kita setel titik aktif untuk (root,'a',1). Itu artinya aktif titik sekarang di suatu tempat di tengah ujung keluar dari node root yang dimulai dengan a, khususnya, setelah posisi 1 di tepi itu. Kita perhatikan bahwa tepi ditentukan hanya dengan yang pertama karakter a. Itu sudah cukup karena bisa ada hanya satu tepi dimulai dengan karakter tertentu (pastikan bahwa ini benar setelah membaca seluruh deskripsi).
  • Kami juga menambah remainder, jadi pada awal langkah selanjutnya itu akan menjadi 2.

Pengamatan: Saat final akhiran kita perlu memasukkan ditemukan sudah ada di pohon, pohon itu sendiri tidak berubah sama sekali (kami hanya memperbarui titik aktif dan remainder). Pohon Ini bukan representasi akurat dari pohon akhiran hingga posisi saat ini lagi, tapi itu mengandung semua sufiks (karena final akhiran a terkandung secara implisit). Oleh karena itu, selain memperbarui variabel (yang semuanya merupakan panjang tetap, jadi ini adalah O (1)), ada tidak ada pekerjaan dilakukan dalam langkah ini.

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

Dan karena remainder adalah 2, kita perlu memasukkan dua final akhiran posisi saat ini: ab dan b. Ini pada dasarnya karena:

  • Itu a akhiran dari langkah sebelumnya tidak pernah benar dimasukkan. Jadi begitu tetap, dan karena kami telah berkembang satu langkah, sekarang telah tumbuh dari a untuk ab.
  • Dan kita perlu memasukkan tepi akhir yang baru b.

Dalam prakteknya ini berarti kita menuju titik aktif (yang menunjuk ke dibalik a pada apa yang sekarang menjadi abcab tepi), dan masukkan karakter terakhir saat ini b. Tapi: Sekali lagi, ternyata itu b aku s juga sudah hadir di tepi yang sama.

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

  • Perbarui titik aktif ke (root,'a',2) (node ​​dan tepi yang sama seperti sebelumnya, tetapi sekarang kami menunjuk ke belakang b)
  • Kenaikan remainder ke 3 karena kita masih belum benar menyisipkan tepi akhir dari langkah sebelumnya, dan kami tidak memasukkan tepi akhir saat ini baik.

Untuk menjadi jelas: Kami harus memasukkan ab dan b di langkah saat ini, tapi karena ab sudah ditemukan, kami memperbarui titik aktif dan melakukannya bahkan tidak berusaha memasukkan b. Mengapa? Karena jika ab ada di pohon, setiap suffix itu (termasuk b) harus berada di pohon, terlalu. Mungkin saja secara implisit, tetapi harus ada, karena cara kita membangun pohon sejauh ini.

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

Karena remainder adalah 3, kita harus memasukkan abx, bx dan x. Titik aktif memberi tahu kita di mana ab berakhir, jadi kita hanya perlu melompat ke sana dan masukkan x. Memang, x belum ada di sana, jadi kita membagi abcabx tepi dan masukkan simpul internal:

Representasi tepi masih mengarah ke teks, jadi memisahkan dan memasukkan node internal dapat dilakukan dalam waktu O (1).

Jadi kita sudah membahasnya abx dan pengurangan remainder ke 2. Sekarang kita perlu memasukkan sisa akhiran berikutnya, bx. Tetapi sebelum kita melakukan itu kita perlu memperbarui titik aktif. Aturan untuk ini, setelah membelah dan menyisipkan tepi, akan dipanggil Aturan 1 di bawah ini, dan itu berlaku kapan saja active_node adalah root (kita akan belajar aturan 3 untuk kasus lain lebih lanjut di bawah). Berikut ini aturan 1:

Setelah penyisipan dari root,

  • active_node tetap root
  • active_edge diatur ke karakter pertama dari akhiran baru kita   perlu memasukkan, mis. b
  • active_length dikurangi 1

Oleh karena itu, triple aktif-titik baru (root,'b',1) menunjukkan bahwa sisipan berikutnya harus dibuat di bcabx tepi, di belakang 1 karakter, di belakang b. Kami dapat mengidentifikasi titik penyisipan dalam O (1) waktu dan periksa apakah x sudah ada atau tidak. Jika itu hadir, kami akan mengakhiri langkah saat ini dan meninggalkan semuanya sebagaimana adanya. Tapi x tidak ada, jadi kami masukkan dengan memisahkan tepi:

Sekali lagi, ini mengambil waktu O (1) dan kami memperbarui remainder ke 1 dan titik aktif untuk (root,'x',0) sebagai aturan 1 negara.

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

Jika kita membagi tepi dan memasukkan node baru, dan jika itu bukan   simpul pertama dibuat selama langkah saat ini, kami menghubungkan yang sebelumnya   menyisipkan node dan node baru melalui pointer khusus, a akhiran   link. Kami kemudian akan melihat mengapa itu berguna. Inilah yang kami dapatkan,   tautan akhiran diwakili sebagai tepian putus-putus:

Kita masih perlu memasukkan akhiran akhir dari langkah saat ini, x. Sejak itu active_length komponen dari simpul yang aktif telah jatuh ke 0, insert akhir dibuat di root secara langsung. Karena tidak ada tepi keluar pada simpul akar dimulai dengan x, kami memasukkan yang baru tepi:

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

Kami melanjutkan langkah 7 dengan pengaturan #= 7, yang secara otomatis menambahkan karakter berikutnya, a, ke semua sisi daun, seperti biasa. Kemudian kami mencoba memasukkan final baru karakter ke titik aktif (root), dan temukan bahwa itu ada di sana sudah. Jadi kita akhiri langkah saat ini tanpa memasukkan apa pun dan perbarui titik aktif ke (root,'a',1).

Di langkah 8, #= 8, kami menambahkan b, dan seperti yang terlihat sebelumnya, ini saja berarti kami memperbarui titik aktif ke (root,'a',2) dan kenaikan remainder tanpa melakukan hal lain, karena b sudah ada. Namun, kita perhatikan (dalam waktu O (1)) titik aktif sekarang berada di ujung ujung. Kami merefleksikan ini dengan mengaturnya kembali (node1,'\0x',0). Di sini, saya gunakan node1 untuk merujuk pada simpul internal ab ujung berakhir pada.

Kemudian, di langkah #= 9, kita perlu memasukkan 'c' dan ini akan membantu kita pahamilah trik terakhir:

Ekstensi kedua: Menggunakan tautan akhiran

Seperti biasa, # memperbarui menambahkan c secara otomatis ke tepi daun dan kami pergi ke titik aktif untuk melihat apakah kami dapat memasukkan 'c'. Itu berputar out 'c' sudah ada di tepi itu, jadi kami mengatur titik aktif ke (node1,'c',1), kenaikan remainder dan tidak melakukan apa pun.

Sekarang di langkah #= 10, remainder is 4, dan jadi kita harus memasukkan terlebih dahulu abcd (yang tersisa dari 3 langkah yang lalu) dengan memasukkan d di aktif titik.

Mencoba memasukkan d pada titik aktif menyebabkan tepi terbelah O (1) waktu:

Itu active_node, dari mana perpecahan itu dimulai, ditandai merah di atas. Inilah aturan terakhir, Aturan 3:

Setelah membelah tepi dari suatu active_node itu bukan akarnya   simpul, kita ikuti tautan akhiran yang keluar dari simpul itu, jika ada   ada, dan mengatur ulang active_node ke simpul yang ditunjuknya. Jika ada   tidak ada tautan akhiran, kami atur active_nodeke root. active_edge   dan active_length tetap tidak berubah.

Jadi titik aktifnya sekarang (node2,'c',1), dan node2 ditandai merah di bawah ini:

Sejak penyisipan abcd selesai, kita mengurangi remainder untuk 3 dan pertimbangkan suffix sisa selanjutnya dari langkah saat ini, bcd. Aturan 3 telah mengatur titik aktif ke titik dan tepi yang tepat jadi memasukkan bcd dapat dilakukan hanya dengan memasukkan karakter terakhirnya d di titik aktif.

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

Kami mengamati: Tautan akhiran memungkinkan kita untuk mereset titik aktif sehingga kita   dapat membuat yang berikutnya sisipan yang tersisa di O (1) usaha. Lihatlah   grafik di atas untuk mengkonfirmasi bahwa memang node di label ab terkait dengan   node di b (sufiksnya), dan simpul di abc terkait dengan    bc.

Langkah saat ini belum selesai. remainder sekarang adalah 2, dan kami perlu mengikuti aturan 3 untuk mereset titik aktif lagi. Sejak itu arus active_node (merah di atas) tidak memiliki tautan akhiran, kami atur ulang akar. Titik aktif sekarang (root,'c',1).

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

Dan karena ini melibatkan penciptaan simpul internal baru, kita ikuti aturan 2 dan setel tautan akhiran baru dari internal yang dibuat sebelumnya simpul:

(Saya menggunakan Graphviz Dot untuk yang kecil ini grafik. Tautan akhiran baru menyebabkan titik untuk mengatur ulang yang sudah ada ujung-ujungnya, jadi periksa dengan saksama untuk memastikan bahwa satu-satunya hal itu disisipkan di atas adalah tautan akhiran baru.)

Dengan ini, remainder dapat diatur ke 1 dan sejak active_node aku s root, kami menggunakan aturan 1 untuk memperbarui titik aktif ke (root,'d',0). Ini berarti insert terakhir dari langkah saat ini adalah menyisipkan satu d di root:

Itu adalah langkah terakhir dan kami selesai. Ada sejumlah terakhir observasi, meskipun:

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

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

  • remainder memberi tahu kami berapa banyak sisipan tambahan yang diperlukan membuat. Sisipan ini sesuai satu-ke-satu dengan akhiran akhir string yang berakhir pada posisi saat ini #. Kami mempertimbangkan satu setelah yang lain dan membuat insert. Penting: Setiap sisipan adalah dilakukan dalam O (1) sejak titik aktif memberitahu kita di mana harus pergi, dan kita perlu menambahkan hanya satu karakter tunggal di aktif titik. Mengapa? Karena karakter lainnya terkandung secara implisit (kalau tidak, titik aktif tidak akan berada di tempat).

  • Setelah setiap masukan seperti itu, kami mengurangi remainder dan ikuti tautan akhiran jika ada. Jika tidak kita pergi ke root (aturan 3). Jika kita sudah di root, kita memodifikasi titik aktif menggunakan aturan 1. Di dalam hal apapun, hanya membutuhkan waktu O (1).

  • Jika, selama salah satu sisipan ini, kita menemukan karakter yang kita inginkan untuk menyisipkan sudah ada, kita tidak melakukan apa - apa dan mengakhiri langkah saat ini, bahkan jika remainder> 0. Alasannya adalah apa pun sisipan yang tersisa akan menjadi sufiks dari yang baru saja kita coba membuat. Oleh karena itu mereka semua implisit di pohon saat ini. Faktanya bahwa remainder> 0 pastikan kita menangani akhiran yang tersisa kemudian.

  • Bagaimana jika di akhir algoritma remainder> 0? Ini akan menjadi kasus kapan pun akhir dari teks adalah substring yang terjadi suatu tempat sebelumnya. Dalam hal ini kita harus menambahkan satu karakter tambahan di ujung string yang belum pernah terjadi sebelumnya. Dalam sastra, biasanya tanda dolar $ digunakan sebagai simbol untuk bahwa. Kenapa itu penting? -> Jika nantinya kita menggunakan pohon akhiran yang sudah selesai untuk mencari sufiks, kita harus menerima kecocokan hanya jika mereka berakhir pada daun. Kalau tidak, kita akan mendapatkan banyak pertandingan palsu, karena ada banyak string secara implisit terkandung dalam pohon yang bukan sufiks aktual dari string utama. Memaksa remainder menjadi 0 pada akhirnya adalah suatu cara untuk memastikan bahwa semua akhiran 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 seluruh algoritma? Jika teksnya adalah n karakter panjangnya, jelas ada n langkah (atau n +1 jika kita tambahkan tanda dolar). Di setiap langkah, kami tidak melakukan apa pun (selain memperbarui variabel), atau kita buat remainder sisipan, masing-masing mengambil O (1) waktu. Sejak remainder menunjukkan berapa kali kita tidak melakukan apa-apa di langkah sebelumnya, dan dikurangi untuk setiap sisipan yang kita buat sekarang, jumlah total kali kita melakukan sesuatu adalah persis n (atau n + 1). Oleh karena itu, kompleksitas totalnya adalah O (n).

  • Namun, ada satu hal kecil yang tidak saya jelaskan dengan benar: Itu bisa terjadi bahwa kita mengikuti tautan akhiran, memperbarui yang aktif titik, dan kemudian menemukan itu active_length komponen tidak bekerja dengan baik dengan yang baru active_node. Misalnya, pertimbangkan situasi seperti ini:

(Garis putus-putus menunjukkan sisa pohon. Garis putus-putus adalah a tautan akhiran.)

Sekarang biarkan titik yang aktif (red,'d',3), jadi menunjuk ke tempat itu dibalik f pada defg tepi. Sekarang asumsikan kita membuat yang diperlukan perbarui dan sekarang ikuti tautan akhiran untuk memperbarui titik yang aktif menurut aturan 3. Titik aktif baru adalah (green,'d',3). Namun, itu d-pukulan keluar dari node hijau de, jadi hanya memiliki 2 karakter. Untuk menemukan titik aktif yang benar, kami jelas harus mengikuti ujung itu ke simpul biru dan setel ulang (blue,'f',1).

Dalam kasus yang sangat buruk, itu active_length bisa sebesar remainder, yang bisa sebesar n. Dan itu mungkin terjadi dengan sangat baik bahwa untuk menemukan titik aktif yang benar, kita tidak hanya perlu melompati satu node internal, tapi mungkin banyak, hingga n dalam kasus terburuk. Apakah itu berarti algoritma tersebut memiliki O yang tersembunyi (n2) kompleksitas, karena di setiap langkah remainder umumnya O (n), dan pasca-penyesuaian ke simpul aktif setelah mengikuti tautan akhiran bisa O (n) juga?

Tidak. Alasannya adalah jika memang kita harus menyesuaikan titik aktif (mis. dari hijau ke biru seperti di atas), yang membawa kita ke simpul baru itu memiliki tautan akhiran sendiri, dan active_length akan dikurangi. Sebagai kami mengikuti rantai tautan akhiran yang kami buat sisipan yang tersisa, active_length hanya dapat menurun, dan jumlah penyesuaian titik aktif yang dapat kita buat Cara tidak bisa lebih besar dari active_length pada waktu tertentu. Sejak active_length tidak pernah bisa lebih besar dari remainder, dan remainder adalah O (n) tidak hanya dalam setiap langkah, tetapi jumlah total kenaikan pernah dibuat untuk remainder selama keseluruhan proses O (n) juga, jumlah penyesuaian titik aktif juga dibatasi oleh Di).


2164
2018-03-01 09:13



Saya mencoba menerapkan Pohon Akhiran 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 akhiran benar-benar benar menggunakan pendekatan ini. Di bawah ini saya akan menulis "ikhtisar" jawaban jogojapan dengan beberapa modifikasi pada aturan. Saya juga akan menjelaskan kasus ketika kita lupa untuk membuat penting tautan akhiran.

Variabel tambahan yang digunakan

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

Mari gunakan konsep simpul internal - semua node, kecuali akar dan daun daun adalah simpul internal.

Observasi 1

Ketika akhir sufiks yang kita perlu masukkan ditemukan ada di pohon sudah, pohon itu sendiri tidak berubah sama sekali (kami hanya memperbarui active point dan remainder).

Observasi 2

Jika pada suatu saat active_length lebih besar atau sama dengan panjang tepi saat ini (edge_length), kami memindahkan active point turun sampai edge_length secara ketat lebih besar dari active_length.

Sekarang, mari kita mendefinisikan kembali aturannya:

Aturan 1

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

  1. simpul aktif tidak berubah
  2. panjang aktif dikurangi
  3. tepi aktif digeser ke kanan (ke karakter pertama dari akhiran berikutnya yang harus kita masukkan)

Aturan 2

Jika kita membuat yang baru simpul internal  ATAU membuat inserter dari simpul internal, dan ini bukan yang pertama SEPERTI ITU  simpul internal pada langkah saat ini, lalu kita tautkan sebelumnya SEPERTI ITU simpul dengan INI satu melalui tautan akhiran.

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

Aturan 3

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

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

Dan akhirnya, Observasi 3:

Ketika simbol yang ingin kita tambahkan ke pohon sudah di tepi, kita, menurut Observation 1, perbarui saja active point dan remainder, meninggalkan pohon itu tidak berubah. TAPI jika ada simpul internal ditandai sebagai membutuhkan akhiran tautan, kita harus menghubungkan simpul itu dengan arus kita active node melalui tautan akhiran.

Mari kita lihat contoh pohon sufiks untuk cdddcdc jika kita menambahkan tautan akhiran dalam hal demikian dan jika kita tidak:

  1. Jika kita JANGAN hubungkan node melalui tautan akhiran:

    • sebelum menambahkan huruf terakhir c:

    • setelah menambahkan huruf terakhir c:

  2. Jika kita MELAKUKAN hubungkan node melalui tautan akhiran:

    • sebelum menambahkan huruf terakhir c:

    • setelah menambahkan huruf terakhir c:

Sepertinya tidak ada perbedaan yang signifikan: pada kasus kedua ada dua tautan akhiran lagi. Tetapi tautan-tautan akhiran ini benar, dan salah satunya - dari simpul biru ke merah - sangat penting untuk pendekatan kami dengan titik aktif. Masalahnya adalah jika kita tidak menempatkan tautan akhiran di sini, nanti, ketika kita menambahkan beberapa huruf baru ke pohon, kita mungkin tidak menambahkan beberapa simpul ke pohon karena Rule 3, karena, menurutnya, jika tidak ada tautan akhiran, maka kita harus meletakkannya active_node ke root.

Ketika kami menambahkan huruf terakhir ke pohon, simpul merah itu sudah ada sebelum kami membuat insert dari simpul biru (tepi dicap 'c'). Karena ada sisipan dari simpul biru, kami menandainya sebagai membutuhkan tautan akhiran. Kemudian, bergantung pada titik aktif pendekatan, yang active node diatur ke simpul merah. Tapi kami tidak membuat insert dari simpul merah, seperti surat itu 'c' sudah di tepi. Apakah ini berarti simpul biru harus dibiarkan tanpa tautan akhiran? Tidak, kita harus menghubungkan simpul biru dengan simpul merah melalui tautan akhiran. Kenapa itu benar? Karena titik aktif pendekatan menjamin bahwa kita sampai ke tempat yang tepat, yaitu, ke tempat berikutnya di mana kita harus memroses penyisipan a singkat akhiran.

Akhirnya, inilah implementasi dari Suffix Tree:

  1. Jawa
  2. C ++

Harapan bahwa "ikhtisar" ini dikombinasikan dengan jawaban rinci jogojapan akan membantu seseorang untuk menerapkan Suffix Tree-nya sendiri.


112
2018-01-29 09:57



Terima kasih untuk tutorial yang dijelaskan dengan baik oleh @jogojapan, Saya mengimplementasikan 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 butuh beberapa hari untuk mendapatkan implementasi saya cukup kuat (Saya seharusnya). Masalah dan solusi tercantum di bawah ini:

  1. Berakhir dengan Remainder > 0 Ternyata situasi ini juga bisa terjadi selama langkah berlangsung, bukan hanya akhir dari seluruh algoritma. Ketika itu terjadi, kita dapat meninggalkan sisanya, actnode, actedge, dan actlength tidak berubah, akhiri langkah yang sedang berlangsung, dan mulai langkah lain dengan terus melipat atau membuka tergantung pada apakah char berikutnya dalam string asli berada di jalur saat ini atau tidak.

  2. Leap Over Nodes: Saat kami mengikuti tautan akhiran, perbarui titik aktif, dan kemudian temukan bahwa komponen active_length-nya tidak berfungsi dengan baik dengan active_node baru. Kita harus maju kedepan ke tempat yang tepat untuk membagi, atau masukkan daun. Proses ini mungkin tidak semudah itu karena selama menggerakkan actlength dan actedge terus berubah sepanjang jalan, ketika Anda harus kembali ke simpul akar, yang akting dan actlength bisa jadi salah karena gerakan itu. Kami membutuhkan variabel tambahan untuk menyimpan informasi itu.

    enter image description here

Dua masalah lainnya entah bagaimana telah ditunjukkan oleh @managonov

  1. Split Bisa Merosot Ketika mencoba untuk memecah tepi, kadang-kadang Anda akan menemukan operasi split tepat di node. Kasus itu kita hanya perlu menambahkan daun baru ke simpul itu, menganggapnya sebagai operasi pembagian tepi standar, yang berarti akhiran tautan jika ada, harus dipertahankan secara bersamaan.

  2. Tautan Sufiks Tersembunyi Ada kasus khusus lain yang terjadi masalah 1 dan masalah 2. Terkadang kita perlu melewati beberapa node ke titik yang tepat untuk perpecahan, kita mungkin melampaui titik yang tepat jika kita bergerak dengan membandingkan sisa string dan label path. Kasus itu tautan akhiran akan diabaikan secara tidak sengaja, jika harus ada. Ini bisa dihindari dengan mengingat titik yang tepat ketika bergerak maju. Tautan akhiran harus dipertahankan jika node perpecahan sudah ada, atau bahkan masalah 1 terjadi selama langkah berlangsung.

Akhirnya, implementasi saya di Python adalah sebagai berikut:

Kiat:  Ini termasuk yang naif pencetakan pohon berfungsi dalam kode di atas, yang sangat penting saat debugging. Itu menyelamatkan saya banyak   waktu dan nyaman untuk menemukan kasus-kasus khusus.


7
2017-08-02 02:35



Intuisi saya adalah sebagai berikut:

Setelah k iterasi dari loop utama Anda telah membangun sebuah pohon akhiran yang berisi semua akhiran dari string lengkap yang dimulai pada karakter k pertama.

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

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

Selama loop, kuncinya adalah titik aktif. Tebakan saya adalah bahwa ini merupakan titik terdalam di pohon akhiran yang sesuai dengan akhiran yang tepat dari karakter k pertama dari string. (Saya pikir yang tepat berarti bahwa akhiran tidak bisa menjadi keseluruhan string.)

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

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

Saat Anda menambahkan karakter baru, Anda melihat apakah titik aktif masih berada di pohon yang ada. Jika itu maka Anda selesai. Jika tidak, Anda perlu menambahkan simpul baru ke pohon akhiran di titik aktif, mundur ke kecocokan terpendek berikutnya, dan periksa lagi.

Catatan 1: Penanda akhiran memberikan tautan ke kecocokan terpendek berikutnya untuk setiap nodus.

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

Catatan 3: Bagian kanonisasi cukup menghemat waktu dalam memeriksa titik aktif. Misalnya, Anda selalu menggunakan origin = 0, dan hanya mengubah pertama dan terakhir. Untuk memeriksa titik aktif Anda harus mengikuti pohon akhiran setiap kali sepanjang semua simpul antara. Masuk akal untuk menyimpan cache hasil mengikuti jalur ini dengan merekam hanya jarak dari node terakhir.

Dapatkah Anda memberikan contoh kode dari apa yang Anda maksud dengan "memperbaiki" variabel pengikat?

Peringatan kesehatan: Saya juga menemukan algoritma ini sangat sulit dimengerti jadi harap sadari bahwa intuisi ini mungkin salah dalam semua detail penting ...


6
2018-02-26 20:16



Hai saya telah mencoba menerapkan implementasi yang dijelaskan di atas di ruby, silakan check it out. tampaknya berfungsi dengan baik.

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

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

3
2018-03-02 10:54



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

@makagonov sejak saya tinggal di dunia Jawa 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
  • pernyataan istirahat;
  • melanjutkan pernyataan;

Jadi saya berakhir dengan implementasi di Jawa yang saya harap mencerminkan semua langkah dengan 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);
        }
    });
  }
}

2
2018-04-21 14:22