Algoritma pencocokan string yang tepat manakah yang tercepat?

Itu tergantung pada masukan. Knuth-Morris-Pratt menjamin waktu kasus terburuk linier; Boyer-Moore seringkali tercepat dalam praktiknya pada teks alami karena melewati karakter dan berjalan sublinier secara rata-rata; Rabin-Karp unggul saat mencari banyak pola atau melakukan perbandingan sidik jari. Tidak ada satu pemenang universal.

Bagaimana Rabin-Karp menghindari membandingkan setiap karakter di setiap posisi?

Ia melakukan hashing pola dan setiap jendela teks dengan panjang yang sama menggunakan hash bergulir yang diperbarui dalam waktu konstan saat jendela bergeser. Hanya ketika hash cocok, ia memverifikasi karakter sebenarnya, sehingga sebagian besar posisi yang tidak cocok ditolak oleh satu perbandingan murah.

Pencocokan String

Pencocokan string menemukan semua kemunculan pola dalam sebuah teks; algoritma klasik memproses pola terlebih dahulu untuk melewati perbandingan yang berlebihan dan mencapai waktu pencarian linier atau sublinier.

Temukan Topik dengan PaperMindSegeraFind papers & topics

Tools & resources

Unduh salindia

Learn & explore

VideoSegera

Definition

Pencocokan string adalah masalah menemukan semua posisi dalam teks di mana string pola tertentu muncul; algoritma pencocokan string yang tepat melaporkan setiap offset di mana pola sejajar secara identik dengan substring teks.

Scope

Topik ini mencakup algoritma pencocokan pola tunggal yang tepat — metode naif, Knuth-Morris-Pratt, Boyer-Moore, dan Rabin-Karp berbasis hashing — bersama dengan prapemrosesan (fungsi kegagalan, tabel pergeseran, hash bergulir) yang membuatnya efisien, dan perluasan ke pencocokan multi-pola melalui automata Aho-Corasick. Pencocokan perkiraan dan pencarian berbasis indeks dibahas dalam topik terkait.

Core questions

Mengapa pencocokan naif membutuhkan waktu yang sebanding dengan hasil kali panjang pola dan teks?
Bagaimana prapemrosesan pola menghindari pemeriksaan ulang karakter teks?
Bagaimana fungsi kegagalan Knuth-Morris-Pratt dan aturan pergeseran Boyer-Moore bekerja?
Bagaimana Rabin-Karp menggunakan hashing untuk menguji keselarasan dengan cepat?
Bagaimana pencocokan diperluas ke banyak pola secara bersamaan?

Key concepts

pencocokan naif
algoritma Knuth-Morris-Pratt
fungsi kegagalan
algoritma Boyer-Moore
aturan karakter buruk dan sufiks baik
algoritma Rabin-Karp
hash bergulir
automata Aho-Corasick

Key theories

Fungsi kegagalan Knuth-Morris-Pratt: Dengan menghitung terlebih dahulu, untuk setiap prefiks pola, prefiks proper terpanjang yang juga merupakan sufiks, algoritma Knuth-Morris-Pratt menggeser pola secara cerdas setelah ketidakcocokan dan tidak pernah memeriksa ulang karakter teks, memberikan pencocokan waktu linier.
Pemindaian kanan-ke-kiri Boyer-Moore: Boyer-Moore membandingkan pola dari karakter terakhirnya ke belakang dan menggunakan aturan karakter buruk dan sufiks baik untuk melewati sebagian besar teks, mencapai kinerja kasus rata-rata sublinier pada masukan tipikal.

Clinical relevance

Pencocokan string mendasari alat dan infrastruktur sehari-hari: pencarian di editor teks dan utilitas baris perintah, pemfilteran konten dan pemindaian tanda tangan deteksi intrusi, deteksi plagiarisme, dan lokasi motif dalam urutan biologis. Pencocokan multi-pola menskalakan ini ke kamus banyak pola sekaligus.

History

Algoritma Knuth-Morris-Pratt (diterbitkan 1977, dikembangkan sebelumnya) memberikan pencocok tepat waktu linier pertama yang dikenal luas, dan Boyer dan Moore (1977) memperkenalkan pencocokan kasus rata-rata sublinier pada tahun yang sama. Pendekatan hashing Rabin dan Karp serta automata multi-pola Aho-Corasick (1975) semakin memperluas bidang ini.

Key figures

Donald Knuth
James H. Morris
Vaughan Pratt
Robert Boyer
J Strother Moore
Michael Rabin
Richard Karp

Seminal works

knuth1977
boyer1977
cormen2009

Frequently asked questions

Algoritma pencocokan string yang tepat manakah yang tercepat?: Itu tergantung pada masukan. Knuth-Morris-Pratt menjamin waktu kasus terburuk linier; Boyer-Moore seringkali tercepat dalam praktiknya pada teks alami karena melewati karakter dan berjalan sublinier secara rata-rata; Rabin-Karp unggul saat mencari banyak pola atau melakukan perbandingan sidik jari. Tidak ada satu pemenang universal.
Bagaimana Rabin-Karp menghindari membandingkan setiap karakter di setiap posisi?: Ia melakukan hashing pola dan setiap jendela teks dengan panjang yang sama menggunakan hash bergulir yang diperbarui dalam waktu konstan saat jendela bergeser. Hanya ketika hash cocok, ia memverifikasi karakter sebenarnya, sehingga sebagian besar posisi yang tidak cocok ditolak oleh satu perbandingan murah.