Backtracking dalam ekspresi reguler
Backtracking terjadi saat pola regex berisi pembilang opsional atau konstruksi pergantian, dan mesin regex kembali ke status tersimpan sebelumnya untuk melanjutkan pencariannya untuk kecocokan. Backtracking adalah pusat kekuatan regex; memungkinkan ekspresi menjadi kuat dan fleksibel, dan untuk mencocokkan pola yang sangat kompleks. Pada saat yang sama, kekuatan ini memiliki risiko. Backtracking sering menjadi faktor terpenting tunggal yang memengaruhi performa mesin regex. Untungnya, pengembang mempunyai kendali atas perilaku mesin regex dan bagaimana ia menggunakan backtracking. Topik ini menjelaskan bagaimana cara kerja backtracking dan bagaimana hal tersebut dapat dikendalikan.
Peringatan
Saat menggunakan System.Text.RegularExpressions untuk memproses masukan yang tidak tepercaya, berikan batas waktu. Pengguna berbahaya dapat memberikan input ke RegularExpressions, yang menyebabkan serangan Penolakan Layanan. ASP.NET API kerangka kerja Core yang menggunakan RegularExpressions batas waktu.
Perbandingan linier tanpa backtracking
Jika pola ekspresi biasa tidak memiliki pembilang opsional atau konstruksi pergantian, mesin regex mengeksekusi dalam waktu linier. Artinya, setelah mesin regex cocok dengan elemen bahasa pertama dalam pola dengan teks dalam string input, ia mencoba mencocokkan elemen bahasa berikutnya pada pola dengan karakter atau kelompok karakter berikutnya dalam string input. Ini berlanjut sampai pencocokan berhasil atau gagal. Pada kedua kondisi tersebut, mesin regex maju sebanyak satu karakter pada satu waktu dalam string input.
Contoh berikut memberikan ilustrasi. Regex e{2}\w\b mencari dua kemunculan huruf "e" diikuti oleh karakter kata apa pun lalu diikuti dengan batas kata.
using System;
using System.Text.RegularExpressions;
public class Example1
{
public static void Run()
{
string input = "needing a reed";
string pattern = @"e{2}\w\b";
foreach (Match match in Regex.Matches(input, pattern))
Console.WriteLine("{0} found at position {1}",
match.Value, match.Index);
}
}
// The example displays the following output:
// eed found at position 11
Imports System.Text.RegularExpressions
Module Example1
Public Sub Run()
Dim input As String = "needing a reed"
Dim pattern As String = "e{2}\w\b"
For Each match As Match In Regex.Matches(input, pattern)
Console.WriteLine("{0} found at position {1}",
match.Value, match.Index)
Next
End Sub
End Module
' The example displays the following output:
' eed found at position 11
Meskipun regex ini mencakup pembilang {2}, ekspresi ini dievaluasi secara linier. Mesin regex tidak melakukan backtrack karena {2} bukan pembilang opsional; mesin ini menentukan angka yang tepat dan bukan variabel berapa kali subekspresi sebelumnya harus cocok. Akibatnya, mesin regex mencoba mencocokkan pola regex dengan string input seperti yang ditunjukkan pada tabel berikut ini.
| Operasi | Posisi di dalam pola | Posisi di dalam string | Hasil |
|---|---|---|---|
| 1 | e | "needing a reed" (indeks 0) | Tidak ada kecocokan. |
| 2 | e | "eeding a reed" (indeks 1) | Kemungkinan cocok. |
| 3 | e{2} | "eding a reed" (indeks 2) | Kemungkinan cocok. |
| 4 | \w | "ding a reed" (indeks 3) | Kemungkinan cocok. |
| 5 | \b | "ing a reed" (indeks 4) | Kemungkinan kecocokan gagal. |
| 6 | e | "eding a reed" (indeks 2) | Kemungkinan cocok. |
| 7 | e{2} | "ding a reed" (indeks 3) | Kemungkinan kecocokan gagal. |
| 8 | e | "ding a reed" (indeks 3) | Pencocokan gagal. |
| 9 | e | "ing a reed" (indeks 4) | Tidak ada kecocokan. |
| 10 | e | "ng a reed" (indeks 5) | Tidak ada kecocokan. |
| 11 | e | "g a reed" (indeks 6) | Tidak ada kecocokan. |
| 12 | e | " a reed" (indeks 7) | Tidak ada kecocokan. |
| 13 | e | "a reed" (indeks 8) | Tidak ada kecocokan. |
| 14 | e | " reed" (indeks 9) | Tidak ada kecocokan. |
| 15 | e | "reed" (indeks 10) | Tidak ada kecocokan |
| 16 | e | "eed" (indeks 11) | Kemungkinan cocok. |
| 17 | e{2} | "ed" (indeks 12) | Kemungkinan cocok. |
| 18 | \w | "d" (indeks 13) | Kemungkinan cocok. |
| 19 | \b | "" (indeks 14) | Cocok. |
Jika pola regex tidak menyertakan kuantifer opsional atau konstruksi perubahan, jumlah maksimum perbandingan yang dibutuhkan untuk mencocokkan pola regex dengan string input kira-kira setara dengan jumlah karakter dalam string input. Dalam hal ini, mesin regex menggunakan 19 perbandingan untuk mengidentifikasi kemungkinan kecocokan dalam string 13 karakter ini. Dengan kata lain, mesin regex berjalan dalam waktu yang hampir linear jika tidak mengandung pembilang opsional atau konstruksi pergantian.
Backtracking dengan kuantifier opsional atau konstruksi alternasi
Ketika regex mencakup pembilang opsional atau konstruksi pergantian, evaluasi string input tidak lagi bersifat linier. Pencocokan pola dengan mesin Nondeterministic Finite Automaton (NFA) didorong oleh elemen bahasa dalam ekspresi reguler dan bukan oleh karakter yang akan dicocokkan dalam string input. Oleh karena itu, mesin regex mencoba untuk sepenuhnya mencocokkan subekspresi opsional atau alternatif. Saat maju ke elemen bahasa berikutnya dalam subekspresi dan kecocokan tidak berhasil, mesin regex dapat meninggalkan sebagian dari kecocokan yang berhasil dan kembali ke status tersimpan sebelumnya demi mencocokkan regex secara keseluruhan dengan string input. Proses kembali ke keadaan yang tersimpan sebelumnya untuk menemukan kecocokan dikenal sebagai backtracking.
Misalnya, pertimbangkan pola regex .*(es), yang cocok dengan karakter "es" dan semua karakter yang mendahuluinya. Seperti yang ditunjukkan oleh contoh berikut ini, jika string input berisi "Essential services are provided by regular expressions.", pola cocok dengan seluruh string hingga dan termasuk "es" dalam "expressions".
using System;
using System.Text.RegularExpressions;
public class Example2
{
public static void Run()
{
string input = "Essential services are provided by regular expressions.";
string pattern = ".*(es)";
Match m = Regex.Match(input, pattern, RegexOptions.IgnoreCase);
if (m.Success)
{
Console.WriteLine("'{0}' found at position {1}",
m.Value, m.Index);
Console.WriteLine("'es' found at position {0}",
m.Groups[1].Index);
}
}
}
// 'Essential services are provided by regular expressions found at position 0
// 'es' found at position 47
Imports System.Text.RegularExpressions
Module Example2
Public Sub Run()
Dim input As String = "Essential services are provided by regular expressions."
Dim pattern As String = ".*(es)"
Dim m As Match = Regex.Match(input, pattern, RegexOptions.IgnoreCase)
If m.Success Then
Console.WriteLine("'{0}' found at position {1}",
m.Value, m.Index)
Console.WriteLine("'es' found at position {0}",
m.Groups(1).Index)
End If
End Sub
End Module
' 'Essential services are provided by regular expressions found at position 0
' 'es' found at position 47
Untuk melakukan ini, mesin regex menggunakan backtracking sebagai berikut:
Mesin itu mencocokkan dengan
.*(yang cocok dengan nol, satu, atau lebih kemunculan karakter apa pun) dengan seluruh string input.Lalu, mesin mencoba untuk mencocokkan "e" dalam pola regex. Namun, string input tidak memiliki karakter tersisa yang tersedia untuk dicocokkan.
String input mundur ke kecocokan terakhirnya yang berhasil, "Layanan penting disediakan oleh regex", dan mencoba untuk mencocokkan "e" dengan titik di akhir kalimat. Pencocokan gagal.
String input terus melakukan backtrack ke keberhasilan pencocokan sebelumnya satu demi satu karakter hingga substring yang dicocokkan secara tentatif adalah "Layanan penting disediakan oleh expr reguler". Lalu membandingkan "e" dalam pola dengan "e" kedua dalam "expressions" dan menemukan kecocokan.
String input membandingkan "s" dalam pola dengan "s" yang mengikuti karakter "e" yang cocok ("s" pertama dalam "expressions"). Pencocokan ini Berhasil.
Backtracking memerlukan 67 operasi perbandingan untuk mencocokkan pola regex dengan string input yang panjangnya 55 karakter saat Anda menggunakannya. Umumnya, jika pola regex memiliki konstruksi pergantian tunggal atau pembilang opsional tunggal, jumlah operasi perbandingan yang diperlukan untuk mencocokkan pola lebih dari dua kali jumlah karakter dalam string input.
Backtracking dengan kuantifer opsional berlapis
Jumlah operasi perbandingan yang dibutuhkan untuk mencocokkan pola regex dapat meningkat secara eksponensial jika pola tersebut mencakup sejumlah besar konstruksi pergantian, jika itu termasuk konstruksi pergantian bersarang, atau, paling sering, jika itu termasuk pembilang opsional berlapis. Misalnya, pola regex ^(a+)+$ dirancang untuk mencocokkan string lengkap yang berisi satu atau beberapa karakter "a". Contoh ini menyediakan dua string input dengan panjang yang sama, tetapi hanya string pertama yang cocok dengan pola tersebut. Kelas System.Diagnostics.Stopwatch digunakan untuk menentukan berapa lama operasi pencocokan akan berlangsung.
using System;
using System.Diagnostics;
using System.Text.RegularExpressions;
public class Example3
{
public static void Run()
{
string pattern = "^(a+)+$";
string[] inputs = { "aaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaaaa!" };
Regex rgx = new Regex(pattern);
Stopwatch sw;
foreach (string input in inputs)
{
sw = Stopwatch.StartNew();
Match match = rgx.Match(input);
sw.Stop();
if (match.Success)
Console.WriteLine($"Matched {match.Value} in {sw.Elapsed}");
else
Console.WriteLine($"No match found in {sw.Elapsed}");
}
}
}
// Matched aaaaaaaaaaaaaaaaaaaaaaaaaaa in 00:00:00.0018281
// No match found in 00:00:05.1882144
Imports System.Text.RegularExpressions
Module Example3
Public Sub Run()
Dim pattern As String = "^(a+)+$"
Dim inputs() As String = {"aaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaaaa!"}
Dim rgx As New Regex(pattern)
Dim sw As Stopwatch
For Each input As String In inputs
sw = Stopwatch.StartNew()
Dim match As Match = rgx.Match(input)
sw.Stop()
If match.Success Then
Console.WriteLine("Matched {0} in {1}", match.Value, sw.Elapsed)
Else
Console.WriteLine("No match found in {0}", sw.Elapsed)
End If
Next
End Sub
End Module
' Matched aaaaaaaaaaaaaaaaaaaaaaaaaaa in 00:00:00.0018281
' No match found in 00:00:05.1882144
Seperti yang ditunjukkan oleh output dari contoh, mesin ekspresi reguler membutuhkan waktu yang jauh lebih lama untuk menemukan bahwa string input tidak cocok dengan pola seperti yang ditunjukkan untuk mengidentifikasi string yang cocok. Ini karena pencocokan yang gagal selalu mewakili skenario terburuk. Mesin regex harus menggunakan regex untuk mengikuti semua jalur yang mungkin melalui data sebelum dapat menyimpulkan bahwa kecocokan tidak berhasil, dan tanda kurung berlapis membuat banyak jalur tambahan melalui data. Mesin regex menyimpulkan bahwa string kedua tidak cocok dengan pola dengan melakukan hal berikut:
Mesin memeriksa bahwa itu berada di awal string, lalu kemudian mencocokkan lima karakter pertama dalam string dengan pola
a+. Kemudian menentukan bahwa tidak ada grup tambahan karakter "a" di dalam string. Akhirnya, mesin menguji akhir string. Karena satu karakter tambahan tetap berada dalam string, pencocokan gagal. Pencocokan yang gagal ini membutuhkan 9 perbandingan. Mesin ekspresi reguler juga menyimpan informasi status dari kecocokannya dengan "a" (yang akan kita sebut cocok dengan 1), "aa" (cocok dengan 2), "aaa" (cocok dengan 3), dan "aaaa" (cocok dengan 4).Mesin kembali ke kecocokan 4 yang disimpan sebelumnya. Mesin menentukan bahwa ada satu karakter "a" tambahan untuk ditetapkan ke grup tambahan yang diambil. Akhirnya, mesin menguji akhir string. Karena satu karakter tambahan tetap berada dalam string, pencocokan gagal. Pencocokan yang gagal ini membutuhkan 4 perbandingan. Sejauh ini, total ada 13 perbandingan yang sudah dilakukan.
Mesin kembali ke kecocokan 3 yang disimpan sebelumnya. Mesin menentukan bahwa ada dua karakter "a" tambahan untuk ditetapkan ke grup tambahan yang diambil. Namun, pengujian akhir string gagal. Kemudian kembali mencocokkan 3 dan mencoba mencocokkan dua karakter "a" tambahan dalam dua grup tambahan yang diambil. Pengujian akhir string masih gagal. Kecocokan yang gagal ini memerlukan 12 perbandingan. Sejauh ini, total 25 perbandingan telah dilakukan.
Perbandingan string input dengan regex berlanjut dengan cara ini sampai mesin regex selesai mencoba semua kemungkinan kombinasi kecocokan, dan kemudian menyimpulkan bahwa tidak ada kecocokan. Karena pembilang berlapis, perbandingan ini adalah O(2n) atau operasi eksponensial, di mana n adalah jumlah karakter dalam string input. Ini artinya bahwa pada kasus terburuk, string input 30 karakter membutuhkan sekitar 1.073.741.824 perbandingan, dan string input 40 karakter membutuhkan sekitar 1.099.511.627.776 perbandingan. Jika Anda menggunakan string ini atau bahkan lebih panjang, metode regex dapat memakan waktu yang sangat lama untuk menyelesaikan ketika mereka memproses input yang tidak sesuai dengan pola ekspresi biasa.
Mengontrol backtracking
Backtracking memungkinkan Anda membuat regex yang kuat dan fleksibel. Namun, seperti yang ditunjukkan pada bagian sebelumnya, manfaat ini dapat digabungkan dengan kinerja buruk yang tidak dapat diterima. Untuk mencegah backtracking yang berlebihan, Anda harus menentukan interval time-out saat Anda membuat instans objek Regex atau memanggil metode pencocokan ekspresi reguler statis. Ini akan dibahas di bagian berikutnya. Selain itu, .NET mendukung tiga elemen bahasa regex yang membatasi atau menekan backtracking dan yang mendukung regex yang kompleks dengan sedikit atau tanpa penalti performa: grup atomik, pernyataan lookbehind, dan pernyataan lookahead. Untuk informasi selengkapnya tentang setiap elemen bahasa, lihat Konstruksi pengelompokan.
Mesin ekspresi reguler non-backtracking
Jika Anda tidak perlu menggunakan konstruksi apa pun yang memerlukan backtracking (misalnya, lookaround, backreference, atau grup atom), pertimbangkan untuk menggunakan mode .RegexOptions.NonBacktracking Mode ini dirancang untuk dijalankan dalam proporsional waktu dengan panjang input. Untuk informasi selengkapnya, lihat Mode NonBacktracking. Anda juga dapat mengatur nilai waktu habis.
Membatasi ukuran input
Beberapa ekspresi reguler memiliki performa yang dapat diterima kecuali input sangat besar. Jika semua input teks yang wajar dalam skenario Anda diketahui berada di bawah panjang tertentu, pertimbangkan untuk menolak input yang lebih lama sebelum menerapkan ekspresi reguler ke input tersebut.
Tentukan interval waktu habis
Anda dapat mengatur nilai waktu habis yang mewakili interval terpanjang mesin ekspresi reguler akan mencari satu kecocokan sebelum meninggalkan upaya dan melempar RegexMatchTimeoutException pengecualian. Anda menentukan interval time-out dengan menyediakan TimeSpan nilai ke Regex(String, RegexOptions, TimeSpan) konstruktor untuk regex instans. Selain itu, setiap metode pencocokan pola statis memiliki kelebihan beban dengan TimeSpan parameter yang memungkinkan Anda menentukan nilai time-out.
Jika Anda tidak mengatur nilai waktu habis secara eksplisit, nilai batas waktu default ditentukan sebagai berikut:
- Dengan memakai nilai time-out di seluruh aplikasi, jika ada. Ini bisa menjadi nilai time-out yang berlaku untuk domain aplikasi tempat objek Regex dibuat atau panggilan metode statis dilakukan. Anda bisa mengatur nilai time-out di seluruh aplikasi dengan memanggil metode AppDomain.SetData untuk menetapkan representasi string nilai TimeSpan ke properti "REGEX_DEFAULT_MATCH_TIMEOUT".
- Dengan menggunakan nilai InfiniteMatchTimeout, jika tidak ada nilai time-out di seluruh aplikasi yang ditetapkan.
Secara default, interval time-out diatur ke Regex.InfiniteMatchTimeout dan mesin regex tidak kehabisan waktu.
Penting
Saat tidak menggunakan RegexOptions.NonBacktracking, kami sarankan Anda selalu mengatur interval waktu habis jika ekspresi reguler Anda bergantung pada backtracking atau beroperasi pada input yang tidak tepercaya.
Pengecualian RegexMatchTimeoutException menunjukkan bahwa mesin regex tidak dapat menemukan kecocokan dalam interval time-out yang ditentukan tetapi tidak menunjukkan mengapa pengecualian dilemparkan. Alasannya mungkin backtracking yang berlebihan, tetapi ada kemungkinan juga bahwa interval waktu habis diatur terlalu rendah mengingat beban sistem pada saat pengecualian dilemparkan. Saat Anda menangani pengecualian, Anda bisa memilih untuk meninggalkan kecocokan lebih lanjut dengan string input atau meningkatkan interval time-out dan mencoba kembali operasi yang cocok.
Misalnya, kode berikut memanggil Regex(String, RegexOptions, TimeSpan) konstruktor untuk membuat Regex instans objek dengan nilai batas waktu 1 detik. Pola regex (a+)+$, yang cocok dengan satu atau beberapa urutan satu atau beberapa karakter "a" di akhir baris, tunduk pada backtracking yang berlebihan. RegexMatchTimeoutException Jika dilemparkan, contoh meningkatkan nilai batas waktu hingga interval maksimum 3 detik. Setelah itu, ia akan meninggalkan upaya untuk mencocokkan pola.
using System;
using System.ComponentModel;
using System.Diagnostics;
using System.Security;
using System.Text.RegularExpressions;
using System.Threading;
public class Example
{
const int MaxTimeoutInSeconds = 3;
public static void Main()
{
string pattern = @"(a+)+$"; // DO NOT REUSE THIS PATTERN.
Regex rgx = new Regex(pattern, RegexOptions.IgnoreCase, TimeSpan.FromSeconds(1));
Stopwatch? sw = null;
string[] inputs = { "aa", "aaaa>",
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
"aaaaaaaaaaaaaaaaaaaaaa>",
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>" };
foreach (var inputValue in inputs)
{
Console.WriteLine("Processing {0}", inputValue);
bool timedOut = false;
do
{
try
{
sw = Stopwatch.StartNew();
// Display the result.
if (rgx.IsMatch(inputValue))
{
sw.Stop();
Console.WriteLine(@"Valid: '{0}' ({1:ss\.fffffff} seconds)",
inputValue, sw.Elapsed);
}
else
{
sw.Stop();
Console.WriteLine(@"'{0}' is not a valid string. ({1:ss\.fffff} seconds)",
inputValue, sw.Elapsed);
}
}
catch (RegexMatchTimeoutException e)
{
sw.Stop();
// Display the elapsed time until the exception.
Console.WriteLine(@"Timeout with '{0}' after {1:ss\.fffff}",
inputValue, sw.Elapsed);
Thread.Sleep(1500); // Pause for 1.5 seconds.
// Increase the timeout interval and retry.
TimeSpan timeout = e.MatchTimeout.Add(TimeSpan.FromSeconds(1));
if (timeout.TotalSeconds > MaxTimeoutInSeconds)
{
Console.WriteLine("Maximum timeout interval of {0} seconds exceeded.",
MaxTimeoutInSeconds);
timedOut = false;
}
else
{
Console.WriteLine("Changing the timeout interval to {0}",
timeout);
rgx = new Regex(pattern, RegexOptions.IgnoreCase, timeout);
timedOut = true;
}
}
} while (timedOut);
Console.WriteLine();
}
}
}
// The example displays output like the following :
// Processing aa
// Valid: 'aa' (00.0000779 seconds)
//
// Processing aaaa>
// 'aaaa>' is not a valid string. (00.00005 seconds)
//
// Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
// Valid: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (00.0000043 seconds)
//
// Processing aaaaaaaaaaaaaaaaaaaaaa>
// Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 01.00469
// Changing the timeout interval to 00:00:02
// Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 02.01202
// Changing the timeout interval to 00:00:03
// Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 03.01043
// Maximum timeout interval of 3 seconds exceeded.
//
// Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>
// Timeout with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>' after 03.01018
// Maximum timeout interval of 3 seconds exceeded.
Imports System.ComponentModel
Imports System.Diagnostics
Imports System.Security
Imports System.Text.RegularExpressions
Imports System.Threading
Module Example
Const MaxTimeoutInSeconds As Integer = 3
Public Sub Main()
Dim pattern As String = "(a+)+$" ' DO NOT REUSE THIS PATTERN.
Dim rgx As New Regex(pattern, RegexOptions.IgnoreCase, TimeSpan.FromSeconds(1))
Dim sw As Stopwatch = Nothing
Dim inputs() As String = {"aa", "aaaa>",
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
"aaaaaaaaaaaaaaaaaaaaaa>",
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>"}
For Each inputValue In inputs
Console.WriteLine("Processing {0}", inputValue)
Dim timedOut As Boolean = False
Do
Try
sw = Stopwatch.StartNew()
' Display the result.
If rgx.IsMatch(inputValue) Then
sw.Stop()
Console.WriteLine("Valid: '{0}' ({1:ss\.fffffff} seconds)",
inputValue, sw.Elapsed)
Else
sw.Stop()
Console.WriteLine("'{0}' is not a valid string. ({1:ss\.fffff} seconds)",
inputValue, sw.Elapsed)
End If
Catch e As RegexMatchTimeoutException
sw.Stop()
' Display the elapsed time until the exception.
Console.WriteLine("Timeout with '{0}' after {1:ss\.fffff}",
inputValue, sw.Elapsed)
Thread.Sleep(1500) ' Pause for 1.5 seconds.
' Increase the timeout interval and retry.
Dim timeout As TimeSpan = e.MatchTimeout.Add(TimeSpan.FromSeconds(1))
If timeout.TotalSeconds > MaxTimeoutInSeconds Then
Console.WriteLine("Maximum timeout interval of {0} seconds exceeded.",
MaxTimeoutInSeconds)
timedOut = False
Else
Console.WriteLine("Changing the timeout interval to {0}",
timeout)
rgx = New Regex(pattern, RegexOptions.IgnoreCase, timeout)
timedOut = True
End If
End Try
Loop While timedOut
Console.WriteLine()
Next
End Sub
End Module
' The example displays output like the following:
' Processing aa
' Valid: 'aa' (00.0000779 seconds)
'
' Processing aaaa>
' 'aaaa>' is not a valid string. (00.00005 seconds)
'
' Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
' Valid: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (00.0000043 seconds)
'
' Processing aaaaaaaaaaaaaaaaaaaaaa>
' Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 01.00469
' Changing the timeout interval to 00:00:02
' Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 02.01202
' Changing the timeout interval to 00:00:03
' Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 03.01043
' Maximum timeout interval of 3 seconds exceeded.
'
' Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>
' Timeout with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>' after 03.01018
' Maximum timeout interval of 3 seconds exceeded.
Kelompok atom
Elemen (?>bahasa subekspresi) adalah pengelompokan atomik. Ini mencegah backtracking ke dalam subekspresi. Setelah elemen bahasa ini berhasil dicocokkan, elemen tersebut tidak akan menyerahkan bagian mana pun dari kecocokannya dengan backtracking berikutnya. Misalnya, dalam pola (?>\w*\d*)1, jika 1 tidak dapat dicocokkan, \d* tidak akan menyerahkan salah satu kecocokannya bahkan jika itu berarti memungkinkan 1 untuk berhasil mencocokkan. Kelompok atom bisa membantu mencegah masalah kinerja yang terkait dengan kecocokan yang gagal.
Contoh berikut ini menggambarkan bagaimana menekan backtracking meningkatkan performa saat menggunakan pembilang berlapis. Ini mengukur waktu yang diperlukan mesin regex untuk menentukan bahwa string input tidak cocok dengan dua regex. Regex pertama menggunakan backtracking untuk mencoba mencocokkan string yang berisi satu atau lebih kejadian dari satu atau lebih digit heksadesimal, diikuti oleh titik dua, diikuti oleh satu atau lebih digit heksadesimal, diikuti oleh dua titik dua. Regex kedua identik dengan yang pertama, namun regex kedua menonaktifkan backtracking. Seperti yang ditunjukkan oleh output dari contoh ini, terjadi peningkatan kinerja yang signifikan dari menonaktifkan backtracking.
using System;
using System.Diagnostics;
using System.Text.RegularExpressions;
public class Example4
{
public static void Run()
{
string input = "b51:4:1DB:9EE1:5:27d60:f44:D4:cd:E:5:0A5:4a:D24:41Ad:";
bool matched;
Stopwatch sw;
Console.WriteLine("With backtracking:");
string backPattern = "^(([0-9a-fA-F]{1,4}:)*([0-9a-fA-F]{1,4}))*(::)$";
sw = Stopwatch.StartNew();
matched = Regex.IsMatch(input, backPattern);
sw.Stop();
Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, backPattern), sw.Elapsed);
Console.WriteLine();
Console.WriteLine("Without backtracking:");
string noBackPattern = "^((?>[0-9a-fA-F]{1,4}:)*(?>[0-9a-fA-F]{1,4}))*(::)$";
sw = Stopwatch.StartNew();
matched = Regex.IsMatch(input, noBackPattern);
sw.Stop();
Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, noBackPattern), sw.Elapsed);
}
}
// The example displays output like the following:
// With backtracking:
// Match: False in 00:00:27.4282019
//
// Without backtracking:
// Match: False in 00:00:00.0001391
Imports System.Text.RegularExpressions
Module Example4
Public Sub Run()
Dim input As String = "b51:4:1DB:9EE1:5:27d60:f44:D4:cd:E:5:0A5:4a:D24:41Ad:"
Dim matched As Boolean
Dim sw As Stopwatch
Console.WriteLine("With backtracking:")
Dim backPattern As String = "^(([0-9a-fA-F]{1,4}:)*([0-9a-fA-F]{1,4}))*(::)$"
sw = Stopwatch.StartNew()
matched = Regex.IsMatch(input, backPattern)
sw.Stop()
Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, backPattern), sw.Elapsed)
Console.WriteLine()
Console.WriteLine("Without backtracking:")
Dim noBackPattern As String = "^((?>[0-9a-fA-F]{1,4}:)*(?>[0-9a-fA-F]{1,4}))*(::)$"
sw = Stopwatch.StartNew()
matched = Regex.IsMatch(input, noBackPattern)
sw.Stop()
Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, noBackPattern), sw.Elapsed)
End Sub
End Module
' The example displays the following output:
' With backtracking:
' Match: False in 00:00:27.4282019
'
' Without backtracking:
' Match: False in 00:00:00.0001391
Pernyataan Lookbehind
.NET mencakup dua elemen bahasa, (?<=subekspresi) dan (?<!subekspresi), yang cocok dengan karakter atau karakter sebelumnya pada string input. Kedua elemen bahasa adalah pernyataan zero-width; artinya, mereka menentukan apakah karakter yang segera mendahului karakter saat ini dapat dicocokkan dengan subekspresi, tanpa harus advancing atau backtracking.
(?<=subekspresi) adalah pernyataan lookbehind positif; yaitu, karakter sebelum posisi saat ini cocok dengan subekspresi. (?<!subekspresi) adalah pernyataan lookbehind positif; yaitu, karakter sebelum posisi saat ini cocok dengan subekspresi. Pernyataan lookbehind positif dan negatif paling berguna saat subekspresi adalah subset dari subekspresi sebelumnya.
Contoh berikut ini menggunakan dua pola regex yang setara yang memvalidasi nama pengguna dalam alamat email. Pola pertama tunduk pada kinerja yang buruk karena backtracking yang berlebihan. Pola kedua memodifikasi regex pertama dengan mengganti pembilang berlapis dengan pernyataan lookbehind positif. Output dari contoh menampilkan waktu eksekusi metode Regex.IsMatch.
using System;
using System.Diagnostics;
using System.Text.RegularExpressions;
public class Example5
{
public static void Run()
{
Stopwatch sw;
string input = "test@contoso.com";
bool result;
string pattern = @"^[0-9A-Z]([-.\w]*[0-9A-Z])?@";
sw = Stopwatch.StartNew();
result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase);
sw.Stop();
Console.WriteLine("Match: {0} in {1}", result, sw.Elapsed);
string behindPattern = @"^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@";
sw = Stopwatch.StartNew();
result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase);
sw.Stop();
Console.WriteLine("Match with Lookbehind: {0} in {1}", result, sw.Elapsed);
}
}
// The example displays output similar to the following:
// Match: True in 00:00:00.0017549
// Match with Lookbehind: True in 00:00:00.0000659
Module Example5
Public Sub Run()
Dim sw As Stopwatch
Dim input As String = "test@contoso.com"
Dim result As Boolean
Dim pattern As String = "^[0-9A-Z]([-.\w]*[0-9A-Z])?@"
sw = Stopwatch.StartNew()
result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
sw.Stop()
Console.WriteLine("Match: {0} in {1}", result, sw.Elapsed)
Dim behindPattern As String = "^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@"
sw = Stopwatch.StartNew()
result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase)
sw.Stop()
Console.WriteLine("Match with Lookbehind: {0} in {1}", result, sw.Elapsed)
End Sub
End Module
' The example displays output similar to the following:
' Match: True in 00:00:00.0017549
' Match with Lookbehind: True in 00:00:00.0000659
Pola regex pertama, ^[0-9A-Z]([-.\w]*[0-9A-Z])*@, didefinisikan seperti yang ditunjukkan pada tabel berikut ini.
| Pola | Deskripsi |
|---|---|
^ |
Mulai pencocokan di awal string. |
[0-9A-Z] |
Cocokkan karakter alfanumerik. Perbandingan ini tidak peka huruf besar/kecil, karena metode Regex.IsMatch dipanggil dengan opsi RegexOptions.IgnoreCase. |
[-.\w]* |
Cocokkan nol, satu, atau lebih kejadian tanda hubung, titik, atau karakter kata. |
[0-9A-Z] |
Cocokkan karakter alfanumerik. |
([-.\w]*[0-9A-Z])* |
Cocokkan nol atau lebih kejadian kombinasi nol atau tanda hubung, titik, atau karakter kata, dan diikuti oleh karakter alfanumerik. Ini adalah grup penangkapan pertama. |
@ |
Cocok dengan tanda ("@"). |
Pola regex kedua, ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@, menggunakan pernyataan lookbehind positif. Ini didefinisikan seperti yang ditunjukkan pada tabel berikut.
| Pola | Deskripsi |
|---|---|
^ |
Mulai pencocokan di awal string. |
[0-9A-Z] |
Cocokkan karakter alfanumerik. Perbandingan ini tidak peka huruf besar/kecil, karena metode Regex.IsMatch dipanggil dengan opsi RegexOptions.IgnoreCase. |
[-.\w]* |
Cocokkan nol atau lebih kejadian tanda hubung, titik, atau karakter kata. |
(?<=[0-9A-Z]) |
Lihat kembali karakter terakhir yang cocok dan lanjutkan pencocokan jika alfanumerik. Perhatikan bahwa karakter alfanumerik adalah subset dari himpunan yang terdiri dari periode, tanda hubung, dan seluruh karakter kata. |
@ |
Cocok dengan tanda ("@"). |
Pernyataan lookahead
.NET mencakup dua elemen bahasa, (?=subekspresi) dan (?!subekspresi), yang cocok dengan karakter atau karakter sebelumnya dalam string input. Kedua elemen bahasa adalah pernyataan zero-width; artinya, mereka menentukan apakah karakter yang segera mendahului karakter saat ini dapat dicocokkan dengan subekspresi, tanpa harus melewati advancing atau backtracking.
(?=subekspresi) adalah pernyataan lookbehind positif; yaitu, karakter setelah posisi saat ini cocok dengan subekspresi. (?!subekspresi) adalah pernyataan lookbehind negatif; yaitu, karakter setelah posisi saat ini tidak cocok dengan subekspresi. Pernyataan lookbehind positif dan negatif paling berguna saat subekspresi adalah subset dari subekspresi sebelumnya.
Contoh berikut ini menggunakan dua pola regex yang setara yang memvalidasi nama tipe yang sepenuhnya memenuhi syarat. Pola pertama tunduk pada kinerja yang buruk karena backtracking yang berlebihan. Yang kedua memodifikasi regex pertama dengan mengganti pembilang bersarang dengan pernyataan lookahead positif. Output dari contoh menampilkan waktu eksekusi metode Regex.IsMatch.
using System;
using System.Diagnostics;
using System.Text.RegularExpressions;
public class Example6
{
public static void Run()
{
string input = "aaaaaaaaaaaaaaaaaaaaaa.";
bool result;
Stopwatch sw;
string pattern = @"^(([A-Z]\w*)+\.)*[A-Z]\w*$";
sw = Stopwatch.StartNew();
result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase);
sw.Stop();
Console.WriteLine("{0} in {1}", result, sw.Elapsed);
string aheadPattern = @"^((?=[A-Z])\w+\.)*[A-Z]\w*$";
sw = Stopwatch.StartNew();
result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase);
sw.Stop();
Console.WriteLine("{0} in {1}", result, sw.Elapsed);
}
}
// The example displays the following output:
// False in 00:00:03.8003793
// False in 00:00:00.0000866
Imports System.Text.RegularExpressions
Module Example6
Public Sub Run()
Dim input As String = "aaaaaaaaaaaaaaaaaaaaaa."
Dim result As Boolean
Dim sw As Stopwatch
Dim pattern As String = "^(([A-Z]\w*)+\.)*[A-Z]\w*$"
sw = Stopwatch.StartNew()
result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
sw.Stop()
Console.WriteLine("{0} in {1}", result, sw.Elapsed)
Dim aheadPattern As String = "^((?=[A-Z])\w+\.)*[A-Z]\w*$"
sw = Stopwatch.StartNew()
result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase)
sw.Stop()
Console.WriteLine("{0} in {1}", result, sw.Elapsed)
End Sub
End Module
' The example displays the following output:
' False in 00:00:03.8003793
' False in 00:00:00.0000866
Pola regex pertama, ^(([A-Z]\w*)+\.)*[A-Z]\w*$, didefinisikan seperti yang ditunjukkan pada tabel berikut ini.
| Pola | Deskripsi |
|---|---|
^ |
Mulai pencocokan di awal string. |
([A-Z]\w*)+\. |
Cocokkan karakter alfabet (A-Z) diikuti dengan nol atau beberapa karakter kata satu atau beberapa kali, lalu diikuti oleh titik. Perbandingan ini tidak peka huruf besar/kecil, karena metode Regex.IsMatch dipanggil dengan opsi RegexOptions.IgnoreCase. |
(([A-Z]\w*)+\.)* |
Cocokkan pola sebelumnya nol atau lebih kali. |
[A-Z]\w* |
Cocokkan karakter abjad diikuti dengan karakter kata nol atau lebih. |
$ |
Akhiri kecocokan di akhir string input. |
Pola regex kedua, ^((?=[A-Z])\w+\.)*[A-Z]\w*$, menggunakan pernyataan lookbehind positif. Ini didefinisikan seperti yang ditunjukkan pada tabel berikut.
| Pola | Deskripsi |
|---|---|
^ |
Mulai pencocokan di awal string. |
(?=[A-Z]) |
Lihatlah ke depan untuk karakter pertama dan lanjutkan pencocokan jika sesuai abjad (A-Z). Perbandingan ini tidak peka huruf besar/kecil, karena metode Regex.IsMatch dipanggil dengan opsi RegexOptions.IgnoreCase. |
\w+\. |
Cocokkan satu atau beberapa karakter kata yang diikuti oleh titik. |
((?=[A-Z])\w+\.)* |
Cocokkan pola satu atau lebih karakter kata diikuti dengan satu atau beberapa kali titik nol. Karakter kata awal harus berupa abjad. |
[A-Z]\w* |
Cocokkan karakter abjad diikuti dengan karakter kata nol atau lebih. |
$ |
Akhiri kecocokan di akhir string input. |
Pertimbangan performa umum
Saran berikut tidak secara khusus untuk mencegah backtracking yang berlebihan, tetapi dapat membantu meningkatkan performa ekspresi reguler Anda:
Pola yang banyak digunakan prakombinasi. Cara terbaik untuk melakukan ini adalah dengan menggunakan generator sumber ekspresi reguler untuk melakukan prakombinasikan. Jika generator sumber tidak tersedia untuk aplikasi Anda, misalnya Anda tidak menargetkan .NET 7 atau yang lebih baru, atau Anda tidak tahu pola pada waktu kompilasi, gunakan RegexOptions.Compiled opsi .
Cache sangat menggunakan objek Regex. Ini secara implisit terjadi ketika Anda menggunakan generator sumber. Jika tidak, buat objek Regex dan simpan untuk digunakan kembali, daripada menggunakan metode Regex statis atau membuat dan membuang objek Regex.
Mulai mencocokkan dari offset. Jika Anda tahu bahwa kecocokan akan selalu dimulai di luar offset tertentu ke dalam pola, teruskan offset dalam menggunakan kelebihan beban seperti Regex.Match(String, Int32). Ini akan mengurangi jumlah teks yang perlu dipertimbangkan mesin.
Kumpulkan hanya informasi yang Anda butuhkan. Jika Anda hanya perlu tahu apakah kecocokan terjadi tetapi tidak di mana kecocokan terjadi, pilih Regex.IsMatch. Jika Anda hanya perlu tahu berapa kali sesuatu cocok, lebih suka menggunakan Regex.Count. Jika Anda hanya perlu mengetahui batas kecocokan tetapi tidak apa-apa tentang tangkapan kecocokan, lebih suka menggunakan Regex.EnumerateMatches. Semakin sedikit informasi yang perlu diberikan mesin, semakin baik.
Hindari pengambilan yang tidak perlu. Tanda kurung dalam pola Anda membentuk grup penangkapan secara default. Jika Anda tidak memerlukan pengambilan, tentukan RegexOptions.ExplicitCapture atau gunakan grup yang tidak menangkap sebagai gantinya. Ini menghemat mesin yang melacak tangkapan tersebut.
Lihat juga
Saran dan Komentar
Segera hadir: Sepanjang tahun 2024 kami akan menghentikan penggunaan GitHub Issues sebagai mekanisme umpan balik untuk konten dan menggantinya dengan sistem umpan balik baru. Untuk mengetahui informasi selengkapnya, lihat: https://aka.ms/ContentUserFeedback.
Kirim dan lihat umpan balik untuk