image2data

Der Tech-Blog

...weitermachen, wo OCR aufhört

Unscharfe Suche von Text in einem Text

Feb 022015

Eine ganz wichtige Funktion, um Suchbegriffe in Texten zu finden, ist die unscharfe Textsuche. Warum "unscharf"? Nun, OCR-Systeme liefern bei qualitativ schlechteren Belegen gerne mal ein "l" anstatt einer "1", eine "1" anstatt eines "I" oder ein "O" anstatt einer "0" (oder umgekehrt) zurück. Soll z.B. das Wort "Immenhorst KG" auf einem Beleg gefunden werden (z.B. um darauf ein bestimmtes Skript anzuwenden), die OCR hat aber "1mmenhorst KG" zurückgeliefert, dann würde eine normale Textsuche fehlschlagen.

image2data bietet hierfür die Funktion "i2dGetFuzzyTextPos", mit deren Hilfe eine unscharfe, d.h. fehlertolerante Textsuche ausgeführt werden kann. Ein Beispiel:

const
  ANYTEXT = 'Lorem ipsum dolor sit amet 1mmenhorst KG consetetur sadipscing elitr';
  SEARCHFOR = 'Immenhorst KG';
 
begin
  if i2dGetFuzzyTextPos(ANYTEXT, SEARCHFOR, 1, 1) > 0 then
    i2dDebugOut(Format('"%s" ist in "%s" vorhanden', [SEARCHFOR, ANYTEXT]));
end.

Obwohl in "ANYTEXT" das Wort "Immenhorst" falsch geschrieben (bzw. im Betrieb falsch "erkannt") wurde, ist die "if"-Bedingung doch wahr, da wir in dem Funktionsaufruf von "i2dGetFuzzyTextPos" mit einer Fehlertoleranz von 1 Fehler suchen. Der erste der beiden numerischen Parameter legt die Startposition fest, ab der gesucht werden soll, der zweite ist für die Fehlertoleranz zuständig.

Wie funktioniert das? Grundlage für diesen Algorithmus ist die sog. "Levenshtein-Distanz". Diese ermittelt, kurz gesagt, die Anzahl Ersetzungen im Suchbegriff, die notwendig wären, um den Begriff im Text zu finden. In "Haxxo" müssten zwei Ersetzungen vorgenommen werden, um diesen Text in "Hallo Welt" zu finden. Der entsprechende Code, um hierfür wäre also:

const
 ANYTEXT = 'Hallo Welt';
 SEARCHFOR = 'Haxxo';
 
begin
 if i2dGetFuzzyTextPos(ANYTEXT, SEARCHFOR, 1, <span style="background-color: #ff9900;">2</span>) > 0 then
 i2dDebugOut(Format('"%s" ist in "%s" vorhanden', [SEARCHFOR, ANYTEXT]));
end.

Atom

powered by Nibbleblog