Tolong Baidu untuk beberapa konsep dasar array sufiks. Sederhananya, array sufiks adalah kumpulan dari semua ukuran sufiks dari string. Kemudian kita dapat mencapai berbagai kebutuhan berdasarkan beberapa sifat array akhiran.
kelas publik mySuffixArraytest {public char [] sufiks; // string asli int n; // string length public int [] peringkat; // peringkat sufiks [i] di semua akhir public int [] sa; // sufiks [1] dengan kadar [sa] [2] ... <suffix [sa [sa [len]], itu, itu, peringkatnya [sa] ... <suffix [sa [sa [len]], yaitu, kanker itu dengan peringkat [2] ... <suffix [sa [len]], ya, itu, peringkatnya dengan peringkat [2] ... Peringkat) Publik int [] tinggi; // menunjukkan akhiran [SA [i]] dan akhiran [SA [i - 1]], yaitu, awalan publik terpanjang dari dua sufiks yang berdekatan, int [] h; // sama dengan ketinggian [I], yaitu public incranta public (sortir public quxix [i] dan sufiks publikasi sebelumnya. y; // Kata kunci kedua peringkat array publik int [] x; // peringkat array bantu}Penjelasan berikut mengambil string "aabaaaab" sebagai contoh. Pertama -tama mari kita tunjukkan hasilnya. Silakan merujuk hasil ini untuk pemahaman dan analisis (saya menyalin gambar orang lain tentang hasil ini. Harap Subskrip 1 secara default, karena array saya dimulai dengan subskrip 0)
Sufiks: Array string asli mengasumsikan bahwa string asli adalah "aabaaaab", maka nilai yang sesuai dari array ini harus {'a', 'a', 'b', 'a', 'a', 'a', 'b'}
N: Panjang string di sini n adalah 8
Peringkat: Array peringkat array sufiks setara dengan peringkat yang sesuai dengan akhiran i-th. Misalnya, peringkat [0] mengacu pada peringkat akhiran "aabaaaab" peringkat [1] mengacu pada peringkat akhiran "abaaaab"
SA: Ini adalah array yang terbalik ke array peringkat. Apakah X-simpul menyimpan akhiran? Atau untuk memberikan contoh untuk menggambarkan bahwa SA [0] mengacu pada array akhiran peringkat pertama, yaitu, 3. yaitu, peringkat yang sesuai [3] dari array adalah 0. Harap pastikan untuk memahami formula SA [peringkat [i]] = i. Jika Anda memahami hubungan antara SA dan peringkat, Anda juga harus memahaminya.
height: height[i] is the length of the largest common prefix of the sa[i] suffix array and the sa[i-1] suffix array height[1] refers to the second and first largest common prefixes sa[1] and sa[0] that is, the largest common prefixes of "aaab" and "aaaab" naturally see height[1]=3 at a glance
H: H [i] mengacu pada akhiran i-th dan awalan publik terbesar dari yang sebelumnya h [0] mengacu pada array sufiks pertama, yaitu "aabaaaab" dan awalan publik terbesar dari yang sebelumnya, yaitu "AAB", yaitu tinggi [peringkat 0]] = tinggi [3] = 3 Ini sedikit sulit untuk dipahami. Anda tidak dapat mengerti untuk saat ini dan melanjutkan membaca.
WS: tidak ada yang perlu dikatakan, hitung penyortiran array tambahan
Y: Kata kunci kedua adalah array SA dengan kata kunci kedua yang diurutkan setara dengan kata kunci kedua
X: Anda dapat memahaminya sebagai cadangan array peringkat. Awalnya menggunakan cadangan array peringkat, dan kemudian merekam array peringkat setelah setiap loop
Pertama, mari kita lihat kode untuk array SA. Saya akan menjelaskan fungsi kode satu per satu dan melampirkan kode total ke yang berikut
peringkat = int new [n]; SA = int new [n]; ws = int baru [255]; y = int baru [n]; x = int new [n]; // Loop string asli untuk mengonversi nilai int menjadi array peringkat untuk (int i = 0; i <n; i ++) {peringkat [i] = (int) sufiks [i]; }Fungsi kode di atas adalah untuk menginisialisasi array dan melakukan penghitungan dan penyortiran pertama. Loop pertama adalah menetapkan nilai awal ke array peringkat. Setelah eksekusi, nilai yang sesuai dari array peringkat adalah {97, 97, 98, 97, 97, 97, 97, 98}. Anda harus melihat bahwa nilai awal dari array peringkat adalah kode ASCII yang sesuai dengan surat tersebut.
Tiga siklus berikutnya adalah penyortiran penghitungan pertama. Jika Anda tidak mengerti menghitung penyortiran, silakan Baidu. Izinkan saya berbicara tentang proses tiga siklus ini
untuk (int i = 0; i <n; i ++) {ws [peringkat [i]] ++; x [i] = peringkat [i]; } untuk (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; }Apa yang dilakukan kedua loop ini adalah menghitung semua nilai kejadian dan mencadangkan array peringkat ke array x. Setelah loop pertama dijalankan, WS [97] = 6, WS [98] = 2, dan setelah loop kedua dijalankan, WS [97] = 6, WS [98] = 8
untuk (int i = n-1; i> = 0; i--) {sa [-ws [peringkat [i]]] = i; }Paragraf di atas adalah kode spesifik untuk menghitung dan menyortir untuk menemukan array SA. Setiap orang harus salah paham saat pertama kali membacanya. Mengapa mereka menemukan SA? Saya juga bingung untuk pertama kalinya, tapi tolong bersabar dan pahami kode ini dengan cermat. Apakah Anda masih ingat formula yang disebutkan di atas SA [peringkat [i]] = Saya misalnya, untuk akhiran "B", kami meminta SA -nya, yaitu SA [peringkat [7]] = SA [98] = 7. Jelas, SA [98] tidak ada, tetapi kami telah mencatat berapa kali 98 muncul di array WS, jadi WS [98] harus menjadi peringkat yang sesuai dari "B". Tolong jangan lupa untuk mengurangi 1 menjadi SA [-WS [peringkat [i]]] = i. Adapun mengapa Anda perlu melintasi dari belakang ke depan, Anda perlu memahaminya dengan cermat di sini, jika tidak, Anda pasti akan benar -benar dibutakan dengan cara Anda mengurutkannya sesuai dengan kata kunci kedua. Bagaimana Anda mengurutkannya jika ada dua nilai peringkat yang sama? Itu harus muncul pertama di depan array SA. Jika Anda berpikir tentang loop ini dan perubahan dalam nilai array WS, Anda akan memahami bahwa urutan loop sebenarnya mewakili urutan pengaturan ketika nilai peringkatnya sama. Traversal dari belakang ke depan berarti bahwa peringkat akhiran juga lebih rendah ketika nilai peringkatnya sama.
Di atas hanyalah penyortiran penghitungan pertama, yang setara dengan hanya membandingkan huruf pertama dari setiap array sufiks untuk menemukan SA. Hasil yang sesuai seperti yang ditunjukkan pada gambar di bawah ini.
// loop kombinasi sort untuk (int j = 1, p = 0; j <= n; j = j << 1) {// Jika Anda perlu mengisinya, tambahkan array penyortiran pertama yp = 0; untuk (int i = n - j; i <n; i ++) {y [p ++] = i; } // Rentang kata kunci kedua sesuai dengan kata kunci pertama SA untuk (int i = 0; i <n; i ++) {if (sa [i]> = j) {y [p ++] = sa [i] - j; }} // Menyortir dua kata kunci untuk (int i = 0; i <ws.length; i ++) {ws [i] = 0; } untuk (int i: x) {ws [i] ++; } untuk (int i: x) {ws [i] ++; } untuk (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } untuk (int i = n-1; i> = 0; i--) {sa [-ws [x [y [i]]] = y [i]; y [i] = 0; } // Hitung array peringkat dari SA int xb [] = int [n]; // x cadangan array untuk (int i = 0; i <n; i ++) {xb [i] = x [i]; } int number = 1; x [SA [0]] = 1; untuk (int i = 1; i <n; i ++) {if (xb [sa [i]]! = xb [sa [i - 1]]) {x [sa [i]] = ++ angka; } else if (sa [i] + j> = n && sa [i - 1] + j> = n) {x [sa [i]] = angka; } else if (sa [i] + j <n && sa [i - 1] + j> = n) {x [sa [i]] = ++ angka; } lain jika (xb [sa [i] + j]! = xb [sa [i - 1] + j]) {x [sa [i]] = ++ angka; } else {x [sa [i]] = angka; } if (number> = n) break; }}Ini adalah kode yang paling sulit untuk dipahami ketika menemukan array SA. Pertama -tama, Anda perlu memahami gagasan algoritma multiplikasi. Setelah pesanan penghitungan pertama, apakah kita sudah tahu penyortiran surat awal pertama dari semua array sufiks? Karena kita tahu penyortiran surat awal pertama setara dengan urutan surat keduanya (perhatikan perbedaan antara penyortiran dan ketertiban. Penyortirannya adalah bahwa kita tahu mana yang ditetapkannya. Urutannya adalah bahwa kita hanya tahu urutan yang muncul, tetapi kita tidak tahu mana yang secara khusus dia peringkat). Ini tentu saja, karena mereka berasal dari string, dan untuk setiap akhiran, itu juga dapat digunakan sebagai akhiran untuk akhiran sebelumnya. Ngomong -ngomong, misalnya, untuk "baaaab" urutan huruf pertamanya sesuai dengan urutan kata kunci kedua "abaaaab". Dengan urutan kata kunci pertama dan jenis kata kunci kedua, kita dapat menemukan jenis gabungan dari dua kata kunci. Menurut hasil dari jenis kombinasi, kita masih bisa menggunakan ide sebelumnya. Setelah kombinasi pertama dari "baaaab", kami memilah urutan dua huruf pertama "BA", sehingga ia juga dapat menggunakan urutan kata kunci kedua "aabaaaab". Logika dari seluruh jenis dirujuk di bawah ini
Kemudian kami akan menganalisis kode di segmen
untuk (int i = n - j; i <n; i ++) {y [p ++] = i; } // Pilih kata kunci kedua sesuai dengan kata kunci pertama SA untuk (int i = 0; i <n; i ++) {if (sa [i]> = j) {y [p ++] = sa [i] - j; }}Kode di atas adalah menemukan SA, yaitu, array Y dari kata kunci kedua, dengan nilai awal p menjadi 0, dan loop pertama adalah untuk memberi peringkat akhiran yang perlu diisi di bagian depan array.
Anda perlu memahami logika loop kedua dalam kombinasi dengan diagram logika sebelumnya. Kami melintasi hasil penyortiran dari kata kunci pertama SA. If (SA [i]> = j) menentukan apakah akhiran dapat digunakan sebagai kata kunci kedua untuk sufiks lainnya. Mengambil loop pertama j = 1 sebagai contoh, ketika SA [i] = 0 mewakili array akhiran "aabaaaab", jelas tidak dapat digunakan sebagai kata kunci kedua untuk sufiks lainnya. Untuk kata kunci kedua yang dapat digunakan sebagai sufiks lainnya, urutan SA -nya adalah kata kunci kedua yang sesuai. SA [i] - J menemukan sufiks miliknya sebagai kata kunci kedua dan meletakkannya di array y, dan p ++. Anda perlu mengerti di sini perlahan.
// gabungkan jenis dua kata kunci untuk (int i = 0; i <ws.length; i ++) {ws [i] = 0; } untuk (int i: x) {ws [i] ++; } untuk (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } untuk (int i = n-1; i> = 0; i--) {sa [-ws [x [y [i]]]] = y [i]; y [i] = 0; }Di atas adalah menemukan penyortiran kombinasi berdasarkan kata kunci pertama menyortir SA dan kata kunci kedua menyortir y. Kode ini cukup tidak jelas. Pertama -tama kita tidak dapat memahami kode, tetapi memahami sebuah ide. Untuk penyortiran dua kata kunci, aturan aktual mirip dengan penyortiran dua angka. Misalnya, 11 dan 12 membandingkan ukurannya, 10 bit adalah kata kunci pertama, dan bit tunggal adalah kata kunci kedua. Setelah membandingkan 10 bit, kami menemukan 11 = 12, dan kemudian membandingkan bit tunggal, kami tahu bahwa 11 <12. Jika 10 bitnya sama, urutan bit tunggal adalah urutan ukuran. Saya mengatakan pertama kali saya menghitung penyortiran di atas bahwa urutan penyortiran penghitungan untuk loop sebenarnya mewakili urutan pengaturan ketika nilai peringkatnya sama. Jadi bagaimana kita menemukan pesanan setelah dua kata kunci digabungkan dalam satu penghitungan penyortiran? Biarkan saya memberi tahu Anda pemahaman saya. Satu jenis penghitungan sebenarnya berisi dua jenis, satu adalah jenis nilai numerik, dan yang lainnya adalah jenis urutan kejadian. Aturannya setara dengan contoh perbandingan sebelumnya dari 11 dan 12. Jenis nilai numerik adalah 10 bit, dan jenis urutan kejadian adalah satu bit. Pada titik ini, kami punya ide. Penyortiran nilai diurutkan berdasarkan kata kunci pertama, dan penyortiran kejadian diurutkan berdasarkan kata kunci kedua, sehingga kita dapat menghitung dan mengurutkan pada satu waktu untuk menemukan penyortiran setelah dua kata kunci digabungkan. Kode di atas adalah implementasi ide ini. Array X adalah array peringkat dari kata kunci pertama, dan kami menghitungnya.
untuk (int i = n-1; i> = 0; i--) {sa [-ws [x [y [i]]]] = y [i]; y [i] = 0; }Loop ini adalah implementasi dari semua ide di atas. Kami melintasi array kata kunci kedua dari belakang. Untuk y [i], kami menghitung peringkat penghitungan dari kata kunci pertamanya. Peringkat penghitungan ini adalah peringkat y [i], dan penghitungan akhir dikurangi 1. Jenis kata kunci gabungan berhasil ditemukan.
Saya percaya bahwa jika Anda memahami semua kode di atas, Anda pasti akan kagum. Saya juga senang ketika saya memikirkan kode ini berulang kali, dan saya hanya yakin. Ini adalah pesona algoritma.
Dengan array SA, kita dapat menemukan array peringkat. Ini tidak sulit, jadi kami tidak akan menjelaskannya. Semua kode untuk menemukan SA dilampirkan di bawah ini.
public static void main (string [] args) {string str = "aabaaaab"; MySuffixArrayTest arraytest = mySuffixArrayTest baru (str.toString ()); arraytest.initsa (); // temukan SA array} public void initsa () {rank = int int [n]; SA = int new [n]; ws = int baru [255]; y = int baru [n]; x = int new [n]; // Loop string asli untuk mengonversi nilai int menjadi array peringkat untuk (int i = 0; i <n; i ++) {peringkat [i] = (int) sufiks [i]; } // sortir hitungan pertama untuk (int i = 0; i <n; i ++) {ws [peringkat [i]] ++; x [i] = peringkat [i]; } untuk (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } untuk (int i = n-1; i> = 0; i--) {sa [-ws [peringkat [i]]] = i; } // Loop Combination Sort for (int j = 1, p = 0; j <= n; j = j << 1) {// Jika Anda perlu mengisi, tambahkan array yang diurutkan pertama yp = 0; untuk (int i = n - j; i <n; i ++) {y [p ++] = i; } // Rentang kata kunci kedua sesuai dengan kata kunci pertama SA untuk (int i = 0; i <n; i ++) {if (sa [i]> = j) {y [p ++] = sa [i] - j; }} // Menyortir dua kata kunci untuk (int i = 0; i <ws.length; i ++) {ws [i] = 0; } untuk (int i: x) {ws [i] ++; } untuk (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } untuk (int i = n-1; i> = 0; i--) {sa [-ws [x [y [i]]] = y [i]; y [i] = 0; } // Hitung array peringkat berdasarkan SA int xb [] = int [n]; // x cadangan array untuk (int i = 0; i <n; i ++) {xb [i] = x [i]; } int number = 1; x [SA [0]] = 1; untuk (int i = 1; i <n; i ++) {if (xb [sa [i]]! = xb [sa [i - 1]]) {x [sa [i]] = ++ angka; } else if (sa [i] + j> = n && sa [i - 1] + j> = n) {x [sa [i]] = angka; } else if (sa [i] + j <n && sa [i - 1] + j> = n) {x [sa [i]] = ++ angka; } lain jika (xb [sa [i] + j]! = xb [sa [i - 1] + j]) {x [sa [i]] = ++ angka; } else {x [sa [i]] = angka; } if (number> = n) break; }}}}Meringkaskan
Di atas adalah contoh kode untuk array kantung array sufiks java yang diperkenalkan kepada Anda. Saya harap ini akan membantu Anda. Jika Anda memiliki pertanyaan, silakan tinggalkan saya pesan dan editor akan membalas Anda tepat waktu. Terima kasih banyak atas dukungan Anda ke situs web Wulin.com!