Archivierung und Indexierung

Texte als digitale Objekte

Struktur: Digital Object besitzt aggregierte Struktur

z.B. Buch - Kapitel - Vers - Wort

Serialisierung: atomare (nicht weiter zerlegbare) DO sind linear geordnet

Suche = Vergleichsoperation für atomare DO

Granularität

Maximales Vokabular bedeutet maximale Granularität (jedes Wort, jede Fundstelle)

Maximalkonkordanz = Codierung des Textes >> kann nicht wesentlich kleiner werden als Text selbst

Index

Metadatensuche

Datensuche (Volltextsuche)

Idee: ADT Wörterbuch

Assoziation zwischen Schlüssel und Wert

Assoziationen speichern und ermöglichen effizienten Zugriff von Schlüsseln auf Werte

Enkodierung des Index

f = Zahl der verschiedenen Suchterm-Dokument-Assoziationen

N = Zahl der Dokumente in der Sammlung

Identifikator für ein Dokument kann mit log N Bits kodiert werden

Indexgröße = f * log N

verkleinern: Vorverarbeitung

Casefolding, Stopwords, Stammformreduktion

verkleinern: Indexkompression

invertierte Liste = Verweis auf Dokumente, in denen der Suchterm vorkommt (Häufigkeit des Suchterms + Verweis auf i-tes Dokument)

Liste von Positionsdifferenzen

Kompressionsprinzip: d-gaps (Prinzip Huffman-Kodierung; höhere Häufigkeit >> kürzere d-gaps)

Binärkodierung: alle Codewörter für d-gaps haben die gleiche Länge, optimal wenn gleiche Wahrscheinlichkeiten

Unärkodierung: optimal, wenn d-gaps mit Wahrscheinlichkeit 2^-g (Länge des Codeworts für die d-gap g)

Golomb-Kodierung

Teil 1: Binärkodierung, Teil 2: Truncuated Binary Codierung

Verweisdichte = f / (N*n)

Dokumentensignaturen

Vorteil: einfache Implementierung

Prinzip: jedem Suchterm und jedem Dokument wird (nicht unbedingt eindeutige) Signatur zugeordnet

Kompatibilität von Suchterm + Dokument wird durch Vergleich der Signaturen ermittelt

m.H. Hashfunktion (Kollisionsvermeidung + möglichst gleichmäßige Verteilung

Suchanfrage q ist kompatibel mit einem Dokument d wenn s(q) = s(q) ^ s(d)

bitweise Disjunktion aller Signaturen der Suchterme im Dokument erhält man Signatur von d

Dreiwertige Anfragelogik: YES - NO - MAYBE