Schneller Stringvergleich nach bestimmtem Muster

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

[taveuni]

Zitat von stahli:

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

Ja.

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

[jobo]

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

[taveuni]

Zitat von jobo:

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

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

Ich mach noch mal ein paar Versuche.

[jobo]

Zitat von taveuni:

Zitat von jobo:

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