Schneller Stringvergleich nach bestimmtem Muster

[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.