(MySQL): Bewährte Lösungen für fehlerkorrgierende Suche?

[AllesMeins]

Hi,

ich möchte bei einer Datenbank möglichst doppelte Einträge vermeiden. Um dieses Ziel zu erreichen will ich vor dem Eintragen prüfen ob bereits sehr ähnliche Einträge in der Datenbank sind und falls ja diese ausgeben. Dazu habe ich schon etwas mit LIKE, Wildcarts und SOUNDEX() rumgspielt. Aber leider komme ich da zu keinem wirklich guten Ergebniss. Entweder das ganze ist viel zu locker und spuckt quasi die komplette Datenbank wieder aus (passiert gerne bei der Arbeit mit SOUNDEX()) oder aber viel zu restriktiv, so das beispielsweise beim bergiff "Freimburg" nicht "Freiburg" gefunden wird. Nun bin ich etwas frustriert und außerdem überzeugt, das ich doch bestimmt nicht der erste bin, der soetwas realisieren will.
Gibt es für eine derartige Funktion vielleicht schon gute Anleitungen, Beispielabfragen oder gar ganze (PHP-)Klassen die sich bewährt haben (bzw. in denen einfach mehr Wissen und Zeit steckt, als ich da rein investieren möchte)?

Marc

[Rouven]

Hi,

du wirst entweder dich oder mich gleich erschießen wollen... String-Matching lautet dein Stichwort, die Algorithmen sind eigentlich (ich musste sie mal für ne Prüfung lernen) relativ einfach. Datenbanken unterstützen sie allerdings eher nicht von Haus aus, d.h. es liefe auf eine Prüfung mittels PHP o.ä. raus.

MfG
Rouven

[Hamster]

ich möchte bei einer Datenbank möglichst doppelte Einträge vermeiden.

Das ist ein aussergewöhnlich grosses Problem mit mehreren Aspekten.

Der erste ist der "physikalische", d.h. es ist sicherzustellen, dass die unterschiedlichen in der Realitaet vorgefundenen Entitäten auch tatsächlich unterschiedlich sind. Der Mensch irrt beim Unterscheiden typischerweise, bspw. kommt es zur Doppelt- oder Mehrfacherfassung von Firmen, Orten, Personen und was alles sonst noch so kreucht und fleucht. Ebenfalls bildet er Entitäten indem er eigentlich unterschiedliche Entitäten zusammenfasst, bspw. habe ich jahrelang zwei unterschiedliche Personen als eine einzige "geführt" (Herkunftsland Südamerika, brauchbar gutes Deutsch, ähnliches Aussehen). Dieser soziale Aspekt ist ganz primär mit sozialen Mitteln zu bearbeiten, IT kann da bestenfalls unterstützen.

Der zweite Aspekt ist IT-seitig zu bearbeiten, es geht wieder um die Mehrfacherfassung, diesmal aber, weil der Nutzer vom Erfassungssystem nicht hinreichend informiert wird über bereits erfasste Entitäten, d.h. der Erfassungsdialog ist unzureichend (ausreichend, also optimal, kann dieser allerdings auch nicht sein ;) . Nach meiner Erfahrung muss der Nutzer bei der Erfassung in einen Dialog (Suchmasken, Auswahlangebote, Trefferlisten) "hineingezwungen" werden, denn der Nutzer tendiert so zu sagen naturgemäss zur Mehrfacherfassung (aus Bequemlichkeit bspw. oder aus Unwissen über den Nutzen von Datenqualität).

Neben den o.g. präventiv zu beachtenden Massnahmen vor oder bei der Erfassung gibt es noch den Aspekt der Datenpflege. Diese ist (leider) auch nicht nur rein technisch zu bearbeiten sondern erfordert eine Portion Grips, d.h. der Mensch wird oft benötigt.

Stringvergleich und Vergleich von "harten Daten" (bspw. Geburtsdatum oder bestimmte IDs oder Kennungen (PassID)) schön und gut, aber letztlich wird qualifiziertes Personal benötigt. Das kannst auch Du sein. ;)
Ob es da vorgefertigte Tools bspw. für relationale Datenbanksysteme gibt, die etwas taugen, wage ich bezweifeln, denn die Datenbasen bzw. die dahinter steckenden Geschäftsmodelle scheinen mir zu unterschiedlich.
Du selbst könntest wohl die geeigneten Abfragen schreiben, allerdings sind die Mittel von SQL da recht eingeschränkt, vermutlich müsstest Du eigene Routinen schreiben in der Programmiersprache Deiner Wahl (PHP?).

Inhaltsanbieter (also diejenigen die strukturierte Daten verkaufen) jeglicher Art haben übrigens genau mit diesem Problem zu kämpfen. Da fällt mir gerade eine Geschichte ein mit einer Firma, die durch intensive Recherchen eine Produktdatenbank (möglichst viele Produkte möglichst vieler Hersteller) pflegt und grosse Schwierigkeiten mit der Aktualität, Qualität im allg. und der angestrebten Vollständigkeit hat...

[AllesMeins]

Hi,

ich erwarte ja nicht am Ende einen perfekten Datensatz zu haben. Das dies (mit rein technischen Methoden) nicht möglich ist, ist mir klar. Mir geht es eher um Erfahrungswerte beim Erstellen solcher "Folgende Einträge sind ähnlich"-Methoden. Also welcher Mix aus welchen Möglichkeiten hat sich bewährt und wie streng sollten diese Möglichkeiten eingestellt sein um weder zu sehr zu nerven aber auch nicht zu wenig auszugeben...
Das ist ja durchaus ein allgemeines Problem. Also um es auf Beispielhaft eine simple Größe zu bringen: Wäre es zum Beispiel sinnvoll nach 50% gleichen Buchstaben zu suchen oder doch eher 80%? Und in welcher Reihenfolge sollte man Abfragen: Ist zum Beispiel erst das komplette Wort, dann Teile des Wortes und dann Soundex sinnvoll? Falls ja, welche Schritte wären noch sinnvoll usw...
Ich denke das ist durchaus ein allgemeines Problem für das es Erfahrungswerte oder vorgefertigte Klassen geben könnte.

Marc

[Hamster]

Das ist ja durchaus ein allgemeines Problem.

Ich hab mal vor etlichen Jahren mit dem Doublettenfinden-Assistent von MS Access gearbeitet (war gar nicht _so_ schlecht). Weiss allerdings nicht, ob der noch lebt.

[MudGuard]

Hi,

ich möchte bei einer Datenbank möglichst doppelte Einträge vermeiden. Um dieses Ziel zu erreichen will ich vor dem Eintragen prüfen ob bereits sehr ähnliche Einträge in der Datenbank sind und falls ja diese ausgeben.

Du müßtest Dir zuerst mal Kriterien überlegen, die in Deinen Augen Ähnlichkeit bedeuten.
Um bei Deinem Freiburg-Beispiel zu bleiben:
Ist Freiberg ähnlich?
Oder Dreiburg?
Oder Rheinburg?
Oder Freibourg?
Oder Freihbourg?

Ist Phantasie ähnlich zu Fantasie?

Willst Du im Zweifelsfall lieber zuviele oder zuwenige ähnliche Strings finden? Das ist immer ein Balance-Akt - faßt man die Kriterien zu eng, werden sehr ähnliche Strings ausgeschlossen, faßt man sie zu weit, rutschen auch sehr abweichende Strings durch.

Was sich z.B. für Straßennamen gegen Postdaten bewährt hat:
Schreibweise erstmal normieren so wie die Post es bereits für die Sortier-Spalte gemacht hat (Uppercase, Sonderzeichen wie Leerzeichen oder Bindestriche weg, Umlaute in AE usw.,), d.h. aus Sankt-Cäcilien-Straße wird STCAECILIENSTR und erst dann einen Soundex darauf loszulassen.
Um dann nicht zu wilde Treffer zu bekommen, z.B. weitere Kriterien anwenden (normierter erster Buchstabe muß übereinstimmen)
(bei uns ging es aber darum, zu einem vom User gegebenen Straßennamen möglichst genau einen Straßennamen aus der Datenbank zu finden).

Man könnte z.B. auch noch Buchstabengruppen normieren wie PH zu F, CK zu K, TZ zu Z usw. Das kann aber u.U. dazu führen, daß seltsame Ergebnisse auftreten - aus Alphorn wird dann Alforn - wie gesagt, das ist immer ein Balance-Akt.

U.U. lohnt es sich, in der Datenbank eine zusätzliche Spalte für die "normierte" Schreibweise zu führen (das widerspricht zwar dem Prinzip, keine redundanten Daten in die Datenbank zu schreiben, kann aber die Query-Zeiten deutlich beeinflussen).

Gibt es für eine derartige Funktion vielleicht schon gute Anleitungen, Beispielabfragen oder gar ganze (PHP-)Klassen die sich bewährt haben

Es kommt vermutlich zu stark auf den Einzelfall an, was als ähnlich gilt, und ob es darum geht, aus der Menge der vorhandenen Strings den ähnlichsten zu finden oder alle, die ein bißchen (wieviel?) Ähnlichkeit haben, oder nur n ähnliche Strings oder ...

cu,
Andreas

[Hamster]

Ist Phantasie ähnlich zu Fantasie?

Richtig, ganz wichtig sind Erfassungsregeln, die vom mit der Erfassung beschäftigten Personal zu beachten sind, dieser Aspekt blieb bisher - so glaube ich zumindest - unbeachtet.
Also bspw. Firmen- oder Namenserfassung immer in der Form "<Nachname>, <Vorname> <ggf.Rechtsform>" und eben nicht "<Vorname> <Nachname> <ggf.Rechtsform>", Strassenerfassung in der Form "<Bezeichnung><strasse|weg|etc.>" aber nicht bspw. "<Bezeichnung><str.>".

U.U. lohnt es sich, in der Datenbank eine zusätzliche Spalte für die "normierte" Schreibweise zu führen (das widerspricht zwar dem Prinzip, keine redundanten Daten in die Datenbank zu schreiben, kann aber die Query-Zeiten deutlich beeinflussen).

Die Redundanzvermeidung ist ja ohnehin eher etwas für Theoretiker, selbstverständlich gehören berechnete Werte (nach Regeln, die sich ändern können) in die Datenhaltung, zn diesem Fall: Interessante Idee.