Performa ekspresi reguler yang buruk?

Diposting oleh Eyal Schneider pada 21 Mei 2009 Paket java.util.regex telah ditambahkan ke Java pada versi 1.4. Ini adalah alat yang sangat ampuh dan seseorang harus menjadi ahli untuk menggunakannya dengan benar. Meskipun ekspresi regulernya benar, ia bisa menjadi sangat lambat jika tidak ditulis dengan cerdas. Lanjutkan membaca jika Anda ingin memahami penyebab masalahnya, atau gulir ke akhir halaman di mana Anda akan menemukan 10 tips berguna untuk meningkatkan kinerja ekspresi reguler di Java.

Apakah ini sangat lambat?

Katakanlah kita ingin memilih hanya baris yang berisi urutan karakter "a" dan "b". Solusi yang tepat mungkin: (a*b*)* Namun, jika Anda menjalankan ekspresi dengan, misalnya, string “aaaaaaaaaaaaaaaaaaaaaaaaaaaaax” , akan memakan waktu beberapa menit sebelum ekspresi selesai dan melaporkan tidak ada kecocokan! Tentu saja, regex terbaik dalam hal ini adalah: (a|b)* Ini membutuhkan waktu kurang dari satu milidetik di mesin saya dengan string yang sama. Jelas ada masalah kinerja di sini.

Mengapa ini terjadi?

Seperti kebanyakan mesin regexp, Java menggunakan pendekatan NFA (Non-Deterministic Finite Automata). Mesin memindai komponen regex satu per satu dan melanjutkan melalui string input yang sesuai. Dan dia bisa kembali ke awal untuk mencari alternatif yang tepat jika dia menemui “jalan buntu”. Hasil alternatif diperoleh dengan menggunakan struktur reguler seperti bilangan ( *, +, ? ) dan pergantian (misalnya a|b|c|d ). Teknik penelitian ini disebut backtracking. Dalam contoh buruk di atas, mesin akan benar-benar memeriksa SEMUA dekomposisi seri dari simbol "a" menjadi seri yang lebih kecil hingga menyadari bahwa tidak ada kecocokan. Contoh ini menunjukkan bagaimana algoritma backtracking dapat menghasilkan perkiraan waktu eksponensial (tergantung pada panjang string input). Hal ini juga menunjukkan sifat penting NFA: akan selalu ada kasus terburuk yang hampir sesuai dengan polanya. Jika ditemukan kecocokan, pencarian dihentikan. Pendekatan utama lainnya untuk digunakan dalam regex adalah DFA (Deterministic Finite Automaton). Dalam pendekatan ini, ekspresi reguler sebenarnya membangun sebuah robot yang digunakan untuk menelusuri string input karakter demi karakter tanpa melakukan backtracking. Hal ini memberikan waktu linier untuk seluruh masukan, terlepas dari kompleksitas ekspresi reguler. Alih-alih memindai string secara berurutan untuk mencari kecocokan (seperti dalam NFA), DFA mensimulasikan pemindaian paralel. Jadi mengapa Java (dan .NET, Perl, Python, Ruby, PHP, dll.) menggunakan NKA dan bukan DKA yang memiliki perilaku lebih baik? Pasalnya, NKA memiliki sejumlah keunggulan signifikan:

Mengkompilasi lebih cepat dan membutuhkan lebih sedikit memori
Mengizinkan beberapa fitur berguna (lihat tutorial Sun untuk detailnya ):

Pengambilan Grup dan Tautan Balik
Pemeriksaan posisi
Quantifier yang Diperluas (Serakah dan Malas)

Penting untuk dicatat bahwa istilah populer NKA dan DKA tidak tepat bila digunakan dalam konteks ekspresi reguler. Secara teori, kedua model ini memiliki kekuatan komputasi yang sama. Artinya, Anda tidak dapat menulis ekspresi reguler dalam satu model automata yang tidak mungkin diungkapkan di model automata lain. Dalam praktiknya, diperlukan lebih banyak kemampuan agar kedua jenis implementasi tersebut berbeda secara semantik. Mesin NKA memberikan lebih banyak fleksibilitas sehingga menjadikannya lebih unggul daripada DKA dalam hal daya komputasi. Karena kecepatan DFA dan fitur unik NFA, ada 2 cara “prefabrikasi” lagi untuk mengimplementasikan ekspresi reguler. Beberapa implementasi menggunakan kedua jenis tersebut (misalnya GNU egrep, yang memilih mesin tertentu saat runtime), dan beberapa telah berhasil mengimplementasikan versi yang benar-benar hibrid (misalnya Tcl regexps) dengan segala kelebihannya.

Saran

Berikut adalah beberapa tips tentang cara menghindari masalah efisiensi regex di Java. Banyak di antaranya ditujukan untuk mengurangi keuntungan.

1) Pra-kompilasi

Basi, tapi patut disebutkan. Jika Anda menggunakan regexp lebih dari sekali, pastikan untuk mengkompilasinya terlebih dahulu:

// компиляция p = Pattern.compile(regex, flags); … // использование Matcher a = p.matcher(input);

2) Pengukur Malas vs. Pengukur Serakah

Secara default, bilangan ( * + ? ) bersifat serakah. Ini berarti mereka mulai mencocokkan dengan urutan terpanjang dan kemudian secara bertahap mengerjakannya kembali jika perlu. Jika Anda mengetahui sebelumnya bahwa pertandingan biasanya akan berlangsung singkat, Anda harus menggunakan bilangan malas. Mereka memulai dengan kecocokan terkecil dan melanjutkan jika perlu. Katakanlah kita hanya ingin mencari baris yang cocok dengan urutan "halo". .*hello.* biasa akan melakukan segalanya dengan benar, tetapi jika kita tahu bahwa "hello" biasanya muncul di dekat awal teks, maka .*?hello.* rata-rata akan bekerja lebih cepat.

3) Gunakan bilangan super serakah jika memungkinkan

Tidak seperti bilangan malas, yang memengaruhi kinerja namun tidak memengaruhi perilaku reguler, bilangan super serakah sebenarnya dapat mengubah arti ekspresi reguler. Ketika *+ digunakan sebagai pengganti * , kecocokan pertama akan menjadi serakah (yaitu, kemungkinan terbesar seolah-olah hanya *), tetapi tidak akan ada kemunduran jika gagal, bahkan jika hal ini menyebabkan seluruh pencarian gagal. Kapan hal ini berguna? Katakanlah kita perlu mencari teks dalam tanda kutip. \"[^\"]*\" biasa akan berfungsi dengan baik. Namun, ini akan membuat lekukan yang tidak perlu dalam kasus negatif (misalnya, “bla bla bla). Menggunakan \"[^\"]*+\" akan menghilangkan rollback tanpa mengubah arti ekspresi. Pengelompokan independen mencapai efek yang sama dan memberikan lebih banyak kontrol (lihat tutorial Sun ).

4) Hindari penangkapan kelompok

Ekspresi apa pun dalam tanda kurung dianggap sebagai grup secara default. Hal ini berdampak kecil pada kinerja. Jadikan grup Anda "tidak dapat ditangkap" bila memungkinkan dengan memulainya dengan (?: alih-alih ( .

5) Gunakan interleaving dengan bijak

Saat interleaving digunakan (misalnya Paul|Jane|Chris ), urutan di mana mesin mencoba mencocokkan opsi sama dengan urutan kemunculannya. Anda dapat memanfaatkan fitur ini dan menempatkan opsi paling umum lebih dekat ke awal. Ini akan meningkatkan waktu respons positif rata-rata.

6) Hindari ambiguitas

Tulis regexps sedemikian rupa untuk meminimalkan jumlah kecocokan berbeda dalam string input. Misalnya: ekspresi reguler (a*b*)* yang diberikan di awal artikel memungkinkan string "aabb" ditafsirkan dalam banyak cara: (a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Regexp (a|b)*, di sisi lain, hanya menafsirkan unik kombinasi secara positif. Hal ini sangat penting untuk mengurangi return pada kasus-kasus near- match.

7) Pratinjau

Pratinjau memungkinkan Anda menambahkan batasan urutan ke kiri/kanan posisi saat ini. Khususnya, dengan pandangan ke depan negatif, Anda dapat mencari baris yang tidak mengandung urutan tertentu (apa yang akan kita lakukan tanpa ini!). Bagaimana hal ini dapat membantu meningkatkan produktivitas? Katakanlah kita ingin mengambil URL dari tag link. Pertimbangkan ekspresi reguler berikut: a .* href=(\S*).*/ Untuk tag reguler, ekspresi ini hanya akan cocok dengan alamat jika teks berisi atribut "href" (\S digunakan untuk semua karakter kecuali pembatas) . Namun pada beberapa tag yang tidak biasa, misalnya, akan terjadi rollback. Misalnya: “a href= href=href=…. href=sesuatu.” Regexp berikut akan mencegah hal ini terjadi ketika mengganti “.*” dalam ekspresi dengan sesuatu yang tidak cocok dengan “href”: a ((?!href).)* href=(\S*)((?!href).)*/

8) Tentukan panjangnya

Java berisi pengoptimal regexp yang memeriksa panjang string input terhadap panjang minimum dan maksimum yang diperoleh dari ekspresi reguler. Hal ini memungkinkan Anda untuk segera berhenti mencari dalam beberapa kasus. Untuk membantu mekanisme ini, jumlah pengulangan harus ditentukan bila memungkinkan (misalnya, [01]{6} cocok dengan semua string biner sepanjang enam karakter).

9) Pilih garis yang identik

Terkadang string yang sama disembunyikan di dalam grup atau alternatif: (hello|hell|heel) Ekspresi ini dapat disederhanakan menjadi: he(llo|ll|el) Dengan melakukan ini, kami memberikan lebih banyak informasi kepada pengoptimal regexp.

10) Uji regexp Anda

Mungkin bijaksana untuk menguji ekspresi reguler terlebih dahulu ketika akan digunakan dalam aplikasi yang kinerjanya penting. Tulis tolok ukur mikro yang menguji ekspresi Anda pada berbagai data masukan. Pastikan untuk menguji data dengan panjang yang bervariasi, dan juga data yang sangat cocok dengan sampel Anda.

Tautan:

http://java.sun.com/docs/books/tutorial/essential/regex/index.html http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page =1 http://www.softec.st/en/OpenSource/DevelopersCorner/RegularExpressions/RegularExpressionEngines.html http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics -dari-Pemrosesan-Ekspresi/