Indexierer für Freitextsuche

Entwicklung eines Modells für einen Indexierer für die schnelle Suche innerhalb von freien Texten.

Ein Index für Freitextsuche in Dokumenten besteht aus einer Tabelle mit Wörtern als Schlüssel und eine Menge von Positionen als Attribute

Eine Position besteht aus Dokumentenname und Positionsangabe im Text, z.B. i-tes Zeichen oder i-tes Wort im Text oder Zeilen- und Spaltennummer.

Ein Index wird aufgebaut, indem ein Text in Wörter zerlegt wird und diese Wörter in die Tabelle eingetragen werden.

Suchanfragen an den Index liefern eine Menge von Dokumenten einschließlich Positionen für die Vorkommen in den Texten.

Die einfachste Anfrage ist eine exakte Suche nach einem einfachen Wort.

Eine allgemeinere Form der Suche ist die Präfixsuche, bei der man den Anfang eines Wortes vorgibt und alle Wörter sucht, die mit diesem Wort beginnen.

Eine Variante der einfachen Such-Anfrage ist eine unscharfe Suche, in der Wörter nicht genau zeichenweise verglichen werden, sondern unscharf.

Anfragen können mit UND und ODER verknüpft werden.

Die Suche nach Phrasen, genauer Wortfolgen, kann manchmal sinnvoll sein, z.B. nach "Angela Merkel". hierzu ist die Positionsangabe innerhalb eines Textes auszunutzen. Dann kann diese Suche auf zwei einfache Suchen zurückgeführt werden.

Eine Verallgemeinerung der Suche nach Phrasen ist die kontextsensitive Suche, d.h. eine Suche nach mehreren Begriffen, die "dicht" nebeneinander verwendet werden, so dass Texte mit den Wortfolgen "Gerhard Schröder und Wladimir Putin", "Schröder und Putin", "Putin und Schröder" gefunden werden, aber nicht "Schröder ... (25 Wörter) ... Putin".

Die Erzeugung eines Indexes erfordert einige Flexibilität bei der Auswahl der zu indexierenden Wörter um eine Form der ungenauen Suche zu ermögliche und um Speicherplatz zu sparen.

Es muss festgelegt werden, welche Zeichenfolgen ein Wort sind.

Es gibt uninteressante Wörter, die nicht zu berücksichtigen sind, in diesem Satz z.B.: es, gibt, die, nicht, sind, in, diesem

Groß- und Kleinschreibung ist häufig uninteressant: Am Anfang eines Satzes wird jedes Wort groß geschrieben, aus Verben können Substantive abgeleitet werden.

Umlaute und ß werden häufig durch Ersatzsequenzen dargestellt.

Abkürzungen und Firmennamen können wichtig sein, obwohl sie die vorgegebene Syntax eines Wortes nicht erfüllen, z.B. 3Com

Eine abstrakte Syntax in Haskell für die Indexstruktur und die Anfragen.

Und ein OMT-Diagramm für ein geeignetes Datenmodell für den Index und die Anfragen.

Konkretisierung und Flexibilisierung des OMT-Modells und/oder der abstrakten Syntax, so daß flexible Implementierungen und einfache Erweiterungen ermöglicht werden