Spree SoSe 2011

VolltextsucheVolltextsucheSequentielle Suche und interviertes Sequentielle Suche und interviertes

DateisystemDateisystem

Seminar I-Prax: Inhaltserschließung visueller Medien, 5.10.2004Spree SoSe 2011

SuchproblemTreffer

Wie funktioniert die Suche in einer Datenbank ?

Modell der sequenziellen Suche mit Musterabgleich

Graphik: Winfried Gödert: Konzepte, Methoden und Verfahren des Information Retrieval, Folie 6

1101001110110001010101100111011010101000010101111..

010101100101011001010110

NeinNeinNein

01010110

Nein

01010110

Nein

01010110

Treffer

Sequentielle Suche / Mustererkennung im Dokument

Methode:

Die Zeichenkette wird nacheinander im gesamten Dokument gesucht:

Probleme:

Zeitaufwändig

Nur möglich, wenn der gesamte Datenbestand vollständig vorliegt.

Quelle: teilweise übernommen von Gödert

Eintrag01Eintrag02Eintrag03Eintrag04Eintrag05Eintrag06Eintrag07Eintrag08Eintrag09Eintrag10Eintrag11Eintrag12Eintrag13Eintrag14Eintrag15Eintrag16Eintrag17Eintrag18Eintrag19Eintrag20Eintrag21Eintrag21Eintrag22Eintrag23Eintrag24

Suche sequenziell ?

NeinNeinNeinNeinNeinNeinNeinNeinNeinNeinNeinNeinNeinNeinNeinNeinNeinNeinNeinNeinNeinNeinNeinNeinNein

Kann das sein?

Gesuchter Eintrag

Fast wörtlich übernommen: Winfried Gödert: Konzepte, Methoden und Verfahren des Information Retrieval, Folie 8

Wie funktioniert die Indexsuche in Datenbanken?

Numerischer und alphabetischer IndexGliederung

Seminar I-Prax: Inhaltserschließung visueller Medien, 5.10.2004Spree SoSe 2009

Dok. 1:<p> Das ist eine Banane</p>

1 das

2 ist

3 eine

4 Banane

Banane 4

Das 1

Eine 3

Ist 2

Dok. 2: <h1>Das ist eine grüne Banane</h1>

Numerischer Index Alphabetischer Index

Wenn ein neues Dokument hinzukommt, muss der alphabetische Index nur ergänzt werden.

grüne wird als neuer Eintrag ergänzt.

1 das

2 ist

3 eine

4 Banane

5 grüne

Index aufbauen und ergänzenGliederung

Seminar I-Prax: Inhaltserschließung visueller Medien, 5.10.2004Spree SoSe 2011

Zeile Wort Eingang

1 banane 4

2 das 1

3 eine 3

4 ist 2

5 grüne 5

Zeile Wort Eingang

1 banane 4

2 das 1

3 eine 3

4 grüne 5

4 wird 5 ist 2

6 wird 7

Alle Einträge unterhalb von eine ändern ihre Position, der Index wird bei jedem Neuzugang neu aufgebaut

grüneEs wird lediglich eine Zeile ergänzt

Invertiertes DateisystemEinführung

Seminar I-Prax: Inhaltserschließung visueller Medien, 5.10.2004Spree SoSe 2011

Wort.Id Dok.Id Position Frequenz Zusatz

1 1

2

1

1

1

1

P

h1

2 1

2

2

2

1

1

P

h1

3 1

2

3

3

1

1

P

h1

4 1

2

3

4

5

2

1

1

1

P

h1

h3

5 2

3

4

1

1

1

h1

h3

Banane 4das 1eine 3grüne 5ist 2

Dok.3 <h3>grüne Banane</hr´3>

Alphabetischer Index/ Zugangsliste

Invertierte Liste

Und noch ein Trick: schnelle Suche im alphabetischen Index

Eintrag01Eintrag02Eintrag03Eintrag04Eintrag05Eintrag06Eintrag07Eintrag08Eintrag09Eintrag10Eintrag11Eintrag12Eintrag13Eintrag14Eintrag15Eintrag16Eintrag17Eintrag18Eintrag19Eintrag20Eintrag21Eintrag21Eintrag22Eintrag23Eintrag24

Bildung von Hälften

Test, ob gesuchter Eintrag in der ersten Häfte

oder in der zweiten Häfte

Nein

Ja

Fast wörtlich übernommen: Winfried Gödert: Konzepte, Methoden und Verfahren des Information Retrieval, Folie 9

Das Verfahren wird mit der zutreffenden Hälfte fortgesetzt

Eintrag13Eintrag14Eintrag15Eintrag16Eintrag17Eintrag18Eintrag19Eintrag20Eintrag21Eintrag21Eintrag22Eintrag23Eintrag24

Nein

Ja

Eintrag19Eintrag20Eintrag21Eintrag21Eintrag22Eintrag23Eintrag24

Das Verfahren folgt einem binären Entscheidungsbaum und kommt auch bei großen Indizes sehr schnell zu einem Ergebnis

Ja

Eintrag19Eintrag20Eintrag21Eintrag21

Ja

Eintrag19Eintrag20

Nein

Ja

Fast wörtlich übernommen: Winfried Gödert: Konzepte, Methoden und Verfahren des Information Retrieval, Folie 10

RessourcenEinführung

Seminar I-Prax: Inhaltserschließung visueller Medien, 5.10.2004Spree SoSe 2011

CROFT 2011

Croft, Bruce. W; Metzler, Donald; Strohman, Trevor GerhardBegleitmaterialien zum Buch: Search Engines : Information Retrieval in Practice. Abruf: 2011-04-05. Download unter: http://dg3rtljvitrle.cloudfront.net/slides/chap5.pdf

GÖDERT 2009

Gödert, Winfried: Konzepte, Methoden und Verfahren des Information Retrieval. Vorlesungsskript SS 2009. Fachhochschule Köln : Institut für Informationswissenschaft. Abruf: 2011-04-05. Download unter: http://www.fbi.fh-koeln.de/institut/personen/goedert/goedert_lehre.php