Assoziative Datenbanken |
Bei der Klassifikation handgeschriebener Zeichen treten häufig mehrdeutige
Fälle auf, d.h. ein einzelnes Zeichen kann mehrere verschiedene
Interpretationen haben, z.B. sind die Schreibweisen der Ziffern ''1'' und
''7'' bei manchen
Schreibern sehr ähnlich. Solche Mehrdeutigkeiten können aber oft
aufgelöst werden, wenn Kontextinformationen zur Verfügung stehen.
So kann im obigen Beispiel eine Entscheidung getroffen werden, wenn
die betrachtete Ziffer Teil einer Bankleitzahl ist und nur eine der beiden
Möglichkeiten eine existierende Bankleitzahl ergibt.
Ausgehend von der Handschriftenerkennung wurde deshalb im Sommer 1995 mit der
Entwicklung der assoziativen Datenbank DACCORD begonnen. Das Ziel war dabei
eine hocheffiziente, portable Anwendung, die auch auf Standard-PCs eine
hohe Verarbeitungsgeschwindigkeit bei großen Datenbankvolumina erzielt.
Diese Eigenschaften führten zu einem schnellen Einsatz bei einer deutschen
Großbank, wo pro Sekunde bis zu 10 Banküberweisungsformulare
basierend auf Datenbanken mit ca. 2.5 Millionen Konten auf einem
PC unter Microsoft Windows NT verarbeitet werden.
Durch schlechte Leseergebnisse bei schwierigen Handschriften
oder die Ausgabe von mehreren Alternativen
nach der Klassifikation wird der Suchraum stark vergrößert.
Datenbanken in der Größenordnung von bis zu 2 GByte können
dann nur durch die Entwicklung schneller Hash-Algorithmen in brauchbarer Zeit
durchsucht werden. Diese erlauben es schon mit wenigen Operationen
festzustellen, ob ein String in der Datenbank vorkommt.
Der Vergleich von Datenbankeinträgen mit den Leseergebnissen geschieht auf
Basis der Levenshteindistanz. Diese stellt ein Maß für
die Abweichung zweier Zeichenketten dar.
Dabei wird die erste Zeichenkette durch aufeinanderfolgende Einfüge
und Löschoperationen in die Zielzeichenkette überführt.
Für die verschiedenen Operationen können dann Kosten vorgegeben
werden. Die aufsummierten Kosten ergeben die gesuchte Distanz. In unserer
Arbeit wurde die Berechnung der Levenshtein-Distanz zu einem Einzelwortabgleich
erweitert, bei dem zu jedem Wort des Quelltextes ein möglichst guter
Match im Zieltext gesucht wird. Aus den einzelnen Distanzen wird dann
zusammen mit den Längen der Einzelworte über verschiedene Gewichte
ein Distanzmaß bestimmt.
|
