Pencocokan pola probabilistik linier dan algoritma Rabin-Karp

Solusi sains dan teknologi -- Kebanyakan algoritma pencarian string linier sulit diterapkan, dan memerlukan preprocessing pola yang berat sebelum menjalankan pencarian.Artikel ini menyajikan algoritma Rabin-Karp, algoritma pencarian string probabilistik sederhana yang didasarkan pada uji kesetimbangan hashing dan polinomial, bersamaan dengan implementasi Python.Sebuah varian streaming dari algoritma dan generalisasi untuk mencari beberapa pola dalam satu pass atas input juga dijelaskan, dan aspek kinerja dibahas.Algoritma ini probabilistik karena tidak selalu mengembalikan hasil yang benar; lebih tepatnya, ia mengembalikan semua kecocokan yang valid dan (dengan probabilitas yang cukup kecil) beberapa pertandingan yang salah (algoritma seperti ini cenderung terlalu optimis dalam melaporkan hasilnya biasanya dianggap benar-bias).

Solusi sains dan teknologi -- Algoritma Mengingat string s dari panjang \ (n \), dan pola panjang \ (k \), algoritma menghitung checksum rolling untuk kedua pola ("jarum") dan substring berturut-turut daripanjang \ (k \) dari string yang dicari ("tumpukan jerami").Setiap kali checksum substring sama dengan pola, kecocokan dilaporkan.cocok = {} pattern_checksum = checksum (pola) substring_checksum = checksum (s [0: k [) untuk posisi dari 0 sampai n - k - 1 lakukan perbarui substring_checksum ke checksum (s [posisi: posisi k [) jika substring_checksum = pattern_checksum itu tambahkan posisi ke pertandingan kembali cocok Fungsi checksum Secara formal, fungsi checksum memetakan string fixed-length ke angka, dengan fungsi checksum yang baik memenuhi dua sifat: pertama, tabrakan (dua senar berbeda dipetakan ke checksum yang sama) harus langka - memang, semakin tinggi tingkat tumbukan, semakin banyak kemungkinan kecocokan yang salah akan muncul.Kedua, checksum harus dihitung dengan cara yang memungkinkan pembaharuan yang efisien: yaitu nilai checksum s [i 1: i k 1 [harus segera diturunkan dari nilai s [i: i k [.

Solusi sains dan teknologi -- Fungsi hash polinomial Salah satu fungsi hash hash yang mudah diterapkann didasarkan pada polinomial.Dengan daftar \ (k \) nomor \ (a_0, \ ldots, a_ {k-1} \), kita mendefinisikan sebuah polinomial1 $$ H (a) (X) = a_0 X ^ {k-1} a_1 X ^ {k-2} \ ldots a_ {k-2} X a_ {k-1} = \ sum_ {j

Solusi sains dan teknologi -- Alasannya adalah bahwa jika memang \ (P = Q \) maka pengujian akan selalu menerima \ (P \) dan \ (Q \) sebagai sama, sementara jika \ (P \ not = Q \) maka probabilitas untuk memukul Saksi yang buruk dan salah menerima \ (P \) dan \ (Q \) sama rendahnya.Lebih tepatnya, jika \ (P \) dan \ (Q \) adalah polinomial derajat \ (≤ k \), dan \ (m \) adalah bilangan prima yang lebih besar daripada koefisien terbesar \ (P - Q \), maka probabilitas memukul akar \ (PQ \) lebih rendah dari \ (kck nilai acak \ (a \) dan bandingkan nilai \ (P (a) \) dan \ (Q (a) \), terima jika dan hanya jika \ (P (a) = Q (a) \) (karena nilai \ (P (a) \) dan \ (Q (a) \) mungkin terlalu besar agar sesuai dengan bilangan bulat berukuran standar, perhitungan umumnya membuat modulo modulus prime besar tertentu \ (m \)).Alasannya adalah bahwa jika memang \ (P = Q \) maka pengujian akan selalu menerima \ (P \) dan \ (Q \) sebagai sama, sementara jika \ (P \ not = Q \) maka probabilitas untuk memukul Saksi yang buruk dan salah menerima \ (P \) dan \ (Q \) sama rendahnya.Lebih tepatnya, jika \ (P \) dan \ (Q \) adalah polinomial derajat \ (≤ k \), dan \ (m \) adalah bilangan prima yang lebih besar daripada koefisien terbesar \ (P - Q \), maka probabilitas memukul akar \ (PQ \) lebih rendah dari \ (kck nilai acak \ (a \) dan bandingkan nilai \ (P (a) \) dan \ (Q (a) \), terima jika dan hanya jika \ (P (a) = Q (a) \) (karena nilai \ (P (a) \) dan \ (Q (a) \) mungkin terlalu besar agar sesuai dengan bilangan bulat berukuran standar, perhitungan umumnya membuat modulo modulus prime besar tertentu \ (m \)).

Solusi sains dan teknologi -- Alasannya adalah bahwa jika memang \ (P = Q \) maka pengujian akan selalu menerima \ (P \) dan \ (Q \) sebagai sama, sementara jika \ (P \ not = Q \) maka probabilitas untuk memukul Saksi yang buruk dan salah menerima \ (P \) dan \ (Q \) sama rendahnya.Lebih tepatnya, jika \ (P \) dan \ (Q \) adalah polinomial derajat \ (≤ k \), dan \ (m \) adalah bilangan prima yang lebih besar daripada koefisien terbesar \ (P - Q \), maka probabilitas memukul akar \ (PQ \) lebih rendah dari \ (kCatatan tunggal LARGEST_CODEPOINT = 0x10FFFF Karakter dipetakan ke koefisien polinomial menggunakan fungsi ord python, yang mengembalikan kode Unicode dari karakter apapun.Poin kode terbesar adalah 0x10FFFF.modulus = 0xB504F32D Koefisien polinom checksum lebih kecil dari LARGEST_CODEPOINT, dan karena modulus harus melebihi semua koefisien polinom checksum, ia harus melebihi LARGEST_CODEPOINT 4.

Solusi sains dan teknologi -- Selanjutnya diperlukan modulus sebesar mungkin membantu mengurangi kemungkinan tabrakan checksum, dan karenanya adanya kecocokan palsu .Akhirnya, menegakkan bahwa hal itu menjadi batas utama jumlah akar bilangan bulat dari polinomial derajat-k.0xB504F32D dipilih karena merupakan nilai terbesar yang memenuhi persyaratan yang sesuai dengan kuadrat bertanda 64 bit.5 substr_checksum = checksum (tumpukan jerami, biji, modulus, needle_length) Sebelum memulai perhitungan bergulir, substr_checksum diinisialisasi ke checksum \ (s [0: k [\).

Solusi sains dan teknologi -- jika needle_checksum == substr_checksum: Untuk mencegah cheTabrakan cksum menghasilkan kecocokan yang salah, seseorang dapat secara eksplisit memverifikasi kecocokan 6 dengan menentukan def verify (tumpukan jerami, pos, jarum): kembali semua (tumpukan jerami [pos k] == jarum [k] untuk k dalam kisaran (0, len (jarum))) dan mengganti tes checksum dengan if needle_checksum == substr_checksum dan verifikasi (tumpukan jerami, jarum, pos): Ini memperlambat algoritma sedikit, namun, mengambil performa terburuknya menjadi \ (O (nk) \) 7 - secara umum , bagaimanapun, kinerjanya tetap bagus selama polanya tidak berlebihan.8 Jika pos

Solusi sains dan teknologi -- Kecocokan yang salah: batas teoritis dan hasil eksperimen.Seperti yang telah dicatat sebelumnya, probabilitas dari sebuah pertandingan palsu muncul pada posisi \ (i \ in \ {0, \ ldots, n-1 \} \) lebih rendah dari \ (ks seperti yang 0xB501 lakukan, dengan biaya meningkatkan tingkat kecocokan yang salah.Kecocokan yang salah: batas teoritis dan hasil eksperimen.Seperti yang telah dicatat sebelumnya, probabilitas dari sebuah pertandingan palsu muncul pada posisi \ (i \ in \ {0, \ ldots, n-1 \} \) lebih rendah dari \ (ks seperti yang 0xB501 lakukan, dengan biaya meningkatkan tingkat kecocokan yang salah.

Solusi sains dan teknologi -- Kecocokan yang salah: batas teoritis dan hasil eksperimen.Seperti yang telah dicatat sebelumnya, probabilitas dari sebuah pertandingan palsu muncul pada posisi \ (i \ in \ {0, \ ldots, n-1 \} \) lebih rendah dari \ (ke pada teks kehidupan nyata akan sering jauh lebih rendah.Hasil eksperimen sulit didapat mengingat waktu yang dibutuhkan untuk mencari file berukuran besar, namun mencari 200 kali string acak 5000 karakter di proyek Gutenberg's pg2554 (Crime and punishment), tidak mengembalikan satu false positive, meski teoritisnya terikat yang bisa diturunkan dari rumus di atas berkenaan dengan probabilitas untuk mendapatkan setidaknya satu kecocokan yang salah dalam percobaan semacam itu di atas satu.Dalam percobaan kedua, saya mencari string TATAAA (rangkaian konsensus kotak TATA, panjang 6) pada genom platipus betina (panjang 1 684 663 807).

Solusi sains dan teknologi -- Sekali lagi, tidak ada kecocokan yang salah ditemukan.Streaming Satu properti bagus dari algoritma di atas adalah bahwa ia tidak mengharuskan seluruh string dimasukkan ke memori; Sebagai gantinya, ia hanya memerlukan penyangga yang panjangnya sama dengan pola yang sedang dicari.Hal ini membuatnya sangat cocok untuk mencari pola yang relatif kecil dengan senar besar, seperti pola gen di dalamnyae pada teks kehidupan nyata akan sering jauh lebih rendah.Hasil eksperimen sulit didapat mengingat waktu yang dibutuhkan untuk mencari file berukuran besar, namun mencari 200 kali string acak 5000 karakter di proyek Gutenberg's pg2554 (Crime and punishment), tidak mengembalikan satu false positive, meski teoritisnya terikat yang bisa diturunkan dari rumus di atas berkenaan dengan probabilitas untuk mendapatkan setidaknya satu kecocokan yang salah dalam percobaan semacam itu di atas satu.

Solusi sains dan teknologi -- Dalam percobaan kedua, saya mencari string TATAAA (rangkaian konsensus kotak TATA, panjang 6) pada genom platipus betina (panjang 1 684 663 807).Sekali lagi, tidak ada kecocokan yang salah ditemukan.Streaming Satu properti bagus dari algoritma di atas adalah bahwa ia tidak mengharuskan seluruh string dimasukkan ke memori; Sebagai gantinya, ia hanya memerlukan penyangga yang panjangnya sama dengan pola yang sedang dicari.Hal ini membuatnya sangat cocok untuk mencari pola yang relatif kecil dengan senar besar, seperti pola gen di dalamnyae pada teks kehidupan nyata akan sering jauh lebih rendah.

Solusi sains dan teknologi -- Hasil eksperimen sulit didapat mengingat waktu yang dibutuhkan untuk mencari file berukuran besar, namun mencari 200 kali string acak 5000 karakter di proyek Gutenberg's pg2554 (Crime and punishment), tidak mengembalikan satu false positive, meski teoritisnya terikat yang bisa diturunkan dari rumus di atas berkenaan dengan probabilitas untuk mendapatkan setidaknya satu kecocokan yang salah dalam percobaan semacam itu di atas satu.Dalam percobaan kedua, saya mencari string TATAAA (rangkaian konsensus kotak TATA, panjang 6) pada genom platipus betina (panjang 1 684 663 807).Sekali lagi, tidak ada kecocokan yang salah ditemukan.Streaming Satu properti bagus dari algoritma di atas adalah bahwa ia tidak mengharuskan seluruh string dimasukkan ke memori; Sebagai gantinya, ia hanya memerlukan penyangga yang panjangnya sama dengan pola yang sedang dicari.

Solusi sains dan teknologi -- Hal ini membuatnya sangat cocok untuk mencari pola yang relatif kecil dengan senar besar, seperti pola gen di dalamnya1 yang pertama di sini, dan putaran pertama update akan menyelesaikan perhitungan checksum.substr = collections.deque (awalan) Nilai yang sesuai dengan substring yang checksumnya dihitung disimpan di jendela geser yang diimplementasikan sebagai antrian dua kali lipat.Jendela ini diperlukan karena nilai pertama dan terakhir yang dikandungnya diperlukan untuk memperbarui checksum rolling.outgoing = substr.popleft () jika pos> 0 else 0 Pemeriksaan kondisional ini mencegah popleft dipanggil pada jendela yang tidak lengkap pada tahap update checksum rolling pertama.

Solusi sains dan teknologi -- Hal ini diperlukan karena pada iterasi pertama loop checksum tidak lengkap, dan jendela geser belum penuh.Kinerja Seperti berdiri, algoritma yang disajikan di atas melakukan agak buruk karena dua alasan: Kelemahan implementasi: Menggunakan iterator untuk loop di atas string input memperkenalkan overhead yang berat dengan kelemahan Algoritma Python: Mengekstrak modulus adalah operasi yang lambat.Plus, algoritma yang digunakan memproses semua karakter; CPyImplementasi default thon, sebaliknya, menggunakan algoritma deterministik berdasarkan dua algoritma pencarian string yang populer, Boyer-Moore dan Horsepool, yang melewatkan sebagian input.Meskipun melakukan acceptably, implementasi python algoritma ini karena itu tidak cocok untuk fungsi built-in string.find CPython yang sangat optimal.

Solusi sains dan teknologi -- Pelaku pertama yang ditunjukkan di atas dapat dengan mudah diperbaiki dengan berpindah ke bahasa lain yang lebih rendah12; Yang kedua, yang terkait langsung dengan algoritma yang digunakan, jauh lebih sulit untuk dikurangi.Menggunakan modulus non-prime kadang dianjurkan; Dalam hal ini, modulus yang paling sering dipilih umumnya \ (2 ^ {64} \) (atau berapa pun ukuran dari bilangan bulat mesin adalah (1), gagasan bahwa semantik pembungkus C menjamin bahwa operasi modulus akan dilakukan hampir untuk bebas oleh perangkat keras, dalam hal ini operasi modulus dapat dihilangkan sama sekali, namun perawatan harus dilakukan untuk memastikan pilihan benih yang tepat, sehingga meminimalkan kemungkinantabrakan checksum Ini menghasilkan percepatan eksperimental sekitar 4 kali di C; kode yang dihasilkan berada di urutan 5 sampai 10 kali lebih lambat dari pada rutinitas CPython yang optimal, namun deterministiknya, dan karenanya rentan terhadap serangan berbasis tabrakan.Pencarian multi-pola Dimana Rabin-Karp bersinar adalah saat mencari beberapa pola panjang yang sama.Dengan modifikasi sepele, algoritma di atas memang bisa diperluas agar sesuai dengan checksum substring saat ini terhadap daftar checksum pola yang telah dihitung sebelumnya.

Solusi sains dan teknologi -- Asalkan operasi pencarian ini cukup efisien, Rabin-Karp menjadi alternatif yang efisien untuk berulang kali menjalankan algoritma pencarian pola tunggal yang lebih efisien.Kode pseudo yang dimodifikasi disajikan di bawah ini: cocok = {} patterns_checksums = [checksum (pola) untuk pola dalam pola] substring_checksum = checksum (s [0: k [) untuk posisi dari 0 sampai n - k - 1 lakukan perbarui substring_checksum jika substring_checksum termasuk dalam pattern_checksum lalu # (→ 1)tambahkan posisi ke pertandingan kembali cocok Semua yang tersisa adalah menemukan implementasi yang tepat dari operasi (→ 1).Tabel hash, meskipun mungkin sesuai, memerlukan memori dalam jumlah besar agar tidak menimbulkan tabrakan tambahan13, dan mereka mengenalkan sedikit kinerja di atas kepala.Sebagai gantinya, memilah pola checksum dan pencarian biner array yang dihasilkan tidak memerlukan memori tambahan, dan memperkenalkan overhead yang sangat rendah untuk menghitung pola yang masuk akal.

Solusi sains dan teknologi -- Grafik berikut menunjukkan efek menggunakan algoritma yang dimodifikasi ini untuk mencari sejumlah besar pola.Empat implementasi dibandingkan: python naif, implementasi C: untuk pola dalam pola: jika haystack.find (pola)> 0: kembali benar untuk pola pola (int pattern_id = 0; pattern_id

Solusi sains dan teknologi -- MSDN dan Wikipedia memiliki rincian lebih lanjut tentang ini.[↩] Diberi bilangan prima \ (m \), \ (\ mathbb {Z}): modulus = random_prime (max (2 ** 30.5, LARGEST_CODEPOINT 1)) [↩] Jika verifikasi semacam itu diterapkan, algoritma ini persis algoritma pencarian string Rabin-Karp [↩] Kasus terburuk ini tercapai ketika tumpukan jerami dan jarum hanya terdiri dari satu karakter, misalnya ketika mencari \ (aaa \) di \ (aaa \ ldots aaa \) [↩] Selanjutnya, dapat dikatakan bahwa biaya langkah pengecekan tambahan ini tidak signifikan, karena program pencarian string seperti grep umumnya menampilkan kecocokan, mengambil Waktu linier sepanjang pola untuk setiap pertandingan.Karena verifikasi hanya terjadi pada kecocokan yang terdeteksi oleh perbandingan checksum, semua yang masih harus diperiksa adalah bahwa kecocokan palsu cukup langka sehingga tidak mempengaruhi waktu eksekusi.[↩] bilangan bulat standar Python dapat naik ke \ (2 ^ {63} - 1 \) sebelum dipromosikan menjadi bilangan bulat presisi sewenang-wenang [↩] Misalnya, mencari string 10 karakter seperti "Petersburg" pada teks biasa versi DostoyevskyKejahatan dan hukuman (~ 1,1 juta karakter).

Solusi sains dan teknologi -- [↩] Perilaku pembungkus didefinisikan dalam sub-pasal 6.2.5 paragraf 9 dari Standar C: "Perhitungan yang melibatkan operand tidak ditandatangani tidak akan pernah meluap, karena hasil yang tidak dapat diwakili oleh jenis integer unsigned yang dihasilkan dikurangi modulo jumlah yang adalah satu lebih besar dari nilai terbesar yang bisa diwakili oleh tipe yang dihasilkan ".[↩] Memang, implementasi C dari algoritma sederhana ini berjalan hanya sekitar 20 kali lebih lambat daripada rutinitas yang dioptimalkan dengan Python [↩] Implementasi streaming yang disajikan di atas hanya memerlukan token \ (k \) terakhir di memori, dan karena itu lebih Memori yang efisien [↩] Idealnya, meskipun, ekspresi reguler yang dihasilkan akan diubah menjadi robot deterministik yang kinerjanya hanya sedikit bergantung pada jumlah pola (secara kebetulan, ini adalah dasar dari algoritma Aho-Corasick).Sayangnya, Python tidak melakukannya secara default.[↩] .