Rechtschreibprüfung bzw. "Meinten Sie"-Funktion

[klausschreiber]

Hallo,

ich möchte mit PHP eine "Meinten Sie" Funktion umsetzen. Wie umfangreich die sein soll, weiß ich noch nicht genau, kommt wohl auch auf die Umsetzungsmöglichkeiten drauf an.

Es gibt in mySQL ja den soundex-Algorithmus oder man könnte auch selber den Metaphone Algorithmus implementieren, aber die sind ja für die englische Sprache optimiert und finden auch normale Vertipper vermutlich nicht so gut, wie ein Distanzalgorithmus ala Levenshtein. Aber den Levenshtein kann man ja nicht performant auf eine komplette Wortdatenbank anwenden (lediglich die Firma exorbyte hat es wohl geschafft, eine Art Levenshtein Algorithmus zu entwickeln, der 2,5 Millionen Wörter in unter 10 Millisekunden vergleichen kann).

Ich habe mir auch mal die Wörterbücher von OpenOffice angeschaut, da scheint es eine Textdatei mit allen einzelnen Wörtern in der Grundform zu geben, eine mit Zusammensetzungen und dann noch eine Datei mit Affixen. Hinter den Wörtern ist teilweise etwas angegeben, was nach Wortart oder so aussieht, leider habe ich nichts genaueres gefunden. Wollte auch mal den Source Code anschauen, aber hab die Stelle nicht gefunden und war außerdem zu doof, ne Doku zu finden^^.

Habe in dem Kontext auch noch etwas von einem KD-Baum gelesen, allerdings dazu auch noch nichts wirklich aufschlussreiches gefunden.

Meine Idee bisher ist, die Grundformen in der Datenbank zu speichern (bei häufig verwendeten Wörtern vielleicht auch die Konjugationen/Deklinationen). Dann will ich einen deutschen Stemmer Algorithmus auf das Wort anwenden (z.B. den hier) und dieses herauskommende Wort in eine Zahl umwandeln, wobei ähnlicher Wörter ähnliche Zahlen haben. So soll man dann in der Datenbank durch Suche nach einer Zahlenrange eventuell passende Wörter finden. Falls ich ein komplettes Wörterbuch integrieren will und nicht nur ein paar Fachbegriffe für die Suche, würde ich die aus der Datenbank zurückgegeben Grundformen vielleicht noch per Algorithmus deklinieren/konjugieren und auf diese wenigen Wörter dann den Levenshtein Algorithmus anwenden (Ich könnte natürlich auch alle Konjugationen und Deklinationen in der Datenbank speichern, aber das wären dann halt 20 Millionen Einträge oder so).

An einem Algorithmus, der ähnliche Wörter in ähnliche Zahlen umwandelt, habe ich mich schon rumprobiert. Hat auch mit ein paar Beispielen geklappt, aber genau habe ich es noch nicht getestet. Aber es müssen dafür doch auch schon Lösungen existieren, da ja jedes Programm eine Rechtschreibprüfungen hat und auch Google so eine "Meinten Sie" Funktion. Ich glaube nicht, dass die sich alle auf soundex verlassen.

Mir ist klar, dass die Levenshtein Umsetzung von exorbyte wohl nicht öffentlich zu finden ist, aber kennt jemand andere gute Umsetzungen bzw. hat Ideen?

Danke und sorry für den langen Text^^,
Klaus

 

[tobomator]

ich habe eine ähnliche Idee für eine Verschlüsselung mal erdacht, aber bislang nicht umgesetzt.

Was wäre denn, Du zerlegst die Wörter in Silben ?
Keine Ahnung wieviele Silben es gibt auf den Duden angewendet, aber es wären weitaus weniger Silben als alle Worte darin.

Du zerlegst die Wörter in Silben, wo jede Silbe einen Zahlenwert hat und legst eine art Checksumme oder was auch immer du nun machst an.
Darüber ist nun jedes Wort eindeutig identifiziert.

Eventuell geht eine Suche über diese Möglichkeit schneller.

Wie gesagt, nur ein Tip mit dem zerlegen in Silben.
Der Rest ist hier mal nicht erwähnt...

 

[klausschreiber]

danke für deine Antwort.
Naja, es geht ja nicht darum, ein Wort eindeutig zu identifizieren, sondern ähnliche Wörter identifizierbar machen. Das heißt wenn ich z.B. versehentlich "lauefn" soll unter den ähnlichen Wörtern "laufen" sein. Weiß jetzt nicht genau, inwieweit man durch die Zerlegung in Silben ein besseres Ergebnis bekommen soll. Bin jetzt allerdings auch bettreif, daher werde ich es mir später nochmal anschauen.

Habe jetzt auch mal meinen Zahlenalgorithmus mit einer Datenbank von 10.000 Wörtern ausprobiert, aber leider war es totaler Griff ins Klo. Auch bei sehr engen Ranges kamen zu viele Wörter zurück, die überhaupt nicht passten.

 

[theHacker]

Also Soundex kannstde vergessen: Is der Tippfehler im ersten Buchstaben kriegstde nie das richtige Wort raus. Längere Wörter sind plötzlich ähnlich zu ganz anderen komischen Wörtern, weil Soundex alles ignoriert, nachdem der Algorithmus drei Ziffern erfasst hat.

 

[ice-breaker]

Also bei einem Projekt, bei dem ich mal geholfen habe, habe wir sehr gute Ergebnisse mit der Kölner Phonetik erzielt.
Erkennt natürlich auch nicht alle Fehler, hatte aber eine gute Trefferquote für die Effizienz, die er bietet (kann Datenbank Indexe nutzen)

 

[tobomator]

Der Sinn im zerlegen in Silben ist vielleicht nicht simpel oder gar einfach, aber Du hast geschrieben, Tipfehler sollen erkannt werden.
Dann erstelle eine Datenbank über alle Silben.
Zerlege die Wörter in Silben, dann vergleiche.
Silbe Korrekt -> nächste Vergleichen -> ... Alle Silben korrekt ? Ok
Wenn es um vertipper geht, kann man silben permutieren und jede Permutation verlgeichen bis ein Treffer existiert.
Wenn allerdings ein Wörterbuch zusätzlich existiert, kann man alle richtigen Silben mit der permutierten "Konkatenieren" und dann im Wörterbuch vergleichen.
Sind halt nur Überlegungen von mir.
Den Aufwand in Geschwindigkeit umzusetzen ist Deine Aufgabe !

Die Beispiele in dem Algorithmus der etwas abtrennt ist nicht zu empfehlen.

Sieg, Siegel, Siegmund, Siegesmund, Sieger, ... werden denn zu was ?

 

[ice-breaker]

Silbenzerlegung ist eine schlechte Idee, lässt sich nicht wirklich effizient in relationalen Datenbanken umsetzen, viel zu viele Results die nach jedem Schritt gejoint werden müssen.

Es gibt viele Möglichkeiten das gesuchte zu realisieren, aber es scheint wohl in einer relationalen Datenbank implementiert zu werden, und da gibt es wirklich nur wenige Modelle die funktionieren, also nur das Suchen nach ähnlich klingenden Wörtern anhand eines festen Wertes (Key-Lookups) und danach einer Filterung der Möglichkeiten, um das Wort zu finden, welches am nächsten ist (Dammerau-Levenshtein-Distanz ?)

Ps: Stemmer haben wir auch ausprobiert, die Ergebnisse waren viel zu ungenau, sowohl nur normales Stemming als auch Stemming mit folgender Kölner Phonetik.

PS2: KD-Trees? Ne, das funktioniert vorne und hinten nicht.

 

[tobomator]

Wer sagt, das eine relationales DBMS zum Einsatz kommen muß ?
Ich habe an eine Index Datenbank gedacht.

Bsp.:

Siegesmund

Sie - ges - mund

Du gehst die Buchstaben entlang wie ein Pfad

s->i->e->g->e->s->...

so würder auch Sie - ger gehen

das heißt: im knoten nach siege-> 1> s 2> r

Sowas in der Art hätte ich mir hier vorgestellt.
Wenn man sich bei seiner Entwicklung nur darum kümmert, passt es in ein relationales DBMS was bringt es dann ?

 

[ice-breaker]

Weil klausschreiber mit keinem Wort erwähnt hat, dass er anderes zur Verfügung hat, als eine Datenbank, und dies hier leider auch nie der Fall ist.

Was du beschreibst nennt sich ein Trie, das hilft dir aber nicht Fehler in einem Wort zu erkennen, da es stupide dem Pfad folgen wird.
Du erreichst also nur, dass ab einem gewissen Punkt, wenn kein Pfad mehr gefunden werden kann, der dem gesuchten Pfad entspricht, einfach ein anderer gewählt wird.
Wenn du dich somit aber schon sehr früh vertippst, landest du auf einem komplett falschen Pfad und findest nur noch Kauderwelsch, man müsste also Heuristiken einbauen, um potentielle Pfade zu erkennen und gemachte Entscheidungen revidieren (Backtracking) zu können, das würde aber in einer immens hohen Komplexität enden.

Um dein Beispiel zu entkräften:
Du hast aus Versehen seigesmund, eingegeben, du wirst also bei Worten landen, die komplett verschieden sind (sea-world, seegang, seeungeheuer)

 

[tobomator]

wenn du nur jeden einzelnen post als solches verstehst, dann bitte ich dich auch mal die davor zu lesen.
Da stehen auch ein paar Andere Dinge drin, die mit in Betracht gezogen werden müssen, wenn Du swas schreibst.

 

[ice-breaker]

Habe ich, es ist aber genau der gleiche gedankliche Fehler, nur auf einer höheren Ebene
Wenn eine Silbe falsch ist, kommt man auf einen falschen Weg, wenn du bei jedem Weg einfach aber nochmal deine "Silbe permutieren" willst, hast du deutlich mehr Pfade zu untersuchen, und deine Suchtiefe steigt exponentiell, vergleichbar mit einem Baum: in jeder Suchtiefe kommen neue mögliche Permutationen hinzu, sehr schlechtes algorithmisches Design.


auf die Idee mit der Verschlüsselung gehe ich mal nicht ein

 

[Benutzer-621]

Mal abgesehen davon, dass Google bestimmt ein eigenes Wörterbuch hat wirst Du sicherlich nicht darum herumkommen dir auch eines anzulegen.

Um die Basis für Dein Wörterbuch zu erschaffen kannst Du allein schon Wörter benutzen die häufig falsch geschrieben werden (https://www.korrekturen.de/beliebte_fehler_a.shtml).

Ein weiterer Schritt wäre, dem "Typosquatting" (Buchstabendreher) zu begegnen. Du kannst hier entweder überprüfen ob die Zeichenketten gleich lang sind und das Vorkommen der Häufigkeit ihrer Buchstaben identisch sind oder Toleranzen von ±X existieren. wikeipdai = wikipedia, deutshcepsot = deutschepost.

Eventuell wäre es auch hilfreich, wenn Du mehrere Vorschläge machst und den Zähler des geklickten Wortes in Relation zum gesuchten Wort erhöhst. Des Weiteren könntest Du vergleichen inwieweit die eingegebenen Wörter eines Users miteinander verwandt sind. Denn es kommt öfters vor, dass ein User mehrmals nach gleichklingenden Wörtern sucht (Whittaker, Whitaker, Whitacre).

Ansonsten muss Du eben ein Mittelweg finden aus den zur Verfügung stehenden Funktionen wie Kölner Phonetik, Soundex, Metaphone, Levenshtein und vielleicht noch T9, wobei dieses auch nur vorgegebenen Schemata folgt.

Bei phpgangsta.de gibt es noch einen Artikel hierzu, in den Kommentaren sind auch einige Links zu nicht-nativen Bibliotheken vorhanden. Wobei hier wieder die englische Sprache vorherrschend ist.

 

[klausschreiber]

wow, hier gings ja rund
Vielen Dank allen für die Vorschläge!

Ich habe jetzt mal die Kölner Phonetik getestet. Die funktioniert eigentlich ganz gut, aber es ist halt auch "nur" ein phonetischer Algorithmus. Bei "tastatur" und "tsatatur" macht er schon Probleme.

Man könnte den Algorithmus natürlich noch mit einem Algorithmus kombinieren, der nur auf Buchstabendreher prüft (man bräuchte die Buchstaben ja nur alphabetisch anordnen, oder falls die Häufigkeit der einzelnen Buchstaben egal ist, jedes Wort in einem Wert aus 26 Bits, je einen für jeden Buchstaben, repräsentieren).

Kleine Tippfehler ala "Tedt" statt "Test" könnte man vermutlich auch noch erkennen, in dem man jedem Buchstaben eine Zahl zuweißt und die dann addiert oder multipliziert oder so und schaut, ob die Zahl ähnlich ist.

Wenn aber ein Buchstabe zuviel ist, z.B. "Terst" statt "Test" versagen alle meine Algorithmen, die performant auf Datenbanken anwendbar sind. OpenOffice findet aber bei der Eingabe von "Terst" auch "Test", also muss es ja irgendeine Lösung geben. Auch OO wird ja wohl kaum die komplette Wortliste mit Levenshtein durchgehen. Nur habe ich es leider nicht geschafft, die Stelle im Quelltext zu finden.

Bezüglich Relationale Datenbank:
Ja, ich hatte eigentlich vor, das in mySQL zu machen. Aber wenn es eine andere Lösung gibt, die viel besser ist, wo man als Privatmensch und Hobbywebmaster (also Nichtmillionär^^) drankommt, dann bin ich natürlich dafür offen.

@k212198:
Danke für den Link zum Wörterbuch mit häufigen Fehlern, sowas hatte ich schon gesucht. Die Sache mit Zähler erhöhen usw. ist eine gut Idee, aber bevor ich daran denke, sollten erstmal die Grundlagen passen.

@ice-breaker:
Naja, wie will man das ohne Stemmer machen? Oder hattet ihr dann wirklich alle möglichen Formen eines Wortes in der Datenbank? Das wären bei einem Verb ja mal 30 Formen oder so (alle Präsens, Imperfekt, Perfekt, Passiv usw.). Und OO schafft es ja auch irgendwie, nur die Grundform in der Wortliste zu haben.

 

[ice-breaker]

Ich habe jetzt mal die Kölner Phonetik getestet. Die funktioniert eigentlich ganz gut, aber es ist halt auch "nur" ein phonetischer Algorithmus. Bei "tastatur" und "tsatatur" macht er schon Probleme.

ja das Problem hast du aber bei allen Methoden, die sich auf Datenbanken abbilden lassen, eine Möglichkeit ist da natürlich Dreher der Zahlencodes mit einer Referenz auf das echte Wort abzuspeichern, kostet Speicherplatz, aber erhöht die Treffergenauigkeit.

Auch OO wird ja wohl kaum die komplette Wortliste mit Levenshtein durchgehen. Nur habe ich es leider nicht geschafft, die Stelle im Quelltext zu finden.

OpenOffice hat ganz andere Möglichkeiten als du, die könne spezielle Datenstrukturen für soetwas erschaffen und dann eben laden, sollte das ne halbe Sekunde brauchen, stört das niemanden, bei PHP kannst du sowas aber eben nicht verkraften.

Bezüglich Relationale Datenbank:
Ja, ich hatte eigentlich vor, das in mySQL zu machen. Aber wenn es eine andere Lösung gibt, die viel besser ist, wo man als Privatmensch und Hobbywebmaster (also Nichtmillionär^^) drankommt, dann bin ich natürlich dafür offen.

auf deutsch, kein eigener Webserver, keine Zusatzsoftware.
Dann musst du dich mit einer der Varianten begnügen

@ice-breaker:
Naja, wie will man das ohne Stemmer machen? Oder hattet ihr dann wirklich alle möglichen Formen eines Wortes in der Datenbank? Das wären bei einem Verb ja mal 30 Formen oder so (alle Präsens, Imperfekt, Perfekt, Passiv usw.). Und OO schafft es ja auch irgendwie, nur die Grundform in der Wortliste zu haben.

wird denn nach Verben gesucht? Wir hatten eben eine Platform wo nur nach Nomen gesucht wird (eine Art Tagging von Produkten).
Wenn wirklich nach Verben gesucht werden soll, muss es natürlich ein Stemmer sein, aber denk daran, dass die Wörter dadurch teilweise sehr ungenau werden, du also im 2. Schritt unter allen potentiellen Kandidaten nochmal den besten filtern musst.




Hier nochwas möglicherweise interessantes:
Google Answers: Spelling Suggestion Technology

 

[klausschreiber]

Danke für deine Antwort.

ja das Problem hast du aber bei allen Methoden, die sich auf Datenbanken abbilden lassen, eine Möglichkeit ist da natürlich Dreher der Zahlencodes mit einer Referenz auf das echte Wort abzuspeichern, kostet Speicherplatz, aber erhöht die Treffergenauigkeit.

Naja, das ist ja leider nicht nur ein Dreher im Zahlencode, sondern einmal kommt 8227 und einmal 28227 raus. Aber das könnte man ja teilweise lösen, in dem man in einer zweiten Spalte die Buchstaben alphabetisch sortiert und danach sucht. Nur so Sachen wie "Testr" erfasst man damit halt leider nicht.

auf deutsch, kein eigener Webserver, keine Zusatzsoftware.
Dann musst du dich mit einer der Varianten begnügen

Naja, einen V-Server könnte ich schon auftreiben, aber halt keine Software für mehrere 1000 Euro anschaffen. Aber exorbyte hat es ja auch geschafft, allerdings weiß ich natürlich nicht, ob ein relationales Datenbanksystem verwendet wurde.

wird denn nach Verben gesucht? Wir hatten eben eine Platform wo nur nach Nomen gesucht wird (eine Art Tagging von Produkten).

Das ist eigentlich ein guter Hinweis. Zumindest wäre es kein Weltuntergang, wenn Verben erstmal nicht funktionieren. Dann lasse ich die wohl erstmal weg, um die Komplexität zu verringern.

 

[theHacker]

[...] aber halt keine Software für mehrere 1000 Euro anschaffen.

Muss es ja nicht sein

So mal als Idee: Wenn du mal von mehr als nur PHP ausgehst; angenommen du hast einen (V-)Server, kannst du schon mal das Wörterbuch im Speicher halten. Damit is das

OpenOffice hat ganz andere Möglichkeiten als du, die könne spezielle Datenstrukturen für soetwas erschaffen und dann eben laden, sollte das ne halbe Sekunde brauchen, stört das niemanden, bei PHP kannst du sowas aber eben nicht verkraften.

-Argument weg. Die halbe Sekunde investiert du einmal geballt beim Hochfahren, fertig.

Klar is dieses Posting jetzt nicht die Lösung auf alle deine Probleme, aber es zeigt dir einen Ausweg, wenn du ein Stückchen weiterdenkst.
Interessant bleibt dennoch, wie du möglichst platzsparend, schnell und effektiv die nötigen Wörter findest.

 

[ice-breaker]

Neija, wenn du einen vServer zur Verfügung hast, ändert das natürlich einiges, Lucene (Solr nutzen ) kann zB Spell Suggestions, wenn ich mich recht entsinne.

 

[klausschreiber]

danke für eure Antworten. Von Lucene habe ich auch schon gelesen. Aber ich bin mir nicht sicher, ob das so individuell anpassbar ist, wie ich es gerne hätte.

Mir kam aber eh heute Mittag eine Idee, die mir glaub zum Durchbruch verholfen hat. Durch die Umwandlung und Speicherung jedes Wortes in einer speziellen Bitform, sowie arithmetische Funktionen habe ich es geschafft, dass mir aus einer Datenbank mit 10.000 Einträgen eine nach Anzahl der (Levenshtein-)Fehler sortierte Liste in 0,009x Sekunden ausgegeben wird. Wenn ich nur alle Fehler kleiner gleich 1 will, dauert es 0,006x Sekunden und wenn ich die Liste komplett ohne Bedingung will nur mit Ausgabe der Fehleranzahl dauert es 0,000x Sekunden.

Sind zwar "nur" 10.000 Wörter in der Datenbank, aber die Geschwindigkeit müsste doch auch für einiges mehr Wörter reichen, oder?

Wenn ich nun "testr" eingebe, wird mir mit einem Fehler "erst", "steht", "Streit", "Rest", "startet", "dreht", "Test", "strebt", "steuert" und "Trends".
Das ist zwar noch nicht ganz perfekt, aber das "dreht" kommt von einer phonetischen Ersetzung (lasse d durch t ersetzen), die womöglich noch nicht ganz optimal ist, aber das kann man ja noch ändern. Die anderen Fehler kommen daher, dass die Reihenfolge der Buchstaben überhaupt nicht beachtet wird. Da ich aber noch 12 Bits frei habe, lässt sich da ja vielleicht noch was machen, außerdem ist es ja kein Problem, ein paar wenige Wörter noch per PHP zu vergleichen.

Was ein kleines Problem ist, ist dass PHP nur mit 32 Bit Integern rechnen kann. Ich brauche aber 64 Bit. Ich mache es derzeit so, dass PHP mir 2 32 Bit Integers erstellt. Für den Aufbau der Datenbank habe ich mit mySQL einen Integerwert nach links geshiftet und per bitwise OR zusammengefügt. Für die Abfragtests habe ich es erstmal per Hand gemacht. Wenn ich z.B.

bits^((4096 << 26) | 4176)

mit in die Abfrage schreibe (je nach Art der Abrage im WHERE oder im SELECT Teil), dann ist mySQL schon zu schlau, die Klammer nur 1x auszurechnen und nicht bei 10.000 Datenbankeinträgen 10.000 mal, oder? ("bits" ist der Name einer Spalte, das muss also jedes Mal berechnet werden, das in der Klammer aber natürlich nicht).


Danke und Gruß,
Klaus
(auch wenns schon wieder so nen ewig langer Text ist, irgendwie schaff ich das nie kürzer^^)

 

[ice-breaker]

Sind zwar "nur" 10.000 Wörter in der Datenbank, aber die Geschwindigkeit müsste doch auch für einiges mehr Wörter reichen, oder?

nein, nur weil es mit wenig Datensätzen gut funktioniert, muss es nicht auch mit vielen.

Wenn ich nun "testr" eingebe, wird mir mit einem Fehler "erst", "steht", "Streit", "Rest", "startet", "dreht", "Test", "strebt", "steuert" und "Trends".
Das ist zwar noch nicht ganz perfekt

also meine Meinung eine ganze Menge false-positives, nicht sehr berauschend.

("bits" ist der Name einer Spalte, das muss also jedes Mal berechnet werden, das in der Klammer aber natürlich nicht).

du hast doch gar nichts gewonnen
Dein MySQL-Index kann nicht genutzt werden, dann kannst du doch auch gleich den Levenshtein nehmen.

 

[klausschreiber]

danke für die Antwort.

Hmm, aber ne einfache Xor-Funktion, sowie darauf folgende Bitzählung ist doch um einiges schneller als ein kompletter Levenshtein?