Suche ähnlich wie Google

[GFEMajor]

Hi.

Ich habe wieder mal eine Frage an euch.
Ich bin auf der Suche nach einer Komponente, in die ich eine TStringList (oder etwas ähnliches) durchsuchen kann. Es soll aber keine "normale" Suche sein, sondern so ähnlich wie bei Google. Wenn ein Wort falsch geschrieben wird (zum Beispiel: statt "Breite" "Briete"), dann soll das richtige Wort als Vorschlag kommen (gern auch mehrere Vorschläge). Gibt es da eine Möglichkeit? (Oder wenigstens ein Ansatzpunkt nachdem ich Suchen kann :)).

LG Major

[Luckie]

Das dürfte nicht trivial sein und ich könnte mir vorstellen, dass Google das Geheimnis, wie das funktioniert, nicht so einfach preisgeben wird; letztendlich ist es ja ein essentielles Feature von Google.

[Fussball-Robby]

Eventuell hilft dir diese Unit. Ich bin leider nie dazu gekommen, sie zu testen..

[Andreas L.]

Da wirst du wohl selber eine Liste mit den falsch geschriebenen Wörtern und den korrekten Entsprechungen erstellen müssen. Eine andere Möglichkeit wäre vllt. häufige Buchstabendreher zu ersetzen.

EDIT: Evtl. eines der freien Rechtschreibwörter-Bücher auf die Phrase anwenden.

[Nersgatt]

Wird wohl eine Form/Erweiterung der Phonetischen Suche sein.
So wird bei der Suche nach Mayer auch der Meier gefunden.

[Andreas L.]

Vielleicht kannst du das hier nach Delphi übersetzen:

http://de3.php.net/manual/de/function.soundex.php#84881

[nahpets]

Hallo,

such' mal nach SoundEx, Kölner Phonetik und Levenshteindistanz.
SoundEx müsste bei Delphi schon dabei sein (StrUtils.pas), ist für Deine Vorstellung aber nur sehr bedingt geeignet.
Die Kölner Phonetik bringt für meine Begriffe gute Suchergebnisse, wenn es z. B. um die Prüfung von Adressbeständen auf identische Sätze bei unterschiedlicher Schreibweise geht. Aber auch für Volltextsuchen kann man sie verwenden, wenn man die Texte vorher entsprechend aufbereitet.

Für Dein Beispiel würde sich folgende Vorgehensweise eignen:

In der Stringliste speicherst Du keine Texte, sondern die entsprechenden Representationen der Kölner Phonetik. Die Suchbegriffe wandelst Du vor der eigentliche Suche entsprechend um und suchst dann mit Stringliste.IndexOf.

Die Beschreibung der Kölner Phonetik bei Wikipedia ist gut genug, um innerhalb von vielleicht mal 'ner Stunde, eine entsprechende Funktion zu schreiben. 'ne Forschleife und ein Case sollten da schon fast ausreichen.

[QuickAndDirty]

So weit ich weiß kann Delphi das schon. Phonetische suche/vergleich meine ich.

alles in der Unit StrUtils

[Andreas L.]

Zitat:

Zitat von QuickAndDirty

So weit ich weiß kann Delphi das schon. Phonetische suche/vergleich meine ich.

alles in der Unit StrUtils

Jo:

Zitat:

StrUtils Unit
___________________
Routinen
....
DecodeSoundexInt
DecodeSoundexWord
...
Soundex
SoundexCompare
SoundexInt
SoundexProc
SoundexSimilar
SoundexWord

[QuickAndDirty]

Sollte doch brauchbar sein. Oder gilt das nur fürs Englische?

[nahpets]

Hallo,

Soundex hat für meine Begriffe den Nachteil, dass der erste Buchstabe übernommen wird und die Länge auf vier Zeichen begrenzt ist. Er ist ursprünglich auf englische/amerikanische Namen optimiert (im Jahre 1918).

Soundex bei Wikipedia

Schaut euch die Beispiele dort an und ihr merkt quasi sofort, wo die Schwachstellen liegen. Chaos und Kaos würden nie als identisch oder auch nur ähnlich erkannt.

[Andreas L.]

Zitat:

Zitat von nahpets

Hallo,

Soundex hat für meine Begriffe den Nachteil, dass der erste Buchstabe übernommen wird und die Länge auf vier Zeichen begrenzt ist. Er ist ursprünglich auf englische/amerikanische Namen optimiert (im Jahre 1918).

Soundex bei Wikipedia

Schaut euch die Beispiele dort an und ihr merkt quasi sofort, wo die Schwachstellen liegen. Chaos und Kaos würden nie als identisch oder auch nur ähnlich erkannt.

Die Funktion SoundEx erwartet als zweiten Parameter eine Längenangabe als Integer. Hier könnte man die Länge des Input-Strings nehmen und angefügte Nullen nachher entfernen.

Delphi-Quellcode:

ShowMessage(StringReplace(SoundEx(Edit1.text, Length(Edit1.text)), '0', '', [rfReplaceAll]));

[nahpets]

Zitat:

Zitat von Andreas L.

Die Funktion SoundEx erwartet als zweiten Parameter eine Längenangabe als Integer. Hier könnte man die Länge des Input-Strings nehmen und angefügte Nullen nachher entfernen.

Delphi-Quellcode:

ShowMessage(StringReplace(SoundEx(Edit1.text, Length(Edit1.text)), '0', '', [rfReplaceAll]));

Diese Variante entspricht aber dann nicht dem patentierten SoundEx, was sicherlich im Bezug auf die Vergleichbarkeit bei längeren Vergleichswerten vorteilhaft ist. Das Problem mit dem Anfangsbuchstaben bleibt. Gerade bei Worten die mit c oder k, v oder w... ist SoundEx nicht wirklich hilfreich.

Nehmen wir mal die Wikipediabeispiele:

Code:

Britney => BRTN => B635, 
Spears => SPRS => S162, 
bewährten => BRTN => B635, 
Superzicke => SPRZCK => S16222 => S162.

Von klanglicher Ähnlichkeit oder Schreibfehlern, wie Google sie erkennt, ist man hier weit entfernt.

[QuickAndDirty]

In diesem Link gibt es eine Abwandlung fürs slawische und jiddische
http://www.jewishgen.org/infofiles/soundex.html

Die kodieren auch den Anfangsbuchstaben

[QuickAndDirty]

Hier gibts was dazu
http://www.delphipraxis.net/internal...ct.php?t=41897

[Andreas L.]

Zitat:

Zitat von nahpets

Zitat:

Zitat von Andreas L.

Die Funktion SoundEx erwartet als zweiten Parameter eine Längenangabe als Integer. Hier könnte man die Länge des Input-Strings nehmen und angefügte Nullen nachher entfernen.

Delphi-Quellcode:

ShowMessage(StringReplace(SoundEx(Edit1.text, Length(Edit1.text)), '0', '', [rfReplaceAll]));

Diese Variante entspricht aber dann nicht dem patentierten SoundEx, was sicherlich im Bezug auf die Vergleichbarkeit bei längeren Vergleichswerten vorteilhaft ist. Das Problem mit dem Anfangsbuchstaben bleibt. Gerade bei Worten die mit c oder k, v oder w... ist SoundEx nicht wirklich hilfreich.

Nehmen wir mal die Wikipediabeispiele:

Code:

Britney => BRTN => B635, 
Spears => SPRS => S162, 
bewährten => BRTN => B635, 
Superzicke => SPRZCK => S16222 => S162.

Von klanglicher Ähnlichkeit oder Schreibfehlern, wie Google sie erkennt, ist man hier weit entfernt.

Ja, du hast recht. Die Ergebnisse werden aber besser wenn man die Routine SoundExInt verwendet. Bsp.:

Zitat:

Britney->34444754
Spears->497547233
bewährten->34444754
Superzicke->497553407
Khaos->277416350
Chaos->57177422
Briete->34336709
Breite->34336709
Brite->34336709
Mach mal->333318833
Macht->332929871
Geländer->170254232
Gländer->170254232
Länder->308706182
Laender->308706182
Laendr->308706182
Ländr->308706182

Das ist nicht das Non-Plus-Ultra. Aber für einfache Suchen reicht das doch vollkommen, oder?

[Gausi]

Und wenn man das ganze ohne Soundex machen will, was für Buchstabendreher und/oder Vertipper nur bedingt geeignet ist, muss man sich da über Levenshtein was selber basteln.

Ich habe da mal was vorbereitet ;-) http://www.delphipraxis.net/internal...t.php?t=134539

Eine direkte Funktion "Meinten Sie" ist nicht dabei, aber die alternativen Schreibweisen werden auch gefunden. :D

[Andreas L.]

Zitat:

Zitat von Gausi

Und wenn man das ganze ohne Soundex machen will, was für Buchstabendreher und/oder Vertipper nur bedingt geeignet ist, muss man sich da über Levenshtein was selber basteln.

Ich habe da mal was vorbereitet ;-) http://www.delphipraxis.net/internal...t.php?t=134539

Eine direkte Funktion "Meinten Sie" ist nicht dabei, aber die alternativen Schreibweisen werden auch gefunden. :D

Wurde ja schon im 2 Post verlinkt. Sieht jedenfalls interessant aus :thumb: Sollte sich der Threadersteller mal reinziehen.

[Gausi]

Ups, das habe ich übersehen. Der ist aber auch kurz und versteckt. :wink:

[nahpets]

Hallo,

@Andreas L.

Zitat:

Zitat von Andreas L.

Ja, du hast recht. Die Ergebnisse werden aber besser wenn man die Routine SoundExInt verwendet. Bsp.:

Zitat:

Britney->34444754
Spears->497547233
bewährten->34444754
Superzicke->497553407
Khaos->277416350
Chaos->57177422
Briete->34336709
Breite->34336709
Brite->34336709
Mach mal->333318833
Macht->332929871
Geländer->170254232
Gländer->170254232
Länder->308706182
Laender->308706182
Laendr->308706182
Ländr->308706182

Das ist nicht das Non-Plus-Ultra. Aber für einfache Suchen reicht das doch vollkommen, oder?

Über SoundExInt bin ich noch nicht gestolpert :oops: , habe was ähnliches seinerzeit mit dBase und später mit Turbopascal realisiert, um größere Datenbestände zu überarbeiten (dBase IV war da noch ganz neu).
Ausgehend von Deinen Beispielen halte ich diese Variante für die gestellte Aufgabe für aussreichend, selbst für mein "Doppeltensuchprogramm" für unser CRM ist es eine Überlegung wert, dies noch zusätzlich mit einzubauen.

@Gausi:

Deine Routinen habe ich mir noch nicht angeschaut, werde es aber asap nachholen.

Die Kombination von Kölner Phonetik und Levenshtein, hat mir bisher die besten Ergebnisse gebracht.

[GFEMajor]

Wow, ich bin begeistert. So viele Antworten in so kurzer Zeit.
Ich werd mir die Sachen mal anschauen, aber auf den ersten Blick scheint mir die approxstrutils am besten geeignet für mein Problem. Ich muss nur schauen sie auch meinen Laufzeitanforderungen entsprechen. Aber das wird sich ja leicht testen lassen :).

Auf jeden Fall ein großes Dankeschön an alle schoneinmal.

LG Major