Wyrażenia regularne do upadłegoapasek.pl

Tak się jakoś dziwnie złożyło, że stanąłem dzisiaj przed problemem napisania pewnego wyrażenia regularnego. Po jego uproszczeniu problem sprowadza się do ciągu liter A i B dowolnej długości, w którym dwie literki B nigdy nie występują obok siebie (literki A mogą być obok siebie w dowolnej ilości). Czyli szukamy takiego regexa, do którego pasują na przykład A, B, AB, BA, AA, ABA, BAB, BABA, ale nie pasują na przykład BB, BBB, ABBA, AAAAABBAAAA, BBA, AABB.

Dla tych, co nie wiedzą czym są wyrażenia regularne, to można je wyjaśnić w skrócie tak: jest to wzorzec, do którego dany ciąg znaków pasuje, albo nie. Wyrażenia regularne służą do automatycznego sprawdzania, czy ciągi znaków podlegają określonym regułom (np.: czy są poprawnymi adresami e-mail, czy są liczbami, itp.). Wyrażenia regularne składają się z tzw. atomów i symboli specjalnych. Atom to coś, co pasuje albo nie do pojedynczego znaku (na przykład ten sam znak). Podstawowe symbole specjalne to ? (za atomem oznacza atom opcjonalny, czyli zero lub jedno wystąpienie) * (za atomem oznacza dowolną ilość powtórzeń, też zero powtórzeń) + (za atomem oznacza co najmniej jedno powtórzenie) | (między atomami oznacza alternatywę, czyli to, co po lewej albo to, co po prawej) i nawiasy robiące atom z czegoś, co atomem nie jest. Nawiasy z alternatywy albo z kilku atomów robią atom. I tyle, jeśli chodzi o podstawy wyrażeń regularnych.

Mój problem rozwiązuje się w oczywisty sposób przy pomocy tzw. negative lookahead tak:

(?!BB)[AB]*

Powyższy zapis oznacza dokładnie to, co trzeba: ciąg dowolnej ilości znaków A i B, w którym nie występuje ciąg BB (czyli w efekcie żaden ciąg n liter B, gdy n >= 2). [AB] to tzw. klasa znakowa i tutaj odpowiada alternatywie (A | B). Jeśli pierwszym znakiem w nawiasie jest ?, to jest to nawias o jakimś specjalnym znaczeniu (akurat tutaj to jest negative lookahead).

OK. Ale okazało się, że nie mogę użyć negative lookahead, bo schemy XSD go nie obsługują. Mówię OK, schemy mają być szybkie, więc to zrozumiałe. Ale w końcu mówię tak: Co? Ja nie wymyślę? Zaraz, zaraz… Przecież w takich ciągach B musi być otoczone przez co najmniej jedno A, chyba że B jest na początku albo na końcu. No to luz. Mój pierwszy regex wyglądał tak:

B?(A+BA+)+B?

Ma on kilka wad, bo nie obsługuje: pojedynczego A, pojedynczego B, ciągu ABABAB i niczego, co taki podciąg zawiera (oj, to już nie dobrze) ani ciągu BABABA. Za przeproszeniem dupa, czyli nic z tego nie będzie. Potem łamałem sobie głowę ze dwie godziny i doszedłem do czegoś takiego:

((BA)+|A+)*B?

Działa? No dobra, sprawdzamy: A, B, AB, BA, AAA, ABA, BAB, ABAB, BABA, itd. Działa! Uff. Zeszło ze mnie całe napięcie. Ja się chyba w ten sposób wykończę. Ale nic. Spoko. Poszedłem zrobić herbatę, położyłem się na chwilę, aż tu nagle….prawdziwe olśnienie! Można prościej!!!

B?(A+B)*A*

O trzy znaki mniej! Sposób podobny do tego pierwszego, ale tam za daleko się zagalopowałem. Tylko spokojnie. Mniej nie oznacza lepiej. Myk, myk i już.

// Regexes to test
var reg = new[] {
	new Regex("((BA)+|A+)*B?"),
	new Regex("B?(A+B)*A*"),
	new Regex("(?!BB)[AB]*"),
	new Regex("[AB]*(?
	new Func(x => x == r.Match(x).Value))
	.ToArray();

// Action Man rulez!!!
var cw = (Action)Console.WriteLine;

// test some bad strings (just to be safe...)
var bad_strings = new[] { "BB", "BBB", "BBBB",
	"ABB", "BBA", "ABBA", "BBABB", "ABBBA" };
foreach (string bad in bad_strings)
	for (int i = 0; i < tests.Length; i++)
		if (tests[i](bad))
			cw("bad test " + i + " failed on " + bad);

// prepare some good strings
var list = new List() { "A", "B" };
for (int i = 0, j = 0; i < 100000; i++, j++)
	if (list[j].EndsWith("A"))
	{
		list.Add(list[j] + "A"); i++;
		list.Add(list[j] + "B");
	}
	else // EndsWith("B")
		list.Add(list[j] + "A");
cw("max len = " + list[list.Count-1].Length);

// prepare the test routine
int duration = 10 * list.Count; // milion, który trzeba pożyczyć
string good;
long start;
Action> run = test =>
{
	int n = Array.FindIndex(tests, test.Equals);
	start = DateTime.Now.Ticks;
	for (int i = 0; i < duration; i++)
	{
		good = list[i % list.Count];
		if (!test(good))
		{
			cw("test " + n + " failed on " + good);
			return;
		}
	}
	cw("test " + n + " took "
		+ (DateTime.Now.Ticks - start));
};

// and finally test the good strings
foreach (var test in tests) run(test);

Oto rezultat powyższego kodu.

bad test 2 failed on ABB bad test 3 failed on BBA bad test 2 failed on ABBA bad test 3 failed on ABBA bad test 2 failed on ABBBA bad test 3 failed on ABBBA max len = 22 test 0 took 38142182 test 1 took 18271045 test 2 took 9980571 test 3 took 10000572Wygląda na to, że drugi regex jest około dwa razy szybszy. Czyli jest to jeden z tych przypadków, kiedy mniej rzeczywiście oznacza lepiej.

Ale, ale. Okazało się, że lookaround, zarówno lookahead (test 2), jak i lookbehind (test 3) są jeszcze prawie dwa razy szybsze. Wydaje mi się, że to zwykle nie jest regułą, ale to prosty przykład i może tak być. Szkoda tylko, że są niepoprawne. Tego się nie spodziewałem. Opłacało się umieścić linie od 17 do 23 żeby testy były bardziej kompletne. Jednak TDD robi swoje, nawet w takich prostych przypadkach.

Wniosek: mamy kolejną złotą regułę B?(A+B)*A*