2006/4 | Fachbeitrag | Suchmaschine

Suchen: gewusst wie

von Benno Nieswand

Von Benno Nieswand

Inhaltsübersicht:

• Fehlertolerante Datenbanken unterstützen den Anwender bei seiner Recherche
• Erfassen neuer Daten und Dokumente
• Integration in vorhandene Datenbanken

Dass die Internetrecherche in den letzten Jahren einfacher geworden ist, verdanken wir den Suchmaschinen. Sie durchforsten Datenbanken, zeigen dem Nutzer jedoch nicht immer die gewünschten Treffer an. Denn meist muss er wissen, wie die Daten und Dokumente in der Datenbank eingetragen wurden. Sind beispielsweise die Umlaute in oe, ae und ue aufgelöst oder blieben sie erhalten? Ob Tippfehler, neue Rechtschreibung, Wortverdreher, Wortgruppierungen - es gibt viele Ursachen für solche "Fehleingaben". Wenn das Suchsystem diese Fälle nicht sinngemäß tolerieren kann, werden keine oder falsche Ergebnisse geliefert. Eine erfolglose Suche ist frustrierend. In der Regel beschwert sich kein Anwender darüber, dass er alles korrekt eingeben muss. Er kennt es von einem Computer nicht anders und ärgert sich im Stillen. Die Konsequenzen einer nicht auffindbaren Information sind allerdings nicht unerheblich. Mancher Kunde eines Online-Shops wird nach wiederholter fehlgeschlagener Suche künftig seinen Warenkorb in einem anderen Laden bestücken. Aber auch unternehmensintern gilt: Können IT-Anwendungen nicht voll ausgeschöpft werden, nehmen die Nutzer sie nicht an. Und das bedeutet erhebliche Kosten.

<script language="javascript" type="text/javascript">

Fehlertolerante Datenbanken unterstützen den Anwender bei seiner Recherche

Populäre Internetsuchmaschinen machen den Anwender durch den Hinweis "Meinten Sie:" auf mögliche Irrtümer aufmerksam (zum Beispiel Google). Wird zu einem Suchbegriff keine überzeugende Zahl an Webseiten gefunden, erhält der Nutzer einen alternativen Vorschlag. Ein Programm im Hintergrund sucht hierfür Ausdrücke, die zwar anders geschrieben, aber doch gleich oder ähnlich ausgesprochen werden. Oftmals wird dabei eine ausschließlich „phonetische Suche“ eingesetzt. Man kann von einem Programm dieser Art also erwarten, dass es bei einer Suche nach "Ritmus" als Alternative "Rhythmus" anbietet oder von sich aus den Ausdruck "Rhythmus" in die Suche einschließt. Bei einer Recherche nach "Meyer" sollte auch "Mayer" mit einbezogen werden und bei einer Suche nach "Operhausen“ auch "Oberhausen".

• Doch auch dieser Lösungsansatz verzeiht die Eingabefehler der Anwender nur begrenzt. Er basiert auf vorher festgelegten Regeln, die beispielsweise definieren, dass „ey“ und „ay“ gleichwertig zu behandeln sind. Dieses Vorgehen ist in dreierlei Hinsicht problematisch:
• Regeln erfassen immer nur die vorhersehbaren Fehler. Die meisten Fehler sind jedoch unerwartet und statistisch nicht relevant.
• Regeln beschreiben einen Sachverhalt nur durch die Klassifizierung von schwarz/weiß. Das heißt, sie treffen zu oder nicht. Folglich könnte ein kleiner Fehler einen Treffer unmöglich machen. Beispiel: Wenn „ey“ versehentlich als „ye“ eingegeben wird, funktioniert eine solche Regel schon nicht mehr.
• Regeln können zu sehr langen Abfragezeiten führen. Da sie begrenzt sind, hegte man die Hoffnung, dass Systeme selber lernen und weitere Regeln hinzufügen könnten. Stichwort: Künstliche Intelligenz. Dieser Ansatz führt zwar in Einzelfällen zu verblüffenden Ergebnissen, aber das Regelwerk wird schnell zu rechenintensiv, ist nicht mehr transparent und damit nicht mehr handhabbar und optimierbar.
  

Der dritte Ansatz zur Fehlertoleranz, der algorithmische Ansatz, hat nicht die Probleme der regelbasierten und statistischen Verfahren. Beim algorithmischen Ansatz wird die Ähnlichkeit einer Anfrage mit allen Datenbankeinträgen mittels eines definierten Algorithmus verglichen. Dabei gibt es verschiedene Vorgehensweisen: die Feature-basierten Techniken, auch Assoziative Speicher genannt, und die Ganzwort-Algorithmen wie die Edit-Distanz-Berechnung. Erstere sind aus verschiedenen Gründen für den Einsatz in der Optischen Zeichenerkennung (OCR) nicht geeignet. Bei den Ganzwort-Algorithmen ist die Edit-Distanz anerkannterweise die sinnvollste. Dabei wird die Ähnlichkeit von Begriffen auf der Basis der einzelnen Buchstaben der Anfrage und der Reihenfolge dieser Buchstaben einerseits sowie einem Datenbankeintrag andererseits berechnet. Dieser Ansatz wird daher von Wissenschaftlern als die optimale Lösung angesehen. Problematisch war bisher, dass der Algorithmus nicht effizient und schnell implementiert werden konnte und somit völlig ungeeignet für Datenbanken mit 100.000 oder mehr Einträgen war.

Inzwischen ist es einigen Unternehmen gelungen, die Edit-Distanz effizient zu implementieren und diese darüber hinaus auch mit anderen Algorithmen zu kombinieren. Derartige Lösungen können auf viele spezielle Situationen angepasst werden. Es ist daher möglich, dass bei einer Datenbank mit 38 Millionen Adressdaten die Antwortzeit bei 150 Millisekunden liegt, auch wenn alle Datenbankfelder gleichzeitig mit OCR-Fehlern gespickt abgefragt werden. Wertvoll wird der algorithmische Ansatz insbesondere durch den Mehrfeld-Querabgleich, mit dem sich fehlerhafte Ergebnisse aus mehreren Feldern miteinander korrelieren und bewerten lassen. Der Kontext bleibt erhalten. Wenn ein Leseergebnis wie „?lebvrg?r Slr – ?re?kfart“ ? --> automatisch in „Dieburger Str. – Frankfurt“ korrigiert werden kann, bedeutet das die Einsparung enormer Kosten in der manuellen Nachbearbeitung.

Erfassen neuer Daten und Dokumente

Im Bereich OCR/Datenerfassung werden die Kosten mit approximativen Datenbankzugriffen gesenkt, weil sie die Automatisierungsrate steigern. Datenbanken, die bereits bei der Eingabe automatisch gegen bestehende Inhalte abgleichen, minimieren von Anfang an die Fehlerquote bei neuen Daten und Dokumenten. Ein Beispiel hierfür ist das Anlegen und die Pflege von Adressdatenbanken. Der Suchende erhält als Ergebnis eine nach Übereinstimmungsgrad geordnete Trefferliste. Zusätzlich bietet die Datenbank auch eine Liste alternativer, ähnlich geschriebener Termini, in der der Nutzer die Schreibweise des gemeinten Suchbegriffs ermitteln und eine weitere Recherche anstoßen kann. Die eingesetzte Software legt dazu einen eigenen Index über den Datenbestand an und erzielt dadurch performante Ergebnisse. Fehlerhafte Eingaben gehören somit künftig der Vergangenheit an und die Qualität der Einträge wird um ein Vielfaches gesteigert. Zugleich entfällt der Arbeitsaufwand, per Hand fehlerhafte Adressen oder Artikelbezeichnungen korrigieren zu müssen.

Integration in vorhandene Datenbanken

In der Regel laufen die performanten Systeme unabhängig von einer Datenbank. Die Suche wird der Datenbank vorgeschaltet, findet im RAM-Speicher statt und verweist dann auf die Datenbank. Die Datenbank-Architektur muss daher nicht geändert werden. Dadurch lässt sich der Integrationsaufwand gering halten. Die Anbindung einer OCR-Validierung dauert zirka einen Tag. Bei einer Suchlösung, beispielsweise für ein Archiv, sollte man mit zwei Tagen rechnen.