Saya sedang mengerjakan algoritma pencarian string yang mendukung pencarian banyak pola. Saya menemukan dua algoritma yang tampak seperti kandidat terkuat dalam hal menjalankan waktu, yaitu Aho-Corasick dan Rabin-Karp . Namun, saya tidak dapat menemukan perbandingan komprehensif antara kedua algoritma. Algoritma mana yang lebih efisien? Juga, mana yang lebih cocok untuk komputasi paralel dan pencarian banyak pola? Akhirnya, mana yang membutuhkan lebih sedikit sumber daya perangkat keras?
Untuk algoritma AC, fase pencarian membutuhkan waktu , sedangkan O ( n m ) untuk RK. Namun, waktu berjalan untuk RK adalah O ( n + m ) yang membuatnya mirip dengan AC. Kesimpulan sementara saya adalah bahwa RK tampak praktis lebih baik karena tidak membutuhkan banyak memori seperti AC. Apakah itu benar?
Jawaban:
Analisis waktu berjalan asimptotik tidak mungkin menjadi alat terbaik untuk memilih antara kedua algoritma ini: analisis asimptotik mengabaikan faktor konstan, dan faktor konstan akan menjadi kritis di sini. Kedua algoritma pada dasarnya memiliki waktu berjalan asimptotik yang sama, jadi analisis asimptotik mungkin tidak terlalu membantu untuk memilih di antara mereka.
Sebagai gantinya, cara yang benar memilih antara kedua algoritma adalah melalui analisis eksperimental. Identifikasi beban kerja yang representatif, dan kemudian patok kinerja kedua algoritma pada beban kerja Anda, pada jenis mesin yang ingin Anda gunakan dalam praktik.
sumber
tetapi dengan pertanyaan implisit Anda untuk "perbandingan komprehensif", beberapa makalah telah ditulis secara eksperimental / empiris membandingkan kedua algoritma ini dan lainnya pada data nyata dan termasuk analisis / perbandingan pro / kontra / pengorbanan dari algoritma yang berbeda misalnya:
Metodologi Pencocokan String Pola Berganda: Analisis Komparatif / Khan, Pateriya
STUDI PERBANDINGAN PADA ALGORITMA PENCARIAN STRING DARI URUTAN BIOLOGIS / Pandiselvam, Marimuthu, Lawrance
sumber