Algoritme pencarian string mana yang paling cepat?

Saya telah terjebak selama beberapa waktu yang merupakan algoritma pencarian string tercepat, mendengar banyak pendapat, tetapi pada akhirnya saya tidak yakin.

Saya telah mendengar beberapa orang mengatakan bahwa algoritma tercepat adalah Boyer-Moore dan beberapa mengatakan bahwa Knuth-Morris-Pratt sebenarnya lebih cepat.

Saya telah mencari kompleksitas pada keduanya, tetapi mereka kebanyakan terlihat sama O(n+m). Saya telah menemukan bahwa dalam skenario terburuk Boyer-Moore memiliki O(nm)kompleksitas dibandingkan dengan Knuth-Morris-Pratt yang memiliki O (m + 2 * n). Di mana n = panjang teks dan m = panjang pola.

Sejauh yang saya tahu Boyer-Moore memiliki linier-waktu-kasus terburuk jika saya akan menggunakan Aturan Galil.

Pertanyaan saya, Lebih dari semua yang sebenarnya merupakan algoritma pencarian String tercepat (Pertanyaan ini mencakup semua kemungkinan algoritma menyengat, bukan hanya Boyer-Moore dan Knuth-Morris-Pratt).

Sunting: Karena jawaban ini

Apa yang sebenarnya saya cari adalah:

Diberikan teks Tdan pola Psaya harus menemukan semua penampilan Pdi T.

Juga panjang P dan T berasal [1,2 000 000]dan program harus berjalan di bawah 0,15 detik.

Saya tahu bahwa KMP dan Rabin-Karp sudah cukup untuk mendapatkan skor 100% untuk masalah ini, tetapi saya ingin seseorang ingin mencoba dan mengimplementasikan Boyer-Moore. Mana yang terbaik untuk jenis pencarian pola ini?

Itu tergantung pada jenis pencarian yang ingin Anda lakukan. Setiap algoritma berkinerja sangat baik untuk jenis pencarian tertentu, tetapi Anda belum menyatakan konteks pencarian Anda.

Berikut ini beberapa pemikiran umum tentang jenis pencarian:

• Boyer-Moore: bekerja dengan pra-menganalisis pola dan membandingkan dari kanan ke kiri. Jika ketidakcocokan terjadi, analisis awal digunakan untuk menentukan seberapa jauh pola dapat digeser dengan teks yang dicari. Ini bekerja sangat baik untuk pola pencarian yang panjang. Secara khusus, ini bisa sub-linear, karena Anda tidak perlu membaca setiap karakter teks Anda.

• Knuth-Morris-Pratt: juga melakukan pra-analisis pola, tetapi mencoba untuk menggunakan kembali apa pun yang sudah cocok di bagian awal pola untuk menghindari harus membuat ulang itu. Ini bisa bekerja dengan baik, jika alfabet Anda kecil (mis. Basis DNA), karena Anda mendapat peluang lebih tinggi bahwa pola pencarian Anda mengandung subpastern yang dapat digunakan kembali.

• Aho-Corasick: Perlu banyak preprocessing, tetapi melakukannya untuk sejumlah pola. Jika Anda tahu Anda akan mencari pola pencarian yang sama berulang kali, maka ini jauh lebih baik daripada yang lain, karena Anda perlu menganalisis pola hanya sekali, bukan sekali per pencarian.

Karenanya, seperti biasa dalam CS, tidak ada jawaban pasti untuk keseluruhan terbaik . Ini lebih merupakan masalah memilih alat yang tepat untuk pekerjaan yang dihadapi.

Catatan lain tentang alasan terburuk Anda: Pertimbangkan jenis-jenis pencarian yang diperlukan untuk membuat terburuk itu dan pikirkan dengan seksama apakah ini benar-benar relevan dalam kasus Anda. Sebagai contoh, O(mn)kompleksitas kasus terburuk dari algoritma Boyer-Moore berasal dari pola pencarian dan teks yang setiap penggunaan hanya satu karakter (seperti menemukan aaadi aaaaaaaaaaaaaaaaaaaaa) - apakah Anda benar-benar harus cepat untuk pencarian seperti itu?

Meskipun saya sedikit terlambat untuk menjawab pertanyaan ini, tetapi saya pikir Z-Algorithmjauh lebih cepat daripada rekan-rekannya. Kompleksitas kasus terburuknya adalah O (m + n) dan tidak memerlukan preprocessing dari pola / teks. Kode ini juga sangat mudah dibandingkan dengan algoritma lainnya.

Ini bekerja dengan cara berikut.

Misalnya ada string S ='abaaba'. Kita harus menemukan z(i)nilai untuk i=0 to len(S)-1. Sebelum masuk ke penjelasan, izinkan saya meletakkan beberapa definisi terlebih dahulu.

z(i)= tidak. karakter dari awalan Syang cocok dengan awalan dari s(i).

s(i)= ithakhiran dari S.

Berikut ini adalah s(i) nilai untuk s = 'abaaba'.

s(0) = 'abaaba' = S
s(1) = 'baaba'
s(2) = 'aaba'
s(3) = 'aba'
s(4) = 'ba'
s(5) = 'a'

Nilai z masing-masing

z(0) = 6 = length(S)
z(1) = 0
z(2) = 1
z(3) = 3
z(4) = 0
z(5) = 1

Untuk pemahaman detail tentang algoritma, lihat tautan berikut.

http://codeforces.com/blog/entry/3107

https://www.youtube.com/watch?v=MFK0WYeVEag

Sekarang dibutuhkan O (N) untuk menemukan semua z nilai tanpa overhead pra-pemrosesan. Orang akan bertanya-tanya sekarang bagaimana Anda bisa menggunakan logika ini untuk mencocokkan pola dalam string yang diberikan?

Mari kita lihat dengan sebuah contoh. Pola (P) aba:, Teks (T):aacbabcabaad .

Masukkan ini dalam bentuk P $ T. ( $- karakter apa pun yang tidak muncul dalam pola atau teks. Saya akan segera membahas pentingnya $.)

P$T = aba$aacbabcabaad

Kami tahu len(P)= 3.

Semua nilai z P$Tadalah

z(0) = 16 = len(P$T)
z(1) = 0
z(2) = 1
z(3) = 0
z(4) = 1
z(5) = 1
z(6) = 0
z(7) = 0
z(8) = 2
z(9) = 0
z(10) = 0
z(11) = 3
z(12) = 0
z(13) = 1
Z(14) = 1
Z(15) = 0

Sekarang yang z(i)= len(P). Ans = 11.Jadi pola kita ada di Ans-len(P)-1= 7. -1adalah untuk $karakter.

Sekarang mengapa $atau karakter khusus seperti itu penting. Pertimbangkan P = 'aaa'dan T = 'aaaaaaa'. Tanpa karakter khusus, semua z(i)akan memiliki nilai tambahan. Seseorang masih dapat menemukan posisi pola dalam teks dengan rumus di bawah ini:

Kondisi: z(i)> = len(P)dan Posisi: Ans-len(P). Tetapi kondisi dalam kasus ini menjadi sedikit rumit dan membingungkan. Saya pribadi lebih suka menggunakan teknik karakter khusus.

Gunakan memori yang dapat dialamatkan konten , diimplementasikan dalam perangkat lunak dalam bentuk pengalamatan virtual (menunjuk huruf ke huruf).

Ini agak berlebihan untuk algoritma pencocokan string rata-rata.

CAM dapat mencocokkan sejumlah besar pola secara bersamaan, hingga sekitar 128 pola huruf (jika ASCII; jika hanya Unicode 64). Dan itu satu panggilan per panjang huruf dalam string yang ingin Anda cocokkan dan satu pembacaan acak dari memori per panjang panjang pola maks. Jadi jika Anda menganalisis string 100.000 huruf, dengan hingga 90.000.000 pola secara bersamaan (yang akan memakan waktu sekitar 128 GiB untuk menyimpan jumlah pola yang besar), itu akan memerlukan 12.800.000 bacaan acak dari RAM, sehingga itu akan terjadi dalam 1 ms.

Inilah cara kerja pengalamatan virtual.

Jika saya mulai dengan 256 alamat awal, yang mewakili huruf pertama, huruf-huruf ini menunjuk ke 256 dari huruf berikutnya. Jika suatu pola tidak ada, Anda tidak menyimpannya.

Jadi jika saya terus menghubungkan surat dengan surat, itu seperti memiliki 128 iris pengalamatan virtual yang menunjuk ke pengalamatan virtual.

Itu akan berhasil - tetapi untuk mendapatkan 900.000.000 pola yang serentak cocok, ada satu trik terakhir untuk ditambahkan - dan ini mengambil keuntungan dari fakta bahwa Anda memulai dengan banyak menggunakan kembali buffer surat ini, tetapi kemudian mencerai-beraikan. Jika Anda daftar konten, alih-alih mengalokasikan semua 256 karakter, maka itu melambat sangat sedikit, dan Anda akan mendapatkan peningkatan kapasitas 100 kali, karena pada dasarnya Anda hanya mendapatkan 1 huruf yang digunakan dalam setiap buffer penunjuk huruf (yang saya juluki ' melarikan diri').

Jika Anda ingin mendapatkan kecocokan string tetangga-terdekat, maka Anda memiliki banyak dari ini berjalan secara paralel dan Anda kumpulkan dalam hierarki, sehingga Anda menyebarkan kesalahan Anda tanpa bias. jika Anda mencoba tetangga terdekat hanya dengan satu, maka Anda bias menuju awal pohon.