Algorithmus gesucht (String zu RegExp)

[syntaxerror]

Hoi ihrs,
syntax schneit auch mal wieder hier rein

Ich bin am Entwickeln eines Algorithmus, aber dass ich da zusätzlich noch einen Hack brauche um unerwünschte Ergebnisse auszufiltern gefällt mir nicht so.

Entwickeln muss ich das ganze aus Zeitgründen direkt in Excel, also nix mit schönen dicken WAMP-en und so

1. Benutzer soll einen Nummernbereich im Format aaaaa-bbbbb eingeben können.
2. In diesem wollte (!) ich per regulären Ausdruck (Engine dafür steht schon und funktioniert auch) den Nummernbereich rausfiltern und dann die gefilterten Einträge irgendwohin schreiben.

Für Bereiche wie 62117-62389 funktioniert meine Routine:

62[1-3][1-8][7-9]

aber bei 62117-62380 funktioniert sie nicht:

62[1-3][1-8][0-7]
(nach internem Swap [7-0]->[0-7], da VBA bei erste Ziffer > zweiter Ziffer einen Fehler in Execute() zurückbringt)

Bei letzterer erwischt er aber auch 62110 bis 62116 mit, und das sollte nicht sein!
Allerdings kann er es in der Tat nicht "wissen", dass er an der Einerstelle die [0-6] nur dann mitparsen soll, wenn davor keine 1 kommt!

Wie krieg ich das hin, dass er GENAU diesen Bereich parst und nix drüber raus, ohne diese Hack-mässige Zusatzabfrage (so wie ich's jetzt hab) ob wir uns innerhalb von [aaaaa;bbbbb] befinden?

[tr-oo-per]

Hi syntaxerror,

Dein Problem scheint nicht weiter schwierig zu bewältigen zu sein.

Ich nehme jetzt an, dass

• der Benutzer Zahlen variabler Länge eingeben darf, z.B. "1-200", "55-57"
• der Benutzer möglicherweise Leerzeichen vor/hinter dem Trennstrich eingibt, z.B. "1 -200" oder "55 - 57"

Die beiden Zahlen (x[0]-x[1]) bekommst Du wie folgt:

$input = "123-4567";
$pattern = "/([1-9][0-9]*)\s*-\s*([1-9][0-9]*)/";
$matches = array();
$n = preg_match($pattern, $input, $matches);
$x = $matches[1];
if(x[0] > x[1]) {
    // Eingabe fehlerhaft
}
else {
    // Eingabe korrekt
} 

Vielleicht hilft Dir das weiter.

[syntaxerror]

Danke!

Schon mal ein recht guter Ansatz, gefällt mir sehr!

Verhält sich hier allerdings geringfügig anders:
Zahlen sind 5-stellig fix.

Also xxxxx-yyyyy hat immer als String gesehen die Länge 11
(zzgl. Nullbyte, je nach Sprache; aber Algorithmen sollten ja sprachunabhängig sein )

[jmc]

Deine Angaben sind für mich zwar nicht ganz klar, aber z.B. so ginge das, wenn ich dich richtig verstehe:

/([1-9][0-9]{4})-([1-9][0-9]{4})/

oder noch einfacher

/([0-9]{5})-([0-9]{5})/

je nach deinen Anforderungen

[syntaxerror]

Tja, wenn's nur SO einfach wär!
(Dann bräuchte ich hier nicht fragen )

Nene. Ich brauche ja für eine Benutzereingabe wie "61030-62190" *eine* einzige RegEx, mit der ich dann im Datenbereich meine Matches finden kann...

Deswegen ja oben im Beispiel die 62[1-3][1-8][7-9]. Die RegEx muss immer genau den Bereich abdecken, der eingegeben wird und wird natürlich (!) dynamisch erzeugt. Bei JavaScript per RegExp()-Objekt.
Der Sinn des Algorithmus soll ja sein, dass man sich - bei großen Datenmengen! - der Schnelligkeit wegen eine handelsübliche FOR-Schleife sparen kann und aus der eingegebenen Range mit einer einzigen RegEx seine Matches holen kann.

Trivial ist das mitnichten; bereits bei Eingaben wie 59099-62070 kann das sehr fies werden, vor allem wenn man - wie im Eingangsposting angedeutet - nicht falsche Matches holen will, dadurch dass er vor dem Startwert welche miterwischt.

[AmicaNoctis]

Ich dachte, ich hätte verstanden, was du eigentlich vorhast und dass tr-oo-per dir bereits eine Lösung genannt hätte, aber langsam zweifle ich daran. Vielleicht doch nochmal da capo?

[TobiaZ]

Das ganze dürfte etwas komplexer werden, als du es bisher stehen hast.

Reduzieren wir das problem mal auf drei Stellen:

Folgende Range willst du abdecken:

137
138
139
140
141
...
149
150
151

Dann musst du in folgende Richtung:

/1(3[7-9]|4[0-9]|5[0-1])

Das sollte dir eigentlich auf die Sprünge helfen.

[AmicaNoctis]

$high und $pad dürfen nicht angegeben werden, die sind nur intern für die rekursiven Aufrufe da.

<?php
    function range2regex ($a, $b, $high = null, $pad = true) {
        if ($pad) {
            $a = str_pad($a, strlen($b), 0, STR_PAD_LEFT);
            $b = str_pad($b, strlen($a), 0, STR_PAD_LEFT);
            if ($b < $a) {
                return range2regex($b, $a, null, false);
            }
        }
        if (!strlen($a)) {
            return "";
        }
        $newa = substr($a, 1);
        $newb = substr($b, 1);
        $rest = str_repeat("[0-9]", strlen($a) - 1);
        if ($high === null) {
            switch ($b[0] - $a[0]) {
                case 0:
                    return $a[0] . range2regex($newa, $newb, null, false);
                case 1:
                    return "(" . $a[0] . range2regex($newa, $newb, false, false)
                        . "|" . $b[0] . range2regex($newa, $newb, true, false) . ")";
                case 2:
                    return "(" . $a[0] . range2regex($newa, $newb, false, false)
                        . "|" . ($a[0] + 1) . $rest
                        . "|" . $b[0] . range2regex($newa, $newb, true, false) . ")";
                default:
                    return "(" . $a[0] . range2regex($newa, $newb, false, false)
                        . "|[" . ($a[0] + 1) . "-" . ($b[0] - 1) . "]" . $rest
                        . "|" . $b[0] . range2regex($newa, $newb, true, false) . ")";
            }
        }
        else if ($high === false) {
            return $a[0] == 9
                ? 9 . range2regex($newa, $newb, $high, false)
                : "(" . $a[0] . range2regex($newa, $newb, $high, false)
                    . "|" . ($a[0] == 8 ? 9 : "[" . ($a[0] + 1) . "-9]") . $rest . ")";
        }
        else {
            return $b[0] == 0
                ? 0 . range2regex($newa, $newb, $high, false)
                : "(" . ($b[0] == 1 ? 0 : "[0-" . ($b[0] - 1) . "]") . $rest
                    . "|". $b[0] . range2regex($newa, $newb, $high, false) . ")";
        }
    }
    
    echo range2regex(61030, 62190);
    // => 6(1(0(3(0|[1-9])|[4-9][0-9])|[1-9][0-9][0-9])|2(0[0-9][0-9]|1([0-8][0-9]|90)))
    // 
    //    6(
    //        1(
    //            0(
    //                3(
    //                    0|
    //                    [1-9]
    //                )|
    //                [4-9][0-9]
    //            )|
    //            [1-9][0-9][0-9]
    //        )|
    //        2(
    //            0[0-9][0-9]|
    //            1(
    //                [0-8][0-9]|
    //                90
    //            )
    //        )
    //    )
?>

[syntaxerror]

SUPER!!



1000 Dank, *DAS* sieht jetzt nach 'ner Lösung aus!
Aber TobiaZ hatte das eigentliche Problem auch schon recht gut begriffen, und schon mal nicht alles mit [0-9] "pauschalisiert", wenn natürlich (!) die jeweilige Untermenge gefunden werden sollte, nicht die gesamte!

Nun denn...das ist ein hervorragender Ansatz, der funktioniert sicher auch in VBA, den kann ich mir dann problemlos übersetzen; vorausgesetzt VBA verschluckt sich nicht am rekursiven Algorithmus! (weiß man ja vorher nie)

Danke nochmal an AmicaNoctis und TobiaZ, aber natürlich auch an die anderen! (sonst sind die beleidigt)

[AmicaNoctis]

Aber TobiaZ hatte das eigentliche Problem auch schon recht gut begriffen

… als erster in diesem Thread und das trotz der miesen Problembeschreibung.

Jedenfalls hab ich dadurch erst kapiert, was du willst.

[jmc]

Sry, dass ich das sage, aber für so etwas eine Regexp zu benutzen ist ziemlich idiotisch und absolut sinnverdreht ausser es ginge um eine Übung. Ich hoffe du willst das nicht ernsthaft in dieser Form einsetzen, oder?

[syntaxerror]

Als hätte ich's geahnt...jetzt muss ich auch noch dieserlei Fragen der Form "ist das nicht total bescheuert es damit zu machen?" beantworten...aber wie gesagt, ich war darauf vorbereitet.

Nee, wieso? Mit diesem einzigen komplexen Ausdruck kann ich z. B. Felder absuchen die so aussehen:

"61099 xxxyyy 123"
"62145 xxxyyy 456"

und bekomme dafür die Ergebnisse im Ziel-Tabellenblatt, so war das gedacht. Du hast aber schon nicht überlesen, dass ich das in Excel mache, ja? Also NIX relationale Datenbank, da würde ich das natürlich ganz anders machen - dort hab ich aber auch SQL!!!

Und angenommen, ich mach es NICHT über RegEx.
Dann darf ich eine Schleife programmieren, die von Range_Anfang bis Range_Ende absucht, und mit Sicherheit 30% langsamer läuft, da die Schleife für *JEDES* Feld separat von Anfang bis [Ende ODER gefunden] laufen muss.

Ob das dann besser ist...na da versuchste besser jemand anderen davon zu überzeugen.
Es sei denn, du hast noch eine viel bessere Idee - aber da bin ich ja mal gespannt
(...denn reden könn'se alle...)

[AmicaNoctis]

Sry, dass ich das sage, aber für so etwas eine Regexp zu benutzen ist ziemlich idiotisch und absolut sinnverdreht ausser es ginge um eine Übung.

Wenn du das wenigstens begründen und eine bessere Lösung anbieten könntest, wäre es sogar denkbar, dich ernst zu nehmen.

[jmc]

Also, eine einfache Lösung:
Suche nach einem nach einem "-" 6 Zeichen davor != Zahl 6 Zeichen danach != Zahl cint für 5 Zeichen bis 1 Zeichen davor, cint für 1 Zeichen bis 5 Zeichen danach. Teste ob Zahl die Zahl davor in deinem Nummernbereich ist und ob die Zahl danach in deinem Nummernbereich ist (diese Version, wenn du in deinem ersten Beitrag wirklich Format xxxxx-yyyyy gemeint hast und nicht Bereich).

Wenn du im 1. Beitrag Bereich gemeint hast ist es immer noch viel schneller, wenn du nach einer 5-stelligen Zahl suchst und cint benutzt.
Wenn die Zahlen sogar immer an einer bestimmten Stelle stehen springst du direkt zu der Stelle und testest die Zahl darauf, ob sie in dem von dir bestimmten Bereich ist. Inwiefern die Zahl vorkommt beschreibst du in deinem Beitrag leider nicht.

noch was zur RegExp unten. Bei Zahlen wie 610300 oder 161030 stimmt das auch zu. Wenn das keine Rolle spielt, dann kennst du wohl die Vorkommnisse der Zahlen und damit hast du garantiert eine sehr einfache Möglichkeit.

Warum also keine RegExp in der Art?
1. Sie ist mit mehreren OR-Konditionen relativ langsam.
2. Es braucht verhältnismässig viel Speicher.
3. Auch wenn das bei heutigen Computern keine Rolle mehr spielt sobald du einmal ein grösseres Projekt hast wirst du Probleme kriegen.
4. RegExp sind dafür gedacht ein gewisses Format zu finden, in deinem Fall hingegen suchst du nicht nur das Format sondern auch nach dem Wert beim selben Format. Du köntest Zahlen natürlich überall mit einer RegExp auf einen bestimmten Bereich prüfen, statt relationale Operatoren zu benutzen, aber selbst, wenn es ein String ist, den du erst noch in eine Zahl konvertieren musst ist es einiges effizienter relationale Operatoren zu benutzen statt einer RegExp

[AmicaNoctis]

@jmc

Dass es um das Finden von Zahlen in einem Text geht, hast du aber erkannt, oder? Ich frage nur, weil mir das erst auch nicht klar war. So, wie ich es inzwischen verstanden habe, läuft es so ab:

User gibt ein Intervall an, z. B. 12345-98765
Programm generiert einen Regex dafür, z. B.
(1(2(3(4(5|[6-9])|[5-9][0-9])|[4-9][0-9][0-9])|[3-9][0-9][0-9][0-9])|[2-8][0-9][0-9][0-9][0-9]|9([0-7][0-9][0-9][0-9]|8([0-6][0-9][0-9]|7([0-5][0-9]|6([0-4]|5)))))
Programm durchsucht einen Text nach Zahlen, die innerhalb dieses Intervalls liegen (fett), z. B.

abc 12300 def 22558 ghi 99887 jkl 55555

noch was zur RegExp unten. Bei Zahlen wie 610300 oder 161030 stimmt das auch zu.

Das ist ja auch nur eine Art Vorlage. Dass dort jeweils noch was drumherum kommt, damit es ein vollständiger Regex wird, versteht sich von selbst, also z. B.

/(^|[^\d])…([^\d]|$)/

Der generierte Code kommt dann da hin, wo … steht.

Sie ist mit mehreren OR-Konditionen relativ langsam.

Sicher? Immerhin ist es komplett lookaheadfrei.