(tech.+jur.) Fragen zu Suchalgorithmus

[Rol]

Hi,

ich habe eine Suchfunktion auf einer Website. Diese durchsucht eigens dafür angelegte „Beschreibungsfelder“ in einer Produktdatenbank und gibt die Treffer aus.
Die eingegebenen Suchbegriffe schreibe ich in ein Logfile um zu sehen, was die Leute so alles suchen und um so das Angebot (der Website) gezielt erweitern zu können.
Beim anschauen des Logfiles fällt mir auf, dass viele Suchbegriffe „haarscharf“ an den offensichtlich gewünschten Ergebnissen vorbei gehen, manchmal nur durch Tippfehler.

Deshalb nun folgende Fragen:
1. Wie könnte man einen Suchalgorithmus etwas mehr „fuzzy“ machen, so dass er z.B. auch (in Grenzen) mit Tippfehlern zurecht kommt. Ich habe darüber vor einiger Zeit mal was gelesen, finde es aber nicht mehr.

2. Etwas mehr „juristisch“: Jemand sucht nach einem Produkt der Firma X. Die Produkte dieser Firma kann ich aber nicht anbieten (verkaufen nur an handverlesene Händler), ich weiß aber genau, dass sehr ähnliche Produkte der Firma Y vielen der suchenden eine wirkliche Alternative wären.
Kann ich meinen Suchalgorithmus so stricken, dass er nach deutlichen Hinweis auf das Nichtvorhandensein der Firma X die Firma Y anbietet?
Im „offline“ Handel würde man das von einem gutem Verkäufer sogar erwarten. Wenn ich den Gebrauchtwagenhändler nach einen Lamborghini frage und er hat keinen, bietet der mir doch sicher einen der Ferraris an.
Andererseits ist die Angabe von fremden Marken z.B. in den Metas ja auch verboten...

Wie sind Euere Meinungen ?

Gruß
Rol
http://www.reiterlein.de/

[Cheatah]

Hi,

1. Wie könnte man einen Suchalgorithmus etwas mehr „fuzzy“ machen, so dass er z.B. auch (in Grenzen) mit Tippfehlern zurecht kommt.

je nachdem, was Du für ein DBMS benutzt: Vielleicht gibt es das schon. Oracle beinhaltet das Intermedia Text Package, welches für solche Zwecke gedacht ist.

Ansonsten: Vereinfache die Wörter auf Ihre grobe Aussprache[1] - sowohl die Begriffe in der DB, als auch die Suchwörter, natürlich mit dem selben Algorithmus. Auf diese Weise werden Tippfehler (tipfeler, tipfela) quasi dezimiert.

Kann ich meinen Suchalgorithmus so stricken, dass er nach deutlichen Hinweis auf das Nichtvorhandensein der Firma X die Firma Y anbietet?

Warum der Hinweis? Damit könntest Du Dir in der Tat Probleme schaffen. Wenn Du darauf verzichtest - nun, das Prinzip nennt sich "Keyword Advertising". Was Du dem User als Suchergebnis anzeigst, ist letztlich Dein Bier.

Im „offline“ Handel würde man das von einem gutem Verkäufer sogar erwarten.

Jupp. Das findet aber gewöhnlich nicht schriftlich statt ;-)

Cheatah

[1] Verdammich, wenn man's mal braucht, fällt einem der Fachbegriff nicht ein. Kann mir einer aushelfen? :-)

[Wilhelm]

Hi

[1] Verdammich, wenn man's mal braucht, fällt einem der Fachbegriff nicht ein. Kann mir einer aushelfen? :-)

Gruesse
Wilhelm

[Sven Rautenberg]

Moin!

[1] Verdammich, wenn man's mal braucht, fällt einem der Fachbegriff nicht ein. Kann mir einer aushelfen? :-)

In PHP heißt das "soundex". :)

- Sven Rautenberg

[Rol]

Hi,

Ansonsten: Vereinfache die Wörter auf Ihre grobe Aussprache[1] -

Du meinst bestimt "phoenetisch" [1]. Das meinte ich eigentlich auch und suche was zu lesen darüber.

Kann ich meinen Suchalgorithmus so stricken, dass er nach deutlichen Hinweis auf das Nichtvorhandensein der Firma X die Firma Y anbietet?
Warum der Hinweis? Damit könntest Du Dir in der Tat Probleme schaffen. Wenn Du darauf verzichtest - nun, das Prinzip nennt sich "Keyword Advertising". Was Du dem User als Suchergebnis anzeigst, ist letztlich Dein Bier.

Denke ich nicht. Man darf z.B. beim Keyword Advertising nicht einen fremden Firmen-/Markennamen buchen, zumindest wurde mir dass von Suchmaschinenbetreibern definitiv so gesagt.

Im „offline“ Handel würde man das von einem gutem Verkäufer sogar erwarten.
Jupp. Das findet aber gewöhnlich nicht schriftlich statt ;-)

Stimmt. Ich ziehe aber gern Parallelen zu richtigen Leben, das täte auch manch anderem gut ;-).

Guß

Rol

..fällt einem der Fachbegriff nicht ein. Kann mir einer aushelfen? :-)

[1]

[Cheatah]

Hi,

Du meinst bestimt "phoenetisch" [1].

ja, genau, danke (auch Wilhelm) :-)

Das meinte ich eigentlich auch und suche was zu lesen darüber.

http://physics.nist.gov/cuu/Reference/soundex.html beispielsweise?

Denke ich nicht. Man darf z.B. beim Keyword Advertising nicht einen fremden Firmen-/Markennamen buchen, zumindest wurde mir dass von Suchmaschinenbetreibern definitiv so gesagt.

Haben sie gesagt, _man_ dürfe das nicht, oder _bei denen_ dürfe man das nicht? Ich kann mir schon sehr gut vorstellen, dass sich die Suchmaschinenbetreiber gegen derartige Beeinflussung von außen absichern können. Was Du bei Dir machst, ist aber prinzipiell eine andere Geschichte. Wobei ich natürlich erwähnen sollte, dass meine juristische Ausbildung gegen e^(-n) (n->oo) strebt ;-)

Cheatah

[Rol]

Hi,

ja, genau, danke (auch Wilhelm) :-)

gerne.

http://physics.nist.gov/cuu/Reference/soundex.html beispielsweise?

Danke.

Haben sie gesagt, _man_ dürfe das nicht, oder _bei denen_ dürfe man das nicht?

Es ging um einen Internet-Blumenversand. Ich wollte dafür Keywords buchen und das Wort "Fleurop" war noch frei! Als ich mich gleich drauf stürzen wollte, wollte man doch noch einmal Rücksprache mit der Rechntsabteilung nehmen. Daraufhin wurde mir erklärt, dass ich in diesem Fall den hohen Bekanntheitsgrad eines Wettbewerbers ausnutzen würde. Dies gilt imho wirklich (z.Z. und hier) als unlauterer Wettbewerb.

Ich kann mir schon sehr gut vorstellen, dass sich die Suchmaschinenbetreiber gegen derartige Beeinflussung von außen absichern können.

Ich denke, die hätten mir dem Bannerplatz gern verkauft, aber ...

»»Wobei ich natürlich erwähnen sollte, dass meine juristische Ausbildung gegen e^(-n) (n->oo) strebt ;-)
ebenso.

Rol

[Stefan Muenz]

Hallo Rol

1. Wie könnte man einen Suchalgorithmus etwas mehr „fuzzy“ machen, so dass er z.B. auch (in Grenzen) mit Tippfehlern zurecht kommt. Ich habe darüber vor einiger Zeit mal was gelesen, finde es aber nicht mehr.

Ganz trivial ist das sicher nicht. Es gibt z.B. ein Produkt namens FactFinder, das so etwas leistet (http://www.fact-finder.de/). Kostet allerdings (wenn auch nicht die Welt) und ich weiss nicht, wie es sich in bestehende CGI-Anwendungen integrieren laesst.

2. Etwas mehr „juristisch“: Jemand sucht nach einem Produkt der Firma X. Die Produkte dieser Firma kann ich aber nicht anbieten (verkaufen nur an handverlesene Händler), ich weiß aber genau, dass sehr ähnliche Produkte der Firma Y vielen der suchenden eine wirkliche Alternative wären.
   Kann ich meinen Suchalgorithmus so stricken, dass er nach deutlichen Hinweis auf das Nichtvorhandensein der Firma X die Firma Y anbietet?

Ich denke, wenn du bei Suchen nach den Produkten, die du selber nicht vertreiben kannst, als "Treffer" einen Hinweis mit Link auf die Haendler, die es vertreiben anbietest, tust du denen so viel Gutes, dass du unterhalb davon auch noch darauf hinweisen kannst, welche Produkte aus deinem eigenen Sortiment aehnlich sind. Ich wuesste nicht, was dagegen einzuwenden waere.

viele Gruesse
  Stefan Muenz

[Michael Schröpl]

Hi Rol,

1. Wie könnte man einen Suchalgorithmus etwas mehr „fuzzy“ machen,
   so dass er z.B. auch (in Grenzen) mit Tippfehlern zurecht kommt.

das kommt auf die Art der Tippfehler an.

Wenn die Leute nicht wissen, was gemeint ist, dann halte ich die
bereits genannte soundex-Methode für sehr interessant.
Das sind dann aber meiner Meinung nach nicht Tipp-Fehler, sondern
Unkenntnis.

Echte Tippfehler selbst könntest Du natürlich auch bekämpfen.
Ansatzpunkte dafür wären beispielsweise

a) Apaches "mod_speling" (das wohl im wesentlichen "Hamming-Distanz 1"
   und "nicht case-sensitiv" für URL-Zugriffe macht)

oder auch

b) glimpse (das ist ein UNIX-Programm, eine Art aufgemotztes "grep",
   welches parametrisierbare Hamming-Distanzen verarbeiten kann).
   Zu letzterem gibt es auch eine (bzw. sogar mehrere drauf gesetzte
   Suchmaschine (teils Freeware, teils kommerziell).

Viele Grüße
      Michael

[Rol]

Hi,

"Hamming-Distanz 1"

Was ist das?

Rol

[Michael Schröpl]

Hi,

"Hamming-Distanz 1"
Was ist das?

da muß ich mal kurz googlen ... ;-)

Nehmen wir mal den hier: http://www.minet.uni-jena.de/~matthi/www.ct-projekt.smigel.de/node57.html

Ja, das klingt _furchtbar_ mathematisch. Ist es auch. ;-)

Ich wollte den Begriff eigentlich nur verwenden, um ein populäres Beispiel
(das habe ich in der Vorlesung über Codierungstheorie 1983 oder so gelernt)
für eine beliebige mathematische Ähnlichkeitsfunktion zu bringen - da gibt
es sicherlich noch diverse andere.

Die Frage ist ja, wie Du das Tippfehlerproblem quantifizieren kannst.
Du willst ja das "ähnlichste" Wort finden - also eine eindimensionale
Optimierungsaufgabe lösen.
Da wäre es doch sehr hilfreich, wenn Du die "Qualität" eines Korrektur-
vorschlages als skaralern numerischen Wert ausdrücken könntest.

Versuchen wir das doch einfach mal:

• Ist "matematisch" ein Tippfehler für "mathemathisch"?
    Ja, wenn Du mit "Tippfehler" das Weglassen eines Zeichens meinst,
    also die Anzahl der erforderlichen Einfügungen zur Korrektur des Fehlers.
    In dieser "Dimension" ist der "Abstand" zwischen beiden Worten gleich 1.
• Ist "matthematisch" ein Tippfehler für "mathemathisch"?
    Ja, wenn Du mit "Tippfehler" das Hinzufügen eines Zeichens meinst,
    also die Anzahl der erforderlichen Löschungen zur Korrektur des Fehlers.
    In dieser "Dimension" ist der "Abstand" zwischen beiden Worten gleich 1.
• Ist "mathematusch" ein Tippfehler für "mathemathisch"?
    Ja, wenn Du mit Tippfehler das Tippen eines falschen Zeichens meinst,
    also die Anzahl der erforderlichen Änderungen zur Korrektur des Fehlers.
  Das sieht nicht wirklich eindimensional aus; irgend eine Transformation
  dieses sicherich vektoriellen Ähnlichkeitswertes in einen Skalar werden
  wir dringend brauchen.

Und beachte, daß sich eine Korrektur zwar sicherlich als "Einfügung und
Löschung" darstellen ließe (dann Abstand 2), daß dies aber dem aufgetrete-
nen Phänomen nicht gerecht wird (ich habe absichtlich die Taste neben dem
richtigen Buchstaben genommen, um einen Tipp- und nicht einen Rechtschreibe-
fehler zu simulieren.
Der "tatsächliche Abstand" bei einem Tippfehler kann also durchaus vom
Tastatur-Layout des Anwender abhängen - bzw. wenn Du über selbiges irgend-
welche Annahmen treffen kannst, dann kannst Du vielleicht "wahrscheinliche
Tippfehler" von "unwahrscheinlichen" unterscheiden.
Genaus würde Dir helfen, wenn Du weißt, welche Sprache der Benutzer spricht.
Wenn Du also einen Teil der Eingabe "verstehst", kannst Du für den anderen,
fehlerhaften Teil schon gewisse Annahmen treffen, welche Deine Chance beim
Raten erhöhen könnten.

Letzteres ist genau dann wichtig, wenn Du mehrere "richtige" Worte im
selben "Abstand" hast und jetzt entweder die Liste nach einer "Ranking-
Funktion" sortiert anbieten oder "auf gut Glück" sogar einen wahrschein-
lichsten Wert raten bzw. vorschlagen möchtest (für eine URL-redirection
wäre letzteres hilfreich).

Viele Grüße
      Michael
P.S.: Gerade in Deinem Themenbereich ist eine mathematische Formalisierung
      "was ist ein Tippfehler" und eine exakte Fixierung einer Aufgaben-
      stellung unabdingbar. Alles andere bleibt Kristallkugel - andere
      würden "KI" dazu sagen. ;-)