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.