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:

Zitat von Sir Rufo (Beitrag 1323805)

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:

Zitat von BUG (Beitrag 1323809)

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:

Zitat von BUG (Beitrag 1323809)

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:

Zitat von BUG (Beitrag 1323809)

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:

Zitat von taveuni (Beitrag 1323812)

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.)?

[jobo]

Ihr habt also keinen Einfluss auf den Code, wohl aber auf den Scanvorgang, physikalisch, prozesstechnisch?

[taveuni]

Zitat:

Zitat von jobo (Beitrag 1323814)

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

Ich mach noch mal ein paar Versuche.

[taveuni]

Zitat:

Zitat von jobo (Beitrag 1323815)

Ihr habt also keinen Einfluss auf den Code, wohl aber auf den Scanvorgang, physikalisch, prozesstechnisch?

Nein- ebenfalls nicht. Wir sind nur Datenempfänger und steuern dann bei den Ausgängen verschiedene Prozesse.

[taveuni]

Zitat:

Zitat von stahli (Beitrag 1323813)

Aber Du bist mit Deinem Algorithmus zufrieden - lediglich nicht mit der Performance?

Ja.

[jobo]

Zitat:

Zitat von taveuni (Beitrag 1323822)

Zitat:

Zitat von jobo (Beitrag 1323814)

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

Ich mach noch mal ein paar Versuche.

Hab grad mal ausprobiert, ein Datenvolumen von ca 40000 auf einer Halligalli VM bekommt man mit LD in deutlich unter 0,5 Sekunden per SQL abgefragt. Die gewünschte Distanz spielt dabei im relevanten Bereich keine Rolle. Kann wahrscheinlich stark beschleunigt werden. Müsst Ihr die 10000 Scans pro Minute alle per Mustervergleich wiederfinden oder nur die Fehler?

Auch wenn Ihr den Scan nicht beeinflussen könnt, noch eine technische Idee dazu:
Wie wär es, wenn man schon den Eingang immer mehrfach scant, vielleicht 3x und dann den besten Treffer nimmt? Das könnte ggF. auch per Blackbox geschehen, also ohne dass die xfache Menge an Scans in den Pool fließt. Kostet natürlich ein paar Scanner extra.
Dann wäre man aus der ShitInShitOut Nummer vielleicht raus.

[taveuni]

Zitat:

Zitat von jobo (Beitrag 1323827)

Hab grad mal ausprobiert, ein Datenvolumen von ca 40000 auf einer Halligalli VM bekommt man mit LD in deutlich unter 0,5 Sekunden per SQL abgefragt. Die gewünschte Distanz spielt dabei im relevanten Bereich keine Rolle. Kann wahrscheinlich stark beschleunigt werden. Müsst Ihr die 10000 Scans pro Minute alle per Mustervergleich wiederfinden oder nur die Fehler?

Das ist eben genau der springende Punkt. Am "Ausgang" wissen wir nicht ob der Code an einem der relevanten Eingänge durch ist. Deshalb müssen wir jeden Ausgang prüfen. Und zwar mit jedem Eingang im Pool. Die welche nicht matchen gehen weiter die anderen werden aussortiert. Werden solche die aussortiert werden müssten weitergelassen geht viel Geld flöten für den Betreiber. Deshalb auch lieber mal einen grosszügigen Match als das Gegenteil. Wobei auch das Probleme mit sich bringt.
Weiter dürfen wir keine Zeit verlieren beim Ausgang. Benötigen wir zu lange für den Vergleich (sprich die Suche mit Leventstein oder was auch immer) blockiert das Band und die ganze Anlage geht auf Notstop.

Zitat:

Zitat von jobo (Beitrag 1323827)

Auch wenn Ihr den Scan nicht beeinflussen könnt, noch eine technische Idee dazu:
Wie wär es, wenn man schon den Eingang immer mehrfach scant, vielleicht 3x und dann den besten Treffer nimmt? Das könnte ggF. auch per Blackbox geschehen, also ohne dass die xfache Menge an Scans in den Pool fließt. Kostet natürlich ein paar Scanner extra.
Dann wäre man aus der ShitInShitOut Nummer vielleicht raus.

Wir erhalten schon mit den Scans einen Score von der Recognition. Wenn dieser Score unter einem Schwellwert liegt werden diese Artikel schon beim Eingang aussortiert. Leider ist der Score aber eben nicht immer zuverlässig. Manchmal ist der auf 99 von 100 aber trotzdem falsch gelsen.

[BUG]

Mir ist was eingefallen: je nachdem wie die Längen verteilt sind, macht vielleicht Sinn die Liste nach Stringlänge zu unterteilen und dir nur die Strings anzugucken die 1 Zeichen kürzer oder länger sind.
Haben die Meisten die gleiche Länge, wird das wohl nichts bringen.

Um nochmal den Gedanken von jobo aufzugreifen: wie groß ist der Anteil der "fehlerhaften" Codes? Korrekte Einträge lassen sich mit einem Directory schneller finden.

Ein mögliches Problem: wenn nicht gefundene Codes in der Liste bleiben, wird die mit der Zeit immer länger, was deine Aufgabe nicht leichter macht.

[taveuni]

Zitat:

Zitat von BUG (Beitrag 1323898)

Um nochmal den Gedanken von jobo aufzugreifen: wie groß ist der Anteil der "fehlerhaften" Codes? Korrekte Einträge lassen sich mit einem Directory schneller finden.

Der Pool ist selbstverständlich in einem Dictionary. Zuerst suchen wir einen Match in diesem. Erst danach die Ähnlichkeit.

Zitat:

Zitat von BUG (Beitrag 1323898)

Ein mögliches Problem: wenn nicht gefundene Codes in der Liste bleiben, wird die mit der Zeit immer länger, was deine Aufgabe nicht leichter macht.

Dies ist ein anderes Problem was auch latent ist. Natürlich werden wir mit der Prüfung auch die ähnlichen Codes rauslöschen. Zusätzlich müssen wir eine manuelle (dynamische) Möglichkeit einbauen Einträge zu löschen.

[Dejan Vu]

Ist das ungefähre Format der Codes bekannt, d.h. z.B. 1-3 Buchstaben, danach 3-12 Ziffern?
Wenn ja, könnte man die Eingangscodes umformulieren, sodaß ein Match schneller wird, z.B.
"XX123456" => 1-3 X + Ziffernfolge: 123456
"XY1234567" => 0-2 X, 0-2 Y, Ziffernfolge 1234567

Ein Vergleich würde dann die 'X' matchen, die Y nicht, aber die Ziffernfolge zu 600/7 %. Mit deinem Schwellenwert wäre das ein match.

Der Matchalgorithmus könnte bei den Ziffernfolgen mit Bitpattern arbeiten, die per AND verknüpft werden. Das Ergebnis liefert über eine Lookuptabelle die Anzahl der 1er Bits und damit den Match.

Dein Algorithmus ist aber schon recht gut, d.h. O(n). LD ist O(n*m). Mir fallen noch Jacquard und Jaro-Winkler O(n*m)) ein. Jacquard ist mW zu allgemein und JW eben auch zu langsam (wobei ich JW ggü LD vorziehe).

Generell scheint mir dein Problem ein sequence aligment Problem zu sein (Finde die optimale Sequenz zweier Nukleotidketten). Leider hast Du keine DNA-Sequenzen, sondern nur sehr kurze Strings.

Da fällt mir ein: Hast Du es mit n-Gram matching versucht?

Ansonsten dürfte eine Einschränkung der Matchkandidaten über die Länge am geeignetsten sein, hier noch etwas zu holen. Deine Eingangsstrings werden einfach auf N Listen verteilt, wobei N die Länge des Eingangsstrings ist.
Ich würde auch überlegen, ob eine Vorverarbeitung der Eingabe-Codes (String-Tree, Charbitmap, o.ä.) bezüglich der Einschränkung etwas bringt... So wäre z.B. ein reiner Vergleich der im Code enthaltenen Zeichen (wieder Bitmuster und Lookup) sehr schnell und würde die Wahrscheinlichkeit verringern, den aufwändigeren Zeichen-für-Zeichen-Algorithmus anwenden zu müssen: Denk immer dran, deine Eingabecodes werden 1000x verglichen, insofern ist JEDE Vorverarbeitung sinnvoll.

Weiterhin könnte PChar ggü StringIndex noch etwas bringen.

Abschließend: Was passiert eigentlich, wenn zwei Eingangscodes matchen?

[jobo]

Zitat:

Zitat von taveuni (Beitrag 1323830)

Das ist eben genau der springende Punkt.

Nagut, ein "Match" entsteht in 98% der Fälle ja offenbar auch ohne Mustervergleich, sondern bei Exaktheit, solche Abfragen gegen 50T Datensätze haben ja quasi keine spürbare Laufzeit. Ein Mustervergleich mit längerer Laufzeit erfolgt dann nur in wenigen Fällen und wie gesagt, die halbe Sekunde aus meinem Versuch ist bestimmt stark optimierbar, siehe z.B. @Bug: Mengeneinschränkung durch Längenfilter, vielleicht hilft auch die Laufzeitbetrachtung zwischen Eingang und Ausgang und natürlich Optimierung an der Abfrage ..

Recognition Score und Ausschusskosten
Ich gehe mal davon aus, dass bei dem genannten Durchsatz und irgendwelchen geschätzten Ausschusskosten, die Anschaffungskosten weiterer Scanner oder tagelange Arbeit Deinerseits nicht weiter ins Gewicht fallen. Letztlich kommt mein Vorschlag ja nur, weil das Gefühl da ist, dass mit dem Matchingverfahren nur ein Symptom behandelt wird. Dein Anliegen hier ist ja auch konkret Beschleunigung, nicht Verbesserung der Trefferrate.

Der Recognition Score ist sicher nett, aber er funktioniert nach dem "gleichen" Prinzip wie Dein Match jetzt. Es ist eher die Behauptung eines 100% Match.
Die Vervielfältigung guter Prozesselemente ist aber ein Konstruktionsprinzip. Daher ist der Mehrfachscan sicher nicht so verkehrt.
Erinnerst Du Dich an die ersten Barcode Scanner Kassen? Wie oft die Kassierer das Teil mehrfach übers Band gezogen haben? Obwohl die Technik schon Jahre vorher in Amiland im Einsatz war. Vermutlich haben die Systeme ähnliche Optimierungsverfahren durchlaufen.

Mehrfachscan kannst Du billig auch mit einem Scanner seriell erreichen*. Wenn das Zeitfenster zu kurz ist, eben mehr Scanner. Die können auch aus unterschiedlichen Positionen und mit unterschiedlichem Licht arbeiten. Es ist bekannt, das Licht, Reflektion,. . ein Problem bei den Teilen ist.

*Mir fällt grad ein, dass solche Systeme ja vielleicht schon so arbeiten, mglw. mit HDR Technik arbeiten oder was weiß ich, bin da kein Kenner. Dann kann eher eine andere Kameraposition helfen.

[taveuni]

Zitat:

Zitat von jobo (Beitrag 1323901)

Nagut, ein "Match" entsteht in 98% der Fälle ja offenbar auch ohne Mustervergleich, sondern bei Exaktheit, solche Abfragen gegen 50T Datensätze haben ja quasi keine spürbare Laufzeit. Ein Mustervergleich mit längerer Laufzeit erfolgt dann nur in wenigen Fällen und wie gesagt, die halbe Sekunde aus meinem Versuch ist bestimmt stark optimierbar, siehe z.B. @Bug: Mengeneinschränkung durch Längenfilter, vielleicht hilft auch die Laufzeitbetrachtung zwischen Eingang und Ausgang und natürlich Optimierung an der Abfrage ..

Leider nicht. Es ist so: Es existieren z.b. 50 "Eingangsscanner". "Ausgangsscanner" nur 5 Stück. Nur 4 von den Eingangsscannern sind aber überhaupt relevant für die ganze Überprüfung (genauer Match, Ähnlichkeit usw.). Also landen nur diese im Pool für den Vergleich an den Ausgängen. Aber alle units passieren die 5 Ausgangsscanner. Somit sind eigentlich 90% am Ausgang nicht relevant. Aber da alle auf den gleichen Ausgang kommen.. müssen wir alle units vergleichen! Und deshalb muss dieser Vergleich sehr schnell sein.

[taveuni]

Eure Vorschläge für die Unterteilung in verschiedene Listen abhängig der Länge werde ich weiter verfolgen. Momentan sehe ich das Problem aber noch in der Abgrenzung. Denn so könnte es ja sein dass ich dann teilweise gegen zwei Listen prüfen muss?

[jobo]

Zitat:

Zitat von taveuni (Beitrag 1323904)

Denn so könnte es ja sein dass ich dann teilweise gegen zwei Listen prüfen muss?

Eher gegen 3?
Aber ist doch egal, der Kern ist eine grobe Reduktion der notwendigen Vergleiche.

[jobo]

Zitat:

Zitat von taveuni (Beitrag 1323903)

Aber da alle auf den gleichen Ausgang kommen.. müssen wir alle units vergleichen! Und deshalb muss dieser Vergleich sehr schnell sein.

Ich rede ja nur davon, dass der Vergleich unterschiedlich komplex Ausfallen kann und damit Zeit gespart werden kann.

[nahpets]

Mal ein paar (unsinnige?) Gedankenspiele:

Ab ins alte Turbopascal, dort enthielt bei Strings das 0. Byte die Länge.
Das dürfte heute bei ShortString noch so sein. Geht ShortString auch? Wenn ja:

Delphi-Quellcode:

var sBaseStr : ShortString;
    lBaseStr : Byte absolut sBaseStr;

Damit befindet sich die Längenangabe von sBaseStr automatisch in lBaseStr. Die wiederholte Längenabfrage per Length kann damit entfallen.

Alternativ die Länge nur einmalig abfragen und in Variabeln speichern. Alles entfernen, was wiederholt gemacht werden muss. Lieber ein paar zusätzliche Variabeln "mitschleppen".

Delphi-Quellcode:

function MatchRule(const BaseStr: String; const CompareList: TStringList): Boolean;
var
  i                  : Integer;
  j                  : Integer;
  cntForward         : Integer;
  cntBackward        : Integer;
  lBase              : Integer;
  lComp              : Integer;
  StrBase            : String;
  lStrBase           : Integer; // Länge von StrBase
  StrCompare         : String;
  lStrCompare        : Integer; // Länge von StrCompare
  lStrBaseStrCompare : Integer; // Differenz: lStrCompare - lStrBase
begin
  Result := False;
  bBreak := 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
      lStrBase    := Length(StrBase);
      lStrCompare := Length(StrCompare);
      if lStrBase < lStrCompare then Result:= Pos(StrBase, StrCompare) > 0;
      if not Result then begin
        // check forward
        for j := 1 to lStrBase - 1 do begin // Warum kein Vergleich beim letzten Zeichen?
          if StrBase[j] = StrCompare[j] then inc(cntForward)
          else break;  // Beim ersten Unterschied raus aus For...
        end;
        // check backward
        lStrBaseStrCompare := lStrCompare - lStrBase;
        for j := lStrBase downto 1 do begin
          if StrBase[j] = StrCompare[j + lStrBaseStrCompare] then
            inc(cntBackward)
          else break;  // Beim ersten Unterschied raus aus For...
        end;
        if lBase = lComp then
          // bei gleicher Länge darf es einen Unterschied geben.
          Result := (cntForward + cntBackward) >= (lStrBase - 1)
        else
          Result := (cntForward + cntBackward) = lStrBase;
      end;
      if Result then Exit;  // hier raus, wenn Result = True;
    end;
    // else Continue; // überflüssig, da wir hier ja sowieso am Ende der Schleife sind.
  end;
end;

Ob das jetzt große Geschwindigkeitsunterschiede gibt, mag ich nicht zu beurteilen.
Meine praktische Erfahrung ist jedoch, dass bei häufig wiederholten Routinen durchaus Geschwindigkeitsvorteile zu erwarten sind, wenn man wiederholt per Pos, Length... ermittelte Werte in separaten Variablen "mitschleppt", um die wiederholte Ausführung, eigentlich trivialer Funktionen, zu eliminieren.

[taveuni]

Danke. Ich habs ausprobiert. Bei Prüfung gegen 50000 habe ich keinen messbaren Unterschied gefunden. Vermutlich Compilermagic.
Zu Deinen Kommentaren:
-Bei Forward warum nicht bis zum Schluss? Um einen Durchlauf zu sparen. Denn wenn es die letzte Ziffer ist spielt es keine Rolle. Wenn es die zweitletzte ist - macht es die Prüfung von hinten wieder wett. Fällt grad auf - vermutlich kann ich Rückwärtslauf das gleiche machen.
- Das Continue: Logisch Danke.

[pertzschc]

Versuch es dochmal mit dem Algorythmus des längsten gemeinsames Teilstrings: hier.
Grüße,
Christoph

[Amateurprofi]

Hallo taveuni,
ich hatte ja schon per PN mitgeteilt, dass ich eine Vergleichsfunktion geschrieben habe, die recht flott arbeitet und hatte dich gebeten mir eine etwas größere Anzahl von Testdaten zur Verfügung zu stellen, um meine Funktion zu testen.
Du hattest mir daraufhin eine Datei mit 200000 echten Scan-Daten gesandt.
Ja, das war nun wirklich eine "etwas größere Anzahl".
Danke dafür.

Ich habe dann jeden dieser Teststrings gegen jedem anderen aus der Liste geprüft, insgesamt ca. 40E9 Vergleiche (hat 42 Minuten gebraucht).

Die Vergleiche habe ich durchgeführt
- Mit deiner Routine. (genauer mit einer Routine die ich aus deinem Code extrahiert habe)
- Mit meiner Pascal Routine.
- Mit meiner Asm Routine.

Anfangs gab es Fehlermeldungen weil deine Routine andere Ergebnisse brachte, als meine beiden Routinen.

Beispiel:
MCB6551
MCB6554
Deine Routine lieferte False, meine beiden True (und korrekt ist True).

Woran lags?!

Delphi-Quellcode:

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

cntForward ist jetzt = 6.
Im folgenden Teil werden die jeweils letzten Zeichen der Texte verglichen, also 1 vs. 4.

Delphi-Quellcode:

// 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;

Da die Zeichen nicht übereinstimmen, kommt das Break zum tragen und die Prüfung, ob cntForward+ cntBackward >= Length(StrBase) -1 ist, wird nicht ausgeführt.

Also: Wenn bei Texten gleicher Länge nur die jeweils letzten Zeichen abweichen, liefert die Routine False statt True.

Ich hab dann nach dem CheckForward eingefügt:

Delphi-Quellcode:

if (lBase = lComp) and (cntForward=lBase-1) then begin
   Result:=True;
   Exit;
end;

Der nächste Fehler kam bei
NE11925
NE1925

Deine Routine lieferte False, meine beiden dagegen True (und korrekt ist True)

Woran lag es?!
Beim Vorwärtszählen wird cntForward = 3.
Beim Rückwärtszählen ist nach Übereinstimmung der beiden 9nen cntBackward = 3 und Result wird = True gesetzt, weil cntForward + cntBackward = Length(StrBase) ist.
Jedoch wird das Rückwärtszählen nicht abgebrochen. Nachdem auch die vor den 9nen stehenden Zeichen gleich sind, ist dann cntBackward = 4 und Result wird = False gesetzt, weil cntForward + cntBackward nicht = Length(StrBase) ist.

Dieser Fehler tritt bei Texte unterschiedlicher Länge genau dann auf, wenn das Zeichen, mit dem das Vorwärtszählen beendet wird (hier die 1), im längeren Text doppelt vorkommt, und die dann folgenden Zeichen (rückwärts betrachtet) identisch sind.

Lösung auf dir Schnelle:
hinter

Delphi-Quellcode:

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

einfügen

Delphi-Quellcode:

if Result then Exit;

Danach wurde die gesamte Prüfung ohne Abweichungen abgearbeitet, also alle 3 Routinen lieferten identische Ergebnisse.

Und nachstehend sind meine beiden Vergleichsroutinen.
Die Pascal Routine arbeitet deutlich schneller als deine, Faktor zwischen 2 und 4 (Bei wiederholten Testen kommen recht unterschiedliche Laufzeiten).
Die Asm-Routine ist dann noch einmal ca. 25 % schneller.

Delphi-Quellcode:

FUNCTION Compare(const S1,S2:String):Boolean;
var I,J,L1,L2:Integer;
begin
   Result:=False;
   if (S1='') or (S2='') then Exit;
   L1:=Length(S1);
   L2:=Length(S2);
   J:=L1-L2;
   case J of
      0  :  for I:=1 to L1 do  // beide gleich lang
               if S1[I]<>S2[I] then
                  if J=1 then Exit
                     else J:=1;
      1  :  begin
               I:=0;
               while J<=L2 do // S2 um 1 kürzer als S1
                  if S2[J]=S1[J+I] then Inc(J)
                     else if I>0 then Exit
                        else I:=1;
            end;
      -1  : begin
               I:=1;
               J:=0;
               while I<=L1 do // S1 um 1 kürzer als S2
                  if S1[I]=S2[I+J] then Inc(I)
                     else if J>0 then Exit
                        else J:=1;
            end;
      else  Exit;
   end;
   Result:=True;
end;

Code:

FUNCTION CompareAsm(const S1,S2:String):Boolean;
asm
               test     eax,eax
               jz       @Ret                 // S1 leer
               test     edx,edx
               jz       @RetFalse            // S2 leer
               mov      ecx,[eax-4]          // Length(S1)
               sub      ecx,[edx-4]          // Length(S1)-Length(S2)
               je       @SameLen
               ja       @Longer              // S1 ist länger
               cmp      ecx,-1
               jne      @RetFalse            // Längendifferenz>1
               jmp      @DifferentLen
@Longer:       cmp      ecx,1
               jne      @RetFalse            // Längendifferenz>1
               xchg     eax,edx              // EAX <--> EDX
@DifferentLen: // Längen unterscheiden sich um 1.
               // EAX=Kürzerer String, EDX=Längerer String
               push     ebx
               mov      ecx,[eax-4]
               lea      eax,[eax+ecx*2]      // Hinter S1
               lea      edx,[edx+ecx*2]      // Auf letztes Zeichen von S2
               neg      ecx
@DLLoop1:      mov      bx,[eax+ecx*2]       // Zeichen aus S1
               cmp      bx,[edx+ecx*2]       // vs. Zeichen aus S2
               jne      @DLNotFound
               add      ecx,1
               jl       @DLLoop1
               jmp      @True
@DLNotFound:   add      edx,2                // Hinter S2
               jmp      @DLEntry
@DLLoop2:      mov      bx,[eax+ecx*2]       // Zeichen aus S1
@DLEntry:      cmp      bx,[edx+ecx*2]       // vs. Zeichen aus S2
               jne      @False
               add      ecx,1
               jl       @DLLoop2
               jmp      @True
@SameLen:      // Längen sind gleich
               push     ebx
               mov      ecx,[eax-4]
               lea      eax,[eax+ecx*2]      // Hinter S1
               lea      edx,[edx+ecx*2]      // Hinter S2
               neg      ecx
@SLLoop1:      mov      bx,[eax+ecx*2]       // Zeichen aus S1
               cmp      bx,[edx+ecx*2]       // vs. Zeichen aus S2
               jne      @SLNext
               add      ecx,1
               jl       @SLLoop1
               jmp      @True
@SLLoop2:      mov      bx,[eax+ecx*2]       // Zeichen aus S1
               cmp      bx,[edx+ecx*2]       // vs. Zeichen aus S2
               jne      @False
@SLNext:       add      ecx,1
               jl       @SLLoop2
@True:         mov      eax,1
               pop      ebx
               jmp      @Ret
@False:        pop      ebx
@RetFalse:     xor      eax,eax
@Ret:
end;

[taveuni]

Hallo Klaus,
Wie schon per PN mitgeteilt - vielen Dank für Deinen Input. Ich werde Deine Funktion übernehmen da der Performancegewinn beträchtlich ist. Die Fehler in meiner Routine hatten wir mit Tests übrigens ebenfalls bereits bereinigt.

Zu Deinen Gedanken:
Der Pool besteht aus Objekten welche primär in einer generischen Objektliste liegen. Bei einem Match oder neu eben einer Ähnlichkeit gibt die übergeordnete Funktion dem Aufrufer das gefundende Objekt als Clone zurück. Am Schluss wird selbstverständlich dieses Objekt aus dem Pool gelöscht.

Der Fall dass mehrere ähnliche Objekte im Pool sein könnten - darüber müssen wir uns zu einem späteren Zeitpunkt Gedanken machen.

Besten Dank!

Gruss Werner