und 
) verstanden:
Erkennung bibliographischer Dubletten mittels Trigrammen:
Messungen zur Performanz - Teil 1
von Harald Jele
1 Einleitung
Die Vorstellung, Ähnlichkeiten zwischen zu vergleichenden (bibliographischen) Datensätzen oder gar zwischen umfangreichen Dokumenten1 aufgrund von Ähnlichkeiten Ihrer "Bestandteile" feststellen und messen zu können, ist eine in der Literatur sowie in der Realisierung praktischer Werkzeuge zur Erkennung von Titel-Dubletten weit verbreitete.
Bereits in den frühen 1970er-Jahren2 konnte empirisch gezeigt werden, dass unter bestimmten Umständen ein günstig gewählter Ausschnitt von 55 Bytes pro bibliographischem Datensatz ausreichen kann, um ca. 5 eines Teilbestands von 214.000 Titelsätzen aus der damals aktuellen Datenbank des OCLC als Dubletten zu bestimmen.
Der Wahl des "günstigen Ausschnitts" als die zu definierende und im Weiteren als repräsentativ angesehene Teilmenge eines Datensatzes einerseits, sowie andererseits der Wahl der anzuwendenden Verrechnungsmethoden sind dabei besondere Aufmerksamkeit zu widmen.
In der vorliegenden Arbeit wurde eine zu ladende Menge von ca. 10.000 bibliographischen Datensätzen mit einer vorhandenen Menge von ca. 437.533 und in weiterer Folge mit einer größeren von ca. 4.5 Mio. verglichen. Das angestrebte Ziel dabei war, letztlich die zu vergleichenden Mengen dublettenfrei zusammenzuführen.
Dabei sollten vorrangig zwei Teilmengen identifiziert werden:
Die entsprechend dieser Vorgehensweise entstehende dritte Menge an Titeldatensätzen, die zwar Ähnlichkeiten, jedoch keine hinreichenden Übereinstimmungen aufwiesen, wurden so gekennzeichnet, dass diese im Anschluss auf Ähnlichkeiten intellektuell geprüft werden konnten.
Bei der Mengenbildung konnten 6.100 Datensätze als Dubletten identifiziert und eine in einem nächsten Schritt noch zu bestimmende Menge als neue, hinzuzufügende Datensätze bewertet werden.
Als eine eindeutige Titel-Dublette wurde hier ein Datensatz gewertet, dessen Einträge zur ISBN/ISSN, zur Jahres- sowie zur Auflagenzahl (gleichzeitig) vollständig mit einem zweiten übereinstimmten. Die Möglichkeit eines dann immer noch bestehenden Unterschieds wurde vernachlässigt und im Rahmen unserer Kenntnis der Datenlage als ein kalkulierbarer Fehler angesehen.
Zur Ermittlung bzw. Messung von Ähnlichkeiten wurden drei Verfahren herangezogen, deren Ergebnisse gegenüber gestellt wurden:
Beide Modelle sind als mathematische Modelle zur Auswertung von Vektordistanzen zwischen zu bildenen Mengen von Trigrammen definiert. Das heißt, dass beiden miteinander zu vergleichenden Datensätzen Inhalte entnommen, diese in weiterer Folge als Zeichenketten ("Strings") interpretiert und wie (mathematische) Vektoren behandelt werden.
Bei der Wahrnehmung deutlicher Unterschiede in den Ergebnissen der drei Modelle wurde jeweils das für die Entscheidungsfindung "schlechtere" Ergebnis (=das pessimistischere) gewählt.
Im Unterschied zu den in der Praxis gängigen Methoden der Zusammenführung bibliographischer Daten wurde hier kein Merge-Verfahren angewandt.
Bei einem solchen wird definiert, welche Kategorien aus dem dubletten bibliographischen Datensatz mit übernommen werden, bevor dieser ausgeschieden wird. Im Vorfeld war aufgrund der Datenlage zudem eindeutig geklärt, dass dublette Datensätze aus der Anfragemenge immer - und nie welche aus der Abfragemenge - ausgeschieden würden. Daher musste in weiterer Folge auch kein Gewinner/Verlierer-Konzept entwickelt werden, über das bestimmt wäre, welcher Datensatz bei Duplizität weitergeführt und welcher ausgeschieden würde.
Um gültige Aussagen auch zur Verrechnung größerer Datenmengen treffen zu können, wurde im Projektverlauf entschieden, im vorliegenden Text ausschließlich die Performanz4 der hier referierten Modelle zu messen.
Die Gültigkeit der erzielten Ergebnisse wird in einem nachzureichenden Text aufgrund der im Verfahren entstandenen umfangreichen empirischen Datenlage eigens ausführlich geprüft.
2 Der Einsatz von Trigrammen
Bei der Bildung von Trigrammen wird die Annahme verfolgt, dass die Ähnlichkeit zwischen zwei Zeichenketten dann gegeben ist, wenn ihre jeweiligen "Bestandteile" (=die einzelnen Zeichen in ihrer Abfolge) hinreichende Übereinstimmungen zueinander aufweisen.5
Zumindest für die mitteleuropäischen Sprachen scheint die Bestimmung von Ähnlichkeiten durch die Bildung von Trigrammen vorteilhafter als die Anwendung von 2- oder 4-Grammen zu sein. Dies lassen zumindest die empirischen Ergebnisse aus der gängigen Literatur vermuten.
4-Gramme "reagieren" im Üblichen zu stark auf "Buchstabendreher" innerhalb von Begriffen. Das heißt, dass durch die Verdrehung bloß zweier Zeichen innerhalb einer Zeichenkette das berechenbare Ähnlichkeitsmaß gegenüber der Berechnung mit Trigrammen deutlicher abnimmt als typischer Weise gewünscht. Damit tritt auch der Fall ein, dass morphologisch sehr ähnliche Wörter, die jedoch völlig verschiedenes bedeuten, mitunter ähnlicher gemessen werden als zwei idente Begriffe, die sich ausschließlich durch einen unbeabsichtigten Buchstabendreher unterscheiden.Buchstabendreher
2.1 Die Bildung von Trigrammen
Einem bibliographischen Datensatz werden in einem ersten Schritt Inhalte von bestimmten Kategorien entnommen, die im Wesentlichen Wörter bzw. Begriffe und Zahlen, sowie standardisierte Zeichenketten (wie z.B. die ISBN oder ein anderer, zum Vergleich geeigneter Standard-Eintrag wie evtl. eine Katalogkartennummer) darstellen. Diese werden anschließend sequentiell zu Einheiten von jeweils drei Schriftzeichen6 zerlegt, wobei die jeweils zwei letzten Zeichen eines Trigramms am Beginn des nächsten wiederholt werden. In unserem Fall werden führende sowie den Zeichenketten nachfolgende Leerzeichen (Blanks) mit in die Bildung der Trigramme aufgenommen. Sollte die Ähnlichkeit zweier Ein-Wort-Begriffe7 zueinander berechnet werden, wird darauf geachtet, diese Leerzeichen in jedem Fall den Zeichenketten am Wortanfang und -ende hinzuzufügen.
Dieses Verfahren kann an folgenden Begriffe einfach gezeigt werden.
Die Wörter Bauernmarkt und Marktbauern werden in ihre Trigramme zerlegt:
Zur weiteren Berechnung werden diese als mathematische Vektoren (hier
und ) verstanden:
Bei der anschließenden Berechnung der Ähnlichkeit dieser beiden Zeichenketten wird in den gewählten Verfahren von den in dieser Weise gebildeten Vektoren ausgegangen.
3 Zeichennormierung
Zwei eigentlich dublette Titel-Datensätze, die in weiterer Folge maschinell miteinander verglichen werden, können (unerwünscht) eine mathematisch geringe Ähnlichkeit zueinander dann aufweisen, wenn z.B. die in den jeweiligen Datensätzen angewandten Schreibweisen von einander abweichen. Allein leicht voneinander abweichende Varianten einer auch sehr ähnlichen Schreibweise können dazu führen, dass ein sinnvoller Schwellenwert nicht mehr ermittelbar ist, ab dem zwei miteinander zu vergleichende Datensätze als Dubletten eingeschätzt werden müssen.
Sollten den Erfassungsmethoden der zu vergleichenden Datensätze zudem verschiedene bibliothekarische Regelwerke zugrunde liegen, sind mitunter unterschiedliche Schreibweisen sogar prolongiert.
Aus diesem Grund werden in den gängigen Verfahren zur Ermittlung von bibliographischen Dubletten "Normierungen" eingesetzt, die eine feldspezifische Behandlung von Zeichen vorsehen, bevor diese sinnvoll miteinander verglichen werden können. Die Funktion der Normierung ist dabei allein in der "Nivellierung" der vorhandenen Differenzen zu sehen, möglichst ohne in die Semantik verändernd einzugreifen (Rusch 1999, S.3).
Aufgrund des Einsatzes unterschiedlicher Zeichensätze der hier zu vergleichenden Datenbestände (ISO-8859-1 = Latin1 versus UTF-8) wurde nach umfangreichen Analysen der sich daraus ergebenden Probleme entschieden, für den Vergleich beide in einen normierten Bestand überzuführen, der ausschließlich aus Zeichen aus dem 7-bit Zeichensatz ASCII, umgewandelt in Großbuchstaben, besteht.
Im Einzelnen bedeutet dies (vgl. ebda. S.5):
Die konkrete Anwendung der feldspezifischen Normierungsfunktionen folgte im Wesentlichen den Vorschlägen von Rusch (vgl. 1999, S.21-22). In ihrem Text wurde versucht, sämtliche, notwendige Vorgänge durch acht, sich teilweise ein wenig überschneidende Normierungsfunktionen abzubilden.
Exemplarisch können zur Veranschaulichung folgende Beispiele wiedergegeben werden:8
4 Die gewählten Berechnungsverfahren
Vektormodelle werden in der Literatur häufig zu Ähnlichkeitsberechungen von Zeichenketten herangezogen. Das Jaccard-Maß bzw. der Jaccard-Koeffizient lassen sich als Kennziffer leicht berechnen und scheinen für das Retrieval genauso gut wie für komplexere Aufgaben geeignet zu sein (vgl. Salton McGill 1987, S.217).
Der euklidische Abstand zweier Vektoren ist zur Berechnung von Ähnlichkeiten zweier oder mehrerer Zeichenketten neben dem Jaccard-Maß ein brauchbarer Ansatz. Zudem kann im deutschsprachigen Raum durchaus eine gewisse Renaissance dieser Methode zur Verrechnung bibliographischer Datensätze seit dem Erscheinen der Arbeit von Hylton (1996) wahrgenommen werden.
Wie bereits eingangs angemerkt, wird die Berechnung des Ähnlichkeitswerts des KOBV hier als Spezialfall einer Berechnung des euklidischen Abstands gesehen, dessen Eigenheiten sich "erst" auf der Ebene des Vergleichs von Datensätzen (nicht aber auf der Ebene des Vergleichs von Zeichenketten) zeigen. Auf der Ebene der Berechnung der Vektordistanzen werden nach Lohrum, Schneider Willenborg (1999) die euklidischen Abstände (im Gegensatz z.B. zum Ansatz von Hylton (1996)) auf einer Skala mit Werten zwischen 0 und 1 abgebildet.
Aus diesem Grund wird bei den nachfolgenden Beispielen im Wesentlichen nur die Transformation der Werte auf eine solche Skala berücksichtigt. Die Gewichtung bzw. der Einfluss einer solchen wird anschließend in Kap.5 besprochen.
4.1 Das Jaccard-Maß
Bei der Beschreibung dieses Berechnungsverfahrens werden die Konventionen und Schreibweisen in Anlehnung an Ferber (2003, S.78-80) sowie Salton McGill (1987, S.213-217) wiedergegeben. Jener (nämlich Ferber) weist darauf hin, dass auch einfache Anfragen des booleschen Retrievals als Spezialfälle eines Vektorraummodells verstanden werden können (vgl. S.64). Aus diesem Grund darf der Umstand weiter nicht überraschen, dass sich in der Anwendung der Berechnungsverfahren beider Modelle (des booleschen sowie jenes, das Zeichenketten als mathematische Vektoren definiert) äquivalente Verfahrensweisen feststellen lassen.
Unter einer Zeichenkette wird im Retrieval in erster Linie ein Term - bzw. aus alltagssprachlicher Sicht "ein (Such-)Begriff" - verstanden. In weiterer Folge (abhängig vom gewählten Berechnungsverfahren) können darunter jedoch auch Kombinationen von Zeichenketten (z.B. sog. Chunks) verstanden werden.
Bei der Berechnung des Jaccard-Maßes werden zwei miteinander zu vergleichende Zeichenketten (Strings) - hier als w und q bezeichnet - bestimmt:
Für das weitere Verfahren werden zur Verrechnung der beiden Zeichenketten (auch entsprechend der booleschen Logik) ausschließlich die Werte und als Gewichte zugelassen. Dieser Umstand bedeutet für die Abfrage bzw. den Abfragevektor formal ausgedrückt, man verwendet 
, wobei 
gilt, wenn die angefragte Zeichenkette j im Datensatz i auftritt, und 
bedeutet, dass die Zeichenkette j nicht im Datensatz i auftritt.
Das Jaccard-Maß wird durch das Verhältnis zwischen den Skalarprodukten des Anfragevektors und des Dokumentenvektors angegeben, wobei das Skalarprodukt durch folgenden Ausdruck definiert wird:
Das Verhältnis der Skalarprodukte wird anschließend gebildet als:
Betrachtet man dieses Maß - wie oben angeführt - für mit den Werten und gewichtete Vektoren, dann steht im Zähler immer genau die Anzahl der Begriffe/Zeichenketten aus der Anfrage, die sowohl im Anfragestring als auch (=logisch UND) im abgefragten Datensatz vorkommen. Diese Ergebnismenge entspricht der Größe der Schnittmenge aus der Anfrage und dem Datensatz.
Im Nenner hingegen steht die Anzahl der Begriffe/Zeichenketten, die in der Anfrage oder im geprüften Datensatz vorkommen, also die Größe der Vereinigungsmenge von Anfrage und Datensatz.
Bei der Berechnung der Ähnlichkeit zwischen den beiden zum Vergleich herangezogenen Vektoren ist in diesem Fall der Nenner immer größer oder gleich , wenn einer der beiden Vektoren einen Eintrag mit dem Wert enthält. Der Ähnlichkeitswert liegt beim Jaccard-Maß demnach immer zwischen (=gänzlich unähnlich) und (=übereinstimmend) (vgl. Ferber 2003, S.78).
Im hier vorliegenden Ansatz werden Zeichenketten (also im Wesentlichen Begriffe sowie standardisierte Einträge der zu vergleichenden Kategorien) den entsprechenden Feldeinträgen in normierter Form entnommen und in Folgen von Trigrammen zerlegt.
Anschließend werden diese Abfolgen von Trigrammen miteinander entsprechend der booleschen Logik verglichen und daraus die sich ergebende Schnittmenge sowie die Vereinigungsmenge gebildet, die für die weitere Berechnung des Jaccard-Maßes notwendig sind.
Das für die Anwendung des Jaccard-Maßes zu berücksichtigende Problem, dass seine geometrischen Funktionskurven Unstetigkeiten aufweisen (vgl. Jones & Furnas 1987), kann hier vernachlässigt werden.
Dieses tritt nur dann auf, wenn die einzelnen, zur Berechnung herangezogenen Vektoren andere Werte außer und annehmen können. Dann allerdings ist es möglich, dass selbst sehr voneinander verschiedene (eigentlich völlig "beliebige") Vektoren auf einer Linie gleicher Ähnlichkeitswerte zu finden sind.9
4.2 Der euklidische Abstand
Zur Berechnung der Ähnlichkeit zweier Zeichenketten kann der euklidische Abstand einer geeignet gewählten Vektordarstellung der Trigrammabfolge dieser Zeichenketten verwendet werden.
Die beiden zu vergleichenden Zeichenketten werden daher als Vektoren ihrer Trigrammabfolge aufgefasst.
Der Vektor einer Zeichenkette wird dazu in eine Anzahl mA Teile (Trigramme) zerlegt. Daneben existiert eine zweite Zeichenkette, dessen Vektor mit auf der Basis seiner Trigramme verglichen werden soll. Die Definitionen gelingen formal durch folgenden Ausdruck:
Gebildet wird nun die Menge X, in der alle in oder vorkommenden Trigramme enthalten sind:
Für alle in X enthaltenen Trigramme wird anschließend überprüft, an welcher Stelle (Position) das jeweilige Trigramm im Vektor vorkommt. Wobei s die Position eines Trigramms im Vektor bezeichnet.
Wenn ein Trigramm an der Position s in vorkommt, so wird dieses Vorkommen (in unserem Fall) binär in einer Matrix vermerkt (kodiert).
Für die Elemente der Matrix gilt
Die Häufigkeit, mit der ein Trigramm in vorkommt, wird als Zeilensumme der Matrix durch
bestimmt.
Zur Veranschaulichung dieses Vorgangs ist folgende Übersicht nützlich:
Nach der analogen Behandlung des Vektors lässt sich der euklidische Abstand durch folgenden Ausdruck bilden:
Die Ähnlichkeit zweier, miteinander zu vergleichender Zeichenketten wird angenommen, wenn der Abstand der beiden Vektoren (eigentlich: die sich ergebende Differenz aus den vorhandenen Trigrammabfolgen) einen zu definierenden Schwellenwert (T, Threshold) nicht übersteigt. Dieser Schwellenwert wird üblicherweise aufgrund empirischer Messungen bzw. durch Schätzungen bestimmt.
Hylton (1996, S.47) hat für die Anwendung seines Algorithmus den Schwellenwert aufgrund einer Stichprobe mit (nur) 50 Paaren an zu vergleichenden Zeichenketten festgesetzt als:
T = 2.486 + 0.025 * n
wobei n die Anzahl der zu vergleichenden Teilstrings in der Vereinigung beider Vektormengen darstellt.10
Zur Verdeutlichung folgt an dieser Stelle ein Beispiel, an dem gezeigt wird, wie mehrfach vorhandene Trigramme verarbeitet werden.
Zu vergleichen sind die beiden Wörter "Flachdach" und "Kuhfladen".
Die Menge X, die alle in Vektor oder vorkommenden Trigramme enthält ist
Für den Vektor ergibt sich auf die Elemente der Menge X folgende Matrix:
Für den Vektor ergibt sich auf die Elemente der Menge X folgende Matrix:
Daraus errechnet sich der euklidische Abstand mit
4.3 Beispiele
Anhand einiger Zeichenketten werden die eben beschriebenen Berechnungsmethoden konkret gezeigt, sowie deren Ergebnisse kommentiert gegenüber gestellt.
Nach der Zerlegung in Trigramme erfolgt zuerst die Ermittlung des Jaccard-Maßes, dann die Berechnung des euklidischen Abstands der entsprechenden Zeichenketten-Vektoren in vereinfachter Form.11
Um die Werte besser einschätzen zu können, wird abschließend zu jedem Beispiel das in Anmerkung 10 genannte Verfahren zum Normalisieren der euklidischen Abstands auf eine Skala von 0 bis 1 angewandt.
4.3.1 Beispiel 1: Vergleich der beiden Begriffe "Bauernmarkt" und "Marktbauern"
Die Trigramm-Bildung ergibt - wie in Kap.2.1 bereits gezeigt - die Zeichenketten
Entsprechend der hier gewählten Vorgaben für die Berechnung des Jaccard-Maßes wird dieses aus dem Mengenvergleich zwischen der booleschen Schnittmenge und der Vereinigungsmenge der beiden in Trigramme zerlegten Zeichenketten gebildet:
Daraus ergibt sich als Jaccard-Maß = Schnittmenge / Vereinigungsmenge = 7 / 11 = 0.636
Der Wert 1 bedeutet auf der Skala zur Bewertung des Koeffizienten Gleichheit beider Zeichenketten, 0 Unähnlichkeit. Für den Vergleich von ausgewählten Einwort-Titeln im zu vergleichenden Bestand wurde ein empirisch ermittelter Schwellenwert von 0.7 festgelegt, über dem Zeichenketten als hinreichend ähnliche bestimmt wurden.
Der ermittelte Wert von 0.636 kann dem entsprechend als zu geringe Ähnlichkeit interpretiert werden.
Die Darstellung der beiden Zeichenketten als Vektoren der zu vergleichenden Trigramme zur Berechnung des euklidischen Abstands erfolgt durch folgenden Ausdruck
= (bau,aue,uer,ern,rnm,nma,mar,ark,rkt)
= (mar,ark,rkt,ktb,tba,bau,aue,uer,ern)
Nach Auswertung der beiden Matrizen für die Vektoren und zeigt sich, dass vier Elemente der Menge X zur Bildung der Differenz herangezogen werden müssen: (rnm, nma, ktb, tba).
Alle Elemente kommen jeweils nur einmal vor.
Eine hinreichend große Ähnlichkeit zwischen den beiden wird angenommen, wenn der euklidische Abstand den Schwellenwert T nicht übersteigt. Dieser errechnet sich im hier (in Anlehnung an Hylton 1996) gewählten Verfahren durch (siehe Kap.4.2)
T = 2.486 + 0,025 * 11 = 2.761
Da 2 < 2.761 wird in diesem Verfahren eine im Weiteren wahrzunehmende Ähnlichkeit zwischen den beiden Begriffen angenommen.
Mit der Normalisierungsfunktion, die in Lohrum, Schneider Willenborg (1999, S.6) beschrieben ist, werden die Werte des euklidischen Abstands auf eine Skala zwischen 0 und 1 projiziert, wobei die Werte 0 geringe Ähnlichkeit, 1 eine Übereinstimmung der zu vergleichenden Zeichenketten repräsentieren.
Der Wert 0.8 wird als Schwellenwert angenommen, über dem sämtliche Werte hinreichende Ähnlichkeit abbilden.
Für den Umstand, dass 
wird zur Normalisierung des errechneten Ähnlichkeitswertes S folgende Funktion eingesetzt
Für den Fall, dass 
wird zur Normalisierung des errechneten Ähnlichkeitswertes xxx hingegen diese Funktion eingesetzt
Im Fall, dass 
wird als Ähnlichkeitswert S angenommen.
Unter Anwendung dieser Bedingungen kann für diese Beispiel ein Ähnlichkeitswert von 0.855 errechnet werden.
Da dieser über dem dort definierten Schwellenwert von 0.8 liegt, würde dieses Zeichenkettenpaar wie im Verfahren nach Hylton (1996) - aber im Gegensatz zur Anwendung des Jaccard-Koeffizienten 0.636 < 0.7 - als ähnlich gewertet werden.
4.3.2 Beispiel 2: Vergleich der beiden Begriffe "_Bauernmarkt_" und "_Marktbauern_"
An diesem Vergleich kann gezeigt werden, dass die Berücksichtigung der Leerzeichen ("Blanks") an den Wortgrenzen zu einer deutlicheren Unterscheidung morphologisch ähnlicher Zeichenketten führt.
Die Trigramm-Bildung ergibt die Zeichenketten
Für die Berechnung des Jaccard-Maßes gilt:
Daraus ergibt sich als Jaccard-Maß = Schnittmenge / Vereinigungsmenge = 7 / 15 = 0.467
Gegenüber dem Wert von 0.636, der bei Vernachlässigung der Leerzeichenstellen an den Wortgrenzen ermittelt wird, ist der Wert des Koeffizienten - und die damit ausgedrückte Ähnlichkeit der Zeichenketten - bei Berücksichtigung dieser mit 0.467 deutlich geringer (und entsprechend weiter vom Schwellenwert 0.7 entfernt).
Die beiden Vektoren zur Berechnung des euklidischen Abstands sind
Die Differenz der beiden Vektoren ist
Für den Schwellenwert T ergibt sich
T = 2.486 + 0,025 * 15 = 2.861
Da 2.828 < 2.861 wird laut diesem Verfahren wiederum eine im Weiteren zu berücksichtigende Ähnlichkeit zwischen den beiden Begriffen angenommen.
Für das in Beispiel 1 vorgestellte Normalisierungsverfahren von Lohrum, Schneider Willenborg (1999) ergibt sich für den errechneten euklidischen Abstand ein Ähnlichkeitswert von 0.827.
Dieser Wert liegt über dem dort definierten Schwellenwert von 0.8. Aus diesem Grund würden diese beiden Zeichenketten - ebenso wie im Verfahren von Hylton (1996), jedoch im Gegensatz zum errechneten Jaccard-Maß - als hinreichend ähnlich gewertet werden.
4.3.3 Beispiel 3: Vergleich der beiden Begriffe "_Bauernmarkt_" und "_Tauernmarkt_"
Hier zeigt sich - in Ergänzung zum Beispiel 2 - deutlich, dass die Berücksichtigung der Leerzeichen ("Blanks") an den Wortgrenzen auch bei Verschiedenheit von nur einem Buchstaben am Wortanfang oder -ende zu einer deutlichen Unterscheidung morphologisch ähnlicher Zeichenketten führt.
Diese Eigenheit ist eines der wesentlichen Charakteristika in der Verrechnung von Trigrammen: kleine Differenzen am Wortanfang und -ende führen üblicherweise zu deutlichen Differenzen in der Berechnung von Ähnlichkeitskoeffizienten (vgl. dazu auch Kap.2).
Die Trigramm-Bildung ergibt die Zeichenketten
Für die Berechnung des Jaccard-Maßes gilt:
Daraus ergibt sich als Jaccard-Maß = Schnittmenge / Vereinigungsmenge = 9 / 13 = 0.692
Die Differenz von nur einem Buchstaben am Wortanfang zwischen den Zeichenketten "Bauernmarkt" und "Tauernmarkt" wirkt sich unter Berücksichtigung der Leerzeichenstellen an den Wortgrenzen im sich ergebenden Koeffizienten von 0.692 markant messbar - und knapp am Schwellenwert von 0.7 - aus.
Bei Vernachlässigung der Leerzeichenstellen ergibt sich für dieses Beispiel ein Wert von 0.8. Dieser liegt deutlich oberhalb des Schwellenwerts von 0.7.
Die beiden Vektoren zur Berechnung des euklidischen Abstands sind
Die Differenz der beiden Vektoren ist
Für den Schwellenwert T ergibt sich
T = 2.486 + 0,025 * 13 = 2.811
Da der errechnete Abstand 2 < 2.811 ist, wird laut diesem Verfahren eine zu berücksichtigende Ähnlichkeit zwischen den beiden Begriffen angenommen.
Bei Vernachlässigung der Leerzeichenstellen an den Wortgrenzen ergibt sich ein deutlich geringerer Abstand
Entsprechend dem im Beispiel 1 vorgestellten Verfahren von Lohrum, Schneider Willenborg (1999, S.6) wird mit diesem ein Wert von 0.855 für das Maß an Ähnlichkeit ermittelt. Dieser Ähnlichkeitswert liegt über dem dort definierten Schwellenwert von 0.8. Daher wird auch nach dieser Berechnung von einer Ähnlichkeit ausgegangen.
4.3.4 Übersicht vergleichbarer Werte
Abb. 1: Erweiterte Wertetabelle in Anlehnung an Lohrum, Schneider & Willenborg (1999, S.6)
Im hier mehrfach zitierten Aufsatz von Lohrum, Schneider Willenborg (1999) wird eine Tabelle angeführt, mit der die Ähnlichkeitskoeffizienten für den euklidischen Abstand sowie für den daraus abgeleiteten Ähnlichkeitswert (auf einer Skala von 0 bis 1) an einigen, ausgewählten Beispielen dargestellt werden.
Diese Tabelle wurde hier übernommen und um die Spaltenwerte für den Jaccard-Koeffizienten erweitert. Um den aus den Berechnungsvorgaben entwickelten Programm-Algorithmus zu testen, wurden die in Abb.1 wiedergegebenen Werte zudem "händisch" überprüft.12
Bei einem ersten Vergleich der Ergebnisse aus Abb.1 zeigt sich, dass bei Berücksichtigung eines Schwellenwerts von 0.8 der berechnete Ähnlichkeitswert fünf mal den Schwellenwert übersteigt. Diese fünf Paare von Zeichenketten wären demnach für eine weitere Beachtung als mögliche Dubletten aufgrund Ihrer Zeichenähnlichkeiten von Relevanz.
Für vier der angeführten Paare übersteigt der berechnete Jaccard-Koeffizient den hier verwendeten Schwellenwert von 0.7.
Somit tragen alle vier in der Tabelle durch das Jaccard-Maß angezeigten Dubletten auch einen Ähnlichkeitswert über der angegebenen Schwelle.
Aus der Gegenüberstellung dieser (sehr vereinfachten) Wertangaben erkennt man zudem, dass ein Zeichenketten-Paar zwar im Wesentlichen gleichzeitig einen hohen Ähnlichkeitswert und zumeist einen eher hohen Jaccard-Koeffizienten aufweist. Man erkennt aber auch deutlich, dass diese beiden Maßangaben kein lineares Verhältnis zueinander zeigen.
In diesem Umstand liegt z.B. begründet, dass einerseits das Zeichenketten-Paar
blue velvet - green velour
das nach "menschlicher" Interpretation wenig (morphologische) Ähnlichkeiten zueinander zeigt, einen relativ hohen Ähnlichkeitswert von 0.408 aber einen sehr geringen Jaccard-Koeffizienten von 0.118 aufweist,
andererseits das Zeichenketten-Paar
springer verlag - vrlg. springer
einen eher weit vom Schwellenwert entfernten Ähnlichkeitswert von 0.486, jedoch einen knapp unter dem Schwellenwert liegenden Jaccard-Koeffizienten von 0.667 aufweist.
Eine rein intellektuelle Interpretation dieser einfachen Gegenüberstellung würde wohl nahelegen, dass der Jaccard-Koeffizient eher Dubletten anzeigt, die auch in der menschlichen und nicht nur durch die maschinelle Wahrnehmung als solche eingeschätzt würden.
Die Interpretation dieser wenigen Beispiele ist jedoch für eine Gesamtdarstellung nicht weiterführend. Sie soll an dieser Stelle ausschließlich auf einige Eigenheiten hinweisen - und die aus Abb.1 bekannten Werte jenen zur Ermittlung des Jaccard-Koeffizienten gegenüberstellen.
Autor
Dr. Harald Jele
Leiter der Abteilung EDV-Administration und -Entwickung der Universitätsbibliothek Klagenfurt
Universitätsstraße 65-67
A-9020 Klagenfurt
harald.jele@uni-klu.ac.at
Anmerkungen
1. Verfahren zur Bestimmung von Textähnlichkeiten bzw. -gleichheiten sind in bekannter Weise innerhalb der automatisierten Indexierung und Klassierung von Dokumenten zu finden. Daneben werden aber auch Programme zunehmend attraktiver, die aufgrund eines vorhandenen Datenpools Text-Plagiate erkennen sollen.Eine Übersicht dazu findet sich z.B. in Kramer (2004).
Die automatische Erkennung und Korrektur von Tippfehlern ist eine weitere, häufig anzutreffende Anwendung solcher Verfahren (vgl. dazu auch Zamora, Pollock Zamora (1981)).
2. vgl. dazu z.B. die in Hickey (1979) publizierten Ergebnisse, die im Wesentlichen auf frühere Ansätze zurückgehen.
Aufgegriffen und fortgesetzt wurde diese Idee bei der Bildung des USBC (=Universal Standard Book Code), der wesentlich später beispielgebend auch in jene Ansätze eingeflossen sind, die z.B. in Goyal (1987) genannt werden.
3. Dieser Ähnlichkeitswert kann zudem als ein zeitgenössisches und sehr prominentes Beispiel gesehen werden. Das Verfahren des KOBV ist eines von sehr wenigen, das seit vielen Jahren zur Dublettenbehandlung beim Online-Retrieval in der KOBV-Suchmaschine (vgl. Kuberek 1999) eingesetzt wird.
KOBV = Kooperativer Bibliotheksverbund Berlin-Brandenburg.
Das dort implementierte Verfahren basiert im Wesentlichen auf dem Ansatz, wie er in Schneider (1999) dargelegt ist.
4. Der im Text verwendete Begriff "Performanz" wird hier wie das englische "Performance" als Angabe der Leistung sowie als Maß für den Verbrauch von Ressourcen in der Informatik gesehen und entsprechend verstanden.
5. Wegst bietet auf seiner Homepage eine einfache Möglichkeit, sich mit der Bildung von Trigrammen als Spezialfall von N-Grammen zur Bestimmung von Ähnlichkeiten zwischen Zeichenketten zu beschäftigen: sowohl für 2- als auch für 3-Gramme sind dort online Berechnungsverfahren frei editierbarer Zeichenketten zugänglich.
vgl. http://www.tillmann-wegst.de/
6. Das sind Buchstaben bei Wörtern und Begriffen sowie Buchstaben und Ziffern innerhalb von freien oder standardisierten Zeichenketten. Sonderzeichen und typographische Satzzeichen werden üblicherweise ignoriert bzw. durch ein vorgeschaltetes Normierungsverfahren ersetzt (vgl. dazu Kap.3).
7. Die Behandlung von Ein-Wort-Begriffen gilt in Bezug auf die Behandlung der Leerzeichen wohl zu den Ausnahmen als zu den Regelfällen. Üblicherweise sind Leerzeichen zwischen den einzelnen Begriffen an den Wortgrenzen ja vorhanden und müssen in irgendeiner Form (sie ignorieren oder nicht) behandelt werden. Das heißt, dass das weitere Verfahren abhängig von ihrem (=den Ein-Wort-Begriffen) Auftreten gewählt wird. Bei Ein-Wort-Begriffen tauchen Leerzeichen in den zu bearbeitenden Zeichenketten üblicherweise nicht auf und müssen entsprechend einem konsistenten Verfahren an den beiden Wortgrenzen (Wortanfang und -ende) nachträglich hinzugefügt werden.
8. Die hier genannten Routinen sind vollständig und - bezogen auf die Vorgaben im Text von Rusch (1999) - kommentiert unter folgendem Link zugänglich:
http://www.uni-klu.ac.at/~hjele/publikationen/ngramme/routinen/index.html
9. Siehe dazu auch die entsprechende Abb.3.26 in Ferber (2003, S.80).
10. Ein ähnliches Verfahren zur Festsetzung eines Schwellenwerts wird im Beitrag von Lohrum, Schneider Willenborg (1999, S.5-7) vorgestellt, wobei dort der Kehrwert des euklidischen Abstands auf eine Werteskala zwischen 0 und 1 normalisiert und der Schwellenwert T=0.8 als definierte Größe für die Bestimmung ähnlicher Zeichenketten, angenommen wird.
11. Vereinfacht heißt hier: nachdem in Kap.4.2 anhand von Matrizen genau gezeigt wurde, wie einzelne Trigramme behandelt werden, auch wenn diese in den Zeichenketten mehrfach vorkommen, werden an dieser Stelle nur noch die nach der Bildung der Vektordifferenz verbleibenden Trigramme zur weiteren Berechnung angegeben.
12. Die daraus entstandenen Unterlagen finden sich unter folgendem Link und können als Veranschaulichung weiterer Berechnungsbeispiele verstanden werden:
http://www.uni-klu.ac.at/126hjele/publikationen/ngramme/haendisches/index.html