Walidacja wszerz

Dzisiaj będzie trochę algorytmicznie :) Zajmowanie się programowaniem grafiki i konstruowaniem silnika jest oczywiście satysfakcjonujące, ale programowanie to przecież nie tylko tworzenie, lecz także rozwiązywanie problemów. Dlatego czasami dobrze jest sobie jakiś problem wynaleźć i go rozwiązać :D

Dzisiejszy wprawdzie nie wziął się znikąd, jako że wynalazłem go już jakiś czas temu przeglądając część mojej biblioteki zajmującą się operacjami na łańcuchach. Zagadnienie dotyczy zaś sprawy dość przydatnej i nie tak znowu trywialnej.
Chodzi tu tzw. filtry wildcards. Jest to bardzo znany (zwłaszcza w Windows) sposób zapisywania szablonów nazw plików, przydatny zwłaszcza przy wyszukiwaniu. Jego reguły są bardzo proste: w filtrze mogą występować w dowolnej ilości dwa znaki specjalne:

• gwiazdka (*), która symbolizuje dowolny ciąg znaków (także pusty)
• znak zapytania (?), który symbolizuje dokładnie jeden dowolny znak

Oprócz tego szablon może też zawierać dowolne inne znaki, które muszą być dopasowane dosłownie. Typowe “plikowe” przykłady takich szablonów to:

• *.exe – pasuje do wszystkich nazw plików wykonywalnych (z rozszerzeniem EXE)
• file????.tmp – pasuje do file0000.tmp, file0001.tmp, ale też fileqwer.tmp, itd.
• *.? – pasuje do wszystkich nazw plików z jednoliterowym rozszerzeniem

Wildcards (swoją drogą, ciekawa nazwa – ktoś zna jej pochodzenie?) stały się na tyle popularne, że rozpoznaje je także większość wyszukiwarek internetowych. Są bowiem całkiem elastyczne, a o wiele prostsze od wyrażeń regularnych.

Jaki więc problem jest z nimi związany? Chodzi po prostu o sprawdzenie, czy podany ciąg znaków pasuje do podanego wzorca wildcards. Na pierwszy rzut oka może wydawać się to proste – niby wystarczy szukać kolejnych “części stałych” i sprawdzać, czy odstępy między nimi są odpowiednio duże. Ten algorytm jest jednak niepoprawny, bowiem czasami znaki sprawdzanego tekstu musimy traktować na różne sposoby. Przykładowo dla szablonu “a*ba” ciąg “ababa” będzie uznany za niepoprawny, gdyż algorytm dopasuje pierwsze “ba” z tekstu do “ba” zapisanego na sztywno we wzorcu zamiast potraktować je jako dowolny ciąg pasujący do gwiazdki.
Poprawne rozwiązanie musi sprawdzać wszystkie możliwe dopasowania – w tym przypadku oba wystąpienia ciągów “ba”. W swoim algorytmie dla poprawienia efektywności zastosowałem jeszcze wstępne przetwarzanie, dzielące wzorzec na fragmenty – czyli części stałe – oraz zakresy – sekwencje znaków * i ?. Samo sprawdzanie polega natomiast na znajdowaniu wszystkich wystąpień fragmentów, które są w odpowiedniej odległości od siebie (wyznaczanej przez zakresy) i dodawaniu ich do kolejki. Potem są one pobieranie i używane do znalezienia dopasowań następnego fragmentu.
Zasadniczo jest to bardzo podobne do przeszukiwania wszerz wyimaginowanego “grafu dopasowań”. Swoją drogą to ciekawe, że szkielet tego algorytmu grafowego może być użyty do tak wielu rzeczy (jak np. wyszukiwanie najkrótszej drogi między dwoma miastami (algorytm Djikstry) czy szukanie węzłów XML pasujących do wyrażenia XPath). Tak jest oczywiście dlatego, że w tych problemach zawsze wchodzi w grę jakiś mniej lub bardziej intuicyjny graf, tyle że w większości wypadków zastanawianie się nad tym, jak on wygląda, nie ma zbytniego sensu. A tak przy okazji, to w moim algorytmie wildcards można by zmienić kolejkę na stos i wszystko byłoby OK – wtedy mielibyśmy po prostu coś w stylu przeszukiwania wgłąb.

Hmm… wyszedł z tego trochę przydługi miniwykładzik ;) Pozwolę sobie jednak nie kończyć go nieodzowną kwestią “Czy są jakieś pytania” – załóżmy po prostu optymistycznie, że pytań nie stwierdzono ;)