Dateimuster-Strings (auch in Kombination) überprüfen und abfragen

Hallo.

Ich habe folgende Problemstellung:

Ich bekommen mehrere Dateimuster vom Benutzer. Zum Beispiel:

1. A*.zip
2. D*.zip
3. DHI*.zip
   ..

Dies Benutzereingaben sollen nun auf Gültigkeit geprüft werden.

1. und 2) wären zusamman gültig, so wie auch 1) und 3).
   Nicht gültig sein soll 2) und 3), da 3) eine Teilmenge von 2) ist.

Kann ich das mit RegEx oder durch andere Mittel abprüfen?
Ich würde nur ungern anfangen den Text selbst zu zerlegen und zu analyseieren.

Jeder Hinweis wird dankend angenommen 😃

Hallo Marcel,

sind alle Muster erlaubt, die man mit den Platzhaltern * und ? überhaupt bilden kann?

Also auch sowas wie X???Y?.z ?

Dann wäre z.B. A*.zip und *Z.zip erlaubt. Die bilden zwar nicht unbedingt Teilmengen voneinander, aber es kann trotzdem sein, dass beiden Muster auf einige Dateien gleichermaßen passen, z.B. auf AZ.zip. Wie soll damit verfahren werden?

Oder geht es dir wirklich nur darum, echt redundante Muster zu finden? Wie in deinem Beispiel, wo DHI*.zip echt redundant zu D*.zip ist.

herbivore

Hallo herbivore.

Dein Beispiel: A*.zip KANN eine Schnittmenge von *Z.zip haben und umgekehrt. Dieser Fall soll ebenfalls nicht erlaubt sein, wenngleich er in der Praxis wohl eher nicht vorkommen wird. Es dürfen also nur Dateimuster zusammen existieren die nicht potenziell kollidieren.

PS: Ja es sollten alle möglichen Muster erlaubt sein. Also alle Kombinationen von * und ?

Hallo Marcel,

Ich würde nur ungern anfangen den Text selbst zu zerlegen und zu analyseieren.

ich glaub, ohne wird es nicht gehen. Ich hab dir zwei Aufgaben aus dem Programmierspiel herausgesucht, die sich mit ähnlichen Themen beschäftigen.

In der ersten Aufgabe (siehe Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch) geht es darum, zu ermitteln, ob ein (klassisches Datei-)Muster auf einen Text (Dateinamen) passt.

In der zweiten Aufgabe (siehe Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch) geht es um ein ähnliches, aber noch etwas komplexeres Matching-Problem.

Ich vermute, deine Lösung wird code-/strukturmäßig ähnlich aufgebaut sein (müssen), wie die im verlinkten Thread ebenfalls zu findenden Lösungen.

Bei dir würde es eben darum gehen zu ermitteln, ob es (mindestens) einen Text gibt, auf den beide Pattern passen. Oder darum, einen solchen Text zu konstruieren. Wenn man einen Algorithmus hat, der verlässlich einen solchen Text konstruiert, wenn es ihn denn gibt, kann man diesen verwenden, um zu testen, ob die Pattern einen Schnittmenge haben/bilden.

herbivore

PS: Wenn du verlangen würdest, dass die Pattern nur nach dem (Meta)Muster AB aufgebaut sind, würde sich deine Aufgabe sehr vereinfachen. Man müsste dann bei A1B1 und A2*B2 nur testen, ob A1 (kein) Substring von A2 ist und umgekehrt und für B1 und B2 genauso.

Hallo herbivore.

Ich hatte soetwas schon befürchtet. Ich habe mich mit meinem Kollegen nochmal kurz geschlossen und wird sind auch der Meinung man müsste immer einen konkreten Text generieren - wie du auch schon sagtest - und diesen dann gegen ein Muster abprüfen. Wobei die zu generierenden Texte dann ja jeglich möglichen Text umfassen würde.

Also bereits ein A*.zip würde eine riesige Liste an möglichen zu prüfenden Texten ergeben..

Aa.zip
Ab.zip
Ac.zip
..
AA.zip
AB.zip
AC.zip
..
A_.zip
A-.zip
A1.zip
A2.zip
A3.zip
..
Aaa.zip
Aab.zip
..

usw..
Wenn ich die Anzahl der möglichen Zeichen auf 26 Buchstaben unseres Alphabetes begrenze, groß und klein Schreibung berücksichtige und zehn Zahlen, dann wäre ich bei 62 Zeichen ohne Sonderzeichen schon irgendwas bei 62 hoch 10 Möglichkeiten einen Text zu generieren, sofern ich mich auf 10 zeichen begrenze.

Wohl weniger performant. Was vielleicht auch der Grund dafür ist warum keine Funktion wie:
Regex.HasIntersect(RegEx regex);
finden konnte.

Ok, ich danke dir für deine Hilfe und die Links. Denke ich werde dann wohl irgendwie die kleine Lösung nutzen müssen..

Hallo Marcel,

Wobei die zu generierenden Texte dann ja jeglich möglichen Text umfassen würde.

nein, so war das nicht gemeint und so würde ich das auch nicht machen. Ich würde eher entlang der beiden Pattern konstruieren. Also immer da, wo feste Zeichen in dem einen Pattern auftauchen, schauen, ob dort im anderen Pattern entweder die gleichen Zeichen stehen oder eben Platzhalter, die für diese Zeichen stehen können. Also im Grunde so wie bei der ersten Programmierspielaufgabe, aber eben nicht mit Pattern und Text, sondern mit zwei Pattern. Man ersetzt also etwas vereinfacht gesagt die Platzhalter aus dem jeweils anderen Pattern gezielt mit den festen Zeichen, aus dem jeweils anderen Pattern. Man konstruiert also den Text, der auf beide passt, wenn es diesen gibt, also ganz gezielt. Das Komplexitätsproblem entsteht also gar nicht. Insbesondere wird der generierte Text kein Zeichen enthalten, das nicht in dem einen oder anderen Pattern auftaucht (außer, wenn * in einen Pattern unausweichlich auf ? im anderen Pattern stößt, aber da nimmt man einfach konstant ein bestimmtes Zeichen, z.B. ein kleines a).

herbivore

Wenn ich dich richtig verstehe, dann würdest du die Muster mergen, sozusagen:

"?ABC*.zip" + "?ABCD*.zip" = "_ABCD.zip" (wenn _ das Füllzeichen für ? wäre)

und das dann gegen die beiden ursprünglichen Muster prüfen. Falls beide matchen, so habe ich eine Schnittmenge.

Mal ein paar Beispiele:

1. "D*.zip" + "D12345*.zip" = "D12345.zip"
2. "." + "BERT?.zip" = "BERT_.zip"
3. "D*.zip" + "*A.zip" = "DA.zip"

Aber was wird aus:

4. "D??A.???" + "D?.???" =

Hallo Marcel,

Wenn ich dich richtig verstehe, dann würdest du die Muster mergen

wenn du es so nennen willst, ja. Allerdings kann das Mergen komplexer werden, als in deinen Beispielen, z.B.

AB.zip und ABC.zip

wobei der Stern von A*B.zip, auf BC (also letztlich BC) passt und nicht die Bs aufeinander, insgesamt ABCB.zip. Aber im Prinzip trotzdem, ja.

Aber was wird aus: 4)

Nichts, denn die Mengen der Muster sind disjunkt, da die einen Dateinamen immer aus genau vier, die anderen immer aus genau zwei Zeichen bestehen.

herbivore

Hallo Marcel,

ich denke, es gibt noch eine einfachere - wenn auch nicht vollkommen triviale - Lösung für dein Problem.

Als Vorverarbeitung normalisiert man so, dass eine beliebige Folge aus sowohl Sternen als auch Fragezeichen durch einen String mit der gleichen Anzahl von Fragezeichen eingerahmt von je einem einzelnen Stern ersetzt wird, z.B. \*?***?*? => \*???*. Außerdem ersetzt man jede Folge von beliebig vielen Stern durch einen einzelnen Stern.

Dann beginnt man von vorne durch beiden Pattern zu laufen. Findet man zwei Zeichen, die nicht aufeinander passen(*), liefert die Methode sofort false. Die Methode liefert ebenfalls sofort false, wenn man am Ende des einen Strings ankommt, aber der andere String nicht ebenfalls endet bzw. mit etwas anderem endet, als einem einzelnen Stern.

(*) Zwei Zeichen passen aufeinander, wenn sie exakt gleich sind, oder mindestens eins von beiden ein Fragezeichen ist.

Ist während der beschrieben Suche mindestens eins der beiden Zeichen ein Stern, merkt man sich die Stelle und beendet die Vorwärtssuche.

Nun sucht man von Ende auf die gleiche Weise von hinten nach vorne, solange die Zeichen passen(*) (sonst sofortiger Abbruch mit false) oder man auf mindestens einen Stern stößt.

Man hat sich also jetzt vorwärts und rückwärts an das aus der jeweiligen Richtung erste Auftreten eines Sterns rangerobbt. Man hat also den entscheidenden Kern der Pattern eingegrenzt.

Dabei kann der vordere und und der hintere Stern jeweils nur im ersten oder nur im zweiten oder gleichzeitig in beiden (Kern-)Pattern auftreten.

Wenn in einem der beiden Kern-Pattern ein Stern vorne ist und im anderen hinten, liefert die Methode true.(**) Wenn beide Kern-Pattern mit einem Stern beginnen, reicht es, wenn sich in einem der der beiden Pattern auch hinten ein Stern befindet.

Bleibt der Fall, dass beide Sterne nur im ersten Kern-Pattern oder beide Sterne nur im zweiten Kern-Pattern sind. Jetzt muss man wieder unterscheiden.

Besitzt der andere Kern-Pattern mindestens einen Stern im inneren, liefert die Methode true.

Tut er das nicht, dann ist dieser Kern-Pattern bis auf etwaige Fragezeichen einfacher Text und kann mit der minimal abgeänderten Methode aus dem Programmierspiel aus einen Match gegen den anderen Kern-Pattern getestet werden. Die eigentliche Methode liefert dann das Ergebnis dieser Prüfung zurück.

Es gibt sicher noch ein paar Spezialitäten, die ich übersehen habe, aber das Grundprinzip sollte hinhauen.

Der Gag an dem beschriebenen Vorgehen ist, dass es vollkommen egal ist, an wie vielen verschiedenen Stellen die Pattern Sterne enthalten. Die Prüfung hebt (bis auf eine einzige genannte Ausnahme) nur auf die äußersten Sterne ab und kann bereits anhand derer entscheiden, ob es zwischen den beiden Pattern einen clash gibt oder nicht.

(**) Und an der markierten Stelle liegt dieser Gag. Denn wenn einer der (Kern-)Pattern einen Stern vorne hat und der andere hinten, z.B. x und y, dann passt der erste Stern eben auf y und der zweite Stern auf x, egal wie komplex x und y sind und egal wieviele Sterne und Fragezeichen sie an egal welchen Stellen sie enthalten.

Gut, wenn man diesen Gag ausprogrammiert, kommen schon einzige Zeilen Code zusammen, aber ich denke, die Grundidee, ist trotzdem einfach und verständlich.

herbivore