RegEx Generator Version 1

[Shadow992]

Originally Posted by Synatex

Okay, ich steig dann mal aus. Für mich ist das eher nur als kleines Nebenprojekt gedacht das einigen das Leben erleichtern soll, will meine wenige Zeit nun ungern in noch kompliziertere Sachen stecken

Hehe kenn ich
Ne war ja auch nie so umstädnlcih gedacht. Ich habe ja von Anfang an gesagt, dass es "cool"/"schön" wäre, wenn das ginge, dass das nicht einfach so gemacht wird, ist klar, aber der Vorposter wollte ja eine mögliche Vorgehensweise des Algorhitmuses sehen.

Edit:
@dowhile
Weil es mir gerade so einfällt, wirf doch auch einmal einen Blick hierauf:
http://de.wikipedia.org/wiki/Unsicheres_Wissen
Dann weißt du wie man mit unsicherem Wissen umgeht.

[dowhile]

Jetzt hast du die Vorgehensweise des Algorithmus in diesen zwei konkreten Fällen beschrieben. An deinen Beschreibungen sieht man gut, wie unterschiedlich der Algorithmus in besonderen Fällen arbeiten muss. Da es aber eine unbegrenzte Anzahl an "besonderen Fällen" gibt, bräuchten wir nun einen Algorithmus, der einen Algorithmus für den vorliegenden, besonderen Fall konstruiert. Kannst du diesen Algorithmus beschreiben?

Wenn ich 1000x eine Summe von 2 Zahlen kleiner 10 rechne und dann plötzlich die Aufgabe kriege Zahlen mit 10 Ziffern und mehr zu addieren, wird auch der Mensch überfordert (nicht umsonst rechnet man in der Schule Stufenweise also bis 20, bis 100, bis 1000 und dann bis 100.000).

Ist das Beispiel nicht recht schlecht gewählt?

Die Addition lässt sich mit den Peano-Axiomen so definieren:

n + 0 = n
n + (m++) = (n + m)++

Mit dieser Definition kann ein Mensch die Summe für beliebige Zahlen berechnen. Er kann die Definition 1000 mal für n, m < 10 verwenden und anschließend auch problemlos für 10^11 < n, m (dauert nur etwas). Der Algorithmus bleibt immer gleich.

Der geforderte Algorithmus muss bei jedem Fall anders vorgehen, d.h. er braucht für jede vorhandene Beispiele einen anderen Algorithmus, um die restlichen Wörter zu erraten. Das ist etwas völlig anderes wie rechnen.

[Shadow992]

Originally Posted by dowhile

Jetzt hast du die Vorgehensweise des Algorithmus in diesen zwei konkreten Fällen beschrieben. An deinen Beschreibungen sieht man gut, wie unterschiedlich der Algorithmus in besonderen Fällen arbeiten muss. Da es aber eine unbegrenzte Anzahl an "besonderen Fällen" gibt, bräuchten wir nun einen Algorithmus, der einen Algorithmus für den vorliegenden, besonderen Fall konstruiert. Kannst du diesen Algorithmus beschreiben?


Ist das Beispiel nicht recht schlecht gewählt?

Die Addition lässt sich mit den Peano-Axiomen so definieren:

Mit dieser Definition kann ein Mensch die Summe für beliebige Zahlen berechnen. Er kann die Definition 1000 mal für n, m < 10 verwenden und anschließend auch problemlos für 10^11 < n, m (dauert nur etwas). Der Algorithmus bleibt immer gleich.

Der geforderte Algorithmus muss bei jedem Fall anders vorgehen, d.h. er braucht für jede vorhandene Beispiele einen anderen Algorithmus, um die restlichen Wörter zu erraten. Das ist etwas völlig anderes wie rechnen.

Prinzipiell läuft der Algorhitmus immer auf dasselbe Prinzip hinaus.
Häufigkeitsanalyse --> Entscheidungen treffen --> Vergleichen --> Erneute Häufigkeitsanalyse --> Entscheidungen treffen --> ...

So außergewöhnlich ist das auch nicht.
Man kann das Vorgehen bei den Zahlen auf Buchstaben erweitern, auch hier kann man eine Häufigkeitsanalyse machen.
Ein paar festgelegte Regeln braucht das System dennoch um eben so Sachen wie 0x zu erkennen, der Rest ist alles Wahrscheinlichkeit und KI mit unsicherem Wissen.

@Dein Beispiel
Hier hast du aber eine fest definierte Regel vorgegeben und eben diese soll das System ja ableiten, du rollst das Problem also von der anderen Seite auf.

[dowhile]

Okay, dann haben wir also in etwa folgenden Algorithmus:

* Nach gleichen Zeichen in allen Beispielen suchen
* Fixe Zeichen mit vorpogrammierten Mustern abgleichen (0x...)
* Abschnitte zwischen diesen fixen Zeichen untersuchen und durch Abschätzen die Zeichengruppe festlegen (unter Berücksichtigung eventueller Überschneidungen mit bekannten Mustern)

Damit kann der Algorithmus IP-Adressen ungefähr erkennen (999.666.555.444 ginge auch, ist aber ungültig) und hexadezimale Zahlen erkennen.

Das Beispiel mit den Kommazahlen funktioniert hingegen nicht.
"3", "3.5" und "4,65" haben keine fixen Zeichen. Zusätzlich muss der Algorithmus optionale Teile berücksichtigen. Er muss erkennen, dass eine oder mehrere (durch Beispiele mit höheren Zahlen) kommt und anschließend ein "." oder "," folgt. Dann wieder Zahlen.

Jetzt seien folgende Beispiele gegeben: "1000", "5901", "400194", "1789999901", "109889", "10".
Als fixes Zeichen würde der Algorithmus die "0" und die "1" erkennen (denn die stecken überall drin). Der Algorithmus würde hier also völlig falsch arbeiten.
Beheben könnte man das, indem fixe Zeichen nicht der restlichen "Gruppe" (Buchstaben, Zahlen, ...) entsprechen dürfen.
Wenn ich aber alle Zeichenketten, die aus Zahlen und mindestens einem "a"s bestehen akzeptieren möchte, besteht das Problem weiter.
Der Algorithmus muss hier also anders funktionieren als oben - und das stelle ich mir schwierig vor.

@Dein Beispiel

Welches genau meinst du?

[Shadow992]

Originally Posted by dowhile

Okay, dann haben wir also in etwa folgenden Algorithmus:

* Nach gleichen Zeichen in allen Beispielen suchen
* Fixe Zeichen mit vorpogrammierten Mustern abgleichen (0x...)
* Abschnitte zwischen diesen fixen Zeichen untersuchen und durch Abschätzen die Zeichengruppe festlegen (unter Berücksichtigung eventueller Überschneidungen mit bekannten Mustern)

Damit kann der Algorithmus IP-Adressen ungefähr erkennen (999.666.555.444 ginge auch, ist aber ungültig) und hexadezimale Zahlen erkennen.

Das Beispiel mit den Kommazahlen funktioniert hingegen nicht.
"3", "3.5" und "4,65" haben keine fixen Zeichen. Zusätzlich muss der Algorithmus optionale Teile berücksichtigen. Er muss erkennen, dass eine oder mehrere (durch Beispiele mit höheren Zahlen) kommt und anschließend ein "." oder "," folgt. Dann wieder Zahlen.

Jetzt seien folgende Beispiele gegeben: "1000", "5901", "400194", "1789999901", "109889", "10".
Als fixes Zeichen würde der Algorithmus die "0" und die "1" erkennen (denn die stecken überall drin). Der Algorithmus würde hier also völlig falsch arbeiten.
Beheben könnte man das, indem fixe Zeichen nicht der restlichen "Gruppe" (Buchstaben, Zahlen, ...) entsprechen dürfen.
Wenn ich aber alle Zeichenketten, die aus Zahlen und mindestens einem "a"s bestehen akzeptieren möchte, besteht das Problem weiter.
Der Algorithmus muss hier also anders funktionieren als oben - und das stelle ich mir schwierig vor.

Ja einfach wäre das mit Sicherheit nicht gemacht, aber es ist nicht unmöglich. Dass der Algorhitmus nie 100% genau arbeiten wird, versteht sich von selbst, das zeichnet ja allgemein den Bereich der KI aus.
Für einzelne Beispiele können sich total kroteske Ergebnisse finden, im Durchschnitt kann die Chance richtig zu liegen, jedoch nahe 100% liegen.

Ein interessanter Ansatz zur Lösung dieses Problems wäre das Benutzen von künstlichen neuronalen Netzen. Einziges Problem wäre hier lediglich die Lernrate, da man rund 100 Beispiele eingeben müsste um gute Ergebnisse zu bekommen. Deswegen fällt dieser Ansatz mit Sicherheit unter dem Tisch, auch wenn er ein interessanter Aspekt wäre.