Schneller Stringvergleich nach bestimmtem Muster

[taveuni]

Zitat von jobo:

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 von jobo:

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 von BUG:

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 von BUG:

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 von taveuni:

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 von jobo:

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 von taveuni:

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 von taveuni:

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.