Mal wieder eine Zusammenfassung meines Lernaufwands des vergangenen Monats, um mir das ganze leichter einzuprägen und nochmal gedanklich zu ordnen. Heute zum Thema “Markupsprachen und semistrukturierte Daten”, ein Überblick von HTML und XML bis Googles Funktionsweise.
Inhalt:
1 – Herkunft und Begriffsdefinition
2 – HTML und CSS
3 – XML, DTD und XML-Schema
4 – XPath, XQuery, XSLT
5 – RDF, SPARQL
6 – Information Retrieval und Suchmaschinen
1 – Herkunft und Begriffsdefinition
Markupsprachen sind Sprachen zur Auszeichnung von Text (und anderen Daten). Früher diente “Markup” den Typographen im Druckergewerbe für Notizen im Text, um z.B. zu wissen, welcher Abschnitt kursiv gedruckt werden soll. Außerdem wurde eine Druckseite zu Zeiten der Schreibmaschine als Matrix (bzw. Array) organisiert, sprich in gleich große Zeilen und Spalten unterteilt. Diese Festlegung bewirkt zahlreiche Probleme, darunter die Beschränkung auf ein unhandliches Layout, das teilweise der Struktur nicht gerecht wird, und zuvorderst die Schwierigkeit, einen bereits geschriebenen Text zu editieren.
Deswegen schwenkte man in der PC-Ära auf die sogenannte “Spaghetti”-Repräsentation um, d.h. der Text ist eine fortlaufende Zeile. Das hat den entscheidenden Vorteil, dass man für ein Update nur die Zeichennummer wissen muss (bzw. die Adresse/Pointer), wo man ein Zeichen einfügen, löschen oder ändern will. Editieren wird somit viel leichter. Der Nachteil ist allerdings, dass der Speicher dabei zugemüllt wird. Damit wird eine Bereinigung (Garbage Collection) nötig. Ein sehr großer Vorteil der “Spaghetti” ist außerdem, dass ein und die selbe Datenstruktur leicht auf unterschiedliche Weise darstellbar ist, z.B. die Anzeige zwischen lateinischen (l.n.r.), japanischen (o.n.u.) oder arabischen (r.n.l.) Zeichen wechseln kann, ohne dass man die komplette Matrix umschreiben müsste. Es genügen dafür entsprechende Layout-Anweisungen, auf die später noch eingegangen wird.
Heute dient Markup zur Datenmodellierung (bzw. Textformatierung), Datenstrukturierung (Repräsentation der logischen oder semantischen Struktur von Dokumenten) und zum Datenaustausch. Aus allen drei Bereichen sind Markupsprachen nicht mehr wegzudenken. XML und darauf basierende Eigenentwicklungen nehmen dabei eine herausragende Rolle ein.
Markup kann man in drei Arten unterteilen:
1. Spezifisches Markup: Dabei handelt es sich um layout-orientiertes Markup wie z.B. bei PostScript oder anderen Seitenbeschreibungssprachen. Dazu passende HTML-Befehle wären z.B. <b> oder <i> für Fett- bzw. Kursivdruck.
2. Generalisiertes Markup ist dagegen struktur-orientiert. HTML, LaTeX und RTF besitzen sowohl spezifische wie auch generalisierte Elemente. Ein Beispiel für diesen Bereich wäre MathML. Generalisiertes Markup für Fett- und Kursivdruck in HTML wären <strong> und <em>.
3. Generisches Markup: Dazu zählen Metasprachen wie XML, mit deren Hilfe man selbst Markupsprachen entwickeln kann. Das obige Beispiel generisch weitergedacht würde z.B. <betont> als Element einführen.
2 – HTML und CSS
Seinen geschichtlichen Ursprung hat HTML am CERN in Genf, wo Tim Berners-Lee Ende der 80er eine Markupsprache entwickelte, um einfach wissenschaftliche Dokumente mit anderen austauschen zu können und darin Links zu Quellen zu plazieren. Wenig später wurde das WWW begründet und dazu das Konsortium (W3C) gegründet, das über HTML wachen sollte. 1992 wurde es erstmals standardisiert. Das W3C gab über die Jahre zahlreiche Empfehlungen zur HTML-Implementierung heraus (”Recommendations”), die es mit den großen Firmen der Branche erarbeitet. Im Jahr 2000 erschien XHTML, eine Anpassung von HTML an die XML-Spezifikationen, v.a. eine striktere Syntax mit dem Ziel einer einfacheren Interpretation durch Web-Browser und Prüfungswerkzeugen.
Ein (X)HTML-Dokument ist ähnlich aufgebaut wie ein XML-Dokument. Es besteht aus einem Prolog, der Sprache, Grammatik und Zeichensatz festlegt, einem Kopfteil bzw. “Head”, der den Titel des Dokuments, Links z.B. zu Stylesheets, Skripte und Metadaten beinhaltet und die Wiedergabe des Dokuments definiert und schließlich einem Körper bzw. “Body”, der den eigentlichen Text beinhaltet. Das sieht beispielsweise so aus:
<?xml version=”1.0″ encoding=”iso-8859-1″?>
<!DOCTYPE html PUBLIC “-//W3C//DTD XHTML 1.0 Strict//EN”
“http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd”>
<html xmlns=”http://www.w3.org/1999/xhtml” xml:lang=”en” lang=”en”>
<head>
<meta http-equiv=”Content-Type” content=”text/html; charset=iso-8859-1″></meta>
<meta name=”Author” content=”Beispielmacher” />
<title>
Beispieldokument
</title>
<link rel=”stylesheet” type=”text/css” href=”myStylesheet.css”></link>
<script src=”/pmsmail.js” type=”text/javascript”></script>
<style type=”text/css”>
…
</style>
</head>
<body>
….
</body>
</html>
Hier bestimmt die erste Zeile, welche XML-Version und welcher Zeichensatz benutzt wird. Diese Zeile ist im Web eher unnötig und führt z.B. beim Internet Explorer zu einem Performanzverlust. Die zweite weist zur DTD, die wir später noch besprechen werden. Der Header beginnt nach dem <html>-Tag, der zusätzlich noch Namensraum und Sprache festlegt. Im Header ist wieder ein (hier redundanter) Hinweis auf den Zeichensatz gegeben (besser als Zeile 1 für IE) und ein Beispiel für die Integration von einem Stylesheet und einer JavaScript-Datei.
CSS
Nun war schon öfter die Rede von Stylesheets. Sie sind eine geordnete Sequenz von Regeln und werden genutzt, um der durch XHTML beschriebenen Struktur ein Layout zu geben. CSS (Cascading Stylesheets) ist hier das Mittel der Wahl. “Cascading” besagt hierbei, dass im Konfliktfall die geltende Regel nach einem kaskadierenden Muster ausgewählt wird, sprich die verschiedenen Regeln nach Wichtigkeit (Spezifizität) durchgegangen werden und die wichtigste ausgewählt wird.
CSS kann entweder als externe Datei eingebunden werden (wie oben im Beispiel mit <link rel”stylesheet” …>) oder im Header als Style-Anweisung (<style type=”text/css”>…) oder man schreibt die Regeln direkt in die entsprechenden Tags (z.B. <td style=”text-align:right;”>).Eine weitere Alternative ist die Einbindung über eine Import-Anweisung im Stylesheet (@import url(myStyles.css) ).
Die besagten Regeln bestehen aus einem oder mehreren Selektoren und einer Liste aus Deklarationen, die wiederum einer Eigenschaft einen Wert zuweisen. Ein Beispiel hierzu:
em, tt { text-align:right; font-size:170%; }
… besagt, dass der Text innerhalb der Tags <em> und <tt> rechtsausgerichtet ist und 170% der normalen Größe hat. Bei CSS erben die Elemente die Eigenschaften ihrer Eltern-Elemente. Ausnahmen hiervon sind Eigenschaften wie background.
Hypertextmodell
Hypertext besticht dadurch, dass man Links zu anderen Seiten einbetten kann. Das Modell von HTML sieht dabei nur Links von einer Quelle zu einem Ziel vor. Mit dieser Limitierung sind einige Nachteile verbunden: Der Link wird im Anker (<a href=”..”>) bzw. der Quelle spezifiziert, was nach sich zieht, dass man bei 1000 Links zu einem bestimmten Ziel diese 1000 Links ändern muss, wenn sich die Adresse des Ziels ändert. Eine intuitive Lösung für dieses Problem ist eine Link-Base, die dem Index eines Lexikons entspricht. Dann muss bei einem Update nur ein Eintrag geändert werden. Andere Modelle wie XLink oder Hytime bieten auch Links zu mehreren Zielen, rückwärts begehbare bzw. multidirektionale Links und personalisierbare bzw. kontextualisierte Links.
Neuere Entwicklungen in dieser Richtung sind Redirection-Seiten wie TinyURL oder BitLy, die v.a. durch Twitter notwendig wurden. Eine weitere Entwicklung ist die Typisierung von Links. Bekannt sind die Attribute rel=”noindex” (Suchmaschinen-Bots sollen dem Link nicht folgen) und rel=”nofollow” (Suchmaschinen sollen Link nicht werten, s.u.). Des Weiteren gibt es noch z.B. rel=”canonical” (um bei inhaltsgleichen Dokumenten eine primäre URI zu spezifizieren, die von Suchmaschinen bevorzugt werden soll).
3 – XML, DTD und XML-Schema
XML erblickte 1998 das Licht der Welt und ist heute die meistverbreitete Markupsprache im Bereich Datenmodellierung und Datenaustausch.
Obiges XHTML-Dokument zeigt schon den Aufbau eines XML-Dokuments. Es besteht aus einem Prolog, der Spezifikation des Dokumentbaums und evtl. Prozessanweisungen (für alle möglichen Anwendungen). Der Prolog setzt sich zusammen aus einer XML-Deklaration samt Zeichensatz (hier im Gegensatz zu oben verpflichtend), evtl. Prozessanweisungen und optional der Deklaration einer DTD. Der Dokumentbaum besteht aus einem Wurzelknoten und (meistens) weiteren Zweigknoten und Blättern. Auch Text (Strings) ist als Blattknoten zu begreifen.
XML erweitert seinen Vorgänger SGML um ein Hypertextmodell und verbietet außerdem Tag-Minimierung, d.h. <li>bla<li>blub ist nicht erlaubt; geöffnete Tags müssen geschlossen werden (<li>…</li>). Das erleichtert die Auswertung und die Nutzung einer kontextfreien Grammatik.
Ein XML-Dokument kann wohlgeformt und valide sein. Wohlgeformt ist es dann, wenn es einen Wurzelknoten besitzt und die Klammerung der Zweigelemente konsistent ist (also keine Minimierung). Valide ist ein Dokument, wenn es wohlgeformt ist und der spezifizierten DTD entspricht.
Der Unterschied zwischen XML und HTML ist hauptsächlich, dass HTML spezifisch und generalisiert ist, während XML generisches Markup ist. Außerdem bietet XML ein ausgeklügelteres Hypertextmodell (s.o.).
DTD
Eine DTD (Document Type Definition) ist eine kontextfreie Grammatik, d.h. der Kontext ist belanglos für das jeweilige Element. Das bedeutet aber auch, dass z.B. bei einem Element <person> und einem Element <unternehmen> kein Element <adresse> gleichzeitig bei beiden benutzt werden kann. Dies ist nicht die einzige ernsthafte Beschränkung, wie wir gleich sehen werden.
Eine DTD besteht aus Markup-Deklarationen, die eine Grammatik für eine Klasse von Dokumenten festlegen. Sie sieht beispielsweise so aus:
<!DOCTYPE transaktion [
<!ELEMENT transaktion (buecherei,kunde,notiz,buecher)*>
<!ATTLIST transaktion datum CDATA #REQUIRED>
<!ELEMENT buecherei (name,strasse,ort,land)>
<!ATTLIST buecherei tel CDATA #REQUIRED>
<!ELEMENT name (#PCDATA)>
<!ELEMENT strasse (#PCDATA)>
usw...
]>
Im DOCTYPE wird das Wurzelelement spezifiziert. ELEMENT tut dasselbe für Elemente, ATTLIST erstellt Attributlisten für ein Element und es gibt auch noch ENTITY als Möglichkeit zur Abkürzung und NOTATION für Anmerkungen. REQUIRED bedeutet, dass das Attribut vorkommen muss, IMPLIED bedeutet, dass es optional ist, FIXED wert, dass es eine Konstante ist. CDATA ist einfacher Text. Kindelemente können entweder eine geordnete Sequenz sein (a,b,c) oder frei angeordnet sein (a|b|c). ? hinter Elementen oder Sequenzen heißt 0- oder 1-mal, * heißt 0- bis n-mal und + heißt 1- bis n-mal.
Attribute können auch eine ID oder IDREF sein, also ein Identifier oder eine Referenz auf einen Identifier. Damit können Zusammenhänge bzw. Querverweise innerhalb des Dokuments hergestellt werden.
Eine weitere Einschränkung einer DTD ist, dass bei freien Sequenzen eine freie Ordnung nicht leicht zu spezifizieren ist. Möchte man z.B. festlegen, dass die Kindelemente entweder (a,b) oder (a,c) sind, kann man nicht einfach ((a,b)|(a,c)) schreiben, da der Prozessor eine deterministische DTD verlangt. Stattdessen muss man (a,(b|c)) schreiben. Für größere Mengen und Permutationen wird eine solche Auflistung zur Horroraufgabe. Auch XML-Schema schafft da keine Abhilfe, erst RelaxNG.
XML-Schema
Im Unterschied zu DTDs ist bei XML-Schema eine kontextabhängige Interpretation eines Elements wegen der lokalen Typspezifikation möglich. XML-Schema bietet außerdem viele simple Datentypen (string, float etc.), abgeleitete Typen (”derived”; token, ID, integer…) und komplexe, selbst-erstellbare Datentypen. Dabei können Intervallrestriktionen festgelegt werden (z.B. Konto darf nicht überzogen werden) oder Constraints (z.B. nicht mehr als 10 Bücher dürfen ausgeliehen werden) und vorhandene Elemente oder Attribute erweitert werden. Gut ist auch, dass XML-Schema selbst in XML ist, also von XML-Parsern gelesen und geprüft werden kann. Vorteile gegenüber DTDs sind also Typisierung, Restriktionen/Constraints und “Parsebarkeit”.
Beispiel:
<xsd:schema>
<xsd:complexType name=”transaktion”>
<xsd:attribute name=”datum” type=”xsd:date”/>
<xsd:sequence>
<xsd:element name=”buecherei” type=”info”/>
<xsd:element name=”kunde” type=”info”/>
<xsd:element name=”notiz” type=”xsd:string”/>
<xsd:element name=”buecher” type=”buecher”/>
</xsd:sequence>
</xsd:complexType>
<xsd:complexType name=”info”>
<xsd:attribute name=”tel” type=”xsd:string”>
<xsd:pattern value=”[0-9][1-9][1-9]-[.......]….”/>
<xsd:attribute>
<xsd:sequence>
<xsd:element name=”name” type=”xsd:string”/>
usw…
</xsd:sequence>
</xsd:complexType>
<xsd:complexType name=”buecher”>
<xsd:element name=”buch” maxOccur=”10″>
<xsd:complexType>
<xsd:attribute name=”buchID” type=”xsd:string”/>
<xsd:element name=”titel” type=”xsd:string”/>
usw…
</xsd:complexType>
</xsd:element>
</xsd:complexType>
</xsd:schema>
Die Ähnlichkeiten zu DTDs ist unverkennbar. Elternelemente werden zu ComplexTypes, Sequenzen zu Sequences und es können eben auch noch Typen festgelegt und Einschränkungen getroffen werden. Es ist auch möglich, Schlüssel wie bei Datenbanken zu definieren.
4 – XPath, XQuery, XSLT
XPath ist eine Abfragesprache, um Teile des XML-Dokuments zu adressieren. Es dient als Grundlage u.a. für XML-Schema, XQuery und XSLT. Viel mehr als der gute Wikipedia-Artikel kann man über XPath nicht erzählen. Einzig noch, dass eine Achsennavigation über Siblinge mit der Kurzschreibweise nicht möglich ist und dass die Auswertung in polynomieller Zeit erfolgt.
XQuery benutzt für Pfadausdrücke, wie eben erwähnt, XPath. Grob besteht die Syntax aus sog. FLWOR-Ausdrücken (sprich “Flower”). Die heißen deswegen so, weil die entsprechenden Schlüsselwörter FOR, LET, WHERE, ORDER BY und RETURN sind. Ein einfaches XQuery-Beispiel für ein Dokument, das obiger DTD entspricht, wäre:
FOR $buecherei IN //buecherei
WHERE $buecherei/name = “Dombücherei”
ORDER BY $buecherei/name
RETURN <p>{$buecherei/ort} hat eine Dombücherei.</p>
Hier wird per XPath jedes Element <buecherei> ausgewählt. Die Where-Bedingung beschränkt die Auswahl dann auf die Büchereien, deren Name “Dombücherei” ist. Dann wird das ganze noch alphabetisch nach Namen sortiert und dann nacheinander jede dementsprechende Bibliothek mit dem selben Satz gewürdigt.
XSLT dient zur Transformation von XML-Dokumenten. Eine solche Funktionalität wird dann benötigt, wenn das Ausgangsdokument nicht zur gewünschten Spezifikation passt, also man z.B. statt <antlitz> sonst immer <gesicht> genutzt hat und deswegen eine solche Umwandlung wünscht. XSLT schafft dies mittels Transformationsregeln, sog. “Matching Rules” bzw. “Template Rules”. Ein Beispiel:
<xsl:template match="//name"> <i> <xsl:apply-templates/> </i> </xsl:template>
Hierbei wird dann im Zieldokument jeder Name kursiv geschrieben. Auch Sortieren und Bedingungen sind möglich.
5 – RDF, SPARQL
SPARQL ist eine Anfragesprache für RDF (Resource Description Framework). Dabei handelt es sich um eine Sprache zur Wissensrepräsentation, die Sachverhalte mittels Tripeln als Graph darzustellen versucht. Ein kurzes Beispiel:
@prefix foaf:
<http://xmlns.com/foaf/0.1/> .
@prefix eg:
<http://www.example.com/persons> .
eg:bob foaf:knows eg:anna .
eg:bob foaf:knows _:X .
eg:anna foaf:age “25″ .
eg:anna foaf:knows eg:chuck .
_:X foaf:knows eg:chuck .
Das RDF-Dokument beschreibt eine Freundschaftsbeziehung zwischen Bob und Anna, besagt, dass Bob irgendeinen kennt, der Chuck kennt, dass Anna 25 ist und Anna Chuck kennt. Folgende SPARQL-Anfrage selektiert die Bekannten von Bob:
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX eg: <http://www.example.com>
SELECT ?person
WHERE { { ?person foaf:knows eg:bob }
UNION { eg:bob foaf:knows ?person } }
SPARQL ähnelt dabei SQL. Die Auswahl wird durch die Tupel-Variablen in WHERE beschränkt, die besagen, dass eine Person gesucht ist, die Bob kennt und gleichzeitig von Bob gekannt wird. Eine erfrischend intuitive Sprache.
6 – Information Retrieval und Suchmaschinen
Aus dem weiten Gebiet der Information Retrieval haben wir in der Vorlesung nur die Textnormalisierung besprochen. Sie findet entweder durch Stemming (nach einfachen Regeln wie Wortende abhacken, z.B. Daches -> Dach) oder Lemmatisation (nach ausgeklügelten Regeln wie Rückführung von Beugungsformen, z.B. sah -> sehen) und Stop-Word-Eliminierung (also Streichen von häufigen Wörtern wie “der” oder “und”). Der ganze Spaß dient dem Zweck maschinell herauszufinden, was der semantische Inhalt eines Textes ist. Dadurch lässt sich dann bestimmen, ob der Text für eine bestimmte Suchanfrage relevant ist.
Beim Information Retrieval gibt es verschiedene Begriffe zu unterscheiden (Term i, Dokument j):
- Die Einfache Termfrequenz (RTF): Anzahl der Vorkommen von i in j
- Die Normalisierte Termfrequenz (TF): RTF geteilt durch Vorkommen von i in allen Dokumenten
- Inverse Dokumentfrequenz (IDF): Anzahl der Dokumente geteilt durch Anzahl der Dokumente mit i, meist logarithmisch gedämpft => log(N/DF(i))
- TF-IDF: TF(i,j) * IDF(j) ergibt eine Gewichtung für die Bedeutung des entsprechenden Terms.
Zwei bedeutende Begriffe sind Precision und Recall. Recall bezeichnet das quantitative Verhältnis von abgerufenen Dokumenten zu relevanten Dokumenten und Precision das Verhältnis von abgerufenen, relevanten Dokumenten zur Anzahl abgerufener Dokumente. Ein hoher Recall-Wert bei niedriger Precision ist genauso fragwürdig wie ein niedriger Recall bei hoher Precision. Optimal ist natürlich ein hoher Wert in beiden Kategorien.
Information Retrieval diente als Thema v.a. zur Hinführung auf die Funktionsweise von Suchmaschinen. Durch die immer größere Flut an Informationen, nicht zuletzt im Internet, wurden Suchmaschinen unerlässlich. Sie bestehen aus:
- Crawler: sammelt und speichert Daten, nutzt den Strukturindex.
- Indexing-Modul: extrahiert Schlüsselwörter, Phrasen und andere Deskriptoren aus den gespeicherten Daten und komprimiert sie und erstellt den Content Index und den Structure Index.
- Query-Modul: implementiert eine Anfragesprache und nutzt beide Indizes.
- Ranking-Modul: weist den vorgehaltenen Seiten einen qualitativen Wert zu.
Interessant ist vor allem das Ranking-Modul. Hier soll nun erklärt werden, wie das Ranking-Modul von Google (”PageRank”) in seinen Grundzügen arbeitet. Die genaue Funktionsweise ist natürlich ein Firmengeheimnis, stetig in Entwicklung und wahrscheinlich nicht so kompakt zu erklären wie die Grundfunktionalität.
Der PageRank bedient sich eines intuitiven Modells. Er modelliert im Grunde die Aktionen eines Surfers, der den Links im Internet folgt und hin und wieder auch mal zu einer beliebigen Seite springt. Das Internet stellen wir uns hierzu als Graphen vor, bei dem die Seiten Knoten und die Links Kanten sind. Aus diesem Graphen lässt sich eine Adjazenzmatrix erstellen. Diese Matrix besteht aus Nullen und hat dort eine 1, wo die Seite der Zeile zur Seite der Spalte einen Link hat (bzw. eine 2 bei zwei Links etc.). Dann werden die Zeilen normalisiert, d.h. die Einzelwerte durch die Summe der Werte der Zeile geteilt. Intuitiv entspricht dies der einzelnen Chance, von der einen zur anderen Seite via Link zu gehen. Der gerade beschriebene “Random Surfer” wird einfach draufaddiert, d.h. zur Adjazenzmatrix wird eine Matrix addiert, deren sämtliche Werte 1/(Anzahl der Seiten) betragen. Bei einem Netz von 5 Seiten wäre also die dadurch entstandene Matrix mit 1/5 besetzt, wo vorher Nullen standen.
Insgesamt sieht die Berechnung der “Google-Matrix” wie folgt aus:
H = (1-c)*A + c*S
wobei A die normalisierte Adjazenzmatrix ist und S die Random-Surfer-Matrix. c ist die probabilistische Einschätzung eines “Random Leaps”, also die Chance, dass ein Surfer zu einer beliebigen Seite springt. Bei Google beträgt dieser Wert c = 0,15 = 15%.
Diese Matrix hilft uns nun dabei herauszufinden, welche Bedeutung die einzelnen Seiten im Netz haben. Hierbei gilt, dass eine Seite umso relevanter ist, je mehr sie verlinkt wird, d.h. je relevanter sie andere Seiten einschätzen. Die Weitergabe von Relevanz ist aber eng damit verbunden, wie relevant die einschätzende Quelle ist. Ist z.B. die Quellseite selbst relevant (z.B. Wikipedia) und verlinkt sie auf eine andere Seite, so ist die verlinkte Seite automatisch sehr viel relevanter. Die Frage ist also nun, wie sich bei dieser rekursiven Definition die Relevanz einer einzelnen Seite bestimmen lässt.
Diese Frage ist ein sogenanntes Eigenvektorproblem. Wir suchen also nach einem Vektor, dessen Richtung (und in diesem Fall auch Länge) durch die Abbildung (salopp also der dargelegte Sachverhalt) nicht verändert wird. Mathematisch ausgedrückt also H*x = x, wobei x der gesuchte Vektor ist. Die nächste Frage ist also, ob es einen solchen Vektor geben kann.
Hier wandert der Blick zurück in der Geschichte bis vor über 100 Jahren. Damals stellte Frobenius an der Preußischen Akademie der Wissenschaften ein Theorem auf, das fast ein Jahrhundert später Google zum Durchbruch verhalf. Er stützte sich dabei auf ein Theorem des jungen Münchner Mathematikers Perron, der formulierte:
Wenn A eine quadratische Matrix ist und ihre Einträge streng positiv (>0), dann 1. existiert ein einfacher Eigenwert λ > 0, sodass A*v = λ*v, wobei der dazugehörige Eigenvektor real und streng positiv ist, 2. λ >= | m | für jeden anderen Eigenwert m von A und 3. jeder andere positive Eigenvektor von A ist ein Vielfaches von v.
Frobenius’ Theorem lautet wie folgt:
Wenn A eine quadratische Matrix ist und die Einträge von A positiv (>=0) und wenn A irreduzibel ist, dann 1. existiert ein einfacher Eigenwert λ > 0, sodass A*v = λ*v, wobei der dazugehörige Eigenvektor real und streng positiv ist, 2. λ >= | m | für jeden anderen Eigenwert m von A, 3. jeder andere positive Eigenvektor von A ist ein Vielfaches von v …
Eine Matrix ist dann irreduzibel, wenn sie entweder die Adjazenzmatrix eines stark verbundenen Graphen ist (salopp: Man kommt von jedem Punkt zu jedem anderen) oder wenn es keine Permutation von Spalten und Zeilen der Matrix gibt, die sie in eine Matrix transformiert, die links unten nur Nullen hat, während sich links oben (darüber) und rechts unten (daneben) quadratische Teil-Matrizen befinden.
Die erste Möglichkeit hört sich schon mal gut an. Sie besagt, dass man in einem gerichteten Graphen entlang der gerichteten Kanten zu jedem Punkt gelangen kann. Gerichtet ist das Web durchaus, Links sind gerichtete Kanten von der Quelle zum Ziel. Allerdings ist das Web nicht stark verbunden, viele Seiten haben keine Links oder werden nicht verlinkt, könnten aber dennoch wichtig sein. Was tun, sprach Zeus?
Hier haben wir wiederum Glück, dass wir das Modell des “Random Surfer” haben. Er beschert uns nämlich die Möglichkeit, von jeder Seite zu jeder anderen zu kommen durch einen zufälligen Sprung. Durch dieses Modell wird aus der Matrix die Adjazenzmatrix eines stark verbundenen Graphen, womit das Theorem anwendbar wird. Der damit verbundene Eigenwert ist 1 (s.o.), es gilt also den Eigenvektor zu bestimmen.
Google nutzt hierbei die Potenzmethode, da sie eine performante Parallelisierung erlaubt. Allerdings ist sie nur bei spärlich (viele Nullen) besetzten Matrizen wirklich gut. Die genannte Matrix hat allerdings keine Nullen mehr. Zum Glück kann man hier leicht Abhilfe schaffen dadurch, dass man das Aufaddieren der Random-Surfer-Matrix verzögert bzw. dadurch, dass die ersetzenden Werte (1/Seitenanzahl) bei einer Seitenanzahl im Internet von mehr als 10 Billionen so gering sind, dass sie wahrlich nahe an Null sind:
H = (1-c)*A + c*S = (1-c)*(A+(1/n)*d*1^T) + c*p*1^T =>
H = (1-c)*A + (1-c)*1/n*d*1^T + c*p*1^T
mit d = 1 für “dangling pages” (also Seiten ohne hereinkommende Links), sonst 0 und 1^T für einen nur mit Einsen besetzten transponierten Vektor.
Es lässt sich ablesen, dass bei der Berechnung die einzig performanzkritische Komponente die Multiplikation (1-c)*A ist, da sie eine Matrix beinhaltet. Die Berechnung des Eigenvektors ist also parallelisierbar: Für jede Multiplikation von Zeile der Matrix mal Vektor bei der Rechnung H*x = x kann ein eigener Rechner verwendet werden. Wie zu sehen war, ist die Potenzmethode anwendbar. Sie ist in meinen Augen eine Brute-Force-Anwendung, denn die Matrix wird so lange mit dem Vektor malgenommen, bis ein Ergebnis ablesbar ist. Die Methode konvergiert recht schnell, allerdings nicht so schnell wie andere Methoden. Eine Tendenz lässt sich schon nach weniger als 10 Schritten feststellen. Google nutzt angeblich 50 Durchläufe. Die Einträge des resultierenden Vektors besagen nun, wie wichtig die einzelnen Seiten sind, ergo ihren “PageRank”.
Wer sich für einen noch tieferen Einblick interessiert, dem sei der Artikel “The $25.000.000.000 Eigenvector” ans Herz gelegt.
Neueste Kommentare