Perbandingan antara algoritma Aho-Corasick dan algoritma Rabin-Karp

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 untuk RK. Namun, waktu berjalan untuk RK adalah 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? $O(n+m)$ $O(nm)$ $O(n+m)$

algorithms algorithm-analysis runtime-analysis strings Elang
sumber

Apakah semua pola Anda memiliki panjang yang sama?

Hendrik Jan

@ HendrikJan Tidak, pola panjang berbeda

Elang

Jika polanya berbeda panjang, sepertinya sulit untuk memprosesnya secara paralel menggunakan RK? Halaman wikipedia tampaknya menyarankan pola-pola ini memiliki panjang yang sama, meskipun memperbarui hash dapat dilakukan untuk panjang yang berbeda.

Hendrik Jan

Apakah Anda tertarik pada semacam studi teoritis atau pengalaman praktis?

Raphael

@Raphael Secara akademis, kami dulu menerapkan studi teoritis terlebih dahulu sebelum kami membuktikannya secara empiris. Saya memposting pertanyaan di sini karena saya tidak mengharapkan jawaban pemrograman. Saya membutuhkan jawaban algoritmik yang logis

Elang

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.

$O(nm)$ $O(n+m)$

$O(n+m)$ $c\cdot(n+m)$ $c$ $O(n+m)$

$O(n+m)$ $O(nm)$

DW
sumber

Namun, saya tidak dapat menemukan perbandingan komprehensif antara kedua algoritma.

$O(n + m)$ $O(n m)$

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

vzn
sumber