Apa algoritma pencarian substring tercepat?

OK, jadi saya tidak terdengar seperti orang bodoh. Saya akan menyatakan masalah / persyaratan secara lebih eksplisit:

• Jarum (pola) dan tumpukan jerami (teks untuk dicari) keduanya adalah string C-style null-dihentikan. Tidak ada informasi panjang disediakan; jika perlu, itu harus dihitung.
• Fungsi harus mengembalikan pointer ke kecocokan pertama, atau NULLjika tidak ada kecocokan yang ditemukan.
• Kasus kegagalan tidak diperbolehkan. Ini berarti setiap algoritma dengan persyaratan penyimpanan non-konstan (atau besar konstan) akan perlu memiliki kasus mundur untuk kegagalan alokasi (dan kinerja dalam perawatan mundur dengan demikian berkontribusi terhadap kinerja kasus terburuk).
• Implementasinya harus dalam C, meskipun deskripsi yang baik dari algoritma (atau tautan ke sana) tanpa kode juga baik-baik saja.

... dan juga yang saya maksud dengan "tercepat":

• Deterministik di O(n)mana n= panjang tumpukan jerami. (Tetapi dimungkinkan untuk menggunakan ide-ide dari algoritma yang biasanya O(nm)(misalnya rolling hash) jika mereka dikombinasikan dengan algoritma yang lebih kuat untuk memberikan deterministikO(n) hasil ).
• Tidak pernah melakukan (terukur; beberapa jam untuk if (!needle[1]) dll. Lebih baik) lebih buruk daripada algoritma brute force naif, terutama pada jarum yang sangat pendek yang kemungkinan merupakan kasus yang paling umum. (Overhead preprocessing berat tanpa syarat adalah buruk, seperti sedang mencoba untuk meningkatkan koefisien linear untuk jarum patologis dengan mengorbankan kemungkinan jarum.)
• Diberikan jarum dan tumpukan jerami yang sewenang-wenang, kinerja yang sebanding atau lebih baik (tidak lebih buruk dari 50% waktu pencarian lebih lama) dibandingkan dengan algoritma lain yang banyak diimplementasikan.
• Selain dari kondisi ini, saya meninggalkan definisi "tercepat" terbuka. Jawaban yang bagus harus menjelaskan mengapa Anda menganggap pendekatan yang Anda sarankan "tercepat".

Implementasi saya saat ini berjalan kira-kira antara 10% lebih lambat dan 8 kali lebih cepat (tergantung pada input) daripada implementasi Two-Way glibc.

Pembaruan: Algoritma optimal saya saat ini adalah sebagai berikut:

• Untuk jarum dengan panjang 1, gunakan strchr .
• Untuk jarum dengan panjang 2-4, gunakan kata-kata mesin untuk membandingkan 2-4 byte sekaligus sebagai berikut: Preload jarum dalam bilangan bulat 16 atau 32-bit dengan bithifts dan daur keluar byte lama / byte baru dari tumpukan jerami di setiap iterasi . Setiap byte tumpukan jerami dibaca tepat sekali dan menimbulkan cek terhadap 0 (akhir string) dan satu perbandingan 16 atau 32-bit.
• Untuk jarum dengan panjang> 4, gunakan algoritma Two-Way dengan tabel shift yang buruk (seperti Boyer-Moore) yang hanya diterapkan pada byte terakhir dari jendela. Untuk menghindari overhead menginisialisasi tabel 1kb, yang akan menjadi kerugian bersih untuk banyak jarum dengan panjang sedang, saya menyimpan array bit (32 byte) yang menandai entri mana dalam tabel shift yang diinisialisasi. Bit yang tidak disetel berhubungan dengan nilai byte yang tidak pernah muncul di jarum, yang memungkinkan pergeseran panjang jarum penuh.

Pertanyaan besar yang tersisa di pikiran saya adalah:

• Apakah ada cara untuk memanfaatkan tabel shift yang buruk dengan lebih baik? Boyer-Moore memanfaatkannya dengan memindai ke belakang (kanan-ke-kiri), tetapi Two-Way membutuhkan pemindaian kiri-ke-kanan.
• Hanya dua algoritma kandidat yang layak yang saya temukan untuk kasus umum (tidak ada kehabisan memori atau kondisi kinerja kuadratik) adalah Two-Way dan String Matching pada Alphabets yang Dipesan . Tetapi apakah ada kasus yang mudah terdeteksi di mana algoritma yang berbeda akan optimal? Tentu saja banyak O(m)(di mana mpanjang jarum) dalam algoritma ruang dapat digunakan untuk m<100atau lebih. Mungkin juga untuk menggunakan algoritma yang kuadratik terburuk jika ada tes mudah untuk jarum yang terbukti hanya membutuhkan waktu linier.

Poin bonus untuk:

• Dapatkah Anda meningkatkan kinerja dengan mengasumsikan bahwa jarum dan tumpukan jerami adalah UTF-8 yang baik? (Dengan karakter dengan panjang byte yang berbeda-beda, well-formed-ness memaksakan beberapa persyaratan penyelarasan string antara jarum dan tumpukan jerami dan memungkinkan perpindahan 2-4 byte secara otomatis ketika byte head yang tidak cocok ditemukan. Tetapi apakah kendala ini membuat Anda banyak / apa pun di luar apa yang perhitungan sufiks maksimal, pergeseran sufiks yang baik, dll. sudah memberi Anda berbagai algoritma?)

Catatan: Saya menyadari sebagian besar algoritma di luar sana, hanya saja tidak sebagus apa yang mereka lakukan dalam praktik. Berikut ini adalah referensi yang baik sehingga orang tidak terus memberi saya referensi tentang algoritma sebagai komentar / jawaban: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

Membangun perpustakaan uji kemungkinan jarum dan tumpukan jerami. Profil tes pada beberapa algoritma pencarian, termasuk brute force. Pilih yang berkinerja terbaik dengan data Anda.

Boyer-Moore menggunakan tabel karakter yang buruk dengan tabel akhiran yang bagus.

Boyer-Moore-Horspool menggunakan tabel karakter buruk.

Knuth-Morris-Pratt menggunakan tabel pertandingan parsial.

Rabin-Karp menggunakan hash yang sedang berjalan.

Mereka semua memperdagangkan overhead untuk perbandingan yang dikurangi ke tingkat yang berbeda, sehingga kinerja dunia nyata akan tergantung pada panjang rata-rata jarum dan tumpukan jerami. Semakin banyak overhead awal, semakin baik dengan input yang lebih lama. Dengan jarum yang sangat pendek, brute force bisa menang.

Edit:

Algoritme yang berbeda mungkin yang terbaik untuk menemukan pasangan basa, frasa bahasa Inggris, atau kata tunggal. Jika ada satu algoritma terbaik untuk semua input, itu akan dipublikasikan.

Pikirkan tentang tabel kecil berikut ini. Setiap tanda tanya mungkin memiliki algoritma pencarian terbaik yang berbeda.

                 short needle     long needle
short haystack         ?               ?
long haystack          ?               ?

Ini harus benar-benar berupa grafik, dengan kisaran input yang lebih pendek hingga lebih panjang pada setiap sumbu. Jika Anda merencanakan setiap algoritma pada grafik seperti itu, masing-masing akan memiliki tanda tangan yang berbeda. Beberapa algoritma menderita dengan banyak pengulangan dalam pola, yang mungkin memengaruhi penggunaan seperti mencari gen. Beberapa faktor lain yang memengaruhi kinerja secara keseluruhan adalah mencari pola yang sama lebih dari satu kali dan mencari pola yang berbeda secara bersamaan.

Jika saya memerlukan set sampel, saya pikir saya akan mengikis situs seperti google atau wikipedia, kemudian menghapus html dari semua halaman hasil. Untuk situs pencarian, ketikkan sebuah kata lalu gunakan salah satu frasa pencarian yang disarankan. Pilih beberapa bahasa yang berbeda, jika berlaku. Dengan menggunakan halaman web, semua teks akan pendek ke sedang, jadi gabungkan halaman yang cukup untuk mendapatkan teks yang lebih panjang. Anda juga dapat menemukan buku domain publik, catatan hukum, dan badan teks besar lainnya. Atau hanya menghasilkan konten acak dengan memilih kata-kata dari kamus. Tetapi tujuan dari profiling adalah untuk menguji terhadap jenis konten yang akan Anda cari, jadi gunakan sampel dunia nyata jika memungkinkan.

Saya meninggalkan pendek dan panjang kabur. Untuk jarum, saya pikir pendek di bawah 8 karakter, sedang di bawah 64 karakter, dan di bawah 1k. Untuk tumpukan jerami, saya menganggap pendek di bawah 2 ^ 10, sedang sebagai di bawah 2 ^ 20, dan selama hingga 2 ^ 30 karakter.

Diterbitkan pada tahun 2011, saya percaya itu mungkin sangat baik "Simple-Time Constant-Space String Matching" algoritma oleh Dany Breslauer, Roberto Grossi, dan Filippo Mignosi.

Memperbarui:

Pada tahun 2014 penulis menerbitkan peningkatan ini: Menuju pencocokan string yang optimal .

The http://www-igm.univ-mlv.fr/~lecroq/string/index.html menghubungkan Anda menunjuk ke adalah sumber dan ringkasan dari beberapa algoritma string matching paling dikenal dan diteliti.

Solusi untuk sebagian besar masalah pencarian melibatkan pertukaran sehubungan dengan pra-pemrosesan persyaratan overhead, waktu dan ruang. Tidak ada algoritma tunggal yang akan optimal atau praktis dalam semua kasus.

Jika tujuan Anda adalah merancang algoritme khusus untuk pencarian string, abaikan apa yang saya katakan, Jika Anda ingin mengembangkan layanan pencarian string umum maka coba yang berikut ini:

Luangkan waktu untuk meninjau kekuatan dan kelemahan spesifik dari algoritma yang telah Anda rujuk. Melakukan peninjauan dengan tujuan menemukan serangkaian algoritma yang mencakup rentang dan ruang lingkup pencarian string yang Anda minati. Kemudian, buat pemilih pencarian ujung depan berdasarkan fungsi classifier untuk menargetkan algoritma terbaik untuk input yang diberikan. Dengan cara ini Anda dapat menggunakan algoritma yang paling efisien untuk melakukan pekerjaan itu. Ini sangat efektif ketika suatu algoritma sangat baik untuk pencarian tertentu tetapi menurun dengan buruk. Sebagai contoh, brute force mungkin yang terbaik untuk jarum dengan panjang 1 tetapi dengan cepat menurun seiring bertambahnya panjang jarum, algoritma sustik-mooremungkin menjadi lebih efisien (lebih dari huruf kecil), maka untuk jarum yang lebih panjang dan huruf yang lebih besar, algoritma KMP atau Boyer-Moore mungkin lebih baik. Ini hanya contoh untuk menggambarkan strategi yang mungkin.

Pendekatan beberapa algoritma bukan ide baru. Saya percaya ini telah digunakan oleh beberapa paket Sort / Search komersial (mis. SYNCSORT yang biasa digunakan pada mainframe mengimplementasikan beberapa algoritma sort dan menggunakan heuristik untuk memilih yang "terbaik" untuk input yang diberikan)

Setiap algoritma pencarian hadir dalam beberapa variasi yang dapat membuat perbedaan yang signifikan pada kinerjanya, seperti, makalah ini menggambarkan.

Benchmark layanan Anda untuk mengkategorikan area di mana strategi pencarian tambahan diperlukan atau untuk lebih menyempurnakan fungsi pemilih Anda. Pendekatan ini tidak cepat atau mudah tetapi jika dilakukan dengan baik dapat menghasilkan hasil yang sangat baik.

Saya terkejut melihat laporan teknologi kami dikutip dalam diskusi ini; Saya adalah salah satu penulis algoritma yang diberi nama Sustik-Moore di atas. (Kami tidak menggunakan istilah itu di koran kami.)

Saya ingin menekankan di sini bahwa bagi saya fitur paling menarik dari algoritma ini adalah cukup sederhana untuk membuktikan bahwa setiap huruf diperiksa paling banyak satu kali. Untuk versi Boyer-Moore sebelumnya mereka membuktikan bahwa setiap huruf diperiksa paling banyak 3 dan kemudian paling banyak 2 kali, dan bukti-bukti itu lebih banyak terlibat (lihat kutipan di kertas). Karena itu saya juga melihat nilai didaktis dalam menghadirkan / mempelajari varian ini.

Dalam makalah ini kami juga menjelaskan variasi lebih lanjut yang diarahkan pada efisiensi sambil mengendurkan jaminan teoretis. Ini adalah makalah pendek dan bahannya harus dapat dimengerti oleh lulusan sekolah menengah pada pendapat saya.

Tujuan utama kami adalah membawa versi ini menjadi perhatian orang lain yang dapat lebih meningkatkannya. Pencarian string memiliki banyak variasi dan kami sendiri tidak mungkin memikirkan semua di mana ide ini dapat membawa manfaat. (Memperbaiki teks dan mengubah pola, memperbaiki pola berbeda teks, preprocessing mungkin / tidak mungkin, eksekusi paralel, menemukan himpunan bagian yang cocok dalam teks besar, memungkinkan kesalahan, hampir cocok dll, dll.)

Algoritma pencarian substring tercepat akan tergantung pada konteks:

1. ukuran alfabet (mis. DNA vs Bahasa Inggris)
2. panjang jarum

Makalah 2010 "Masalah Pencocokan String Tepat: Evaluasi Eksperimental Komprehensif" memberikan tabel dengan runtime untuk 51 algoritma (dengan ukuran alfabet dan panjang jarum yang berbeda), sehingga Anda dapat memilih algoritma terbaik untuk konteks Anda.

Semua algoritma tersebut memiliki implementasi C, serta test suite, di sini:

http://www.dmi.unict.it/~faro/smart/algorithms.php

Pertanyaan yang sangat bagus. Cukup tambahkan beberapa bit kecil ...

1. Seseorang berbicara tentang pencocokan urutan DNA. Tetapi untuk urutan DNA, apa yang biasanya kita lakukan adalah membangun struktur data (misalnya susunan sufiks, sufiks pohon atau indeks-FM) untuk tumpukan jerami dan mencocokkan banyak jarum dengan itu. Ini pertanyaan yang berbeda.

2. Akan sangat bagus jika seseorang ingin membandingkan berbagai algoritma. Ada tolok ukur yang sangat baik pada kompresi dan pembangunan susunan sufiks, tetapi saya belum melihat patokan pada pencocokan string. Calon calon tumpukan jerami bisa dari patokan SACA .

3. Beberapa hari yang lalu saya menguji implementasi Boyer-Moore dari halaman yang Anda rekomendasikan (EDIT: Saya perlu pemanggilan fungsi seperti memmem (), tetapi itu bukan fungsi standar, jadi saya memutuskan untuk mengimplementasikannya). Program pembandingan saya menggunakan tumpukan jerami acak. Tampaknya implementasi Boyer-Moore di halaman tersebut lebih cepat daripada memmem () dan strnstr () dari glibc di Mac. Jika Anda tertarik, implementasinya ada di sini dan kode tolok ukurnya ada di sini . Ini jelas bukan tolok ukur yang realistis, tetapi ini adalah awal.

Saya tahu ini adalah pertanyaan lama, tetapi sebagian besar tabel shift yang buruk adalah karakter tunggal. Jika masuk akal untuk dataset Anda (misalnya, terutama jika itu adalah kata-kata tertulis), dan jika Anda memiliki ruang yang tersedia, Anda bisa mendapatkan percepatan dramatis dengan menggunakan tabel shift buruk yang terbuat dari n-gram daripada karakter tunggal.

Gunakan stdlib strstr:

char *foundit = strstr(haystack, needle);

Itu sangat cepat, hanya butuh sekitar 5 detik untuk mengetik.

Inilah implementasi pencarian Python , yang digunakan dari seluruh inti. Komentar menunjukkan menggunakan tabel boyer-moore delta 1 terkompresi .

Saya telah melakukan beberapa percobaan yang cukup luas dengan mencari string sendiri, tetapi itu untuk beberapa string pencarian. Implementasi perakitan Horspool dan Bitap sering dapat menahan mereka sendiri terhadap algoritma seperti Aho-Corasick untuk jumlah pola rendah.

strchrAlgoritme "Pencarian untuk karakter pencocokan tunggal" (ala ) yang lebih cepat.

Catatan penting:

• Fungsi-fungsi ini menggunakan gcckompiler intrinsik- "nomor / jumlah (terkemuka | trailing) nol __builtin_ctz. Fungsi-fungsi ini cenderung hanya cepat pada mesin yang memiliki instruksi yang melakukan operasi ini (yaitu, x86, ppc, arm).

• Fungsi-fungsi ini menganggap arsitektur target dapat melakukan 32 dan 64 bit unaligned load. Jika arsitektur target Anda tidak mendukung ini, Anda perlu menambahkan beberapa logika start up untuk menyelaraskan bacaan dengan benar.

• Fungsi-fungsi ini netral dari prosesor. Jika CPU target memiliki instruksi vektor, Anda mungkin dapat melakukan (jauh) lebih baik. Sebagai contoh, strlenFungsi di bawah ini menggunakan SSE3 dan dapat secara sepele dimodifikasi menjadi XOR byte yang dipindai untuk mencari byte selain 0. Benchmark dilakukan pada laptop 2.66GHz Core 2 yang menjalankan Mac OS X 10.6 (x86_64):

  • 843.433 MB / s untuk strchr
  • 2656.742 MB / s untuk findFirstByte64
  • 13094.479 MB / s untuk strlen

... versi 32-bit:

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (_x == 0u)   ? 0 : (__builtin_clz(_x) >> 3) + 1; })
#else
#define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu);                    (__builtin_ctz(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte32(unsigned char *ptr, unsigned char byte) {
  uint32_t *ptr32 = (uint32_t *)ptr, firstByte32 = 0u, byteMask32 = (byte) | (byte << 8);
  byteMask32 |= byteMask32 << 16;
  while((firstByte32 = findFirstZeroByte32((*ptr32) ^ byteMask32)) == 0) { ptr32++; }
  return(ptr + ((((unsigned char *)ptr32) - ptr) + firstByte32 - 1));
}

... dan versi 64-bit:

#ifdef __BIG_ENDIAN__
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (_x == 0ull) ? 0 : (__builtin_clzll(_x) >> 3) + 1; })
#else
#define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full);                    (__builtin_ctzll(_x) + 1) >> 3; })
#endif

unsigned char *findFirstByte64(unsigned char *ptr, unsigned char byte) {
  uint64_t *ptr64 = (uint64_t *)ptr, firstByte64 = 0u, byteMask64 = (byte) | (byte << 8);
  byteMask64 |= byteMask64 << 16;
  byteMask64 |= byteMask64 << 32;
  while((firstByte64 = findFirstZeroByte64((*ptr64) ^ byteMask64)) == 0) { ptr64++; }
  return(ptr + ((((unsigned char *)ptr64) - ptr) + firstByte64 - 1));
}

Sunting 2011/06/04 OP menunjukkan dalam komentar bahwa solusi ini memiliki "bug yang tidak dapat diatasi":

dapat membaca melewati terminator byte atau null yang dicari, yang dapat mengakses halaman atau halaman yang tidak dipetakan tanpa izin baca. Anda tidak bisa menggunakan bacaan besar dalam fungsi string kecuali jika mereka selaras.

Secara teknis ini benar, tetapi berlaku untuk hampir semua algoritma yang beroperasi pada bongkahan yang lebih besar dari satu byte, termasuk metode yang disarankan oleh OP dalam komentar:

strchrImplementasi tipikal tidak naif, tetapi sedikit lebih efisien daripada apa yang Anda berikan. Lihat akhir dari ini untuk algoritma yang paling banyak digunakan: http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

Ini juga tidak ada hubungannya dengan perataan . Benar, ini berpotensi menyebabkan perilaku yang didiskusikan pada mayoritas arsitektur umum yang digunakan, tetapi ini lebih berkaitan dengan detail implementasi arsitektur mikro- jika pembacaan yang tidak selaras mengangkangi batas 4K (sekali lagi, tipikal), maka pembacaan itu akan menyebabkan program menghentikan kesalahan jika batas halaman 4K berikutnya tidak dipetakan.

Tapi ini bukan "bug" dalam algoritma yang diberikan dalam jawaban- perilaku itu karena fungsi suka strchrdan strlentidak menerima lengthargumen untuk mengikat ukuran pencarian. Pencarian char bytes[1] = {0x55};, yang untuk keperluan diskusi kita kebetulan ditempatkan di akhir batas halaman 4K VM dan halaman berikutnya tidak dipetakan, dengan strchr(bytes, 0xAA)(di mana strchrimplementasi byte-at-a-waktu) akan crash persis cara yang sama. Ditto untuk strchrsepupu terkait strlen.

Tanpa lengthargumen, tidak ada cara untuk mengetahui kapan Anda harus beralih dari algoritma kecepatan tinggi dan kembali ke algoritma byte-by-byte. "Bug" yang jauh lebih mungkin adalah membaca "melewati ukuran alokasi", yang secara teknis menghasilkanundefined behavior menurut berbagai standar bahasa C, dan akan ditandai sebagai kesalahan oleh sesuatu seperti valgrind.

Singkatnya, apa pun yang beroperasi pada potongan yang lebih besar dari byte akan berjalan lebih cepat, seperti yang dilakukan kode jawaban ini dan kode yang ditunjukkan oleh OP, tetapi harus memiliki byte semantik yang akurat yang cenderung "buggy" jika tidak ada lengthargumen untuk mengontrol kasus sudut "the last read".

Kode dalam jawaban ini adalah kernel untuk dapat menemukan byte pertama dalam ukuran kata CPU alami dengan cepat jika CPU target memiliki ctzinstruksi seperti cepat . Sangat mudah untuk menambahkan hal-hal seperti memastikan itu hanya beroperasi pada batas alami yang disejajarkan dengan benar, atau beberapa bentuklength terikat, yang akan memungkinkan Anda untuk beralih dari kernel kecepatan tinggi dan ke cek byte-by-byte yang lebih lambat.

OP juga menyatakan dalam komentar:

Adapun optimasi ctz Anda, itu hanya membuat perbedaan untuk operasi ekor O (1). Itu dapat meningkatkan kinerja dengan string kecil (misalnya strchr("abc", 'a');tetapi tentu saja tidak dengan string ukuran besar apa pun).

Apakah pernyataan ini benar atau tidak tergantung banyak pada mikroarsitektur yang dimaksud. Menggunakan model pipa RISC kanonik 4 tahap, maka hampir pasti benar. Tetapi sangat sulit untuk mengetahui apakah itu benar untuk CPU skalar super out-of-order kontemporer di mana kecepatan inti benar-benar dapat mengerdilkan kecepatan streaming memori. Dalam hal ini, itu tidak hanya masuk akal, tetapi sangat umum, karena ada kesenjangan besar dalam "jumlah instruksi yang dapat dihentikan" relatif terhadap "jumlah byte yang dapat dialirkan" sehingga Anda memiliki " jumlah instruksi yang dapat dihentikan untuk setiap byte yang dapat dialirkan ". Jika ini cukup besar, ctzinstruksi + shift dapat dilakukan "gratis".

Cukup cari "strstr tercepat", dan jika Anda melihat sesuatu yang menarik, tanyakan saja kepada saya.

Dalam pandangan saya, Anda memaksakan terlalu banyak batasan pada diri Anda (ya kita semua ingin linear sub-linear di max pencari), namun dibutuhkan programmer nyata untuk melangkah, sampai saat itu saya berpikir bahwa pendekatan hash hanyalah solusi bagus-limbo ( diperkuat dengan baik oleh BNDM untuk pola 2..16 yang lebih pendek).

Contoh singkat:

Melakukan Pencarian untuk Pola (32bytes) ke String (206908949bytes) sebagai satu-line ... Lewati-Performance (besar-the-baik): 3041%, 6.801.754 melompat / iterasi Railgun_Quadruplet_7Hasherezade_hits / Railgun_Quadruplet_7Hasherezade_clocks: 0/58 Railgun_Quadruplet_7Hasherezade kinerja: 3483KB / jam

Melakukan Pencarian untuk Pola (32bytes) ke String (206908949bytes) sebagai satu-line ... Lewati-Performance (besar-the-baik): 1554%, 13.307.181 melompat / iterasi Boyer_Moore_Flensburg_hits / Boyer_Moore_Flensburg_clocks: 0/83 Boyer_Moore_Flensburg kinerja: 2434KB / jam

Melakukan Pencarian Pola (32bytes) ke dalam String (206908949bytes) sebagai satu-baris ... Lewati-Kinerja (lebih besar-lebih baik): 129%, 160239051 lompatan / iterasi Two-Way_hits / Two-Way_clocks: 0/816 Two Kinerja -Way : 247KB / jam

Sanmayce,
Salam

Algoritma Dua Arah yang Anda sebutkan dalam pertanyaan Anda (yang omong-omong luar biasa!) Baru-baru ini ditingkatkan untuk bekerja secara efisien pada kata-kata multibyte sekaligus: Pencocokan String yang Dikemas Secara Optimal .

Saya belum membaca keseluruhan makalah, tetapi tampaknya mereka bergantung pada beberapa instruksi CPU khusus yang baru (termasuk dalam contoh SSE 4.2) menjadi O (1) untuk klaim kompleksitas waktu mereka, meskipun jika tidak tersedia mereka dapat mensimulasikan mereka dalam waktu O (log w) untuk kata-kata w-bit yang tidak terdengar terlalu buruk.

Anda dapat menerapkan, katakanlah, 4 algoritma berbeda. Setiap M menit (ditentukan secara empiris) jalankan semua 4 pada data aktual saat ini. Akumulasi statistik lebih dari N berjalan (juga TBD). Kemudian gunakan hanya pemenang untuk M menit berikutnya.

Log statistik pada Kemenangan sehingga Anda dapat mengganti algoritma yang tidak pernah menang dengan yang baru. Pusatkan upaya pengoptimalan pada rutinitas terbaik. Berikan perhatian khusus pada statistik setelah setiap perubahan pada perangkat keras, database, atau sumber data. Sertakan info itu di log statistik jika memungkinkan, jadi Anda tidak perlu mencari tahu dari tanggal log / cap waktu.

Baru-baru ini saya menemukan alat yang bagus untuk mengukur kinerja berbagai algo yang tersedia: http://www.dmi.unict.it/~faro/smart/index.php

Anda mungkin menemukan itu berguna. Juga, jika saya harus melakukan panggilan cepat pada algoritma pencarian substring, saya akan pergi dengan Knuth-Morris-Pratt.

Anda mungkin juga ingin memiliki tolok ukur yang beragam dengan beberapa jenis string, karena ini mungkin berdampak besar pada kinerja. Algo akan melakukan differenlty berdasarkan pencarian bahasa alami (dan bahkan di sini mungkin masih ada perbedaan berbutir karena perbedaan morfologi), string DNA atau string acak dll.

Ukuran alfabet akan berperan dalam banyak algos, seperti halnya ukuran jarum. Misalnya Horspool bagus dalam teks bahasa Inggris tetapi buruk pada DNA karena ukuran alfabet yang berbeda, membuat hidup sulit untuk aturan karakter buruk. Memperkenalkan akhiran yang baik membuat saya sangat tersisih.

Saya tidak tahu apakah itu yang terbaik, tetapi saya memiliki pengalaman yang baik dengan Boyer-Moore .

Ini tidak langsung menjawab pertanyaan, tetapi jika teksnya sangat besar, bagaimana kalau membaginya menjadi bagian yang tumpang tindih (tumpang tindih dengan panjang pola), kemudian secara bersamaan mencari bagian menggunakan utas. Berkenaan dengan algoritma tercepat, Boyer-Moore-Horspool saya pikir adalah salah satu yang tercepat jika bukan yang tercepat di antara varian Boyer-Moore. Saya memposting beberapa varian Boyer-Moore (saya tidak tahu nama mereka) dalam topik ini Algoritma lebih cepat daripada Pencarian BMH (Boyer – Moore-Horspool) .

Yang tercepat saat ini adalah EPSM, oleh S. Faro dan OM Kulekci. Lihat http://www.dmi.unict.it/~faro/smart/algorithms.php?algorithm=EPSM&code=epsm

"Exact Packed String Matching" dioptimalkan untuk SIMD SSE4.2 (x86_64 dan aarch64). Performanya stabil dan terbaik di semua ukuran.

Situs yang saya tautkan membandingkan 199 algoritma pencarian string cepat, dengan yang biasa (BM, KMP, BMH) menjadi sangat lambat. EPSM mengungguli semua yang disebutkan di sini pada platform ini. Ini juga yang terbaru.