INFORMATION RETRIEVAL SYSTEME

Geschwurbel von Daniel Schwamm (Wintersemester 1992/1993)

INFORMATION RETRIEVAL SYSTEME

Übungsarbeit

vorgelegt am

Lehrstuhl für Wirtschaftsinformatik II

Prof. Dr. J. Niedereichholz

im

Wintersemester 1992/1993

von

Daniel Schwamm

aus Mannheim

Wirtschaftsinformatik, 7. Semester

Inhalt

1. Einführung

Ein Information Retrieval System (IRS) - Was ist das nun wieder? Wie lässt sich so etwas beurteilen? Und welchen Anforderungen sollte es gerecht werden?

Im folgendem wird versucht, darauf eine Antwort zu geben. Neben einer allgemeinen IRS-Betrachtung wird hierzu kurz PIZZA gestreift, ein real existierendes IRS, welches von Moscheh Mresse, wissenschaftlicher Mitarbeiter des Instituts für Informatik an der Universität Zürich, 1984 in seinem Buch "Information Retrieval - Eine Einführung" beschrieben wird.

2. Allgemeine Grundlagen von IRS

2.1. Zielsetzung

Der Hardwaremarkt boomt, die Automation schreitet fort, und also wachsen die elektronischen Datenbestände in den Büros ins Unermessliche. Die Folge: Das Auffinden eines bestimmten Datums entartet leicht zur Suche nach der berühmten Stecknadel im Heuhaufen. Abhilfe dagegen soll Information Retrieval schaffen, was "I.w.S. das Auffinden (Wiedergewinnen) bestimmter Informationen innerhalb eines grossen gespeicherten Datenbestandes" bedeutet.

2.2. Grundidee

Karteikartensysteme beherrschten Büros lange vor Datenbank-Managementsysteme (DBMS), und sie erfüllten ihren Zweck nicht schlecht. Denn ihre Handhabung war einfach, und die Information, die als Resultat einer jeden Suche erwartet wurde, befand sich am Ende stets auf einer einzelnen, anschaulichen Karte.

Auch IRS beschreiben diesen Weg, allerdings statt manuell maschinell, wodurch sie sich gegenüber den herkömmlichen Karteikartensysteme von zahlreichen Restriktionen befreien konnten: die Kartenanzahl und ihre Informationsmengen sind nicht länger begrenzt, Suchmerkmale können zu logischen Suchausdrücken verbunden werden, Datenbestände sind über Netzverbindungen schneller zugänglich, usw.

2.3. Begriffe

2.3.1. Informationseinheit (IE)

Eine IE entspricht einer elektronischen Karteikarte. Sie beinhaltet den Text (eine Folge unformatierter Zeichen, Wörter oder Sätze) und die Deskriptoren. Synonyme Verwendung finden die Bezeichnungen Entität, Objekt oder Dokument.

2.3.2. Deskriptor (DK)

Ein DK dient zur Kennzeichnung von Texten in (unformatierten) Datenbanksystemen. Ihre Gesamtheit wird in Thesauri gespeichert. In der Literatur bezeichnet man DK oft auch als Attribut, Merkmal, Fragekriterium, Schlagwort oder Stichwort.

2.3.3. Thesaurus (Wörterbuch)

Ein Thesaurus ist ein gespeicherter Katalog von DK, welche über Querverweise so miteinander verknüpft wurden, dass sie eine komprimierte Systematik des abgespeicherten Wissensgebiets liefern. I.d.R. ist er baumartig aufgebaut, was schnellen Zugriff auf diejenigen DK erlaubt, über die die Verbindung zu den IE aufgenommen wird. Zudem verweist er häufig auch noch auf synonyme Fragekriterien.

2.3.4. Datenaufnahme

Zur Datenaufnahme stellen IRS benutzerfreundliche Methoden zur Verfügung, und zwar für die Dateneingabe, für die Definition der Struktur von IE, und für die Text- und DK-Aufnahme. Als Resultat gewinnt man die Rohdaten (eine Menge von IE; den Informationspool).

2.3.5. Ladevorgang

Während des Ladevorgang werden die Rohdaten umorganisiert und zusätzliche Informationen über die Datenstruktur gespeichert, wodurch sich der Zugriff bei Datenabfragen verbessert.

2.3.6. Datenabfrage

Die Datenabfrage (Recherche, query) umfasst alle Tätigkeiten, die der Wiedergewinnung der Daten dient. Dabei gilt für den Benutzer: "Durch geeignete Kombination von Fragekriterien ... lässt sich der Antwortumfang einschränken". U.U. sorgen IRS selbst für die nötige Präzision, indem sie den Benutzer zu Neuabfragen auffordern (Dialog-Prinzip).

2.3.7. Klassifizierung

IRS gibt es in vielen Variationen: Ein Volltext-IRS muss den gesamten Text in maschinenlesbarer Form vorliegen haben, ein anderes erlaubt die automatische DK-Generation (s.f.w.), und wieder ein anderes lässt sich die gespeicherten Daten von DBMS verwalten. Einen Standard darüber, was ein IRS können muss, gibt es also nicht - nur eine Vorstellung darüber, was es können sollte ...

3. Theoretische Aspekte

3.1. Beurteilung der Güte

Gut geeignet zur quantitativen Beurteilung der Güte eines IRS ist die Länge der Antwortzeit nach einer Abfrage. Hier gilt natürlich: je kürzer, desto besser.

Schwieriger wird es bei der qualitativen Beurteilung der Güte eines IRS; die Qualität einer Antwort hängt ja davon ab, wie viele der gespeicherten, relevanten IE gefunden werden, und wie viele der ausgewählten IE relevant sind. Als Masszahlen werden daher von Mresse u.a. vorgeschlagen:

  • die Präzision = ausgewählte relevante IE/alle ausgewählten IE
  • die Ausbeute = ausgewählte relevante Dokumente bzw. alle gespeicherten IE
  • die Ausfallrate = ausgewählte irrelevante IE bzw. alle gespeicherten irrelevanten IE

3.2. Deskriptorenauswahl (Indexing)

Eine effiziente Datenabfrage kann nur bei vorheriger Inhaltserschliessung der gespeicherter Dokumente garantiert werden. Daher bieten IRS Methoden und Verfahren zur DK-Auswahl an, mit denen eine IE charakterisiert werden kann.

Bei der manuellen Auswahl müssen die relevanten DK eines Dokuments vom Benutzer selbst ausgewählt und gekennzeichnet bzw. separat eingegeben werden - genauso wie Eselsohren in einem Buch. I.d.R. wird dies aber (anders als bei Büchern) nur von fachlich versierten Dokumentatoren vorgenommen werden können.

Es existieren auch automatische Verfahren, die teils mit statistischen, teils mit sprachwissenschaftlichen Methoden zu einer DK-Auswahl von passabler Qualität gelangen. Relevante Stichwörter werden z.B. dadurch ermittelt, dass sie im Thesaurus wiedergefunden bzw. im Anti-Thesaurus (Stopp-Listen) nicht wiedergefunden werden. - Oder aber sie werden durch kleine Textanalyse-Verfahren gewonnen, die etwa wie im folgenden Beispiel vorgehen: Die IE "Der Bandit war beschäftigt wie ein einarmiger Tapezierer" besitzt die allgemeine DK "Bandit" und "einarmig"; daraus lässt sich nun ein speziellerer DK "einarmiger Bandit" für zukünftige, präzisere Abfragen kreieren.

3.3. Gewichtung der selektierten Dokumente

Ein DK (z.B. "Knochen") kann in vielen IE vorkommen, und in einigen sogar mehrfach (z.B. in einem Text über dt. Museen). Um diesem Tatbestand bei Abfragen Rechnung tragen zu können, ermitteln einige IRS in Dokumenten die Häufigkeit von DK, gewichten sie dementsprechend, und geben hierüber Benutzern (z.B. einem hungrigem Dackel) die Möglichkeit, lohnende Dokumente von den weniger lohnenden zu trennen. Dies rentiert sich v.a. dann, wenn ein IRS rückgekoppelte Abfragen (relevance feedback) erlaubt: dem Benutzer wird eine (Zufalls-)Auswahl von Dokumenten gemäss absteigender Relevanz präsentiert, er trennt die relevanten von den nicht-relevanten, das IRS modifiziert die Abfrage und trifft eine erneute Auswahl, wobei gilt: "Bei Wiederholung der Abfrage soll die Ausbeute bei gleichbleibender oder erhöhter Präzision verbessert werden".

3.4. Suchen

3.4.1. Metazeichen

Wer kennt das nicht? Man sucht im Telefonbuch den DK "Maier", sieht aber zuerst alle Positionen von "Meier", "Meyer" und "Mayer" durch - und das natürlich umsonst.

Derlei vage Kenntnisse von DK sind erfahrungsgemäss eher die Regel denn die Ausnahme. Daher bieten (vermutlich) alle IRS die Möglichkeit, in einer Abfrage Metazeichen - Platzhalter, Substitute oder 'Joker' - einzusetzen. Statt nach "Meier", "Meyer", "Mayer" und "Maier" lässt man dann das IRS einfach einmalig nach "M??er" forschen (allerdings dann evtl. sequenziell).

3.4.2. Soundex-Methode

Ähnlich klingende Worte gibt es in allen Sprachen zuhauf, z.B. Sex statt Sechs oder Air France statt Eier-Franz. Die Soundex-Methode ist nun die Angel, mit die es möglich ist, in IRS, trotz falschem Köder (den DK), die richtige Beute (also die IE) aus dem Informationspool zu fischen - in dem sie den zu findenden DK und die gefundenen DK auf max. einen Buchstaben und drei Zahlen reduziert und dann miteinander vergleicht. Eine Abfrage nach "Paulchenneumann" findet so immerhin noch IE mit dem DK "Paul Newman".

3.4.3. Vergleichen von Zeichenketten

Eine der häufigsten, und damit auch zeitkritischsten Operationen von IRS ist das Auffinden von Mustern in grösseren Texten. Mresse nennt in diesem Zusammenhang vier Algorithmen: den SF-Algorithmus mit Worst-case-Komplexität O( Musterlänge * Textlänge), und die KMP-, BM- und AC-Algorithmen mit O( Musterlänge + Textlänge).

IRS-lohnend ist v.a der BM-Algorithmus: jedes Textzeichen wird nur max. einmal mit den Musterzeichen verglichen, und dadurch, dass die Vergleiche am Anfang mit dem letzten Musterzeichen begonnen werden, können u.U. Musterlänge-1 Vergleiche eingespart werden.

3.5. Kontrolle konkurrierender Zugriffe (concurrency control)

Die Kontrolle konkurrierender Zugriffe sorgt durch 2-Phase-Language (2PL) oder Timestamp-Ordering (T/O) für die Serialisierung von Transaktionen. Da in IRS immer nur max. ein Benutzer Schreiben kann, werden Deadlocks durch 2PL hinreichend verhindert, während sie bei T/O sowieso von vorneherein ausgeschlossen sind.

4. Ein Beispiel - PIZZA

Das IRS PIZZA entstand nicht etwa in der Pizzeria Da Gina Mimmo, sondern als Pilotstudie für das Gerichtlich-Medizinische Institut der Universität Zürich. Implementiert wurde es auf IBM 3033 unter OS/MVS mit VSAM (Virtual Storage Access Method) und auf dem UNIX-Mikrorechner ONYX. Die Daten sind unterteilt in die Relationen:

  • text: enthält Texte in ursprünglicher Form; ein Direkt-Zugriff ist möglich
  • desc: enthält DK und Adresse des ersten orth-Element; variabel lange Sätze
  • orth: enthält Text-, DK-Adressen und logische Verknüpfungswerte

Aufgrund seiner relationalen Datenorganisation kann in PIZZA günstigerweise SQL zur Datenabfrage benutzt werden; ein 'ask <text> for <boolescher Ausdruck>' wird dabei von einem Compiler-Interpreter-System folgendermassen weiterverarbeitet:

  1. Der Compiler wandelt die Abfrage in sog. S-Code-I um, und zwar zur symbolischen DK-Suche in der vorsortierten desc-Datei. Da dort variabel lange Datensätze vorliegen, binäres Suchen aber ungleich schneller ist als sequenzielles, werden Satzadressen jeweils nach einem einfach-genialen Prinzip berechnet. Nur wenn der erste Buchstabe des DK ein Metazeichen ist, wird in PIZZA über den SF-Algorithmus gesucht (d.h. sequenziell).
  2. Nach dem Finden der DK werden deren Namen durch Byte-Adressen der orth-Datei ersetzt. Es entsteht somit S-Code-II, aus dem der Interpreter (eine sogenannte Hypothetische Stack Maschine) die IE selektieren kann. Die Stack-Elemente sind dabei Bit-Ketten, in denen jedes gesetzte Bit für einen gewählten Text steht, d.h. also die Stack-Breite ist identisch mit der maximalen Anzahl wählbarer Texte, wohingegen die Stack-Tiefe identisch ist mit der Anzahl der Operationen auf die Textmengen.

Hinweis: Dadurch, dass der Compiler unabhängig von der eigentlichen Datenbank ist - er löst Referenzen auf Texte und DK ja nicht auf, sondern benutzt nur deren Symbole -, lässt sich PIZZA auch leicht als verteiltes System konfigurieren.

5. Schlussbemerkung

IRS bieten herrliche Spielwiesen für Freunde kniffliger Algorithmen (z.B. zur Vektoren-Kompression, Normalformen, Anwendungsmöglichkeiten nicht-boolescher DK-Ausdrücken, und und und). Doch am Beispiel PIZZA zeigte Mresse sehr schön auf, dass auch weniger aufwendige IRS nicht nur einsetzbar sind, sonder auch alle an sie gestellten Erwartungen erfüllen können (trotz des schwachen Manipulationsteils). Die unzähligen Funktionen grosser IRS, wie z.B. bei STAIRS von IBM, wirken dagegen doch eher abschreckend auf den normal-sterblichen Benutzer.

Auch in einem anderen Punkt scheint mir PIZZA recht zukunftsweisend zu sein; sollten nämlich Assoziativspeicher wirklich einmal zum Standard werden, gehören Tabellen und Zeiger der Vergangenheit an - eine relationale Datenorganisation wie bei PIZZA wäre dann eindeutig favorisiert.