Schneller Stringvergleich nach bestimmtem Muster

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