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
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.
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.
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.
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.
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.
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.
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).
Während des Ladevorgang werden die Rohdaten umorganisiert und
zusätzliche Informationen über die Datenstruktur gespeichert, wodurch
sich der Zugriff bei Datenabfragen verbessert.
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).
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 ...
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
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.
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".
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).
Ä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".
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.
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.
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:
-
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).
-
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.
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.