Eine fehlertolerante Suchsoftware für Onlineshops

Eine fehlertolerante Suchsoftwarefür Onlineshops

DIPLOMARBEIT

Zur Erlangung des akademischen Gradeseines Magisters der Sozial- und Wirtschaftswissenschaften

im Diplomstudium Wirtschaftsinformatik

eingereicht an der Johannes Kepler Universität LinzInstitut für Wirtschaftsinformatik

Software Engineering

Betreuung:a. Univ.-Prof. Mag. Dr. Reinhold Plösch

Verfasst von: Andreas Wabro

St. Georgen/Gusen, im September 2005

ii

Ich erkläre hiermit, dass ich die vorliegende Diplomarbeit mit dem Titel „Eine fehlertolerante

Suchsoftware für Onlineshops“ eigenständig verfasst, andere als die angegebenen Quellen

und Hilfsmittel nicht benutzt und die aus anderen Quellen entnommenen Stellen als solche

gekennzeichnet habe.

St. Georgen/Gusen, 9. September 2005

iii

iv

Kurzfassung

Erlöse, die aus dem Verkauf von Produkten in Online-Shops erzielt werden, tragen

mittlerweile bei vielen Firmen wesentlich zum Gesamtumsatz bei. Um die Produktivität und

den Umsatz eines Online-Shops zu steigern ist unter anderem der Einsatz einer

leistungsfähigen Suchsoftware sinnvoll, da ein Großteil der Benutzer und potentiellen Käufer

die Suchfunktion der Webseite benutzen, um Produkte und Dienstleistungen zu finden. Findet

ein Benutzer aufgrund eines Tipp- oder Rechtschreibfehlers keine Produkte, so verlässt er

unter Umständen den Shop und kauft das gesuchte Produkt bei einem Konkurrenten. Zudem

kommt es oft vor, dass ein gesuchtes Produkt unter einem anderen Namen in der Datenbank

gespeichert ist und somit auch bei einem richtig geschriebenen Suchbegriff keine Produkte

gefunden werden.

Das Ziel dieser Diplomarbeit war es, eine fehlertolerante Suchsoftware zu entwickeln, welche

Tipp- und Rechtschreibfehler toleriert. Zudem wurde ein Thesaurus integriert um eine Suche

nach Synonymen und Unterbegriffen zu ermöglichen.

Der theoretische Teil dieser Arbeit zeigt Vor- und Nachteile verschiedener Suchalgorithmen

und Indizes, sowie deren Einsatzmöglichkeiten für eine fehlertolerante Suchsoftware im

Kontext von Online-Shops.

v

Abstract

Many companies generate a significant amount of their total revenue by sales in online shops.

In order to increase the productivity and the revenue of such shops, a powerful search engine

should be integrated, as a lot of users and potential customer use the search function in order

to find potential products and services. With common search functions, a user probably won’t

find a product, in case of misspelled search terms. As a result he may leave the shop and buy

the product at a competitor. Another common reason why search queries fail is that products

are stored under a different name in the companies’ database.

The aim of this diploma thesis was to implement a fault tolerant search engine, which handles

search term that contains spelling mistakes. Additionally a thesaurus was implemented so that

the engine automatically searches for terms that are related with the search term.

The theoretical part of this work demonstrates the advantages and disadvantages of several

search algorithms and indices as well as their usage in a fault tolerant search engine within the

context of online shops.

vi

Inhaltsverzeichnis

1 Einleitung............................................................................................................................1

1.1 Motivation...................................................................................................................1

1.2 Fehlertolerante Suchsoftware......................................................................................2

1.3 Prototyp.......................................................................................................................4

1.4 Gliederung der Diplomarbeit......................................................................................5

2 Fehlertolerante Suchalgorithmen....................................................................................7

2.1 Überblick.....................................................................................................................7

2.2 Phonetische Algorithmen............................................................................................8

2.3 Berechnen der Ähnlichkeit zweier Zeichenketten....................................................11

2.4 Fazit...........................................................................................................................23

3 Indexierungsmethoden...................................................................................................25

3.1 Invertierter Index......................................................................................................26

3.2 Trie............................................................................................................................27

3.3 Patricia-Trie..............................................................................................................30

3.4 Suffix-Trie.................................................................................................................31

3.5 Suffix-Tree................................................................................................................33

3.6 Suffix-Array/PAT-Array...........................................................................................34

3.7 Fazit...........................................................................................................................35

4 Anforderungen an eine fehlertolerante Suchsoftware.................................................36

4.1 Begriffsdefinition Anforderung................................................................................37

4.2 Szenarien...................................................................................................................37

4.3 Funktionale Anforderungen......................................................................................39

4.4 Nichtfunktionale Anforderungen..............................................................................44

5 Lucene..............................................................................................................................46

5.1 Allgemeiner Überblick..............................................................................................47

5.2 Indexierung...............................................................................................................48

5.3 Suche.........................................................................................................................51

5.4 Erforderliche Anpassungen/Erweiterungen..............................................................52

vii

6 Implementierung.............................................................................................................54

6.1 Überblick...................................................................................................................54

6.2 Verwendete Bibliotheken und Frameworks..............................................................55

6.3 Architektureller Überblick........................................................................................62

6.4 Implementierte Komponenten und Funktionen des Prototyps..................................66

6.5 Beispielapplikation...................................................................................................72

6.6 Last- und Performancetests.......................................................................................77

7 Zusammenfassung und Ausblick...................................................................................81

Danksagung.............................................................................................................................83

Abbildungsverzeichnis............................................................................................................84

Literaturverzeichnis...............................................................................................................85

viii

1 Einleitung

Inhalt

Motivation

Komponenten einer fehlertoleranten Suchsoftware

Prototyp

Gliederung der Diplomarbeit

1.1 Motivation

Ein Großteil der bestehenden Onlineshops stellt dem Benutzer eine Suchfunktion zur

Verfügung. Ohne Suchfunktion muss ein Benutzer durch verschiedene Produktkategorien

navigieren und Auflistungen durchsuchen bis er letztlich das gesuchte Produkt findet oder

seine Suche ergebnislos abbricht. Da dieser Vorgang für den Benutzer relativ mühsam ist und

er oft nicht weiß in welcher Kategorie sich das gesuchte Produkt befindet, ist die Nutzung der

Suchfunktion sehr beliebt. Die Ergebnisse einer Suchanfrage sind jedoch häufig

unbefriedigend, da viele Suchfunktionen nur buchstabengetreu vergleichen. Tipp- und

Rechtschreibfehler werden nicht toleriert und führen daher zu keinen befriedigenden

Ergebnissen. Zudem, können Produkte, die unter einem anderem als den gesuchten Namen

gespeichert sind, nicht gefunden werden. Führt eine Suche zu einer leeren Ergebnisliste, so

erweckt dies beim Benutzer den Eindruck, dass sich das Produkt nicht im Sortiment des

Unternehmens befindet. Dies führt unter Umständen dazu, dass er den Online-Shop verlässt

und das Produkt bei einem Konkurrenten kauft.

Der Einsatz einer leistungsfähigen Suchsoftware ist daher dringend notwendig, da diese nicht

nur die Produktivität und Benutzbarkeit sondern auch den Umsatz eines Online-Shops

steigert.

1

Das Ziel dieser Diplomarbeit war die Realisierung einer fehlertoleranten Suchsoftware,

welche Tipp- und Rechtschreibfehler toleriert und definierte Synonyme und Unterbegriffe

eines Suchbegriffes findet.

1.2 Fehlertolerante Suchsoftware

Eine Suchsoftware setzt sich üblicherweise aus zwei Hauptkomponenten zusammen. Zum

einen sind dies, die von der Software verwendeten Suchalgorithmen und zum anderen der zu

durchsuchende Index. Ein Index wird zwar nicht unbedingt benötigt, da eine Suche auch

direkt auf Datenbanken oder sonstigen Datenträgern ausgeführt werden kann, für den Einsatz

in Online-Shops ist es jedoch sinnvoll einen solchen Index zu verwenden um Suchabfragen zu

beschleunigen und somit die Wartezeit für Benutzer zu verkürzen. Weiters sollte eine

Suchsoftware für Online-Shops über einen Thesaurus sowie über eine Komponente, zur

Protokollierung von Suchabfragen verfügen. Mittels eines Thesaurus kann die Software

gleichzeitig nach Synonymen und Unterbegriffen eines Suchbegriffes suchen. Dadurch muss

der Benutzer nicht genau wissen unter welchem Begriff ein bestimmtes Produkt gespeichert

ist. Eine Suche nach Fernseher kann somit auch zu Suchergebnissen mit der Bezeichnung

Fernsehgerät oder TV führen, falls diese Synonyme im Thesaurus gespeichert sind. Die

Protokollierung von Suchabfragen in Online-Shops ist wichtig, damit der Betreiber des

Systems weiß welche Produkte gefragt sind und ob diese auch gefunden werden. Falls sie im

Sortiment des Unternehmens vorhanden sind und nicht gefunden werden, so muss der

Thesaurus um entsprechende Einträge erweitert werden. Sind sie jedoch nicht vorhanden so

kann sich der Unternehmer entscheiden stark nachgefragte Produkte ins Sortiment

aufzunehmen.

Fehlertolerante Suchalgorithmen können in die Kategorien phonetische Algorithmen und

Algorithmen, welche die Ähnlichkeit zweier Zeichenketten berechnen, eingeteilt werden.

Phonetische Algorithmen versuchen in einem Text jene Wörter zu finden, die gleich oder

ähnlich wie der gesuchte Begriff ausgesprochen werden. Sie produzieren oft unbrauchbare

Ergebnisse, da sie auch Treffer beinhalten, die nicht wie der gesuchte Begriff ausgesprochen

werden. Aufgrund ihrer Unzuverlässigkeit sollten phonetische Algorithmen nicht oder nur in

Kombination mit einem Algorithmus der zweiten Kategorie verwendet werden. Für die

Berechnung der Ähnlichkeit zweier Zeichenketten, gibt es eine große Anzahl an Algorithmen.

2

Zu den schnellsten Vertretern gehören Bitparallele- und Filterungsalgorithmen. Bitparallele

Algorithmen nutzen den Umstand aus, dass CPUs heutiger Computer Rechenoperationen

parallel mit 32 oder 64 Bit durchführen. Filterungsalgorithmen versuchen hingegen möglichst

große Teile eines Textes zu verwerfen und nur potentielle Übereinstimmungen mittels eines

approximativen Algorithmus zu prüfen. Die beiden erwähnten Algorithmen berechnen die

Ähnlichkeit durch die Anzahl der Operationen die nötig sind um eine Zeichenkette durch

Einfügen, Löschen, Ersetzen und Austauschen von Buchstabe in eine andere Zeichenkette zu

transformieren. Dies hat jedoch den Nachteil, dass sie Wortvariationen nicht erkennen

können. Ein Beispiel hierfür ist eine Suche nach Druckerkabel im Text Kabel für Drucker.

Für dieses Problem gibt es so genannte Q-Gramm oder N-Gramm Algorithmen. Sie versuchen

auch Wortvariationen zu erkennen indem sie den Suchbegriff sowie den zu durchsuchenden

Text in Teilzeichenketten der Länge q teilen. Anschließend vergleichen sie die Anzahl

gemeinsamer Teilzeichenketten. Weist der Text in einem bestimmten Bereich sehr viele

gleicher Teilzeichenketten auf so wird angenommen, dass es dort eine Übereinstimmung mit

dem Suchbegriff gibt. Der Nachteil dieser Art von Algorithmen ist, dass sie im Gegensatz zu

den beiden vorhin beschriebenen sehr langsam sind und durch das Erstellen der

Teilzeichenketten mehr Speicherplatz benötigen.

Ein Index ist wie bereits erwähnt eine Datenstruktur, welche darauf ausgerichtet ist, die

Verarbeitungsgeschwindigkeit von Suchabfragen zu erhöhen. Ein Index soll jedoch nur

verwendet werden, wenn die Anzahl der Suchabfragen, größer als die Anzahl der Änderungen

des Index ist, da nicht nur die Erstellung sondern auch die Aktualisierung eines Index ein

Vielfaches der Zeit einer Suchabfrage kostet [BaNa04].

Bei der Auswahl eines Index ist unter anderem das Kriterium Speicherplatzverbrauch von

Bedeutung, da ein speicherschonender Index, im Hauptspeicher gehalten werden kann und so

langsame Zugriffe auf externe Datenträger vermieden werden. So benötigt zum Beispiel der

Suffix-Array den 3-fachen Speicherplatz des ursprünglichen Textes, was im Gegensatz zu

Datenstrukturen die in Form eines Baumes aufgebaut sind, relativ wenig ist. Einen noch

geringeren Speicherplatzbedarf weist der Invertierte Index auf. Dieser wächst ab einer

bestimmten Größe nur noch sublinar zur Textgröße an. Approximatives Suchen in Suffix-

Arrays ist schneller als in einem Invertierten Index. Kann der Suffix-Array jedoch auf Grund

seines Speicherplatzverbrauches nicht im Hauptspeicher gehalten werden so ist er um ein

vielfaches langsamer als ein invertierter Index der im Hauptspeicher Platz findet. Ein weiterer

Nachteil des Suffix-Array ist sein komplizierter Aufbau. Dem hingegen lässt sich ein

3

Invertierter Index sehr einfach erstellen und aktualisieren. Auch ist es möglich einen

Invertierten Index auf mehrere Computer aufzuteilen, womit sich die Geschwindigkeit von

Suchabfragen weiter steigern lässt und sich das Problem des begrenzten Hauptspeicherplatzes

verringert.

Eine fehlertolerante Suchsoftware verfügt daher idealerweise über einen oder mehrere

schnelle Suchalgorithmen, einem speicherschonenden Index sowie über einen Thesaurus und

einer Protokollierungskomponente.

1.3 Prototyp

Für die Realisierung des Prototyps wurden zuerst verschiedene Suchalgorithmen und Indizes

verglichen und diese auf einen möglichen Einsatz in der Suchsoftware geprüft. Anschließend

wurden zwei Anwendungsszenarien beschrieben und daraus funktionale und nicht funktionale

Anforderungen abgeleitet.

Da die Implementierung der Software auf dem Suchframework Lucene aufbaut, war es

erforderlich sich zuerst einen Überblick über das Framework zu verschaffen und es auf nötige

Änderungen und Erweiterungen zu prüfen. Für die Auswahl des Frameworks Lucene waren

die Eigenschaften, dass es auf Java basiert, einen invertierten Index verwendet und bereits

grundlegende Suchfunktionen bereitstellt, von entscheidender Bedeutung. Neben Lucene

kamen auch das Testframework JUnit, das Build-Werkzeug ANT, die Bibliothek Log4J und

Phonetix, der XML Parser Xerxces 2, sowie das Webapplikationsframework Struts und das

Lasttestwerkzeug JMeter zum Einsatz.

Der erstellte Prototyp stellt Funktionen für eine exakte, fehlertolerante und phonetische Suche

zur Verfügung. Zudem können Suchergebnisse sortiert und durch Angabe von

Wertebereichen eingeschränkt werden. Die Software speichert die Daten in Form eines

invertierten Index auf einen externen Datenträger und liest diesen beim Start der Software in

den Hauptspeicher ein. Suchabfragen erfolgen daher immer auf einen Index der sich im

Hauptspeicher befindet. Auch das Speichern und Suchen von heterogenen Datenstrukturen

wie Produktdaten und Webseiten ist möglich.

4

Anhand einer Beispielanwendung wurde der Einsatz des Prototyps gezeigt und dessen

Geschwindigkeit mittels Load- und Perfomancetests geprüft.

1.4 Gliederung der Diplomarbeit

Kapitel 2

Kapitel 2 gibt einen Überblick über verschiedene Ansätze für fehlertolerantes Suchen. Es

werden fehlertolerante Algorithmen beschrieben und deren Vor- und Nachteile im Hinblick

auf den Einsatz in einer fehlertoleranten Suchsoftware herausgearbeitet.

Kapitel 3

In diesem Kapitel werden diverse Indizes beschrieben, verglichen und deren Eignung für

einen Einsatz in der zu implementierenden Suchsoftware, geprüft. Ein besonderes Augenmerk

wird dabei auf den benötigten Speicherplatz der einzelnen Indizes gelegt.

Kapitel 4

In Kapitel 4 werden zwei Anwendungsszenarien, für eine fehlertolerante Suche in Online-

Shops dargestellt. Aus diesen beiden Szenarien wurden anschließend funktionale und nicht

funktionale Anforderungen abgeleitet. Auf Grundlage der in Kapitel 4 definierten

Anforderungen wurde der Prototyp entwickelt und der fertig gestellte Prototyp auf funktionale

Vollständigkeit geprüft.

Kapitel 5

Dieses Kapitel beschreibt das Suchframework Lucene. Zudem werden notwendige

Modifikationen und Erweiterungen des Frameworks erhoben, um einen funktional

vollständigen Prototyp zu erhalten.

Kapitel 6

Kapitel 6 befasst sich mit der Implementierung des Prototyps. Es wird ein kurzer Überblick

über die verwendeten Werkzeuge, Bibliotheken und Frameworks gegeben und die wichtigsten

Komponenten des erstellten Systems erläutert. Zudem wird in diesem Kapitel der Einsatz des

Prototyps, anhand einer Beispielapplikation mit realen Produktdaten, gezeigt.

5

Kapitel 7

In diesem Kapitel werden die wesentlichsten Punkte der Diplomarbeit zusammengefasst und

ein Ausblick auf weiterführende Arbeiten gegeben.

6

2 Fehlertolerante Suchalgorithmen

Inhalt

Überblick

Phonetische Algorithmen

Soundex

Phonix

Double Metaphone

Berechnen der Ähnlichkeit zweier Zeichenketten

Levenshtein Algorithmus

Automatensuche

Bit-Parallelismus

Filterungsalgorithmen

Q-Gramme/N-Gramme

Dieses Kapitel beschreibt verschiedene Ansätze für fehlertolerantes Suchen. Der Zweck

dieses Kapitel ist ein Grundwissen über die Funktionsweise fehlertoleranter Algorithmen zu

schaffen, sowie ihre Einsatzmöglichkeiten zu zeigen, um eine ausreichende

Entscheidungsgrundlage für die Planung und Implementierung des Prototyps zu erlangen.

2.1 Überblick

Fehlertolerante Suchalgorithmen werden grundsätzlich in zwei Kategorien eingeteilt. Der

ersten Kategorie werden phonetische Algorithmen zugeordnet, welche auf die Aussprache

von Wörtern Rücksicht nehmen. Algorithmen der zweiten Kategorie messen die Ähnlichkeit

zweier Zeichenketten, indem sie entweder eine so genannte Editierdistanz berechnen oder

7

indem sie die Anzahl an gleichen Teilzeichenketten, welche als Q-Gramme oder auch als N-

Gramme bezeichnet werden, ermitteln.

Der Zweck phonetischer Algorithmen ist in einem Text t jene Wörter zu finden, die ähnlich

wie der Suchbegriff s betont und ausgesprochen werden. Sinnvoll ist die Anwendung von

phonetischen Algorithmen, wenn der Benutzer nicht weiß wie der gesuchte Begriff

geschrieben wird. Sucht ein Benutzer zum Beispiel nach Playstation tippt jedoch Playsteschn

als Suchbegriff ein, so sollte ein phonetischer Algorithmus erkennen, dass beide Wörter

ähnlich betont und ausgesprochen werden.

Algorithmen welche die Editierdistanz zwischen zwei Zeichenketten ermitteln, berechnen die

Anzahl der nötigen Operationen, um eine Zeichenkette s1 in eine Zeichenkette s2 zu

transformieren. Editieroperationen setzen sich aus dem Einfügen, Ersetzen, Löschen und

Austauschen von Buchstaben zusammen. Um zum Beispiel den Suchbegriff Kraswate in

Krawatte umzuwandeln sind zwei Editieroperationen nötig. Eine Operation, um den

Buchstaben s in s1 zu löschen und eine Operation, um den Buchstaben t in s1 einzufügen.

Q-Gramm oder N-Gramm basierende Algorithmen unterteilen ein Wort in Zeichenketten mit

der Länge q. Zum Beispiel würde der Begriff Waschmaschine mit der Länge q=2 in die Q-

Gramme WA, AS, SC, CH, HM, MA, AS, HI, IN, NE unterteilt werden. Die Ähnlichkeit zweier

Wörter wird durch die Anzahl an gleichen Q-Grammen bestimmt.

2.2 Phonetische Algorithmen

2.2.1 Soundex

Der erste phonetische Algorithmus mit der Bezeichnung Soundex [NARA00, Knut73] wurde

von Robert C. Russell und Margaret K. Odell entwickelt und 1918 patentiert. Der

Algorithmus erstellt zuerst aus jedem Wort einen vierstelligen Code und vergleicht

anschließend den Code des Suchbegriffs mit den Codes der Wörter im Text. Wird nun der

8

Suchbegriff und ein Wort im Text durch den gleichen Code dargestellt, so wird angenommen,

dass es zwischen den beiden Wörtern eine phonetische Übereinstimmung gibt.

Der Code des Wortes wird anhand einer kleinen Anzahl an Regeln erstellt. Für die erste Stelle

des Codes wird der erste Buchstabe des zu codierenden Wortes verwendet. Die Vokale A, E,

I, O und U sowie die Konsonanten Y, H und W werden für die Codierung nicht beachtet. Die

restlichen Buchstaben sind in Gruppen eingeteilt wobei jede Gruppe durch eine Ziffer

repräsentiert wird.

Ziffer Buchstabengruppe1 B, F, P, V2 C, G, J, K, Q, S, X, Z3 D, T4 L5 M, N6 R

Tabelle 1 zeigt die Buchstabengruppen des Soundexalgorithmus

Wie in Tabelle 2 dargestellt ergibt der Begriff Receiver den Code R216. Zeichenketten die

einen längeren Code ergeben, werden nur durch die ersten vier Stellen dargstellt und zu kurze

Codes werden durch Nullen ergänzt. Zum Beispiel wird das Wort Hose durch den Code H200

repräsentiert, da die Vokale o und e nicht beachtet werden. Stehen zwei oder mehrere

Buchstaben der gleichen Buchstabengruppe hintereinander so werden diese nur durch eine

Ziffer abgebildet.

R E C E I V E RR - 2 - - 1 - 6

Tabelle 2 stellt den Soundexcode für den Begriff Receiver dar

Beispiele für eine phonetische Übereinstimmung nach Soundex sind Mayer und Maier, die

jeweils den Code M600 ergeben oder die Begriffe Display und Disbley die auf den Code

D214 abgebildet werden.

Der Soundex Algorithmus ist jedoch nicht besonders zuverlässig, so würden zum Beispiel die

Begriffe Haus, Hose und Heike, welche keine phonetische Übereinstimmung aufweisen, den

Code H200 ergeben. Ein weiterer Nachteil des Algorithmus ist die Beschränkung des Codes

9

auf 4 Zeichen, dadurch wird bei längeren Wörtern mit gleichem Präfix derselbe Code

gebildet. Die Begriffe Druckerpatrone und Druckerkabel würden in Soundex somit durch den

Code D626 repräsentiert.

Mittlerweile gibt es zahlreiche weiterentwickelte Algorithmen. Eine wesentlich bessere

Alternative zu Soundex stellen die phonetischen Algorithmen Double Metaphone und Phonix

dar.

2.2.2 Phonix

Der weniger bekannte Phonix [Gadd88, Gadd90] Algorithmus versucht durch

Berücksichtigung von Ausspracheregeln, die Ergebnisse des Soundex Algorithmus zu

verbessern. Wie bei Soundex werden die Buchstaben in Buchstabengruppen eingeteilt und der

erste Buchstabe für die erste Stelle des Codes verwendet. Jedoch existieren für den ersten

Buchstaben die Ausnahmen das W und H ignoriert werden und die Buchstaben A, E, I, O, U,

Y durch V ersetzt werden. Im Wortinneren werden Vokale, doppelte Konsonanten und die

Buchstaben W, H und Y ignoriert. Im Gegensatz zu Soundex wird das Wort erst nach

Anwendung von 100 Ersetzungsregeln codiert. In diesen Ersetzungsregeln werden nicht nur

Buchstaben, sondern auch Buchstabenzusammensetzungen betrachtet und entsprechend der

Regel durch neue Buchstaben ersetzt. So wird zum Beispiel Ph in Phone durch F ersetzt und

anschließend in den Code F500 konvertiert. Auch der Phonix Algorithmus beschränkt den

Code auf nur 4 Zeichen, was zum bereits beschriebenen Problem bei langen Zeichenketten

führt.

2.2.3 Double Metaphone

Double Metaphone [Lawr00] wurde im Jahr 2000 von Lawrence Phillips vorgestellt und ist

eine Weiterentwicklung seines 1990 publizierten Metaphone [Lawr90] Algorithmus. Der

Metaphone Code hat eine variable Länge und ist nicht wie in Soundex auf vier Stellen

beschränkt. Eine Verbesserung der Suchergebnisse wird wie in Phonix durch die

Rücksichtnahme auf Ausspracheregeln der englischen Sprache erreicht. Da jedoch auch der

Metaphone Algorithmus noch einige Schwächen aufwies entwickelte Lawrence Phillips den

10

Double Metaphone Algorithmus, der zwei Codes für Wörter erstellt, welche eine Aussprache

auf mehre Arten zulassen. Weitere Änderungen betreffen den ersten Buchstaben, der immer

als A codiert wird, wenn dieser ein Vokal ist. Die Buchstaben Y und W werden ignoriert, und

die Buchstaben B und P werden nicht mehr separat codiert.

2.3 Berechnen der Ähnlichkeit zweier Zeichenketten

Im Folgenden werden grundlegende Algorithmen beschrieben, die die Ähnlichkeit zweier

Zeichenketten s1 und s2 berechnen, bzw. einen Suchbegriff s mit einer maximalen Anzahl an

k Fehlern in einem Text t finden. Algorithmen dieser Kategorie eignen sich um auf fehlerhafte

Eingaben, die durch Tippfehler entstehen, tolerant zu reagieren.

Zu Beginn wird der Algorithmus von Levenshtein [Leve65, Leve66] beschrieben, der auf

einfache Weise eine Editierdistanz zwischen zwei Zeichenketten berechnet. Anschließend

wird auf Algorithmen eingegangen, die eine bessere Laufzeitkomplexität und einen

geringeren Speicherbedarf aufweisen.

Tabelle 3 stellt eine Übersicht über die im Text verwendeten Symbole dar.

s gesuchte Zeichenkette

t zu durchsuchender Text

m = | s | Länge von s

n = | t | Länge von t

k Anzahl benötigter Editieroperationen um s in t zu transformieren

= k/m Fehlerquotient

w Anzahl der Bits mit denen eine CPU arbeitet, normalerweise 32 oder 64

ε leere Zeichenkette

∑ Alphabet, z.B. deutsches Alphabet, ASCII Zeichensatz oder Binäralphabet

Tabelle 3 Definition der im Text verwendeten Symbole

2.3.1 Levenshtein Algorithmus

11

Der Levenshtein Algorithmus wurde erstmals 1965 von dem russischen Wissenschaftler

Vladimir Levenshtein vorgestellt. Der Algorithmus berechnet die Ähnlichkeit von zwei

Zeichenketten, indem er die minimale Anzahl an benötigten Editieroperationen berechnet, um

eine Zeichenkette s1 in eine Zeichenkette s2 zu transformieren. Editieroperationen bestehen

aus dem Einfügen, Löschen und Ersetzen von Zeichen. Zum Beispiel kann das Wort Husen,

mit zwei Operationen, an das Wort Hose angepasst werden, indem das Zeichen u ersetzt und

das Zeichen n im Wort Husen gelöscht wird.

Im ersten Schritt des Algorithmus wird ein Array d erstellt, dass 0 bis m Reihen und 0 bis n

Spalten enthält. Die erste Reihe wird mit 0 bis n und die erste Spalte mit 0 bis m initialisiert.

H O S E0 1 2 3 4

H 1U 2S 3E 4N 5

Tabelle 4 Initialisierter Array für die Berechnung der Editierdistanz zwischen den Wörtern Hose und Husen.

Nach der Initialisierung werden die Reihen i = 1 bis m in den Spalten j = 1 bis n durchlaufen

und der Wert für die aktuelle Zelle durch folgende Vorschrift ermittelt. Der Wert der Zelle

d[i, j] berechnet sich aus dem Minimum der Zelle d[i-1, j]+1, der Zelle d[i, j-1]+1 und der Zelle

d[i-1, j-1]+Kosten. Die Kosten betragen 0, wenn s[i] gleich t[j] ist, ansonsten betragen die

Kosten 1. Der Wert in der Zelle d[n, m] drückt die Editierdistanz zwischen den beiden

Wörtern aus.

Berechnung der 1. Spalte Berechnung der 2. Spalte

12

Berechnung der 3. Spalte Berechnung der 4. Spalte

Tabelle 5 zeigt die Berechnung der Editierdistanz mittels Levenshtein – Algorithmus. Der fett gedruckte Wert in der letzten Zeile der 4. Spalte drückt die Distanz zwischen den beiden Wörtern aus.

Wie in Tabelle 5 gezeigt wurde kann das Wort Husen durch zwei Operationen an das Wort

Hose angepasst werden, da der Wert in d[n,m] = d[5,4] zwei beträgt.

Für den Austausch zweier angrenzender Buchstaben benötigt der Levenshtein Algorithmus

zwei Operationsschritte. Die Wörter Hsoe und Hose haben daher eine Levenshtein Distanz

von 2, da zwei Ersetzungen vorgenommen werden müssen. Damit der Algorithmus den

Austausch zweier angrenzender Buchstaben als eine Editieroperation zählt, ist es nötig eine

weitere Regel hinzuzufügen. Die Zelle d[i, j] kann auch durch d[i-2, j-2]+1 berechnet werden

wenn s[i-1] = t[j] und s[i] = t[j-1] ist. [LoWa75]

Mit dem gezeigten Algorithmus ist es nicht möglich eine approximative Suche von

Teilzeichenketten durchzuführen. Eine Suche nach Hosn im Text Jeanshose würde zu keinem

erfolgreichen Suchergebnis führen, da die Anzahl der Editieroperation zu groß ist. Dieses

Problem lässt sich jedoch lösen, in dem der Algorithmus etwas angepasst wird. Der

Unterschied zum vorhin beschriebenen Verfahren besteht darin, dass im modifizierten

Algorithmus jede Position in t der potentielle Anfang eines Treffers ist. Somit ist es nötig d[0,

j] für j ε 0..n mit 0 zu initialisieren.

J E A N S H O S E0 0 0 0 0 0 0 0 0

H 1 1 1 1 1 0 1 1 1O 2 2 2 2 2 1 0 1 2S 3 3 3 3 3 2 1 0 1N 4 4 4 4 4 3 2 1 1

13

Tabelle 6 Der dynamische Programmieralgorithmus für die Suche nach Hosn im Text Jeanshose. Fett markierte Einträge zeigen einen Treffer mit einem Fehler an.

Die Laufzeitkomplexität des ursprünglichen Levenshtein Algorithmus beträgt O(mn) und der

Speicherbedarf beträgt O(m). Seit der Veröffentlichung des Levenshtein Algorithmus gab es

jedoch zahlreiche Verbesserungen hinsichtlich Laufzeit und Speicherbedarf, wie zum Beispiel

bit-parallele Algorithmen oder Filterungsalgorithmen.

2.3.2 Automatensuche

Da bit-parallele Algorithmen die Funktionsweise von Automaten simulieren, wird im

Folgenden ein Überblick über das Konzept von Automaten gegeben. Auf eine detaillierte

Beschreibung der Algorithmen wurde jedoch verzichtet, da die nachfolgend beschriebenen

bit-parallelen Algorithmen, dieselben Eigenschaften wie Automaten haben, jedoch eine

geringere Laufzeitkomplexität aufweisen.

Die approximative Suche mittels finiter/endlicher Automaten wurde erstmals 1985 von Esko

Ukkonen [Ukko85] vorgestellt.

Finite Automaten beschreiben ein mathematisches System mit diskreten Ein- und Ausgaben.

Das modellierte System verfügt dabei über eine begrenzte Anzahl an Zuständen. Der aktive

Zustand zu einem bestimmten Zeitpunkt, fasst Informationen über bereits verarbeitete

Eingaben zusammen. Ein gutes Beispiel für ein finites System ist der Kontrollmechanismus

eines Aufzuges. Der Mechanismus merkt sich keine Anfragen die bereits ausgeführt wurden,

er weiß jedoch in welchem Stock sich der Aufzug befindet, in welche Richtung er sich bewegt

(rauf oder runter) und welche Anfragen noch auszuführen sind. [HoUl79]

Es gibt zwei unterschiedliche Typen von finiten Automaten, deterministische und

nichtdeterministische. Deterministische finite Automaten (DFA) lassen jeweils nur einen

Zustandsübergang zu, bei nichtdeterministischen finiten Automaten (NFA) sind hingegen

mehrere Zustandsübergänge möglich. Ein Zustandsübergang ist ein Wechsel von einem

Zustand q1 in einen anderen Zustand q2.

14

Abbildung 1 Das Diagramm auf der linken Seite stellt einen deterministischen finiten Automaten dar, das rechte Diagramm zeigt einen nichtdeterministischen finiten Automaten. Beide Diagramme haben q3 als Endzustand

definiert. Wenn ein zu durchsuchender Text t als Eingabe dient und der Buchstabe b eingelesen wird dann befindet sich der DFA im Zustand q2, der NFA hat jedoch nach Einlesen von b zwei aktive Zustände q0 und q2

Der von Ukkonen beschriebene Automat ist in deterministischer Form. Eine

nichtdeterministische Lösung für die Berechnung der Editierdistanz stellte Byeza-Yeates

[Byez91] 1991 vor.

Abbildung 2 NFA für den Suchbegriff Pulower mit maximal zwei Fehlern. Die gestreiften Zustände sind aktiv nachdem die Buchstaben P und U eingelesen wurden.

Abbildung 2 zeigt den Suchbegriff Pulower in Form eines NFA, welcher jene Zeichenketten

in t findet, die durch maximal zwei Editieroperationen an s angepasst werden können. Die

erste Reihe wird für eine Suche ohne Fehler benötigt. Die zweite Reihe dient der Suche nach

Zeichenketten mit einem Fehler und die dritte Reihe für die Suche nach Zeichenketten mit

zwei Fehlern. Horizontale Zustandsübergänge bedeuten, dass das eingelesene Zeichen mit

dem aktuellen Zeichen im Suchbegriff übereinstimmt. Diagonale und vertikale

Zustandsübergänge stellen eine Editieroperation dar. Muss ein Buchstabe des Suchbegriffs

durch ein anderes Zeichen ersetzt werden, so wird dies durch einen diagonalen

15

Zustandübergang mit dem Zeichen ∑ ausgedrückt. ∑ steht dabei für einen beliebigen

Buchstaben des verwendeten Alphabetes. Eine Löschoperation wird durch das Zeichen ε

gekennzeichnet, welches für eine leere Zeichenkette steht. Ein vertikaler Zustandsübergang

wiederum steht für eine Einfügeoperation im Suchbegriff. Auch dieser Zustandsübergang ist

mit ∑ beschriftet. Eine Editieroperation wird daher immer mit einem Zustandsübergang in

eine darunter liegenden Reihe ausgedrückt. Abbildung 2 weist drei mögliche Endzustände

auf. Ist einer der drei Endzustände aktiv so wurde ein Treffer gefunden. Ein aktiver

Endzustand der ersten Reihe bedeutet, dass ein Treffer ohne Fehler gefunden wurde. Ein

aktiver Endzustand der zweiten Reihe bedeutet, dass eine Übereinstimmung mit genau einem

Fehler gefunden wurde usw.

Der von Ukkonen vorgestellte Algorithmus benötigt einen Speicherplatz von O(min(3m,

m(2mσ)k)). Der Algorithmus ist daher nur für sehr kurze Suchbegriffe und einer niedrigen

Anzahl an maximal erlaubten Fehlern praktikabel.

Obwohl einige Verbesserungen und Weiterentwicklungen des ursprünglichen Algorithmus

existieren, ist die Simulation eines NFA mittels Bit-Parallelismus ein besserer Lösungsansatz,

da diese eine geringere Laufzeitkomplexität aufweisen.

2.3.3 Bit-Parallelismus

Die Grundidee dieser Art von Algorithmen, ist einen nichtdeterministischen Automaten oder

Algorithmus der dynamischen Programmierung, zu parallelisieren. Bit-Parallele Algorithmen

nutzen dabei die parallele Verarbeitung des Computers aus. Moderne Computer führen

Rechenoperationen mit 32 oder 64 Bit aus. Die Anzahl der Operationen, die ein Algorithmus

durchführt, kann durch die parallele Verarbeitung des Computers bis zu einem maximalen

Faktor w reduziert werden, wobei w die Anzahl der Bits ausdrückt. [Nava01]

Der Shift-Or [BaYa92] Algorithmus ist für schnelles exaktes Suchen von Zeichenketten

geeignet. Mit diesem Algorithmus ist es daher nur möglich Zeichenketten mit null Fehlern zu

finden. Da er jedoch die Basis für nachfolgende approximative Suchalgorithmen bildet, wird

er im Folgenden vorgestellt.

16

Der Shit-Or Algorithmus simuliert einen NFA indem er dessen Zustandsübergänge

parallelisiert.

Abbildung 3 Nichtdeterministischer Automat der nach Disc ohne Fehler sucht.

Zum besseren Verständnis wird der Shift-And Algorithmus beschrieben. Diesen haben Baeza-

Yates und Gonnet in den Shift-Or Algorithmus konvertiert, da das Auffüllen mit 1 bei

Schiebeoperationen in der Programmiersprache C nicht möglich ist.

Der Algorithmus erstellt einen Bitvektor R mit der Länge m, in welchem der aktuelle

Suchfortschritt gespeichert wird. Auch für jedes Zeichen c des Alphabetes ∑wird ein Vektor

angelegt. Der Vektor speichert die Positionen von c im Suchbegriff. Der Bitvektor VD für den

Suchbegriff Disc hat somit die Bitfolge 1000 und Vektor VI die Bitfolge 0100 usw.

Die Bits des Vektors R0 werden mit 0 initialisiert. Die hochgestellte 0 in R0 steht für die

Anzahl der Fehler. R0 dient daher der Suche nach Zeichenketten mit 0 Fehlern. R0’ wird durch

eine bitweise Verschiebung in R0 nach rechts, welche mit eins aufgefüllt wird, sowie einer

anschließenden UND Operation mit dem Vektor des eingelesenen Zeichens, ermittelt. Eine

Übereinstimmung des Musters in einem Text liegt dann vor, wenn R0’m gleich 1 ist.

VD VI VS VK Vsonst

1000 0100 0010 0001 0000

Tabelle 7 zeigt die Vektoren des Suchbegriffes Disk. Die Position des Buchstaben im Wort wird im Vektor durch eine 1 ausgedrückt. Jene Buchstaben die nicht im Suchbegriff vorkommen, werden durch den Vektor Vsonst

repräsentiert, welcher nur Nullen enthält.

Im Folgenden wird die Anwendung des Shift-And Algorithmus anhand des Suchbegriffs Disk

im Text Harddisk gezeigt.

1 Initialisierung des Zustandsvektors R 0000

2 Bitweise Verschiebung des Zustandsvektors nach rechts

1000

3 Bitweise UND Operation mit Vektor von 1000 Zustandsvektor

17

Zeichen H. Da der Suchbegriff das Zeichen H nicht enthält wird der Vektor Vsont für die UND Operation verwendet.

0000 Vektor sontige 0000 neuer Zustandsvektor

4 Bitweise Verschiebung nach rechts 1000

5 Bitweise UND Operation mit Vektor von Zeichen A (Vsont)

0000 (neuer Zustandsvektor)


7 Bitweise UND Operation mit Vektor von Zeichen R

0000


9 Bitweise UND Operation mit Vektor von Zeichen D

1000


11 Bitweise UND Operation mit Vektor von Zeichen D

1000


13 Bitweise UND Operation mit Vektor von Zeichen I

0100


15 Bitweise UND Operation mit Vektor von Zeichen S

0010


17 Bitweise UND Operation mit Vektor von Zeichen K

0001 (Treffer im Text Harddisk)

Tabelle 8 zeigt die exakte Suche von Disk im Text Harddisk, die durch eine bitweise Verschiebung in R0, sowie einer UND Operation mit dem jeweiligen Buchstabenvektor, realisiert wird. R0’17 zeigt einen Treffer mit null

Fehlern an, da dass letzte Bit auf eins gesetzt ist.

Im Unterschied zum Shift-And Algorithmus, speichert der Shift-Or Algorithmus die

Bitmuster der Zeichen in umgekehrter Reihenfolge und kennzeichnet die Positionen in denen

das Zeichen vorkommt mit einer 0, alle anderen mit einer 1 (VD = 11110). Vektor R wird mit

R0i = 1, 1 ≤ i ≤ m initialisiert, bitweise nach links verschoben und mit einer 0 aufgefüllt. Durch

einen anschließenden OR Vergleich von Vt und R wird R’ ermittelt. Eine Übereinstimmung

des Musters ist gegeben, wenn R0’1 = 0 ist.

In [WuMa92] zeigen Wu und Manber wie der Shift-Or Algorithmus zu einem approximativen

Suchalgorithmus erweitert werden kann. Die Idee liegt in der Simulation eines NFA, wie er

zum Beispiel in Abbildung 2 dargestellt wurde, mittels bitparalleler Operationen. Die

Erweiterung wird anhand des Basisalgorithmus Shift-And beschrieben, da dies verständlicher

ist.

18

Wu und Manber verwenden 0 bis k Arrays für R, welche jeweils für die Berechnung der

aktiven Zustände benötigt werden. Der Vektor R0 entspricht der ersten Reihe eines NFA. Er

dient daher zur exakten Suche von s in t. Der Vektor R1 wiederum simuliert die zweite Reihe

des Automaten usw. Zudem wird wie in Tabelle 6, ein Vektor für jedes Zeichen des

Suchbegriffes erstellt, um die Positionen der Buchstaben im Suchbegriff zu kennzeichnen. Ein

Treffer im Text mit maximal k Fehlern liegt dann vor, wenn der Zustandsvektor R0j [m] = 1

bzw. Rkj [m] = 1 ist. Für jede Editieroperation wird nun gezeigt wie der Übergang von R1

j-1 zu

R1j berechnet wird.

Angenommen der Algorithmus lässt nur Einfügeoperationen zu, so gibt es eine

Übereinstimmung der ersten i Zeichen des Musters mit den letzten i+1 bis j Zeichen des

Textes, falls Rij [i] = 1 ist.

Es gibt zwei Fälle in welchem der Suchbegriff bis zu Zeichen i mit maximal einem Fehler mit

den Zeichen tj+1 übereinstimmt. Der erste Fall trifft dann zu wenn die ersten i Zeichen bis tj

übereinstimmen. Wird nun ein Zeichen im Suchbegriff eingefügt so gibt es eine

Übereinstimmung mit einer Einfügeoperation bis zu tj+1. Im zweiten Fall gibt es eine

Übereinstimmung der ersten i-1 Zeichen bis tj. Dies bedeutet, dass bereits innerhalb des

Suchbegriffes ein Buchstabe eingefügt wurde und das Zeichen tj+1 gleich si sein muss, damit

eine Übereinstimmung gegeben ist.

Im ersten Fall genügt es den Wert von R0j einfach nach R1

j+1 zu kopieren. Für den zweiten Fall

ist eine Verschiebung des Bitmusters R1j nach rechts und eine AND Operation mit Vt+1 nötig.

Die Berechnungsvorschrift für Rdj+1 lautet daher Rd-1

j OR RShift[Rdj] AND Vt+1.

R01 R0

2 R03 R0

4 R05

H O U S E1 0 0 0 00 1 0 0 00 0 0 0 00 0 0 0 0

Tabelle 9 zeigt Vektor R0 bei einem Vergleich von Suchbegriff HOSE mit dem Text HOUSE.

R11 R1

2 R13 R1

4 R15

H O U S E1 1 0 0 00 1 1 0 00 0 0 1 00 0 0 0 1

Tabelle 10 zeigt Vektor R1 bei einem Vergleich von Suchbegriff HOSE mit dem Text HOUSE mit

maximal einer Einfügeoperation.

Tabelle 10 zeigt einen Treffer des Suchbegriffes Hose im Text House mit maximal einer

Einfügeoperation, da das letzte Bit in Vektor R15 auf eins gesetzt ist. Zur näheren Erläuterung

wird die Berechnung von Vektor R13 erklärt. Mit R1

3 wird der Zustandsvektor R nach dem

Einlesen des dritten Zeichens bezeichnet, der maximal eine Einfügeoperation beinhaltet. Für

19

die Berechnung von R1 wird der Vektor R0 sowie der Vektor Vt benötigt. Der Zustandsvektor

R0 wird wie bereits erwähnt, für exaktes Suchen verwendet, also zur Suche nach

Zeichenketten die keine Fehler beinhalten. Vt steht für den Vektor, der die Positionen des

eingelesenen Zeichens im Suchbegriff beinhaltet. Laut Berechnungsvorschrift ist R13 gleich

R02 OR RShift[R1

2] AND Vt=U. Der Vektor VU ist gleich 0000 da das Zeichen U nicht im

Suchbegriff vorkommt. Für R13 ergibt sich folgende Berechnung. R1

3 = 0100 OR RShift[1100]

AND 0000 = 0100 OR 0110 AND 0000 = 0100 OR 0000 = 0100.

Ist nur das Löschen eines Zeichens erlaubt so ist eine Übereinstimmung gegeben wenn die

ersten i-1 Zeichen des Suchbegriffes exakt bis zu tj+1 übereinstimmen. Dies entspricht einem

Löschen von Zeichen pi und einer Übereinstimmung der ersten i-1 Zeichen. Für den zweiten

Fall gilt, wenn die ersten i-1 Zeichen bis zu tj übereinstimmen, wurde bereits ein Zeichen im

Suchbegriff gelöscht und tj+1 muss gleich pi sein damit ein Treffer mit k=1 erzielt wird.

Für den ersten Fall ist eine Verschiebung des Wertes Rj+1 nach rechts nötig. Die

Berechnungsvorschrift für den zweiten Fall entspricht der Berechnungsvorschrift des zweiten

Falles für das Einfügen eines Buchstaben. Für Rdj+1 ergibt sich somit RShift(Rd-1

j+1) OR

RShift[Rdj] AND Vt+1.

R01 R0

2 R03 R0

4

H O S E1 0 0 00 1 0 00 0 0 00 0 0 00 0 0 0

Tabelle 11 zeigt Vektor R0 bei einem Vergleich von Suchbegriff HOUSE mit HOSE.

R11 R1

2 R13 R1

4

H O S E1 1 1 11 1 0 00 1 0 00 0 1 00 0 0 1

Tabelle 12 zeigt Vektor R1 bei einem Vergleich von Suchbegriff HOSE mit HOUSE mit maximal einer

Löschoperation.

Auch für die Ersetzung eines Zeichens gibt es zwei Möglichkeiten. Im ersten Fall gibt es eine

exakte Übereinstimmung der ersten i-1 Zeichen bis zu tj. Dieser Fall entspricht dem Ersetzen

eines Zeichens pi durch tj+1 sowie einer Übereinstimmung der ersten i-1 Zeichen. Im zweiten

Fall wurde bereits ein Zeichen im Suchbegriff ersetzt. Die ersten i-1 Zeichen stimmen mit

einer Ersetzung bis zu tj überein. tj+1 muss somit gleich pi sein damit eine Übereinstimmung

möglich ist. Der zweite Fall wird wie schon vorhin durch eine Verschiebung von R1j nach

rechts und einem AND mit Vj+1 abgedeckt. Für den ersten Fall ist eine Verschiebung von Rj

20

nötig. Dies entspricht einer Betrachtung von Rj[i-1]. Rdj+1 wird durch RShift(Rd-1

j) OR

RShift[Rdj] AND Vt+1 berechnet.

H O S E1 0 0 00 0 0 00 0 0 00 0 0 0

Tabelle 13 zeigt Vektor R0 bei einem Vergleich von Suchbegriff HUSE mit HOSE.

H O S E1 1 1 10 1 0 00 0 1 00 0 0 1

Tabelle 14 zeigt Vektor R1 bei einem Vergleich von Suchbegriff HUSE mit HOSE mit maximal einer

Ersetzungsoperation.

Für alle drei Editieroperationen gilt zusammenfassend: Rdj+1 = (RShift[Rd

j] AND Vt+1) OR Rd-1j

OR RShift(Rd-1j+1) OR RShift(Rd-1

j). Dies kann weiter vereinfacht werden zu Rdj+1 = (RShift[Rd

j]

AND Vt+1) OR Rd-1j OR RShift(Rd-1

j+1 OR Rd-1j).

2.3.4 Filterungsalgorithmen

Algorithmen, die auf dem Konzept der Filterung von Text basieren, verwerfen jene Teile

eines Textes, die nicht mit dem Teilmuster eines Suchbegriffes übereinstimmen. Der

Suchbegriff wird in k+1 Teile zerlegt, somit kann eine exakte Suche nach mindestens einem

Teilmuster durchgeführt werden. Textstellen die als potentielle Übereinstimmung erkannt

wurden, müssen zudem mit einem approximativen Suchalgorithmus verifiziert werden. Wird

z.B.: nach dem Begriff Taschenrechner mit maximal k=1 Fehler in einem Text gesucht, so

muss entweder der Teilbegriff Taschen oder der Teilbegriff rechner mit k=0 Fehlern im Text

vorkommen, da ein Fehler in beiden Teilbegriffen k=1 überschreiten würde.

Filterungsalgorithmen arbeiten sehr schnell bei einem kleinen Fehlerquotienten = k/m. Für

approximative Suchen mit einem hohen Fehlerquotienten sind Filterungsalgorithmen nicht

sinnvoll, da der Suchbegriff in viele kurze Teilbegriffe unterteilt wird und es daher eine große

Anzahl an potentiellen Treffern gibt, die nochmals mit einem approximativen

Suchalgorithmus überprüft werden müssen.

Ein relativ einfacher Filterungsalgorithmus wurde von Wu und Manber [WuMa92] 1992

vorgestellt. Sie teilen den Suchbegriff in k+1 Teile und verwenden anschließend einen

modifizierten Shift-Or Algorithmus mit welchem die Teilbegriffe parallel gesucht werden.

21

Die parallele Suche wird realisiert indem sie die Zeichen der einzelnen Teilbegriffe

hintereinander reihen und das Bitmuster, um k+1 Stellen, verschieben. Zum Beispiel wird der

Begriff Taschenrechner mit k=3 in die Teilbegriffe tasch, enrec, hner aufgeteilt. Durch die

Aneinanderreihung der einzelnen Buchstaben aus den Teilbegriffen wird der Suchbegriff

tehannsrecerhc für den modifizierten Shift-Or Algorithmus gebildet. Ein Treffer eines

Teilbegriffes liegt vor, wenn einer der letzten k Bits in R gleich 0 ist. Da für die parallele

Suche keine zusätzlichen Operationen durchgeführt werden müssen ist sie genauso schnell

wie die Suche nach nur einem Suchbegriff.

2.3.5 Q-Gramme/N-Gramme

Die unscharfe Suche mittels Q-Gramme oder auch N-Gramme genannt, ist eine einfache

Methode zwei Zeichenketten zu vergleichen. Die beiden Begriffe werden jeweils in

Teilzeichenketten der Länge q geteilt. Dabei entsteht eine Menge, welche sich aus Q-

Grammen zusammensetzt, die sowohl im Suchbegriff s als auch im Text t vorkommen sowie

Q-Gramme, welche nur in einer der beiden Zeichenketten vorkommen.

Q-Gramme Text Suchbegriff

Jacke Jake

ja X X

ac X

ck X

ke X X

ak X

Tabelle 15: Q-Grammvergleich der Wörter Jacke und Jake mit einer Länge q=2.

Die Ähnlichkeit zwischen s und t ist durch die gemeinsame Gramm-Anzahl(s, t) = |Gs ∩ Gt|

gegeben. Die Ähnlichkeit zwischen Jacke und Jake, mit q=2 ist somit 2, da beide Begriffe die

Gramme ja und ke beinhalten. Bei dieser Berechnung wird die Buchstabenreihenfolge nicht

beachtet, da jedoch die meisten Wörter keine Q-Gramme beinhalten, die wiederholt auftreten,

kann dies vernachlässigt werden. [ZoDa95]

Einfach nur die Anzahl gleicher Q-Gramme von s und t zu zählen reicht für die Suche nach

ähnlichen Zeichenketten nicht aus, da auf unterschiedliche Zeichenkettenlängen nicht

eingegangen wird. So hätte ein Vergleich von Hose mit sich selbst dieselbe Gramm-Anzahl

22

wie ein Vergleich von Hose mit Hosenanzug. Ukonnen [Ukko92a] schlägt daher die

Berechnung eines Gramm-Abstandes vor, der durch die Anzahl der ermittelten Q-Gramme

aus dem Suchbegriff sowie dem zu vergleichenden Wort im Text, abzüglich der gemeinsamen

Q-Gramme berechnet wird. Der Gramm-Abstand für q=2 zwischen Jacke und Jake beträgt

somit 3 und der Abstand von Hose und Hosenanzug beträgt 6. Wenn s und t einen

Editierabstand k nicht überschreiten sollen so müssen sie mindestens (max( |s|, |t| ) + q – 1) –

k * q gleiche Q-Gramme besitzen. [GrPa01] Für Jacke und Jake mit q=2 und maximal k=2

Fehlern ergibt dies eine Mindestanzahl an (max(5,4)+2-1)-2*2 = 2 Q-Grammen.

2.4 Fazit

Phonetische Algorithmen eignen sich nur beschränkt für den Einsatz in einer fehlertoleranten

Suchsoftware, da sie nicht besonders zuverlässig sind und dadurch die Qualität des

Suchergebnisses leidet. Sie sollten nur in Kombination mit einem weiteren Algorithmus

eingesetzt werden, welcher die Editierdistanz oder den Gram-Abstand zweier Zeichenketten

berechnet. Ein mögliches Anwendungsszenario wäre eine phonetische Suche immer dann

durchzuführen wenn der mit ihm eingesetzte Algorithmus, keinen Treffer im Text erzielen

konnte. Es gilt jedoch zu beachten, dass die hier beschriebenen phonetischen Algorithmen für

die englische Sprache entwickelt wurden und sie alle eine hohe Laufzeitkomplexität

aufweisen. Wird ein phonetischer Algorithmus eingesetzt so gilt es dem Double Methaphone

Algorithmus den Vorzug zu geben, da dieser durch eine variable Codelänge und einer großen

Anzahl von Ersetzungsregeln die wenigsten Schwächen aufweist.

Der ursprüngliche Levenshteinalgorithmus hat mit O(mn) eine relativ Hohe

Laufzeitkomplexität. Seine Vorteile liegen in der einfachen Implementierung und in der

Berechnung der erweiterten Editierdistanz, also den Austausch zweier angrenzender

Buchstaben als eine Operation zu zählen. Eine approximative Suche mit Shit-Or/Shift-And ist

mit O(k⌈m/w⌉ sehr schnell. Der Nachteil dieses Algorithmus ist jedoch, dass nur die einfache

Editierdistanz berechnet werden kann. Filterungsalgorithmen gehören zu den schnellsten

Algorithmen, solange der Fehlerquotient klein ist. Q-Gram/N-Gram basierende Algorithmen

können im Gegensatz zu den anderen Algorithmen auch Wortvariation finden, dazu benötigen

sie jedoch extra Speicherplatz. Für die Auswahl einer dieser Algorithmen gilt es daher die

Kriterien: Berechnung der erweiterten Editierdistanz, Geschwindigkeit, maximal mögliche

23

Größe des Fehlerquotienten, Suche von Wortvariationen und Speicherplatzverbrauch zu

gewichten.

24

3 Indexierungsmethoden

Inhalt

Invertierter Index

Trie

Patricia-Trie

Suffix-Trie

Suffix-Tree

Suffix-Array/PAT-Array

Fazit

In diesem Kapitel werden Indizes beschrieben, die häufig in der Praxis eingesetzt werden oder

eine Grundlage für weitere verbesserte Indexierungsmethoden darstellen. Jeder Index wird

hinsichtlich seiner Eignung für den Einsatz in einer fehlertoleranten Suchsoftware geprüft und

seine Einsatzbereiche, sowie seine Vor- und Nachteile erörtert.

Ein Index ist eine Datenstruktur, welche darauf ausgerichtet ist, die Verarbeitungs-

geschwindigkeit von Suchabfragen zu erhöhen. Es muss jedoch beachtet werden, dass Indizes

Speicherplatz sowie Zeit für ihre Erstellung benötigen. Die Verwendung eines Index ist nur

sinnvoll, wenn die Anzahl der Suchabfragen größer als die Anzahl der Änderungen des Index

ist, da nicht nur die Erstellung sondern auch die Aktualisierung eines Index ein Vielfaches der

Zeit einer Suchabfrage kostet [BaNa04].

Im Hinblick auf das Ziel dieser Diplomarbeit, eine fehlertolerante Suchsoftware für

Onlineshops zu implementieren, ist es zweckmäßig einen Index zu verwenden, da sich

Produktdaten zwar täglich ändern können, die Anzahl der Suchabfragen aber üblicherweise

weitaus größer ist als die Anzahl der Änderungen eines Index.

25

Für die Beispiele in diesem Kapitel gilt, dass zwischen Groß- und Kleinschreibung nicht

unterschieden wird. Für Indizes die durch eine Baumstruktur dargestellt werden, wurde

zusätzlich das Terminierungssymbol $ verwendet um ein Wortende zu kennzeichnen.

3.1 Invertierter Index

Ein invertierter Index speichert alle Wörter eines Textes und die Positionen ihres Auftretens

im Text in eine Liste.

1 5 10 18 22 29 38 42 47 55 59

Ein Text besteht aus vielen Wörtern. Ein Wort besteht aus Buchstaben.

Vokabular Positionen

aus 18, 55

besteht 10, 47

Buchstaben 59

ein 1, 38

Text 5

vielen 22

Wort 42

Wörtern 29

Abbildung 4 Ein Text und der dazugehörige invertierte Index

Die Suche in einem invertierten Index ist sehr einfach, da nur die Liste mit dem Vokabular

durchsucht werden muss und bei einem Treffer die dazugehörigen Positionen zurückgegeben

werden. Auch eine Suche mittels regulärer Ausdrücke sowie unscharfes Suchen ist möglich.

Dazu muss jedoch die ganze Liste durchlaufen und die einzelnen Wörter auf

Übereinstimmung geprüft werden.

Invertierte Indizes können in O(n) Zeit erstellt werden und benötigen ab einer bestimmten

Textgröße weniger Speicherplatz als der Text selbst. Baeza-Yates und Ribeiro-Neto [BaNe99]

zeigen, dass die Anzahl der Wörter in einem Text ab einer bestimmten Größe nur noch

sublinear mit der Textgröße steigt und die frei wählbare Größe ß in Heaps’ Law [Heap78]

26

üblicherweise zwischen 0,4 und 0,6 liegt. Heaps’ Law definiert die Vokabulargröße mit O(nß)

wobei ß ein positiver Wert kleiner 1 ist und n die Textlänge ausdrückt.

Abbildung 5 zeigt einen sublinearen Anstieg der Vokabulargröße zur Textgröße nach Heaps’ Law. Die X-Achse stellt die Textgröße dar, die Y-Achse zeigt die Vokabulargröße. Übernommen aus [Answ05]

Der invertierte Index eignet sich für schnelles exaktes Suchen und ist sehr einfach, zum

Beispiel durch einen Hashtable oder mittels einer sortierten Liste, zu implementieren. Als

Nachteil ist zu erwähnen, dass für eine approximative Suche sowie für eine Suche nach

Teilzeichenketten und regulären Ausdrücken das gesamte Vokabular durchlaufen werden

muss.

3.2 Trie

Die Trie Datenstruktur wurde erstmals 1959 von Renee de la Briandais [Brian59] publiziert.

1960 führte Edward Fredkin [Fred60] die Bezeichnung Trie ein, welche aus dem englischen

Begriff Retrieval abgeleitet wurde und wie try ausgesprochen wird.

Ein Trie ist ein Suchbaum in dem alle Teilzeichenketten, mit gleichem Präfix, an denselben

Knoten angehängt werden. Die internen Knoten des Baumes repräsentieren jeweils Zeichen

eines Präfixes und verlinken auf alle möglichen nachfolgenden Zeichen. In den Blättern des

Tries befinden sich die eigentlichen Informationen. Dies kann zum Beispiel die gesuchte

27

Zeichenkette, die Position der Zeichenkette im Text oder auch eine Liste von URLs sein,

welche den Suchbegriff beinhalten.

Abbildung 3 zeigt wie der Text Fischers Fritz fischt frische Fische in einem Trie gespeichert

wird.

Abbildung 6 Trie mit dem Text Fischers Fritz fischt frische Fische.

Sucht man im Trie von Abbildung 6 nach Fritz, so beginnt man bei der Baumwurzel, folgt der

F Kante, anschließend der R Kante, dann der I und der T Kante und zuletzt der Z Kante. Für

eine Suche nach Franz wird wieder von der Wurzel ausgegangen dann der F und R Kante

gefolgt, da es aber keine A Kante gibt, befindet sich der gesuchte Begriff nicht im Text.

28

Ein Trie kann auf verschiedene Arten implementiert werden. Im Folgenden wird anhand der

Wörter Fritz und fischt eine Implementierung mit Arrays, sowie durch eine verlinkte Liste,

gezeigt.

Abbildung 7 zeigt zwei Implementierungsmöglichkeiten eines Tries mit den Wörtern fischt und Fritz. Auf der linken Seite wird eine Implementierung durch Arrays dargestellt, auf der rechten Seite wird eine

Implementierung mittels einer verlinkte Liste gezeigt.

Eine Implementierung mittels Arrays ermöglicht einen schnellen Zugriff auf die einzelnen

Zeichen, hat jedoch den Nachteil, dass bei einem Index mit wenigen Wörtern viel Speicher

verschwendet wird, da die meisten Pointer auf Null zeigen. Die Laufzeit für die Suche einer

Zeichenkette beträgt im schlechtesten Fall O(m) wobei m für die Länge der längsten

Zeichenkette steht.

Tries werden unter anderem zur Rechtschreibprüfung oder als Indizes in Web-Suchmaschinen

verwendet. Auch für approximatives Suchen und für die Suche nach regulären Ausdrücken

können Tries verwendet werden. Ein regulärer Ausdruck beschreibt ein Muster mit Hilfe von

Symbolen. So kann zum Beispiel der reguläre Ausdruck (A+C)((B+C)D) für ABD, CBD,

ACD oder auch CCD stehen [Sedg92].

29

Der Trie Index ermöglicht eine sehr schnelle Suche. Eine Teilzeichenkettensuche sowie eine

approximative Suche sind jedoch nur in linearer Zeit zur Textgröße möglich, da hierfür der

gesamte Baum durchwandert werden muss.

3.3 Patricia-Trie

Der 1968 von Donald R. Morrison [Morr68] veröffentlichte Patricia-Trie, ist eine

Abwandlung eines Tries. Das Akronym PATRICIA steht für Practical Algorithm to Retrieve

Information Coded in Alphanumeric. Im Gegensatz zum normalen Trie werden im Patricia-

Trie die Daten in komprimierter Form gespeichert. Dies wird erreicht, indem nur dann ein

Kindknoten erzeugt wird wenn eine Verzweigung im Baum entsteht.

Abbildung 8 Patricia Trie mit dem Text Fischers Fritz fischt frische Fische.

Der Vorteil des Patricia-Trie ist, dass er wesentlich weniger Speicher als der Trie von de la

Briandais benötigt, und die Laufzeit für die Suche einer Zeichenkette mit O(m) gleich bleibt.

30

3.4 Suffix-Trie

Ein Suffix-Trie speichert sämtliche Suffixe eines Wortes in der Baumstruktur. Zum Beispiel

besteht das Wort Fernseher aus den Suffixen Fernseher, ernseher, rnseher, nseher, seher,

eher, her; er und r.

In den Blättern des Suffix-Tries werden die Anfangspositionen der einzelnen Suffixe

gespeichert.

Text F E R N S E H E RPosition 1 2 3 4 5 6 7 8 9

Tabelle 16 Anfangspositionen der Suffixe für den Text Fernseher

31

Abbildung 9 Suffix-Trie für das Wort Fernseher

Der Suffix-Trie eignet sich sehr gut für die Suche nach Teilzeichenketten, jedoch findet er in

der Praxis kaum Verwendung, da er O(n²) Speicherplatz und im ungünstigsten Fall O(n²) Zeit

für seine Erstellung benötigt. [Nels96]

32

3.5 Suffix-Tree

Die Struktur des Suffix-Trees gleicht der des Suffix-Tries, benötigt jedoch wesentlich weniger

Speicherplatz. Dies wird erreicht, indem wie bei dem Patricia-Trie nur dann ein Kindknoten

erzeugt wird, wenn der Baum eine Verzweigung aufweist.

Abbildung 10 Suffix-Tree für den Begriff FERNSEHER

Abbildung 9 zeigt den Suffix-Trie aus Abbildung 10 nachdem er in einen Suffix-Tree

konvertiert wurde. Durch das Löschen der Knoten mit nur einem Nachfolger wurde die

Knotenanzahl von 51 auf 13 reduziert.

Der Suffix-Trie benötigt O(n) Speicherplatz. Weiner [Wein73], McCreight [McCr76] und

Ukkonen [Ukko92b, Ukko95] zeigen, dass der Suffix-Tree in linearer Zeit erstellt werden

kann, wobei der Algorithmus von Ukkonen die häufigste Verwendung findet, da er einfacher

als die beiden anderen Algorithmen zu implementieren ist.

Für viele Anwendungen eignen sich jedoch auch Suffix-Trees nicht, da in der Praxis die

Speicherkomplexität O(n) mit einer Konstante multipliziert werden muss. Eine einfache

Implementierung des Suffix-Trees würde zumindest 20 Bytes pro Indexpunkt benötigen, was

im schlechtesten Fall dem 20-fachen der Textgröße entspricht. Ein Indexpunkt ist ein Zeiger

auf die Suffixposition im Text. Auch die effizientesten Implementierungen [Gieg99]

benötigen noch immer 9 bis 12 Bytes pro Indexpunkt. [BaNa04]

33

3.6 Suffix-Array/PAT-Array

Diese Datenstruktur wurde unabhängig voneinander, von Gonnet [Gonn92], der ihr den

Namen PAT-Array gab und von Manber und Myers [MaMy93], welche sie als Suffix-Array

bezeichneten, entdeckt.

Der Suffix-Array benötigt weniger Speicherplatz als der Suffix-Tree, da er nur die Blätter des

Trees in ein Array speichert. Da die Blätter von links nach rechts durchlaufen und im Array

gespeichert werden, befinden sie sich automatisch in lexikographischer Reihenfolge.

Abbildung 11 Suffix-Array für den Text Fernseher

Die Positionen eines Suffixes im Text werden durch binäres Suchen im Array ermittelt. Da

ein Suffix mehrmals im Text auftreten kann, muss der Anfang sowie das Ende des Bereichs

ermittelt werden in denen die Anfangspositionen für das Suffix gespeichert sind.

Abbildung 12 zeigt den Bereich im Array für die Teilzeichenkette er

Wie in Abbildung 12 zu sehen ist tritt die Teilzeichenkette er im Text Fernseher an den

Positionen 8 und 2 auf.

Der Suffix-Array stellt eine gute Alternative für den Suffix-Tree dar, da er pro Index Punkt

nur noch 4 Bytes benötigt. Wird für jedes Zeichen ein Indexpunkt verwendet, wie es für eine

Teilzeichenkette nötig ist, dann beträgt die Indexgröße die 4-fache Textgröße.

34

3.7 Fazit

Eine fehlertolerante Suchsoftware für Online-Shops soll dem Benutzer möglichst rasch

Ergebnisse liefern. Um dies gewährleisten zu können, ist es nötig, den Index im

Hauptspeicher zu halten, da Zugriffe auf externe Speichermedien verhältnismäßig lange

dauern.

Sofern ausreichend Hauptspeicher verfügbar ist, stellt der Suffix-Array eine mögliche

Alternative dar, da diese Datenstruktur sehr schnelles approximatives Suchen zulässt und im

Gegensatz zu Indizes, welche eine Baumstruktur aufweisen, nur die 4-fache Textgröße

benötigt. Fehlertolerantes Suchen im Suffix-Array kann zum Beispiel durch N-Gramm/Q-

Gramm Suchalgorithmen realisiert werden.

Eine weitere gute Alternative für die zu implementierende Software, stellt der invertierte

Index dar, da er sehr wenig Speicherplatz verbraucht und einfach zu implementieren ist. Für

eine approximative Suche muss zwar das ganze Vokabular durchlaufen werden, dieser

Nachteil wiegt sich jedoch durch den Geschwindigkeitsgewinn eines Suchdurchlaufs im

Hauptspeicher, im Vergleich zu einer Suche auf einen externen Speicher, wieder auf. Zudem

wirkt sich der Nachteil eines vollständigen Durchlaufens der Liste, nur begrenzt auf die

Performance aus, da das Vokabular nur sublinear mit der Textgröße anwächst.

Die restlichen vorgestellten Indizes, sind für die fehlertolerante Suchsoftware nicht geeignet,

da sie mehr Speicherplatz als die beiden erwähnten Alternativen benötigen und/oder keinen

Geschwindigkeitsgewinn gegenüber diesen Alternativen aufweisen.

35

4 Anforderungen an eine fehlertolerante Suchsoftware

Inhalt

Begriffsdefinition Anforderung

Szenarien

Funktionale Anforderungen

Verarbeitung strukturierter Daten

Fehlertolerante Suchfunktion

Exakte Suchfunktion

Verknüpfung von Suchabfragen

Angabe von Wertebereichen

Sortierfunktion

Indexierung

Thesaurus

Mindestähnlichkeit

Protokollierung

Verwendung von Wildcards

Phonetische Suche

Nichtfunktionale Anforderungen

Antwortzeit

Portabilität

Robustheit

In diesem Kapitel werden Anforderungen an eine fehlertolerante Suchsoftware für Online-

Shops spezifiziert. Auf Grundlage dieser Anforderungen wird ein Prototyp für fehlertolerantes

Suchen entwickelt und der fertig gestellte Prototyp auf funktionale Vollständigkeit überprüft.

36

4.1 Begriffsdefinition Anforderung

Der IEEE Standard 610 [IEEE90] definiert eine Anforderung als (1) eine Vorraussetzung oder

Fähigkeit die ein Anwender zur Lösung einer Aufgabe oder zur Erreichung eines Ziels

benötigt. (2) Eine Vorraussetzung oder Fähigkeit, die von einem System oder einer

Systemkomponente erbracht werden muss oder die es/sie besitzen muss, um einen Vertrag,

einen Standard, eine Spezifikation oder andere formell auferlegte Dokumente zu erfüllen. (3)

Eine dokumentierte Darstellung der Vorraussetzungen oder Fähigkeiten wie in Punkt (1) und

(2) beschrieben.

Anforderungen an Softwaresysteme werden oft in funktionale und nichtfunktionale

Anforderungen unterteilt. Funktionale Anforderungen beschreiben, was ein System leisten

soll bzw. über welche Funktionen ein System verfügen soll. Nicht funktionale Anforderungen

beschreiben Eigenschaften wie Zuverlässigkeit, Reaktionszeit, Speicherbedarf, Portierbarkeit

usw. und beziehen sich nicht auf die einzelnen Systemanforderungen, sondern auf das ganze

System. [Somm00]

4.2 Szenarien

Da es einfacher ist einen Bezug zu realen Beispielen herzustellen werden im Folgenden zwei

Szenarien beschrieben, die als Grundlage für die Anforderungsanalyse dienen und einen

groben Überblick geben, was der Prototyp leisten soll.

Ein Benutzer sucht in einem Online-Shop Informationen zu einem Produkt und benutzt dazu

dessen Suchfunktion. Die Suchfunktion des Online-Shops besteht aus einer einfachen Suche

sowie einer erweiterten Suche, die zusätzliche Funktionen wie Festlegen einer Ober- und

Untergrenze des Preises, Auswahl der Größe und Farbe des Produktes, zur Verfügung stellt.

Der Benutzer sucht nach TV-Geräten, jedoch vertippt er sich bei der Eingabe in das

vorgesehene Suchfeld und schreibt Fernsehr anstatt Fernseher. Da er seinen Fehler nicht

bemerkt, drückt er die Eingabetaste um die Suche zu starten. Die Suchsoftware ermittelt jene

Produkte, die den gesuchten Begriff in ihrer Bezeichnung oder Beschreibung beinhalten oder

eine festgelegte Mindestähnlichkeit mit dem Suchbegriff aufweisen. Die Ähnlichkeit wird

durch einen Ähnlichkeitskoeffizient, der mit 1-(k/m) bestimmt ist, berechnet. k steht dabei für

37

die Anzahl der Operation, die nötig sind, um einen Suchbegriff mit der Zeichenlänge m durch

Einfügen, Löschen oder Ersetzen eines Buchstaben, an ein Wort im gesuchten Text

anzupassen. Zudem werden im Suchergebnis auch Treffer angezeigt, die in einem definierten

Zusammenhang mit dem Suchbegriff stehen. Ob ein Zusammenhang mit einem Suchbegriff

besteht, wird in einer Thesaurusdatei festgelegt. Ein Thesaurus ist eine Vokabularsammlung

dessen Begriffe durch Relationen miteinander verbunden sind [Wiki05a]. Diese Relationen

umfassen Synonyme, Ober- und Unterbegriffe. Ein Synonym ist z.B. TV für Fernseher. Als

Beispiel für Ober- und Unterbegriff kann Hose und Jeans angeführt werden, wobei Hose der

Oberbegriff von Jeans ist. Dies hat zur Folge, dass bei einer Suche nach dem Begriff Hose

auch automatisch nach dem Begriff Jeans gesucht wird, umgekehrt gilt dies jedoch nicht. So

könnten im vorliegenden Szenario nicht nur Produkte mit der Bezeichnung Fernseher,

sondern auch automatisch Produkte mit der Bezeichnung TV, TV-Gerät, Plasma TV, LCD-TV

oder Fernsehgerät im Suchergebnis aufscheinen.

Trotz des Rechtschreibfehlers, wird das Suchergebnis innerhalb einer Sekunde angezeigt. Da

nach Empfinden des Benutzers zu viele Treffer gefunden wurden, verwendet er die erweiterte

Suchfunktion. Dort schränkt er den Preis auf 500 bis 700 Euro ein. Ein weiterer Suchvorgang

bringt nun die gewünschten Ergebnisse. Anschließend sortiert der Benutzer das Ergebnis nach

einer beliebigen Eigenschaft wie z. B. Bezeichnung oder Preis. Aus der sortierten

Ergebnisliste wählt er ein Produkt aus um dessen Details zu sehen und verlässt somit den

Funktionsbereich der Suche.

Ein weiteres Szenario bezieht sich auf einen Systementwickler, der mit der Integration der

fehlertoleranten Suchsoftware in ein bestehendes E-Commerce System beauftragt wird. Dazu

installiert der Entwickler zuerst die Software auf ein Testsystem, anschließend legt er die

Datenquelle, welche die Produktinformationen beinhaltet, fest und passt Parameter wie

minimale Höhe des Ähnlichkeitskoeffizienten, zu durchsuchende Produkteigenschaften und zu

indexierende Webseiten des Online-Shops usw. an. Nachdem sämtliche Einstellungen

durchgeführt wurden, testet er die Suche und nimmt gegebenenfalls Änderungen an den

Einstellungen vor. Die Software wird anschließend mit den festgelegten Einstellungen auf das

Produktionssystem übertragen. Durch Mitloggen der Suchanfragen und Auswerten der

Ergebnisse ergänzt ein Wartungsbeauftragter, den Thesaurus der Suchsoftware um fehlende

Einträge. Stellt der Wartungsbeauftragte fest, dass zum Beispiel Suchanfragen mit dem

Begriff TV vorliegen und die Suche keine Treffer lieferte, das Produkt jedoch im Sortiment

38

des Onlineshops unter der Bezeichnung Fernseher geführt wird, so ergänzt er den Thesaurus

um das Synonym TV für Fernsehgerät.

4.3 Funktionale Anforderungen

4.3.1 Verarbeitung strukturierter Daten

Produktdaten müssen in einer beliebigen eindimensionalen Struktur gespeichert werden

können. Die gesamten Daten zu einem Produkt könnten zum Beispiel in Bezeichnung,

Beschreibung und Preis aufgeteilt werden. Die einzelnen Teilbereiche der Produktdaten

werden im Folgenden als Felder bezeichnet. Eine Suche muss nach einem oder mehreren

Feldern möglich sein. Auf ein Feld kann sowohl durch einen eindeutigen Feldnamen wie z.B.

Preis als auch durch die Nummer des Feldes angesprochen werden. Die Nummerierung der

Felder beginnt bei 0.

4.3.2 Fehlertolerante Suchfunktion

Die fehlertolerante Suchsoftware soll sowohl nach Produkten als auch nach Webseiten (z.B.:

AGBs) des Online-Shops suchen. Die Analyse und Bereitstellung der Webseiteninhalte

erfolgt durch einen Webcrawler und gehört nicht zum Funktionsumfang der Software.

Fehlerhafte Suchbegriffe, die durch Vertippen oder Rechtschreibfehler entstehen, müssen von

der Software so verarbeitet werden, dass trotz des Fehlers nach dem korrekten Produkt oder

der richtigen Webseite gesucht wird. Dies gilt jedoch nur, sofern der Suchbegriff einen

Ähnlichkeitskoeffizienten aufweist, der größer oder gleich einem vom Systementwickler

festgelegten Wert ist. Werden mehrere Suchbegriffe eingegeben, so darf die Suchsoftware nur

jene Treffer als Ergebnis ausgeben, die alle gesuchten Begriffe beinhalten. Zahlen im

Suchbegriff müssen auch von der fehlertoleranten Suchfunktion exakt gesucht werden. Eine

Abfrage nach Canon i 950 darf daher im Ergebnis keine Treffer mit Canon i 990 beinhalten.

Zwischen Groß- und Kleinschreibung soll nicht unterschieden werden, sie darf daher für das

Ergebnis der Suchabfrage keine Rolle spielen.

39

4.3.3 Exakte Suchfunktion

Die Suchsoftware muss neben der fehlertoleranten Suchfunktion auch eine exakte

Suchfunktion bereitstellen. Dies ist insofern nötig, da z.B. ein Auswahlmenü auf der

Suchseite des Online-Shops festgelegte Werte wie grau, blau usw. enthalten kann. Wählt der

Benutzer nun den Wert blau aus, und ist vom Systementwickler ein Ähnlichkeitskoeffizient <

0,5 gesetzt, so wäre es möglich, dass im Suchergebnis auch Treffer mit dem Wert grau

aufscheinen. Treffer der exakten Suchfunktion weisen einen Ähnlichkeitskoeffizienten von 1

auf und stimmen vollständig mit dem Suchbegriff überein. Ob eine komplette

Übereinstimmung des Suchbegriffs innerhalb einer Teilzeichenkette zu einem Treffer führen

soll, muss beim Aufruf der Suchfunktion angegeben werden können.

4.3.4 Verknüpfung von Suchabfragen

Suchabfragen können miteinander durch eine UND, ODER sowie einer UND NICHT

Operation verknüpft werden. Durch eine UND Verknüpfung wird ein Suchergebnis erstellt,

welches nur jene Treffer enthält, die in beiden Ergebnissen vorkommen. Eine ODER

Verknüpfung erzeugt ein Suchergebnis, dass die Treffer zweier Sucherabfragen, beinhaltet.

Dabei dürfen Treffer die von beiden Abfragen gefunden werden, nur einmal im Suchergebnis

aufscheinen. Eine UND NICHT Operation erstellt ein Suchergebnis, welches die Treffer der

ersten Suchabfrage abzüglich der Treffer der zweiten Suchabfrage beinhaltet.

4.3.5 Angabe von Wertebereichen

Die Suchsoftware muss eine Funktion zur Verfügung stellen, die es ermöglicht, eine

Wertebereichsabfrage auf ein Feld durchzuführen. Der Wertebereich wird durch eine Ober-

und Untergrenze definiert, die jeweils durch Angabe einer Zahl oder durch einen Null Wert

festgelegt werden. Ein Null Wert wird als ∞ interpretiert und darf jeweils nur für eine der

beiden Grenzen gesetzt werden. Treffer des Suchergebnisses sind größer oder gleich der

Untergrenze und kleiner oder gleich der Obergrenze, dabei wird mindestens bis zu den ersten

4 Kommastellen verglichen. Eine Wertebereichsabfrage muss auf ein Feld erfolgen, welches

ausschließlich Zahlen beinhalten (z.B. Abfrage auf ein Feld mit Produktpreisen). Ist dies nicht

der Fall so wird ein Suchergebnis ohne Treffer zurückgeliefert.

40

4.3.6 Sortierfunktion

Das Suchergebnis muss nach einzelnen Feldern sowie nach dem Ähnlichkeitskoeffizienten

sortiert werden können. Neben dem zu durchsuchenden Feld ist die Angabe eines Parameters

möglich, der festlegt ob das Suchergebnis auf- oder abwärts sortiert wird. Bei einer

Aufwärtssortierung haben Zahlen Vorrang vor Buchstaben. Eine Aufwärtssortierung reiht die

Treffer des Suchergebnisses zuerst nach Sonderzeichen, dann nach Ziffern von 0 bis 9 und

anschließend nach Buchstaben von A bis Z. Bei einer Abwärtssortierung werden die Treffer

des Suchergebnisses umgekehrt von Z bis A, dann von 9 bis 0 und anschließend nach

Sonderzeichen gereiht. Die Sortierreihenfolge der Sonderzeichen selbst wird hier nicht

festgelegt. Wird der Sortierfunktion kein Wert für die Sortierrichtung mitgegeben so erfolgt

eine standardmäßige Aufwärtssortierung.

4.3.7 Indexierung

Ein Index ist eine Datenstruktur zum schnellen Auffinden von Datensätzen. Der Index muss

heterogene Datenstrukturen verwalten können, damit eine Suchabfrage sowohl nach

Webseiten als auch nach Produkten des Onlineshops möglich ist. Der Index darf die 3fache

Größe gegenüber der ursprünglichen Datenmenge nicht überschreiten und muss im

Hauptspeicher gehalten werden können. Der Größenvergleich bezieht sich auf

unkomprimierte Produktdaten in einem CSV(Comma Separated Value) Dateiformat und der

Größe des erstellten Index.

4.3.8 Thesaurus

Durch die Angabe einer Thesaurusdatei wird bei einer Suchabfrage automatisch nach

Synonymen und Unterbegriffen des Suchbegriffes gesucht. Die Thesaurusdatei steht als XML

Datei zur Verfügung. Die Struktur der XML Datei ist durch folgende DTD (Document Type

Definition) verbindlich festgelegt.

41

<?xml version=“1.0“ encoding=“UTF-8“?>

<!ELEMENT thesaurus (tEntry*)><!ELEMENT tEntry ((synonym, synonym+)|(parent, child+))><!ELEMENT synonym (#PCDATA)><!ELEMENT parent (#PCDATA)><!ELEMENT child (#PCDATA)>

Abbildung 13 DTD einer Thesaurusdatei der fehlertoleranten Suchsoftware

Durch die Thesaurusdatei in Abbildung 14 wird festgelegt, dass bei einer Suche nach TV auch

automatisch nach den Begriffen Fernseher und Fernsehgerät gesucht wird. Bei einer Suche

nach Kleidung muss auch nach Hose und nach Jeans gesucht werden. Wird nach dem Begriff

Hose gesucht, so wird auch automatisch nach Jeans gesucht, jedoch nicht nach Kleidung.

<?xml version=“1.0“ encoding=“UTF-8“?><!DOCTYPE thesaurus SYSTEM “thesaurus.dtd“><thesaurus>

<tEntry><synonym>Fernseher</synonym><synonym>Fernsehgerät</synonym><synonym>TV</synonym>

</tEntry><tEntry>

<parent>Kleidung</parent><child>Hose</child>

</tEntry><tEntry>

<parent>Hose</parent><child>Jeans</child>

</tEntry><tEntry>

<synonym>Notebook</synonym><synonym>Laptop</synonym>

</tEntry></thesaurus>

Abbildung 14 Beispiel einer Thesaurusdatei

4.3.9 Mindestähnlichkeit

Der Parameter dieser Funktion gibt an, wie fehlertolerant die Software bei einer Suchabfrage

reagieren soll. Die Mindestähnlichkeit kann einen Wert von 0 bis 1 aufweisen. Wird der Wert

der Mindestähnlichkeit zum Beispiel mit 0,7 festgesetzt, so bedeutet dies, dass die Treffer im

Suchergebnis eine Mindestähnlichkeit mit dem Suchbegriff von 70% aufweisen müssen. Eine

Einstellung des Parameters auf den Wert 0 liefert somit auch Treffer, welche keine

Ähnlichkeit mit dem Suchbegriff haben. Ein festgelegter Wert von 1 liefert hingegen nur

42

Treffer, die exakt mit dem Suchergebnis übereinstimmen. Die Standardeinstellung dieser

Funktion ist mit dem Wert 0,8 festgelegt.

4.3.10 Protokollierung

Sämtliche Suchanfragen werden in einer Logdatei mitprotokolliert, sofern ein absoluter Pfad,

in welchem die Logdatei gespeichert werden soll, angegeben wurde. Die Einträge der

Logdatei befinden sich in einem reinen Textformat und müssen folgende Syntax aufweisen:

IP-Adresse des anfordernden Computers | Zeitpunkt der Anfrage (Datum Uhrzeit) |

Suchbegriff(e) | Suchbeschränkung (Feld Grenze Wert) | Anzahl der Treffer

Abbildung 15 Syntax der Logdatei

Das Datum und die Uhrzeit müssen das Format TT/MM/JJJJ hh:mm:ss aufweisen, wobei die

Buchstaben T für Tag, M für Monat, J für Jahr, h für Stunde, m für Minute und s für Sekunde,

stehen. Die Suchbeschränkung setzt sich aus dem Feldnamen, auf welchem die Beschränkung

vorgenommen wurde, der Ober- oder Untergrenze welche durch die Buchstaben O bzw. U

repräsentiert werden, sowie dem eingegebenen Wert zusammen. Eine Logdatei mit der

beschriebenen Syntax könnte wie folgt aussehen.

193.154.168.57 | 13/02/2005 11:37:18 | Canon S 750 | Preis U 400, 5 Preis 600 | 0212.241.109.162 | 13/02/2005 11:37:05 | Joel on Software | | 162.25.122.3 | 13/02/2005 11:37:22 | Drucker | Preis U 50 | 38

Abbildung 16 Beispiel einer Logdatei

Die erste Zeile der Logdatei sagt aus, dass von einem Computer mit der IP-Adresse

193.154.168.57 am 13. Februar 2005 um 11 Uhr 37 Minuten und 18 Sekunden eine

Suchanfrage mit dem Begriff Canon S 750 mit der Einschränkung 400 bis 600 auf dem Feld

Preis, gestartet wurde. In der zweiten Zeile wurde eine Suchanfrage mit den Begriffen Joel on

Software mitprotokolliert, welche einen Treffer erzielte, und in der dritten Zeile wurde eine

Abfrage mitgeloggt, in der nach Drucker mit einem Mindestpreis von 50 Euro gesucht wurde.

43

4.3.11 Verwendung von Wildcards

Das Suchprogramm muss auch Begriffe verarbeiten können, die Platzhalter, so genannte

Wildcards, beinhalten. Ein Wildcard wird durch ein Fragezeichen ?, welches für ein einzelnes

beliebiges Zeichen steht, oder durch einen Stern * der für eine beliebig lange Zeichenkette

steht, repräsentiert. So kann der Suchbegriff ?uch für Tuch aber auch für Buch stehen. Eine

Suche nach Ba*e kann zu Treffern wie Bademantel oder Batterie führen.

4.3.12 Phonetische Suche

Zum Funktionsumfang der Software gehört auch eine phonetische Suche. Die phonetische

Suche versucht Treffer zu finden, die ähnlich wie der gesuchte Begriff betont und

ausgesprochen werden. Durch einen Parameter kann festgelegt werden, ob die phonetische

Suche zusätzlich zur fehlertoleranten Suche durchgeführt wird, ob sie nur durchgeführt wird,

wenn die fehlertolerante Suche keine Treffer erzielen konnte, oder ob sie generell

abgeschaltet ist. Enthält der Parameter den Wert 0, so wird die zusätzliche Suche aktiviert, der

Wert 1 steht für eine phonetische Suche, sofern keine Treffer erzielt wurden, und mit dem

Wert 2 wird die phonetische Suche deaktiviert. Standardmäßig ist die phonetische Suche

deaktiviert.

4.4 Nichtfunktionale Anforderungen

4.4.1 Antwortzeit

Unter den folgenden Vorraussetzungen darf die Antwortzeit für eine Suchabfrage nicht länger

als eine Sekunde dauern. Die Suchabfrage besteht aus einem einzelnen Suchbegriff, dessen

Länge zwischen 3 und 20 Zeichen liegt. Der erstellte Index wird vollständig im Hauptspeicher

gehalten und hat eine Größe von maximal 1 GB. Das System auf welchem die Suchsoftware

ausgeführt wird verfügt über eine CPU mit mindestens 2,0 GHz und über genügend

Arbeitsspeicher, um den Index im Hauptspeicher zu halten, mindestens jedoch 512 MB.

Die Antwortzeit wird ab dem Zeitpunkt des Funktionsaufrufes des Suchprogramms bis zu

dem Zeitpunkt, an dem das Programm eine Liste mit allen gefundenen Treffern bereitstellt,

44

gemessen. Die festgelegte Antwortzeit von einer Sekunde, muss bis zu 5 gleichzeitigen

Suchabfragen eingehalten werden.

4.4.2 Portabilität

Die Software muss auf den Betriebssystemen WinXP, WinNT, Sun Solaris und Linux

eingesetzt werden können. Ferner soll das Produkt in Java implementiert und unter Einsatz

der JRE (Java Runtime Environment) 1.4 lauffähig sein.

4.4.3 Robustheit

Ein besonderer Wert wird auf die Stabilität und Robustheit der Software gelegt. Die Software

muss bei auftretenden Fehlern eine Exception, mit einer Beschreibung des Problems, werfen.

Exceptions können somit vom Systementwickler des Online-Shops abgefangen und in einer

Logdatei mitprotokolliert werden.

45

5 Lucene

Inhalt

Allgemeiner Überblick

Indexierung

Suche

Anpassungen/Erweiterungen

Für die Implementierung des Prototyps standen die Alternativen, die Software von Grund auf

neu zu implementieren, eine vorhandene Suchsoftware, entsprechend den in Kapitel 4

definierten Anforderungen, zu modifizieren oder ein Suchframework zu verwenden, zur

Auswahl.

Von diesen drei Möglichkeiten wurde dem Framework der Vorzug gegeben, da eine von

Grund auf neue Implementierung zeitaufwendig und fehleranfällig ist. Eine bereits vollständig

implementierte Suchsoftware anzupassen birgt wiederum den Nachteil in sich, das diese

bereits auf einen speziellen Kontext zugeschnitten wurde und eine Erweiterung bzw.

Anpassung des Codes nur sehr schwer möglich. Ein Framework hingegen lässt sich leicht

anpassen und erweitern. Es besteht aus einer Menge zusammenarbeitender Klassen, die einen

wieder verwendbaren Entwurf für einen bestimmten Softwarebereich darstellen. Die

Architektur eines Frameworks bestimmt alle darauf basierenden Anwendungen. Es definiert

die Struktur im Großen, seine Unterteilung in Klassen und Objekte, die jeweiligen zentralen

Zuständigkeiten, die Zusammenarbeit der Klassen und Objekte, sowie den Kontrollfluss. Es

legt diese Entwurfsparameter im Voraus fest, so dass sich Anwendungsentwickler auf die

spezifischen Details Ihrer Software konzentrieren können. [GaHe95]

Im Unterschied zu einem von Grund auf neu erstellten System können Anwendungen weitaus

schneller und mit einer geringen Fehlerrate entwickelt werden.

Für die Implementierung des Prototyps standen die beiden frei erhältlichen Frameworks

Lucene [Luce05] und Egothor [Egot05] in der engeren Auswahl. Egothor und Lucene setzen

46

in den Hauptklassen ähnliche Algorithmen ein und bieten auch insgesamt eine ähnliche

Funktionalität [GoHa04]. Die Entscheidung fiel für den Einsatz von Lucene, da dieses

Framework besser dokumentiert und von einer größeren Gemeinschaft unterstützt wird.

5.1 Allgemeiner Überblick

Lucene wurde ursprünglich von Doug Cutting entwickelt und ist seit September 2001 ein

Projekt der Apache Software Foundation. Lucene steht unter der Apache Lizenz Version 2.0

[Apac05], welche eine Veränderung des Quellcodes sowie den Einsatz in kommerziellen

Produkten erlaubt. Bei einem Vertrieb der Software muss jedoch darauf hingewiesen werden,

welcher Teil der Software von der Apache Software Foundation stammt bzw. welche Teile

der Software geändert wurden. Zudem muss eine Kopie der Lizenz beigelegt werden.

Lucene ist keine fertige Suchsoftware sondern ein Framework das bereits Klassen zum

Indexieren und Suchen von Textdaten beinhaltet. Neben diesen Hauptklassen stehen weitere,

für Textretrieval typische Klassen, zur Verfügung. Zum Beispiel unterstützt das Framework

Wordstemming, das Filtern von Stop Wörtern und viele weitere Funktionalitäten. Die beiden

wichtigsten Funktionalitäten betreffen jedoch die Indexierung und Suche.

Abbildung 17 zeigt den Programmablauf für die Indexierung und Suche in Lucene. Der

strichlierte Pfad zeigt wie der Index mit Dokumenten gefüllt wird. Als Dokument wird in

diesem Kontext eine Datenstruktur bezeichnet, welche so genannte Felder, beinhaltet. In den

einzelnen Feldern wiederum sind die eigentlichen Daten gespeichert. So besteht ein

Dokument zum Beispiel aus den Feldern ArtikelID, Bezeichnung, Beschreibung und

dergleichen. Die Dokumente müssen vom Benutzer bereitgestellt werden. Diese können zum

Beispiel von einer Datenbank oder einer Textdatei kommen. Die Dokumente werden an die

Klasse Analyzer weitergereicht. Der Analyzer wertet die Daten in den Dokumente aus, und

filtert gegebenenfalls StopWörter heraus, oder konvertiert den Inhalt in Kleinbuchstaben usw.

Das Resultat des Analyzers wird and die Klasse IndexWriter übermittelt, welche den Index

erstellt bzw. aktualisiert.

Um eine Suchabfrage auf den erstellten Index auszuführen muss zuerst eine Subklasse der

abstrakten Klasse Query instanziert werden. Zum einen ist es möglich eine Instanz der

gewünschten Subklasse wie zum Beispiel WildcardQuery direkt anzulegen, zum anderen

47

kann diese Aufgabe auch von der Klasse QueryParser übernommen werden. Aufgabe des

Klasse QueryParser ist die gesuchte Zeichenkette auszuwerten. Enthält ein Wort der

Zeichenkette einen Stern oder ein Fragezeichen so wird mit diesem Wort eine WildcardQuery

instanziert. Für Wörter oder Wortphrasen die unter Hochkomma gestellt sind wird hingegen

die Klasse PhraseQuery instanziert usw. Der Klasse QueryParser kann zudem eine Analyzer

Klasse übergeben werden. Dies sollte die gleiche Klasse sein, die auch zur Indexierung

verwendet wurde. Das Ergebnis der Klasse QueryParser ist eine Query Klasse, welche an die

Klasse IndexSearcher übergegeben wird. Diese durchsucht den Index auf mögliche Treffer

und gibt die Klasse Hits zurück, welche sämtliche gefundenen Suchergebnisse beinhaltet.

Abbildung 17 zeigt den Ablauf der Indexierung und Suche in Lucene. Übernommen aus [RiAv04]

5.2 Indexierung

Wie in Kapitel 3 gezeigt wurde, gibt es verschiedenste Möglichkeiten einen Index für eine

schnelle Suche zu erstellen. Lucene verwendet einen invertierten Index, welcher den Vorteil

hat, dass er wenig Speicherplatz benötigt, da er sublinear zur Textgröße wächst. In Lucene

wird dieser invertierte Index nicht in einer einzigen Datenstruktur abgespeichert sondern in

mehrere Segmente unterteilt. Wird dem Index ein Dokument hinzugefügt so wird für dieses

48

Dokument zuerst ein neues Indexsegment angelegt und dieses in einem Stack in welchem sich

sämtliche Segmente befinden abgelegt. Sobald die Anzahl der Indexsegmente, eine vom

Benutzer festgelegte Größe erreicht, werden sie zu einem Segment zusammengefügt.

Abbildung 18 zeigt wie der invertierte Index in Lucene verwaltet wird. Es sind 11 indizierte

Dokumente und ein Stack mit 4 Indexsegmenten zu sehen. Indexsegmente werden

zusammengefügt, sobald es 3 Segmente mit gleicher Anzahl an Dokumenten gibt. Grau

eingefärbte Indexsegmente wurden bereits gelöscht bzw. zu einem größeren Segment

zusammengefügt.

Abbildung 18 Lucene Index Diagram. Übernommen aus [Cutt00]

Im Folgenden werden die wichtigsten Klassen für eine Indexierung in Lucene beschrieben.

5.2.1 IndexWriter

Eine zentrale Komponente im Indexprozess spielt die Klasse IndexWriter. Sie ist für das

Erzeugen eines neuen Index zuständig. Eine weitere Aufgabe besteht im Hinzufügen von

neuen Dokumenten zu einem bestehenden Index. Die Klasse IndexWriter hat nur

Schreibzugriff auf den Index und verfügt über keine Lese- oder Suchfunktionen.

49

5.2.2 Directory

Die abstrakte Klasse Directory repräsentiert den Speicherot eines Index. Die Subklassen

FSDirectory und RAMDirectory werden von der Klasse IndexWriter verwendet um einen Index

auf einen externen Datenträger oder im Hauptspeicher zu erstellen. Für Applikationen die

einen schnellen Zugriff auf den Index benötigen, wie zum Beispiel in Online-Shops, eignet

sich die Klasse RAMDirectory. Neben einem leeren Konstruktor verfügt die Klasse

RAMDirectory auch über einen Konstruktor der eine Klasse FSDirectory aufnimmt. Es ist

daher möglich einen Index auf einen externen Datenträger zu speichern und ihn beim Start der

Suchsoftware mit der Klasse RAMDirectory in den Hauptspeicher zu laden. So wird der Index

einerseits persistent gehalten, andererseits ist es aber auch möglich schnelle Suchabfragen auf

den Index im Hauptspeicher durchzuführen.

5.2.3 Analyzer

Oft ist es sinnvoll, für die Suche unbedeutsame Wörter, aus einem Text zu löschen bevor

dieser indexiert wird. Zum Beispiel sind die Wörter der, die, wir, durch, und, er und noch

viele andere, für die Unterscheidung von Dokumenten wenig sinnvoll. Diese Wörter werden

auch als Stoppwörter bezeichnet, dementsprechend lautet die dafür zuständige Klasse

StopAnalyzer. StopAnalyzer ist, neben den Subklassen StandardAnalyzer, SimpleAnalyzer

und WhitespaceAnalyzer, eine Subklasse der abstrakten Klasse Analyzer.

5.2.4 Document

Die Klasse Document speichert eine Liste von Feldern. Werden zum Beispiel Produkte eines

Online-Shops indexiert so könnte eine Instanz der Klasse Document die Felder ProduktID,

Bezeichnung, Beschreibung, Preis und dergleichen beinhalten.

5.2.5 Field

Jedes Document beinhaltet ein oder mehrere benannte Felder, also Instanzen der Klasse Field.

Insgesamt gibt es vier Typen von Feldern. Felder des Typs Keyword, werden indexiert und im

Index gespeichert, jedoch nicht von der im IndexWriter spezifizierten Klasse Analyzer

50

modifiziert. Für Felder deren Inhalt im Suchergebnis angezeigt wird, nach denen aber nicht

gesucht werden soll, gibt es den Typ UnIndexed. Felder dieses Typs werden im Index

gespeichert aber weder analysiert noch indexiert. Ein mögliches Beispiel für eine Anwendung

dieses Typs wäre ein Link der vom Suchergebnis zur Detailseite des gefundenen Produktes

führt. Felder des Typs UnStored werden analysiert und indexiert aber nicht im Index

gespeichert. Sie eignen sich zum Beispiel zum Indexieren von Webseiten, nach denen zwar

gesucht werden soll, deren Inhalt aber nicht im Suchergebnis angezeigt wird. Eine weitere

Möglichkeit ist Felder mit dem Typ Text zu instanzieren. Felder dieses Typs werden

analysiert, indexiert und gespeichert wenn sie mit einem String instanziert werden, jedoch nur

analysiert und indexiert wenn sie mit einem Reader Objekt instanziert werden.

5.3 Suche

Mit Lucene lässt sich ein Index sehr einfach und schnell durchsuchen. Lucene beinhaltet

Klassen für exaktes Suchen, für eine Suche nach Wildcards, Phrasen und Teilzeichenketten

sowie für unscharfes Suchen. Eine approximative Suche in Teilzeichenketten ist jedoch nicht

implementiert. Zum Beispiel ist es nicht möglich mit dem falsch geschriebenen Suchbegriff

Druckr ein Produkt mit der Bezeichnung Tintenstrahldrucker zu finden. Eine Erweiterung

von Lucene um diese und andere Funktionalitäten ist Teilaufgabe dieser Diplomarbeit. Eine

Beschreibung über alle notwendigen Erweiterungen und Modifikationen von Lucene, folgt am

Ende dieses Kapitels.

Im Folgenden werden die Klassen die für eine Suche in Lucene benötigt werden beschrieben.

5.3.1 IndexSearcher

Die Klasse IndexSearcher ist das Gegenstück zur Klasse IndexWriter. IndexSearcher öffnet

den von IndexWriter erzeugten Index im Lesemodus und beinhaltet bereits einige

Suchmethoden. Die einfachste Suchmethode erwartet als Parameter eine Instanz der Klasse

Query und gibt als Ergebnis ein Hits Objekt zurück.

51

5.3.2 Term

Die Klasse Term besteht aus dem Namen des gesuchten Feldes und dem gesuchten

Suchbegriff. Für eine Suche nach dem Begriff Fernseher in der Produktzeichnung, müsste

also ein Term Objekt mit den Parametern Bezeichnung und Fernseher instanziert werden.

5.3.3 Query

Die abstrakte Klasse Query dient als Basisklasse für die Klassen TermQuery, WildcardQuery,

FuzzyQuery und noch weiterer Subklassen. Query Objekte werden von der Klasse

IndexSearcher für die Suche verwendet. Eine besondere Rolle kommt der Klasse

BooleanQuery zu. Mit ihr ist es möglich mehrere Query Klassen zu verknüpfen. Mittels der

Methode public void add(Query query, boolean required, boolean

prohibited) können die einzelnen Query Instanzen zur Klasse BooleanQuery hinzugefügt

werden. Durch Parameter required und prohibited wird angegeben, ob das Ergebnis einer

Abfrage für das Gesamtergebnis erforderlich ist, ob es optional ist oder ob das

Gesamtergebnis die Treffer dieser Suchabfrage nicht beinhalten darf.

5.3.4 Hits

Nach einer durchgeführten Suche wird von der Klasse IndexSearcher ein Objekt der Klasse

Hits zurückgegeben. Das Hits Objekt enthält alle nach Ähnlichkeit sortierten Suchergebnisse.

Die einzelnen Suchergebnisse sind in Form von Documents gespeichert. Mit der Methode

doc(int n) wird auf die einzelnen Document Instanzen des Hits Objekt zugegriffen.

5.4 Erforderliche Anpassungen/Erweiterungen

Obwohl Lucene grundlegende Klassen für die Indexierung und Suche bereitstellt, muss das

Framework noch um Funktionalitäten erweitert bzw. angepasst werden, damit der Prototyp,

den in Kapitel 4 definierten Anforderungen, entspricht. Sämtliche Anpassungen betreffen

lediglich den Suchteil des Frameworks. Der Index wird hingegen unverändert übernommen,

52

da es mit ihm bereits ermöglich ist, Daten strukturiert zu speichern und der verwendete Index

zudem speichereffizient und einfach zu verwalten ist.

Wie vorhin erwähnt beinhaltet Lucene keine unscharfe Suche in Teilzeichenketten. Zudem

werden Buchstabenverdreher als zwei Fehler gezählt. Zum Beispiel würde für den falsch

geschriebene Suchbegriff Montior im Text Monitor nur eine Ähnlichkeit von 71,4% ermittelt

(1-k/(min(m,n))), obwohl das Austauschen der Buchstaben ti zu it in einer Operation möglich

ist. Eine Wertung als einen Fehler ergibt eine wesentlich höhere Ähnlichkeit von 85,7%. Eine

approximative Suche in Teilzeichenketten kann auf mehrere Arten implementiert werden und

wird im Kapitel Implementierung näher beschrieben.

Neben dieser Modifikation muss Lucene um einen Thesaurus, einer phonetische Suche, einer

Protokollierungsfunktion von Suchabfragen und einer Analyse von Suchbegriffen erweitert

werden. Die Analyse von Suchbegriffen dient der Zuordnung des gesuchten Begriffes zur

entsprechenden Abfrage. So soll nach Suchbegriffen generell approximativ, nach

Suchbegriffen, welche Zahlen oder Wildcards enthalten, jedoch exakt gesucht werden.

Alle weiteren, in Kapitel 4 definierten Anforderungen, können ohne Modifikationen oder

Erweiterung mit dem bestehenden Framework realisiert werden.

53

6 Implementierung

Inhalt

Überblick

Verwendete Bibliotheken und Frameworks

JUnit

Ant

Log4J

Xerces 2 Java Parser

Phonetix

Struts

JMeter

Architektureller Überblick

Indexkomponente

Suchkomponente

Komponenten und Funktionen des Prototyps

Thesaurus

SearchRequestLogger

Phonetische Suche

Fehlertolerante Suche

QueryParser

Angabe von Wertebereichen

Beispielapplikation

Last- und Performancetests

6.1 Überblick

54

Für die Implementierung des Prototyps kamen neben dem Framework Lucene weitere

Bibliotheken und Frameworks zum Einsatz. Alle verwendeten Bibliotheken und Frameworks

gelten zurzeit als de facto Standard in ihrem Anwendungsbereich. Für die Entwicklung des

Prototyps wurde das Konzept der testgetriebenen Entwicklung oder Test-Driven

Development, wie es im Englischen bezeichnet wird, angewandt. Dies bedeutet, dass zuerst

Tests für Softwarekomponenten geschrieben werden und erst anschließend die Komponente

selbst implementiert wird. Zur Umsetzung der testgetriebenen Entwicklung wurde das

Testframework JUnit [JUni05] verwendet. Die Build-Prozesse wurden mit Hilfe des

Werkzeuges Ant [Ant05] durchgeführt. Ein Build-Werkzeug führt Schritte, die für eine

Veröffentlichung eines Programm nötig sind, automatisch durch. Dazu gehören unter

anderem Code-Kompilierung, Binden des kompilierten Codes an Bibliotheken, die

Generierung einer technischen Dokumentation oder das Durchführen von Komponententests.

Als Alternative zu Ant stand auch das Build Werkzeug Maven [Mave05] zur Auswahl,

welches auf Ant aufbaut und dieses erweitert. Da die Funktionalitäten von Ant für die

Erstellung des Prototyps jedoch ausreichten, wurde auf das komplexere Werkzeug Maven

verzichtet. Für die Protokollierung von Fehlern und Informationen wurde die Bibliothek

Log4J [Log05] und für das Parsen der Thesaurus Datei der XML Parser Xerces2 [Xerc05]

verwendet. Die Bibliothek Phonetix [Phon05] der Firma .tangentum technologies wurde für

die Implementierung der phonetischen Suche eingesetzt. Weiters wurde für eine

Beispielanwendung, das Webapplikationsframework Struts [Strut05] verwendet. Das Ziel der

Beispielanwendung besteht darin, den Einsatz des Prototyps unter Verwendung realer

Produktdaten zu zeigen und den Nutzen der Software besser einschätzen zu können. Für

abschließende Lasttests kam Apaches JMeter [JMet05] zum Einsatz.

6.2 Verwendete Bibliotheken und Frameworks

Im Folgenden wird zuerst jeweils eine kurze Beschreibung der verwendeten Bibliotheken und

Frameworks gegeben und anschließend der erstellte Prototyp beschrieben.

6.2.1 JUnit

55

http://de.wikipedia.org/wiki/Dokumentation_(Technik)

http://de.wikipedia.org/wiki/Bibliothek_(Programmierung)

http://de.wikipedia.org/wiki/Linker_(Programm)

http://de.wikipedia.org/wiki/Kompilierung

http://de.wikipedia.org/wiki/Quelltext

http://de.wikipedia.org/wiki/Anwendungsprogramm

JUnit ist ein Testframework für Komponententests. Eine Komponente ist ein Baustein zur

Softwareherstellung, welche ihre Funktionalität über Schnittstellen anbietet [Szyp98]. Der

Quellecode für das Testframework ist frei verfügbar und steht unter IBM’s Common Public

Lizenz Version 1.0. Diese Lizenz erlaubt es JUnit für die Entwicklung kommerzieller

Produkte einzusetzen.

Komponententests oder auch Unit Tests, wie sie im Englischen genannt werden, prüfen das

Verhalten der Bausteine. Es wird geprüft, ob ein bestimmter Eingabewert einer Methode

einen erwarteten Rückgabewert erzeugt. [Mass04]

Anhand eines sehr einfachen Beispiels wird nun gezeigt wie Tests in JUnit implementiert

werden.

public class Calculator {

public double add(double number1, double number2) {

return number1 + number2;

}

}

Codebeispiel 1 Die Klasse Calculator berechnet die Summe zweier Zahlen.Übernommen aus JUnit in Action [Mass04]

Die Klasse Calculator stellt eine Methode add zur Verfügung, welche die Summe zweier Zahlen berechnet. Um sicher zu gehen, dass die Methode die Summe richtig berechnet, wird sie mittels der Klasse TestCalculator getestet.

import junit.framework.TestCase;

public class TestCalculator extends TestCase{

public void testAdd() {

Calculator calculator = new Calculator();

double result = calculator.add(10, 50);

assertEquals(60, result, 0);

}

}

Codebeispiel 2 Die Klasse TestCalculator prüft ob die Methode add der Klasse Calculator den erwarteten Wert erzeugt. Übernommen aus JUnit in Action [Mass04]

56

Die Klasse TestCalculator erweitert die Klasse TestCase und prüft mittels der Methode

testAdd() die Methode add() der Klasse Calculator. Der erste Wert der Methode assertEquals

steht für das erwartete Ergebnis, der zweite Wert steht für das tatsächliche Ergebnis. Der

dritte Parameter gibt eine maximale Abweichung der beiden ersten Parameter an. Er kann

meist vernachlässigt werden, da er nur in speziellen Fällen für Fließkommaberechnungen

benötigt wird. Neben der Methode assertEquals gibt es noch eine Reihe weiterer Methoden,

wie assertTrue, assertNotNull usw., zur Überprüfung der Bausteine.

Klassen, welche die Klasse TestCase erweitern können zu einer TestSuite zusammengefügt

werden. Die Verwendung einer TestSuite eignet sich um zusammengehörige Tests zu

gruppieren.

Mittels eines Build Werkzeuges wie Ant oder Maven können Komponententests automatisiert

werden. Durch eine entsprechende Konfiguration der Build Datei, werden bei jedem Build

Prozess sämtliche Komponententests durchgeführt. Somit kann sichergestellt werden, dass

alle getesteten Komponenten im Laufe des gesamten Entwicklungsprozess funktionieren.

Sollte ein Test fehlschlagen, da eine getestete Komponente verändert wurde und somit nicht

mehr das erwartete Ergebnis liefert, dann bricht das Build Werkzeug den

Veröffentlichungsprozess ab und teilt dem Benutzer mit, welcher Test nicht erfolgreich

durchgeführt werden konnte.

6.2.2 Ant

Ant ist ein auf Java basierendes Build Werkzeug. Mit diesem Werkzeug lassen sich Aufgaben

wie das Kompilieren von Code, Erstellen von Dokumentationen, das Durchführen von Tests

und weitere Routineaufgaben automatisieren. Dies ist insbesondere bei größeren Projekten

von Vorteil, da mit nur einem Knopfdruck eine aktuelle Version des Programms erstellt

werden kann. Konfiguriert wird Ant über eine XML Datei die üblicherweise unter dem

Namen build.xml gespeichert wird.

57

Abbildung 19 Konzeptionelle Darstellung einer Build Datei. Übernommen aus [HaLo03]

Abbildung 19 stellt einen Build Prozess konzeptionell dar. Der Prozess setzt sich aus

verschiedenen Aufgaben (Tasks) zusammen, die zu Zielen (Targets) gruppiert wurden.

Zwischen Zielen kann es Abhängigkeiten geben. So muss zuerst das Ziel init erfolgreich

durchgeführt werden, bevor die Ziele compile und doc abgearbeitet werden können. Die

Aufgaben des Zieles deploy können erst erledigt werden, wenn die Aufgaben aller anderen

Ziele durchgeführt wurden.

Das folgende Codebeispiel zeigt die Umsetzung der konzeptionellen Darstellung in Form

einer Ant konformen XML-Datei.

<?xml version="1.0" ?><project name="OurProject" default="deploy">

<target name="init"><mkdir dir="build/classes" /><mkdir dir="dist" />

</target><target name="compile" depends="init" >

<javac srcdir="src" destdir="build/classes"/>

</target><target name="doc" depends="init" >

<javadoc destdir="build/classes" sourcepath="src" packagenames="org.*" />

</target><target name="deploy" depends="compile,doc" >

58

<jar destfile="dist/project.jar" basedir="build/classes"/>

<ftp server="${server.name}" userid="${ftp.username}" password="${ftp.password}"><fileset dir="dist"/>

</ftp></target>

</project>

Codebeispiel 3 zeigt einen Auszug einer Ant Konfigurationsdatei. Übernommen aus [HaLo03]

Das Codebeispiel 3 sollte großteils selbsterklärend sein. Die Notation ${..} steht für eine

Variable, die ebenfalls in der Konfigurationsdatei festgelegt sein muss. Variablen können mit

dem Tag property definiert werden. Mit <property name="ftp.username"

value="testUser"/> würde man somit den Wert testUser als Benutzername festlegen.

6.2.3 Log4J

Log4J ist ein Framework zur Protokollierung von Anwendungsmeldungen in Java. Um ein

Ereignis zu protokollieren, wird die Wichtigkeit der Nachrichten festgelegt und an das

Logginsystem übergeben. Dem Entwickler bleibt lediglich die Aufgabe, die Wichtigkeit der

Nachricht einzuschätzen. Die Stufen reichen von DEBUG, INFO, WARN, ERROR bis FATAL,

wobei DEBUG am unwichtigsten ist. Zur Laufzeit kann die Filterung und die Art der Ausgabe

konfiguriert werden. Legt man z.B. als Schwellwert die Stufe WARN fest, so werden nur

Meldungen der Stufe WARN, ERROR und FATAL ausgegeben. Auch das Ziel der Ausgabe,

zum Beispiel direkt auf der Konsole oder in einer Datei, kann festgelegt werden.

package test;

import org.apache.log4j.Logger;

public class HelloWorld {

static Logger logger = Logger.getLogger("test.HelloWorld");

static public void main(String[] args) {

logger.debug("Hello world.");

}

}

Codebeispiel 4 zeigt die Verwendung des Log4J Frameworks

59

Das Codebeispiel 4 zeigt eine Protokollierung mit Hilfe des Log4J Frameworks. Zuerst wird

eine statische Variable logger definiert. Die logger Variable wird durch einen Aufruf der

Methode getLogger der Klasse Logger initialisiert. Dies hat zur Folge, dass neben der

Nachricht Hello world auch der Name der Klasse gespeichert wird. [Wiki05b]

10 [main] DEBUG test.HelloWorld – Hello world.

Codebeispiel 5 zeigt eine mögliche Ausgabe der Klasse HelloWorld

Die Ausgabe enthält die relative Zeit vom Programmstart bis zum Aufruf der Loggermethode,

den Namen des Threads, die Wichtigkeit der Nachricht, den Namen des Loggers und die

eigentliche Nachricht. [Gülc04]

6.2.4 Xerces 2 Java Parser

Xerces 2 Java Parser analysiert XML Dokumente und baut aus den gewonnen Daten eine

Baumstruktur auf. Die Baumstruktur besteht aus Knoten, die miteinander durch Zeiger

verbunden sind und Dokumente, Elemente und Attribute enthalten. Der Xerces 2 Java Parser

implementiert das vom World Wide Web Consortium (W3C) spezifizierte Document Object

Model (DOM). DOM ist eine API und beschreibt, wie auf HTML- oder XML-Dokumente

zugegriffen wird.

6.2.5 Phonetix

Die Klassenbibliothek Phontix der Firma tangentum technologies beinhaltet

Implementierungen der phonetischen Algorithmen Soundex, Metaphone sowie

DoubleMetaphone. Die Bibliothek ist frei erhältlich und steht unter der GNU Lesser General

Public Lizenz [GNU05]. Zusätzlich enthält die Bibliothek Adapterklassen für Lucene, durch

die eine rasche Integration der Algorithmen möglich ist.

6.2.6 Struts

Für die Beispielanwendung, anhand derer der Einsatz der fehlertoleranten Suchsoftware

gezeigt wird, wurde das Webapplikationsframework Struts verwendet. Struts verfolgt einen so

60

genannten Modell 2 Ansatz, der eine Übertragung des Modell View Controller Konzeptes auf

Webanwendungen ist.

Abbildung 20 zeigt die Umsetzung des Model 2 Konzeptes in Struts. Übernommen aus [IBM05]

JSP oder HTML Seiten dienen zur Anzeige und Aufnahme von Daten. Die Controller

Komponente wird von Struts durch ein Servlet mit der Bezeichnung ActionServlet zur

Verfügung gestellt. Dieses Servlet liest eine Konfigurationsdatei ein, in welchem die

Komponenten zur Verarbeitung der Daten festgelegt sind.

<action path="/simpleSearch"type="SimpleSearch"name="searchForm"validate="true"input="/search.jsp"><forward name="productsFound"

path="/displayResults.jsp"/><forward name=“noProductFound“

Path=“/noResults.jsp“/>

</action>

Codebeispiel 6 Auszug einer Struts Konfigurationsdatei

Das Codebeispiel 6 zeigt einen Auszug einer Struts Konfigurationsdatei. Eine Action schickt

einen Request an eine vom Entwickler implementierte Komponente. Das Attribut path

bezeichnet die Action welche von einer JSP oder HTML Seite aus angesprochen werden kann.

Mit type wird die Komponente, welche den Request verarbeiten soll, angesprochen. Bevor

dies jedoch geschieht, wird die im Attribut name festgelegte Formklasse mit den

übermittelten Daten der JSP bzw. HTML Seite gefüllt. Falls validate auf true gesetzt ist, wird

eine im Form festgelegte Validierung durchgeführt. Nur wenn diese erfolgreich durchgeführt

wurde, werden die Daten an die in type festgelegte Klasse übermittelt. Schlägt die

61

Validierung fehl, so wird auf die in input spezifizierte Seite weitergeleitet. Pro Action sind

mehrere forward Tags möglich. Diese geben die Seite an, zu welche der Benutzer

weitergeleitet wird, nachdem die in type festgelegte Komponente, die Daten verarbeitet hat.

6.2.7 JMeter

JMeter ist ein Werkzeug zum Ausführen von Lasttests. Um einen Test in JMeter

durchzuführen, wird zuerst ein Testplan erstellt. Ein Testplan enthält wiederum eine oder

mehrere Testgruppen. Für jede Testgruppe wird festgelegt, wie viele Instanzen gleichzeitig

auf das Testobjekt zugreifen sollen und in welcher Anlauf-Zeit dies geschehen soll.

Abbildung 21 JMeter Benutzeroberfläche

Die Anlauf-Zeit gibt an, wie lange JMeter benötigen soll, um die volle Anzahl an Instanzen

auf das Testobjekt zu leiten. Zum Beispiel startet JMeter bei einer Anlauf-Zeit von 60

Sekunden und 6 Instanzen, innerhalb dieses Zeitraumes, alle 10 Sekunden eine weitere

Instanz.

6.3 Architektureller Überblick

Abbildung 22 zeigt eine grobe Struktur des Prototyps. Für den Einsatz der Suchsoftware in

einer Webapplikation, müssen lediglich die zu durchsuchenden Produktdaten bereitgestellt

und die Klassen Indexer sowie Searcher konfiguriert werden. Soll die Suchsoftware auch

62

nach Synonymen und Unterbegriffen eines Suchausdruckes suchen, so muss überdies eine

Thesaurusdatei definiert werden.

Abbildung 22 Architektur der Suchsoftware

Die beiden nächsten Abbildungen zeigen wie die Klassen der Index- sowie Suchkomponente

zusammenhängen. Zweck dieses Kapitels, ist es einen Überblick über die Architektur der

Software zu geben. Die Abbildungen enthalten daher nur die wichtigsten Klassen und

Methoden.

Wie in Abbildung 23 zu sehen ist, spielt die Klasse Indexer eine zentrale Rolle bei der

Indexerstellung. Für den Einsatz der Software muss nur eine Instanz der Klasse Indexer

erstellt und konfiguriert werden. Alle weiteren Aufgaben, wie das Auslesen von Synonymen

und Oberbegriffen aus einer Thesaurusdatei, die Erstellung von phonetischen Codes usw.,

wird mithilfe der abgebildeten Klassen, wie zum Beispiel ThesaurusAnalyzer automatisch

durchgeführt.

Auch die in Abbildung 24 dargestellte Suchkomponente, verfügt über eine zentrale Klasse

Searcher, welche lediglich instanziert und konfiguriert werden muss, um eine lauffähige

Suchapplikation zu erhalten.

Eine nähere Beschreibung der einzelnen Klassen wird in Punkt 6.4 gegeben.

63

Abbildung 23 architektureller Überblick der Indexkomponente

64

Abbildung 24 architektureller Überblick der Suchkomponente

65

6.4 Implementierte Komponenten und Funktionen des Prototyps

Im Folgenden werden die implementierten Komponenten sowie realisierte Funktionen des

Prototyps näher beschrieben.

6.4.1 Thesaurus

Der Thesaurus besteht aus den Klassen ThesaurusNode, ThesaurusFileReader und der

Klasse Thesaurus. Die Klasse ThesaurusNode repräsentiert jeweils einen Begriff mit

Referenzen zu dessen Unterbegriffen sowie Synonymen. Die ThesaurusFileReader Klasse

liest mit Hilfe von Apache Xerces 2 Java Parser eine XML Datei, in der sämtliche Relationen,

wie Synonyme und Unterbegriffe, gespeichert sind, ein und baut eine Struktur mit

ThesaurusNode Objekten auf. Die erstellte Struktur wird an die Klasse Thesaurus übergeben.

Für eine Suche nach Synonymen sowie Unterbegriffen eines Suchbegriffs stellt die Klasse

Thesaurus die Methode getSynonymsAndChilds(String searchTerm) zur Verfügung, die eine

Liste mit allen gefunden Begriffen liefert. Um Synonyme und Oberbegriffe zu einem Begriff

zu finden muss die Methode getSynonymsAndParents (String serachTerm) aufgerufen

werden.

Thesaurus thesaurus = new Thesaurus("C:/thesaurus.xml");

ArrayList list = thesaurus.getSynonymsAndChilds("Computer");

Codebeispiel 7 zeigt eine Anwendung der Thesauruskomponente

Neben direkten Relationen findet der Thesaurus auch Konstruktionen wie den Unterbegriff

eines Unterbegriffes oder das Synonym eines Unterbegriffes.

66

Abbildung 25 zeigt Struktur und Aufbau des Thesaurus

Der Thesaurus verfügt über einen Hashtable, der einen schnellen Zugriff auf die gespeicherten

Knoten ermöglicht. Die Methoden getSynonymsAndChilds sowie getSynonymsAndParents

der Klasse Thesaurus gehen von dem Knoten mit dem gesuchten Begriff aus, und speichern

alle mit ihm verbunden Relationen in eine Liste. Ein Thesaurus, der die in Abbildung 25

dargestellten Knoten enthält, würde bei einem Aufruf der Methode

getSynonymsAndChilds("Computer") eine Liste mit den Begriffen Notebook sowie Laptop

liefern. Eine Suche nach Laptop hingegen würde nur eine Liste mit dem Begriff Notebook

liefern.

Für die Integration der Thesauruskomponente in Lucene gab es zwei Alternativen. Die erste

Möglichkeit bestand darin, die Wörter einer Suchanfrage zu extrahieren und mit diesen nach

Synonymen und Kindern im Thesaurus zu suchen. Anschließend müsste für jedes Synonym

und für jeden Unterbegriff eine Query erzeugt und die einzelnen Query Objekte in einer

BooleanQuery optional verknüpft werden. Die Idee der zweiten Alternative lag darin,

während der Indexerstellung bereits Synonyme und Oberbegriffe der im Index

vorkommenden Begriffe zu suchen und zu speichern. Die erste Möglichkeit hat den Vorteil,

dass nach Relationen, welche neu in der Thesaurusdatei eingefügt wurden auch sofort gesucht

werden kann. Jedoch müsste bei jeder Suchabfrage zusätzlich eine Suchabfrage auf den Inhalt

des Thesaurus ausgeführt werden. Bei Treffern im Thesaurus würden überdies weitere Query

Objekte instanziert, mit welchen jeweils eine Suchabfrage auf dem Index ausgeführt werden

müsste. Ferner lässt diese Alternative keine Suche nach Wortphrasen zu. Werden Synonyme

und Oberbegriffe direkt zu einem Begriff im Index gespeichert, so hat dies keine wesentlichen

Auswirkungen auf die Performance von Suchabfragen. Der Nachteil dieser Lösung ist, dass

67

der Index neu erstellt bzw. aktualisiert werden muss, wenn Änderungen in der Thesaurusdatei

vorgenommen wurden. Da die Performance der Suchsoftware von hoher Bedeutung ist und

Änderungen der Thesaurusdatei und die damit verbundenen Nachteile eher selten auftreten,

wurde die zweite Alternative implementiert.

Um den Thesaurus in der Suchsoftware zu integrieren, mussten Adapterklassen für Lucene

geschrieben werden. Bei einer Indexierung werden die Produktdaten durch die Klasse

ThesaurusAnalyzer geschickt. Der Analyzer greift über die Klasse ThesaurusEngine auf den

Thesaurus zu und fügt den analysierten Wörtern Synonyme und Oberbegriffe hinzu.

6.4.2 SearchRequestLogger

Für die Protokollierung von Suchanfragen wurde die Klasse SearchRequestLogger

implementiert. Um Suchanfragen zu protokollieren, muss der Pfad der Protokollierungsdatei

über den Konstruktor oder in der Methode setLogFilePath(String logFilePath) gesetzt werden.

Mit der Methode addLogMessage können anschließend Suchanfragen protokolliert werden.

Bei auftretenden Fehlern wirft die Methode eine LoggerException, die den Grund des Fehlers

enthält. Eine Exception wird zum Beispiel geworfen, wenn der Parameter searchItem null ist,

sich die übergebene IP Adresse in einem falschen Format befindet usw.

Wird die Suchsoftware in ein System eingebunden, so ist es nicht nötig, die Klasse

SearchRequestLogger direkt zu instanzieren. Stattdessen muss lediglich in der Klasse

Searcher der Pfad der Protokolierungsdatei in der Methode setLoggerPath(String path)

gesetzt werden. Wurde ein gültiger Pfad gesetzt, werden sämtliche Anfragen von der

Suchsoftware automatisch mitprotokolliert. Der Entwickler braucht sich somit nicht weiter

um die Instanzierung und Übergabe der richtigen Parameter kümmern.

6.4.3 Phonetische Suche

Die phonetische Suchfunktion wurde mithilfe der Bibliothek Phonetix der Firma tangentum

technologies realisiert. Für die Integration der Suchfunktion standen bereits Adapterklassen

wie zum Beispiel eine PhoneticAnalyzer Klasse zur Verfügung. Bei einer phonetischen

Suchabfrage wird die gesuchte Zeichenkette an die PhoneticAnalyzer Klasse übergeben.

Diese greift auf die Klasse DoubleMetaphone zu, die aus der Zeichenkette einen Code

68

erzeugt, welcher anschließend im Index gesucht wird. Damit eine phonetische Suche möglich

ist, muss bereits bei der Indexierung der Parameter phoneticFlag, im Konstruktor der Klasse

Index, auf true gesetzt werden. Da sich die phonetische Suche negativ auf die Größe des

Index auswirkt, ist sie standardmäßig deaktiviert. Die Indexierung einer Produktdatei mit

einer Größe von 2,10 MB ergab einen 3,62 MB großen Index. Durch eine erneute Indexierung

mit aktiver phonetischer Indexierung wurde ein 6,89 MB großer Index erstellt. Dies entspricht

einer Zunahme der Indexgröße um 90,3 %.

Phonetische Suchabfragen werden durchgeführt, wenn zum einen phontische Codes indexiert

wurden und zum anderen der Parameter phonticFlag der Methode setPhoneticFlag in der

Klasse Searcher auf den Wert 0 bzw. 1 gesetzt wurde. Da Variabelnamen aussagekräftiger

sind, wurden die statischen Variablen PHONETICSEARCHON mit dem Wert 0,

PHONETICSEARCHIFNOPRODUCTFOUND mit dem Wert 1 und PHONETICSEARCHOFF

mit dem Wert 2 in der Klasse Searcher definiert.

6.4.4 Fehlertolerante Suchfunktion

Für fehlertolerantes Suchen stellt Lucene die Klasse FuzzyQuery bereit. Da es mit dieser

Klasse jedoch nicht möglich ist eine fehlertolerante Suche in Teilzeichenketten

durchzuführen, wurde für den Prototyp die Klasse ASQuery implementiert. Die eigentliche

Implementierung des Suchalgorithmus liegt jedoch in der Klasse ASTermEnum, welche von

der Klasse ASQuery verwendet wird. Für die Berechnung der Editierdistanz wurde

ursprünglich der Shift-And Algorithmus (siehe Kapitel 2) implementiert. Zudem wurde für

einen Vergleich ein modifizierter Levenshtein Algorithmus (siehe Kapitel 2), der die

erweiterte Editierdistanz berechnet und Suchabfragen in Teilzeichenketten durchführt,

implementiert. Der Vergleich der beiden Implementierungen zeigte, dass die Implementierung

des Levenshtein Algorithmus in der Regel gleich schnell wie die Implementierung des Shift-

And Algorithmus ist. Dies überrascht, da der Shift-And Algorithmus, mit einer theoretischen

Laufzeitkomplexität von O(k⌈m/w⌉, bei weitem schneller sein sollte als der Levenshtein

Algorithmus, der eine Laufzeitkomplexität von O(mn) aufweist. Warum der Shift-And

Algorithmus in diesem Fall nicht schneller als der Levenshtein Algorithmus ist, kann unter

anderem mit dem Aufbau des Suchframeworks begründet werden. Bei einer Suchabfrage wird

der Algorithmus für jedes im Text vorkommende Wort aufgerufen. Der Levenshtein

Algorithmus hat durch diesen Programmablauf keinen Nachteil, da er ohnehin für jeden

Vergleich zweier Zeichenketten einen neuen Array anlegt und in diesem die Editierdistanz

69

berechnet. Der Shift-And Algorithmus hingegen zielt darauf, Treffer in einem Fliesstext zu

finden. Da das Framework jedoch so aufgebaut ist, dass es immer nur ein Wort und nicht den

gesamten Text liefert, kann der Shift-And Algorithmus diesen Vorteil nicht ausnutzen.

private final int editDistance(String s, String t, int n, int m) {

if (e.length <= n || e[0].length <= m) {

e = new int[Math.max(e.length, n+1)][Math.max(e[0].length, m+1)];

}

int d[][] = e; // Arrray zur Berechnung der Editierdistanz

int i; // durchläuft die Zeichenkette s

int j; // durchläuft die Zeichenkette t

char s_i; // das i Zeichen der Zeichenkette s

int min = 1000; // Initialisierung der Editierdistanz

if (n == 0) return m;

if (m == 0) return n;

// Initialisierung des Arrays

for (i = 0; i <= n; i++) d[i][0] = i;

for (j = 0; j <= m; j++) d[0][j] = 0; //Initialisierung mit 0 um

//fehlertolerant in

//Teilzeichenketten zu Suchen

// Beginn der Berechnung

for (i = 1; i <= n; i++) {

s_i = s.charAt(i - 1);

for (j = 1; j <= m; j++) {

if (s_i != t.charAt(j-1))

if (i>1 && j>1) {

//Buchstabendreher

if (s.charAt(i-2)==t.charAt(j-1) &&

s.charAt(i-1)==t.charAt(j-2)) {

d[i][j] = min(d[i-1][j], d[i][j-1], d[i-1][j-1],

d[i-2][j-2])+1;

}

else {

d[i][j] = min(d[i-1][j], d[i][j-1],

d[i-1][j-1])+1;

}

}

else {

70

d[i][j] = min(d[i-1][j], d[i][j-1], d[i-1][j-1])+1;

}

//zwei gleiche Zeichen

else d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]);

//ermittle den niedrigsten Wert der letzten Reihe im Array

if (i==n && d[i][j]<min) min=d[i][j];

}

}

//die berechnete Editierdistanz

return min;

}

Codebeispiel 8 Modifizierter Levenshtein Algorithmus

Fehlertolerante Suchabfragen können durch einen Aufruf der Methode search bzw

searchWithRange der Klasse Searcher durchgeführt werden. Durch setzten des Parameters

similarity mittels der Methode setMinimumSimilarity kann der minimale

Ähnlichkeitkoeffizient, welcher zwischen 0 und 1 liegen muss, definiert werden.

Standardmäßig beträgt der minimale Ähnlichkeitskoeffizient 0,8.

6.4.5 QueryParser

Die Klasse QueryParser wird von der Klasse Searcher für das Parsen von Suchausdrücken

verwendet. Die Methode parse(String query, String field, Analyzer analyzer) der Klasse

QueryParser erstellt aus der gesuchten Zeichenkette ein Query Objekt, das für die Suche an

eine Instanz der Klasse IndexSearcher übergeben wird. Lucene’s QueryParser Klasse würde

aus der Suchabfrage Sony Fernseher, für jedes Wort eine TermQuery generieren und diese

mittels einer BooleanQuery verknüpfen. Da TermQuery Objekte für exaktes Suchen

verwendet werden, musste die Klasse QueryParser dahingehend erweitert werden, dass sie

standardmäßig anstelle von TermQuery, ASQuery Objekte erstellt. Zudem wurde die Methode

parse mit den zusätzlichen Parametern exactFlag und phoneticFlag überladen. Durch setzen

des Parameters exactFlag auf true wird für den Suchbegriff eine TermQuery erstellt, welche

nach einer exakten Übereinstimmung im Text sucht. Um eine phonetische Suche

durchzuführen, muss der Parameter phoneticFlag auf true gesetzt werden. Phonetische

Suchabfragen können jedoch nur Ergebnisse liefern wenn bereits bei der Indexierung

angegeben wurde, dass für sämtliche Wörter phonetische Codes erstellt werden sollen.

71

6.4.6 Angabe von Wertebereichen

Für Abfragen mit definierten Wertebereichen, stellt Lucene die Klasse RangeQuery bereit.

Diese Klasse führt lexikographische Vergleiche durch, da Lucene intern mit Zeichenketten

arbeitet. Es ist daher nicht vorgesehen, Grenzen für Zahlen zu definieren. Angenommen der

Index enthält drei Produkte mit den Preisen 11, 60, 201 und es werden Produkte mit Preisen

größer gleich 10 und kleiner gleich 55 gesucht, so würden mithilfe der Klasse RangeQuery,

die Produkte mit den Preisen 11 und 201, ermittelt. Um eine Einschränkung von

Wertebereichen zu ermöglichen legt die für den Prototyp implementierte Klasse Indexer für

jedes Feld, das genau eine Zahl beinhaltet, ein weiteres Feld an. In diesem Feld wird die Zahl

zusätzlich im Format DDDDDDD,DDDD gespeichert. Wird die Methode searchWithRange

der Searcher Klasse aufgerufen, so werden die Parameter minimumValue und maximumValue

an das erwähnte Zahlenformat angepasst und an die Klasse RangeQuery übergeben. Der Wert

55 würde zum Beispiel in die Zeichenkette 0000055,0000 konvertiert. Ein lexikographischer

Vergleich stellt somit kein Problem mehr da. Es muss jedoch beachtet werden, dass ein

Vergleich nur bis maximal 9999999,9999 möglich ist und nur die ersten 4 Kommastellen

miteinander verglichen werden. Für Online-Shops sollte dies jedoch ausreichend sein.

6.5 Beispielapplikation

Der Zweck der Beispielapplikation besteht darin, den Einsatz des Prototyps unter

Verwendung realer Produktdaten zu zeigen. Einerseits wird gezeigt, dass sich der Prototyp

leicht in einen Onlineshop einsetzen und konfigurieren lässt und andererseits kann durch die

Applikation eine bessere Aussage über den Nutzen der Software gemacht werden.

Für die Beispielapplikation wurden neben der fehlertoleranten Suchsoftware das

Webapplikationsframework Struts und die Bibliothek Log4J verwendet.

Um realistische Rahmenbedingungen zu schaffen wurden Produktdaten eines Onlineshops,

mithilfe eines Webcrawlers, ermittelt und in einer Textdatei gespeichert. Die Textdatei enthält

insgesamt 7152 Produkte.

72

1547|SONY Memory-Card|für Playstation 2. 8 MB unkommprimiert. |Technik|29,99

1327|Gürtel|aus echtem Leder. Gesteppte Nähte. Breite ca. 3 cm. |Mode|9,99

Abbildung 26 Auszug der Textdatei

Alle Produkte beinhalten die Felder ArtikelID, Bezeichnung, Beschreibung, Kategorie sowie

Preis.

//erstelle Index mit phonetischen Codes (2. Parameter=true)

Index index = new Indexer(indexPath, true, thesaurusFilePath);

//Textdatei mit Produktdaten wird zeilenweise durchlaufen

while ((productData = bufferedReader.readLine()) != null) {

String[] productArray = productData.split("[|]");

if (productArray.length >= 5 ) {

artikelID = productArray[0];

bezeichnung = productArray[1];

beschreibung = productArray[2];

kategorie = productArray[3];

//ersetze Beistrich im Preis durch einen Punkt

preis = productArray[4].replace(",",".");

Document doc = new Document();

doc.add(Field.Keyword("articleID", artikelID));

doc.add(Field.Text("title", bezeichnung));

doc.add(Field.Text("description", beschreibung));

doc.add(Field.Text("category", kategorie));

doc.add(Field.Keyword("price", preis));

index.addDocument(doc);

}

}

index.createIndex();

Codebeispiel 9 Code für die Erstellung des Index

Auf Grundlage der vorhin beschriebenen Textdatei wurde der Index erstellt. Im Codebeispiel

wird zuerst eine Instanz der Klasse Index mit dem Konstruktor Indexer(String path, boolean

phoneticFlag, String thesaurusFilePath) angelegt. Diesem werden durch die Methode

addDocument(Document document) alle in der Textdatei befindlichen Produkte in Form von

Document Objekten hinzugefügt. Nachdem das Index Objekt mit allen Produkten befüllt

wurde, wird der Index mit der Methode createIndex() im Pfad indexPath erstellt.

73

searcher = new Searcher(config.get("index.path"));

searcher.setLoggerPath(config.get("searchRequestLogger.path"));

searcher.setPhoneticSearch(config.getInt("search.phonetic",

Searcher.PHONETICSEARCHOFF));

searcher.setMinimumSimilarity(config.getFloat("search.minimumSimilarity",

0.80f));

Codebeispiel 10 Initialisierung und Festlegung der Parameter der Suchkomponente

In Codebeispiel 10 wird gezeigt, wie die Suchkomponente in der Beispielapplikation

initialisiert und konfiguriert wird. In der ersten Zeile wird eine Instanz der Klasse Searcher

angelegt. Die Variable config ist eine Instanz der Klasse Configuration. Diese Klasse liest

beim Start der Webapplikation eine Configurationsdatei ein, welche aus Schlüsselwörtern und

zugeordneten Werten besteht. Die Methode get liefert den Wert eines Schlüsselwortes in der

Configurationsdatei.

search.minimumSimilarity = 0.80f

search.phonetic = 0

searchRequestLogger.path = C:/Programme/searchExample/logFile.txt

index.path = C:/Programme/searchExample/index/

Codebeispiel 11 Auszug der Configurationsdatei

Zum Beispiel wird durch den Aufruf get("index.path") der Pfad, in dem sich der Index

befindet, in Form eines Strings zurückgeliefert. Die Klasse Searcher lädt den Index in den

Hauptspeicher und kann ab diesem Zeitpunkt für Suchabfragen genutzt werden. In den

darunter liegenden Zeilen wird der Pfad der Protokollierungsdatei gesetzt, die phonetische

Suche ausgeschaltet und die minimale Ähnlichkeit zwischen Suchabfrage und

Suchergebnissen definiert.

hits = searcher.search(productTitle, "title", request.getRemoteAddr());

if (hits.length() > 0) {

for (int i = start; i <= end; i++) {

Product product = new Product();

product.setProductTitle(hits.doc(i).get("title"));

product.setProductDescription(hits.doc(i).get("description"));

product.setCategory(hits.doc(i).get("category"));

product.setPrice(hits.doc(i).get("price"));

74

product.setArticleID(hits.doc(i).get("articleID"));

//add product into array list

products.add(product);

}

}

Codebeispiel 12 Suchabfrage mit der Methode search welche ein Hits Objekt liefert

Codebeispiel 12 zeigt die Implementierung einer einfachen Suchabfrage. Die Variable

productTitle enthält den gesuchten Begriff. Die Zeichenkette title bezeichnet das Feld,

welches im Index durchsucht werden soll. Im dritten Parameter wird die IP-Adresse des

Clients übermittelt, welche zusammen mit der Suchabfrage und der Anzahl der gefundenen

Treffer in der definierten Protokolldatei gespeichert wird. Das von der Methode search

zurückgelieferte Hits Objekt enthält alle gefundenen Treffer. Auf die Suchergebnisse wird mit

der Methode doc zugegriffen. Diese Methode liefert ein einzelnes Suchergebnis in Form eines

Document Objekts. Der Zugriff auf die Werte des Document Objekts erfolgt durch Übergabe

des Feldnamens in der Methode get. Im Codebeispiel werden die Werte des Suchergebnisses

in das Hilfsobjekt der Klasse Product gespeichert und dieses einer ArrayList hinzugefügt.

<c:forEach var="product" items="${searchForm.result}" begin="0" end="${searchForm.maxResultsPerPage}" step="1"> <tr> <td> <html-el:link action="/ProductDetail.do? productTitle=${searchForm.productTitle}& articleID=${product.articleID}"> <c:out value="${product.productTitle}"/> </html-el:link> </td> <td> <c:out value="${product.price}"/> € </td> </tr> <tr> <td><img src="images/spacer.gif" height="20"></td> </tr></c:forEach>

Codebeispiel 13 Ausgabe des Suchergebnisses

Auf der Ausgabeseite der Webapplikation wird das ArrayList Objekt durchlaufen und die

Werte der Suchergebnisse ausgegeben.

75

Abbildung 27 zeigt eine Ergebnisseite der Beispielapplikation

Abbildung 27 zeigt ein nach dem Preis absteigend sortiertes Suchergebnis. Da in der

Thesaurusdatei die Begriffe TV und Fernseher als Synonym definiert wurden enthält das

Ergebnis auch Treffer mit dem Begriff TV.

Neben den nachfolgenden Last- und Performancetests wurden zahlreiche Suchabfragen

durchgeführt um die Qualität der Suchergebnisse zu prüfen. Die Aktivierung der phonetischen

Suche brachte eine Qualitätsverschlechterung des Suchergebnisses, da durch sie zwar

zusätzliche, jedoch unpassende Produkte gefunden wurden. Durch den Einsatz des Thesaurus

konnte die Treffsicherheit der Suchsoftware großteils gesteigert werden. So fand die Software

bei einer Suchabfrage nach Hose auch Treffer wie HIS Jeans „Sunny“, EXPLORER Jeans

76

usw. Ohne den Einsatz eines Thesaurus wären dem Benutzer solche Treffer entgangen. Es

zeigte sich aber auch, dass durch den Thesaurus auch unerwünschte Treffer in das

Suchergebnis einfließen können. So enthielt die Suchabfrage nach Hose, auch ein Produkt mit

der Bezeichnung H.I.S. Jeansjacke im Suchergebnis, da in der Thesaurusdatei Hose als

Oberbegriff von Jeans definiert wurde. Werden der Thesaurusdatei Einträge hinzugefügt, so

sollten diese immer mit anschließenden Suchabfragen getestet werden, um sicherzugehen,

dass diese das Suchergebnis nicht negativ beeinflussen.

Abfragen mit verschieden hoher Mindestähnlichkeit ergaben, dass diese zwischen 75 und 85

Prozent liegen sollte. Wird die Mindestähnlichkeit zu hoch gesetzt, so werden Fehler nur bei

sehr langen Zeichenketten toleriert, wird sie jedoch zu niedrig gesetzt, so werden auch

unerwünschte Produkte gefunden. Mit einer Mindestähnlichkeit von 80 Prozent wurden zum

Beispiel bei einer Suchabfrage mit dem relativ kurzen Begriff Hosn auch noch Produkte mit

der Bezeichnung Hosen gefunden. Unerwünschte Treffer im Suchergebnis blieben bei einer

Mindestähnlichkeit von 80 Prozent aus. Der eingesetzte approximative Suchalgorithmus trägt

somit wesentlich zur Qualitätsverbesserung des Suchergebnisses bei, sofern die

Mindestähnlichkeit im Bereich von 75 bis 85 Prozent liegt.

6.6 Last- und Performancetests

Sämtliche Last- und Performancetests wurden auf einem Webapplikationsserver mit 512 MB

Hauptspeicher und 1,53 GHz, mit dem Werkzeug JMeter durchgeführt. Als Betriebssystem

kam WindowsXP und als Webapplikationscontainer Apache Tomcat zum Einsatz. JMeter

wurde so konfiguriert, dass 10 gleichzeitige Suchabfragen ausgeführt und jede Abfrage 100-

mal durchgeführt wird. Pro Testdurchlauf wurden daher insgesamt 1000 = (10 x 100)

Suchabfragen an das System gestellt. Die Anlaufzeit wurde mit 5 Sekunden festgelegt.

Die grüne Linie in den Lasttestdiagrammen gibt den Durchsatz/Minute an. Der Durchsatz

drückt die Anzahl der Suchabfragen aus, die von der Beispielapplikation innerhalb einer

Minute verarbeitet werden können. Die blaue Linie stellt die durchschnittliche Dauer dar,

welche eine einzelne Suchabfrage benötigt wird.

77

Abbildung 28 Einfache Suche nach dem Begriff Hose

Abbildung 28 zeigt das Lasttestergebnis einer Suchabfrage mit dem Begriff Hose. Im

Durchschnitt wurde eine Suchabfrage in 10 Millisekunden durchgeführt.

Abbildung 29 Einfache Suche nach dem Begriff Microsoft Keyboard

Im Vergleich zu Abbildung 28 ist in Abbildung 29 zu sehen, dass eine Suchabfrage mit

mehreren und längeren Zeichenketten eine entsprechend höhere Laufzeit hat. Dennoch ist

eine Antwortzeit von durchschnittlich 31 Millisekunden als sehr gut zu bezeichnen.

78

Abbildung 30 Erweiterte Suche nach dem Begriff Hose

Die Grafik in Abbildung 30 zeigt ein Lasttestergebnis in welchem eine erweiterte

Suchabfrage mit dem Begriff Hose ausgeführt wurde. Neben dem gesuchten Begriff wurde

festgelegt, dass der Preis der Produkte größer gleich 10 Euro und kleiner gleich 30 Euro sein

muss und nur Produkte angezeigt werden sollen, die sich in der Kategorie Mode befinden.

Abbildung 31 Suche nach dem Begriff Hose mit zusätzlicher phonetischer Suche

Eine Aktivierung der phonetischen Suche hat nur minimale Auswirkungen auf die Suchdauer,

wie in Abbildung 31 zu sehen ist. Dies liegt daran das phonetische Codes bereits bei der

Indexierung berechnet werden, die Codes sehr kurz sind und phonetische Suchabfragen einen

exakten Vergleich durchführen.

Zusammenfassend kann gesagt werden, dass die Performance des Prototyps für kleine und

mittelgroße Onlineshops ausreichend schnell ist. Die Tests zeigten, dass die Antwortzeit des

79

Prototyps, selbst bei 10 gleichzeitigen Suchabfragen, im Durchschnitt unter 40ms liegt. Pro

Minute könnten somit theoretisch über 5000 Suchabfragen durchgeführt werden.

Der verwendete Index wurde auf Grundlage von ca. 7000 Produktdaten erstellt. Dies

entspricht dem Produktsortiment eines mittelgroßen Onlinehops. Leider war es nicht möglich

das Laufzeitverhalten des Prototyps unter Verwendung einer sehr großen Anzahl von

Produktdaten zu messen. Von der Möglichkeit, vorhandene Produktdaten zu duplizieren oder

Produktdaten zufällig zu generieren wurde abgesehen, da dies Last- und Performancetests

verfälschen würde.

Da die Antwortzeiten in der Beispielapplikation sehr niedrig sind und der Index nur sublinear

zur Größe der Produktdaten anwächst, sollte es für den Prototyp grundsätzlich möglich sein,

Suchabfragen auf große Indizes, mit zum Beispiel 500.000 Produktdaten, innerhalb einer

Sekunde, durchzuführen. Eine definitive Aussage über die Skalierbarkeit kann jedoch nicht

gegeben werden.

80

7 Zusammenfassung und Ausblick

Diese Arbeit hat einen Überblick über aktuelle fehlertolerante Suchalgorithmen und Indizes

gegeben, deren Vor- und Nachteile herausgearbeitet und sie hinsichtlich eines Einsatzes in

einer fehlertoleranten Suchsoftware geprüft. Zudem wurden Anforderungen für eine

fehlertolerante Suchsoftware erhoben, welche neben einer fehlertolerante Suchfunktion

zusätzliche Komponenten, wie zum Beispiel eine Thesaurus- und eine

Protokollierungskomponente, umfassen.

Der Prototyp wurde auf Basis des Suchframeworks Lucene implementiert. Da der Index des

Frameworks speicherschonend und einfach zu verwalten ist, wurde er für den Prototyp

unverändert übernommen. Der fehlertolerante Suchalgorithmus musste jedoch für die

Berechnung der erweiterten Editierdistanz und für fehlertolerantes Suchen in

Teilzeichenketten modifiziert bzw. erweitert werden. Der Prototyp verfügt weiters über

phonetische und exakte Suchfunktionen, einer Sortierfunktion, einer Thesaurus- und einer

Protokollierungskomponente.

Abschließend wurde anhand einer Beispielapplikation der Einsatz des Prototyps gezeigt und

mit Hilfe des Werkzeuges JMeter Last- und Stresstests durchgeführt. Diese zeigten, dass die

im Kapitel Anforderungen definierte maximale Antwortzeit von der Software eingehalten

wird.

Das Ergebnis dieser Arbeit ist ein lauffähiger Prototyp, der als Suchsoftware für Online-Shops

eingesetzt werden kann. Dennoch gibt es eine Reihe von Verbesserungsmöglichkeiten und

Funktionalitäten, die im Rahmen dieser Diplomarbeit nicht realisiert wurden.

So würde zum Beispiel der Einsatz eines zusätzlichen Q-Gramm/N-Gramm Algorithmus die

Qualität der Suchergebnisse weiter verbessern, da damit auch Wortvariationen wie zum

Beispiel Druckerkabel und Kabel für Drucker gefunden werden. Weiteres wäre eine

Anpassung des phonetischen Algorithmus auf Grundlage deutscher Ausspracheregeln

wünschenswert, da der eingesetzte DoubleMetaphone Algorithmus für die englische Sprache

entwickelt wurde.

Auch die Implementierung einer Funktion zur Berechnung einer relativen Mindestähnlichkeit

wäre nützlich. Eine relative Mindestähnlichkeit ist vom besten Treffer des Suchergebnisses

81

abhängig und wird durch die Formel Ähnlichkeit des besten Treffers * (Parameter/100) berechnet.

Durch die Implementierung einer Funktion zur Berechnung der relativen Mindestähnlichkeit

könnte die Ergebnisliste auf die wesentlichsten Treffer beschränkt werden.

Eine Herausforderung für die Zukunft stellt die Implementierung der beschriebenen

Funktionen dar. Zudem gilt es die Entwicklung des Suchmaschinenmarktes zu beobachten

sowie neu erscheinende, wissenschaftliche Arbeiten zu evaluieren und gegebenenfalls deren

Erkenntnisse in die Suchsoftware einzuarbeiten.

82

Danksagung

Abschließend möchte ich mich bei meinen Eltern bedanken, die mein Studium in jeder

Hinsicht unterstützt haben.

Insbesondere möchte ich mich bei a. Univ.-Prof. Mag. Dr. Reinhold Plösch, für die

hervorragende Betreuung dieser Diplomarbeit, bedanken.

Ein besonderer Dank gilt auch meinen Freunden und Studienkollegen für Ihre Hilfe und

Unterstützung während des Studiums und dem Schreiben dieser Diplomarbeit.

83

Abbildungsverzeichnis

Abbildung 1 deterministischer und nichtdeterministischer finiter Automat.............................15

Abbildung 2 NFA für den Suchbegriff Pulower mit maximal zwei Fehlern...........................15

Abbildung 3 NFA für die exakte Suche nach DISC.................................................................17

Abbildung 4 Text und der dazugehörige invertierte Index.......................................................26

Abbildung 5 Heaps’ Law [Answ05].........................................................................................27

Abbildung 6 Trie.......................................................................................................................28

Abbildung 7 Implementierungsmöglichkeiten eines Tries.......................................................29

Abbildung 8 Patricia Trie..........................................................................................................30

Abbildung 9 Suffix-Trie...........................................................................................................32

Abbildung 10 Suffix-Tree.........................................................................................................33

Abbildung 11 Suffix-Array.......................................................................................................34

Abbildung 12 Beispiel Suffix-Array.........................................................................................34

Abbildung 13 DTD einer Thesaurusdatei.................................................................................42

Abbildung 14 Beispiel einer Thesaurusdatei............................................................................42

Abbildung 15 Syntax der Logdatei...........................................................................................43

Abbildung 16 Beispiel einer Logdatei......................................................................................43

Abbildung 17 Programmablauf der Indexierung und Suche in Lucene [RiAv04]...................48

Abbildung 18 Lucene Index Diagram [Cutt00]........................................................................49

Abbildung 19 Konzeptionelle Darstellung einer Build Datei [HaLo03]..................................58

Abbildung 20 Umsetzung des Model 2 Konzeptes in Struts [IBM05].....................................61

Abbildung 21 JMeter Benutzeroberfläche................................................................................62

Abbildung 22 Architektur der Suchsoftware............................................................................63

Abbildung 23 architektureller Überblick der Indexkomponente..............................................64

Abbildung 24 architektureller Überblick der Suchkomponente...............................................65

Abbildung 25 zeigt Struktur und Aufbau des Thesaurus..........................................................67

Abbildung 26 Auszug der Textdatei.........................................................................................73

Abbildung 27 zeigt eine Ergebnisseite der Beispielapplikation...............................................76

Abbildung 28 Einfache Suche nach dem Begriff Hose............................................................78

Abbildung 29 Einfache Suche nach dem Begriff Microsoft Keyboard....................................78

Abbildung 30 Erweiterte Suche nach dem Begriff Hose..........................................................79

Abbildung 31 Suche nach dem Begriff Hose mit zusätzlicher phonetischer Suche.................79

84

Literaturverzeichnis

[Answ05] Answers.com, Heaps’ law, http://www.answers.com/topic/heaps-law, Abruf am 2005-04-05.

[Ant05] Apache Ant, http://ant.apache.org, Abruf am 2005-05-11

[Apac05] Apache Software License, Version 2.0, Jänner 2004, Abruf am 2005-04-06

[BaNa04] Baeza-Yates, Ricardo A.; Navarro, Gonzalo: Text Searching: Theory and Practice, Formal Languages and Applications, Springer, Seite 565-597, 2004

[BaNe99] Baeza-Yates, Ricardo A.; Ribeiro-Neto, Berthier: Modern Information Retrieval. ACM Press / Addison-Wesley, 1999

[BaYa92] Baeza-Yates, Ricardo; Gonnet Gaston H.: A new approach to text searching. Communications of the ACM 35(10), S. 74-82, 1992

[BaYa91] Baeza-Yates, Ricardo.: Some new results on approximate string matching. In Workshop on Data Structures, 1991

[Brian59] de la Briandais, Renee: File Searching Using Variable Length Keys. Proceedings of the Western Joint Computer Conference, 1959

[Cutt00] Cutting, Doug: The Lucene Search Engine, Inktomi Seminar, 16 Juni 2000, http://lucene.sourceforge.net/talks/inktomi, Abruf am 2005-04-07

[Egot05] Egothor, http://www.egothor.org, Abruf am 2005-04-06

[Fred60] Fredkin, Edward: Trie Memory, Communications of the ACM, 3(9), Seite 490-499, 1960

[Gadd90] Gadd, T.N.: PHONIX: The Algorithm, 24(4), S. 363, 1990

[Gadd88] Gadd, T. N.: “Fisching fore werds”: phonetic retrieval of written text in information systems. 22(3), S. 222, 1988

[GaHe95] Gamma Erich, Helm Richard, Johnson Ralph, Vlissides John: Design Patterns, Elements of Reusable Object-Oriented Software, Addison Wesley, 1995

[Gieg99] Giegerich, Robert; Kurtz, Stefan; Stoye, Jens: Efficient implementation of lazy suffix trees. In Proc. 3rd Workshop on Algorithm Engineering, Lecture Notes In Computer Science 1668, Seite 30-42, 1999

[GNU05] GNU Lesser General Public License, http://www.gnu.org/copyleft/lesser.html, Abruf

am 2005-05-18

[GoHa04] Otis, Gospodnetić; Hatcher, Erik: Lucene in Action, Manning Publications, 2004

[Gonn87] Gonnet, Gaston H..: PAT 3.1: An efficient text searching system, User’s manual. UW Centre for the New OED, University of Waterloo, 1987

[GrPa01] Gravano, Luis; Ipeirotis, Panagiotis G.; Jagadish, H. V.; Koudas, Nick; Muthukrishnan, S.; Pietarinen, Lauri; Srivastava, Divesh; Using q-grams in a DBMS for Approximate String Processing, IEEE Data Engineering Bulletin, 2001

85

http://www.gnu.org/copyleft/lesser.html

http://www.egothor.org/

http://lucene.sourceforge.net/talks/inktomi

http://ant.apache.org/

http://www.answers.com/topic/heaps-law

[Gülc04] Gülcü, Ceki: The Complete log4j Manual, 2004

[HaLo03] Hatcher, Erik; Loughran, Steve: Java Development with Ant, Manning Publications,

2003

[Heap78] Heaps, H. S.: Information Retrieval, Computational and Theoretical Aspects. Academic Press, 1978

[HoUl] Hopcroft, John E.; Ullman, Jeffrey D.: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979

[IBM05] IBM, Struts, an open-source MVC implementation,

http://www-106.ibm.com/developerworks/library/j-struts/?dwzone=java, Abruf am

2005-05-16

[IEEE90] Industry of Electrical and Electronics Engineers: IEEE Standard Glossary of

Software Engineering Terminology. IEEE Std.610.12-1990, The Institute of Electrical

and Electronic Engineers, New York, 1990.

[JMet05] Apache JMeter, http://jakarta.apache.org/jmeter, Abruf am 2005-05-17

[Juni05] JUnit, http://junit.sourceforge.net, Abruf am 2005-05-11

[Knut73] Knuth, Donald: The Art of Computer Programming 3: Sorting and Searching, Addison-Wesley-Verlag, 1973

[LaWa75] Lowrance, R.; Wagner, Robert A.: An Extension of the String-to-String Correction Problem. Journal of the ACM 22(2), S. 177-183, 1975

[Lawr90] Lawrence, Philips: “Hanging on the metaphone”. Computer Language Magazine 7(12), S. 38-44, Dezember 1990

[Lawr00] Lawrence, Philips: The Double-Metaphone Search Algorithm, C/C++ User’s Journal 18(6), Juni 2000

[Leve65] Levenshtein, Vladimir I.: Binary Codes capable of correcting spurious insertions and deletions of ones. Problems of Information Transmission 1(1), S. 8-17, 1965

[Leve66] Levenshtein, Vladimir. I.: Binary Codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady 10(8), S. 707-710, 1966

[Log05] Apache Log4J, http://logging.apache.org, Abruf am 2005-05-11

[Luce05] Apache Lucene, http://lucene.apache.org, Abruf am 2005-04-06

[MaMy93] Manber, Udi; Myers, Eugene W.: Suffix arrays: a new method for on-line string searches. SIAM Journal on Computing, 22(5), Seite 935-948, 1993

[Mass04] Massol, Vincent; Husted Ted: JUnit in Action. Manning Publications, 2004

86

http://lucene.apache.org/

http://logging.apache.org/

http://junit.sourceforge.net/

http://jakarta.apache.org/jmeter

http://www-106.ibm.com/developerworks/library/j-struts/?dwzone=java

[Mave05] Apache Maven, http://maven.apache.org, Abruf am 2005-05-11

[McCr76] McCreight, Edward M.: A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM, 23(2), Seite 262-272, 1976

[Morr68] Morrison, Donald R.: PATRICIA – Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM, 15(4), Seite 514-534, 1968

[Myers86] Myers, Eugene W.: Incremental alignment algorithms and their applications. Tech. Rep. TR86-22, Dept. of Computer Science, Univ. of Arizona, 1986

[NARA00] US National Archives and Records Administration: The Soundex Indexing System. http://www.archives.gov/research_room/genealogy/census/soundex.html, 2000-02-19, Abruf am 2004-11-05.

[Nava01] Navarro, Gonzalo: A Guided Tour to Approximate String Matching. ACM Computing Surveys 33(1), S. 31-88, 2001

[Nels96] Nelson, Mark: Fast String Searching With Suffix Trees, Dr. Dobb’s Journal, http://www.dogma.net/markn/articles/suffixt/suffixt.htm, 1996, Abruf am 2005-03-27.

[PfPo96] Pfeifer, Ulrich; Poersch, Thomas; Fuhr, Norbert: Retrieval Effectiveness of Proper Name Search Methods. Information Processing and Management, 1996

[Phon05] Phonetix, tangentum technologies,

http://www.tangentum.biz/en/products/phonetix/index.html, Abruf am 2005-04-25

[RiAv04] Richardson, Clay W.; Avondolio, Donald; Vitale, Joe; Len, Peter; Smith, Kevin T.: Professional Portal Development with Open Source Tools: JavaTM Portlet API, Lucene, James, Slide. Wrox, 2004

[Sedg92] Sedgewick, Robert: Algorithmen, Addision-Wesley, 1992

[Somm00] Sommerville, Ian: Software Engineering. Addison-Whesley, 6. Auflage, 2000.

[Strut05] Apache Struts, http://struts.apache.org, Abruf am 2005-05-11

[Szyp98] Szyperski, Clemens: Component Software – Beyon Object-Oriented Programming.

Addison-Wesley, 1998

[Ukko92a] Ukkonen, Esko: Approximate string-matching with g-grams and maximal matches. Theoretical Computer Science, 92, S. 191-211, 1992

[Ukko92b] Ukkonen, Esko: Constructing Suffix-trees On-Line in Linear Time. Algorithms, Software, Architecutre: Information Processing, 1(92), Seite 484-492

[Ukko95] Ukkonen, Esko: On-line Construction of Suffix Trees. Algorithmica, 14(3), Seite 249-260, 1995

[Ukko85] Ukkonen, Esko: Finding approximate patterns in strings. Journal of Algorithms6(1-3), S. 132-137, 1985

[Wein73] Weiner, P.: Linear pattern matching algorithms. In Proceedings of IEEE Symposium on Switching and Automata Theory, Seite 1-11, 1973

[Wiki05a] Wikipedia - Die freie Enzyklopädie, http://de.wikipedia.org/wiki/Thesaurus, Abruf am

27.01.05.

87

http://de.wikipedia.org/wiki/Thesaurus

http://struts.apache.org/

http://www.tangentum.biz/en/products/phonetix/index.html

http://maven.apache.org/

[Wiki05b] Wikipedia, Log4J, http://de.wikipedia.org/wiki/Log4J, Abruf am 2005-05-16

[WuMa92] Wu, Sun; Manber, Udi: Fast text searching allowing errors. Communications of the ACM 35(10), S. 83-91, 1992

[Xerc05] Apache Xerces2 Java Parser, http://xml.apache.org/xerces2-j, Abruf am 2005-05-11

[ZoDa95] Zobel, Justin; Dart, Philip: Finding Approximate Matches in Large Lexicons. Software – Practice and Experience, 25(3), S. 331-345, 1995

88

http://xml.apache.org/xerces2-j

http://de.wikipedia.org/wiki/Log4J