%\documentclass{book}
%\usepackage{graphicx}
%\usepackage{german}
%% Zahlenmengen
%\def\RR{\mathbb{R}} %reelle Zahlen
%\def\NN{\mathbb{N}} %natuerliche Zahlen
%\def\ZZ{\mathbb{Z}} %ganze Zahlen
%\def\BB{\mathbb{B}} %boolesche Zahlen (={true,false})
%\def\CC{\mathbb{C}} %komplexe Zahlen
%\begin{document}
\subsubsection{Einf\"{u}hrung}\label{intro}

Mit der Popularit\"{a}t des Internets sind auch die Quellen der Dokumentensammlungen (Zeitungsartikel, Webseiten, Bibliographien, usw) gestiegen, die f\"{u}r die Informationsgewinnung den Nutzern zur Verf\"{u}gung stehen. Somit ist auch die Frage entstanden, wie man unter dieser gro"sen Informationsmenge, auf effiziente Art und Weise, Dokumente f\"{u}ndig machen kann, die einem relevant erscheinen. Bew\"{a}hrt haben sich daf\"{u}r Web-Suchmaschinen, welches den Nutzern als Hilfsmittel dient, um bestimmte Dokumente in Sammlungen zu finden. Diese liefern einen leichten und effizienten Zugang zu Informationen. Neben der effizienten Suchfunktion sind Suchmaschinen auch f\"{a}hig Indexierung vorzunehmen. Viele g\"{a}ngige Suchmaschinen sind Indexbasiert. Man stelle sich den Index wie das Schlagwortverzeichnis eines Buches vor. Durch st\"{o}bern im Index nach dem gesuchten Wort, findet man schliesslich den passenden Verweis auf die Seite und schl\"{a}gt diese dann auf. Vorteil hierbei ist mit Sicherheit die verk\"{u}rzte Suchzeit.
In Kapitel 2 m\"{o}chte ich vorstellen wie man den Index als Datenstruktur konstruiert und verwalten kann. Zus\"{a}tzlich will ich in die Indexstruktur, dem Inverted File n\"{a}her eingehen.
Da im Internet eine erheblich gro"se Menge an Dokumenten zur Verf\"{u}gung stehen, k\"{o}nnen dementsprechend auch die Indizes gro"s ausfallen.
In Kapitel 3 werde ich zeigen, wie man mit geeigneten Kompressionsverfahren die Indexgr\"{o}"se reduzieren kann.
Zum Abschlu"s in Kapitel 4 will ich auf weitere Indexierungsverfahren eingehen, dem Signature File, dem Suffix Array, sowie dem Suffix Tree.
\subsubsection{Index}\label{ix}
\paragraph{Inverted Files}\label{if}
Ein Index ist eine Datenstruktur, welches Ausdr\"{u}cke auf Dokumente abbildet, die sie enthalten.
Die effizienteste Indexstruktur, die zum Indizieren verwendet wird, ist das Inverted File. Das Inverted File ist Sammlung von Listen indem alle Ausdr\"{u}cke abgespeichert werden die in Dokumenten vorkommen. Dabei unterscheidet man 2 Varianten des Index. Zum einen das word-level Index, indem angezeigt wird, an welcher Position ein Ausdruck im Dokument vorkommt. Die zweite Variante ist das document-level Index, indem nur Information vorliegt, ob ein Ausdruck in einem Dokument vorkommt, ohne den Hinweis daf\"{u}r zu liefern an welcher Stelle der jeweilige Ausdruck erscheint.
\"{U}blich ist die Zuordnung jedes einzelnen Dokumentes einer Menge von Ausdr\"{u}cken. Doch wie der Name Inverted File verr\"{a}t, findet hier eine Zuordnung jedes Terms auf eine Liste von Informationen \"{u}ber das Vorkommen des Terms in Dokumenten statt.
Ein Inverted File besteht im wesentlichen aus einem W\"{o}rterbuch, indem alle vorkommenden Terme eines Dokuments abgelegt werden. Das W\"{o}rterbuch bildet dann auf ein Posting File ab, indem die doc-id, also Termvorkommen, eventuell auch Wortpositionen abgespeichert sind.
Der Vorteil einer solchen Datenstruktur ist der schnelle Zugriff auf Terme und Dokumente. Daraus resultiert nat\"{u}rlich eine kurze Suchzeit.
Der Nachteil bei einer gro"sen Anzahl an W\"{o}rtern die in Listen abgespeichert werden m\"{u}ssen, ist der hohe Speicheraufwand.
Durch Erweiterungen des Index wird beabsichtigt eine Suche m\"{o}glichst effizient zu machen.
Methoden wie Stemming oder Stopping beispielsweise sorgen daf\"{u}r den Index klein zu halten. 
Mit Stemming werden W\"{o}rter auf ihre Stammforme reduziert. Man betrachtet dabei nicht die Worte sondern die Wortst\"{a}mme und trennt die Endungen eines Wortes und speichert die W\"{o}rter in ihrer Grundform im Index ab.
Mit Stopping werden Pr\"{a}positionen wie (die,von,bzw.,...) weggelassen, die wenig Aussagekraft haben. Dies erm\"{o}glicht die Einsparung von Platz bei der Speicherung des Indexes. Daraus resultiert eine effiziente Suche da der Index kleiner ist.
Andere Techniken, die verwendet werden um die Gr\"{o}"se des Index klein zu halten ist der Thesaurus. Ein Lexikon, indem unterschiedliche W\"{o}rter gleicher Bedeutung zusammengefasst werden.
\paragraph{Indexkonstruktion}\label{ik}
Die Konstruktion eines Indexes, auch Invertierung genannt, beinhaltet die folgenden 3 Schritte: Im ersten Schritt, dem Parsen der Dokumente, werden die Dokumente die zu indizieren sind von vorne bis hinten durchlaufen und eine Liste der W\"{o}rter mit der Dokumenten-id erstellt.Dabei k\"{o}nnen schon die Stopw\"{o}rter, die den Index unn\"{o}tig vergr\"{o}"sern, ausgelassen werden.
Nachdem man diese Liste alphabetisch mit Hilfe von Sortieralgorithmen sortiert hat, werden W\"{o}rter die in der Liste doppelt vorkommen, zusammengefasst. Durch die in der Liste angegebenen Dokumenten-id ist das Vorkommen der W\"{o}rter eindeutig bestimmt. 
Beim Erstellen des Index k\"{o}nnen auch m\"{o}gliche Probleme auftreten. Durch das Sortieren des Index m\"{u}ssten alte umsortierte oder neue sortierte Daten auf die Platte abgelegt werden. Diese w\"{u}rde kurzzeitig zu einem erh\"{o}hten Speicherverbrauch f\"{u}hren.
\paragraph{Indexverwaltung}\label{iv}
Da die Aktualisierung eines Index meistens Neu Einf\"{u}gungen von W\"{o}rtern ist, und selten gel\"{o}scht wird, w\"{a}chst nat\"{u}rlich auch die Gr\"{o}"se des Index enorm. Der Index wird meist in Speicher verwaltet. Dabei werden kurze invertierte Listen in Speicher fester Gr\"{o}"se zugeordnet, lange Listen werden in zusammenh\"{a}ngende Speicherbereiche variabler Gr\"{o}"se abgespeichert. 
Jede invertierte Liste wird in einem Bucket hinterlegt, da sie zu Beginn noch als kurze Liste hineinpasst. Doch mit dem Hinzuf\"{u}gen neuer Terme und dem Wachstum der Liste, droht ein \"{U}berlauf des Buckets. Ist der \"{U}berlauf geschehen, wird die \"{a}lteste darin enthaltene Liste zu einer langen Liste. 
Als Datenstruktur f\"{i}r einen Index werden meist Verkettete 
Listen genutzt. 
Diese erm\"{o}glichen eine dynamische Speicherbelegung, und ein einfaches Zuf\"{u}gen von Ausdr\"{u}cken in Dokumenten.
\paragraph{Indexoptimierung}\label{io}
Wie schon erw\"{a}hnt kann der Index durch zuviele Eintr\"{a}ge stetig wachsen. In Kapitel 2 wurden Verfahren erl\"{a}utert, die die Gr\"{o}"se des Index reduzieren. Das Stemming k\"{u}rzt W\"{o}rter auf ihre Stammform ab, und fasst diese in einem Wort zusammen.
Bsp. neues, neuem, neuesten wird abgek\"{u}rzt zu neu.
Wenn man in der Suchanfrage den Begriff ''neu'' eingibt, werden auch all die Dokumente ausgegeben, in denen das Wort neu mit verschiedenen Endungen auftritt.
Durch das Auslassen von Pr\"{a}positionen, Artikel, also sogenannten Stopw\"{o}rtern, verringert sich der Speicherbedarf des Index.
\subsubsection{Kompressionsverfahren}\label{komp}
Es gibt aber auch andere Ans\"{a}tze mit denen man einen Index klein halten kann. 
Und zwar sind dies Komprimierungsverfahren, die mittels geeigneter Kodierung zu einem erw\"{u}nschten Ergebnis f\"{u}hren.
Diese Kodierungsmethoden erm\"{o}glichen eine Reduzierung der Textgr\"{o}"se auf fast 50 Prozent. Daraus resultiert eine geringere Auwertungszeit von Fragen. Zus\"{a}tzlich kann in kurzer Rechenzeit ein Index erstellt werden.
\paragraph{Golomb-Code}
Der Golomb-Code wurde 1966 von Solomon W. Golomb vorgestellt.
Dabei handelt es sich um eine Darstellungsform f\"{u}r alle positiven Zahlen, einschliesslich der Null. Ein gro"ser Vorteil an diesem Kodierungsverfahren ist die Abspeicherung von Daten unbekannter Gr\"{o}"se. Es erm\"{o}glicht eine schnelle Kodierung und eine sparsame Nutzung des Speichers. Die Idee des Golomb Ansatzes besteht darin, die darzustellende 
Zahl n durch den Quotienten q, einem frei w\"{a}hlbarem Parameter b und seinem Rest r zu beschreiben. 
Dazu wird im ersten Schritt der Quotient der Zahl n berechnet mit der simplen Formel $$q=\left\lfloor  \frac{n-1}{b}\right\rfloor$$.
Das Ergebnis des Quotienten wird un\"{a}r kodiert ausgegeben, und an das Ende der Bitfolge wird eine logische 0 angeh\"{a}ngt.
Im zweiten Schritt bestimmt man den Rest r der Zahl n mit Hilfe der Formel: $$r=n*(q*b)-1.$$ Das Ergebnis wird nun bin\"{a}r ausgegeben. Zum Abschluss h\"{a}ngt man den zweiten Teil des Code-Wortes an das Ergebnis aus dem ersten Schritt und man erh\"{a}lt das fertige Code Wort. 
Zus\"{a}tzlich zum Golomb-Code gibt es noch den Rice-Code. Der
Rice-Code ist ein Spezialfall des Golomb-Code. Hierbei ist der Paramater b nicht frei w\"{a}hlbar, sondern eine zweier Potenz.
\subsubsection{Weitere Indexierungsverfahren}\label{inx}
Selbstverst\"{a}ndlich gibt es auch weitere Ans\"{a}tze um Indexierung vorzunehmen. So sind das Suffix Array, der Suffix Tree und die Signature Files Verfahren mit denen man einen Index erzeugen kann.
\paragraph{Signature Files}
In einem Signature File k\"{o}nnen Eintr\"{a}ge einer Datenbasis, welche eine bestimmte Bedingung erf\"{u}llen, effizient herausgefiltert werden.
Vor allem gro"se Textbest\"{a}nde sind, innerhalb kurzer Zeit nach Schl\"{u}sselw\"{o}rtern durchsuchbar. Die Signaturen selbst werden durch die Abbildung von W\"{o}rtern auf Bitstrings mittels Hash-Funktion erzeugt.
Dabei werden die Dokumente in einer Textdatei, die Signaturen in einer separaten Datei abgespeichert. Ein Vorteil gegen\"{u}ber dem Inverted File ist der geringe Speicherplatzbedarf, jedoch ist dieses Verfahren ineffizient f"ur gro"se Datenbanken und ein Nachteil sind die falschen Eintr\"{a}ge, sogenannte False Drops, die herausgefiltert werden.
Die Konstruktion eines Signature File besteht darin, das Dokument in logische Bl\"{o}cke zu unterteilen. F\"{u}r jeden Block werden die einzelnen Signaturen gebildet, wobei jeder Block eine konstante Anzahl an W\"{o}rtern hat. 

\paragraph{Suffix Array}
Ein Suffixarray ist ein Array, welches die Suffixe, in lexikographischer Reihenfolge angeben kann. Der Text ist als eine lange Zeichenkette abgespeichert. Jedes Teilst\"{u}ck des Textes ist eindeutig durch seine Position bestimmt, wobei die Positionen im Text frei w\"{a}hlbar sind. Der Vorteil des Suffixarrays als Index zu nutzen liegt darin, m\"{o}glichst schnell jedes Teilwort innerhalb des Wortes zu lokalisieren. Durch die lexikographische Sortierung k\"{o}nnen die Suffixe effizient mit Hilfe der bin\"{a}ren Suche gesucht werden.

\paragraph{Suffix Tree}
Ein Suffix-Tree dient dazu, die Suffixe in einer baumartigen Struktur darzustellen. Die Suffixe enden als Blatt im Baum. Also hat ein Suffix-Tree soviele Blätter wie eine Zeichenkette Suffixe besitzt. Aus den inneren Knoten gehen mindestens zwei Kinder aus. Jede Kante des Suffix-Trees definiert ein Teilwort der Zeichenkette.$$Beispiel: acacb$$
\begin{enumerate}
\item Suffix= cacb
\item Suffix= acb
\item Suffix= cb
\item Suffix= b
\end{enumerate}
\begin{figure}[h]
	\centering
		\includegraphics{bilder_emel/SuffixBaum2.jpg}
	\caption{Suffix Baum}
	\label{fig:Suffix Baum}
\end{figure}


%\bibliographystyle{plain}
%\bibliography{bibfile}
%\begin{itemize}
	%\item Justin Zobel, Alistair Moffat \textit{Inverted Files for Text Search Engines}
	%\item Prof. Dr. Christoph Schlieder \textit{Archivierungs- und    Suchfunktionen} Vorlesung 3, 4. November 2003
	%\item ( http://de.wikipedia.org/wiki/Golomb-Code)
	%\item ( http://de.wikipedia.org/wiki/Suchmaschine)
	%\item (http://de.wikipedia.org/wiki/Suffixarray)
	%\item (http://de.wikipedia.org/wiki/Suffixbaum)
	%\item (http://www.iai.uni-bonn.de) \textit{Signature Files} 
%\end{itemize}
%\end{document}
