Pasujące symbole wieloznaczne — Matching wildcards

W informatyce algorytm dopasowywania symboli wieloznacznych (znany również jako globbing ) 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łoki Bourne'a lub wiersza poleceń Microsoft Windows lub edytora tekstu lub menedżera plików, a także interfejsy niektórych wyszukiwarek i baz danych. Dopasowywanie symboli wieloznacznych to podzbiór problemu dopasowywania wyrażeń regularnych i ogólnie dopasowywania ciągów .

Problem

Dopasowywanie symboli wieloznacznych testuje wzorzec wieloznaczny 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 być oparty na dowolnej powszechnej składni (patrz globbing ), ale programiści Windows zwykle omawiają tylko uproszczoną składnię obsługiwaną przez natywne środowisko wykonawcze C:

Nie zdefiniowano znaków ucieczki
Symbole wieloznaczne: ?dopasowuje dokładnie jedno wystąpienie 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 zaznaczono inaczej.

Definicja

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

{\ Displaystyle {\ zacząć {wyrównany} m_ {00} i = (p_ {0}= t_ {0}) \ \ m_ {0j} i = (p_ {j-1} = {\ tekst {'*'} })\land m_{0,j-1}\\m_{i0}&={\text{false}}\\m_{ij}&={\begin{case}m_{i-1,j-1 }&{\text{for}}\;p_{i-1}=t_{j-1}\lor p_{i-1}={\text{'?'}}\\m_{i,j- 1}\lub m_{i-1,j}&{\text{for}}\;p_{i-1}={\text{'*'}}\\{\text{false}}&{\ text{for}}\;p_{i-1}\neq t_{j-1}\end{cases}}&&\quad {\text{for}}\;1\leq i\leq |p|,1 \leq j\leq |t|.\end{wyrównany}}}

gdzie m _ij jest wynikiem dopasowania wzorca p do tekstu t skróconego odpowiednio przy znakach i i j . Jest to sformułowanie używane przez algorytm Richtera i algorytm Snippets znaleziony w kolekcji Cantatore. Ten opis jest podobny do odległości Levenshteina .

Powiązane problemy

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

Dopasowywanie wzorców za pomocą nie przejmuje się ani lukami, wyszukiwaniem niezakotwiczonych ciągów tylko z odpowiednikiem ?zdefiniowanego.
Dopasowywanie wzorców za pomocą symboli wieloznacznych, wyszukiwanie niezakotwiczonych ciągów ze zdefiniowanymi odpowiednikami obu symboli wieloznacznych. Ma wykładnicze środowisko wykonawcze, chyba że w dopasowaniu wzorca z elastycznym wariantem symboli wieloznacznych podano ograniczenie długości.

Historia

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

Wśród algorytmów zarówno rekurencyjnych, jak i nierekurencyjnych, strategie wykonywania operacji dopasowywania wzorców różnią się znacznie, czego dowodem jest 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 niektórych algorytmach, szczególnie tych opracowanych przez krytyków algorytmów rekurencyjnych.

Algorytmy rekurencyjne

Rekurencja zwykle ma miejsce *podczas dopasowywania, gdy istnieje więcej sufiksów do dopasowania. Jest to forma wycofywania się , również wykonywana przez niektóre dopasowania wyrażeń regularnych.

Rich Salz ' wildmat algorytm (SH jak składni)
Algorytm Filipa i algorytm Vignesha Murugesana
Algorytm Martina Richtera (identyczny jak Snippets i powiązany z algorytmem 7-zip)
Implementacje fnmatch biblioteki C (wsparcie [...]i zestawy znaków wielobajtowych):
- Fnmatch BSD libc Guido van Rossuma , także część biblioteki Apple libc
- Glibc fnmatch

Ogólna forma tych algorytmów jest taka sama. W przypadku rekursji algorytm dzieli dane wejściowe na podciągi i uważa, że dopasowanie miało miejsce, gdy JEDEN z podciągów zwraca dodatni wynik. Bo dowild("*X", "abcX")chciwie wzywał dowild("X", "abcX"), dowild("X", "bcX"), dowild("X", "cX")i dowild("X", "X"). Zwykle różnią się one mniej ważnymi rzeczami, takimi jak obsługa funkcji i ważniejszymi czynnikami, takimi jak drobne, ale bardzo skuteczne optymalizacje. Niektóre z nich to:

Sygnał ABORT przeciwko nadmiernej rekurencji (Lars Mathiesen 1991). Chociaż poprawne jest naiwne rekursyzowanie przez całą resztę ciągów (wzór i tekst) *i upewnienie się, że JEDEN z podciągów zwraca pozytywne dopasowanie, czas działania staje się wykładniczy dla odrzucenia dopasowania z wieloma *w tekście. Lars Mathiesen zmienia zwrot na trzy klasy, dopasowanie, brak dopasowania i PRZERWIJ (w ogóle niemożliwe dopasowanie w przypadku rekursji gwiazdki). Wartość PRZERWIJ jest zwracana, gdy tekst jest zużywany zbyt wcześnie lub gdy inne dopasowanie gwiazdki nie powiodło się, gwarantując wydajność liniowa w odniesieniu do liczby gwiazdek. (Całkowita złożoność jest dodatkowo kwadratowa do liczby znaków pozostałych do dopasowania.) Wildmatch ABORT w Git/Rsync obejmuje również nieprawidłowe dane wejściowe. Nowy uwildmat INN robi to samo.
Zaawansowanie gwiazdką w rekurencji. Ta modyfikacja Wildmatchu jest stosunkowo mniejsza. Dotyczy to sytuacji, gdy rekursja chce dopasować „*X” do „abcX”: gdy po gwiazdki następuje literał „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. Na * powraca do zwiększania jednego z indeksów, zgodnie z dynamicznym programowaniem sformułowania problemu. Stosuje się do niej również technika „PRZERWIJ”. W typowych wzorcach (testowanych przez Cantatore) jest wolniejszy niż implementacje greedy-call.

Algorytmy rekurencyjne są generalnie łatwiejsze do zrozumienia, a po modyfikacji ABORT działają w sposób akceptowalny pod względem złożoności najgorszego przypadku. W przypadku ciągów bez *, dopasowanie rozmiaru liniowego do rozmiaru ciągu zajmuje czas, ponieważ istnieje stała relacja jeden do jednego.

Algorytmy nierekurencyjne

Krytycy algorytmów rekurencyjnych opracowują następujące rozwiązania:

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

Następujące nie jest:

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

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

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 firmy Russ Cox można lekko zmodyfikować pod kątem takich. Oparty na BDM algorytm nrgrep Gustavo Navarro zapewnia bardziej uproszczoną implementację z naciskiem na wydajne przyrostki. Zobacz także wyrażenia regularne § implementacje .

Languages

In other projects