Der PageRank-Algorithmus

Der PageRank-Algorithmus wurde, 1995 bis 1998, von Larry Page und Sergey Brin an der Stanford Universität entwickelt.

Der Algorithmus beschreibt ein Verfahren, dass verlinkte Dokumente für einen Suchindex gewichtet.

Die kommerzielle Websuchmaschine Google , die zur Zeit den größten Marktanteil aufweisen kann, verwendet den PageRank-Algorithmus als Grundlage für die Bewertung der Suchergebnisse.

Er ist einer der wesentlichen Innovationen, die Google, innerhalb weniger Jahre von einer von zwei Studenten gegründeten Firma zum Milliardenunternehmen machte.

In The PageRank Citation Ranking: Bringing Order to the Web beschreibt Larry Page zwei Annahmen auf denen der Algorithmus basiert:

Web pages vary greatly in terms of the numbers of backlinks they have. For example, the Netscape home page has 62,804 backlinks in our current database compared to the most pages which have just a few backlinks. General ly, highly linked pages are more ”important” than pages with a few links. […] For example, if a web page has a link off the Yahoo home page, it may be just a link but is a very important one. This page should be ranked higher than many pages with more links but from obscure places. (Page u. a. 1998, S.3)

 

Dies bedeutet, dass Webseiten die häufig verlinkt sind „wichtiger“ angesehen werden als solche, die nur wenige Verlinkungen aufweisen. Die zweite Annahme: Seitenlinks mit einem hohen PageRank sind potenziell „wichtiger“ als Links von Seiten mit einem niedrigerem Pagerank.

Wichtigkeit wird ausdrücklich nicht definiert und ergibt sich aus den Verlinkungen. Somit kann eine Implementierung des PageRank-Algorithmus als soziale Software betrachtet werden, sofern man das setzen eines Links als soziale Interaktion betrachten möchte.

Berechnung des Pagerank

Der PageRank-Algorithmus wurde von den Google Gründern in mehreren, unterschiedlichen Varianten beschrieben. Die folgenden Erklärungen beziehen sich auf die Beschreibung in The PageRank Citation Ranking: Bringing Order to the Web (Page u. a. 1998, S.4).

Der PageRank einer Webseite u wird als R'(u) bezeichnet. Der Dämpfungsfaktor c dient zur Normalisierung und muss zwischen Null und Eins liegen. Zur Berechnung des PageRanks von u werden die PageRank-Werte aller auf u zeigender Webseiten Bu durch ihre ausgehenden Links Nv dividiert und aufsummiert.

R(U) dient lediglich zum Ausgleich von PageRank-Senken, die durch ungünstige Kombinationen von Verlinkungen entstehen können.

 

 

R'(u) = Ranking der Webseite u

R'(v) = Ranking der Webseite v

c = Dämpfungsfaktor für den gilt: 0 < c < 1

Bu = Anzahl der Seiten mit Links zur Webseite u

Nv = Anzahl der abgehenden Links von v

E(u) = Faktor zur Verhinderung von PageRank-Senken

Ruby

A few years ago, I came across the Ruby programming language, and I fell in love. Somehow, it just seemed to work the way my brain works—I can express myself in Ruby more naturally and with less intervening fluff than in any other language I know. […] And now, for the first time, I can seriously say that Ruby is ready for the enterprise. The language is stable, the libraries are great, and there is a growing pool of talented and enthusiastic Ruby developers, all rising to the challenge. Dave Thomas (Schmidt 2006, Foreword)

 

Ruby ist eine Programmiersprache, die 1995 von dem Japaner Yukihiro Matsumoto veröffentlicht wurde. Sie wurde durch die Sprachen Perl, Eiffel, Ada, Smalltalk und Lisp inspiriert. Die herausragenden Eigenschaften von Ruby sind:

  • Vollständige Objektorientierung. Es existieren keine einfachen Datentypen.
  • Die durch Lisp inspirierten Closures erlauben mächtige Operationen.
  • Ruby Mixins, die eine elegante Art der Mehrfachvererbung darstellen.
  • Das dynamische Typsystem, das große Flexibilität ermöglicht.
  • Die Ausbalancierung zwischen funktionaler und imperativer Programmierung.

Suchmaschinen

Eine Suchmaschine ist eine Software, die Verfahren des Information Retrieval implementiert. Sie dient zur Informationsfilterung von Dateien, die in einem Computersystem abgelegt sind. Eine Suchmaschine erstellt einen Index für die Datenbasis, um Suchanfragen für jeden Suchbegriff mit einer nach Relevanz geordneten Ergebnisliste zu beantworten. Dieser Index ist vergleichbar mit einem Index-Objekt eines Datenbanksystems. Nach Eingabe eines Suchbegriffes zeigt die Suchmaschine eine Liste mit Verweisen auf relevante Dokumente. Meistens werden die Suchergebnisse mit dem Titel des Dokuments und einem mit dem Suchbegriff enthaltenen Auszug aus dem Dokument dargestellt. Suchmaschinen haben drei wesentliche Aufgabenbereiche: 

  • Generierung, Aktualisierung und Optimierung einer Datenstruktur mit Informationen über die zu durchsuchenden Dokumente. Diese Datenstruktur wird Index genannt.
  • Verarbeitung der Suchanfragen und ordnen der Ergebnisse anhand der Relevanz des indizierten Dokumentes zum Suchbegriff.
  • Aufbereitung und Darstellung der Ergebnisse in einer Form, die vor allem den Kriterien: Erwartungskonformität, Aufgabenangemessenheit und Selbstbeschreibungsfähigkeit entspricht.

Nach der von Jakob Nielson erstellten und zuletzt im Jahr 2007 aktualisierten Liste mit den zehn schlimmsten Fehlern im Webdesign ist eine schlechte Suche der zurzeit am Häufigsten gemachte Fehler auf Webseiten. In Search: Visible and Simple beschreibt Jakob Nielsen die Gründe, warum Anwender Suchfunktionen auf Webseiten erwarten. Diese sind:

  • Anwender wollen nicht die Navigation einer Seite benutzen. Sie wollen nur das finden, was sie interessiert.
  • Die Suche bietet einen Ausweg wenn sich die Anwender in der Navigationsstruktur verloren fühlen und nicht weiter wissen.

Daraus ergibt sich, dass auf größeren Webauftritten eine Suchmaschine, aus Gesichtspunkten der Usability, ein unverzichtbarer Bestandteil ist. Jedoch ist die Implementierung einer Volltextsuchmaschine und die sinnvolle Gewichtung der zu durchsuchenden Inhalte sehr aufwendig.

Stammformreduktion

Als Stammformreduktion bezeichnet man im Information Retrieval ein Verfahren, mit dem verschiedene Varianten eines Wortes auf ihren gemeinsamen Wortstamm zurückgeführt werden. So sollen bei einer Suche nach test auch Ergebnisse zu finden sein, die zum Beispiel die Begriffe tested, tests oder testing enthalten.

Zur Stammformreduktion gibt es unterschiedliche Algorithmen für verschiedene Sprachen. Die Entwicklung eines Algorithmus zur Stammformreduktion ist eine experimentelle Wissenschaft, da dieser nicht mathematisch verifiziert werden kann, sondern an realen Texten getestet werden muss.

Man verfolgt mit der Stammformreduktion zwei Ziele:

  1. Durch das Zusammenführen verschiedener Wortformen zu einem Wort tritt dieses tendenziell häufiger auf. Es sollten deshalb mehr Dokumente bei einem Suchbegriff gefunden werden.
  2. Durch die Zusammenführung verschiedener Wortformen zu Einem, werden Listen mit Verweisstrukturen auf die zu indizierenden Dokumente kleiner, da weniger Wörter verwaltet werden müssen.

Stammformreduktion ist immer sprachenabhängig, da je nach Sprache unterschiedliche grammatikalische Regeln für Wortkomposition, Flexion und das Hinzufügen von Affixen (Präfix, Suffix und Infix) gelten, die unterschiedliche Algorithmen erfordern.

Kandelmarsch 2008

Der 86. Kandelmarsch fand im Rahmen der Absolventenverabschiedung der Hochschule Esslingen am 25. Juli 2008 statt. Dabei ziehen die Absolventen der Hochschule Esslingen mit Frack, Zylinder und einer Holzleiter durch die Esslinger Innenstadt. Wie im Jahr 1922 marschieren die Befrackten im Kandel – immer ein Fuß auf dem Gehweg und einer auf der Straße.

Die Hochschule hat auch einen Bericht über den Kandelmarsch ins Netz gestellt.

Information Retrieval

Information Retrieval (IR) ist ein Fachgebiet der Informatik, das die inhaltliche Suche nach Informationen in Dokumentensammlungen untersucht und Modelle, Methoden und Verfahren dafür entwickelt. Der Begriff Information Retrieval wurde 1950 von dem amerikanischen Informatikpionier Calvin Northrup Mooers geprägt. Es existiert keine eindeutige Definition des Begriffes. Die Fachgruppe Information Retrieval der Gesellschaft für Informatik beschreibt den Begriff folgendermaßen:

Im Information Retrieval (IR) werden Informationssysteme in Bezug auf ihre Rolle im Prozess des Wissenstransfers vom menschlichen Wissensproduzenten zum Informations-Nachfragenden betrachtet. Die Fachgruppe „Information Retrieval“ in der Gesellschaft für Informatik beschäftigt sich dabei schwer- punktmäßig mit jenen Fragestellungen, die im Zusammenhang mit vagen Anfragen und unsicherem Wissen entstehen. Vage Anfragen sind dadurch gekennzeichnet, dass die Antwort a priori nicht eindeutig definiert ist. […] Aus dieser Problematik ergibt sich die Notwendigkeit zur Bewertung der Qualität der Antworten eines Informationssystems, wobei in einem weiteren Sinne die Effektivität des Systems in Bezug auf die Unterstützung des Benutzers bei der Lösung seines Anwendungsproblems beurteilt werden sollte (Gesellschaft für Informatik).

 

Diese Definition ist sehr allgemein gehalten. Es wird die Vagheit oder Unschärfe betont. Zur Bewertung soll die Nützlichkeit herangezogen werden. Es wird also versucht, aus gespeichertem Wissen in Form einer Datenbasis den Informationsbedarf eines Benutzers zu befriedigen. Dabei spezifiziert der Benutzer eine Anfrage, die die erwartete Antwort nur grob charakterisieren muss. Das IR-System versucht dann diejenigen Informationen in der Datenbasis ausfindig zu machen, die Relevanz für diese Anfrage aufweisen. Dabei können eventuell mehrere Benutzerinteraktionen notwendig sein, bis ein endgültiges Ergebnis vorliegt. Zur Bewertung der Ergebnisse hinsichtlich ihrer Relevanz ist ein Bewertungsverfahren nötig, mit dem sich die Qualität der Ergebnisse feststellen lässt.