Archiwa tagu: regex

Średnio zaawansowane

Wyrażenia regularne w Javie – figle i psikusy

Dodaj komentarz

To trzeci (i na jakiś czas ostatni) z serii wpisów na temat wyrażeń regularnych w Javie, po O wyrażeniach regularnych. Podstępna różnica pomiędzy find i matches oraz Wyrażenia regularne dla nieprogramistów. Historycznie ten jest najwcześniejszy – to zaktualizowana wersja tekstu z mojego poprzedniego bloga.

Poruszam tu bardzo podstawowe kwestie, które potrafią jednak dać się we znaki. Rozwiązanie tych paru niewinnych problemików kosztowało mnie niemało czasu i nerwów. Liczę, że kiedy jakaś zbłąkana dusza znajdzie się w tej samej sytuacji, Google zaprowadzi ją prosto w moje troskliwe ramiona.

Artykuł powstał podczas mojej pracy nad narzędziem do przekształcania metadanych.

Psikus 1: znaki ucieczki w wyrażeniach wczytywanych z zewnętrznego pliku

Załóżmy, że wyrażenie (które chcemy wczytać z zewnętrznego pliku) w zwykłym kodzie Javy wygląda tak:

Linia przedstawia zakres wieków, do którego dopasuje się na przykład linia:

Proste, prawda?

Prawda – ale do czasu. Problemy pojawiły się, kiedy zaczęłam wczytywać wyrażenia regularne zapisane w zewnętrznym pliku. Wczytywałam między innymi następujący fragment:

Wszystko przestało działać. Łańcuchy znaków, które bez najmniejszych wątpliwości powinny były dopasować się do wyrażenia, przechodziły niezauważone. Po godzinie analiz niebezpiecznie zbliżałam się do stanu, w którym myślałam, że oszalał albo świat dokoła mnie. Wtedy na szczęście nadeszła pora lunchu. Opowiedziałam o problemie nad talerzem naleśników, a jeden z kolegów zadał oczywiste w sumie pytanie – czy na pewno dobrze wyeskejpowałam (przepraszam!!!) wszystkie znaki specjalne. I wtedy wreszcie nadeszło olśnienie: nie, nie zrobiłam tego dobrze. Przeeskejpowałam je.

Znaki specjalne, takie jak d, w wyrażeniu regularnym oznaczające cyfrę, należy poprzedzić tzw. symbolem ucieczki, czyli w tym wypadku backslashem (ukośnikiem wstecznym). W łańcuchach znaków w kodzie Javy konieczne jest wprowadzenie dodatkowego backslasha, gdyż musimy jeszcze odebrać specjalne znaczenie samemu backslashowi (musimy poprzedzić znak ucieczki znakiem ucieczki…). Tyle razy widziałam te dwa ukośniki w parze, że zupełnie zapomniałam o tym, że w zewnętrznym pliku należy użyć tylko jednego!

Psikus 2: flagi

To bardzo proste. Załóżmy, że wyrażenie nie ma brać pod uwagę wielkość liter. Normalnie oznaczamy to tak:

Świetnie, tylko jak przekazać tę flagę, jeśli wyrażenie jest wczytywane z zewnątrz? Wychodzi na to, że flagę, poprzedzoną znakiem zapytania, należy umieścić w nawiasie na początku wyrażenia. Ignorowanie wielkości liter (przy okazji, poznałam ostatnio nowe słowo – kasztowość) to literka i, zatem dodajemy (?i). Ostatecznie, w kodzie wyrażenie wygląda tak:

a poza kodem, z pojedynczymi ukośnikami, tak:

Psikus 3: String.replaceAll

W pewnym brzegowym przypadku mój kod, w wyniku wczytania wyrażeń regularnych z pliku, wykonywał operację, którą można w uproszczeniu zapisać tak:

Po wykonaniu się tego kodu spodziewałam się, że treść zostanie całkowicie zastąpiona, czyli wartością s będzie:

skoro * jest zachłannym kwantyfikatorem, to .* powinno dopasować się do całego napisu niezależnie od okoliczności.

Wyobraźcie sobie moje zaskoczenie (czy raczej przerażenie), gdy okazało się, że s przyjęło wartość:

Próbowałam użyć jeszcze bardziej zaborczego kwantyfikatora *+, ale efekt był ten sam. Byłabym mniej zaskoczona, gdyby .* zostało dopasowane do każdej litery w łańcuchu. Jakim cudem dopasowało się dokładnie dwa razy?

Dalsze śledztwo wykazało, że przebieg akcji jest następujący:

  1. Cały łańcuch dopasowuje się do .* i jest zamieniany na łańcuch “nowa treść”.
  2. Po dopasowaniu z oryginalnego łańcucha znaków nie zostaje nic, a raczej zostaje łańcuch "". Metoda replaceAll jeszcze raz sprawdza możliwość dopasowania i okazuje się, że "" także pasuje do .*, zatem pusty łańcuch również zostaje wymieniony.
  3. Zasadniczo można by kontynuować i w nieskończoność dodawać na końcu "nowa zawartość", jednak na szczęście (?) dana pozycja w łańcuchu znaków jest traktowana jako sprawdzona i wykonanie metody kończy się.

Pozdrawiam siostry i braci w cierpieniu.

Ogólnie o programowaniu

Wyrażenia regularne dla nieprogramistów

11 komentarzy

Wyrażenia regularne wspominałam już w poprzednim wpisie. Jest to narzędzie ukochane przez część programistów i znienawidzone przez innych. Dzisiaj chciałabym podzielić się następującą refleksją: wyrażenia regularne mogą ułatwić życie nie tylko programistom. Przy ich pomocy można uprościć wiele manualnych czynności, wykonywanych na przykład w pracy biurowej.

Czym są wyrażenia regularne?

Teoria raczej nie zachęci początkujących, ale do zastosowań praktycznych wystarczy potraktować je jako wzorce, które umożliwiają przeszukiwanie tekstu i dokonywanie w nim podmian.

Pełna składnia wyrażeń regularnych została opisana na przykład w tej (angielskojęzycznej) ściądze. Poniższa tabelka opisuje kilka najbardziej podstawowych symboli:

Symbol Znaczenie Przykład
. Dowolny znak. k.t pasuje do „kot” i „kat”
+ Powtórzenie poprzedzającego znaku jeden lub więcej razy. kot+ pasuje do „kot”, „kott”, „kott” itp.
* Powtórzenie poprzedzającego znaku zero lub więcej razy. kot* pasuje do „ko”, „kot”, „kott” itp.
{m,n} Powtórzenie poprzedzającego znaku od m do n razy. ko{2,4}t pasuje do „koot”, „kooot” i „kooot”.
^ Początek linii. ^k – literka k zapisana na początku linii
$ Koniec linii k$
[abc] Znaki ze zbioru, wyszczególnione k[ao]t pasuje do „kot” i „kat”.
[a-c] Znaki ze wskazanego przedziału [2-4] to cyfra „2”, „3” lub „4”.
\b Granica słowa .+a\b to dowolne słowo kończące się na literą „a”, np. „torba”.
\d Cyfra \d\d pasuje na przykład do „23”
\s Biały znak k\st pasuje do „k t”
\S Znak niebiały k\St pasuje do „kot”, „kit”, ale nie do „k t”

Zadanie

Wyobraźmy sobie teraz następujący scenariusz z życia biura. Szef firmy, pan Cebuliński, organizuje przedświąteczną galę. W ramach oszczędności poprosił siostrzenicę – studentkę pierwszego roku informatyki – o wydobycie z bazy danych informacji o klientach, którzy terminowo opłacali faktury. Na podstawie przesłanej przez nią listy menedżerka biura, pani Nokturniak, ma przygotować listę gości. Jej zadaniem jest znalezienie stu klientów, na których firma w tym roku zarobiła najwięcej. Dodatkowo, ponieważ prezes Cebuliński rozwodzi się ze swoją żoną Anną, na liście gości nie może znaleźć się ani jedna kobieta o tym imieniu.

Lista ma następującą postać:

1. Borowiak, Kazimierz; 10000 zł; terminowo; kborowiak@example.com
2. Borowiak, Ania B.; 10011 zł; nieterminowo; abborowiak@example.com
3. Nowak, Jan, 9321 zł; terminowo; a@example.com
4. Nowak, Janina, 9322 zł; nieterminowo; ab@example.com
...
9816. Zi łkowski, Andrzej; 100 zł; terminowo; aziolkowski@example.com

Zadania pani Nokturniak prezentują się następująco:

  1. Musi usunąć z listy wszystkie Anie, Anki i Anny.
  2. Zauważyła, że litera „ó” została zamieniona na spację. Musi więc przejrzeć listę prawie 10000 nazwisk i poprawić niektóre z nich.
  3. Musi znaleźć 100 „najdroższych” klientów spośród tych, którzy płacili terminowo, aby wysłać im zaproszenia.

Pani Nokturniak zaplanowała kolejną długą noc przy komputerze. Spróbujmy chociaż trochę ułatwić jej życie.

Potrzebny nam będzie edytor tekstu, który rozumie wyrażenia regularne (albo konsola Linuksa – pokażę w kolejnym wpisie, jak ją do tego wykorzystać). Może to być np. Notepad++. Załóżmy, że pani Nokturniak otworzyła już edytor i przekleiła do niego dane.

Usunięcie Ań

Co wspólnego mają ze sobą łańcuchy znaków „Ania”, „Anka” i „Anna”? Wyglądają prawie tak samo, różnią się jedynie trzecim znakiem. Zgodnie z zamieszczoną powyżej tabelą, kropka (.) to symbol uniwersalny. Do wszystkich trzech słów zostanie dopasowany dopasowany wzorzec:

An.a

Wyrażenie regularne w edytorze Notepad++ dopasowane do słowa w tekście
Wyrażenie regularne w edytorze Notepad++ dopasowane do słowa w tekście

Tu uwaga na drobną pułapkę. Ciąg znaków „Anna” może być częścią dłuższego słowa, np. nazwiska („Annakowski”). Dla pewności zaznaczmy, że interesują nas tylko te wystąpienia, które nie są częścią dłuższego słowa. Użyję do tego symbolu granicy słowa:

\bAn.a\b

Co dalej? Wyczyśćmy wszystkie linie zawierające imię Anna. Wzorzec musi mieć postać: „nieważne co – imię Anna – nieważne co”, czyli:

.*\bAn.a\b.*

albo jeszcze lepiej dodajmy do niego znak początku i końca linii (choć domyślnie wyrażenia regularne i tak działają jedynie w ramach jednej linii, czyli efekt będzie ten sam):

^.*\bAn.a\b.*$.

Każmy edytorowi zastąpić wszystkie takie linie linią pustą.

regex2
Zamiana linii zawierającej którąś z wersji imienia “Anna” na linię pustą.

W tej chwili nasz dokument nie zawiera już danych żadnych Ann.

W podobny sposób możemy od razu usunąć wiersze reprezentujące klientów nieterminowych, których także nie mamy uwzględniać w obliczeniach.

2. Zamiana (niektórych!) spacji na „ó”

Jeśli po prostu zamienię wszystkie spacje na „ó”, efekt nie będzie zadowalający:

Muszę odszukać tylko te spacje, które znajdują się pomiędzy dwiema małymi literami.

Mogę wykorzystać w tym celu przedziały:

[a-z] [a-z]

lub bezpieczniej

[a-zA-ZąśćżńżĄŚĆŻŃŹ] [a-zząśćżńż]

lub najbezpieczniej (z uwzględnieniem wszystkich, nie tylko polskich znaków w nazwiskach, ale nie w każdym edytorze to zadziała) pełną klasę małych liter:

\p{Lu} \p{Lu}

Ok, znaleźliśmy te spacje, tylko jak je teraz zamienić? Jeśli zamienię cały znaleziony łańcuch znaków, Zi łkowski nie zamieni się w Ziółkowskiego, tylko w Zókowskiego (litery dopasowane do [az] również zostaną zamienione). Na pomoc spieszą nam tzw. capturing groups, czyli grupy przechwytujące.

Wszystko, co napiszę w nawiasie, zostanie zapamiętane jako grupa oznaczona kolejnym numerem. Do grup mogę się następnie odnieść w wyrażeniu, którym chcę zastąpić odnaleziony wzorzec. Jak to zrobić? Mogę mój wzorzec zapisać tak:

([a-zA-Z]) ([a-z])

a wyrażenie zastępujące:

\1ó\2

Wówczas każde wystąpienie spacji pomiędzy dwiema literami (przy czym druga z nich musi być mała) zostanie zastąpione literą „ó” otoczoną oryginalnymi dwiema literami (z grupy pierwszej i drugiej).

regex3

3. Odnalezienie „najdroższych” klientów

Do tego zadania można podejść na dwa różne sposoby.

Łatwiej ale z pomocą z zewnątrz

W wersji pierwszej wystarczy sprowadzić dokument do formatu CSV (skrót od Comma-Separated Values, czyli wartości rozdzielane przecinkami, ale czym w rzeczywistości najczęściej są to średniki, a nie przecinki). Format ten jest rozumiany przez większość, jeśli nie wszystkie, programów kalkulacyjnych typu Excel. Następnie można posortować wiersze według kolumny zawierającej poniesione przez klienta koszty.

W obecnej chwili nasze wiersze mają następujący format:
1. Borowiak, Kazimierz; 10000 zł; terminowo; kborowiak@example.com
Wystarczy zamienić pierwszą kropkę na średnik albo usunąć liczbę i kropkę. Na dobrą sprawę moglibyśmy nawet zostawić numer porządkowy jak jest. Nie będzie miał sensu, ale nie przeszkodzi w naszych obliczeniach.

Dla porządku (sic) usuńmy jednak numer porządkowy. Chcemy dopasować się do liczby na początku linii, po której następuje kropka oraz spacja – i całość zastąpić pustym łańcuchem znaków. Czyli:

^\d+\. albo ^\d+. (kropka to symbol uniwersalny, w szczególności dopasuje się do symbolu kropki; jeśli chcemy na pewno złapać tylko kropkę, musimy poprzedzić ją we wzorcu tzw. symbolem ucieczki „\”, który odbiera znakowi jego specjalne znaczenie).

Dokument z liniami postaci:
Borowiak, Kazimierz; 10000 zł; terminowo; kborowiak@example.com

możemy już spokojnie otworzyć w excelu jako plik CSV i tam przeprowadzić sortowanie.

Wersja dla ambitniejszych

Alternatywnie możemy przestawić kwotę na początek linii i w oparciu o nią posortować linie w pliku. Z pomocą znowu przyjdą nam grupy. Plan jest następujący: podzielić każdą linię na 3 grupy: przed kwotą, kwota i za kwotą, następnie zmienić ich kolejność z 123 n 213. Na koniec posortować (w edytorze, jeśli daje taką możliwość, albo w wierszu poleceń dowolnego systemu operacyjnego za pomocą instrukcji sort).

Spróbujmy. Linię pasującą do wzorca

^(.+)(\d+ zł; )(.+)$

zamieńmy na

\2\1\3

W efekcie mamy linie:
10000 zł; 1. Borowiak, Kazimierz; terminowo; kborowiak@example.com
Takie linie możemy już posortować wg wartości liczbowych.

Sortowanie linii według wartości liczbiwych.
Sortowanie linii według wartości liczbiwych.

Możliwy kłopot z sortowaniem

Drobny kłopot: standardowe sortowanie leksykograficzne (czyli według alfabetu) ustawi nam liczby w nieodpowiedniej kolejności, np. 10 przed 9, np.:
1
10
11
2
22
9
Żeby takie sortowanie się udało, liczby muszą być tej samej długości – dopełnione na początku zerami (09 będzie przed 10).
01
02
09
10
11
22

Prawdę mówiąc na szybko nie potrafię podać jednej zamiany, która upora się z wszystkimi przypadkami! Ale można zastosować tę samą zamianę kilka razy, aż przestaniemy widzieć jakiekolwiek zmiany. Załóżmy, że chcemy, żeby wszystkie liczby ostatecznie zajmowały 10 cyfr.

Możemy wtedy zamieniać każdą liczbę na początku linii, która ma mniej niż 10 cyfr:

^(\d{1,9} )

na tę samą liczbę (grupa przechwytująca!) poprzedzoną zerem:

0\1

Kiedy zapis liczby osiągnie długość 10 znaków, wzorzec przestanie się dopasowywać.

Na koniec wreszcie poprawnie sortujemy – i już możemy rozsyłać zaproszenia.

Trwało do trochę krócej niż całą noc, prawda?

Średnio zaawansowane

O wyrażeniach regularnych. Podstępna różnica pomiędzy find i matches

5 komentarzy

Wyrażenia regularne to jedno z zagadnień dzielących programistów. Są tacy, którzy je uwielbiają i ci, którzy szczerze ich nienawidzą.

Sama zaliczam się do pierwszej grupy, być może z powodu upodobań lingwistycznych (wyrażenia regularne ≈  języki regularne ≈ automaty skończone). Wyrażenia regularne pozwalają na bardzo zwięzły i precyzyjny zapis warunków wyszukiwania, które – gdyby ograniczyć się do tradycyjnych konstrukcji zawartych w danym języku programowania – mogłyby zająć wiele linii. Po stronie minusów należy zapisać trudność zrozumienia dłuższych wyrażeń regularnych, zwłaszcza, jeśli są dziełem kogoś innego.

W tym wpisie chcę podzielić się swoją niedawną przygodą optymalizacyjną. W najbliższym czasie (czyli przed końcem roku) wrzucę jeszcze stary tekst o pułapkach, w które można wpaść pisząc wyrażenia regularne w Javie oraz nowy o tym, jak regeksy mogą przydać się nieprogramistom w ich codziennych zadaniach.

Do rzeczy.

Napisałam ostatnio kod analizujący treść stron internetowych. Mniejsza z tym, po co to robił. Stanowił część większej całości (moduł mavenowy) i podobnie jak reszta kodu korzystał m.in. z Javy 8 i biblioteki JSoup. Napisałam masę testów jednostkowych, testowałam na kilkuset stronach… Jednak prawdziwa próba ognia miała nadejść kilka dni po oddaniu przeze mnie projektu, podczas uruchomienia pełnego łańcucha przetwarzania na kilkudziesięciu (kilkuset?) tysiącach stron.

W pięciu przypadkach mój kod zawiesił się na ponad dobę.

Naprawa, kiedy już do niej zasiadłam zajęła mi niecałą godzinę. Co się okazało? W kilku miejscach w moim kodzie użyłam metody Element::getElementsByAttributeValueMatching i dałam się zwieść nazwie. Na swoją obronę mam to, że Javadoc też wprowadza w błąd. Otóż wyobraziłam sobie, że gdzieś w głębinach metoda wywołuje metodę Matcher::matches, dlatego szukany przeze mnie fragment otoczyłam znakami ".*" przed i po właściwym wzorcu.

Skoro już wszystko się zapętliło, zajrzałam do środka, a tam:

Podstawowa różnica pomiędzy wspomnianą już Matcher::matches a Matcher::find jest taka, że matches szuka pełnych dopasowań (cały łańcuch znaków musi pasować do wzorca), a find zadowoli się dopasowaniem w środku łańcucha znaków (i może takich dopasowań zwrócić wiele).

Czyli jeśli nasz wzorzec ma postać "[abc]e", to find dopasuje go do łańcucha "cel", w przeciwieństwie do metody matches:

Jeśli dodam na początku i na końcu wzorca uniwersalne symbole ".*" (uzyskując ".*[abc]e.*") to również metoda matches uzna, że mamy dopasowanie:

Jednak jednak użyjemy metody find przy odpowiednio złożonym i zagnieżdzonym wyrażeniu regularnym z opcjonalnymi elementami i przy odpowiednio długim tekście, pojawi się tyle możliwości dopasowania wyrażenia do łańcucha znaków, że wejdziemy na obszar tzw. Catastrophic Backtracking (katastrofalne nawracanie?).

Moja poprawka sprowadziła się, oczywiście, do usunięcia czterech znaków: ".*" z początku i końca wyrażenia przekazanego jako argument metodzie Element::getElementsByAttributeValueMatching.

Jaka z tego nauczka? Rutynowo zaglądać w cudzy kod, niestety.

PS. Polecam krzyżówki regeksowe: Regex Crossword.

Tajemne szyfry (zaawansowane)

Odkrywam nową Javę przy okazji dat

3 komentarze

Przyznaję, że ten wpis jest nieco wymuszony. Zasady Daj się poznać nakładają na mnie obowiązek wrzucania dwóch postów konkursowych tygodniowo. Tymczasem, choć informatycznie działo się u mnie sporo, projekt konkursowy w tym tygodniu leżał odłogiem. Dlaczego? Pomijając już przygody z nadgarstkiem – rozpoczęłam studia podyplomowe (przetwarzanie danych – big data)!  Wczoraj, na moim dawnym wydziale, bawiłam się SQL-em, dzisiaj R. O R mam nawet anegdotę, ale na razie nie wymyśliłam pretekstu, żeby podciągnąć ją pod temat konkursowy.

Jeśli chodzi o moją aplikację Szafbook: nadal gnębi mnie kwestia dat. Pisałam już o tym, że HTML5 udostępnia pole wejściowe input typu date.  Niektóre przeglądarki (Chrome!) wyświetlają przy nim elegancki widżet do wyboru daty z kalendarza. Inne nadal pozwalają/nakazują użytkownikowi samodzielne wpisanie wartości.

Nie byłam pewna, co z tym zrobić. Nie chcę rozbijać daty urodzenia na trzy osobne pola – za bardzo podoba mi się rozwiązanie z Chrome. Nie chcę wykrywać przeglądarki i podejmować decyzji w zależności od niej. Tak długo, jak będzie to możliwe, chcę się trzymać z dala od JavaScriptu.

Co tymczasowo wymyśliłam? Własny sposób tworzenia obiektu reprezentującego datę na podstawie danych wprowadzonych przez użytkownika, w  którym pozwalam użytkownikowi na nieco większą elastyczność niż trzymanie się jednego sztywnego formatu daty.

Kod i uwagi do niego wklejam poniżej. Przy okazji zauważyłam kilka nowych (dla mnie) rzeczy w Javie. Najbardziej spodobały mi się grupy nazwane w wyrażeniach regularnych, wprowadzone w Javie 7.  Dzięki ich istnieniu mogę wyciągnąć rok, miesiąc i dzień z tekstu dopasowanego do jednego z dwóch różnych wyrażeń regularnych. Bez nazw miałabym z tym większy problem, ponieważ numery grup (których trzeba było używać wcześniej) nie zgadzałyby się ze sobą (rok to grupa 1 w pierwszym wzorcu i grupa 3 w drugim).

W ogóle lubię wyrażenia regularne! 🙂 Na poprzednim blogu pojawił się kiedyś wpis o pułapkach regeksowych w Javie. Chyba przypomnę go w przyszłym tygodniu.

  • 8. Użycie mojego własnego kodu do zamiany wartości tekstowej na typ Calendar.
  • 17 i 18: Wyrażenia regularne mają umożliwić akceptację dat takich jak: 2016-04-10, 2016.04.10, 04/10/2014. Każde z wyrażeń definiuje 3 grupy nazwane: year, month oraz day.
  • 39-41: Odwołuję się do grup, które są obecne niezależnie od tego, który z dwóch wzorców zadziałał.
  • 43: Dość lekkie testy poprawności daty dopasowanej do wzorca. Zajrzałam do implementacji kalendarza. Podanie nieistniejącego dnia miesiąca nie powinno spowodować rzucenia wyjątku. Jeśli użytkownik będzie uparcie twierdził, że urodził się 30 lutego… Mało mnie interesuje, jaką datę ustawi mu system.
  • 45: Ustawiam odpowiednią datę w moim kalendarzu. Początkowo chciałam mieć w tym miejscu obiekt typu Date, ale zorientowałam się, że tworzenie instancji Date w oparciu o rok, miesiąc i dzień od dawna nie jest zalecane.

Na koniec pozdrawiam z Warszawy! Przyjechałam z całą rodziną na konferencję 4Developers.