Entwicklung eines Suchalgorithmus für das Information Retrieval

Inhaltsverzeichnis

1 Einleitung

2 Einführung in Algorithmen
2.1 Algorithmus-Definition
2.2 Algorithmenanalyse
2.3 Klassifikation von Algorithmen
2.4 Optimieren von Algorithmen
2.5 Beispiele für die Optimierung von Algorithmen
2.5.1 Algorithmen-Optimierung auf semantischer Ebene
2.5.2 Algorithmen-Optimierung auf struktureller Ebene

3 Implementationen von Algorithmen
3.1 Sortieralgorithmen
3.1.1 Der Sortieralgorithmus Quicksort
3.1.2 Implementierung des Quicksort-Algorithmus
3.2 Schedulingalgorithmen
3.2.1 Der Round-Robin-Algorithmus (Prioritätsstufenbasiert)
3.2.2 Implementierung des prioritätenbasierten Round-Robin-Algorithmus
3.3 Suchalgorithmen
3.3.1 Der Suchalgorithmus nach Boyer-Moore
3.3.2 Implementierung des Boyer-Moore-Algorithmus

4 Suchalgorithmen für das Information Retrieval
4.1 Indexbasierte Suche vs. Online-Suche
4.2 Methoden von Suchalgorithmen für die Volltextsuche beim Information Retrieval
4.2.1 Methode des zu entwickelnden Suchalgorithmus für die Volltextsuche beim Information Retrieval
4.2.2 Implementierung des zu entwickelnden Suchalgorithmus für die Volltextsuche beim Information Retrieval

5 Quellenverzeichnis
5.1 Internet-Quellenverzeichnis
5.2 Literaturverzeichnis

6 Anlagenverzeichnis

Abbildungsverzeichnis

Abbildung 1 – Gegenüberstellung der Laufzeiten von quadratischen und kubischen Algorithmen

Abbildung 2 – Prozentuale Abweichung der Anzahl der Verarbeitungsschritte der Implementierungen

Abbildung 3 – Schaubild der Funktionsweise des Quicksort-Algorithmus

Abbildung 4 – Beispiel der Funktionsweise des Boyer-Moore Algorithmus

Tabellenverzeichnis

Tabelle 1 – Gegenüberstellung der Laufzeiten iterativer und rekursiver Algorithmen Algorithmus-Implementierungen

Implementierung 1 – equationValues (nicht-optimierte Version)

Implementierung 2 – equationValues (erste optimierte Version)

Implementierung 3 – equationValues (zweite optimierte Version)

Implementierung 4 – equationValues (endgültig optimierte Version)

Implementierung 5 – fibonacciRekursiv

Implementierung 6 – fibonacciIterativ

Implementierung 7 – quickSorter

Implementierung 8 – scheduler

Implementierung 9 – patternMatching

1 Einleitung

Diese Seminararbeit beschäftigt sich mit dem Thema der Algorithmen für die Anwendung in der Informatik, im Speziellen mit Suchalgorithmen für Textvergleiche im Rahmen des Information Retrieval.

Durch die rasante Entwicklung und Verbreitung der Informationstechnologie, vor allem im Bereich der Massenspeicher und der weltweit geschaffenen Kommunikationsinfrastruktur des Internets, ist die Menge an direkt oder indirekt zugänglichem Wissen überproportional gestiegen.^[1] Um von der stetig wachsenden Anzahl an verfügbaren Informationen in den Wissensdatenbanken zu profitieren, besteht die Notwendigkeit die verfügbaren Datenbestände in geeigneter Form verwalten und die gewünschten Informationen kontextbezogen schnell wieder finden zu können. Daher müssen die Datenbestände systematisch und schnell durchsucht werden, wofür unterschiedliche Algorithmen zum Einsatz kommen.

Um den Leser zuerst in die Thematik einzuführen, wird vorab das Gebiet der Algorithmen im Allgemeinen aufgearbeitet. Im Rahmen des folgenden Kapitels sollen daher die grundlegenden Kenntnisse und Methoden vermittelt und so eine gemeinsame Wissensbasis für das Verständnis der Implementierung des zu entwickelnden Suchalgorithmus zur Bestimmung der Affinität von Texten geschaffen werden.

Anschließend werden einige Ansätze von für das Information Retrieval geeignete Suchalgorithmen diskutiert und letztlich die Implementierung des zu entwickelnden Suchalgorithmus vorgestellt.

2 Einführung in Algorithmen

Ziel dieses Abschnitts ist es, dem Leser einen kurzen Überblick in die verschiedenen Paradigmen von Computer-Algorithmen sowie deren Funktionsweise und Verwendung zu geben.

Zur Aufarbeitung der Thematik bedient sich diese Arbeit dabei vor allem zweier Standardwerke im Bereich der algorithmischen Computerprogrammierung. Dies ist zum einen das für eine Vielzahl verschiedener Programmiersprachen veröffentlichte Buch „Alogrithmen in C“ von Robert Sedgewick, das aufgrund seines Lehrbuchcharakters inhaltlich und hinsichtlich der Vorgehensweise als Orientierung diente sowie der dritte Band des Werkes „The Art of Computer Programming“ von Donald E. Knuth, welcher sich im Speziellen mit Such- und Sortieralgorithmen befasst.

Um den Einstieg in das Thema zu erleichtern, sollen nach der folgenden Begriffsdefinition die Grundlagen zur Beurteilung und Charakterisierung von Algorithmen geschaffen werden. Anschließend werden zu den gegenwärtig bedeutendsten Einsatzgebieten von Algorithmen repräsentative Beispiele gegeben und diese kurz erläutert.

Dabei wird der Fokus auf die praktischen Anforderungen und Anwendungsmöglichkeiten von Algorithmen gelegt und nicht mehr als nötig theoretisches Grundwissen auf Basis idealisierter Rahmenbedingungen vermittelt. Da es sich lediglich auf eine Einführung in dieses Gebiet handelt, ist somit auch kein Anspruch auf Vollständigkeit gegeben und bedürfte des eingehenden Studiums bspw. der oben erwähnten und einschlägigen Fachliteratur.

Grundkenntnisse der Programmierung in einer objekt-orientierten Programmiersprache werden im Folgenden vorausgesetzt.

2.1 Algorithmus-Definition

“Each algorithm not only computes the desired answers to a numerical problem, it also is intended to blend well with the internal operations of a digital computer.“^[2]

Der Begriff „Algorithmus“ beschreibt in der Informatik einen schematischen Lösungsweg, der mit einer endlichen Folge von Anweisungen zu dem gewünschten Ergebnis führt. Diese Definition impliziert für einen Algorithmus dessen

- Determiniertheit (ein Algorithmus liefert bei gleicher Ausgangssituation reproduzierbare Ergebnisse),
- Diskretheit (ein Algorithmus besteht aus genau n Verarbeitungsschritten),
- Eindeutigkeit (jeder Verarbeitungsschritt eines Algorithmus ist klar definiert) und
- Endlichkeit (ein Algorithmus endet nach endlich vielen Verarbeitungsschritten).

Aus der Sicht der Programmierung besteht ein Algorithmus aus zwei grundlegenden Strukturelementen. Einerseits aus einer Rechenanweisung, die die auszuführende Operation beschreibt und andererseits aus einer bedingten Sprunganweisung, welche das Verhalten des Algorithmus beim Eintreten eines bestimmten Zustandes definiert.

2.2 Algorithmenanalyse

Zur Auswahl und Beurteilung von Algorithmen wird die benötigte Zeit untersucht, „die ein Programm im durchschnittlichen [günstigsten] Fall bei typischen Eingabedaten … [und] im ungünstigsten Fall bei der denkbar ungünstigsten Konfiguration der Eingabedaten“^[3] benötigt.

Die Untersuchung der Zeitkomplexität der Ausführung eines Algorithmus hängt zum einen von seiner Struktur und zum anderen von der Performanz der zugrunde liegenden Hardware-Infrastruktur sowie der Zusammensetzung der Eingabedaten ab.

Eine Analyse hinsichtlich der Geschwindigkeit der Ausführung der Rechenanweisungen seitens der Hardware-Ressourcen gestaltet sich allerdings schwierig, weil vor allem bei Einsatz aktueller Multitasking-Plattformen durch die Ressourcenteilung keine exakte Aussage zur benötigten Zeit für die Ausführung genau einer Programm-Anweisung getroffen werden kann.

Der unterschiedliche Aufbau eines jeden Algorithmus bedingt ebenfalls ein sehr unterschiedliches Verhalten bei identischen Eingabedaten. So läuft ein Algorithmus „bei einer bestimmten Art von Eingabe[datenkonstellationen] effizienter ab“^[4] als ein anderer und erschwert somit ebenfalls die Vergleichbarkeit von Algorithmen hinsichtlich ihrer Laufzeiten.

Trotz dieser Probleme bei der Algorithmenanalyse ist es dennoch in vielen Fällen möglich, eine präzise Vorhersage über die Leistungsfähigkeit von Computer-Algorithmen zu treffen und sie entsprechend zu klassifizieren.

2.3 Klassifikation von Algorithmen

Für gewöhnlich hängt die Zeitkomplexität von Algorithmen maßgeblich von der Anzahl der zu verarbeitenden Datenelemente N ab. Die meisten Algorithmen können zu einer der folgenden Funktionen hinsichtlich ihrer Laufzeit durch ein konstantes Vielfaches beschrieben werden:

1 Die Laufzeit des Algorithmus ist konstant zu der Anzahl der übergebenen Datenelemente. Dies repräsentiert den Idealfall.

log N Die Laufzeit des Algorithmus ist logarithmisch, nimmt also bei einer steigenden Anzahl von Datenelementen unterproportional zu. Dieses Verhalten deutet auf einen Algorithmus hin, der nach der Top-Down-Methode die Komplexität eines Problems bis zu einem gewissen Grad auf einfachere Teilaufgaben reduziert.

N Die Laufzeit des Algorithmus ist linear abhängig von der Anzahl der Datenelemente; d.h. wenn N sich verdoppelt, verdoppelt sich auch die Laufzeit.

N log N Die Laufzeit des Algorithmus verhält sich „linear-logarithmisch“ zu N. Wie bei den logarithmischen Algorithmen arbeitet diese Algorithmen-Klasse ebenfalls nach der Top-Down-Strategie, wobei die Teilprobleme unabhängig voneinander bearbeitet werden und dann in Kombination die Lösung ergeben.

N log² N Die Laufzeit dieser Algorithmen-Klasse liegt zwischen den Laufzeiten N log N und N ², wobei bei einer großen Zahl an Datenelementen eher gegen N log N tendieren. Die Funktionsweise diese Algorithmen beruht auf einer zweistufigen Zerlegung der Aufgabe in Teilprobleme.

N ² Die Laufzeit des Algorithmus ist quadratisch abhängig von der Anzahl der Datenelemente. Typischerweise verwenden diese Algorithmen zwei ineinander verschachtelte Schleifen zur Lösung des Problems und finden in der Praxis aufgrund ihrer relativ langen Laufzeiten nur bei „kleinen“ Problemen Anwendung.

N³ Die Laufzeit des Algorithmus ist kubisch abhängig von der Anzahl der Datenelemente. Hier bilden drei verschachtelte Schleifen die Struktur des Algorithmus und bedingen sehr hohe Laufzeiten.

2 N Algorithmen mit exponentieller Laufzeit sind meist für praktische Anwendungen ungeeignet, da sich bei jeder Verdopplung von N die Laufzeit quadriert.^[5]

Neben der Zeitkomplexität ist der am häufigsten untersuchte Aspekt von Algorithmen deren Platzkomplexität, die den minimalen Speicherbedarf eines Algorithmus zur Lösung eines Problems angibt.

Dabei wird die Skalierbarkeit des Algorithmus geprüft, in dem der Speicheraufwand in Abhängigkeit von der Datenmenge analysiert wird.

2.4 Optimieren von Algorithmen

Ziel eines jeden Entwicklers von Computer-Algorithmen ist es, einen möglichst effizienten Algorithmus zur Lösung einer spezifischen Problemstellung zu implementieren; dies ist natürlich in der Praxis im Zusammenhang mit dem mit der Implementierung verbundenen Aufwand und den gestellten Anforderungen evtl. zu relativieren.

Um jedoch einen möglichst optimalen^[6] Algorithmus zu programmieren, gibt es einige Grundsätze an denen sich der Programmierer bei der Implementierung orientieren sollte.

So ist die „innere/innerste Schleife“ des Algorithmus möglichst effizient zu implementieren, da sie während der iterativen oder rekursiven Lösung des Problems ständig bzw. am häufigsten aufgerufen bzw. durchlaufen wird und somit die in ihr enthaltenen Befehle die meiste Rechenzeit beanspruchen.

Daher gilt es zum einen, diese Befehle hinsichtlich ihrer Anzahl zu minimieren. Zum anderen müssen die Programmanweisungen auch hinsichtlich ihrer Semantik optimiert werden. Dabei sollten zum Beispiel mathematische Berechnungen so weit wie möglich vereinfacht, die Anzahl der Schleifen bzw. Schleifendurchläufe reduziert sowie Prozedur- bzw. Methoden-Aufrufe vermieden und deren Code direkt implementiert werden.

Des Weiteren ist die Struktur bzw. das Verfahren der Implementierung zu überprüfen, da eine iterative Implementierung eines Algorithmus einer möglicherweise leichter verständlicheren rekursiven Lösung aus Performanz-Gründen vorzuziehen ist.

2.5 Beispiele für die Optimierung von Algorithmen

Um die eben erwähnten algorithmenspezifischen Verbesserungsmöglichkeiten zu verdeutlichen, sollen hier anhand einiger Beispiel-Implementierungen mögliche Optimierungen diskutiert werden.

2.5.1 Algorithmen-Optimierung auf semantischer Ebene

Der nun folgende Algorithmus ermittelt alle möglichen Variablen-Kombinationen der Gleichung n = a + b + c für ein gegebenes Ergebnis n unter der Annahme, dass alle Variablen lediglich positive ganze Zahlen repräsentieren.

Das folgende Code-Fragment zeigt die anfängliche nicht-optimierte Version des Algorithmus zur Lösung der beschriebenen Aufgabe:

Abbildung in dieser Leseprobe nicht enthalten

Implementierung 1 – equationValues (nicht-optimierte Version)

Der Algorithmus spielt alle potentiellen Variablen-Ausprägungen durch, indem er über drei ineinander verschachtelte For-Schleifen alle Summanden für die Werte von 0 bis n durchläuft und prüft, ob die Gleichung erfüllt ist und die Werte-Kombination ggf. abspeichert.

Somit handelt es sich hier vom Laufzeitverhalten her um einen kubischen Algorithmus (vgl. Kapitel 2.3 Klassifikation von Algorithmen).

Der nachfolgende Quellcode-Auszug bildet eine optimierte Variation des zuvor vorgestellten Algorithmus ab:

Abbildung in dieser Leseprobe nicht enthalten

Implementierung 2 – equationValues (erste optimierte Version)

In dem vorliegenden optimierten Code-Fragement wurde gegenüber dem nicht-optimierten Algorithmus die innerste Schleife durch eine Variablen-Zuweisung und erweiterte Bedingung ersetzt bzw. ergänzt.

Dadurch reduziert sich die Anzahl der Verarbeitungsschritte des Algorithmus auf eine quadratische Abhängigkeit von der Anzahl der Datenelemente – hier gleich dem Betrag des Gleichungsergebnisses n (vgl. Kapitel 2.3 Klassifikation von Algorithmen).

Abbildung in dieser Leseprobe nicht enthalten

In der nebenstehenden Grafik ist das Verhalten der beiden Algorithmen in Hinblick auf die Anzahl der Verarbeitungsschritte abgebildet.

Bereits ab einer Anzahl von 15 Datenelementen liegt die prozentuale Abweichung der Anzahl der Verarbeitungsschritte der nicht-optimierten von der optimierten Implementierung des Algorithmus bei annähernd 100%. Dieser Zusammenhang ist in Abbildung 2 ebenfalls grafisch dargestellt.

[...]

^[1] Vgl. Ferber, R. (Hrsg.) (2003), http://information-retrieval.de/, Stand: 22.03.2005

^[2] Knuth, D. (2002a), S. IX

^[3] Sedgewick, R. (1992),

^[4] Sedgewick, R. (1992),

^[5] Sedgewick, R. (1992), S. 96ff

^[6] Einen optimalen Algorithmus gibt es nicht – Vgl. ders. (1992),