Buchstabendreher

Anagramme finden und Scrabble lösen

17. Oktober 2010

Bildet man ein Wort durch Permutation eines anderen Wortes, spricht man von einem Anagramm. Aus „gerne”, wenn man Gross- und Kleinschreibung ignoriert, wird durch Vertauschen der Buchstaben z. B. „Regen”. Warum solche Funktionalität nicht in die d-rhyme Wortsuche mit integrieren? Bei einem Datenbestand von derzeit über 140.000 Wörtern vielleicht naheliegend. Zugegeben, es gibt hierfür mit Wordplay ein wirklich gutes Tools mit frei konfigurierbarer Suchtiefe online. Suchtiefe bedeutet hier, dass zu einem Suchwort alle möglichen Sub-Anagramme aufgelistet werden. Beim „Wetterfrosch” würden zwei Sub-Anagramme z. B. „Schwerter” und „oft” sein.

Wie dem auch sei, auf den Suchtiefen-Modus würde ich verzichten. Mir wäre wichtig, dass Nutzer echte Anagramme finden, also Worte, die gleichlang sind und dieselben Buchstaben enthalten. Wie findet man Anagramme, wenn ein Nutzer das Wort „gerne” eingibt und Regen erwartet? Der erste Ansatz ist wie fast immer ein Regulärer Ausdrück. Nun hat die Sache aber einen Haken, denn ein Regulärer Ausdruck, bei dem die Reihenfolge der Buchstaben ohne Belang ist, ist nur durch ein sehr unangenehmes und äußerst verschachteltes Konstrukt möglich.

Da ich einfache Lösungen mag, nehme ich zuerst als Datenbankabfrage einen simplen Regulären Ausdruck, der alle Worte derselben Länge findet, die die gesuchten Buchstaben irgendwo enthalten. Dieser könnte so aussehen.

SELECT wort FROM wortliste WHERE LCASE(wort) != ‘gerne’ AND LCASE(word) REGEXP '^[gern]{5}$';

Das Ergebnis enthält natürlich den gesuchten „Regen”, aber auch blinde Treffer wie z. B. „Genre”, das laut Definition kein Anagramm ist. Ich behalte diesen Modus trotzdem und nenne ihn den Permissiven Modus. Jetzt brauche ich noch den Strikten Modus, der aus diesem Ergebnis die Teilmenge „echte Anagramme” rausfischt. Dazu bietet sich serverseitig PHP mit einer kleinen Filterfunktion an. Die macht nichts anderes als Such- und Resultatwort in einen Array zu verwandeln, ihn sortiert und den Hashwert z. B. via RIPEMD-160 auf Gleichheit überprüft. Ist das der Fall, handelt es sich um ein echtes Anagramm.

Nachdem das fertig entwickelt war, kam mir der Gedanke, das auch zur Scrabble-Suche zu verwenden, sprich zu einem Suchwort alle enthaltenen Worte zu finden. Wobei mit Suchwort hier viel eher Buchstabensalat gemeint ist. Vom Prinzip her fast identisch. Das SQL-Statement wird geringfügig angepasst.

SELECT wort FROM wortliste WHERE LCASE(wort) != ‘gerne’ AND LCASE(word) REGEXP '^[gern]{1,5}$';

Und die serverseitige Filterung benötigt natürlich einen anderen Ansatz. Gemäß der Mengenlehre in der Mathematik kam die Idee, dass wenn die Schnittmenge A ∩ B der Buchstaben von Such- und Ergebniswort gleich den Buchstaben des Suchwortes ist, es sich um ein gültiges Teilwort handelt.

Aber auch diese Sache hat natürlich einen Haken, denn mathematische Mengen enthalten keine doppelten Elemente, wie es bei Worten aber fast immer der Fall ist. Mit der php-Funktion array_intersect allein kommt man also nicht weiter. Diese musste also noch umgebogen werden, damit es mit Multimengen auch funktioniert.

Das klingt ja wie …

Objektorientierter Wortgenerator

29. August 2010

Neben der Wort- und Reimsuche bekommt d-rhyme demnächst Zuwachs in Sachen Funktionalität. Auch wenn der Seitentitel vermuten lässt, es geht primär um Reime, so beinhaltet dieses Projekt doch mehr. Eigentlich geht es um Sprache und alle Möglichkeiten, die man aus Sicht der Informatik damit anstellen kann.

So auch das automatische Erzeugen von Wörtern, indem eine real existierende Sprache vereinfacht und objektorientiert abgebildet wird. Das ist sicherlich nichts Neues und kein Thema für eine Doktorarbeit, aber solch ein Service ist derzeit im Web nicht wirklich zu finden — wenn man von ein paar Passwortgeneratoren mal absieht, die zufälligen Buchstabensalat produzieren.

Da ich für Einfachheit anstelle komplexer Algorithmen bin, erzeuge ich in php Sprachklassen, z. B. German, die ich von einer Klasse Language ableite. Und eine Sprache besteht für mich in vereinfachter Variante nur aus Vokalen (V), Konsonanten (K) und den typischen Sprachlauten (L). Im Deutschen wären solche Laute z. B. sch, eu, ck etc. Und diese kleinsten Elemente haben wiederum Referenzen auf mögliche Folgeobjekte, und lassen sich via Generator über bestimmte Muster zu Worten aneinanderreihen. Als letzte Komponente definiere ich für jedes Sprachelement noch eine Häufigkeit, mit der es auftritt.

Zuerst „erschuf” ich Japanisch, da diese Sprache ziemlich einfach nachzubilden ist und Wikipedia die nötige Silben- bzw. Morenstruktur frei Haus liefert. Die Generatorklasse bekommt als Muster für den ersten Test (KVKVLKV) übergeben und … siehe da, hier kommt mit Yarushoji, Tayochiri, Nisachonu, Misachoji, suyachoyu etwas, das für mich als Gaikokujin irgendwie japanisch klingt.

Mitte September 2010 stelle ich das Ding unter d-labs online, wahrscheinlich mit einer vorläufigen Auswahl an Sprachen wie Japanisch, Türkisch, Französisch oder auch Latein. Stellt sich für Außenstehende noch die berühmte Frage nach dem Sinn. Was soll ich damit — mir getürktes Türkisch auf den Arm tätowieren, um später festzustellen, dass der Generator ein Schimpfwort erzeugt hat? Das vielleicht nicht, aber Kunstworte haben derzeit Hochkonjunktur. Zumindest im Web, wo Domains real existierender Wörter inzwischen rar sind und Unternehmen auf mehr oder minder gelungene Kunstworte zurückgreifen. Und wenn ein Online-Schuhgeschäft einer Namensagentur Geld spendiert, Experten wochenlang brüten und am Ende ein Wort herauskommt, das doof ist und nach Generator riecht, dann existiert für mich allein deshalb ein Sinn.

Elektronische Entschleunigung

Dubstep

22. Juli 2010

Dubstep als elektronischer Musikstil gibt es seit einigen Jahren, ursprünglich um 2001 in London aus 2Step und Garage entstanden, hat er sich weiterentwickelt und im Laufe der Zeit Einflüsse aus verschiedensten Stilrichtungen aufgenommen. Persönlich aufmerksam wurde ich um 2006, als die unerträglichen House-Elemente verschwanden und die Reise mehr in Richtung Dub ging.

Trotz einer Geschwindigkeit zwischen 140 und 145 BPM wirkt es eher langsam, da ähnlich wie bei Dub und Reggae meist nur der der erste und dritte Vierteltakt perkussiv betont sind. Dazu gesellt sich der markante „Wobble-Bass”, ein durch LFO-Modulation entstandenes tieffrequentes Bass-Gerüst. Bei „Reggae-Dubstep” ist der zweite und vierte Vierteltakt meist mit Riffs besetzt, was in Kombination mit Delay, Reverb und Rastafari-Riddims dem Ganzen ein Jamaika-Feeling verpasst.

Betrachtet man das aktuelle Spektrum, dann fällt auf, dass viele Sachen nur für die Tanzfläche produziert sind — überfrachtet mit Bässen, knallbunt, unruhig und, ganz ehrlich, ziemlich nervig. Nichts, was ich mir neben der Arbeit oder zum Chillen antun würde. Einen guten, intelligenten Mix zu finden ist nicht wirklich leicht. Liquid Stangers Babylon Outcast Mix oder DopeLabs zählen zu den wenigen mir bekannten Ausnahmen.

Dubstep hat definitiv mehr Potential als nur reine Partymusik. Ein gelungenes Beispiel ist Dj Zhaos Mashup FUSION ONE – Weltmusik verschmilzt mit Dubstep zu einer hörenswerten Synthese. Aber nicht nur Traditionelles aus Asien und Afrika lässt sich neben Reggae gut kombinieren, theoretisch kommt vieles infrage – Klassik, Jazz, Rock bis hin zu Videospiel-Soundtracks. Die Zeit wird zeigen, ob man in zehn Jahren noch von „Dubstep” spricht oder das Ganze unter einem anderen Namen „massentauglich” geworden ist.

Kommentare anzeigen ( 1 Kommentar )
Kommentieren