Muster in String

[Monday]

Ja ich meine das so wie Sir Rufo es auch gesehen hat. Das "usw." sollte nur heißen, dass eben verschiedene Muster möglich sind und nicht exakt so aussehen wie in dem Beispiel.

Und ja, ich dachte an die längste Musterkette.

Ich habe inzwischen die Idee, dass man einen der String durch den anderen von links nach rechts durchlaufen lässt und dann die Zeichen vergleicht. Irgendwann müsste sich dann theoretisch das Muster herauskristalisieren. Evtl. reicht es auch einen der Strings nach Rechts und nach Links zu schieben. Ich weiß nicht, ob die Idee verständlich ist. Bin gerade über den Code, aber habe noch nichts lauffähiges das ich zeigen kann.

(Anwendung: In einem Analyseprogramm, dass solche Zeichenfolgen ausgibt, will ich so Auffälligkeiten in der Ausgabe finden.)

[Luckie]

Ich werfe noch mal reguläre Ausdrücke in die Runde.

[SMO]

Und ich werfe mal längster gemeinsamer Substring in die Runde.
Denn wenn ich Monday recht verstehe, möchter er in diese Richtung, aber mit Wildcards im Suchmuster. Könnte schwierig werden.

[BUG]

Wenn ich das richtig sehe, dann sucht er den längsten String, dessen Zeichen in dieser Reihenfolge in beiden Eingabestrings vorkommen.

Oder anders formuliert: Suche den längsten String, so das man diesen String aus beiden Eingabestrings erhalten kann, indem man Zeichen löscht.

Ist das nun richtig oder nicht? Nur der Montag wird die Antwort bringen

[p80286]

Zitat von BUG:

Wenn ich das richtig sehe, dann sucht er den längsten String, dessen Zeichen in dieser Reihenfolge in beiden Eingabestrings vorkommen.

Das könnte so sein. Aber Sir Rufo hat ja auch *1?2?3* als Muster identifiziert, da ist dann die Frage, was ist ein Muster, oder anders herum welche Bedingung muß eine Zeichenkombination erfüllen, damit sie ein Muster ist?

Gruß
K-H

[Dejan Vu]

Hat jemand mal meine Klasse aus probiert? Wenn man die etwas umschreibt, bekommt man tatsächlich die längsten Variationen (nein, keine Substrings, keine Muster, schlicht und ergreifend und mathematisch korrekt: Variationen) zweier Zeichenketten.

Code:

    internal class VariationMatcher
     {
         private readonly string _text1;
         private readonly string _text2;

         private readonly List<string> _patterns=new List<string>(); 

         public IEnumerable<string> Patterns { get { return _patterns; } }

         public VariationMatcher(string text1, string text2)
         {
             this._text1 = text1;
             this._text2 = text2;
         }

         public void FindLongestVariation()
         {
             for (int subLength = _text.Length; subLength >2; subLength--)
             {
                 ScanPattern(_text1, "", 0, subLength);
                 if (_Patterns.Any()) 
                   return;
              }
         }

         private void ScanPattern(string text, string pattern, int i, int remaining)
         {
             if (remaining == 0)
             {
                 FindPattern(_text2, pattern,"",0);
             }
             else
                 for (int j = i; j <= text.Length - remaining; j++)
                     ScanPattern(text, pattern + text[j], j + 1, remaining - 1);
         }

         private void FindPattern(string text, string patternToMatch, string pattern, int i)
         {
             if (pattern.Length == patternToMatch.Length)
                 _patterns.Add(pattern);
             else
             {
                 char charToMatch = patternToMatch[pattern.Length];
                 for (int j = i; j <= text.Length - patternToMatch.Length + pattern.Length; j++)
                     if (text[j] == charToMatch)
                         FindPattern(text, patternToMatch, pattern + charToMatch, j + 1);
             }
         }
     }

Nun nur noch 'FindLongestVariation' aufrufen und sich das Ergebnis in 'Patterns' anschauen.

[BUG]

Zitat von p80286:

was ist ein Muster, oder anders herum welche Bedingung muß eine Zeichenkombination erfüllen, damit sie ein Muster ist?

Genau deshalb hab ich ja den Vorschlag gemacht. Das wäre eine konkrete Definition mit der man arbeiten könnte.

Ich hab bloß den Eindruck, das hier viele Muster lesen und dann gleich "Muster - Suchmuster - Regulärer Ausdruck" denken, während die Beispiele imho gar nicht so aussehen.

[Perlsau]

Im Grunde ist alles ein Muster. Anders ausgedrückt: Es gibt praktisch nichts, das sich nicht als Muster definieren ließe. Es geht doch aber darum, was der TE eigentlich sucht. Man kann nicht nach irgend einem Muster suchen, sondern immer nur nach einem ganz bestimmten Muster, das vor der Suche eindeutig und unmißverständlich zu definieren ist. So lange der TE diese Definition nicht liefert, ist jeder weitere Kommentar dazu reinste Spekulation.

[Sir Rufo]

So richtig explizit wurde es nicht gesagt, darum muss man hier ein wenig interpretieren.

Ein Muster wird dargestellt in einer Kombination aus Platzhaltern und Zeichen.

• * => 0-n Zeichen
• ? => genau ein Zeichen

Ein Muster das mit *? startet oder mit ?* endet ist nicht zulässig.

Ein Muster liegt dann vor, wenn in einer gegebenen String-Menge in allen Strings Zeichen an einer beliebigen Stelle im gleichen Abstand vorkommen. Das Muster selber muss mindestens 2 Zeichen breit sein (Platzhalter werden nicht mitgezählt).

Beispiel:

Die gegebene String-Menge

Code:

1234567890
blhe1234j6
f1234k67id

und die (in allen Strings) vorkommenden Muster:

Code:

*12*
*1?3*
*1??4*
*123*
*1?34*
*12?4*
*1234*
*1????6*
*12???6*
...
*123??6*
*1234?6*

Das längste Muster ist das Muster, wo die Musterbreite abzüglich der Platzhalterzeichen ein Maximum aufweist. Dieses könnten aber auch mehrere Muster sein.

In dem Beispiel wäre das *1234?6*

[BUG]

Zitat von BUG:

Ich hab bloß den Eindruck, das hier viele Muster lesen und dann gleich "Muster - Suchmuster - Regulärer Ausdruck" denken, während die Beispiele imho gar nicht so aussehen.

Zitat von Sir Rufo:

Ein Muster wird dargestellt in einer Kombination aus Platzhaltern und Zeichen.

Genau das meinte ich

Nicht jedes "Muster" was jemand finden möchte ist regulär, und dem TE geht es explizit um eine bestimmte Art von Gemeinsamkeiten zwischen zwei Strings, wobei die konkreten Zeichen nicht feststehen. Wahrscheinlich ist der Begriff "Muster" an der Stelle einfach irreführend.

Zitat von Monday:

Ich weiß nicht, welches Muster es ist oder wie lange, ich weiß nur das in beiden Strings eine Zeichenfolge/Muster (im Beispiel 123) gleich sind. Und möchte herausfinden, welcher es ist.

Zitat von Perlsau:

So lange der TE diese Definition nicht liefert, ist jeder weitere Kommentar dazu reinste Spekulation.

Jup, wobei es auch sein könnte das der TE auch nicht genau weiß was er eigentlich möchte