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