Advitum.de auf Google+

Wie eine einfache Tagcloud zur schlafraubenen Hürde wird

Wie eine einfache Tagcloud zur schlafraubenen Hürde wird
VN:F [1.9.22_1171]
Bewertung: 4.5/5 (2 Stimmen abgegeben)
Von am
Kategorien: Arbeit, Design, JavaScript, jQuery, 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?

Wie eine einfache Tagcloud zur schlafraubenen Hürde wird, 4.5 out of 5 based on 2 ratings

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 400×300 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 400×300 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.

Das Ergebnis sieht zu linear aus
Das Ergebnis des Algorithmus sieht viel zu linear und unzufällig aus.

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.

Die Tags sind viel zufälliger verteilt
Durch die zufällige Auswahl des Startpunktes sind die Tags viel besser verteilt.

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 400×300 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.

Mein Wordle im Vergleich zum Original
Im direkten Vergleich zum Original (rechts) weist mein Wordle (links) 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.

Wie eine einfache Tagcloud zur schlafraubenen Hürde wird, 4.5 out of 5 based on 2 ratings

Jetzt seid ihr dran!

Teilt eure Meinung mit uns in den Kommentaren, gebt eine Bewertung für diesen Artikel ab und teilt ihn in Social Networks!

Über

Ich bin ein junger Webdesigner und Programmierer aus Siegen und blogge auf Advitum.de über meine Erfahrungen im Web. Meine Themenschwerpunkte liegen im Bereich der Web-Entwicklung mit PHP, JavaScript, HTML und anderen Script-, Programmier- und Markup-Sprachen, der Nutzung von Content Management System wie Typo3, Wordpress etc. und der Effekt-Hascherei mit Photoshop. Seit 2008 blogge ich auf Advitum.de – mal mehr, mal weniger regelmäßig – über alles, was mich so interessiert. Wenn dir mein Blog gefällt, freue ich mich immer sehr über Feedback in Form von Kommentaren und E-Mails.

Kommentare zu diese Artikel

Schreibe jetzt einen Kommentar!

Michael schrieb am Antworten

Hi Lars,

und bist Du schon weiter gekommen? Hast Du das Problem schon in den Griff bekommen? Ich kann zu deinem Problem allenfalls ein paar Anregungen geben.

Kannst Du den Raum für die Kollisionsberechnungen nicht sukzessiv eingrenzen, damit du nicht so viele Schleifendurchläufe benötigst. Kannst Du nicht die größte zusammenhängende Fläche einer Farbe berechnen! Muss man jeden einzelnen Pixel überprüfen? Könnte man nur jeden zweiten, dritten oder vierten Pixel überprüfen?

Aber bestimmt, hast Du darüber schon nachgedacht.

Ich finde deinen dynamischen Ansatz schon Klasse.

Viele Grüße

    Lars Ebert schrieb am Antworten

    Hi Michael,

    die Idee, nur jeden x-ten Pixel zu prüfen, habe ich schon eingebaut, in meinem Script wird in X- und Y-Richtung nur jeder 6te Pixel überprüft. Nachteil ist allerdings, dass dadurch größere Lücken zwischen den Tags entstehen, dafür habe ich aber 36 mal weniger Schleifendurchläufe.

    Die Idee mit der zusammenhängenden Fläche finde ich gar nicht schlecht, ich weiß aber nicht, wie ich das mit JavaScript realisieren könnte.

    Insgesamt wäre es mir sowieso lieber, die Erstellung mit PHP zu machen, aber mein Problem war dabei, dass ich nicht genau wusste, wie man die genauen Größen der einzelnen Tags mit PHP ermitteln kann. Diese könnten doch von Browser zu Browser variieren.

    Alternativ könnte man ja noch vom Server (also mit PHP) ein Bild rendern lassen, die Position und Größe der Tags übermitteln und mit JavaScript über jedem Tag einen transparenten Link platzieren. Glaubst du, das lässt sich realisieren?

Michael schrieb am Antworten

Hi,

okay du überprüfst jeden 6-ten Pixel ==> Problem: Gleichverteilung ==> Lsg: Zufallszahl (1,6)?

man könnte das Bild ja in der Datenbank speichern als „mediumblob“ und irgendwie auswerten?

Das mit PHP rendern, da hab ich auch mal was gelesen. Da kann man ja dann auch den Winkel des Schriftszugs bestimmen.

    Lars Ebert schrieb am Antworten

    Stimmt. Ich bleibe auf jeden Fall an dem Problem dran. Wenn es etwas neues gibt, erfahrt ihr das hier!

Heinz-Günter Weber, 7media Webdesign schrieb am Antworten

Nur mal laut gedacht. Ich nehme an, du zählst zunächst die Vorkommen der Worte für die Tagcloud, um die unterschiedlichen Größen berechnen zu können (falls es von der Anzahl des Vorkommens von Worten auf einer Website abhängen sollte, sonst Zufall). Ich weis nicht wie das in JS zu machen wäre, in PHP schon eher. Die am meisten vorkommenden Worte sind bei Dir noch nicht so viel größer als beim Beispiel-Wordle. Die zwei, drei größten könntest Du dann relativ zentral platzieren (z.B. nur von Pixel x bis Pixel y erlauben), noch ohne Kollionsberechnung. Die nächsten 2-3 dann etwas kleiner, evt. auch ohne Kollisionsberechnung, nur platziert neben den ersten (ähnlich wie Beispiel). Dann wieder die nächsten, diesmal evt. 5, mit Kollisionsprüfung, aber auch nicht mit allen Pixeln sondern z.B. nur da wo sie hochkant oder quer auch hinpassen würden (wenn 70px Breit, dann nur bis x-Achse -70). Danach dann die weiteren Lücken füllen. Aber wahrscheinlich hast Du Dir das alles schon selber so gedacht 🙂 Wie macht das Wordle? Mit viel Rechenpower?

    Lars Ebert schrieb am Antworten

    Ja genau, bei Wordle ist nicht JavaScript sondern Java am Werk, aber die Erstellung der Grafik dauert auch Recht lange. Deshalb ist das für eine dynamische Erzeugung auch nicht zu gebrauchen.

    Momentan bin ich soweit, das ganze als Grafik von PHP erzeugen und chachen zu lassen und dann mit JavaScript transparente Links drüber zu legen. Aber ich bin damit noch lange nicht fertig, wenn es was neues gibt, schreibe ich auch einen neuen Artikel.

Axel Michel schrieb am Antworten

War heute auf der Suche nach einer Wordle-ähnlichen echten, heisst voll funktionalen, Tagcloud. Bin zunächst über Deinen Artikel gestolpert und habe mir Dein Beispiel angesehen. Nicht schlecht – aber bevor Du – und andere ggf. weitere Stunden in das Script investieren – schau mal hier: d3 cloud Jason Davies hat auf Basis von d3 eine beindruckende Lösung gebaut. Seine Demo macht einfach nur Spass und ist eine wirklich perfekte Portierung der Wordle Anwendung in JavaScript.

    Lars Ebert schrieb am Antworten

    Vielen Dank! Die Demo ist echt genial und macht Spaß. Ich werd mal schauen, wie das ganze funktioniert. Danke!

Diese Artikel könnten dir auch gefallen