Schneller Stringvergleich nach bestimmtem Muster

[taveuni]

Hallo zusammen,
Der Titel ist etwas bescheuert - mir ist aber nichts besseres eingefallen. Folgendes Szenario: Es werden automatisch irgendwelche Codes gescannt an verschiedenen Stellen - nennen wir diese Eingänge. Die Artikel werden befördert und kommen an Ausgänge an welchen sie wieder gescannt werden. Nun sollen Artikel welche an bestimmten Eingängen eingegangen sind automatisch an bestimmten Ausgängen gesondert behandelt werden. Soweit einfach - wir erhalten die Standorte sowie die Scancodes. Die Codes der definierten Eingänge sammeln wir in einem Pool. Wenn wir an einem Ausgang einen Code erhalten welcher im Pool ist reagieren wir entsprechend. Das Problem ist nun: Die Codes sind auf teilweise zerknittertem Papier aufgedruckt und werden teilweise unterschiedlich am Ein- und Ausgang gelesen. Alle Versuche seitens des Betreibers diese Fälle zu eliminieren sind gescheitert. Deshalb müssen wir neu wenn wir keinen Match haben auch noch nach einem bestimmten Muster suchen. Wenn dieses zutrifft wird angenommen dass es sich um den identischen (aber unterschiedlich gelesenen) Code handelt. Ich habe mir eine Funktion zusammengeschustert welche funktioniert. Allerdings: Wir erhalten im Durchschnitt 10000 Scans pro Minute. Im Pool können bis zu 30000 Codes sein. Ich muss diesen Vergleich so schnell wie möglich machen. Kann man die Funktion bezüglich Geschwindigkeit optimieren? Folgend ein Beispiel:

Eingangs-Scan: XX123456

Wahrheitstabelle Ausgangs-Scan:

Gelesen	Gültig
XY123456	Ja
X123456	Ja
XX1234567	Ja
Y123456	Nein
XX1234	Nein

Die bisherige Funktion:

Delphi-Quellcode:

function MatchRule(const BaseStr: String; const CompareList: TStringList): Boolean;
var
  i,j, cntForward, cntBackward: Integer;
  lBase, lComp: Integer;
  StrBase, StrCompare: String;
begin
  Result:= False;
  lBase:= Length(BaseStr);
  for i := 0 to CompareList.Count -1 do
  begin
    lComp:= Length(CompareList[i]);
    if InRange(lBase - lComp,-1,1) then
    begin
      cntForward:= 0;
      cntBackward:= 0;
      if lBase <= lComp then
      begin
        StrBase:= BaseStr;
        StrCompare:= CompareList[i];
      end
      else
      begin
        StrBase:= CompareList[i];
        StrCompare:= BaseStr;
      end;

      // compare contains base
      if Length(StrBase) < Length(StrCompare) then
        Result:= Pos(StrBase, StrCompare) > 0;

      if not Result then
      begin
        // check forward
        for j := 1 to Length(StrBase) -1 do
        begin
          if StrBase[j] = StrCompare[j] then
            inc(cntForward)
          else break;
        end;

        // check backward
        for j := Length(StrBase) downto 1 do
        begin
          if StrBase[j] = StrCompare[j+(Length(StrCompare) - Length(StrBase))] then
            inc(cntBackward)
          else break;


        if lBase = lComp then
          Result:= (cntForward + cntBackward) >= (Length(StrBase) -1)
        else
          Result:= (cntForward + cntBackward) = Length(StrBase);
        end;

      end;
      if Result then Exit;
    end
    else Continue;

  end;
end;

Die Codes können 3-12 stellig sein und beginnen meistens mit Buchstaben.

Die Ansätze welche ich mir zur Verbesserung überlegt habe:
- Sollte ich die Liste zuerst nach dem Anfang des zu prüfenden Strings sortieren?
- Sollten die Längen des Strings zuerst in Variablen gespeichert werden um das dauernde Length() zu vermeiden?
- What else?

Danke für Eure Hilfe

[baumina]

Welche Art von Barcodes verwendet ihr denn dass die unterschiedliche Ergebnisse beim scannen liefern können? Klingt ja beängstigend.

[taveuni]

Es sind keine Barcodes. Es handelt sich um Klartext Charakter. Je nach Land mit unterschiedlichen Fonts usw. Die Erkennung wird via Bildanalyse gemacht. Jede Kamera bringt 250 Bilder/Sek und hat einen eigenen Rechner für die Recognition. Es ist nichts triviales und es kann nicht anders gelöst werden. Deshalb wenn jemand helfen kann zur Verbesserung der Funktion bin ich happy. Die darunterliegende Struktur ist gegeben.

[Sir Rufo]

Gibt es noch eine Möglichkeit auf die Code-Gestaltung Einfluß zu nehmen?

Dann wäre es ratsam eine Prüfziffer in die Codes zu integrieren (oder gibt es die schon?) um die falsch gelesenen Codes zu minimieren.

[jobo]

Ich finde das ähnlich gruselig wie Baumina.
Aber was mir spontan zu Deinem Problem einfällt ist die Levenshtein-Distanz
https://de.wikipedia.org/wiki/Levenshtein-Distanz

Kurz, der Algo bestimmt die Anzahl der Unterschiede (Buchstabenänderungen), die bis zur Identität von 2 Worten durchgeführt werden müssen.
Es dürfte vermutlich sogar fertige Implementierungen dazu geben.

Achso vergessen: Man würde dann lediglich die Distanz als Schwellwert definieren und sagen 1 oder 2(das ist schon viel) Schritte wären noch ok. Der Rest ist ungültig.

[BUG]

Deine Vergleichsfunktion ist etwas gewöhnungsbedürftig. Ich hab die mal nachvollzogen

Code:

Return false wenn Längenunterschied größer als 1
Return true wenn kürzerer String in längerem enthalten ist

Zähle wieviel Buchstaben identisch sind, wenn man das kürzere Wort mit dem Anfang des längerem vergleicht
Zähle wieviel Buchstaben identisch sind, wenn man das kürzere Wort mit dem Ende des längerem Vergleicht
Addiere diese Werte
Vergleiche diesen Wert der Länge des kürzerem String

Ist das korrekt?

Was die Überlegung dahinter?
Hast du mal die Levenstein-Distanz getestet? Wie schneidet die im Vergleich ab?
Mit einer Distanz/Metrik kanst du dir eventuell die Dreiecksfunktion zunutze machen um einen Index zu erstellen.

[taveuni]

Zitat von Sir Rufo:

Gibt es noch eine Möglichkeit auf die Code-Gestaltung Einfluß zu nehmen?

Dann wäre es ratsam eine Prüfziffer in die Codes zu integrieren (oder gibt es die schon?) um die falsch gelesenen Codes zu minimieren.

Leider nein. Vergleiche es mit Kennzeichen an Fahrzeugen welche Du an Ein- und Ausfahrten via Bild OCR erkennst. Diese können bei der Einfahrt mit Schnee bedeckt, verschmutzt oder sonst was sein. An der Ein- und Ausfahrt können die Lesewinkel, die Beleuchtung usw. unterschiedlich sein. Alle diese Fälle sind unter 2% aber sie sind vorhanden.

[taveuni]

Zitat von BUG:

Code:

Return false wenn Längenunterschied größer als 1
Return true wenn kürzerer String in längerem enthalten ist

Zähle wieviel Buchstaben identisch sind, wenn man das kürzere Wort mit dem Anfang des längerem vergleicht
Zähle wieviel Buchstaben identisch sind, wenn man das kürzere Wort mit dem Ende des längerem Vergleicht
Addiere diese Werte
Vergleiche diesen Wert der Länge des kürzerem String

Ist das korrekt?

Richtig. Mit der Ergänzung dass am Schluss beim Vergleich der Werte True ist wenn
- beide Strings gleich lang sind UND der Wert diesem entspricht.
- Der eine kürzer ist und der Wert dem des kürzeren entspricht.

Zitat von BUG:

Was die Überlegung dahinter?

Es darf ein Zeichen fehlen, eines falsch sein, eines mehr sein usw. Die Matrix entspricht genau der Realität (dieses Ganzen).

Zitat von BUG:

Hast du mal die Levenstein-Distanz getestet? Wie schneidet die im Vergleich ab?
Mit einer Distanz/Metrik kanst du dir eventuell die Dreiecksfunktion zunutze machen um einen Index zu erstellen.

Ja - ich habe alle bekannten Ähnlichkeits Algorithmen getestet. Soundex usw. Diese sind hier nicht anwendbar. Siehe oben.

[stahli]

Also alles <> 100% Übereinstimmung wäre mir mulmig.
In dem Fall würde ich einen Bearbeiter den Treffer erst bestätigen lassen.
Sonst sind falsche Abläufe ja quasi vorprogrammiert.

Aber Du bist mit Deinem Algorithmus zufrieden - lediglich nicht mit der Performance?
Dann kann ich erst mal nicht helfen.

Wir hatten mal einen Thread, der unscharfe Suchen vergleicht: http://www.delphipraxis.net/154811-v...rozentual.html
Ich denke aber eigentlich nicht, dass Dir da etwas weiter hilft.

[jobo]

Zitat von taveuni:

Es darf ein Zeichen fehlen, eines falsch sein, eines mehr sein usw. Die Matrix entspricht genau der Realität (dieses Ganzen).

Das ist doch Levenshtein Distanz 1 oder (bis auf das usw.)?