einzelnes Zeichen aus Dokument zufällig auswählen

[wahsaga]

hi,

für eine optische Spielerei möchte ich ein einzelnes Zeichen aus dem Textinhalt eines Dokumentes zufällig auswählen und gesondert formatieren. Dies soll darüber hinaus mehrmals hintereinander geschehen (zeitverzögert). Berücksichtigt werden sollen natürlich nur "sichtbare" Zeichen, also kein Whitespace, und ein bereits vorher derart selektiertes Zeichen soll natürlich später nicht erneut behandelt werden.

Erst mal aus allen Textknoten zufällig einen auswählen, und aus diesem dann zufällig ein Zeichen auszuwählen ergibt keine Gleichverteilung der Wahrscheinlichkeit für die Auswahl eines Zeichens, da Textknoten natürlich unterschiedlich lange Inhalte haben.

Ich sehe bisher zwei Möglichkeiten:

Möglichkeit 1:

• Gesamtzahl aller (relevanten) Textzeichen wird ermittelt - Knotenstruktur wird einmal rekursiv durchlaufen, um die Gesamtanzahl der Zeichen zu ermitteln.
• Zufallswert x ermitteln, 0 <= x < Gesamtanzahl Zeichen
• Anschließend Knotenstruktur noch einmal rekursiv durchlaufen, dabei "mitzählen", und abbrechen wenn der Textknoten erreicht wurde, der das x-te Zeichen enthält.

Vorteil: Einfach zu implementieren, durch erneutes rekursives Durchlaufen bei jedem Aufruf stellt auch die Nicht-Berücksichtigung bereits behandelter Zeichen kein größeres Problem dar.
Nachteil: Höchst unperformant.

Möglichkeit 2:

• Knotenstruktur einmal rekursiv durchlaufen, dabei in einem Array die Referenz auf jeden Textknoten ablegen sowie die Anzahl der Zeichen des aktuellen Textknotens plus der der Vorgänger.
• Anschließend "gewichtete" Zufallsauswahl nach der Anzahl der Zeichen: Zufallswert 0 <= x < Gesamtanzahl Zeichen; In Schleife Array so lange durchlaufen, wie gespeicherte Anzahl der Zeichen < Zufallswert.

Vorteil: Performanter, wenn Array mit Textknoten nur einmal ermittelt werden müsste.
Nachteil: Zum gesonderten Formatieren eines einzelnen Zeichens werden die Textknoten gesplittet, Zeichen als neuer Textknoten mit einem Span umgeben - Resultat: Ein Textknoten mit einem Zeichen, der aus dem Array entfernt werden müsste, um dieses Zeichen nicht erneut behandeln zu müssen. Bis zu zwei neue Textknoten (vor/nach ausgeschnittenem Zeichen), die an die richtige Position ins Arrays eingefügt werden müssten. Anschließend Neuberechnung der "Anzahl Zeichen bis zu diesem Knoten einschließlich" für alle nachfolgenden Textknoten nötig. Erfordert nicht unbedingt erneutes rekursives Durchlaufen des DOM-Baumes, sollte durch Dekrementierung der Werte für alle nachfolgenden Textknoten um eins erreichbar sein.

Beide Möglichkeiten nicht sonderlich schön bzw. "effektiv".
Möglichkeit 2 aufwendiger in der Implementierung, dafür etwas performanter.
Zusätzlicher Nachteil Möglichkeit 2: Es werden vermutlich neue Inhalte per AJAX hinzugeladen werden, da müsste also auch bei dieser Möglichkeit das Array neu aufgebaut werden, wenn diese neuen Inhalte bei der nächsten Auswahl mitberücksichtigt werden sollen (dynamische Erweiterung des Arrays um die hinzugekommenen Textknoten wird mir zu aufwendig in der Implementierung).

Fällt jemandem noch eine "einfachere", performantere Möglichkeit ein?

innerHTML stellt keine Alternative dar - abgesehen davon, dass man da mit ebenfalls unperformanten regulären Ausdrücken oder einem eigenen Parser Tags von Textinhalt trennen müsste, würden Entities ein weiteres Problem darstellen - &gt; sind vier Zeichen, die ein sichtbares Zeichen repräsentieren.

gruß,
wahsaga

[Felix Riesterer]

Lieber wahsaga,

für eine optische Spielerei möchte ich ein einzelnes Zeichen aus dem Textinhalt eines Dokumentes zufällig auswählen und gesondert formatieren.

Du machst Sachen... Na, dann viel Spaß! (Krass!)

Liebe Grüße aus Ellwangen,

Felix Riesterer.

[agapanthus]

Moin.

Möglichkeit 1:

Wenn Du die Aufgaben auf Server und Client verteilst?

• Gesamtzahl aller (relevanten) Textzeichen wird ermittelt -

Das macht der Server und liefert die Gesamtzahl beim Ausliefern der Seite mit. Somit sparst Du auf Clientseite einen Durchlauf. Aber ob das insgesamt performanter ist...?

• Zufallswert x ermitteln, 0 <= x < Gesamtanzahl Zeichen
• Anschließend Knotenstruktur noch einmal rekursiv durchlaufen, dabei "mitzählen", und abbrechen wenn der Textknoten erreicht wurde, der das x-te Zeichen enthält.

Gruß Frank

[wahsaga]

hi,

Wenn Du die Aufgaben auf Server und Client verteilst?

Dann müsste ich also serverseitig parsen bzw. ein (XML-)DOM durchlaufen.

Außerdem optionale clientseitige, Javascript-basierte Spielerei - da möchte ich nicht den Server mit belästigen.

gruß,
wahsaga

[molily]

Hallo,

ich habe auf die Schnelle auch keine Patentlösung, aber ein paar Anmerkungen:

Letztlich scheint der Flaschenhals darin zu bestehen, ein »zufälliges« Zeichen aus dem Dokument zu wählen. Darin sehe ich wenig Sinn. Wenn das Dokument mit einer größeren Menge natürlichem deutschsprachigem Text arbeitet, so ist der Zeichenbestand ziemlich überschaubar und man wird die übliche Buchstabenhäufigkeit finden. »Zufällig« wird dann sehr oft ein »e« oder »n« gewählt werden. ;)

Insofern kostet es viel, nutzt aber wenig, wirklich statistisch mit dem Gesamtstring des Dokuments zu arbeiten. Ich würde daher vielleicht mit einer festen Zeichenliste arbeiten (z.B. lateinisches Alphabet plus Umlaute plus Satzzeichen), die sich wirklich zufällig durchsuchen lässt. Wobei in dem Fall (wenn auch unwahrscheinlich) ein Zeichen gewählt werden kann, was im Dokument nicht vorkommt, dann müsste neu gewürfelt und gesucht werden, was langsam wäre. Aber unter dem Strich wohl schneller als die vorgestellten Ansätze.

Was das Durchlaufen des DOM angeht, so sollte man möglichst auf das händische rekursive Durchlaufen verzichten. Einerseits kann man mit einem TreeWalker arbeiten, andererseits müsste es (glaube ich zumindest) auch möglich sein, Textknoten mit XPath auszuwählen (document.evaluate usw.). Beides sollte auf jeden Fall performanter sein. Letztlich ist das natürlich ein schwacher Trost, weil man um das manuelle Durchlaufen im IE nicht herum kommt (vielleicht kann man irgendwas mit TextRanges basteln).

innerHTML stellt keine Alternative dar - abgesehen davon, dass man da mit ebenfalls unperformanten regulären Ausdrücken oder einem eigenen Parser Tags von Textinhalt trennen müsste, würden Entities ein weiteres Problem darstellen - &gt; sind vier Zeichen, die ein sichtbares Zeichen repräsentieren.

Was spricht dagegen, die für reine Zeichenauswahl innerText bzw. textContent vom body zu nehmen und dann erst beim Markiervorgang die Textknoten zu suchen, in denen das Zeichen liegt?

Mathias

[wahsaga]

hi,

Letztlich scheint der Flaschenhals darin zu bestehen, ein »zufälliges« Zeichen aus dem Dokument zu wählen. Darin sehe ich wenig Sinn. Wenn das Dokument mit einer größeren Menge natürlichem deutschsprachigem Text arbeitet, so ist der Zeichenbestand ziemlich überschaubar und man wird die übliche Buchstabenhäufigkeit finden. »Zufällig« wird dann sehr oft ein »e« oder »n« gewählt werden. ;)

Oh, da hast du mich wohl falsch verstanden - ich möchte nicht "alle »e«" oder "alle »n«" auswählen und formatieren.
Sondern nur ein einzelnes Zeichen aus der gesamten Text, der angezeigt wird, egal ob es »e« oder »n« ist - es soll nur über die gesamte Textlänge zufällig ausgewählt werden, und dabei soll es jede "Position" mit der gleichen Wahrscheinlichkeit erwischen können.

Was das Durchlaufen des DOM angeht, so sollte man möglichst auf das händische rekursive Durchlaufen verzichten. Einerseits kann man mit einem TreeWalker arbeiten,

Werde ich mir mal anschauen, ggf. mal die Performance im Vergleich "benchmarken".

Was die Browserkompabilität angeht - Safari wird laut Scriptkommentierung wegen fehlerhafter Umsetzung ausgeschlossen, Konqueror erfordert eine Alternative zum Bewegen mittels firstChild/nextSibling.
Firefox und Opera können es vermutlich (?), IE bräuchte auf jeden Fall eine Extrawurst - da wäre zu überlegen bzw. zu messen, wie viel performanter der TreeWalker gegenüber "manuellen" rekursiven Durchlaufen des DOMs ist (hast du Erfahrungswerte?), bevor ich hier für eine Spielerei zwei Wege implementiere.

andererseits müsste es (glaube ich zumindest) auch möglich sein, Textknoten mit XPath auszuwählen (document.evaluate usw.). Beides sollte auf jeden Fall performanter sein. Letztlich ist das natürlich ein schwacher Trost, weil man um das manuelle Durchlaufen im IE nicht herum kommt (vielleicht kann man irgendwas mit TextRanges basteln).

Also wieder zweigleisig fahren, hm - oder IE ausschließen (möchte ich eigentlich nicht).

Was spricht dagegen, die für reine Zeichenauswahl innerText bzw. textContent vom body zu nehmen

Für die Ermittlung der Anzahl Zeichen denkbar.

und dann erst beim Markiervorgang die Textknoten zu suchen, in denen das Zeichen liegt?

Hier komme ich dann um rekursives Durchlaufen (welcher Art auch immer) aber wohl nicht herum.

gruß,
wahsaga