MySQL : mit regulären Ausdrücken Wörter für Buchstaben suchen

[Thomaier]

Hallo,

gleich vorweg: Ich nutze MySQL Version 5.0.51b.

Ich habe eine meiner Meinung nach nicht sehr komplexe Anwendung geschrieben, die mit Hilfe einer Worttabelle die Wörter herausfiltert, in denen die vom Nutzer eingegebenen Buchstaben vorkommen. Z.B. gibt der Nutzer "eehgnd" ein und bekommt sortiert nach Länge Ergebnisse wie "gehend, hegend, gehen, hege", etc. Zu sehen auf http://www.wort-suchen.de.
Die Tabelle enthält ein Feld "word", die restlichen Felder spielen bei der Suche keine Rolle. Alle Wörter sind ausschließlich in Großbuchstaben in der Tabelle enthalten.
Folgende Probleme haben sich mit der Zeit bei der Suche mittels regulärer Ausdrücke ergeben:

1. Doppelte Buchstaben vermeiden
Die einfache Suche erfolgt über folgende Abfrage:
SELECT word FROM word_table WHERE word REGEXP '(^[EEHGND]{0,6}$)'
Das Problem: Es werden auch sämtliche Wörter gefunden, in denen die Buchstaben mehrfach vorkommen. Ich suche also nach einer Möglichkeit, das Vorkommen einzelner Buchstaben zu beschränken. "E" kommt ja z.B. maximal zweimal vor. Derzeit muss ich in einem zweiten Schritt via PHP die zusätzlich gefundenen Wörter vor der Ausgabe löschen. Diesen zweiten Schritt würde ich mir gerne ersparen.

2.1. Joker
Ich möchte gerne die Möglichkeit geben, einen Joker einzusetzen. Damit kann ein Buchstabe (oder auch mehr) zusätzlich zu den gewählten vorkommen. Die derzeitige Abfrage sieht wie folgt aus:
SELECT word FROM word_table WHERE word REGEXP '(^[EEHGND]{0,6}.[EEHGND]{0,6}$)'
Auch hier wieder das Problem, dass ich nachträglich mit PHP aussortieren muss. Wenn ich jetzt gerne zwei Joker haben möchte, dann bekomme ich schon Probleme sowohl mit der Abfrage als auch mit der Masse an aus der Datenbank gelieferter Datensätze. Vielleicht fällt jemandem eine elegantere Lösung ein.
2.2 Umlaute
Ein weiteres Problem mit dem jetzt verwendeten Joker sind Umlaute. Die werden einfach nicht anstelle des Punktes gefunden.
SELECT word FROM word_table WHERE word REGEXP '(^[HRE]{0,3}.[HRE]{0,3}$)'
sollte meiner Meinung nach auch "Ähre" finden und tut es aber nicht, obwohl das Wort in der Datenbank vorhanden ist.

3. Wiederholung von Zeichen / Gruppen
Das Beispiel aus 2. beinhaltet auch mein 3. Problem. Das mit den ersten eckigen Klammern gefundene Zeichen soll, je nach zulässiger Anzahl, in der zweiten eckigen Klammer nicht mehr auftauchen. In PHP gibt es dazu die Möglichkeit auf Gruppen zu referenzieren. Sowas habe ich jedoch für MySQL nicht gefunden. Ich hoffe hier hat jemand eine Art Workaround.

Zu Generierung der SQL-Abfragen nutze ich PHP, in dem ich mich meines Erachtens auch ausreichend zurechtfinde. Mit geht es hier allein um die MySQL-Abfragen.

Ich habe sehr ausführlich im Internet recherchiert und denke, dass es für die meisten meiner Probleme keine einfache Lösung geben wird. Vielleicht hat hier aber jemand für das ein oder andere einen Hinweis. Das komplette Einlesen der Datenbank in PHP ist bei über 100.000 Stichwörtern keine Möglichkeit. Vielleicht habe ich mich aber generell für die falsche Herangehensweise bei einer solchen Suche entschieden, bis hin zur Auswahl von MySQL als Datenbank. Ich bin für jeden noch so kleinen Hinweis dankbar.

MfG
Thomas

[ChrisB]

Hi,

bevor man sich darüber zielführend Gedanken machen kann, müssten erst mal ein paar Einzelheiten der Aufgabenstellung exakter spezifiziert werden.

Ich habe eine meiner Meinung nach nicht sehr komplexe Anwendung geschrieben, die mit Hilfe einer Worttabelle die Wörter herausfiltert, in denen die vom Nutzer eingegebenen Buchstaben vorkommen. Z.B. gibt der Nutzer "eehgnd" ein und bekommt sortiert nach Länge Ergebnisse wie "gehend, hegend, gehen, hege", etc. [...]

Das Problem: Es werden auch sämtliche Wörter gefunden, in denen die Buchstaben mehrfach vorkommen. Ich suche also nach einer Möglichkeit, das Vorkommen einzelner Buchstaben zu beschränken. "E" kommt ja z.B. maximal zweimal vor.

Es sollen also alle Wörter gefunden werden, die nur *genau* die vom Nutzer eingegebenen Zeichen enthalten, also auch von der Anzahl Buchstaben her der Länge der eingegebenen Buchstabenkette entsprechen?

Alle Wörter sind ausschließlich in Großbuchstaben in der Tabelle enthalten.

Enthalten die zu durchsuchenden "Wörter" also ausschliesslich Grossbuchstaben - oder können es auch noch andere, nicht-buchstaben-Zeichen sein?

Bzw. in einer nächsten Stufe dann noch plus einem zusätzlichen beliebigen Buchstaben, der mittels dem Jokerzeichen dargestellt werden soll. Da käme dann die Frage auf: Darf bei Suche nach EEHGND* (* sei mal das Jokerzeichen) dann auch ein Wort gefunden werden, welches drei E enthält, oder müssen es zwei E und noch ein zusätzlicher Buchstabe, der in den anderen Suchbuchstaben nicht enthalten ist, sein?

Derzeit muss ich in einem zweiten Schritt via PHP die zusätzlich gefundenen Wörter vor der Ausgabe löschen. Diesen zweiten Schritt würde ich mir gerne ersparen. [...]
Auch hier wieder das Problem, dass ich nachträglich mit PHP aussortieren muss.

Ob sich das (performant) komplett DB-seitig lösen lässt, vermag ich gerade nicht zu sagen.

Ich würde vielleicht bei der Suche nach EEHGND bzw. EEHGND* erst mal alles per REGEX aus dem zu durchsuchenden String entfernen, was *nicht* einem der fünf Buchstaben E G H N D entspricht - und dann die Länge davon betrachten, ob sie im ersten Falle kleiner 6 bzw. im zweiten kleiner 7 Zeichen ist.

Damit wäre der Bereich der potentiellen Kandidaten schon mal recht gut eingeschränkt.
Die Prüfung, ob sie auch den darüber hinaus gehenden "schärferen" Kritieren entsprechen, würde ich dann vermutlich wirklich lieber scriptseitig machen - per REGEX kann ich mir jedenfalls kaum einen Weg vorstellen, das in irgendeiner Weise performant abzubilden.

MfG ChrisB

[Thomaier]

Hi,
danke für die ausführliche Antwort.

Es sollen also alle Wörter gefunden werden, die nur *genau* die vom Nutzer eingegebenen Zeichen enthalten, also auch von der Anzahl Buchstaben her der Länge der eingegebenen Buchstabenkette entsprechen?

Da habe ich mich nicht klar ausgedrückt. Es müssen nicht alle vom Nutzer eingegebenen Buchstaben überhaupt bzw. in ihrer Häufigkeit vorkommen. "EEHGND" findet also auch "GEHE" oder "GEH".

Enthalten die zu durchsuchenden "Wörter" also ausschliesslich Grossbuchstaben - oder können es auch noch andere, nicht-buchstaben-Zeichen sein?

Es sind nur Buchstaben vorhanden. Die Tabelle ist für Scrabble vorgesehen, daher fehlt auch das "ß" vollständig.

Darf bei Suche nach EEHGND* (* sei mal das Jokerzeichen) dann auch ein Wort gefunden werden, welches drei E enthält, oder müssen es zwei E und noch ein zusätzlicher Buchstabe, der in den anderen Suchbuchstaben nicht enthalten ist, sein?

Der Joker kann für ein beliebiges Zeichen stehen, also sowohl erlaubte Zeichen wiederholen (z.B. ein weiters E) als auch neue darstellen.

Ich würde vielleicht bei der Suche nach EEHGND bzw. EEHGND* erst mal alles per REGEX aus dem zu durchsuchenden String entfernen, was *nicht* einem der fünf Buchstaben E G H N D entspricht - und dann die Länge davon betrachten, ob sie im ersten Falle kleiner 6 bzw. im zweiten kleiner 7 Zeichen ist.

Jetzt komme ich leider nicht ganz mit. Ich kann doch mit REGEX nichts entfernen und dann die Länge vergleichen. Könntest du mir vielleicht eine entsprechende Abfrage aufschreiben?

Danke für deine Hilfe,
MfG
Thomaier

[Alexander (HH)]

Moin Moin!

Deine Suche ist auf jeden Fall sehr teuer. Pattern Matching ist schon nicht billig, und dann noch ein nicht vermeidbarer Full Table Scan. Und warum suchst Du nach Worten der Länge 0? Ich würde 1 als Mindestlänge angeben.

Versuche, mit Vorberechnung zu arbeiten.

Um alle Anagramme eines Wortes zu finden, könntest Du die Buchstaben in den Worten in der DB alphabetisch sortieren, und über die "sortierten Wörter" suchen. Der Suchbegriff muß natürlich auch buchstabenweise sortiert werden.

word   | sorted_word
-------+--------------------
gehend | eedghn
hegend | eedghn
gehen  | eeghn
hege   | eegh
eggen  | eeggn
eck    | cek

SELECT word FROM word_table WHERE sorted_word='eedghn'

Buchstabenhäufigkeiten und optionale Buchstaben kannst Du wieder über RegExps erschlagen:

SELECT word FROM word_table WHERE word REGEXP '^e{1,2}dghn$'
(Ein oder zwei 'e's)

SELECT word FROM word_table WHERE word REGEXP '^e+d?g?hn$'
(Mindestens ein 'e', 'd' und 'g' optional)

Das Umlautproblem dürfte auf UTF8-Codierung zurückzuführen sein, von der MySQL (oder die RE-Engine) nichts weiß. Auch wenn Du ein Zeichen 'Ö' in die DB schreibst und von dort wieder liest, sieht MySQL stattdessen zwei Zeichen 'Ö'. Die Kommunikation mit MySQL und die Speicherung in MySQL müssen einheitlich in UTF-8 oder ISO-8859-1 sein. Gemischt geht es nicht.

Alexander

[Vinzenz Mai]

Hallo Alexander,

Das Umlautproblem dürfte auf UTF8-Codierung zurückzuführen sein,

davon gehe ich auch aus.

von der MySQL (oder die RE-Engine) nichts weiß. Auch wenn Du ein Zeichen 'Ö' in die DB schreibst und von dort wieder liest, sieht MySQL stattdessen zwei Zeichen 'Ö'. Die Kommunikation mit MySQL und die Speicherung in MySQL müssen einheitlich in UTF-8 oder ISO-8859-1 sein. Gemischt geht es nicht.

Das hilft bei UTF-8 (genauer bei jeder Multi-Byte-Codierung) nicht. REGEXP ist derzeit (MySQL 5.x) nicht multibyte-safe und arbeitet byteweise, nicht zeichenweise.

Freundliche Grüße

Vinzenz

[Alexander (HH)]

Moin Moin!

Das hilft bei UTF-8 (genauer bei jeder Multi-Byte-Codierung) nicht. REGEXP ist derzeit (MySQL 5.x) nicht multibyte-safe und arbeitet byteweise, nicht zeichenweise.

Aaarg! Diese SCHMERZEN! Im Ernst: Gut zu wissen, dass das NICHT geht. Ein weiterer Sargnagel für MySQL in zukünftigen Projekten.

Alexander

[Thomaier]

Hallo,

»» Das Umlautproblem dürfte auf UTF8-Codierung zurückzuführen sein,
davon gehe ich auch aus.

Die MySQL-Tabelle ist mit utf8_general_ci kodiert. Ebenso alle verwendeten Scripte und Vorgänge mit UTF-8 zum schreiben in und lesen aus der Datenbank.

»» von der MySQL (oder die RE-Engine) nichts weiß. Auch wenn Du ein Zeichen 'Ö' in die DB schreibst und von dort wieder liest, sieht MySQL stattdessen zwei Zeichen 'Ö'. Die Kommunikation mit MySQL und die Speicherung in MySQL müssen einheitlich in UTF-8 oder ISO-8859-1 sein. Gemischt geht es nicht.

Das hilft bei UTF-8 (genauer bei jeder Multi-Byte-Codierung) nicht. REGEXP ist derzeit (MySQL 5.x) nicht multibyte-safe und arbeitet byteweise, nicht zeichenweise.

Ich verstehe das Problem noch nicht, was aber sicherlich an meinen mangelnden technischen Fähigkeiten liegt. Vielleicht ein praktisches Beispiel:
Ein Nutzer will "MÄHDERIN" in der Datenbank finden und gibt "mhderin" mit einem Joker ein. Ich habe jetzt mal mit dem konkreten Beispiel experimentiert und
SELECT ID, word, points FROM word2 WHERE word REGEXP BINARY '^M[Ä]{1}[HDERIN]{0,7}$' ORDER BY word
findet es NICHT,
dagegen findet
SELECT ID, word, points FROM word2 WHERE word REGEXP BINARY '^MÄ[HDERIN]{0,7}$' ORDER BY word
das Wort und auch andere. Wo ist da der Unterschied in Bezug auf den Umlaut "Ä"?

Vielen Dank für jeden Hinweis.
MfG
Thomas

[Alexander (HH)]

Moin Moin!

»» Das hilft bei UTF-8 (genauer bei jeder Multi-Byte-Codierung) nicht. REGEXP ist derzeit (MySQL 5.x) nicht multibyte-safe und arbeitet byteweise, nicht zeichenweise.

Ich verstehe das Problem noch nicht, was aber sicherlich an meinen mangelnden technischen Fähigkeiten liegt.

Mit UTF-8 gilt die aus ASCII-Zeiten bekannte Regel 1 Byte = 1 Zeichen nicht mehr. Zeichen außerhalb des ASCII-Zeichensatzes (ab Zeichen 128) belegen zwei bis vier Bytes. Siehe http://de.wikipedia.org/wiki/UTF-8.

Jeder Code, der mit der Annahme 1 Byte = 1 Zeichen arbeitet, funktioniert mit UTF-8 nicht mehr, sobald auch nur ein Zeichen oberhalb Zeichen 127 vorkommt.

Das Wort "Bär" wird in ISO-8859-1 durch die drei Bytes 0x42, 0xE4, 0x72 dargestellt. In UTF-8 wird es durch vier Bytes 0x42, 0xC3, 0xA4, 0x72 dargestellt. Ein UTF-8-fähiges System (z.B. Perl 5.8 und neuer) kann beide Darstellungen in eine interne Darstellung überführen, die auf Zeichen (und nicht auf Bytes) basiert. Die length()-Funktion liefert dann auch für beide Bytefolgen 3 (Zeichen). Ein System, das von UTF-8 keine Ahnung hat, ermittelt für die UTF-8-Darstellung eine Länge von 4 (Bytes). Ein UTF-8-fähiges System vergleicht die beiden Darstellungen anhand der internen, Zeichen-basierenden Darstellung und hält sie für identisch. Ein System, das UTF-8 nicht berücksichtigt, sieht zwei unterschiedliche und sogar unterschiedlich lange Bytefolgen, die demnach absolut nicht identisch sind.

Das Problem mit den Character Classes (z.B. [abfgx]) ist nun, das MySQL hier byteweise arbeitet und nicht Zeichenweise. [Bär] als Character Class sucht nach den VIER(!) BYTES(!) 0x42, 0xC3, 0xA4, 0x72. Und aufgrund der UTF-8-Codierung kommt 0xC3 in UTF-8-Strings relativ häufig vor.

Das Problem mit dem Punkt als Platzhalter ist ähnlich. Obwohl du eigentlich ein beliebiges ZEICHEN meinst, vergleicht MySQL hier BYTES. Das Pattern /B.r/ paßt zwar auf "Bar", aber nicht auf "Bär" in UTF-8-Darstellung, weil das "ä" aus zwei Bytes zusammengesetzt ist. /B..r/ bzw. /B.{2}r/ würde zwar auf "Bär" in UTF-8-Darstellung passen, aber eben auch auf "Bahr" und nicht mehr auf "Bar".

MySQL ist an dieser Stelle schicht und ergreifend kaputt, weil die RE-Engine mit Bytes operiert, wo sie mit Zeichen arbeiten sollte.

Ein sehr kruder Workaround wäre, sowohl den Wert als auch die Regular Expression explizit in ISO-8859-x umzuwandeln, bevor der Vergleich stattfindet. Das scheitert allerdings, sobald Du Zeichen außerhalb ISO-8859-x benutzt. Sauberer wäre ein vollständiger Wechsel auf ISO-8859-x. Und noch besser wäre es, MySQL zu reparieren oder durch ein UTF-8-taugliches RDBMS zu ersetzen.

Alexander

[Thomaier]

Hallo Alexander,
vielen Dank für das ausführliche Posting. Ich mache mir da mal ausführlich Gedanken zwischen der Zeichenkonvertierung in ISO-8859-x und dem Umstieg auf ein anderes Suchsystem. Webglimpse ist mir da mal begegnet, kann jedoch auf den ersten Blick nicht alle REGEXP-Eigenschaften und ist auch nicht kostenlos. Wenn du da einen Tipp hast, dann ist er willkommen.

MfG
Thomas

[Alexander (HH)]

Moin Moin!

Umstieg auf ein anderes Suchsystem. Webglimpse ist mir da mal begegnet

Das ist zum Durchsuchen von Dateien, nicht von Datenbanken.

Dein Problem ist die kaputte RE-Engine von MySQL. Es gibt diverse andere RDBMS, die diesen Fehler nicht haben.

Ich hab mir den Spaß gemacht und mal mit einer produktiven PostgreSQL-Datenbank getestet, auf die ich gerade Zugriff habe. (Ja, das macht man nicht.)

select lastname from users where lastname~*'^[1]{4}$'

(Suche mir alle Nachnamen aus der Benutzer-Tabelle, die die vier Buchstaben W, E, I und ß in Groß oder Klein enthalten und die exakt vier Zeichen lang sind.)

Antwort: "Weiß" (ja, nur ein User hat diesen Nachnamen.)

Hätte PostgreSQL das UTF-8-Problem, wäre das Pattern und der Nachname fünf Bytes lang und das Pattern hätte keinen Treffer ergeben.

Der sauberste Weg ist also wohl die Migration auf PostgreSQL, damit bekommst Du nicht nur eine funktionierende RE-Engine, sondern ersparst Dir auch diverse andere Merkwürdigkeiten von MySQL. Nicht, das PostgreSQL keine Merkwürdigkeiten hätte, aber die Liste ist deutlich kürzer, betrifft teilweise nur uralte Versionen, und die Problemstellen sind IMHO exotischer als bei MySQL.

Alexander

---

1. weiß ↩︎

[Thomaier]

Hallo Alexander,

»» Umstieg auf ein anderes Suchsystem. Webglimpse ist mir da mal begegnet

Das ist zum Durchsuchen von Dateien, nicht von Datenbanken.

Richtig. Ich habe mal über die Auslagerung der DB in eine txt-Datei nachgedacht. Das scheint beim Wörterbuch www.beolingus.de sehr gut zu funktionieren.

Der sauberste Weg ist also wohl die Migration auf PostgreSQL, damit bekommst Du nicht nur eine funktionierende RE-Engine, sondern ersparst Dir auch diverse andere Merkwürdigkeiten von MySQL.

Leider habe ich keinen eigenen Server und wahrscheinlich klappt die Installation nicht ohne. Das gleiche Problem habe ich aber auch mit Webglimpse. Ich mache mich da aber mal schlau.

Danke,
Thomas

[Thomaier]

Hallo,

Und warum suchst Du nach Worten der Länge 0? Ich würde 1 als Mindestlänge angeben.

Du hast recht, das ist sinnlos und wurde von mir ohne nachzudenken von einem anderen Codeschnipsel übernommen. Ich habe jetzt sogar "2" als Mindestlänge, weil es sich ja um Worte handeln soll.

Um alle Anagramme eines Wortes zu finden, könntest Du die Buchstaben in den Worten in der DB alphabetisch sortieren, und über die "sortierten Wörter" suchen. Der Suchbegriff muß natürlich auch buchstabenweise sortiert werden.

Dies Lösung scheint mir, zumindest für die jokerfreie Suche genial. Danke für den Hinweis.

MfG
Thomas

[Alexander (HH)]

Moin Moin!

Du hast recht, das ist sinnlos und wurde von mir ohne nachzudenken von einem anderen Codeschnipsel übernommen. Ich habe jetzt sogar "2" als Mindestlänge, weil es sich ja um Worte handeln soll.

Damit trittst Du jetzt aber mindestens Engländern und Spaniern auf die Füße, wo ein Wort durchaus aus nur einem Buchstaben bestehen kann.

Alexander

[Thomaier]

Hallo,

Damit trittst Du jetzt aber mindestens Engländern und Spaniern auf die Füße, wo ein Wort durchaus aus nur einem Buchstaben bestehen kann.

und Polen, Slowaken, Tschechen, Russen...
Mir ist das Problem als Student der slawischen Sprachen durchaus bewusst. Nur handelt es sich 1. um eine auf Scrabble ausgerichtete Suche. Dort müssen Wörter generell mindestens 2 Buchstaben haben, 2. ist es eine deutsche Suche und 3. sollte jemand für einbuchstabige Wörter vielleicht keine Suche brauchen. Das sind die Grundgedanken, die hinter der Begrenzung stehen.

MfG
Thomas

[Thomaier]

Hallo Alexander,

SELECT word FROM word_table WHERE word REGEXP '^e{1,2}dghn$'
(Ein oder zwei 'e's)

SELECT word FROM word_table WHERE word REGEXP '^e+d?g?hn$'
(Mindestens ein 'e', 'd' und 'g' optional)

Diese Abfragen habe ich soweit umgesetzt. Sie sind zwar nicht schneller als die vorherige, dafür spare ich mir das Aussortieren zusätzlicher Zeichen in PHP. Also Ziel erreicht. Jetzt habe ich jedoch noch das Problem, dass mittels eines Jokers ein weiteres Zeichen hinzukommt. Ich habe es mal in WHERE über einen zweiten REGEXP probiert, doch da gingen mir schnell die Ideen aus. Zwischen jeden angegebenen Buchstaben einen Punkt (.) setzen fällt nicht nur wegen der mangelnden Unterstützung von Umlauten aus, sondern auch, weil dann zu viele Unbekannte drin sind. Du hattest bisher sehr gute Ideen, vielleicht hast du hier noch eine weitere.

MfG,
Thomas

[Vinzenz Mai]

Hallo,

» SELECT word FROM word_table WHERE word REGEXP '^e{1,2}dghn$'
» (Ein oder zwei 'e's)
»
» SELECT word FROM word_table WHERE word REGEXP '^e+d?g?hn$'
» (Mindestens ein 'e', 'd' und 'g' optional)

Diese Abfragen habe ich soweit umgesetzt. Sie sind zwar nicht schneller als die vorherige,

warum auch. Die Verwendung von REGEXP sorgt dafür, dass jeder Datensatz betracht werden muss. Reguläre Ausdrücke sind im allgemeinen noch ziemlich teuer.

Ich würde auf REGEXP komplett verzichten, statt dessen wegen des speziellen Einsatzzweckes in 29(!) weiteren Spalten die einzelnen Buchstabenhäufigkeiten abspeichern [1] und bei der Abfrage nutzen.

Die Buchstabenhäufigkeiten könntest Du

a) in der API (sprich) PHP oder
b) mit einem Trigger

ermitteln. Ich gehe auch bei dieser Lösung davon aus, dass es stets zu einem Full-Table-Scan kommen wird. Dafür wird aber die teure REGEXP-Engine nicht angeworfen.

Freundliche Grüße

Vinzenz

[1] ganz bewusst gegen Normalisierung verstoßend. Ich gehe davon aus, dass
    es bei dieser DB nur selten zu INSERTs kommt und UPDATE-Operationen fast
    ausgeschlossen sind.

[Alexander (HH)]

Moin Moin!

Ich würde auf REGEXP komplett verzichten, statt dessen wegen des speziellen Einsatzzweckes in 29(!) weiteren Spalten die einzelnen Buchstabenhäufigkeiten abspeichern [1] und bei der Abfrage nutzen.

[1] ganz bewusst gegen Normalisierung verstoßend.

Guter Ansatz für eine lese-optimierte DB. Und sauberer als das "sortierte Wort" ist das auch. Nur wird die Abfrage halt etwas länger. Gut, dass man das SQL-Statement berechnen kannn.

Ich würde angesichts der Joker-Problematik allerdings nochmal nachdenken, ob die Buchstabehäufigkeiten in einer getrennten Tabelle nicht besser aufgehoben wären, weil GROUP BY, COUNT und SUM da evtl. einfacher zu formulieren sind.

Die Forderung "zwei Es, zwei Rs, und zwei beliebige andere Buchstaben" läßt sich aber auch in der nicht normalisierten Form ausdrücken:

... where count_e=2 and count_r=2 and count_a+...+count_d+count_f+....+count_q+count_s+...count_z+count_ae+count_oe+count_ue+count_sz=6

Die Anfrage ist halt für jede Eingabe neu zu berechnen, während eine Konstruktion mit SUM und COUNT immer wieder benutzt werden könnte.

Alexander

[Thomaier]

Hallo Alexander,

Ich würde angesichts der Joker-Problematik allerdings nochmal nachdenken, ob die Buchstabehäufigkeiten in einer getrennten Tabelle nicht besser aufgehoben wären, weil GROUP BY, COUNT und SUM da evtl. einfacher zu formulieren sind.

Ich verstehe dich so: für jeden Buchstaben eines jeden Wortes einen neuen Datensatz anlegen? Spalten: word_id (mit Index), letter, number.
Dann mit SUM bzw. COUNT alle Häufigkeiten (number) eines Indexes addieren? Das gilt für den Abgleich wegen Jokern. Für die einfache Suche verfahre ich dann aber wie? Wahrscheinlich mit GROUP? Habe ich noch nicht gemacht, daher die Rückfrage.
Als Vorteil einer Auslagerung nach genanntem Muster sehe ich bei weiterem Nachdenken noch, dass ich mich nicht auf die zu verwendenden Buchstaben festlegen muss. Demnach können Wörter verschiedener Sprachen in einer Tabelle stehen. Sehe ich das so richtig?

Dank und Gruß,
Thomas

[Alexander (HH)]

Moin Moin!

»» Ich würde angesichts der Joker-Problematik allerdings nochmal nachdenken,

(Fehlende Fußnote: Wirklich als Nachdenken gemeint, ich hab nicht weiter gegrübelt, ob die Normalisierung hilft oder stört.)

»» ob die Buchstabehäufigkeiten in einer getrennten Tabelle nicht besser aufgehoben wären, weil GROUP BY, COUNT und SUM da evtl. einfacher zu formulieren sind.

Ich verstehe dich so: für jeden Buchstaben eines jeden Wortes einen neuen Datensatz anlegen? Spalten: word_id (mit Index), letter, number.

Ja, genau. Wobei number ein reserviertes Wort bei einigen RDBMS ist. Nennen wir die Tabelle mal provisorisch letter_freq, mit word_id, letter, n (statt number).

Dann mit SUM bzw. COUNT alle Häufigkeiten (number) eines Indexes addieren? Das gilt für den Abgleich wegen Jokern. Für die einfache Suche verfahre ich dann aber wie? Wahrscheinlich mit GROUP? Habe ich noch nicht gemacht, daher die Rückfrage.

Die Suche nach "zwei Es, zwei Rs, und zwei beliebige andere Buchstaben" müßte natürlich anders formuliert werden. Schon auf Deutsch: Gesucht sind alle Worte mit insgesamt sechs Buchstaben, in denen die Buchstaben E und R je zweimal vorkommen.

Erste Forderung - Wortlänge:

select word_id from letter_freq group by word_id where sum(n)=6
(Je nach RDBMS muß sum(n) auch noch zwischen select und from vorkommen.)

Zweite und dritte Forderung - Häufigkeit ausgewählter Buchstaben:

select word_id from letter_freq where letter='E' and n=2
select word_id from letter_freq where letter='R' and n=2

Gesamtergebnis sind dann alle Worte, deren IDs in allen drei Query-Ergebnissen vorkommen. Das kann man mit SQL ausdrücken, aber ich hab gerade eine Denkblockade.

Als Vorteil einer Auslagerung nach genanntem Muster sehe ich bei weiterem Nachdenken noch, dass ich mich nicht auf die zu verwendenden Buchstaben festlegen muss. Demnach können Wörter verschiedener Sprachen in einer Tabelle stehen. Sehe ich das so richtig?

Richtig. Mit der normalisierten Form kannst Du den gesamten Unicode-Bereich erschlagen, in der nicht normalisierten Form müßtest Du die Wort-Tabelle um ca. 100.000 (aktuell) bis ca. 1 Mio. (max.) Spalten erweitern.

Alexander

[Vinzenz Mai]

Hallo,

select word_id from letter_freq group by word_id where sum(n)=6
(Je nach RDBMS muß sum(n) auch noch zwischen select und from vorkommen.)

nein, ein Fall für die HAVING-Klausel:

HAVING SUM(n) = 6 :-)

Zweite und dritte Forderung - Häufigkeit ausgewählter Buchstaben:

select word_id from letter_freq where letter='E' and n=2
select word_id from letter_freq where letter='R' and n=2

Gesamtergebnis sind dann alle Worte, deren IDs in allen drei Query-Ergebnissen vorkommen. Das kann man mit SQL ausdrücken, aber ich hab gerade eine Denkblockade.

Subselects, vergleiche </archiv/2009/1/t182493/#m1207580>. Von Selfjoins rate ich hier dringend ab :-)

» Als Vorteil einer Auslagerung nach genanntem Muster sehe ich bei weiterem Nachdenken noch, dass ich mich nicht auf die zu verwendenden Buchstaben festlegen muss. Demnach können Wörter verschiedener Sprachen in einer Tabelle stehen. Sehe ich das so richtig?

Als Zusatzinformation müsstest Du zu einem Wort die zulässigen Sprachen und die zugehörigen Buchstabenmengen hinterlegen. Ich ging von einer einsprachigen Variante mit den Buchstaben von A-Z sowie ÄÖ und Ü aus, da Du das ß bereits ausgeschlossen hattest.

Aber auch im Fall von gelegentlichen Erweiterungen der Wortliste sollten die Lesezugriffe bei weitem überwiegen und sich eine Optimierung für Lese-/Suchzugriffe auszahlen.

Freundliche Grüße

Vinzenz

[Thomaier]

Hallo,
danke für die zahlreichen Antworten. Ich werde mich die Tage intensiv reindenken, ausprobieren und dann das Ergebnis - hoffentlich ohne weiteren Klärungsbedarf - hier wieder posten.

Nochmals danke,
Thomas

[Thomaier]

Hallo,

ich habe Subselects ausprobiert, komme aber nicht ganz klar. Folgende Version war mein letzter Vorschlag:

  
SELECT ID_word, letter, n  
FROM (  
 SELECT ID_word, letter, n  
 FROM (  
  SELECT ID_word, letter, n  
  FROM word_letter  
  GROUP BY ID_word  
   HAVING SUM(n)=6  
 ) AS wl_R  
 WHERE wl_R.letter = 'R' AND wl_R.n = 2  
 GROUP BY wl_R.ID_word  
) AS wl_E  
WHERE wl_E.letter = 'E' AND wl_E.n = '2'

Die Idee war die immer weitere Einschränkung der Ergebnisse. Die innere SELECT-Abfrage mit SUM funktioniert. Auch die zweite Schicht liefert als Ergebnis alle Wörter mit 6 Buchstaben, die zwei "R" enthalten. Doch die letzte Schicht liefert keine Ergebnisse mehr, obwohl z.B. "RETTER" ein mögliches Ergebnis wäre. Wie liefert die innere Abfrage der mittleren Abfrage, was diese der äußeren nicht mehr liefert?
Ich habe andere Möglichkeiten mit Subselects ausprobiert, die waren aber viel weniger performant, als es diese Möglichkeit zu sein scheint. Widerspruch nehme ich gerne entgegen.

Danke im Vorraus,
Thomas

[Thomaier]

Hallo
zu vorher genannten Abfrage hier eine Beispieltabelle zur Verdeutlichung.

Tabelle: word

ID | word
---+-----
1  | RETTE
2  | RETTER
3  | RETTEN

Tabelle: word_letter
n = Häufigkeit der Buchstaben in dem Wort

ID_word | letter | n
--------+--------+---
1       | R      | 1
1       | E      | 2
1       | T      | 2
2       | R      | 2
2       | E      | 2
2       | T      | 2
3       | R      | 1
3       | E      | 2
3       | T      | 2
3       | N      | 1

1. Schritt:
nach der ersten Abfrage sollen alle "Wörter" mit einer bestimmten Länge übrig bleiben und folgende Tabelle übergeben werden.

ID_word | letter | n
--------+--------+---
2       | R      | 2
2       | E      | 2
2       | T      | 2
3       | R      | 1
3       | E      | 2
3       | T      | 2
3       | N      | 1

("RETTE" ist damit schonmal raus)

2. Schritt:
im zweiten Schritt bleiben noch alle Wörter, in denen "R" zweimal vorkommt:

ID_word | letter | n
--------+--------+---
2       | R      | 2
2       | E      | 2
2       | T      | 2

Schritt 2 wiederholt sich mit allen vom Nutzer eingegeben Buchstaben, liefert also in längeren Listen immer genauere Auswahlen. Wende jedoch die von mir oben formulierte Abfrage an, so wird auch "RETTET" nicht mehr gefunden.
In der äußersten Abfrage wird dann über LEFT JOIN auch das Wort aus der Tabelle word ausgelesen. Das muss ja vorher nicht passieren.

Ich hoffe, jetzt ist das Problem, bzw. überhaupt die Anforderung klarer.

Gruß,
Thomaier

[Vinzenz Mai]

Hallo,

Tabelle: word

ID | word
---+-----
1  | RETTE
2  | RETTER
3  | RETTEN

es ist ganz sicher aus Gründen der Leseoptimierung sinnvoll, die Zeichenlänge des Wortes (redundant) in einer eigenen Spalte abzuspeichern:

ID | word    | length
---+---------+-------
1  | RETTE   |  5
2  | RETTER  |  6
3  | RETTEN  |  6

Tabelle: word_letter
n = Häufigkeit der Buchstaben in dem Wort

ID_word | letter | n
--------+--------+---
1       | R      | 1
1       | E      | 2
1       | T      | 2
2       | R      | 2
2       | E      | 2
2       | T      | 2
3       | R      | 1
3       | E      | 2
3       | T      | 2
3       | N      | 1

1. Schritt:
   nach der ersten Abfrage sollen alle "Wörter" mit einer bestimmten Länge übrig bleiben

die Abfrage dazu vereinfacht sich zu

SELECT             -- Gib mir  
    ID,            --    ID,  
    word           --    wort  
FROM               -- aus der Tabelle  
    word           --    word  
WHERE              -- wobei nur Wörter mit der  
    length = 6     --    Zeichenlänge 6 berücksichtigt werden sollen.  

Dies ist ganz sicher performanter als ein Join mit Gruppierung und HAVING-Klausel, da sonst *alle* Datensätze berücksichtigt werden müssen.

und folgende Tabelle übergeben werden.

ID_word | letter | n
--------+--------+---
2       | R      | 2
2       | E      | 2
2       | T      | 2
3       | R      | 1
3       | E      | 2
3       | T      | 2
3       | N      | 1

ein einfacher Join mit word_letter

SELECT                  -- Gib mir  
    w.ID      ID_word,  --     die IDs der Worte  
    wl.letter letter,   --     die darin vorkommenden Buchstaben  
    wl.n      n         --     und ihre Anzahl  
FROM                    -- aus der Tabelle  
    word w              --     word (als w angesprochen),  
INNER JOIN              -- die mit der Tabelle  
    word_letter wl      --     word_letter (als wl angesprochen)  
ON                      -- über die Spalten  
    w.ID = wl.ID        --     ID (in beiden Tabellen) verknüpft ist  
WHERE                   -- wobei nur die Worte interessieren,  
    w.length = 6        --     die 6 Zeichen lang sind.  

("RETTE" ist damit schonmal raus)

Diese "Tabelle" kann die Grundlage entweder diverser Selfjoins oder halt diverser Subselects sein. Da die Anzahl der Buchstaben jeweils unterschiedlich ist, kannst Du das dritte Beispiel nicht anwenden, sondern musst Dich mit dem zweiten begnügen :-(

2. Schritt:
   im zweiten Schritt bleiben noch alle Wörter, in denen "R" zweimal vorkommt:

ID_word | letter | n
--------+--------+---
2       | R      | 2
2       | E      | 2
2       | T      | 2

Was performanter ist:
Subselect über die ganze word_letter-Tabelle oder über obige Abfrage, das musst Du mit Deinen Daten selbst durchtesten (EXPLAIN hilft Dir dabei):

SELECT  
    w.word  
FROM  
    word w  
WHERE  
    w.length = 6  
AND  
    w.ID IN (  
        SELECT  
             wl.ID  
        FROM  
             word_letter wl  
        WHERE  
             letter = 'R'  
        AND  
             n = 2  
    )  
AND  
    w.ID IN (  
        SELECT  
             wl2.ID  
        FROM  
             word_letter wl2  
        WHERE  
             letter = 'E'  
        AND  
             n = 2  
    )  

Beachte dabei die Hinweise im Handbuchkapitel Optimizing Subqueries, aber insbesondere den ersten Satz.

Freundliche Grüße

Vinzenz

[Thomaier]

Hallo Vinzenz,
danke für die ausführliche Erläuterung. Folgende Abfrage mit den Buchstaben "eehgn" klappte erstmal sehr gut

  
SELECT w.ID AS ID_word, w.word  
FROM word2 AS w  
INNER JOIN word2_letter wl_e ON w.ID = wl_e.ID_word2 AND wl_e.letter = 'E' AND wl_e.n <= 2  
INNER JOIN word2_letter wl_g ON w.ID = wl_g.ID_word2 AND wl_g.letter = 'G' AND wl_g.n <= 1  
INNER JOIN word2_letter wl_h ON w.ID = wl_h.ID_word2 AND wl_h.letter = 'H' AND wl_h.n <= 1  
INNER JOIN word2_letter wl_n ON w.ID = wl_n.ID_word2 AND wl_n.letter = 'N' AND wl_n.n <= 1  
WHERE wl_e.n+wl_g.n+wl_h.n+wl_n.n = w.length

Das Problem ist nur, dass ich nicht als Bedingung hatte, dass alle Buchstaben vorkommen müssen. Obere Abfrage kommt also über "gehen", "hegen" und "gehn" nicht hinaus. Daher muss es noch die Möglichkeit geben, dass einzelne Buchstaben überhaupt nicht vorkommen. Ich habe mit OR statt AND und mit einer NULL-Angabe im INNER JOIN experimentiert, aber keine Ergebnisse erzielt.

Die Subselect-Struktur hat den Nachteil, dass ich in WHERE nicht auf die Unterabfragen referenzieren kann und damit die meines Erachtens notwendige Angabe von WHERE wl_e.n+wl_g.n+wl_h.n+wl_n.n = w.length raus fällt.

Als Frage bleibt also offen: Wie stelle ich ein, dass nicht alle Buchstaben vorkommen müssen.

Gruß
Thomas

PS: Sorry für das Doppelposting. Stehe unter Zeitstress.

[Thomaier]

Hallo Vinzenz,

Reguläre Ausdrücke sind im allgemeinen noch ziemlich teuer.

Mein Provider hat sich noch nicht beschwert und von der Zeit her geht es auch.

Ich würde auf REGEXP komplett verzichten, statt dessen wegen des speziellen Einsatzzweckes in 29(!) weiteren Spalten die einzelnen Buchstabenhäufigkeiten abspeichern [1] und bei der Abfrage nutzen.

»»[1] ganz bewusst gegen Normalisierung verstoßend. Ich gehe davon aus, dass

es bei dieser DB nur selten zu INSERTs kommt und UPDATE-Operationen fast
   ausgeschlossen sind.

Und dann alle Spalten indizieren? Das Problem ist aber, dass ich wirklich mal dazu übergehen will, dass Nutzer etwas in die DB eintragen können. Das wird sich aber wohl in Grenzen halten. Generell soll es mehr um das Auslesen gehen.

Ich werde den Ansatz mal umsetzen. Lange Abfragen sind nicht das Problem, werden sie doch von PHP generiert.

Dank und Gruß,
Thomas

[Alexander (HH)]

Moin Moin!

»» Reguläre Ausdrücke sind im allgemeinen noch ziemlich teuer.
Mein Provider hat sich noch nicht beschwert und von der Zeit her geht es auch.

Beschweren wird er sich kaum, wenn Du zu viel Resourcen belegst, wird Dein Prozess gekillt oder auf low priority gesetzt. Notfalls wird auch mal die gesamte Domain auf eine "Überlastet"-Seite umgebogen.

"teuer" ist für geringe Last kein Problem, und manchmal kommt man um "teure" Aktionen einfach nicht herum. Man muß sich dessen nur bewußt sein. Wenn ich weiß, dass eine bestimmte Aktion 1000x mehr Aufwand als die durchschnittliche Aktion benötigt, aber nur zweimal täglich vorkommt und auch nur für besonders priviligierte Benutzer, dann lasse ich das so. Ist diese teure Aktion aber für jeden Seitenzugriff nötig, dann ist das einer der ersten Optimierungspunkte, sobald mehr als nur ein paar Seitenaufrufe am Tag stattfinden.

Das Problem ist aber, dass ich wirklich mal dazu übergehen will, dass Nutzer etwas in die DB eintragen können.

Da würde ich auf jeden Fall bei einem RDBMS bleiben, mit Textdateien und dem notwendigen Locking artet der Aufwand dann doch etwas aus.

Und gerade bei dieser DB, wo es nur um einzelne Worte geht, würde ich ein direktes, ungeprüftes Eintragen durch den Benutzer NICHT zulassen. Es wäre sonst viel zu einfach, Deine DB ganz schnell mit ganz viel Müll zu füllen. Entweder trägst DU die neuen Worte ein, die die Nutzer in eine separate Kandidaten-Tabelle (ID, Wort, erklärender Text) füllen, oder Du markierst die ungeprüften Worte in der Haupttabelle als solche und berücksichtigst diese erst einmal nicht oder gibst sie getrennt von den geprüften Worten aus. Du müßtest dann regelmäßig die neuen überprüfen und entweder als geprüft markieren oder löschen.

Alexander