Passende Platzhalter - Matching wildcards

In der Informatik ist ein Algorithmus zum Abgleichen von Platzhaltern (auch als Globbing bekannt ) beim Vergleichen von Textzeichenfolgen nützlich, die Platzhaltersyntax enthalten können . Häufige Anwendungen dieser Algorithmen sind Befehlszeilenschnittstellen , zB die Bourne-Shell oder Microsoft Windows- Befehlszeilen- oder Texteditor oder Dateimanager, sowie die Schnittstellen für einige Suchmaschinen und Datenbanken. Wildcard-Matching ist eine Teilmenge des Problems des Matchings von regulären Ausdrücken und String-Matching im Allgemeinen.

Das Problem

Ein Wildcard-Matcher testet ein Wildcard-Muster p gegen eine Eingabezeichenfolge s . Es führt einen verankerten Match durch und gibt nur true zurück, wenn p mit der Gesamtheit von s übereinstimmt .

Das Muster kann auf jeder gängigen Syntax basieren (siehe globbing ), aber unter Windows neigen Programmierer dazu, nur eine vereinfachte Syntax zu diskutieren, die von der nativen C-Laufzeit unterstützt wird:

  • Es sind keine Escape-Zeichen definiert
  • Platzhalter: ?entspricht genau einem Vorkommen eines beliebigen Zeichens. *stimmt mit beliebig vielen (einschließlich null) Vorkommen eines beliebigen Zeichens überein.

Dieser Artikel behandelt hauptsächlich die Windows-Formulierung des Problems, sofern nicht anders angegeben.

Definition

In nullbasierten Indizes ausgedrückt, kann das Wildcard-Matching-Problem rekursiv definiert werden als:

wobei m ij das Ergebnis des Vergleichens des Musters p mit dem Text t ist, der auf i bzw. j Zeichen abgeschnitten ist . Dies ist die Formulierung, die von Richters Algorithmus und dem Snippets- Algorithmus in Cantatores Sammlung verwendet wird. Diese Beschreibung ähnelt der Levenshtein-Distanz .

Verwandte Probleme

Direkt damit verbundene Probleme in der Informatik sind:

  • Pattern-Matching mit Don't Cares oder Lücken, eine nicht verankerte String-Suche mit nur dem Äquivalent von ?definiert.
  • Mustervergleich mit Wildcards, eine nicht verankerte String-Suche mit dem Äquivalent beider definierter Wildcards. Hat eine exponentielle Laufzeit, es sei denn, in der Variante Mustervergleich mit flexiblen Platzhaltern ist eine Längenbegrenzung angegeben.

Geschichte

Frühe Algorithmen zum Abgleichen von Platzhaltern beruhten oft auf Rekursion , aber die Technik wurde aus Gründen der Leistung und Zuverlässigkeit kritisiert. Nicht-rekursive Algorithmen zum Abgleichen von Wildcards haben angesichts dieser Überlegungen an Popularität gewonnen.

Sowohl bei rekursiven als auch bei nicht-rekursiven Algorithmen variieren die Strategien zum Durchführen der Mustervergleichsoperation stark, wie aus der Vielzahl von Beispielalgorithmen ersichtlich, auf die unten Bezug genommen wird. Testfallentwicklung und Leistungsoptimierungstechniken wurden nachweislich auf bestimmte Algorithmen angewendet, insbesondere auf diejenigen, die von Kritikern der rekursiven Algorithmen entwickelt wurden.

Rekursive Algorithmen

Die Rekursion erfolgt im Allgemeinen beim Abgleichen, *wenn mehr Suffixe zum Abgleichen vorhanden sind. Dies ist eine Form des Backtrackings , die auch von einigen Matchern für reguläre Ausdrücke durchgeführt wird.

  • Rich Salzes ' wildmat Algorithmus (sh-ähnliche Syntax)
  • Filips Algorithmus und Vignesh Murugesans Algorithmus
  • Martin Richters Algorithmus (identisch mit Snippets und verwandt mit dem 7-Zip-Algorithmus)
  • Fnmatch- Implementierungen der C-Bibliothek (unterstützt [...]und Multibyte-Zeichensätze):

Die allgemeine Form dieser Algorithmen ist dieselbe. Bei der Rekursion zerlegt der Algorithmus die Eingabe in Teilzeichenfolgen und betrachtet eine Übereinstimmung als aufgetreten, wenn EINE der Teilzeichenfolgen eine positive Übereinstimmung zurückgibt. Denn dowild("*X", "abcX")es würde gierig rufen dowild("X", "abcX"), dowild("X", "bcX"), dowild("X", "cX")und dowild("X", "X"). Sie unterscheiden sich in der Regel durch weniger wichtige Dinge wie die Unterstützung von Funktionen und durch wichtigere Faktoren wie kleinere, aber sehr effektive Optimierungen. Einige von ihnen umfassen:

  • Das ABORT-Signal gegen Überrekursion (Lars Mathiesen 1991). Während es richtig ist, den gesamten Rest der Strings (Muster und Text) naiv zu wiederholen *und sicherzustellen, dass EINE der Teilstrings eine positive Übereinstimmung zurückgibt , wird die Laufzeit exponentiell, wenn eine Übereinstimmung mit vielen *im Text abgelehnt wird . Lars Mathiesen ändert die Rückgabe in drei Klassen, Match, No-Match und ABORT (bei Sternrekursion überhaupt kein Match möglich). Der ABORT-Wert wird zurückgegeben, wenn der Text zu früh verbraucht wird oder ein anderer Stern-Match fehlgeschlagen ist lineare Leistung in Bezug auf die Anzahl der Sternchen. (Die Gesamtkomplexität ist zusätzlich quadratisch zur Anzahl der verbleibenden Zeichen.) Der Wildmatch ABORT von Git/Rsync deckt auch ungültige Eingaben ab. Der neue INN uwildmat macht das Gleiche.
  • Asterisk-Fortschritt in der Rekursion. Diese Wildmatch-Optimierung ist relativ geringfügiger. Dies gilt für den Fall, dass die Rekursion "*X" auf "abcX" abgleichen möchte: Wenn auf ein Asterisk ein Literal wie "X" folgt, ist es offensichtlich, dass nur der letzte Vergleich mit gleicher Länge eine Chance auf eine Übereinstimmung haben würde . Dies ist früher in uwildmat im Jahr 2000 und impliziter in van Rossums fnmatch für zu sehen FNM_PATHNAME.

Der Algorithmus von Martin Richter ist eine Ausnahme von diesem Muster, obwohl die Gesamtoperation äquivalent ist. Ein * es recurses in zunehmenden entweder der Indizes nach der dynamischen Programmierung Formulierung des Problems. Die Technik "ABORT" ist auch darauf anwendbar. Bei typischen Mustern (wie von Cantatore getestet) ist es langsamer als die gierigen Aufruf-Implementierungen.

Die rekursiven Algorithmen sind im Allgemeinen leichter nachvollziehbar und mit der ABORT-Modifikation verhalten sie sich in Bezug auf die Worst-Case-Komplexität akzeptabel. Bei Zeichenfolgen ohne * benötigen sie Zeit, um die lineare Zeichenfolgegröße abzugleichen, da es eine feste Eins-zu-Eins-Beziehung gibt.

Nicht-rekursive Algorithmen

Folgendes wird von Kritikern der rekursiven Algorithmen entwickelt:

  • Wildcard-Matching-Algorithmus von Kirk J. Krauss , verwendet von IBM
  • Alessandro Cantatores Sammlung von Wildcard-Matching-Algorithmen
  • Dogan Kurts iterativer Matcher und langsamerer NFA-Matcher.
  • Silers falscher Algorithmus (fehlt MATCH("da*da*da*", "daaadabadmanda"))

Folgendes ist nicht:

  • Jack Handys falscher Algorithmus (fehlt MATCH("*?", "xx"))

Die obigen iterativen Funktionen implementieren Backtracking, indem sie einen alten Satz von Muster-/Textzeigern speichern und darauf zurückgreifen, falls eine Übereinstimmung fehlschlägt. Da nur ein erfolgreiches Match erforderlich ist, muss laut Kurt nur ein solcher Satz gespeichert werden.

Darüber hinaus kann das Problem des Wildcard - Matching umgewandelt wird in regulären Ausdruck Anpassung eines naiven mit Text-Ersatz Ansatz . Obwohl nicht-rekursive Matcher für reguläre Ausdrücke wie die von Thompsons Konstruktion in der Praxis aufgrund fehlender Unterstützung für Rückverweise weniger verwendet werden, bietet der Wildcard-Matching im Allgemeinen keine ähnlich umfangreichen Funktionen. (Tatsächlich unterstützen viele der oben genannten Algorithmen nur ?und *.) Die Russ Cox-Implementierung von Thompson NFA kann für solche trivial modifiziert werden. Der BDM- basierte nrgrep-Algorithmus von Gustavo Navarro bietet eine optimierte Implementierung mit Schwerpunkt auf effizienten Suffixen. Siehe auch §-Implementierungen für reguläre Ausdrücke .

Siehe auch

Verweise