10.01.2008PG 520 - L-Tree - Martin Böhmer1 Der Lexical Tree und seine Freunde Ein Crashkurs zur Erstellung eines großen Wort-Indexes

10.01.2008 PG 520 - L-Tree - Martin Böhmer 1

Der Lexical Tree und Der Lexical Tree und seine Freundeseine Freunde

Ein Crashkurs zur Erstellung eines großen Wort-Indexes


AgendaAgenda

• Lexical Tree– Grundlagen und Datenstruktur– Implementierung– Experiment Bundestagsprotokolle– Speicherplatz-Problematik

• Inverted Files– Prinzip– im Lexical Tree

• Fazit


Lexical TreeLexical TreeGrundlagen und Grundlagen und DatenstrukturDatenstruktur


Der Lexical TreeDer Lexical Tree

• auch kurz „L-Tree“ genannt• Datenstruktur zur Indexierung• Vorteile:

– sehr kompakte Datenhaltung– eignet sich auch für große Datenmengen

• Anwendungen:– Spracherkennung (Indexierung von

Lauten)– Wörterbuch-Index (Dokumente finden)


Die Datenstruktur:Die Datenstruktur:IdeeIdee

„Das was aus Bestandteilen so zusammengesetzt ist, dass es ein einheitliches Ganzes bildet, nicht nach Art eines Haufens, sondern wie eine Silbe, das ist offenbar mehr als bloß die Summe seiner Bestandteile.“ - Aristoteles


Die Datenstruktur:Die Datenstruktur:IdeeIdee

• Zerlege Daten, so dass– ihre Gemeinsamkeiten nur einmal

gespeichert werden– sich die Teile zu einem Ganzes

zusammenfügen

• Das ist mehr als die Summe der Bestandteile!– Speicherplatz sparen: weniger ist mehr– Zusatzinformationen verwalten


Die Datenstruktur:Die Datenstruktur:Von Bäumen, Knoten und Von Bäumen, Knoten und

Kindern…Kindern…• L-Tree ist eine Baum-Datenstruktum

(engl. „tree“ = Baum)

• Baum T = (V, E)– Kontenmenge V mit |V| = n– Kanten E = { (vi, vj) | vi, vj € V} mit |E| = m– T ist zusammenhängend und es gilt: m = n - 1

• Pfad P = {v1, …, vk € V |(vi, vi+1) € E für alle i = 1, …, k-1}Länge des Pfads: k

• Tiefes eines Baum: Längster Pfad von Wurzel zu Blatt

Knoten

Kinder

Elter

Wurzel(-knoten)


Die Datenstruktur:Die Datenstruktur:L-Tree als Wort-Dokument-L-Tree als Wort-Dokument-

IndexIndex• Menge von Dokumenten D, bestehend aus

Wörtern• Speichere Wort w = b1, …, bn (Buchstaben):

– Ein Konten v speichert bifür i = n speichere Dokumente in denen w vorkommt

– Elter von v speichert bi-1

– Ein Kind von v speichert bi+1

• Maximale Anzahl an Kindern:59 (A-Z, a-z, Ää, Öö, Üü, ß)

• Tiefe des L-Tree:Längstes Wort {d € D | b1…bn € d}

b1

…

bn


d1d1, d2d2

d2

L-Tree als Wort-Dokument-L-Tree als Wort-Dokument-Index:Index:

Ein BeispielEin Beispiel

d1: Grottenolme sind Lurche.d2: Lurche singen laut lachend

in der Grotte.

-

d

e

r

d2

c

h

e

n

d

d1

G

r

o

t

t

e

n

o

l

m

e

d2

i

n

L

u

r

c

h

e

d2

l

a

u

td1

i

s

n

d

d2

g

e

n


Lexical TreeLexical TreeImplementierungImplementierung


KlassenKlassenÜberblickÜberblick

• LexcialTreeImplemntierung des L-Tree

• LexcialTreeNodeImplentierung eines Baumknoten

• LexicalTreeBuilderAufbau oder Laden des L-Trees aus Datei

• FileSpider / WordSplitterFastDatei-Enumerator / Wort-Enumerator


KlassenKlassenJava Datentypen in Java Datentypen in LexicalTreeNodeLexicalTreeNode

{d € D | b1…bn € d}

b1

…

bn

charHashmap<character, LexicalTreeNode>

Hashmap<<docIdType>, Integer>


Nutzung des L-TreeNutzung des L-TreeErstellungErstellung

• Nutze Klasse LexicalTreeBuilder• Aufbau des L-Tree

LexicalTree<String> ltree = LexicalTreeBuilder.buildLTree(<docPath>, <stopwordfile>);ltree.saveToFile("ltree_full.dat");

• Laden des L-TreeLexicalTree<String> ltree = LexicalTreeBuilder.loadFromFile("ltree.dat");


Nutzung des L-TreeNutzung des L-TreeWichtige AbfragenWichtige Abfragen

• Ist das Wort „Grottenolm“ im L-Tree?– Aufruf: ltree.containsWord("Grottenolm")– Rückgabe: boolean

• Welche Dokumente enthalten „Grottenolm“?– Aufruf: ltree.getDocumentIds("Grottenolm")– Rückgabe: Set<String>

• Welche Dokumente enthalten „Grottenolm“ und wie oft kommt das Wort dort vor?– Aufruf: ltree.getDocumentIds("Grottenolm")– Rückgabe: Hashmap<String,Integer>


Fragen zur Fragen zur Implementation?Implementation?Zur Benutzung?Zur Benutzung?

Sourcecode zeigen?Generische Typen genauer

erklären?


Lexical TreeLexical TreeExperiment Experiment

BundestagsprotokolleBundestagsprotokolle



ExperimentExperiment• L-Tree Aufbau mit

Bundestagsprotokollen (BTP) der Wahlperioden 13 - 16

• Anzahl Dokumente: 50.363• Anzahl Wörter im L-Tree: ca.

470.000• Längstes Wort: 67

Buchstaben



Wörter Anzahl (BTP)Wörter Anzahl (BTP)


BTP - Das QuizBTP - Das QuizRunde 1Runde 1

• 37-Zeichen Frage:Was wird im Bundestag durchgeführt, wenn sich mal wieder keine Einigung findet?

Konsensfindungserleichterungs-maßnahme



• 51-Zeichen Frage:Wie lautet das komplizierteste Adjektiv?Tipp: Es geht um Geld…

arbeitgeberbeitragsfondssteuer-ergänzungsfinanzierte


Lexical TreeLexical TreeSpeicherplatzproblematSpeicherplatzproblemat

ikik


Heap-Size der JVM Heap-Size der JVM erhöhenerhöhen

-Xmx1600m -Xms1600m

Xmx = maximale Größe, Xms = Startgröße, 1600m = 1600 MB



Speicherplatz (BTP)Speicherplatz (BTP)• Zur Verfügung: 1600 MB Arbeitsspeicher• Testlauf 1:

– L-Tree, wie vorgestellt– Speicher nach 25.000 Dokumenten voll

(Abbruch)• Testlauf 2: (Dauer 15min)

– L-Tree ohne Dokument-Listen– L-Tree Dateigröße: 150 MB

Dokumentenliste muss besser organisiert

werden



SpeicherplatzredukltionSpeicherplatzredukltionWas tun?• Unterscheidung zwischen Groß- und

Kleinschreibung aufheben Informationsverlust

• Stemming: Wörter auf ihren Wortstamm reduzieren Informationsverlust

• Wörter ausschließen– Wörter die in allen Dokumenten vorkommen– Stopwörter: Wörter, die keine Information

tragenz.B. der/die/das/dieser/dieses/

• Dokumentenlisten auslagern



Wörter reduzierenWörter reduzierenWort Abs. H. Rel. H. Wort Abs. H. Rel. H.Bundestag 50278 99,8% zu 48687 96,7%Deutscher 50278 99,8% ist 48467 96,2%den 49551 98,4% für 48082 95,5%der 49389 98,1% das 47972 95,3%von 49384 98,1% des 47615 94,5%und 49188 97,7% auf 47516 94,3%die 49169 97,6% nicht 47357 94,0%in 48760 96,8% Summe 731693 2,8%

Häufigkeit des Vorkommens eines Wortesin den 50.363 BTP Dokumenten



Wörter reduzierenWörter reduzieren• Maßnahmen

– offensichliche Stopwörter:der, die , das, dass, dieses, diese, einer, vor

– Analyse Worthäufigkeit:Deutscher, Bundestag, haben, werden, sind, Sie, deshalb, …

• Ergebnis:– insgesamt 250 Stopwörter– Ersparnis von ca. 22% der Dokumentenverweise– L-Tree Datei-Größe: 350 MB!– Erstellungsdauer: 40min, Ladedauer: 10min Geht das mit Auslagerung noch besser?



• 56-Zeichen Frage:Ich würde gerne 100km Autobahn bauen! Wie finde ich heraus, ob sich die Bedingungen dazu zu meinem Nachteil ändern können?

Fernstraßenbauprivatfinanzierungs-gesetzesänderungsgesetz


Inverted Files zur Inverted Files zur AuslagerungAuslagerung


Dokumentenlisten Dokumentenlisten auslagernauslagern

• Wir haben gesehen:– Wortmenge nach oben beschränkt– Dokumentenlisten bestimmen Platzbedarf

• Idee:– Lagere Teile oder alle Dokumentenlisten in Dateien

aus.– Erweiterung: Halte nur Listen für häufig abgefragte

Wörter im Speicher (statische Auswahl)– Erweiterung 2: Lernender Algorithmus, der mit

jeder Abfrage die Auswahl der gecachten Listen anpasst


Inverted IndexInverted Index

• Situation: Suche nach einer Menge von Wörtern

• Forward Index– Zu jedem Dokument wird die Menge der

enthaltenen Wörter verwaltet– alle Dokumente müssen durchsucht werden

• Inverted Index (oder Inverted Files)– Zu jedem Wort wird die Menge der

Dokuemente, in denen es vorkommt, gespeichert

– Wörter sind sortiert (schnelle Suche)


Inverted Files BeispielInverted Files Beispiel

Inverted File :der {1} Grottenolme {1, 3}Grotte {2}in {2}lachend {2}laut {2}Lurche {1, 2}nicht {3}sind {1}singen {2, 3}

d1: Grottenolme sind Lurche.d2: Lurche singen laut lachend

in der Grotte.d3: Grottenolme singen nicht.


d1: <Häufigkeit von b1…bn in d1>

…

dm: <Häufigkeit von b1…bn in dm>

Inverted Files im L-TreeInverted Files im L-TreeVariante 1Variante 1

• Speichere für jedes Wort eine Textdatei mit seinen Dokumenten und Häufigkeiten

{d € D | b1…bn € d}

b1

…

bn

Nachteil: Für jedes Wort eine Datei



• Seien if1, …, ifp Inverted Files• Jedes ifj verwaltet eine disjunkte

Teilmenge aller Wörter und deren Dokumente

• Hashfunktion– H: Wort → j, j = 1, …, p– ordnet einem bei der Erstellung des L-Tree

jedem Wort ein Inverted File zu

d1: <Dokumente zu d1>d5: <Dokumente zu d5>

d99: <Dokumente zu d99>







• Vorteil:– wenige Dateien– Dateien können einzeln gecacht werden– Hashfunktion könnte Wörter nach

Relevanz ordnen, so dass alle häufig abgefragten Wörter in einem Inverted File im Cache liegen.

• Bis jetzt leider nicht beantwortet:– Wie viele Inverted Files sind optimal?– Wie lautet die Hashfunktion?


FazitFazit

• L-Tree dient als sehr kompakter Index für große Dokumentensammlungen

• Speicherreduktion durch Stopwörter und häufigste Wörter

• Weitere Verbesserung durch die Auslagerung der Dokumentenlisten in Inverted Files



• 59-Zeichen Frage:Wer hilft mir eigentlich, wenn ich meine Krankenkasse in die Luft sprengen will?

Bundeskrankenversicherungs-explosionsbeschleunigungsmi

nister


LiteraturverzeichnisLiteraturverzeichnis

• „Datenstrukturen und Datenbanken“, Schäfer 1989, Vieweg

• Wikipedia - „Inverted Index“http://en.wikipedia.org/wiki/Inverted_index

• „Indexierung für Suchmaschinen“, Vortrag von Emel Günal im Rahmen der PG520 am Lehrstuhl für Informatik 8, Universität Dortmund



• 67-Zeichen Frage:Wo wird geregelt, wie ich meinen Nachbarn für den 40-Tonner in meinem Garten verantwortlich machen kann?

Grundstücksverkehrsgenehmigungs-

zuständigkeitsübertragungsverordnung


Vielen Dank für die Vielen Dank für die Aufmerksamkeit!Aufmerksamkeit!

Documents

10.01.2008PG 520 - L-Tree - Martin Böhmer1 Der Lexical Tree und seine Freunde Ein Crashkurs zur Erstellung eines großen Wort-Indexes