Pasujące symbole wieloznaczne

W informatyce algorytm dopasowywania symboli wieloznacznych (znany również jako globowanie ) jest przydatny do porównywania ciągów tekstowych, które mogą zawierać składnię symboli wieloznacznych . Typowe zastosowania tych algorytmów obejmują interfejsy wiersza poleceń , np. powłoka Bourne'a lub wiersz poleceń systemu Microsoft Windows , edytor tekstu lub menedżer plików, a także interfejsy niektórych wyszukiwarek i baz danych. Dopasowywanie symboli wieloznacznych jest podzbiorem problemu dopasowywania wyrażeń regularnych i dopasowywania ciągów znaków ogólnie.

Problem

Funkcja dopasowywania symboli wieloznacznych sprawdza wzorzec symboli wieloznacznych p względem ciągu wejściowego s . Wykonuje zakotwiczone dopasowanie, zwraca true tylko wtedy, gdy p pasuje do całości s .

Wzorzec może opierać się na dowolnej wspólnej składni (zobacz globbing ), ale w systemie Windows programiści mają tendencję do omawiania tylko uproszczonej składni obsługiwanej przez natywne środowisko wykonawcze C:

Nie zdefiniowano znaków ucieczki
Symbole wieloznaczne: ? pasuje dokładnie do jednego wystąpienia dowolnego znaku. * dopasowuje dowolną liczbę (w tym zero) wystąpień dowolnego znaku.

W tym artykule omówiono głównie sformułowanie problemu w systemie Windows, chyba że określono inaczej.

Definicja

Wyrażony w indeksach od zera problem dopasowywania symboli wieloznacznych można zdefiniować rekurencyjnie jako:

{\ Displaystyle {\ rozpocząć {wyrównane} m_ {00} & = (p_ {0} = t_ {0}) \\ m_ {0j} & = (p_ {j-1} = {\ tekst {'*'} })\land m_{0,j-1}\\m_{i0}&={\text{false}}\\m_{ij}&={\begin{przypadki}m_{i-1,j-1 }&{\text{for}}\;p_{i-1}=t_{j-1}\lor p_{i-1}={\text{'?'}}\\m_{i,j- 1}\lor m_{i-1,j}&{\text{for}}\;p_{i-1}={\text{'*'}}\\{\text{fałsz}}&{\ text{for}}\;p_{i-1}\neq t_{j-1}\end{przypadki}}&&\quad {\text{for}}\;1\równoważnik i\równik |p|,1 \leq j\leq |t|.\end{wyrównane}}}

gdzie m _ij jest wynikiem dopasowania wzorca p do tekstu t obciętego odpowiednio o znaki i i j . Jest to sformułowanie używane przez algorytm Richtera i Snippets znaleziony w kolekcji Cantatore'a. Ten opis jest podobny do odległości Levenshteina .

Powiązane problemy

Bezpośrednio związane problemy w informatyce obejmują:

Dopasowywanie wzorców za pomocą not cares lub gaps, niezakotwiczone wyszukiwanie ciągów z odpowiednikiem ? zdefiniowane.
Dopasowywanie wzorców za pomocą symboli wieloznacznych, niezakotwiczone wyszukiwanie ciągów ze zdefiniowanym odpowiednikiem obu symboli wieloznacznych. Ma wykładniczy czas wykonywania, chyba że w wariancie dopasowywania wzorców z elastycznymi symbolami wieloznacznymi podano ograniczenie długości.

Historia

Wczesne algorytmy dopasowywania symboli wieloznacznych często opierały się na rekurencji , ale technika ta była krytykowana ze względu na wydajność i niezawodność. W świetle tych rozważań przychylność zyskały nierekurencyjne algorytmy dopasowywania symboli wieloznacznych.

Wśród algorytmów rekurencyjnych i nierekurencyjnych strategie wykonywania operacji dopasowywania wzorców są bardzo zróżnicowane, o czym świadczy różnorodność przykładowych algorytmów, o których mowa poniżej. Techniki opracowywania przypadków testowych i optymalizacji wydajności zostały wyraźnie zastosowane w przypadku niektórych algorytmów, szczególnie tych opracowanych przez krytyków algorytmów rekurencyjnych.

Algorytmy rekurencyjne

Rekurencja zwykle ma miejsce przy dopasowywaniu * , gdy jest więcej sufiksów do dopasowania. Jest to forma cofania się , wykonywana również przez niektóre programy dopasowujące wyrażenia regularne.

Wildmat Richa Salza ( składnia podobna do sh)
Algorytm Filipa i algorytm Vignesha Murugesana
Algorytm Martina Richtera (identyczny z Snippets i powiązany z algorytmem 7-zip)
biblioteki C fnmatch (obsługuje [...] i wielobajtowe zestawy znaków):
- BSD libc fnmatch Guido van Rossuma , również część Apple libc
- Glibc fnmatch

Ogólna postać tych algorytmów jest taka sama. Podczas rekurencji algorytm dzieli dane wejściowe na podciągi i uznaje, że dopasowanie nastąpiło, gdy JEDEN z podciągów zwróci dodatnie dopasowanie. W przypadku dowild("*X", "abcX") chciwie wywołałoby to dowild("X", "abcX") , dowild("X", "bcX") , dowild("X", "cX") i dowild("X", "X") . Zwykle różnią się mniej ważnymi rzeczami, takimi jak obsługa funkcji, i ważniejszymi czynnikami, takimi jak drobne, ale bardzo skuteczne optymalizacje. Niektóre z nich obejmują:

Sygnał ABORT przeciw nadmiernej rekurencji (Lars Mathiesen 1991). Chociaż poprawne jest naiwne rekursowanie przez całą resztę ciągów (wzorzec i tekst) na * i upewnienie się, że JEDEN z podciągów zwraca dodatnie dopasowanie, czas działania staje się wykładniczy w przypadku odrzucenia dopasowania z wieloma * w tekście. Lars Mathiesen zmienia metodę powrotu na trzy klasy: dopasowanie, brak dopasowania i ABORT (w przypadku rekurencji z gwiazdką żadne dopasowanie nie jest możliwe). Wartość ABORT jest zwracana, gdy tekst zostanie zużyty zbyt wcześnie lub gdy inne dopasowanie z gwiazdką się nie powiedzie, co gwarantuje wydajność liniowa w odniesieniu do liczby gwiazdek. (Ogólna złożoność jest dodatkowo kwadratowa w stosunku do liczby znaków pozostałych do dopasowania.) Dopasowanie ABORT Git/Rsync obejmuje również nieprawidłowe dane wejściowe. Nowy uwildmat INN robi to samo.
Postęp gwiazdki w rekurencji. Ta poprawka Wildmatch jest stosunkowo mniejsza. Dotyczy to sytuacji, gdy rekurencja chce dopasować „*X” do „abcX”: gdy po gwiazdce następuje literał taki jak „X”, oczywiste jest, że tylko ostatnie porównanie o równych długościach miałoby szansę na uzyskanie dopasowania . Widać to wcześniej w uwildmat w 2000 roku i bardziej pośrednio w fnmatch van Rossuma dla FNM_PATHNAME .

Algorytm Martina Richtera jest wyjątkiem od tego wzorca, chociaż ogólna operacja jest równoważna. On * powraca do zwiększania jednego z indeksów, zgodnie z dynamicznym sformułowaniem problemu. Technika „ABORT” ma również zastosowanie do tego. Na typowych wzorcach (testowanych przez Cantatore) jest wolniejszy niż implementacje zachłannego wywołania.

Algorytmy rekurencyjne są generalnie łatwiejsze do uzasadnienia, a po modyfikacji ABORT działają akceptowalnie pod względem złożoności najgorszego przypadku. Na ciągach znaków bez * dopasowanie zajmuje czas liniowy do rozmiaru łańcucha, ponieważ istnieje stała relacja jeden do jednego.

Algorytmy nierekurencyjne

Krytycy algorytmów rekurencyjnych opracowali:

Algorytm dopasowywania symboli wieloznacznych Kirka J. Kraussa , używany przez IBM
Zbiór algorytmów dopasowywania symboli wieloznacznych Alessandro Cantatore
Iteracyjny matcher Dogana Kurta i wolniejszy matcher NFA.
Niepoprawny algorytm Silera (nie powiodło się MATCH("da*da*da*", "daaadabadmanda") )

Poniższe nie jest:

Niepoprawny algorytm Jacka Handy'ego (nie powiodło się MATCH("*?", "xx") )

Powyższe funkcje iteracyjne implementują cofanie się, zapisując stary zestaw wskaźników wzorca/tekstu i powracając do niego, jeśli dopasowanie się nie powiedzie. Według Kurta, ponieważ wymagany jest tylko jeden udany mecz, tylko jeden taki zestaw musi zostać zapisany.

Ponadto problem dopasowywania symboli wieloznacznych można przekształcić w dopasowywanie wyrażeń regularnych przy użyciu naiwnego podejścia polegającego na zastępowaniu tekstu . Chociaż nierekurencyjne dopasowania wyrażeń regularnych, takie jak konstrukcja Thompsona , są rzadziej używane w praktyce ze względu na brak obsługi odwołań wstecznych, generalnie dopasowywanie symboli wieloznacznych nie ma podobnie bogatego zestawu funkcji. (W rzeczywistości wiele z powyższych algorytmów obsługuje tylko ? i * .) Implementację Thompsona NFA Russa Coxa można w prosty sposób zmodyfikować. BDM Gustavo Navarro Algorytm nrgrep oparty na oprogramowaniu zapewnia bardziej usprawnioną implementację z naciskiem na wydajne sufiksy. Zobacz także wyrażenie regularne § Implementacje .

Zobacz też