Inhaltsverzeichnis

1  Einleitung  6

1.1  Motivation  6

1.2  Aufgabenstellung  8

1.3  Vorgehensweise und Struktur der Arbeit  9

2  Information Retrieval  11

2.1  Einf uhrung und Definition des Information Retrieval  11

2.2  Struktur und Funktionsweise eines Information-Retrieval-Systems  12

2.3  Beurteilung von IR-Systemen  13

2.4  Gewinnung von Indextermen  14

2.5  Das Vektorraummodell  16

2.6  Aufl osen von Mehrdeutigkeiten  18

2.7  Thesauren  20

3  Cross-language Information Retrieval  23

3.1  Einf uhrung und Definition des Cross-language Information Retrieval  23

3.2  Architekturen von CLIR-Systemen  24

3.3  Aufl osen von Mehrdeutigkeiten im CLIR  26

3.4  Interlingual Retrieval  28

3.5  Erkennung der Sprache eines Textes mit n-Grammen  31

4  Serviceorientierte Architekturen  33

4.1  Einordnung der serviceorientierten Architektur  33

4.2  Elemente einer serviceorientierten Architektur  34

4.3  Merkmale einer serviceorientierten Architektur  35

4.4  Web Services  37

5  Anforderungen und Entwurf des Systems  43

5.1  Vorbedingungen und Anforderungen an das System  43

5.2  Systemarchitektur und Systementwurf  44

5.3  1. Phase: Entwurf der Interlingua-W orterb ucher und Konzepterkennung  46

5.4  2. Phase: Entwurf des Indexierungsprozesses  51

5.5  3. Phase: Entwurf des Suchprozesses  53

5.6  Abschließender System uberblick  59

6  Verwendete Methoden und Werkzeuge  61

6.1  Allgemeine Werkzeuge  61

6.2  Apache Lucene  61

6.3  Lucene Erweiterungen und sonstige Werkzeuge  69

4

Inhaltsverzeichnis

7  Implementierung der Suchanwendung  72

7.1  Allgemeines uber das entwickelte System  72

7.2  Nutzung des Systems  73

7.3  Implementierung der Interlingua-W orterb ucher und  

Ubersetzung   75

7.4  Implementierung der Indexierung  81

7.5  Implementierung der Suche als Webseite  82

7.6  Implementierung der Suche als Web Service  89

7.7  Beispielanfragen an die Suchanwendung  92

7.8   

Uberblick  uber die Projektdateien  95

8  Bewertung des Systems und m ogliche Erweiterungen  97

8.1  Das Interlingua-Konzept  97

8.2  Bewertung der Indexierung  98

8.3  Bewertung der Suche  99

9  Zusammenfassung und Ausblick  101

Abk  urzungsverzeichnis  103

Abbildungsverzeichnis   104

Tabellenverzeichnis 106   

Literaturverzeichnis   107

5

1 Einleitung

1.1 Motivation

1.1.1 Entwicklung der Sprachanteile im Internet

Durch die schnelle Verbreitung des Internets in den letzten zehn Jahren ist ein Zustand eingetreten, in dem ann¨ ahernd der gesamten Welt ein normiertes, digitales Kommunikationsmedium zur Verf¨ ugung steht. Standards wie etwa TCP/IP, HTTP und HTML sorgen f¨ ur einen weltweit vereinheitlichten Datenaustausch - sei es in Form von Webseiten, E-Mails oder multimedialen Datenstr¨ omen. Es hat sich eine allgemein akzeptierte Technologie etabliert, die einen grenz¨ uberschreitenden Nachrichten- und Datenaustausch erm¨ oglicht. Trotz aller Bem¨ uhungen, die internationale und interkulturelle Kommunikation zu vereinfachen, kann das Internet (zur Zeit) nicht mehr sein als ein Medium, das zuverl¨ assig und

Abbildung 1.1: Sprachverteilung der Internet-Webseiten von 1997 und 2002.

Tabelle 1.1: Die Top 10 Muttersprachen der Internetbenutzer. Stand: 31. M¨ arz 2006. Quelle: [Min06a].

Die den Internetdaten fehlende Semantik ist auch Grund daf¨ ur, dass das Internet unter sprachwissenschaftlichen Aspekten noch in den Kinderschuhen steckt. Die Tatsache, dass weltweit unterschiedlichste Gruppen die Entwicklung des Internets vorangetrieben haben (und heute noch vorantreiben), f¨ uhrte zwar dazu, dass jede Sprache und eventuelle Dialekte vom Internet unterst¨ utzt und digital repr¨ asentiert werden k¨ onnen, ¨ anderte aber nichts daran, dass sich die Inhalte nur denjenigen erschließen, die der entsprechenden Sprache m¨ achtig sind. Das Internet kann zur Zeit die Verst¨ andigung in verschiedenen Sprachen genauso wenig vereinfachen wie die Erfindung des Telefons den Beruf des Dolmetschers ¨ uberfl¨ ussig machte.

Die Sprachbarriere ist also nach wie vor im Internet vorhanden und obwohl es unbestritten Fortschritte auf dem Gebiet der maschinellen ¨ Ubersetzung zu verzeichnen gibt, sind immer

noch keine ausgereiften Technologien entstanden, die eine sprachtransparente Nutzung des Internets erm¨ oglichen.

Das Forschungsgebiet des Cross-language Retrievals verfolgt eine Vorstufe dieses Ideals. Ziel ist nicht die vollst¨ andige ¨ Ubersetzung des Internets in alle gew¨ unschten Sprachen, sondern das Suchen und Finden von Dokumenten, die in einer anderen Sprache verfasst sind als die Suchanfrage. Viele Schwierigkeiten der maschinellen ¨ Ubersetzung, wie z. B. syntaktische

Umbauten sowie Erg¨ anzung und Entfernung von W¨ ortern, sind im Cross-language Retrieval nicht vorhanden, da ein Text bez¨ uglich einer Anfrage nur als relevant oder nicht relevant eingestuft werden muss. F¨ ur diese Klassifizierung sind nur punktuelle ¨ Ubersetzungen notwendig. Freilich ist dieser Ansatz nur f¨ ur Personen interessant, die einerseits zwar keine fremdsprachliche Suchanfragen formulieren, andererseits aber durchaus ein in der Fremdsprache geschriebenes Dokument lesen und verstehen k¨ onnen.

Abbildung 1.1 zeigt, dass die Weltsprache Englisch in den Anf¨ angen des Internets 1997 mit einem Anteil von 84 % eindeutig die dominierende Sprache von Webseiten war. Bereits 2002 hatte sich dieses Bild ver¨ andert: Der Anteil von in anderen Sprachen verfassten Webseiten hatte stark zugenommen und Englisch war nur noch mit 56,4 % vertreten. Dass diese Verteilung im Netz jedoch immer noch nicht der Sprachverteilung in der Wirklichkeit entspricht, wird bei Betrachtung der Tabellen 1.1 und 1.2 deutlich. In Tabelle 1.1 ist ersichtlich, dass lediglich 30 % der Internetnutzer Englisch als Muttersprache sprechen.

7

Tabelle 1.2: Die Top 10 L¨ ander mit den meisten Internetbenutzern. Stand: 31. M¨ arz 2006. Quelle: [Min06b].

An zweiter und dritter Stelle stehen bereits die fern¨ ostlichen Sprachen Chinesisch (13,0 %) und Japanisch (8,5 %), dann erst sind Spanisch, Deutsch und Franz¨ osisch vertreten. In Tabelle 1.2 werden die Top 10 L¨ ander mit den meisten Internetbenutzern aufgef¨ uhrt. Auch dort stehen China und Japan bereits an zweiter und dritter Stelle. Es ist damit zu rechnen, dass sich die Sprachverteilung des Internets weiterhin an die realen Gegebenheiten ann¨ ahern wird. Durch die wachsende digitale Sprachvielfalt werden daher die maschinelle ¨ Ubersetzung und das Cross-language Retrieval noch st¨ arker in den Mittelpunkt des Internets r¨ ucken.

1.1.2 Moderne Systementwicklung

F¨ ur die Entwicklung von IT-Systemen m¨ ussen immer komplexere Sachverhalte beschrieben, modelliert und programmiert werden. Dadurch sind stets neue Programmierkonzepte ent-standen, die sich f¨ ur die zunehmende Komplexit¨ at von Projekten eignen. Momentaner Stand der Technik sind die serviceorientierten Architekturen, die auf dem Prinzip beruhen, dass ein Dienst von einem Dienstbetreiber f¨ ur einen Dienstnutzer zur Verf¨ ugung gestellt wird. Die Nutzung eines Dienstes findet dynamisch zur Laufzeit des Programms statt, wobei der Dienstnutzer ggf. zwischen mehreren, funktional gleichen Diensten w¨ ahlen kann. Ein Dienst wird in einer standardisierten Form beschrieben und kann plattform¨ ubergreifend genutzt werden, wodurch eine problemlose Maschine-zu-Maschine-Kommunikation erm¨ oglicht werden soll. Die Implementierung des Dienstes kann in einer beliebigen Programmiersprache erfolgen.

Popul¨ are Internetangebote wie Google und Amazon sind bereits als Web Service verf¨ ugbar und k¨ onnen somit von anderen Programmen genutzt werden.

1.2 Aufgabenstellung

Ziel dieser Arbeit ist die Prototypentwicklung einer sprach¨ ubergreifenden Suchmaschine. Dazu soll eine geeignete Architektur ausgew¨ ahlt und implementiert werden. Das System indexiert Dokumente ohne Benutzerinteraktion und stellt die notwendigen Datenstrukturen

8

1 Einleitung

bereit. Dabei wird die Sprache eines Dokuments automatisiert erkannt und als Metainformation in den Index eingetragen. Außerdem sollen aktuelle, sprachspezifische Analysetechniken auf die Texte angewendet werden, um die Retrievaleffizienz zu steigern. Die zu indexierenden Dokumente stammen aus einem abgegrenztem Themengebiet, das durch eine ¨ uberschaubare Menge an Vokabeln ausgezeichnet ist. Diese Einschr¨ ankung erm¨ oglicht die eigene Erstellung eines W¨ orterbuchs, das durch geeignete Kontextinformationen die korrekte ¨ Ubersetzung mehrdeutiger W¨ orter erm¨ oglicht.

Das Durchsuchen des Dokumentbestandes kann sowohl durch die Nutzung einer zu erstellenden Weboberfl¨ ache erfolgen, als auch durch die Bereitstellung und Verwendung eines Web Services, wie er in aktuellen serviceorientierten Architekturen zu finden ist. Wie bei gel¨ aufigen Internetsuchmaschinen ¨ ublich, soll das System neben der Standardsuche auch

die Suche nach exakten Phrasen unterst¨ utzen und in den Suchergebnissen Textausz¨ uge der Trefferdokumente anzeigen.

Die gesamte Architektur soll daraufhin ausgerichtet sein, dass die Suchmaschine um zus¨ atzliche Datenquellen, Dateiformate und Sprachen erweitert werden kann. Wie eingangs deutlich wurde, gewinnen auch zunehmend fern¨ ostliche Sprachen an Bedeutung. Deshalb soll das System initial neben den Sprachen Deutsch und Englisch auch die Indexierung von japanischen Texten unterst¨ utzen. So wird gleichzeitig die F¨ ahigkeit demonstriert, nichtlateinische Zeichens¨ atze zu verarbeiten.

1.3 Vorgehensweise und Struktur der Arbeit

Zun¨ achst werden im sich anschließenden Kapitel 2 die Grundlagen des Information Retrievals vorgestellt. Neben der obligatorischen Definition und der generellen Funktionsweise von Information Retrieval Systemen werden insbesondere die Verarbeitung von Texten zur Gewinnung von Indextermen, das Vektorraummodell und der Umgang mit mehrdeutigen W¨ ortern behandelt.

Im 3. Kapitel werden diese Inhalte um den Aspekt der sprach¨ ubergreifenden Suche erweitert. Nach der Nennung von unterschiedlichen Architekturen wird ein Schwerpunkt auf das Interlingual Retrieval gelegt, das im zu entwickelnden System zum Einsatz kommen wird. Außerdem wird beschrieben, durch welches Verfahren die Sprache eines Textes zuverl¨ assig erkannt werden kann.

Das 4. Kapitel besch¨ aftigt sich mit den Grundlagen von serviceorientierten Architekturen (SOA). Nach einem Abriss der Historie von unterschiedlichen Programmierparadigmen werden die Funktionsweise und die Vorteile der serviceorientierten Architekturen erl¨ autert. Als konkrete Implementierungstechnik einer SOA kommen zur Zeit haupts¨ achlich Web Services zum Einsatz, deren Kernkomponenten ebenfalls in diesem Kapitel kurz vorgestellt werden. In dem darauf folgenden 5. Kapitel werden die Anforderungen festgelegt und der Entwurf des Systems beschrieben. Dabei werden drei wesentliche Phasen identifiziert:

1. Erstellung der Interlingua-W¨ orterb¨ ucher und Konzepterkennung

2. Indexierung

3. Suchen

9

1 Einleitung

Auf Basis des Entwurfes werden anschließend im 6. Kapitel die verwendeten Methoden und Werkzeuge pr¨ asentiert.

Kapitel 7 beschreibt die Implementierung der Anwendung. Nach einer kurzen Einf¨ uhrung in die konkrete Nutzung werden die Umsetzung der o. g. ersten beiden Phasen sowie die Zugriffstechniken f¨ ur die 3. Phase ” Suchen“ in Gestalt der Weboberfl¨ ache und des Web Services erl¨ autert.

Eine kritische W¨ urdigung des Systems, in der auch Erweiterungsm¨ oglichkeiten genannt werden, erfolgt in Kapitel 8. Die Zusammenfassung sowie ein Ausblick finden im schließenden Kapitel 9 statt.

10

2 Information Retrieval

In diesem Kapitel werden die Grundlagen des Information Retrievals vorgestellt. Nach der Definition des Begriffs wird der Aufbau und die Arbeitsweise eines Information-Retrieval-Systems erl¨ autert. Anschließend wird kurz auf die Maße zur Beurteilung von IR-Systemen und die Analyse von Texten zur Gewinnung von Indextermen eingegangen. Da heutige Suchmaschinen meist auf dem sogenannten Vektorraummodell basieren, werden dieses Modell und wichtige damit in Zusammenhang stehende Konzepte erkl¨ art. Da das Synonymie- und das Polysemieproblem im Information Retrieval von Bedeutung sind, werden diese Probleme erl¨ autert und Techniken zum Umgang damit pr¨ asentiert. Abschließend wird auf Aufgabe und Form von Thesauren eingegangen.

2.1 Einf¨ uhrung und Definition des Information Retrieval

Information Retrieval (IR) ist ein Fachgebiet, das insbesondere seit der rasanten Verbreitung des Internets an Bedeutung gewonnen hat. Im WWW dient ein IR-System dazu, eine anhand von Suchbegriffen beschriebene Fragestellung entgegen zu nehmen und anschließend diesbez¨ uglich relevante Internetseiten aufzulisten. IR-Systeme kommen aber auch in einer Vielzahl von (Wissens-)Datenbanken zum Einsatz, um das Auffinden von bestimmten Informationen zu erleichtern.

F¨ ur den Begriff des Information Retrieval existiert keine allgemein akzeptierte Definition. In [BYRN99] (S. 1) werden die Aufgaben und Ziele des IR wie folgt beschrieben:

Information Retrieval (IR) deals with the representation, storage, organization of, and access to information items. The representation and organization of the information items should provide the user with easy access to the information in which he is interested.

Anhand dieser Definition wird deutlich, dass f¨ ur eine effektive Wiedergewinnung von In-formationen zun¨ achst die Repr¨ asentation, Verwaltung und Speicherung von Dokumenten zu behandeln sind. Anschließend kann dann - i. d. R. durch die Eingabe von Suchtermender eigentliche Suchvorgang durchgef¨ uhrt werden. Eine Besonderheit des Information Retrievals besteht darin, dass bei der Suche vage bzw. ungenaue Anfragen zu verarbeiten sind und meist nat¨ urlichsprachliche Dokumente gesucht werden. Diese Tatsache wird auch auf der Webseite der Fachgruppe ” Information Retrieval“ in der Gesellschaft der Informatik betont ([Fuh96]):

Im Information Retrieval (IR) werden Informationssysteme in bezug auf ihre Rolle im Prozess des Wissenstransfers vom menschlichen Wissensproduzenten zum Informations-Nachfragenden betrachtet. Die Fachgruppe ” Information Re-

trieval“ in der Gesellschaft f¨ ur Informatik besch¨ aftigt sich dabei schwerpunktm¨ aßig mit jenen Fragestellungen, die im Zusammenhang mit vagen Anfragen und

11

2 Information Retrieval

unsicherem Wissen entstehen. Vage Anfragen sind dadurch gekennzeichnet, daß die Antwort a priori nicht eindeutig definiert ist. [...]

Demnach pr¨ agen insbesondere die Vagheit und die Unsicherheit das Information Retrieval. Der Begriff Vagheit ist in der Definition der Fachgruppe ” Information Retrieval“ dabei etwas

missverst¨ andlich beschrieben. Er ist vielmehr als das Problem zu verstehen, dass der Benutzer sein Informationsbed¨ urfnis nicht pr¨ azise darstellen kann. Das zeigt sich auch anhand der Tatsache, dass mehrere Benutzer die gleiche Fragestellung oft mit unterschiedlichen Anfragen beschreiben. Die Unsicherheit des IR besteht darin, dass das System bestimmte Kenntnisse ¨ uber die Inhalte der Dokumente (z. B. die exakte Bedeutung eines mehrdeutigen Wortes) nicht besitzt, was zu fehlerhaften und fehlenden Antworten f¨ uhren kann. Reginald Ferber stellt in [Fer03] (S. 30) außerdem fest, dass im Information Retrieval auch Aspekte der Wissensverarbeitung des Menschen zu ber¨ ucksichtigen sind und es damit auch humanwissenschaftliche Anteile wie z. B. die Sprachpsychologie enth¨ alt. Deshalb sei die Vagheit des IR auch daher zu begr¨ unden, dass es zwischen der Informatik und den Kognitionswissenschaften anzusiedeln ist.

Die Vagheit im IR ist gleichzeitig ein wichtiges Unterscheidungskriterium zum so genannten Data Retrieval, das z. B. bei einer SQL-Abfrage einer relationalen Datenbank vorgenommen wird. Hier erh¨ alt man als Ergebnis Datens¨ atze, die pr¨ azise die in der Abfrage definierten Bedingungen erf¨ ullen. Aufgrund dieser grunds¨ atzlich anderen Arbeitsweise spricht man bei IR-Systemen von ” weichen“ und bei Data-Retrieval-Systemen von ” harten Anfragen“.

Es bleibt festzuhalten, dass Information Retrieval sich mit der Repr¨ asentation, Speicherung und Organisation von nat¨ urlichsprachlichen Informationen sowie mit der Wiederauffindbarkeit dieser Informationen besch¨ aftigt. Dabei sind ungenaue, vage Anfragen der Benutzer und ggf. dem System fehlendes semantisches Wissen ¨ uber die Dokumente zu ber¨ ucksichtigen. Ziel eines jeden IR-Systems ist unumstritten die Gewinnung von Informationen, die den Informationsbedarf des Nutzers gut abdecken. Die Ergebnismenge soll dabei m¨ oglichst viele relevante und wenig irrelevante Dokumente enthalten (siehe [BYRN99], S. 2).

2.2 Struktur und Funktionsweise eines

Information-Retrieval-Systems

Grunds¨ atzlich gibt es beim Information Retrieval zwei Komponenten, die durch das IR-System in Bezug gebracht werden: Zum einen die Objektsammlung bzw. Wissensbasis, die durchsucht werden soll, zum anderen die Anfrage des Benutzers, anhand derer die relevanten Dokumente gefunden werden sollen. Sowohl die Objekte als auch die Anfragen m¨ ussen in einem IR-System geeignet repr¨ asentiert werden, damit die Suche schnell und effektiv durchgef¨ uhrt werden kann. Der eigentliche Retrievalprozess vergleicht nun Anfrage und Dokumente und gibt bez¨ uglich der Anfrage als relevant eingestufte Dokumente als Ergebnismenge zur¨ uck. Abbildung 2.1 zeigt den grundlegenden Aufbau eines IR-Systems. Der Suchprozess ist in der Grafik durch den oval markierten Pfeil zu erkennen. Ein m¨ oglicher naiver Ansatz, um ein IR-System zu betreiben, ist die Entgegennahme des Suchbegriffs und die sequentielle Suche dieses Suchbegriffs in allen Dokumenten. Es ist leicht einzusehen, dass diese Vorgehensweise bei umfangreichen und wachsenden Dokumentmengen sowie vielen gleichzeitigen Anfragen eine unzureichende Skalierbarkeit und

12

Abbildung 2.1: Grundlegender Aufbau eines IR-Systems. Quelle: [Fer03], S. 25.

Performanz besitzt. Deshalb f¨ uhren IR-Systeme eine Vorverarbeitung der Dokumentmenge durch, die eine effizientere Suche erm¨ oglichen soll.

Klassische Information Retrieval Modelle (z. B. das Boolesche Retrieval) sehen dabei eine abfrageoptimierte Indexierung vor. Dazu werden die jeweils f¨ ur ein Dokument charakteristischen W¨ orter ermittelt (siehe Abschnitt 2.4) und in eine invertierte Liste eingetragen. Die invertierte Liste ist mit einer Datenbank vergleichbar, die zu einem bestimmten Wort sehr schnell alle in der Dokumentmenge vorhandenen Fundstellen aufzeigen kann. Aufgrund der hohen Geschwindigkeitsanforderung steht die invertierte Liste in dem Konflikt, einerseits alle charakteristischen W¨ orter zu enthalten, andererseits nicht zu umfangreich zu werden. Zur Durchf¨ uhrung der Suche werden die Anfrage ¨ ahnlich der Dokumentindexierung zun¨ achst analysiert und darin enthaltene Indexterme identifiziert. Die invertierte Liste liefert zu diesen Termen die Fundstellen. Anhand der Fundstellen werden dann die relevanten Dokumente ermittelt. In weiterentwickelten Modellen wie dem Vektorraummodell (siehe Abschnitt 2.5) wird die ¨ Ahnlichkeit zwischen Anfrage und einzelnen Dokumenten ¨ uber ein ¨ Ahnlichkeitsmaß genauer bestimmt. Bei der Darstellung der Suchergebnisse ist es so m¨ oglich, dass die relevanten Dokumente absteigend nach ihrer ¨ Ahnlichkeit sortiert werden und

damit die (wahrscheinlich) passendsten Dokumente dem Nutzer gleich zu Beginn angezeigt werden.

2.3 Beurteilung von IR-Systemen

Um die Qualit¨ at von IR-Systemen zu beurteilen bzw. IR-Systeme zu vergleichen, betrachtet man in erster Linie die Retrievalergebnisse. Es werden hierbei zwei Evaluierungsmaße verwendet (vgl. [Fer03], S. 86 f.):

Precision Die Precision gibt an, wieviele der gefundenen Dokumente bez¨ uglich der Anfrage relevant sind. Dieses Maß beschreibt die Genauigkeit der Suchergebnisse.

Recall Der Recall gibt an, wieviele aller vorhandenen relevanten Dokumente in der Antwort des IR-Systems enthalten sind. Recall macht also eine Aussage ¨ uber die Vollst¨ andigkeit des Retrievalprozesses.

13

2 Information Retrieval

Die Entscheidung, ob ein Dokument bez¨ uglich einer Anfrage relevant bzw. nicht relevant ist, kann von einer Maschine nicht entschieden werden. Deshalb werden die Dokumente in Testsammlungen und -anfragen im Vorhinein von Spezialisten klassifiziert. Basierend auf dieser Klassifikation k¨ onnen dann die Werte f¨ ur Precision und Recall eines konkreten IR-Systems berechnet werden.

Formal werden Precision und Recall in [Fer03] (S. 86) wie folgt definiert:

Definition 2.1 Sei D = {d 1 , . . . , d m } eine Menge von Dokumenten, q ∈ Q eine Anfrage und D q die Menge der in D zur Anfrage q gefundenen Dokumente.

Sei ferner r : D × Q → {0, 1} eine Relevanzrelation und r q : D → {0, 1}; r q (d) := r(d, q) die zur Anfrage q geh¨ orende Relevanzfunktion. Dann heißt

Precision der Antwort auf die Anfrage q und

Recall der Antwort auf die Anfrage q.

Es ist leicht einzusehen, dass sowohl f¨ ur Precision als auch f¨ ur Recall der Wert 1 anzustreben ist. In der Praxis verhalten sich beide Werte allerdings gegenl¨ aufig, d. h. eine hohe Pr¨ azision geht meist mit einer abgeschw¨ achten Vollst¨ andigkeit einher und umgekehrt.

2.4 Gewinnung von Indextermen

Da das Information Retrieval insbesondere f¨ ur die Suche in nat¨ urlichsprachlichen Texten eingesetzt wird, st¨ oßt man auf mehrere Schwierigkeiten, die man w¨ ahrend des Indexierungsprozesses, d. h. bei der Gewinnung von Indextermen, ber¨ ucksichtigen muss. Im Folgenden werden die verschiedenen Phasen der Indexierung eines Textdokuments beschrieben und m¨ ogliche L¨ osungsans¨ atze erl¨ autert (vgl. [BYRN99], S. 165 f.). Das Verfahren ist in Abbildung 2.2 veranschaulicht. Zu beachten ist, dass viele Stufen der Indexierung optional sind und somit ¨ ubersprungen werden k¨ onnen. In der Abbildung verdeutlichen Pfeile die m¨ oglichen Prozessabl¨ aufe.

1. Aus informationstechnischer Sicht ist ein digitales Textdokument zun¨ achst ein Datenstrom aus Zeichen. Das Ziel des ersten Schrittes besteht darin, diesen Strom in W¨ orter aufzuteilen, die in den darauf folgenden Schritten als Kandidaten f¨ ur die Aufnahme in den Index in Betracht gezogen werden. Dazu wird der Text einer lexikalischen Analyse unterzogen. Als naheliegendste und h¨ aufigste Indikation f¨ ur eine Worterkennung dienen die Leerzeichen. Nach dieser Leerzeichen-Segmentierung k¨ onnen jedoch W¨ orter entstehen, f¨ ur die weitere Betrachtungen notwendig sind. Dabei handelt es sich u. a. um die folgenden Sonderf¨ alle:

• allein stehende und mit Buchstaben kombinierte Zahlen,

14

Abbildung 2.2: Stufen der Indexierung eines Textdokuments. Quelle: [BYRN99], S. 166.

• W¨ orter, die Trenn- bzw. Bindestriche enthalten,

• W¨ orter, die Sonderzeichen (z. B. @, Apostroph) enthalten,

• Behandlung von Punkten (Satzende vs. Eigenname (z. B. x.id)).

In dieser Phase wird außerdem meist eine Konvertierung der W¨ orter in durchgehende Klein- oder Großschreibung vorgenommen. Nur in Dom¨ anen, wo strikt zwischen Klein- und Großschreibung unterschieden wird (z. B. Unix-Befehle) sollte die Originalschreibweise erhalten bleiben.

Die Elemente, die man nach Ausf¨ uhrung dieser ersten Stufe erh¨ alt, werden auch als Token bezeichnet, die in den weiteren Ausf¨ uhrungen durch eckige Klammern kenntlich gemacht werden ([bank]). Ein Token besteht mindestens aus dem urspr¨ unglichen Wort selbst, kann aber auch weitere Informationen beinhalten (z. B. eine Angabe ¨ uber

die Position innerhalb des Dokuments).

2. Nicht alle W¨ orter, die der erste Schritt als Termkandidaten liefert, sind als Indexterme geeignet. W¨ orter, die sich nicht zur Unterscheidung verschiedener Texte eignen, da sie in einem Großteil der Dokumente vorkommen, sind so genannte Stoppw¨ orter. Insbesondere Artikel, Pr¨ apositionen und Konjunktionen finden sich in einer Vielzahl von Dokumenten und sind zudem keinerlei Tr¨ ager von auszeichnenden Informationen. Deshalb k¨ onnen Stoppw¨ orter aus der Kandidatenmenge eliminiert werden. Dies geschieht anhand einer sprachabh¨ angigen Stoppwortliste, die auch ¨ uber die o. g. Wortgruppen hinausgehende Stoppw¨ orter enthalten kann.

3. Insbesondere Nomen sind Tr¨ ager von auszeichnenden Informationen. Deshalb kann in diesem Schritt die Kandidatenmenge weiter reduziert werden, indem alle W¨ orter außer Nomen eliminiert werden. Voraussetzung f¨ ur diesen Schritt sind W¨ orterb¨ ucher, die W¨ orter als Nomen klassifizieren.

4. W¨ orter einer nat¨ urlichen Sprache werden bei ihrer Verwendung h¨ aufig gebeugt. Im einfachsten Fall geschieht dies durch Anh¨ angen eines Suffixes an den Wortstamm (z. B.

15

2 Information Retrieval

bei der Bildung des Plurals: Tisch → Tische). Jedoch gibt es auch komplexere Beu-gungsformen, die keinem allgemeing¨ ultigen Muster folgen (Haus → H¨ auser vs. Maus → M¨ ause). Um den Umfang des Index zu verkleinern und damit die IR-Effizienz zu erh¨ ohen sowie den Recall zu verbessern, kann ein IR-System bei der Indexierung (und sp¨ ater auch bei der Verarbeitung der Anfrage) eine Grundformenreduktion oder Stammformenreduktion durchf¨ uhren. Bei der Grundformenreduktion werden Beugungen von Substantiven auf den Nominativ Singular sowie Flexionen von Verben auf den Infinitiv zur¨ uckgef¨ uhrt. Die Stammformenreduktion hingegen f¨ uhrt gebeugte W¨ orter auf ihren Wortstamm zur¨ uck. Beide Reduktionsformen werden auch als Lemmatisierung oder Stemming bezeichnet (vgl. [Fer03], S. 40 f.). Es gibt mehrere Verfahren, um eine Lemmatisierung durchzuf¨ uhren. Eine M¨ oglichkeit besteht in der Aufstellung von Regels¨ atzen, die W¨ orter automatisiert in ihre Stammform transformieren (siehe z. B. [Por79] f¨ ur englische und [Cau99] f¨ ur deutsche Texte). Bei dieser Variante k¨ onnen allerdings nicht alle Sonderf¨ alle lexikalischer Flexionen ber¨ ucksichtigt werden. Ein anderer Ansatz besteht darin, f¨ ur jedes Wort in einem geeigneten Lexikon dessen Grundform bzw. dessen Stamm nachzuschlagen.

5. Im letzten Schritt wird nun die eigentliche Indexierung durchgef¨ uhrt. Die bis hierhin hervorgegangenen Termkandidaten bzw. der Volltext (falls Stoppworteliminierung, Reduktion auf Nomen und Lemmatisierung ausgespart wurden) werden entweder manuell oder automatisch f¨ ur die Eintragung in den Index ausgew¨ ahlt. Bei der ersten Variante

entscheidet dabei ein Spezialist ¨ uber die Eignung als Indexterm. Werden die zul¨ assigen Indexterme f¨ ur einen Eintrag in die invertierte Liste grunds¨ atzlich ” vorgegeben, spricht man von einem kontrollierten Vokabular (vgl. [Fer03], S. 36). Bei der automatischen Indexierung werden meist die Termkandidaten aus den vorherigen Stufen unver¨ andert ¨ ubernommen und als Indexterme verwendet.

2.5 Das Vektorraummodell

Um ein Information-Retrieval-System zu entwickeln, muss man sich zun¨ achst f¨ ur ein IR-Modell entscheiden, welches die Darstellung der Anfragen und Dokumente implementiert. Neben dem weniger m¨ achtigen booleschen Retrieval ist insbesondere das Vektorraummodell sehr leistungsf¨ ahig und deshalb weit verbreitet.

2.5.1 Vektorrepr¨ asentation und Termgewichtung

Beim Vektorraummodell werden Dokumente als Vektoren in einem hochdimensionalen Vek-torraum dargestellt. Jede Dimension repr¨ asentiert dabei einen Indexterm. Im einfachsten Fall wird der Wert der i-ten Komponente eines Dokumentvektors auf 1 gesetzt, falls der i-te Term in diesem Dokument mindestens einmal vorkommt (entspricht dem booleschen Retrieval). F¨ ur eine genauere Relevanzbeurteilung eines Dokuments werden in Vektorkomponenten allerdings nicht bin¨ are Werte, sondern reelle Zahlen zur Gewichtung verwendet. Folgende Parameter fließen dabei in die Berechnung des Gewichts ein (vgl. [Fer03], S. 67 f.):

Termh¨ aufigkeit Im einfachsten Fall wird als Gewicht w i,j die H¨ aufigkeit h(i, j) des Terms t j im Dokument d i verwendet. Dabei wird allerdings nicht ber¨ ucksichtigt, dass in

16

2 Information Retrieval

l¨ angeren Texten die H¨ aufigkeiten der Terme i. d. R. gr¨ oßer sind als in kurzen. Um diese Gegebenheit auszugleichen, wird die Termh¨ aufigkeit in Relation zu dem Vorkommen des h¨ aufigsten Terms t l im Text gesetzt:

Da dieses Maß lediglich das Vorkommen eines Terms innerhalb eines Dokuments betrachtet, ist die Termh¨ aufigkeit ein lokaler Gewichtungseinfluss.

Inverse Dokumentenh¨ aufigkeit Die inverse Dokumentenh¨ aufigkeit (inverse document frequency, kurz IDF) beschreibt die Anzahl der Dokumente d(j), in denen ein Term t j auftritt. Auch hier gibt es zun¨ achst eine einfache Form:

Um die hohen Gewichte seltener Terme abzud¨ ampfen, wird in der folgenden Variante logarithmiert:

N ist dabei die Gesamtanzahl an Dokumenten im Retrieval System. Dieses Maß betrachtet im Gegensatz zur Termh¨ aufigkeit das Vorkommen ¨ uber alle Dokumente und

wird deshalb als globaler Gewichtungseinfluss bezeichnet.

In [BYRN99] (S. 29) wird folgende Berechnung des Termgewichtes empfohlen, da diese beide Parameter kombiniert und somit lokale und globale Gewichtungseinfl¨ usse ber¨ ucksichtigt:

2.5.2 Anfragerepr¨ asentation und ¨ Ahnlichkeitsmaße

F¨ ur die Ausf¨ uhrung der Suche wird auch die Anfrage in einen (ggf. gewichteten) Vektor, den Anfragevektor, umgewandelt. Anschließend werden die Dokumentvektoren mit dem Anfra-gevektor paarweise verglichen und die ¨ Ahnlichkeiten festgestellt. Die dabei resultierenden ¨ Ahnlichkeitswerte k¨ onnen f¨ ur die Erstellung einer Rangfolge genutzt werden, indem die Dokumente nach der ¨ Ahnlichkeit absteigend sortiert werden. Es gibt unterschiedliche ¨ Ahnlichkeitsmaße, von denen zwei im Folgenden kurz mit Berechnungsformel genannt werden (aus [Fer03], S. 72 f.). Dabei ist q der Anfragevektor und w i der Dokumentvektor des Dokuments d i .

• Skalarprodukt:

n

• Cosinus-Maß: n

2 Information Retrieval

Das einfach zu berechnende Skalarprodukt hat in der Praxis mehrere Schw¨ achen aufgezeigt. Der Maximalwert ist offensichtlich nur durch die endliche Anzahl von Vektordimensionen begrenzt. Deshalb haben l¨ angere Dokumente statistisch gesehen gr¨ oßere Chancen, hohe ¨ Ahnlichkeitswerte zu bekommen. Aufgrund dieser Schw¨ ache wurden weitere ¨ Ahnlichkeitsmaße wie z. B. das Cosinus-Maß entwickelt. Beim Cosinus-Maß hat die L¨ ange der Vektoren keinen direkten Einfluss auf die ¨ Ahnlichkeit; lediglich die Ausrichtung der Vektoren wird Ahnlichkeitswert beim Cosinus-Maß stets zwischen −1

und betrachtet. Außerdem liegt der ¨ 1 und erlaubt somit eine absolute Beurteilung. 2.5.3 Definition des Vektorraummodells

Abschließend soll eine Definition des Vektorraummodells genannt werden, die alle oben genannten Aspekte noch einmal zusammenfasst (aus [Fer03], S. 62):

Definition 2.2 Sei T = {t 1 , . . . , t n } eine endliche Menge von Termen und D = {d 1 , . . . , d m } eine Menge von Dokumenten. F¨ ur jedes Dokument d i ∈ D sei zu jedem Term t k ∈ T ein Gewicht w i,k ∈ R gegeben. Die Gewichte des Dokuments d i lassen sich zu einem Vektor w i = (w i,1 , . . . , w i,n ) ∈ R n zusammenfassen. Dieser Vektor beschreibt das Dokument im

Vektorraummodell: Er ist seine Repr¨ asentation und wird Dokumentvektor genannt. Auch Anfragen werden durch Vektoren repr¨ asentiert. Wie bei der Repr¨ asentation der Dokumente wird die Anfrage durch eine Menge gewichteter Terme dargestellt. Der Vektor der Gewichte wird Anfragevektor genannt.

Ahnlichkeitsfunktion s : R n × R n → R definiert, mit der jedem Paar Schließlich sei eine ¨

aus zwei Vektoren x, y ∈ R n ein reeller ¨

2.6 Au߬ osen von Mehrdeutigkeiten

2.6.1 Synonymie und Polysemie

Viele nat¨ urliche Sprachen haben die Eigenschaft, dass Gegenst¨ ande, Vorg¨ ange usw. durch mehrere unterschiedliche W¨ orter beschrieben werden k¨ onnen. Diese in Worte gefassten Ideen werden wie in der einschl¨ agigen Literatur im Folgenden Konzepte genannt. Alle W¨ orter, die das gleiche Konzept beschreiben, werden als Synonyme bezeichnet, sind also W¨ orter gleicher (oder sehr ¨ ahnlicher) Bedeutung. (Beispiel: Rasen ⇒ Wiese, Gr¨ un, Weide. . .). Bei der Suche kann die Existenz von Synonymen dazu f¨ uhren, dass Dokumente nicht gefunden werden, die ausschließlich Synonyme der Suchbegriffe enthalten. Da diese Dokumente jedoch das gleiche Konzept thematisieren, sind sie bez¨ uglich der Suchanfrage relevant. Des weiteren k¨ onnen einzelne W¨ orter mehrere Bedeutungen haben, wobei nur durch den Kontext erkennbar ist, welches Konzept beschrieben wird. (Beispiel: Bank ⇒ 1. Ersch¨ opft setzte sie sich auf eine Bank. 2. Morgen hat sie ein Beratungsgespr¨ ach bei der Bank, weil sie einen Kredit aufnehmen will.) Diese Probleme sind in der Literatur auch als Synonymie und Polysemie bekannt. Abbildung 2.3 zeigt diese beiden Probleme noch einmal grafisch auf. Bewusst werden die Konzepte grafisch dargestellt, um die Unabh¨ angigkeit der Konzepte von einer Sprache zu verdeutlichen.

Im Information Retrieval m¨ ussen diese Probleme gleich an zwei Stellen ber¨ ucksichtigt werden, wenn man die Effektivit¨ at des IR-Systems steigern will. Einerseits muss erkannt

18

werden, welche Konzepte der Autor eines Dokuments vermitteln will, andererseits ist festzustellen, welchen Informationsbedarf ein Benutzer der Suchmaschine mit seinen Suchtermen ausdr¨ ucken m¨ ochte ([Bal01], S. 9). In der englischen Literatur wird dieser Prozess auch als Disambiguation bezeichnet.

Im Folgenden werden kurz einige verbreitete Techniken zum Umgang mit Mehrdeutigkeiten erl¨ autert, die zur L¨ osung oder zumindest Abschw¨ achung o. g. Probleme Einsatz finden k¨ onnen.

2.6.2 Query Expansion

Query Expansion begegnet insbesondere dem Synonymieproblem. Vor Ausf¨ uhrung der Suche werden zun¨ achst anhand eines geeigneten Thesaurus (siehe Abschnitt 2.7) Synonyme oder andere verwandte Begriffe zu den Termen der Anfrage gesucht. Diese Synonyme werden anschließend der urspr¨ unglichen Anfrage hinzugef¨ ugt. Nun wird die modifizierte Anfrage ausgef¨ uhrt. Dieses Verfahren hat zur Folge, dass bei Eingabe von ‘Rasen’ die Suche um die Begriffe ‘Wiese’, ‘Gr¨ un’ und ‘Weide’ erweitert wird. Entsprechend werden auch Dokumente gefunden, die mindestens eines dieser Synonyme enthalten. Bei diesem Ansatz wird folglich nicht versucht, die durch die Suchterme beschriebenen Konzepte korrekt zu erkennen und danach gezielt zu suchen, sondern es werden alle m¨ oglichen Konzepte in Betracht gezogen. Diese Verbreiterung der Suche f¨ uhrt zwar zu einer Verbesserung des Recalls, aber auch gleichzeitig zu einer Reduzierung der Precision. Außerdem muss im Vektorraummodell ber¨ ucksichtigt werden, dass der Ursprungsterm und seine Synonyme bei der Berechnung der Termgewichtung als ein einziger Pseudoterm behandelt werden. Ansonsten w¨ urde ein Synonym, das selten in der Dokumentsammlung verwendet wurde, unberechtigt ein st¨ arkeres Gewicht erhalten, obwohl der Ursprungsterm eine sehr niedrige IDF und damit ein schwaches Gewicht hat (siehe auch [BC98b]).

2.6.3 Festlegung des Konzepts im Dialog mit dem Benutzer

Eine weitere Technik zur Aufl¨ osung von Mehrdeutigkeiten besteht in einer Interaktion mit dem Benutzer. Dieses Verfahren ist insbesondere bei der Verarbeitung der Suchanfrage interessant, da diese i. d. R. nur eine kleine Menge von Termen enth¨ alt ([Fer03], S. 47). Dabei erkennt das System - anhand eines Thesaurus oder unter Nutzung statistischer Methoden - Terme, die mehrdeutig sind, und bietet dem Benutzer eine Menge m¨ oglicher Konzepte

19

2 Information Retrieval

an. Anschließend wird die Suche gezielt auf die Angaben des Benutzers ausgerichtet. Bezugnehmend auf die oben genannten Beispiele m¨ usste der Benutzer bei Eingabe von ‘Bank’ als Suchterm anschließend zwischen ‘Bank (Finanzwesen)’ und ‘Bank (M¨ obel)’ w¨ ahlen, um dem System das korrekte Konzept mitzuteilen. Im Weiteren kann entweder eine Query Expansion durchgef¨ uhrt werden, die allerdings nur Synonyme aus den festgelegten Konzepten verwendet, oder die nun spezifizierten Anfragekonzepte werden mit Dokumentkonzepten in Bezug gebracht, falls diese f¨ ur die Dokumente hinterlegt sind.

2.6.4 Nutzung von Kookurrenzdaten

Es wurde bereits festgestellt, dass mehrdeutige W¨ orter ihre Bedeutung durch den Kontext erhalten, also durch das gleichzeitige Auftreten mit bestimmten anderen W¨ ortern. Bei der Erstellung einer Kookurrenzstatistik wird analysiert, welche W¨ orter besonders h¨ aufig gleichzeitig in einem Dokument auftreten ([Bal01], S. 10 und [Fer03], S. 224). Voraussetzung f¨ ur eine aussagekr¨ aftige Kookurrenzstatistik ist ein so genannter Korpus, also eine große, f¨ ur die Dom¨ ane repr¨ asentative Textsammlung. Die Qualit¨ at des Korpus bedingt die Korrektheit und den Umfang der Kookurrenzdaten. In der Praxis stellt diese Voraussetzung eines der gr¨ oßten Probleme dar ([BC98b]).

2.6.5 Erkennung von Konzepten anhand von Kontext

Die Konzeptauswahl im Dialog mit dem Anwender ist zwar die zuverl¨ assigste Methode zur Aufl¨ osung von Mehrdeutigkeiten, w¨ ahrend der Indexierung jedoch meist nicht praktikabel. Stattdessen ist neben der Nutzung von Kookurrenzdaten die Erkennung von Konzepten anhand eines speziellen W¨ orterbuches m¨ oglich. Dieses W¨ orterbuch enth¨ alt zu jedem mehr-

deutigen Begriff die m¨ oglichen Konzepte und gibt zur Differenzierung ” So k¨ onnte der mehrdeutige Begriff ” auf das Geldinstitut und in Kookurrenz mit dem Kontextwort ” abgebildet werden. Dabei kann der im Ursprungstext betrachtete Umgebungsbereich nur wenige W¨ orter vor und nach dem mehrdeutigen Begriff, aber auch das gesamte Dokument umfassen. Die Genauigkeit dieser automatisierten Konzepterkennung h¨ angt unmittelbar von dem Umfang und der Qualit¨ at des genutzten W¨ orterbuchs ab. Technisch l¨ asst sich diese Vorgehensweise durch das Vektorraummodell realisieren. Es werden sowohl f¨ ur das mehrdeutige Wort und seine Umgebungsw¨ orter als auch f¨ ur den W¨ orterbucheintrag mit den Kontextw¨ ortern Vektoren aufgespannt. Nach einem Vergleich mittels Cosinus-Maß wird das ¨ ahnlichere Konzept gew¨ ahlt.

2.7 Thesauren

In seiner einfachsten Form besteht ein Thesaurus zum einen aus einer Liste wichtiger W¨ orter einer spezifischen Dom¨ ane, zum anderen aus verwandten Begriffen f¨ ur jedes dieser W¨ orter. Oft handelt es sich dabei um Synonyme ([BYRN99], S. 170). Fortgeschrittene Thesauren haben jedoch eine weit komplexere Struktur. So k¨ onnen sie zus¨ atzlich auch Phrasen, Antonyme, Oberbegriffe und speziellere Begriffe beinhalten. Bei mehrdeutigen W¨ ortern werden die verschiedenen Konzepte gruppiert und einzeln aufgelistet. Somit erfassen Thesauren W¨ orter und Ausdr¨ ucke eines Sachgebiets und beschreiben die Beziehungen zwischen ihnen.

20

Wenn Thesauren im IR eingesetzt werden, dienen sie der Beschreibung des Wissensgebietes, in dem die Suchmaschine eingesetzt wird, und der eindeutigen Zuordnung von Dokumenten zu dieser Dom¨ ane. Der Thesaurus bildet das kontrollierte Vokabular, d. h. er beinhaltet die Terme, die zur Indexierung verwendet werden d¨ urfen (vgl. [Fer03], S. 54). Jeder Term im Thesaurus ist sorgf¨ altig ausgew¨ ahlt, hat innerhalb der spezifischen Dom¨ ane eine wohldefinierte Bedeutung und ist mit einer Menge von verwandten W¨ ortern verkn¨ upft. Die W¨ orter des kontrollierten Vokabulars werden Deskriptoren genannt und ausschließlich diese werden zur Indexierung von Dokumenten verwendet. Falls ein Dokument ein oder mehrere Synonyme eines Deskriptors enth¨ alt, wird zur Indexierung dieses Dokuments der Deskriptor verwendet, da dieser zusammen mit den Synonymen (innerhalb des Fachgebiets) dasselbe Konzept repr¨ asentiert.

Ein umfangreicher Thesaurus ist eine wichtige Voraussetzung f¨ ur die Query Expansion, bei der die urspr¨ ungliche Anfrage um verwandte W¨ orter erweitert werden soll.

F¨ ur die englische Sprache ist im Internet der freie Thesaurus WordNet ¹ verf¨ ugbar, der

¹ http://wordnet.princeton.edu. (Abruf 20.06.2006)

21

2 Information Retrieval

seit 1985 am Cognitive Science Laboratory der Princeton University entwickelt wird (j¨ ungste Ver¨ offentlichung: WordNet 2.1 im M¨ arz 2005). ¨ Ahnliche Projekte f¨ ur Deutsch und weitere

europ¨ aische Sprachen wurden zwar initiiert, haben aber seit l¨ angerem keine Aktualisierung

erfahren oder sind nicht frei zug¨ anglich. Dazu z¨ ahlt auch das Projekt GermaNet ² , dessen

Datenbestand vom Oktober 2001 stammt, das aber nicht zum freien Download steht. Eine neue Release war f¨ ur Mai 2006 angek¨ undigt, jedoch zum Zeitpunkt der Erstellung dieser Arbeit (Juni 2006) noch nicht ver¨ offentlicht.

Abbildung 2.4 auf Seite 21 zeigt die Ergebnisse von WordNet bei der Eingabe von ‘bench’.

² http://www.sfs.uni-tuebingen.de/lsd. (Abruf 20.06.2006)

22