Zur Hauptseite ... Zum Onlinearchiv ... Zum Abonnement ... Zum Newsletter ... Zu den Tools ... Zum Impressum ... Zum Login ...

Achtung: Dies ist nicht der vollständige Artikel, sondern nur ein paar Seiten davon. Wenn Sie hier nicht erfahren, was Sie wissen möchten, finden Sie am Ende Informationen darüber, wie Sie den ganzen Artikel lesen können.

Kompletten Artikel lesen?

Einfach für den Newsletter anmelden, dann lesen Sie schon in einer Minute den kompletten Artikel und erhalten die Beispieldatenbanken.

E-Mail:

Gedrucktes Heft

Diesen Beitrag finden Sie in Ausgabe 4/2010.

Unser Angebot für Sie!

Lesen Sie diesen Beitrag und 500 andere sofort im Onlinearchiv, und erhalten Sie alle zwei Monate brandheißes Access-Know-how auf 72 gedruckten Seiten! Plus attraktive Präsente, zum Beispiel das bald erscheinende Buch 'Access 2010 - Das Grundlagenbuch für Entwickler'!

Diesen Beitrag twittern

Zusammenfassung

Lernen Sie die Grundlagen der fehlertoleranten Suche und Techniken für den sofortigen Praxiseinsatz kennen.

Techniken

Suche, VBA

Voraussetzungen

Access 2000 und höher

Beispieldateien

FehlertoleranteSuche.zip

Shortlink

www.access-im-unternehmen.de/733

Fehlertolerantes Suchen

Sascha Trowitzsch, Berlin

"Firma Waren-Paradies, Konstanze Meyer am Apparat. Was kann ich für Sie tun?" - "Ja, Katschmarek. Ich hatte letzte Woche eine Bestellung aufgegeben; die möchte ich gerne stornieren." - "Wie war der Name?" - "Katschmarek!" Die Kundenbetreuerin Frau Meyer gibt den Namen in die Suchmaske des Kundenformulars ihrer Datenbank zur Bestellabwicklung ein. Die Datenbank findet den Kunden nicht. "Würden Sie den Namen bitte buchstabieren?" - "K-A-C-S-M-A-R-E-K" - "Mit C-S?" - "Ja, genau!” Ein Glück, dass Herr Kacsmarek nicht mit "Kaufmann-Anton-Cäsar-Samuel-Martha-..." antwortete, denn dann hätte Frau Meyer wahrscheinlich nochmals nachgefragt ...

Dieser Fall ist wohl nicht selten. Hat man nur das gesprochene Wort zur Verfügung, so dürfte man mit der korrekten Schreibweise gerade von Namen häufig überfordert sein. Eine Datenbank, die Begriffe nur anhand exakter Übereinstimmung vergleicht, wird dem nicht gerecht.

Dabei hätte der Entwickler der Datenbank Frau Meyer die Sache leichter machen können, wenn er Methoden zur fehlertoleranten Suche, eine "Unscharfsuche", eingebaut hätte. Solche Routinen versuchen, zwei Begriffe auf größtmögliche Übereinstimmung zu vergleichen, und geben die plausibelsten Treffer in einer Liste zurück, aus der man schließlich den wahrscheinlichsten auswählen kann.

Anwendungsbereiche für eine solche fehlertolerante Suche gibt es viele: Außer Nachnamen wären etwa Straßennamen Kandidaten, Bezeichnungen von Artikeln, Ländernamen oder selbst Telefonnummern, die Zahlendreher enthalten. Wenn auch Sie den Benutzern Ihrer Datenbanken ähnlichen Komfort bieten möchten, dann integrieren Sie einfach eine Lösung, wie die nachfolgend vorgestellte.

Was ist ähnlich?

Bevor man einen Algorithmus entwickelt, der zwei Strings auf Ähnlichkeit untersucht, muss man sich zunächst fragen, was unter "Ähnlichkeit" überhaupt zu verstehen ist. Was für den Cortex eines Menschen kein Problem zu sein scheint, bereitet dem Linguisten und erst recht dem Programmierer erhebliches Kopfzerbrechen.

Zudem kann die Fehlerquelle für falsche Schreibweise auch noch ganz unterschiedlich sein. Im Beispiel oben handelt es sich um ein phonetisches Problem: die Aussprache beider Begriffe ist identisch, ihre Länge unterscheidet sich aber um zwei Buchstaben. Von den Lauten her hat Frau Meyer nichts falsch gemacht.

Doch selbst dann, wenn sie ungarische Vorfahren hätte und die richtige Schreibweise wüsste, hätte ihr ein Schreibfehler unterlaufen und die Eingabe "Kascmarek" sein können - sie hat sich schlicht vertippt. Die Aufgabe liegt also darin, einerseits Schreib- und Tippfehler aufzufangen und andererseits phonetische Ähnlichkeiten zu erkennen.

Die rein programmtechnische Frage ist außerdem, wie eine Ähnlichkeitsfunktion das Maß der Übereinstimmung widergeben soll. Es haben sich hier zwei Verfahren eingebürgert, die sinnbildlich so aussehen:

fuSimilar ("Begriff1" , "Begriff2") = TRUE oder FALSE

fuSimilar ("Begriff1" , "Begriff2") = 0...100

Im ersten Fall sagt die Funktion lediglich, ob die Begriffe überhaupt ähnlich sind oder nicht (Ja oder Nein).

Im zweiten wird ein Wert zurückgegeben, der mit 100 völlige Übereinstimmung, mit 0 überhaupt keine und dazwischen teilweise Übereinstimmung feststellt.

Phonetik

Viele Algorithmen spezialisieren sich darauf, Begriffe zu vergleichen, die gleich oder möglichst ähnlich ausgesprochen werden. Dazu werden, bevor es zum eigentlichen String-Vergleich kommt, zunächst beide Begriffe einer phonetischen Analyse unterzogen.

Nehmen wir mal den Namen "Becker". Hier besteht die deutsche Eigentümlichkeit darin, dass ein "CK" genau so ausgesprochen wird, wie das "K" allein. Man könnte den String also analysieren und das "CK" zunächst durch ein "K" ersetzen.

Nach dieser Vorbehandlung wären die beiden Begriffe "Becker" und "Beker" identisch. Ein Algorithmus mit phonetischem Präprozessor würde nun den Wert 100 für den Vergleich zurückgeben.

Da dies nicht wirklich zutrifft, ziehen die gängigen Algorithmen hier einfach einen kleinen Ausgleichswert ab - etwa 10 -, falls der Präprozessor tatsächlich an den Eingangs-Strings geschraubt hat. In diesem Fall wäre das Ergebnis folglich 90, was man als "so gut wie, aber nicht identisch" interpretieren könnte.

Das Beispiel bietet noch mehr Potenzial: Im Deutschen lauten "E" und "Ä" gleich. Somit kann ein "Ä" ebenfalls durch ein "E" ersetzt werden. Das "Ä" wiederum könnte auch umlautlos als "AE" daherkommen. Folgende Namen wären dann nach Durchlaufen des Präprozessors identisch:

"Becker", "Beker", "Bäker", "Bäcker", "Baeker", "Baecker"

Alle sechs resultierten im vorbehandelten String "Beker".

Zu überlegen wäre auch, ob nicht Vokalverdoppelungen reduziert werden könnten:

"Beeker" > "Beker"

Das Spiel kann beliebig fortgesetzt werden. So ist die Endung "er" im Deutschen etwa weitgehend lautgleich mit "a". Aus "Becker" würde "Beka".

Damit das funktioniert, reicht ein einfaches Replace auf die Eingangs-Strings allerdings nicht aus. Soll alles korrekt laufen, so muss ein Begriff eigentlich in Silben aufgetrennt, die Position einer Zeichenkombination ermittelt und außerdem analysiert werden, ob vor einer Konsonantenkombination ein Vokal steht oder nicht.

Und damit wären wir schon bei den Nachteilen eines phonetischen Präprozessors: Die Berechnung kostet sehr viel Zeit und ist nicht sehr zuverlässig, weil etwa eine Silbentrennung nicht mit hinreichender Performance zu bewerkstelligen ist.

Außerdem funktioniert der phonetische Präprozessor nur für eine bestimmte Sprache. Im Slawischen etwa würde der Name "Becker" eher wie "Betschker" ausgesprochen. Wäre die Zielsprache also Serbisch, so benötigte man dafür einen völlig anderen Präprozessor.

Gerade für Namensvergleiche eignet sich das Verfahren daher weniger, weil - siehe Eingangsbeispiel "Kacsmarek" - internationale Namen im deutschen Sprachraum immer häufiger vorkommen.

Aus Performancegründen verwenden Ähnlichkeitsalgorithmen deshalb normalerweise nur sehr einfache phonetische Präprozessoren. Im Ergebnis sind sie dann mal besser, mal schlechter als Algorithmen ohne Präprozessor. Es kommt immer auf den genauen Anwendungsbereich an, ob man sie einsetzen sollte oder nicht.

In der später vorgestellten Demo können Sie sich selbst ein Bild davon machen. Zwei der verwendeten Algorithmen können optional auch mit phonetischem Präprozessor betrieben werden. Testen Sie einfach, ob die phonetische Vorbehandlung etwas bringt.

Vertippt

Sie kennen das sicher: Sie tippen schnell mal ein Wort in die Tastatur und haben schließlich statt "Becker" den Text "Bekcer" auf dem Schirm - ein Verdreher. Oder die letzte Taste wurde nicht richtig gedrückt, was "Becke" zum Ergebnis hat.

Aufgabe der Datenbank soll nun sein, trotzdem den beabsichtigten Begriff zu finden. Wie kann man das anstellen?

Ähnlichkeitsalgorithmen

Fast alle gängigen Algorithmen verwenden für unseren Zweck das sogenannte Distanz-Verfahren. Am bekanntesten ist die Levenshtein-Distanz, benannt nach ihrem Schöpfer.

Dabei wird ermittelt, wie viele Zeichen der Eingangs-Strings jeweils an der gleichen Position genau übereinstimmen, beziehungsweise, ob sich eine übereinstimmende Position möglicherweise in der Nähe befindet.

Sehen wir uns "Becker" vs. "Bekcer" näher an (s. Abb. 1). An vier Positionen befinden sich übereinstimmende Zeichen, die den Gewichtungsfaktor 1 bekommen. Bei zwei Zeichen gibt es jeweils Übereinstimmung an um eins verschobenen Positionen. Diese werden nun willkürlich mit dem Faktor 0.5 belegt, was aussagen soll, dass eine mögliche Gleichheit besteht.

becker.png

Abb. 1: Vergleich von Becker und Bekcer

Bereits hier wird sichtbar, dass solche Berechnungen die Realität nur annähernd widerspiegeln und auf reinen, zum Teil stochastischen Annahmen beruhen. Und genau dies ist die Kunst solcher Algorithmen: Sie sollen dem, was ein Mensch als ähnlich empfindet, möglichst nahekommen.

Deshalb gibt es auch Hunderte solcher Verfahren, die sich manchmal nur in kleinen, aber wichtigen Details unterscheiden, und ganze Studienprojekte beschäftigen ihre Eleven mit der Optimierung solcher Routinen.

Wer hier einen näheren Blick riskieren will, der schaue sich auf der Seite von SimMetrics [1] um, einem Open-Source-Projekt der englischen Universität Sheffield. Dort sind zahlreiche Algorithmen in einem Projekt zusammengefasst und bewertet worden, das auch als Visual Studio.NET-Paket zur Verfügung steht.

Die jeweiligen Algorithmen sind darin übersichtlich in einzelnen C-Libraries abgelegt. Zur Warnung: Wie bei Uni-Projekten üblich, ist der Verständnis-Level hier nur eine Sache für wissenschaftlich Interessierte.

Um beim Beispiel zu bleiben - in Abb. 2 hat sich jemand noch mehr vertan. Die Buchstaben sind ziemlich durcheinander und doch erkennt man mit dem Auge auf einen Blick, dass Ähnlichkeit zwischen beiden Begriffen besteht, obwohl nur drei Zeichen an der korrekten Position übereinstimmen. Die anderen sind mehr oder weniger verschoben und dem tragen die Faktoren 0.5 und 0.25 Rechnung.

becker2.png

Abb. 2: Vergleich von Becker und Bekecr

Letztlich summiert man nun die Gewichtungsfaktoren und setzt sie in Beziehung zur durchschnittlichen Gesamtzahl an Zeichen beider Strings. Im letzten Beispiel:

f = 4.25/6 = 0.7083

Da die Rückgabewerte im Bereich von 0 bis 100 liegen sollen, wird dieses Ergebnis noch mit 100 multipliziert, gerundet und Sie erhalten 71.

In der praktischen Auswertung würde man nun ein Limit setzen und annehmen, dass etwa alle Ergebnisse oberhalb von 75 als hinreichend ähnlich anzusehen seien. In diesem Fall fiele das letzte Beispiel aus der Liste der plausiblen Ergebnisse heraus, das vorige aber genügte der Bedingung:

f = Round (5/6 * 100) = 83

Übrigens kommt derselbe Wert auch dann heraus, wenn man "Becker" und "Wecker" vergleicht. Dieses Ergebnis kann man schon weniger akzeptieren. Doch dafür gibt es leider keine Regel: Es hat sich stochastisch schlicht ergeben, dass der Anfangsbuchstabe seltener falsch geschrieben wird.

Sie haben das Ende des frei verfügbaren Teils des Artikels erreicht. Lesen Sie weiter, um zu erfahren, wie Sie den vollständigen Artikel lesen und auf viele hundert weitere Artikel zugreifen können.

Sind Sie Abonnent?Jetzt einloggen ...
 

Kompletten Artikel lesen?

Einfach für den Newsletter anmelden, dann lesen Sie schon in einer Minute den kompletten Artikel und erhalten die Beispieldatenbanken.

E-Mail:

Verwandte Beiträge:

Globale Suche

Suchfunktionen von einfach bis komplex

Suchformularassistent

Suchfunktion mit phonetischem Vergleich

Tipps und Tricks

Amazon Webservices per VBA nutzen

Suchformular für die Datenblattansicht

© 2003-2015 André Minhorst Alle Rechte vorbehalten.