Textmuster mit Platzhalterzeichen (*) vergleichen – Diskussion

[Technipion]

Dieser Post bezieht sich hierauf: Textmuster miteinander vergleichen

Das interessiert mich doch jetzt.
Javascript, php oder in c, oder in was könntest du?

Ich habe mal eine Beispielimplementierung in Python geschrieben. Hier der Code:

# tutorials.de
# Textmuster miteinander vergleichen

import functools


def main():
    patterns = ["DS05-03",
                "DS05-04",
                "DS05-**",
                "DS**-04",
                "DS**-**",
                "DS0504",
                "DS05**",
                "BS05-04"]

    base_text = "DS05-04"

    print("*** base text:", base_text, "***")
    for pattern in patterns:
        print(pattern, "Match" if is_match(pattern, base_text) else "No match", sep=" -> ")


def is_match(pattern, base_text):
    if len(pattern) != len(base_text):
        return False

    tokens = tokenize(pattern)
    return all(base_text[token[0]:token[1]] == pattern[token[0]:token[1]]
               for token in tokens)


@functools.cache
def tokenize(pattern):
    if len(pattern) == 0:
        return []

    tokens = []
    on_token = bool(pattern[0] != '*') # are we currently parsing a token?
    last_index = 0 # index of beginning of current token

    for i, ch in enumerate(pattern):
        if ch == '*':
            if on_token: # token has finished
                tokens.append((last_index, i))
                on_token = False
            else: # consecutive asterisks
                continue
        else:
            if on_token: # still on token
                continue
            else: # new token begins
                last_index = i
                on_token = True

    # if necessary: add pending token
    if on_token:
        tokens.append((last_index, len(pattern)))

    return tokens


if __name__ == '__main__':
    main()

Erzeugt bei mir die Ausgabe:

$ python solve.py
*** base text: DS05-04 ***
DS05-03 -> No match
DS05-04 -> Match
DS05-** -> Match
DS**-04 -> Match
DS**-** -> Match
DS0504 -> No match
DS05** -> No match
BS05-04 -> No match

Zwei Punkte dazu:

• Ich verwende hier Memoisation, da ein Pattern immer zu genau den gleichen Token umgewandelt wird. So spare ich mir einfach die manuelle Pufferung.
• Der wichtige Teil ist hier base_text[token[0]:token[1]] == pattern[token[0]:token[1]]. Sieht zwar nicht so aus, ist aber ein String-Comparison und lässt sich prinzipiell zu effizientem Assembly (REPE + CMPS) herunterkompilieren.

Interessant wäre mal ein Performance-Vergleich mit RegEx, da bin ich jetzt aber zu faul dafür

Gruß Technipion

 

[Zvoni]

hmm..... ich glaub ich versteh jetzt was du meinst.
Das einzige was mich jetzt ein "wenig" stört (wobei ich definitiv kein Python-er bin):
In Zeile 42 beginnst du die Schleife erneut bei 0, obwohl du das in Zeile 39 und 40 schon erledigt hast.
Genau so auch die zwei continues. Ist eigentlich ein Hinweis die If-Condition umzudrehen

Ausserdem erschliesst sich mir nicht, wieso du nur zwei Elemente in tokens hast (token[0] und token[1])

 

[Zvoni]

OK, obiger Algoritmus anbei in Pascal (allerdings mit kleinen Abweichungen)

program Project1;
Uses StrUtils; //Needed for PosEx

Type
  TToken = Array[0..1] Of Integer;
  TTokens = Array Of TToken;
Const
  patterns: Array[0..7] of String=('DS05-03','DS05-04','DS05-**','DS**-04','DS**-**','DS0504','DS05**','BS05-04');
  base_text:String='DS05-04';
  c:Char='*';
Var
  k:Integer;

Function tokenize(APattern:String):TTokens;
Var
  i:SizeUInt=1;
  p:SizeInt;
  l:Integer;
  Procedure AdjustResult(StartToken, LengthToken:Integer);
  Begin
    SetLength(Result,Length(Result)+1);
    Result[High(Result)][0]:=StartToken;   //Start of Token
    Result[High(Result)][1]:=LengthToken;  //Length of Token
  end;
Begin
  l:=Length(APattern);
  While i<=l Do
    Begin
      //PosEx = SearchForWhat, SearchWhere, StartAt
      p:=PosEx(c,APattern,i);
      If p>i Then //we found a '*'
         Begin
           AdjustResult(i,p-i);
           i:=p+1; //Set next Starting position
         end
      Else   //This part can only be entered if consecutive '*' or no more '*' in the remaining pattern
        If (i<l) And (p=0) Then  //Catches pending token
          Begin
            AdjustResult(i,l-i+1);
            Exit;
          end
        Else Inc(i); //move on
    end;
End;

Function is_match(APattern, ASource:String):Boolean;
Var
  tt:TTokens;
  i:Integer;
Begin
  If Length(APattern)<>Length(ASource) Or (Length(APattern)=0) Then Exit(False);
  Result:=True; //Preset successful Result
  tt:=tokenize(APattern);
  For i:=Low(tt) To High(tt) Do
    Result:=Result And (MidStr(APattern,tt[i][0],tt[i][1])=MidStr(ASource,tt[i][0],tt[i][1]));
end;
//Main Entry point
begin
  For k:=low(patterns) To High(patterns) Do
    Writeln('Pattern: ',patterns[k],' = ',base_text,' -> Match? ',is_match(patterns[k],base_text));
end.

Ergibt:

Pattern: DS05-03 = DS05-04 -> Match? FALSE
Pattern: DS05-04 = DS05-04 -> Match? TRUE
Pattern: DS05-** = DS05-04 -> Match? TRUE
Pattern: DS**-04 = DS05-04 -> Match? TRUE
Pattern: DS**-** = DS05-04 -> Match? TRUE
Pattern: DS0504 = DS05-04 -> Match? FALSE
Pattern: DS05** = DS05-04 -> Match? FALSE
Pattern: BS05-04 = DS05-04 -> Match? FALSE

 

[Yaslaw]

Ich finde deinen Ansatz übertrieben aufgeblasen. Ich ersetze einfach jeden * durch \w und prüfe mit RegeEx. Wenn ich sicher bin, dass jedes * nur eine Ziffer sein kann, dann geht auch \d. Sollte * was anderes als Ziffer oder Buchstabe sein, so währe der Punkt anstelle von \ zu wählen

<pre><?php
$patterns = array("DS05-03",
                "DS05-04",
                "DS05-**",
                "DS**-04",
                "DS**-**",
                "DS0504",
                "DS05**",
                "BS05-04");

$value = 'DS05-04';

foreach($patterns as $pattern){
    $regExPattern = '/'.str_replace('*', '\w', $pattern).'/';
    $result = preg_match($regExPattern, $value);
    echo("{$pattern} -> {$result}<br />");
}
?></pre>

DS05-03 -> 0
DS05-04 -> 1
DS05-** -> 1
DS**-04 -> 1
DS**-** -> 1
DS0504 -> 0
DS05** -> 0
BS05-04 -> 0

 

[Zvoni]

Ja, mag aufgebläht aussehen, die berechtigte Frage ist aber was ist performanter:
die schleifen mit den tokens, oder die replaces zzgl. Noch 8 regex aufrufe?