AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Muster in String

Ein Thema von Monday · begonnen am 27. Nov 2015 · letzter Beitrag vom 29. Nov 2015
Antwort Antwort
Seite 1 von 3  1 23   
Monday

Registriert seit: 24. Aug 2012
103 Beiträge
 
FreePascal / Lazarus
 
#1

Muster in String

  Alt 27. Nov 2015, 19:43
Hallo,

ich möchte ein Muster in zwei Strings herausfinden.

Ich habe zwei Strings: Beispiel:
A) a123bcdef
B) ghij123kl

Möglich wäre auch
A) a1b2cd3ef
B) ghi1j2kl3

usw.

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.

Gibt es hierfür eine Funktion? Und falls nicht, welcher Weg ist hierfür am geschicktesten für die Lösung?

Was ich sicher weiß, das die Strings immer 100 Zeichen lang sind.

Ich habe erst gedacht, das ich String A mittels Bruteforce aufteile und dann die einzelnen Elemente mit String B vergleiche. Aber hab festgestellt dass das er ein laaangwieriger Weg ist,...
gibt es einen einfacheren Weg?

LG
Monday

Geändert von Monday (27. Nov 2015 um 19:47 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#2

AW: Muster in String

  Alt 27. Nov 2015, 19:50
In 100 Zeichen langen Strings gibt es potenziell Unmengen an gemeinsamen Teilzeichenketten. Man denke nur an die einzelnen Zeichen.

Suchst du nur die längste gemeinsame Teilzeichenkette?


EDIT: Ok, ich hatte das Problem falsch verstanden
Als erstes könntest du alle Zeichen entfernen, die nicht in beiden Zeichenketten vorkommen.

Geändert von BUG (27. Nov 2015 um 19:56 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Sir Rufo
Sir Rufo

Registriert seit: 5. Jan 2005
Ort: Stadthagen
9.454 Beiträge
 
Delphi 10 Seattle Enterprise
 
#3

AW: Muster in String

  Alt 27. Nov 2015, 20:15
Das Zauberwort heißt hier Permutation.

Dazu brauchst einen Algorithmus, der die alle möglichen Muster aus einem String generiert.

Die Muster kann man ja als Zeichen und ein Array darstellen.
Delphi-Quellcode:
TFollower = record
  Character: Char;
  Offset: Integer;
end;

TPattern = record
  First: Char;
  Followers: array of TFollower;
end;
Das Muster '123' aus 'a123bcdef' würde dann z.B. so aussehen:
Code:

  "First": "1",
  "Follower": [
    { 
      "Character": "2",
      "Offset": 1 
    },
    { 
      "Character": "3",
      "Offset": 2 
    } 
  ]
}
Das Muster '123' aus 'a1b2cd3ef' würde dann z.B. so aussehen:
Code:

  "First": "1",
  "Follower": [
    { 
      "Character": "2",
      "Offset": 2 
    },
    { 
      "Character": "3",
      "Offset": 5 
    } 
  ]
}
Die Suche in den anderen Strings ist dann relativ einfach. Man sucht nach der Position von First . Wenn es da eine gibt, dann schaut man, ob es am Offset des ersten Followers diesen Character gibt, usw.

Findet man alle Follower , dann hat man einen Match.

Auch wenn es nur 100 Zeichen in einem String sind, die Anzahl der Permutationen in der Breite von 1 bis 100 wird da schon gewaltig werden. Die sollte man versuchen sinnvoll einzuschränken.

z.B. Die gesuchten Muster sind zwischen 3 und 5 Zeichen lang. Das würde die Verarbeitungsgeschwindigkeit dramatisch verkürzen (man findet aber auch nur diese Muster).
Kaum macht man's richtig - schon funktioniert's
Zertifikat: Sir Rufo (Fingerprint: ‎ea 0a 4c 14 0d b6 3a a4 c1 c5 b9 dc 90 9d f0 e9 de 13 da 60)

Geändert von Sir Rufo (27. Nov 2015 um 20:21 Uhr)
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#4

AW: Muster in String

  Alt 27. Nov 2015, 21:43
Ich glaube, das sind keine Permutationen, sondern Kombinationen (oder Variationen, irgendwie so)
Auf jeden Fall gibt es in einer Zeichenkette der Länge n so ziemlich n!/(n-k)! Muster der Länge k.
Das ist ne Menge, aber machbar.

Oder irre ich?
  Mit Zitat antworten Zitat
Benutzerbild von Sir Rufo
Sir Rufo

Registriert seit: 5. Jan 2005
Ort: Stadthagen
9.454 Beiträge
 
Delphi 10 Seattle Enterprise
 
#5

AW: Muster in String

  Alt 27. Nov 2015, 23:13
Ich glaube, das sind keine Permutationen, sondern Kombinationen (oder Variationen, irgendwie so)
Auf jeden Fall gibt es in einer Zeichenkette der Länge n so ziemlich n!/(n-k)! Muster der Länge k.
Das ist ne Menge, aber machbar.

Oder irre ich?
Da kannst durchaus Recht haben ... (ich sollte da mal eine Autokorrektur eintragen )
Kaum macht man's richtig - schon funktioniert's
Zertifikat: Sir Rufo (Fingerprint: ‎ea 0a 4c 14 0d b6 3a a4 c1 c5 b9 dc 90 9d f0 e9 de 13 da 60)
  Mit Zitat antworten Zitat
Benutzerbild von Luckie
Luckie

Registriert seit: 29. Mai 2002
37.621 Beiträge
 
Delphi 2006 Professional
 
#6

AW: Muster in String

  Alt 28. Nov 2015, 01:08
Würde da nicht auch ein pos bzw. posex reichen?
Michael
Ein Teil meines Codes würde euch verunsichern.
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#7

AW: Muster in String

  Alt 28. Nov 2015, 09:49
Würde da nicht auch ein pos bzw. posex reichen?
Ich denke nicht
Möglich wäre auch
A) a1b2cd3ef
B) ghi1j2kl3
Mein gedanklicher Ansatz wäre: Schreibe die beiden Zeichenketten untereinander und verbinde die gleichen Zeichen zwischen den Wortern mit einer geraden Linie. Alle Linien (bzw. deren Zeichen) die sich mit keiner anderen kreuzen sind auf jeden Fall im längsten Muster.

Nun wäre die Frage, ob es eine gute Strategie gibt, um kreuzende Linien zu entfernen oder ob man da "dummes" Brute-Force machen muss.

EDIT/PS: Die Idee ist hier: Die kreuzenden Linien zeigen wo Zeichen in beiden Wörtern in unterschiedlicher Reihenfolge vorkommen.

Geändert von BUG (28. Nov 2015 um 10:03 Uhr)
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#8

AW: Muster in String

  Alt 28. Nov 2015, 12:41
Der Ansatz von Sir Rufo führt auf jedem Fall zum Ziel. Meine Rechnung (wenn sie denn stimmt) zeigt, das Brute Force bei nicht zu langen Zeichenketten durchaus funktionieren könnte. Natürlich kann man die Kandidaten eingrenzen. Hier ein Ansatz in C#

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 Find(int minSubLength, int maxSubLength)
        {
            for (int subLength = minSubLength; subLength <= maxSubLength; subLength++)
                ScanPattern(_text1, "", 0, subLength);
        }

        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);
            }
        }
    }
Verwendung
Code:
var matcher = new VariationMatcher ("a1b2cd3ef","ghi1j2kl3");
matcher.Find (3,3); // Nur pattern der Länge 3
Console.Writeln(string.Join ("\r\n",matcher.Patterns);
Edit: Sorry, kein Delphi zur Hand. sollte 1:1 in Delphi übersetzbar sein.

Geändert von Dejan Vu (28. Nov 2015 um 12:49 Uhr)
  Mit Zitat antworten Zitat
jobo

Registriert seit: 29. Nov 2010
3.072 Beiträge
 
Delphi 2010 Enterprise
 
#9

AW: Muster in String

  Alt 28. Nov 2015, 14:29
ich möchte ein Muster in zwei Strings herausfinden.

Ich habe zwei Strings: Beispiel:
A) a123bcdef
B) ghij123kl

Möglich wäre auch
A) a1b2cd3ef
B) ghi1j2kl3

usw.

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.
"usw." finde ich nicht sehr erschöpfend in der Beschreibung. Klar scheint ja die feste Zeichenfolge zu sein, was aber gilt als Muster? Geht das genauer?
Gruß, Jo
  Mit Zitat antworten Zitat
Benutzerbild von Sir Rufo
Sir Rufo

Registriert seit: 5. Jan 2005
Ort: Stadthagen
9.454 Beiträge
 
Delphi 10 Seattle Enterprise
 
#10

AW: Muster in String

  Alt 28. Nov 2015, 15:04
Mit meinem Mustererkennungblick sehe ich *123*
  • a123bcdef
  • ghij123kl
und *1?2??3*
  • a1b2cd3ef
  • ghi1j2kl3
oder als weiteres Beispiel *AA??A*
  • lkrAAkfAj
  • kAA34Appp
Kaum macht man's richtig - schon funktioniert's
Zertifikat: Sir Rufo (Fingerprint: ‎ea 0a 4c 14 0d b6 3a a4 c1 c5 b9 dc 90 9d f0 e9 de 13 da 60)
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 3  1 23   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 14:38 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz