Bagaimana cara kerja ekspresi reguler?

Katakanlah Anda memiliki dokumen dengan esai yang ditulis. Anda ingin mengurai esai ini hanya memilih kata-kata tertentu. Keren.

Apakah menggunakan ekspresi reguler lebih cepat daripada mem-parsing baris demi baris file dan kata demi kata mencari kecocokan? kalau begitu, bagamana itu bekerja? Bagaimana Anda bisa lebih cepat daripada melihat setiap kata?

Bagaimana cara kerjanya?

Lihatlah teori automata

Singkatnya, setiap ekspresi reguler memiliki otomat terbatas yang setara dan dapat dikompilasi dan dioptimalkan untuk otomat terbatas. Algoritma yang terlibat dapat ditemukan di banyak buku kompiler. Algoritma ini digunakan oleh program unix seperti awk dan grep.

Namun, sebagian besar bahasa pemrograman modern (Perl, Python, Ruby, Java (dan bahasa berbasis JVM), C #) tidak menggunakan pendekatan ini. Mereka menggunakan pendekatan backtracking rekursif, yang mengkompilasi ekspresi reguler menjadi pohon atau urutan konstruksi yang mewakili berbagai sub-bongkahan dari ekspresi reguler. Kebanyakan sintaks "ekspresi reguler" modern menawarkan referensi-ulang yang berada di luar kelompok bahasa reguler (mereka tidak memiliki representasi dalam automata terbatas), yang secara sepele dapat diterapkan dalam pendekatan backtracking rekursif.

Optimalisasi biasanya menghasilkan mesin keadaan yang lebih efisien. Sebagai contoh: pertimbangkan aaaab | aaaac | aaaad, seorang programmer normal bisa mendapatkan implementasi pencarian yang sederhana tetapi kurang efisien (membandingkan tiga string secara terpisah) tepat dalam sepuluh menit; tetapi menyadari itu setara dengan aaaa [bcd], pencarian yang lebih baik dapat dilakukan dengan mencari empat 'a' lalu menguji karakter ke-5 terhadap [b, c, d]. Proses optimasi adalah salah satu pekerjaan rumahan kompiler saya bertahun-tahun yang lalu, jadi saya berasumsi itu juga di kebanyakan mesin ekspresi reguler modern.

Di sisi lain, mesin negara memang memiliki beberapa keuntungan ketika mereka menerima string karena mereka menggunakan lebih banyak ruang dibandingkan dengan "implementasi sepele". Pertimbangkan program untuk melepaskan kutip dari string SQL, yaitu: 1) dimulai dan diakhiri dengan tanda kutip tunggal; 2) tanda kutip tunggal diloloskan oleh dua kutip tunggal berturut-turut. Jadi: input ['a' ''] harus menghasilkan output [a ']. Dengan mesin negara, tanda kutip tunggal berturut-turut ditangani oleh dua negara. Kedua status ini melayani tujuan mengingat histori input sehingga setiap karakter input diproses tepat hanya sekali, seperti yang diilustrasikan berikut:

...
S1->'->S2
S1->*->S1, output *, * can be any other character 
S2->'->S1, output '
S2->*->END, end the current string

Jadi, menurut pendapat saya, ekspresi reguler mungkin lebih lambat dalam beberapa kasus sepele, tetapi biasanya lebih cepat daripada algoritma pencarian yang dibuat secara manual, mengingat fakta bahwa pengoptimalan tidak dapat dilakukan secara andal oleh manusia.

(Bahkan dalam kasus sepele seperti mencari string, mesin pintar dapat mengenali jalur tunggal di peta keadaan dan mengurangi bagian itu menjadi perbandingan string sederhana dan menghindari mengelola negara.)

Mesin tertentu dari kerangka / pustaka mungkin lambat karena mesin melakukan banyak hal lain yang biasanya tidak dibutuhkan oleh programmer. Contoh: kelas Regex di .NET membuat banyak objek termasuk Pertandingan, Grup dan Capture.

Ekspresi reguler hanya terlihat cepat karena Anda memiliki komputer yang cepat.

Kembali pada 1980-an ketika 1 MIPS adalah komputer yang cepat, ekspresi reguler adalah area yang cukup besar dari kekhawatiran, kekhawatiran, dan penelitian karena mereka lambat dan jelek serta komputasi intensif. Pengembangan algoritma pintar diikuti dan membantu - tetapi untuk semua tujuan praktis hari ini Anda melihat keajaiban mesin cepat melapisi celah-celah.

Menurut Anda mengapa mereka lebih cepat daripada mencari dokumen?

Ada beberapa trik yang bisa Anda lakukan, misalnya. Jika Anda mencari kata 10letter yang diawali dengan A dan diakhiri dengan B maka jika Anda menemukan posisi A dan karakter 9 lebih jauh bukanlah B maka Anda dapat melewati beberapa. lihat algoritma Knuth – Morris – Pratt

Apa yang membuat ekspresi reguler cepat?

Sebenarnya tidak. Tak sebanyak itu. Hanya saja mereka tidak cukup lambat untuk kita ketahui. Kembali di masa lalu yang lambat, itu jauh lebih terlihat.

Mereka juga bukan alat yang tepat untuk setiap pekerjaan - palu .

RegEx secara komparatif lebih cepat daripada kode yang mungkin Anda tulis karena sebagian besar pustaka adalah hasil dari banyak pengembang menghabiskan bertahun-tahun mengoptimalkannya untuk mencicit setiap bit terakhir dari kinerja yang mungkin. Sulit bagi satu orang untuk menggandakannya dalam kode pencarian mereka sendiri.

Premis dasar Anda salah.

Ekspresi reguler tidak selalu lebih cepat daripada pencarian sederhana. Itu semua tergantung konteks. Itu tergantung pada kompleksitas ekspresi, panjang dokumen yang dicari, dan sejumlah faktor.

Yang terjadi adalah bahwa ekspresi reguler akan dikompilasi menjadi pengurai sederhana (yang membutuhkan waktu). Jadi, jika dokumennya kecil, waktu tambahan ini akan lebih besar daripada keuntungannya. Juga, jika ekspresinya sederhana, maka ekspresi reguler tidak akan memberi Anda keuntungan apa pun.

Jika ekspresinya kompleks dan dokumennya cukup besar, maka Anda dapat memperoleh manfaat. Apakah ini cukup signifikan untuk mempertimbangkan ekspresi reguler menjadi lebih cepat akan sangat tergantung pada seberapa banyak upaya yang ingin Anda lakukan dalam pencarian (juga ekspresi reguler mungkin memiliki beberapa optimasi yang dapat disediakan oleh perpustakaan yang Anda tidak akan memikirkan diri sendiri).

Yang ingin saya katakan adalah bahwa tidak ada jawaban menyeluruh yang menyeluruh. Jika Anda memiliki ekspresi tertentu (dan ukuran dokumen yang diketahui), maka Anda bisa mengatakan memperoleh jawaban ya / tidak untuk apakah ekspresi itu lebih cepat daripada pencarian sederhana (dan mengapa).

Keuntungan nyata dari ekspresi reguler adalah setelah Anda memahami cara menulisnya, kemampuan untuk mengekspresikan pencarian yang kompleks dengan cara yang ringkas. Karena ini adalah formulir yang digeneralisasi, Anda kemudian dapat membangun alat yang memungkinkan pencarian dengan cara yang berguna dalam kasus umum; biasanya paling tidak secepat pencarian sederhana (pada dokumen dengan ukuran minimum; pada dokumen yang lebih kecil dari ini tidak masalah karena meskipun lebih lambat, masih cukup cepat).

Masuk akal bahwa dalam beberapa bahasa tingkat tinggi (mungkin javascript), menggunakan pustaka regex yang diimplementasikan dalam bahasa tingkat rendah (mungkin C) akan lebih cepat daripada menulis logika parser dalam bahasa tingkat tinggi.

Masuk akal - Saya tidak tahu apakah ini benar-benar terjadi.