Fehlerkorrektur von Zeichenketten - Algorithmus o. Whitepaper gesucht

[hanvas]

Hallo ich habe folgendes Problem :

ich möchte bei Zeichenketten die per OCR/ICR gelesen werden, mit fest definierter Struktur [1] eine Fehlerkorrektur durchführen. Dazu erfasse ich die Struktur in einer einfachen Maske die für jede gültige Stelle der zu bearbeitenden Zeichenkette definiert welche Zeichen zulässig sind. Wenn die vorliegende Zeichenkette die gleiche Anzahl Ziffern und Zeichen hat wie die Maske ist die Korrektur einfach - es wird einfach das "ähnlichste" erlaubte Zeichen zu einem gefundenen unerlaubten Zeichen gesucht.

Aber gibt es eine Lösung wenn zu viele oder zu wenig Zeichen vorliegen um herauszufinden welche(s) Zeichen an welcher Position mit der größten Wahrscheinlichkeit gelöscht bzw. eingefügt werden muss. Im Falle von Einfügevorgängen ist die wahrscheinliche Position wichtiger als das einzufügende Zeichen, denn das Zeichen kann ich aufgrund der fehlenden Information wahrscheinlich eh nicht bestimmen. Die (wahrscheinliche) Position würde mir aber unter Umständen dabei helfen die Zeichenkette in Gruppen von Zeichen aufzuteilen da im (häufig vorkommenden) dritten Beispiel der naive Ansatz von links nach rechts scheitert.

Beispiele

Erkannte Zeichenkette SNI'7GVSO028
Gesuchte Zeichenkette SNI176VS00028
Korrigierte Zeichenkette SNI176VS0028 -

ein Zeichen zu wenig

Erkannte Zeichenkette SNI'702SO0028I
Gesuchte Zeichenkette SNI176VS00028
Korrigierte Zeichenkette SNI170QS000281 -

ein Zeichen zu viel und falsch korrigiert aber vermutlich nicht besser hinzubekommen

Erkannte Zeichenkette SNI'7G|VS-O0281
Gesuchte Zeichenkette SNI176VS00028
Korrigierte Zeichenkette SNI176IV800281

Das eigentliche Problem, es gibt eine Reihe von Lösungen wie die Beste herausfinden.

Ich bin für jeden Hinweis dankbar

cu Ha-Jö


[1] zum Beispiel Entsorgungsnachweisnummern, gilt aber genauso für andere Strukturen

http://www.lung.mv-regierung.de/date...rlass_2015.pdf

1. Stelle - E oder S (Entsorgungsnachweis / Sammelentsorgungsnachweis)
2. Stelle - N
3. Stelle - Landeskennzeichen
4. Stelle - Kreis Nummer (1.Stelle der Kreisnummer)
5. Stelle - Kreis Nummer (2.Stelle der Kreisnummer)
6-12 Stelle - Fortlaufende rechtsbündige Zählernummer
oder
6 Stelle - Von der Behörde vergebene Kennziffer (ABCDEFGHIJKLMNOPQRSTUVWXYZ)
7 Stelle - Art der Anlage (HKSMZCBRVDUTAEFGI)
8-9 Stelle - Fortlaufende Zählnummer
10-12 Stelle - Fortlaufende Zählbuchstaben und Ziffernfolgen

Daraus ergibt sich folgende Maske für die Entsorgungsnachweisnummer ([[ trennen immer eine Stelle der Zeichenkette ab, # ist numerisch ? ist Alphabetisch )

[[ES[[N[[ABCDEFGHIKLMNPRS[[0123456789[[0123456789[[ABCDEFGHIJKLMNOPQRSTUVWXYZ[[HKSMZCBRVDUTAEFGI[[0123456789[[0123456789[[#?[[#?[[#