Anhand Tags den ähnlichsten Eintrag finden (eine Art Scoring)

Einklappen
X
 
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Anhand Tags den ähnlichsten Eintrag finden (eine Art Scoring)

    Ich habe eine etwas kniffilge Aufgabe bei der ich gerne mal ein paar Meinungen und Vorschläge hören würde.

    Ausgangspunkt ist folgender:
    Ich habe eine Tabelle mit Einträgen, diese Einträge können getagged werden. In einer Suchmaske sollen Suchwörter eingegeben werden und gesucht werden. Der Eintrag der am besten passt soll dann ausgegeben werden.

    Es gibt zwei Tabellen

    Eine Tabelle mit Einträgen sieht ungefähr so aus
    EntryID, EntryName,...

    Eine zweite Tabelle mit den zugehörigen Tags sieht so aus
    TagID, EntryID, TagName

    es ist eine 1:n verknüpfung auch wenn eine n:m Verknüpfung (zwei 1:n) vielleicht etwas besser der Normalform entspräche, musste ich etwas den Aufwand gegen Nutzen aufwägen, daher hab ich mich bewusst (wenn auch nicht ganz mit reinem Gewissen) dagegen entschieden.

    Mein Momentaner Stand ist folgendes SQL Statement

    Das Statement ist etwas vereinfacht und funktioniert soweit auch
    select e.*, COUNT(t.EntryID) as Counting FROM entries e, tags t where e.EntryID= t.EntryID AND (t.TagName = 'suchwort1' OR TagName = 'suchwort2') GROUP BY t.EntryID ORDER BY Counting DESC

    Ich bekomme jetzt die Datensätze auf die mindestens ein Suchwort zutrifft und natürlich die Trefferanzahl vom größten zum kleinsten Sortiert.

    1. Frage: Um die Trefferwahrscheinlichkeit zu erhöhen würde ich gerne gewisse Zeichen wie Punkt, Komma, Bindestrich ignorieren. Gibt es eine möglichkeit z.b. den Datenbankeintrag A.B.C finden zu lassen wenn das Suchwort abc ist?

    Zusätzlich will ich aber noch zusätzlich eine Ähnlickeitssuche mit levenshtein machen (eine entsprechende Prozedur hab ich im Internet schon gefunden und eingefügt, sodass man es ggf im SQL Statement verwenden kann), um z.b. vertipper etwas zu kompensieren. eine notlösung wäre halt die vertipper ebenfalls als tags zu speichern, was zwar funktioniert und leicht umzusetzen ist aber meiner meinung nach nicht die schönste lösung ist.

    ich hab mir also gedacht, dass man es vielleicht mit einer Art Scoringverfahren machen könnte, welches dann den Datensatz mit der höchsten Punktzahl zurückgeben würde.
    Mein Ansatz wäre etwas im Hunderterbereich zu machen. Quasi jeder Direkte Treffer würde 100 Punkte geben und je größer das Verhältnis zwischen Wortlänge und Lev Distanz ein kleineren Satz, danach entweder summieren und schauen.

    2. Frage lässt sich sowas überhaupt in Mysql umsetzen? oder ist es doch eher besser wenn man es von php machen lässt, da die Datenmenge nicht überdimensional wird, würde es notfalls gehen.

    3. Frage kann man sowas komplexes mit Storedprocedures berechnen lassen. Das Problem wäre ja die Auswertung von Selectstatements und ich hab mir erstmal ein paar Grundlagen angesehen.

    Frage 1 (weiter oben) wäre übrigens eine sehr wichtige frage, damit schon recht gut zumindest die möglichkeiten einschränken kann

  • #2
    Zitat von st@tic Beitrag anzeigen
    1. Frage: Um die Trefferwahrscheinlichkeit zu erhöhen würde ich gerne gewisse Zeichen wie Punkt, Komma, Bindestrich ignorieren. Gibt es eine möglichkeit z.b. den Datenbankeintrag A.B.C finden zu lassen wenn das Suchwort abc ist?
    Sicher kann man da mit irgendwelchen Zeichenkettenfunktionen on-the-fly rangehen - das zieht aber die Performance nach unten.
    Effektiver wäre es, gleich beim Abspeichern eine "normalisierte" Form des Tags in einer extra Spalte abzulegen, und dann darin zu suchen.


    Gleiches für die Ähnlichkeitssuche, ob mit Levenshtein, SoundEx oder sonstwas realisiert - auch da würde ich das Ergebnis der jeweiligen Funktion vorberechnen und in einer extra Spalte ablegen.

    Das erspart zum einen das Ermitteln des Funktionsergebnisses bei jedem Aufruf, und macht, noch etwas wichtiger, auch die Nutzung eines Index möglich.


    Man könnte u.U. auch noch überlegen, den JOIN (bei deinem Statement übrigens ein impliziter, Pfui!) sein zu lassen - erst mal aus der Tag-Tabelle die IDs aller passenden Tags holen, und dann in einer zweiten Query diese IDs im IN-Operator eines SELECTs auf die Eintrags-Tabelle nutzen. Ob das "nötig" ist, oder kaum noch eine Verbesserung bringt, müsste man dann aber am konkreten Beispiel testen.
    Zuletzt geändert von wahsaga; 15.07.2009, 14:28.
    I don't believe in rebirth. Actually, I never did in my whole lives.

    Kommentar


    • #3
      Zitat von wahsaga Beitrag anzeigen
      Effektiver wäre es, gleich beim Abspeichern eine "normalisierte" Form des Tags in einer extra Spalte abzulegen, und dann darin zu suchen.
      die normalisierte form abspeichern ist ne gute idee und auch leicht und effektiv umzusetzen.

      Zitat von wahsaga Beitrag anzeigen
      Gleiches für die Ähnlichkeitssuche, ob mit Levenshtein, SoundEx oder sonstwas realisiert - auch da würde ich das Ergebnis der jeweiligen Funktion vorberechnen und in einer extra Spalte ablegen.
      da kann ich jetzt nicht so ganz folgen.

      Zitat von wahsaga Beitrag anzeigen
      Man könnte u.U. auch noch überlegen, den JOIN (bei deinem Statement übrigens ein impliziter, Pfui!) sein zu lassen
      ja das ist auch wahr. der join kam als spontanversuch zustande und da ich kein guter "sqler" bin hab ich mich gefreut aber falls ich den join beibehalten wollte, müsste ich ihn auf INNER JOIN ummoddeln oder?

      Kommentar


      • #4
        Zitat von st@tic Beitrag anzeigen
        da kann ich jetzt nicht so ganz folgen.
        Ach so, das geht natürlich nur bei Soundex - Levenshtein nimmt ja zwei Srings als Parameter, und liefert einen Ähnlichkeitswert zurück.

        Soundex hingegen nimmt einen String, und wandelt den um - und zwar in einer Art und Weise, dass "ähnliche" Strings gleiche Ergebnisse erzeugen.
        Das kann man also, im Gegensatz zu Levenshtein, gut im voraus berechnen und in einer extra Spalte ablegen. Dann muss man nur noch den Suchbegriff ebenfalls mit Soundex behandeln, und kann das dann mit dem statischen Spalteninhalt vergleichen.

        Eine genauere Beschreibung gibt's bei der Wikipedia, http://de.wikipedia.org/wiki/Soundex:
        Soundex ist ein phonetischer Algorithmus zur Indizierung von Wörtern und Phrasen nach ihrem Klang in der englischen Sprache. Gleichklingende Wörter sollen dabei zu einer identischen Zeichenfolge kodiert werden.
        Wohlgemerkt, "nach ihrem Klang in der englischen Sprache" - wenn die Begriffe also überwiegend deutsch sind, ist das mnachmal weniger geeignet. Da tut dann die Kölner Phonetik bessere Dienste, http://de.wikipedia.org/wiki/Kölner_Phonetik - entweder selbst implementieren, oder nach was fertigem Suchen. Das kann man dann auch ruhig PHP-seitig schon machen, da muss man keine aufwendige DB-Procedure für Erstellen - beim Eintragen neuer Tags Wert im Script mit berechnen und eintragen, und für den Suchbegriff genauso vor dem Einsetzen in die Query.
        I don't believe in rebirth. Actually, I never did in my whole lives.

        Kommentar


        • #5
          achso meintest du das.
          mit soundex und kölner phonetik hab ich mich auch schon befasst.
          wäre vielleicht ne überlegung wert.

          für weitere anregungen bin ich weiterhin sehr dankbar

          Kommentar

          Lädt...
          X