Schwieriges (REGEX?) Problem bei Stringanalyse

[schic]

Hallo,

ich habe ein schwieriges Regular-Expression Problem. Zum Hintergrund: Ich muss ein Referenz-String mit einem OCR-String vergleichen. Im OCR-String (Aus einem Optical-Character Recognition System) können somit unsinnige Buchstabenzusammensetzungen wie |< für K oder statt l ein | stehen. Meine Aufgabe ist es festzustellen, wie viele und welche Buchstaben im Referenz-String falsch vom OCR-System erkannt wurden. Das schwierige ist, dass beide Strings u.U. nicht gleich lang sind, da z.B. ein K als l< im OCR-String repräsentiert wird.
Beispiel 1:
Referenz: Multifunktionsarmlehne
OCR: MuLtifunl<tionsarmLehne
Hier wurden genau 3 Stellen nicht richtig erkannt, nämlich l,k und l.
Beispiel 2:
Referenz: Korrektursignal
OCR: Korrel<tursignal
Hier wurde 1 Stelle nicht richtig erkannt, nämlich k.
Wie kann ich das Problem elegant lösen?

Danke schonmal für eure Hilfe

 

[chmee]

Nun, ist Dir Groß-/Kleinschreibung wichtig? Damit wären schon einige Fehler weg.

Möglicherweise ist Regex nicht die Lösung sondern andere Algorithmen wie zB

• Hamming-Abstand - http://de.wikipedia.org/wiki/Hamming-Abstand
• Levenshtein-Distanz - http://de.wikipedia.org/wiki/Levenshtein-Distanz

mfg chmee

 

[HonniCilest]

StringUtils besitzt übrigens auch eine Methode um die von chmee erwähnte Levenshtein-Distanz zu berechnen...

Wenn ich das Problem lösen müsste, dann würde ich spontan an einen Backtracking-Algorithmus denken. Dieser kann durchaus auf Regex basieren, ist Regex aber deine eigene Idee oder tatsächlich eine Anforderung?

 

[Thomas Darimont]

Hallo,


also du hast einen Referenz String gegeben und einen OCR Ergebnis String. In diesen beiden Strings möchtest du nach dem obigen Beispiel die unterschiede finden / markieren.

Dazu würde ich googles Diff-Patch-Match Algorithmus verwenden:
http://code.google.com/p/google-diff-match-patch/
http://neil.fraser.name/software/diff_match_patch/svn/trunk/demos/demo_diff.html

Gruß Tom