Wie Semager mit PHP Keywords und Beziehungen berechnet und speichert

Semantische Suche
Kommentare

Wie wird die nächste Generation des Internets aussehen? Was wird anders sein und warum? Viele Agenturen, Trendscouts und Informationsarchitekten stellen sich diese Fragen und versuchen, aus ihren Rückschlüssen neue Projekte zu starten, um später, wenn es hoffentlich alle machen, einen Schritt voraus zu sein. Beschäftigt man sich mit diesem Thema, taucht unweigerlich immer wieder der Begriff „semantisches Web“ oder auch „Web 3.0“ auf. Was steckt dahinter?

Tim Berners Lee, der Erfinder von HTML, beschrieb Anfang 2005 das „Semantic Web“ als eine Erweiterung zum bestehenden Web: „Es wäre nicht nur wichtig, Dinge und Seiten miteinander zu verknüpfen, sondern ebenfalls zu beschreiben, auf welche Weise diese miteinander in Bezug stehen.“ Dabei wird durch Metainformationen zugeordnet, ob ein Wort z.B. eine Stadt oder ein Name ist. Es entsteht das „Internet der Dinge“.

Bis es soweit ist, wird es aber noch eine Weile dauern. Das Web entwickelt sich laut Semager in der Zwischenzeit aber schon zum „Web 2.5“ – dem „assoziativen Web“ – ein logischer Zwischenschritt zum semantischen Web. Beim assoziativen Web existieren vielfältige Verknüpfungen zwischen Wörtern von unterschiedlicher Stärke, aber es ist noch nicht bekannt, auf welche Art und Weise die Wörter in Beziehung zueinander stehen. So ist dem assoziativen Web z.B. bekannt, dass „Merkel“ sehr viel mit „Berlin“ zu tun hat. Aber, dass „Berlin“ in diesem Fall eine Ortsangabe ist, ist nicht bekannt. „Berlin“ ist also nur eine Assoziation zu „Merkel“ und keine Semantik.

Vielleicht kennen Sie ja auch diese Wortwolken (Tagclouds). Auf vielen Web-2.0-Seiten (grob gesagt, überall da, wo viele Nutzer nach einer Meinung gefragt und diese in Summe ausgewertet werden) sieht man häufiger eine Ansammlung von Keywords in einer Box. Diese sind zumeist unterschiedlich groß geschrieben und/oder farblich hervorgehoben. Dabei gilt, je größer und je lesbarer die Schrift, umso wichtiger ist das Wort. Meist werden diese Wortwolken im Zusammenhang mit „andere Besucher suchten auch nach“, „beliebte Suchbegriffe“ oder „verwandte Suchen“ genannt.

Die Grundlage für die Wortwolken bildet entweder eine statistische Analyse der eingegebenen Suchbegriffe oder eine Zusammenfassung der von den Benutzern gemachten Verschlagwortung, um z.B. eine bestimmtes Bild, ein Video oder eine Webseite zu beschreiben. Diese Verschlagwortung, auch „Tagging“ genannt, bzw. „Social Tagging“ wenn es viele machen, bildet eine „Folksonomy“ ab (Verschmelzung aus den englischen Wörtern „folk“ und „taxonomies“), die als oben genannte Wortwolke dargestellt wird. Man zählt einfach, wie oft welches Wort eingegeben worden ist, sortiert nach Häufigkeit und stellt die Top-20-Begriffe dar. Ein möglicher PHP-Code könnte dazu wie folgt aussehen:

97, 'testen'=>79, 'testberichte'=>77, 'iq test'=>75, 'testergebnisse'=>69, 'egal'=>50, 'bestanden'=>40, 'durchgefallen'=>20);
$max = max($key_array);
foreach ($key_array as $key => $weight) 
{
	$size = round( log($weight/10, $max/10) *99 *1.5 );
	echo ''.$key.' ';
}
?>

In der ersten Zeile definieren wir ein Array mit Keywords und wie oft nach diesen gesucht worden ist. Diese Daten bekommen Sie am besten, wenn Sie ein eigenes Suchfeld auf Ihrer Webseite haben. Sie speichern die Sucheingaben in einer Datenbank und werten diese z.B. wöchentlich aus. Haben Sie keine Suchfunktion auf Ihrer Webseite, können Sie alternativ auch die Logdateien Ihres Webservers auswerten und analysieren, unter welchen Suchbegriffen Ihre Seite bei Suchmaschinen gefunden worden ist. Anschließend macht das Script eine Schleife durch das Array und berechnet die Größe des aktuell darzustellenden Worts. Häufiger vorkommende Worte werden dabei größer dargestellt. Das Wort, das am meisten vorkommt, hat eine Größe von 150 %. Alle weiteren Werte richten sich logarithmisch danach aus.

Unglücklicherweise geht das Konzept nur dann auf, wenn man genügend Nutzer hat, die viele und sinnvolle Wörter eingeben. Wenn Sie das aber nicht haben und nicht wissen, woher Sie Ihre Keywords bekommen sollen, wird es etwas komplizierter. Ein Ansatz dazu könnte sein, sich seine eigene Keyword-Suchmaschine zu programmieren.

Woher kommen die Keywords

Neben den durch den Benutzer erzeugten Daten gibt es natürlich auch fertige Datenbanken oder APIs, die Sie importieren und nutzen können (z.B. OpenThesaurus, Wordnet). Damit hat man schon einen Grundstock mit dem man Anfangen kann. Wenn Sie sich intensiver damit beschäftigen, werden Sie aber feststellen, dass die genannten Datenbanken zumeist allgemein gehalten sind und sich nur selten mit dem Thema Ihrer Webseite beschäftigen. Entsprechend unpassend sind dann die Zusammenhänge zu Ihrem Internetauftritt. Wenn Sie weitersuchen, werden Sie noch ein paar weitere Anlaufstellen für fertige Keyword-Listen finden, die meisten beschränken sich aber auf Tippfehler oder auf die Suchhäufigkeit bei Suchmaschinen und sind zumeist kostenpflichtig. Um Sie aber nicht ganz im Dunkeln stehen zu lassen, sind hier ein paar interessante Anlaufstellen für Einsteiger: das Google Adwords Tool. Dort finden Sie Suchbegriffe, die Adwords-Betreiber verwenden, um Werbung zu einem bestimmten Sachgebiet zu schalten. Ebenfalls interessant und informativ sind Miva und Yahoo. Beide Seiten zeigen Ihnen nach Eingabe eines Suchbegriffs die Suchhäufigkeit sowie die Anzahl von ähnlichen Suchvorgängen an.

Nachteilig ist, dass Sie diese Daten nicht automatisch abrufen können. Sie können einen guten Überblick über das allgemeine Interesse an bestimmten Suchbegriffen vermitteln und diese Daten dann für sich nutzen. Um es in Ihr Projekt einzubauen, ist es aber leider nicht das Richtige. Außerdem wollen (sollten) Sie ja Ihre eigenen Daten haben und nicht die von anderen einfach Kopieren. Dazu folgender Ansatz:

Sie programmieren einen Crawler, der ein paar tausend Webseiten abruft und speichert und anschließend ein Skript, dass statistische Messungen darüber macht, welches Wort wie oft mit welchem anderen Wort genannt wird, herausgibt. Diese so genannten Kollokationen speichern Sie einfach irgendwo ab. Um sich nicht auf ein paar wenige Domains und Quellen einzuschränken, erhöhen wir die etwa tausend Webseiten auf ein paar Millionen und beachten dabei, dass wir auch nur Webseiten aus der richtigen Sprache durchsuchen. Anschließend analysieren wir nach Kriterien wie HAL (Hyperspace Analogue to Language) und LSI (Latent Semantic Indexing). Beides sind Ansätze im Bereich Semantik, um Verwandtschaften zwischen Dokumenten und Sätzen zu berechnen. Die einfachste Erklärung dazu: „Wörter mit ähnlicher Bedeutung erscheinen in ähnlichen Sätzen.“ Das Ganze wird dann „probalistisch“ (Beschränkung auf Wahrscheinlichkeiten) gewürzt, mit ein paar eigenen Filtern (Stoppworte, Wertigkeiten innerhalb des Dokuments) garniert und schon haben unsere Rechner eine ganze Menge Futter. Um noch Eines obendrauf zu setzten, entwickelte Semager einen eigenen, vollkommen neuen Algorithmus „Neuronales Routing“. Dies soll hier jedoch nicht näher erläutert werden.

Tabelle 1: Beispiel „Kuchen“ (1.976 verwandte Keys)

cellpadding=“2″ cellspacing=“2″> Verwandschaftsgrad Keyword 93 backen 91 Apfelkuchen 89 rezepte 83 torten 75 blechkuchen 74 teig 74 obstkuchen 73 rezept 73 schokoladenkuchen 72 baumkuchen 71 Backrezepte 70 Käsekuchen 68 leckere 66 Backpulver 65 backe 65 kochen 65 Puderzucker 65 Brot

Wenn auch Sie kein Startup mit genügend Risikokapital sind und somit kein Geld für teure Software, Server oder Programmierer haben, könnte z.B. alles unter Linux laufen und einfacherweise mit PHP berechnet werden.

Warum aber PHP und nicht C++ oder Java? Weil es mit den Webprojekten kombinierbar ist. Eine Klasse, die Sie für die Berechnung von Städtenamen im Backend verwenden, kann man mit nur wenigen Handgriffen in eine API verwandeln oder im Frontend als Ausgabemodul einsetzen. PHP ist schnell zu entwickeln und dank seiner Stärken in der String-Verarbeitung für Textanalysen sehr gut einsetzbar. Außerdem ist es kostenlos und perfekt in Apache und Linux integriert.

Zugegeben, es wäre sinnvoller alles z.B. in Python zu programmieren, aber Python-Programmierer sind rar. PHP-Programmierer gibt es dagegen genügend. Zudem werden die Beziehungen ohnehin im Backend auf Servern berechnet, auf denen die Ausführungsgeschwindigkeit letztlich keine Rolle spielt. Es muss nur gewährleistet sein, das im Frontend, dort wo die Daten nachher abgerufen werden, alles möglichst schnell funktioniert. Wichtig ist auch, dass der Code von allen im Team verstanden und erweitert werden kann und dass natürlich qualitativ gute Ergebnisse dabei herauskommen. Die Quantität lässt sich später durch das Hinzufügen weiterer Server regeln.

Zurück zu den Keywords. Wirft man die ganzen Programme zusammen, kommen am Ende Unmengen an Daten und Tabellen heraus. Zu jedem Wort, das existiert, gibt es hunderte, mitunter sogar tausende verwandte Wörter (Tab. 1, die ersten 20 Treffer von insgesamt fast 2.000). Diese müssen alle sortiert und nach unterschiedlichen Sprachen mit weiteren Metainformationen gespeichert werden. Im Schnitt werden derzeit bei Semager pro Minute und Sprache bis zu 800 Beziehungen berechnet. Nicht jede davon ist neu, es gibt auch viele Beziehungen zwischen Wörtern, die sich nur bestätigen. Dennoch ist es ein sehr hohes Datenaufkommen und es stellt sich zurecht die Frage, wie man dieses möglichst schnell und effizient verwalten kann.

Das größte Problem: die richtige Datenbank

Halten mir einmal die Fakten fest:

  • Es soll kostenlose Software verwendet werden.
  • Wir brauchen keine Transaktionen. Wenn einmal ein Datensatz verloren geht, was soll’s.
  • Schreibgeschwindkeit (inserts, updates) ist relativ unwichtig und kann vernachlässigt werden.
  • Die Lesegeschwindkeit ist sehr wichtig (selects).
  • Einfacher Aufbau der Datenbank, keine Joins oder Subselects.
  • Erfahrungsgemäß pro Server ca. 50 GB Datenaufkommen.

Was kommt in Frage?

  • MySQL, immer ein gute Wahl.
  • PostgreSQL, auch eine gute Wahl.
  • SQLite, sehr schnell bei einfachen Abfragen.
  • Lucene, Suchmaschinenindex, sehr schnell zu lesen.
  • Ein paar weitere wie Firebird oder Berkely.

Die grundsätzliche Frage, ob Sie als Datenbankserver MySQL, PostgreSQL oder Firebird einsetzen, ist oft eher eine Entscheidung der persönlichen Vorlieben. Ich persönlich entscheide mich immer für MySQL. Die Erfahrungen in der Administration und der Datenbankanbindung via PHP sind einfach da. Außerdem ist es ein Robustes und zuverlässiges System.

Hauptproblem sind aber die großen Datenmengen. Wie schon erwähnt, gibt es pro Wort im Schnitt ca. 800 Wortverwandtschaften. Pro 100 000 Wörter (und es gibt weit mehr davon) hätten Sie schon 80 Millionen Datensätze. Diese effizient in eine Datenbank zu packen, ist eine Herausforderung. Will man wirklich hunderttausend Tabellen in eine relationale Datenbank wie MySQL anlegen und dort mit jeweils 20-20 000 Einträgen hantieren? Einen Versuch war es Wert. Aber glauben Sie mir, sobald Sie einmal zwei Millionen Datensätze überschritten haben, wird das Ganze schon sehr langsam. Besonders die Updates zwingen den Server in die Knie, da bei jedem Update vorher gesucht werden muss, ob der Key schon existiert. Und eine Installation über mehrere Server hinweg kam aufgrund des TCP/IP Overheads und der Synchronisierungsprobleme auch nicht in Frage. Bei einem weiteren Versuch sollte die Daten stark atomisiert und optimiert in eine einzige Riesentabelle geschrieben werden. Ein Desaster!

Es blieb also nur eine auf dem Filesystem basierende Datenbank, also SQLite und Lucene. Es gibt sicherlich noch viele weitere Ansätze, aber diese alle zu testen und zu vergleichen kostet jede Menge Zeit. Nach einiger Recherche im Internet findet man oft immer wieder diese beiden Systeme. Zudem ist es auch wichtig, dass es eine aktive Community mit Blogs und Foren gibt, die man im Zweifelsfall auch fragen kann.

Lucene ist ein in Java geschriebenes Framework zur Erstellung von Suchmaschinenindices. Der Vorteil von Lucene ist seine enorme Lesegeschwindigkeit. Zudem gibt es Implementierungen für jede wichtige Programmiersprache. So gibt es auch eine PHP-Portierung von Lucene im Zend Framework, die zwar leider nicht an die Geschwindigkeit von Java herankommt, sich aber dennoch sehr gut für eine Suchfunktion innerhalb einer kleinen Webseite eignet. Bei Lucene werden Datenblöcke in eine Datei geschrieben. Pro Datenblock können Daten z.B. im Volltext oder als einzelne Keywords (tokenized) gespeichert werden. Zusätzlich wird definiert, ob diese Daten durchsuchbar (indexed) gemacht werden sollen oder nicht (z.B. für eine cached-Version eines Dokuments). Aufgrund der Architektur von Lucene ist in unserem Fall aber von einem Einsatz als Datenbank abzuraten. Bei Lucene können Daten nämlich nicht so einfach verändert werden. Wie gesagt, es ist auf Lesen optimiert. Bei einem Update muss der betreffende Datenblock erst aus dem Index entfernt werden, dann verändert und anschließend wieder hinten an den Index gehängt werden. Da bei jedem Updatevorgang jedes verwandte Wort in eine spezielle Tabelle geschrieben wird, wäre ein solcher Vorgang sehr festplattenintensiv und das Abspeichern dauert entsprechend lange. Zudem sollte noch der Index nach jedem Update optimiert werden, damit der neue Datenblock in die optimale Position innerhalb des Datenbankfiles geschrieben wird. Zwar findet die Berechnung im Hintergrund statt, trotzdem ist die Schreibrate bei Lucene mit PHP als sehr langsam zu bezeichnen und meines Erachtens in diesem Fall nicht die beste Lösung.

SQLite ist eine embedded Datenbank und kommt ohne Server aus. Sie ist sehr klein und kann fest in PHP integriert werden. Da es keinen Server gibt, legt SQLite für jede Datenbank eine eigene Datei an. Durch einfaches Kopieren der Datei auf einen anderen Server ist die komplette Datenbank damit ebenfalls kopiert und kann dort wiederum gelesen und verändert werden. Größter Nachteil ist: Wenn Daten geschrieben werden, ist die Datei und somit die Datenbank für Lesezugriffe gesperrt. Ein Vorteil wiederum ist die sehr schnelle Bearbeitung von einfachen Schreib- und Lesezugriffen. Bei Anfragen, die nur eine Tabelle betreffen, ist SQLite sogar fast doppelt so schnell wie MySQL.

Im Falle der Keyword-Listen ist SQLite eine ideale Lösung. Mit ihr lässt sich für jedes Keyword eine einzelne Datenbank anlegen und die verwandten Wörter darunter abspeichern. Das Problem dabei ist nur zu wissen, welche Wörter schon berechnet worden sind und welche noch nicht. Für diesen Zweck haben wir eine MySQL-Datenbank angelegt. Sie merkt sich, welche Wörter bereits berechnet worden sind und wo diese als SQLite-Datei abgelegt wurden. Daneben lassen sich noch weitere Metainformationen ablegen (z.B. ob das Wort eine Stadt oder ein Name ist), sodass die SQLite-Datenbank nur dann geöffnet werden muss, wenn diese auch wirklich benötigt wird. Einen Flaschenhals bilden bei dieser Konstruktion die Festplatten. Das System ist sehr stark von den Zugriffsgeschwindigkeiten der Platten abhängig, da ständig Dateien geöffnet und geschlossen werden. Zum Glück laufen im Backend aber keine zeitkritischen Anwendungen, sodass hier mit einem normalen RAID 5 gearbeitet werden kann. Die Zugriffsgeschwindigkeiten sind für Berechnungen ebenfalls absolut ausreichend. Sogar mehr als das, so lässt sich das Backend im Notfall auch als Failover für das Frontend nutzen. Im Frontend selbst, dort wo die Daten primär von Benutzern abgerufen werden, sorgt ein RAID 0 über 4 Platten mit 15 000 U/Min und einem guten SCSI Controller für den nötigen Vorschub. Zwar ist das nicht besonders sicher, und falls eine Platte ausfallen sollte sind alle Daten weg, aber sie lassen sich vom Backend schnell wieder aufspielen. Als Filesystem wurde in allen Fällen XFS gewählt (Abb. 1).

Abb.1: Ausschnitt aus der zentralen Datenbank mit Keyword, Speicherort der SQLite-Datei und Metainformationen
Performance-Tweaks

Wie holt man die maximale Geschwindigkeit aus PHP raus?

Schritt 1, man compiliere sich sein Linux und seine Dienste selbst. Anstatt einen Kernel und Daemons zu benutzen, die auf jedem x86er-Rechner laufen würden, lädt man sich den Sourcecode und kompiliert alles von Hand – optimiert auf seine jeweilige Prozessorarchitektur. Gentoo erleichtert einem damit die Arbeit. Das Linux-Derivat setzt auf die maximal erreichbare Ausführungsgeschwindigkeit von Programmen. Zu diesem Zweck konfiguriert man eine einzelne Datei (/etc/make.conf) und teilt dem System mit, welchen Prozessor man benutzt. Profis können noch weitere Compiler Flags setzten und weiter optimieren (pointer und pipes). Anschließend werden alle Pakete als Quelldateien geladen und zu ausführbaren Programmen übersetzt. Je nach Prozessorarchitektur können dadurch große Geschwindigkeitsvorteile gegenüber nichtoptimierten Systemen entstehen. Beim Übersetzen werden nämlich die Besonderheiten und Befehlssätze der verwendeten CPU beachtet, wohingegen ein generisch ausführbares Programm nur den kleinsten gemeinsamen Befehlssatz aller Prozessoren verwenden kann.

Im zweiten Schritt betrachten wir die Schnittstelle zwischen PHP und Datenbanken im Allgemeinen. Ich kann Ihnen nur empfehlen, nutzen Sie PDO! Aber bitte fest in PHP einbinden und nicht als PECL-Extension nutzen. Außerdem sollten Sie sich Ihre eigene Datenbankklasse schreiben und von der Verwendung von z.B. AdoDB oder Pear::DB absehen. Machen Sie sich stattdessen ein kleines und vor allem schnelles eigenes Skript, nur mit dem was Sie wirklich brauchen. Es zahlt sich auf Dauer aus.

Der kostenlose eAccelerator ist ein Programm, um die Geschwindigkeit von PHP-Anwendungen zu steigern. Dazu speichert der eAccelerator den kompilierten Bytecode des PHP-Programms im RAM. Dies wirkt sich besonders bei komplexen Webseiten mit vielen includes aus. Die ganze Webseite kann so um bis zu 500 % schneller werden.

Beim Programmieren mit Arrays verwenden viele gerne die foreach-Schleife. In manchen Fällen ist es aber sinnvoller array_walk oder array_map einzusetzen. Hinweise dazu finden Sie genügend im Web. Am besten Sie schreiben sich ein kleines Testprogramm und messen die Ausführungsgeschwindigkeit der unterschiedlichen Befehle, in dem Sie es z.B. 10 000 mal ausführen. Das könnte z.B. folgendermaßen aussehen:

$time = get_microtime();
for ($i=1; $i

PHP mag vielleicht nicht in allen Fällen die ideale Programmiersprache sein, aber mit ein bisschen Optimierung ist es fast immer eine gute Wahl. Besonders für Programmierer, die PHP sehr gut beherrschen und nicht unbedingt eine weitere Programmiersprache lernen wollen, lässt sich viel herausholen. Problematisch wird es nur, wenn mehrere Skripte parallel laufen sollen. In diesem Fall sollte man wirklich z.B. auf Python ausweichen.

Matthias Schneider ist Gründer und Geschäftsführer von Semager und entwickelt und vertreibt semantische Datenbanken.

Unsere Redaktion empfiehlt:

Relevante Beiträge

Meinungen zu diesem Beitrag

X
- Gib Deinen Standort ein -
- or -