Wie eine einfache Tagcloud zur schlafraubenen Hürde wird
Kategorien: Arbeit, Design, JavaScript, jQuery and Programmieren
Letzte Woche bekam ich von einem Designer ein Design für eine Internetseite vorgelegt, in der er ein Wordle zur Darstellung der häufigsten Suchbegriffe benutzt wurde. Ein Wordle zu erstellen ist im Grunde ganz einfach, gibt es dafür doch eine einfache Online-Anwendung. Einziger Nachteil: jedes Mal, wenn sich die Begriffe ändern, muss das Wordle von Hand neu erzeugt werden. Da in meinem Fall die Wörter jedoch dynamisch erzeugt werden, stellt dies eine echte Hürde dar.
Auf den ersten Blick erschien mir JavaScript für diese Aufgabe am geeignetsten, auf den zweiten Blick auch, also machte ich mich an die Arbeit und schrieb ein kleines jQuery-Plugin - zumindest dachte ich, es würde ein kleines Plugin werden. Doch schnell tauchten die ersten Probleme auf. Ich konnte zwar recht einfach mit outerWidth() und outerHeight() die Größe, die das Wort brauchen würde, ermitteln, aber wie sollte der Algorithmus aussehen, der diese dann platziert?
Mit dem Kopf durch die Wand
Mangels einer guten Alternative entschied ich mir für das Motto »Trial and Error«. Um einen passenden Platz für das Schlagwort zu finden, laufen zwei verschachtelte Schleifen jede Zeile und jede Spalte Pixel für Pixel durch und führt einen Kollisionstest mit allen bisher platzierten Schlagworten durch. Die erste getestete Position ist also (0|0), die zweite (1|0) und so weiter.
Wenn der neue Tag mit einem bereits platzieren Tag kollidiert, dann wird zur nächsten Position gesprungen. Wenn keine Kollision gefunden wurde, passt der Tag an die gewählte Position und bleibt dort. Und wenn keine Position gefunden werden kann, wird der Tag einfach gar nicht angezeigt.
Dieser Algorithmus ist nicht besonders intelligent und auch sehr langsam. Dies ist auch der größte Nachteil an dem Algorithmus. Wenn das Wordle zum Beispiel 400x300 Pixel groß werden soll, müssen für jedes Schlagwort 120.000 Positionen überprüft und für jede dieser Positionen eine Kollisionsprüfung für jeden bisher platzieren Tag machen.
Bei dem ersten Tag wirkt sich keiner der beiden Nachteile aus, da die erste Position garantiert frei ist und keine einzige Kollisionsprüfung durchgeführt werden muss, es sind nämlich noch gar keine anderen Tags da, die die Position versperren oder eine Kollisionsprüfung nötig machen würden. Es wird also nur ein Schleifendurchlauf mit null Kollisionsprüfungen durchgeführt.
Je mehr Tags jedoch schon platziert wurden, desto schwieriger wird es, einen geeigneten Platz für den Tag zu finden und desto mehr Kollisionsprüfungen müssen durchgeführt werden. So werden, benutzt man unsere Beispielmaße von 400x300 Pixeln, bis zu 120.000 Schleifendurchläufe benötigt, bevor eine Position gefunden wird, und bei jedem einzelnen Schleifendurchlauf müssen wieder für jeden bereits platzierten Tag eine Kollisionsprüfung durchgeführt werden.
Lange Rede, kurzer Sinn - dieser Trial-and-Error-Algorithmus ist unannehmbar langsam. Wenn jemandem ein besserer Ansatz für diesen Algorithmus einfällt, würde ich mich über einen Kommentar oder eine Mail sehr freuen.
Ein weiterer Nachteil an dem Algorithmus ist das nicht besonders zufriedenstellende Ergebnis. Da bei jedem Tag wieder von der oberen linken Ecke angefangen wird, häufen sich dort lineare Ansammlungen von Tags.
Um diesem Nachteil entgegenzuwirken, habe ich für jeden Tag die Anfangsposition zufällig gewählt. Das Ergebnis wirkt viel zufälliger und nicht so oben-links-gewichtig.
Komm mir nicht in die Quere
Viel zeitaufwändiger als die vielen Schleifendurchläufe sind die vielen Kollisionsberechnungen. Nehmen wir mal an, wir haben 100 Tags in einer Fläche von 400x300 Pixeln zu platzieren. Für den letzten Tag werden dann im Extremfall 120.000 Schleifendurchläufe und pro Schleifendurchlauf 99 Kollisionsberechnungen nötig, also insgesamt 11.880.000 oder anders gesagt fast zwölf-Millionen Kollisionsberechnungen nötig.
Vor der Optimierung der Kollisionsberechnungen dauerte das Rendern des Wordles bei mir immer mindestens 60 Sekunden, meistens sogar noch viel länger. Dies ist der Knackpunkt in dem Algorithmus, weshalb ich mich lange mit der Optimierung von Kollisionsberechnungen beschäftigt habe.
Also habe ich mir viele Artikel und wissenschaftliche Arbeiten zum Thema Bounding Volume Hierarchies durchgelesen und war schnell davon überzeugt, dass dies mir weiterhelfen könnte. Bounding Volume Hierarchies sind viel zu kompliziert, um sie in diesem Artikel »mal eben so nebenbei« zu erklären, deshalb findet sich am Ende des Artikels eine kleine Liste mit weiterführenden Links zum Thema Bounding Volume Hierarchies.
Ich habe jedenfalls mit Bounding Volume Hierarchies meine Kollisionsberechnungen optimiert und konnte so eine Beschleunigung des Algorithmus erreichen, mit der ich gar nicht gerechnet hatte. Statt anfänglicher 60 Sekunden Renderzeit konnte ich mit Bounding Volume Hierarchies eine Bestzeit von 10 bis 15 Sekunden erreichen.
Ein ganz neuer Ansatz?
Trotz dieser Verbesserung bin ich mit dem Ergebnis noch nicht zufrieden. Im direkten Vergleich mit dem Original-Wordle weist mein Wordle noch einige Schönheitsfehler auf.
Leider kann ich mit JavaScript nicht die Leerräume optimal füllen und ich vereinfache jedes Wort einfach zu einem Rechteck. Meiner Meinung nach könnte man hier auch noch einiges verbessern, aber ich stecke mittlerweile zu tief in dem Problem, um es vernünftig zu abstrahieren. Mit anderen Worten: ich hänge irgendwie fest.
Mein Zwischenstand - jetzt seid ihr dran!
Wie schon erwähnt, habe ich das Ganze in ein jQuery-Plugin verpackt. Wenn ihr Interesse daran habt, könnt ihr den Quellcode und eine funktionierende Demo herunterladen.
Das Plugin könnt ihr beliebig weiter verbreiten, verändern oder kopieren. Bitte verweist aber bei einer Veröffentlichung auf diesen Artikel. Und ich würde mich freuen, wenn ihr die Ergebnisse mit mir teilt. Vielleicht bringt mich das ja der Lösung des Problems näher.
Mir raubt diese Tagcloud bis heute den Schlaf, vielleicht habt ihr ja mehr Glück.
Links zum Thema »Bounding Volume Hierarchies«
Diesmal sind die Links zum Thema wirklich nur was für die ganz Harten. Alle in Englisch, teilweise schwer verständlich. Aber absolut empfehlenswert ist der erste Link, dort werden Bounding Volume Hierarchies relativ gut erklärt.