Seite 1 von 2
Suche 'intelligenten' Suchalgorithmus
Verfasst: 25.09.2008 11:21
von Kiffi
Moin,
ich möchte gerne anhand eines Suchausdrucks und einer Liste von
mehreren hundert Einträgen eine Liste von 'best matches' erhalten.
Konkret heißt das: Ich habe einen Suchausdruck 'bubu' und eine zu
durchsuchende LinkedList, die viele Einträge beinhaltet. Nun möchte ich
als Ergebnis eine Liste der Einträge erhalten, die irgendwie zu dem
Suchausdruck passen (sortiert nach den besten Treffern).
Als erstes käme bubu (klar: der Treffer entspricht zu 100% dem Suchbegriff).
Dann käme *bubu* (wie beispielsweise in 123bubuxyz, weil der Suchbegriff irgendwo im Eintrag vorhanden ist)
dann *bub* und *ubu*,
dann *ub* und *bu*
und zu guter letzt *b* und *u*
Gibt's da schon was brauchbares hier im Forum? Mir fehlen ehrlich gesagt
die Begriffe, mit der ich die Suchmaschine hier füttern kann.
Danke im voraus & Grüße ... Kiffi
Verfasst: 25.09.2008 11:29
von Batze
Als ichs mal gesucht habe habe ich jedenfalls nichts gefunden. Allerdings ist das auch schon ne Weile her. Geht's denn um Geschwindigkeit?
Verfasst: 25.09.2008 11:42
von Kiffi
Batze hat geschrieben:Geht's denn um Geschwindigkeit?
wenn ich mir das jetzt selber programmieren würde, dann benötigt der Code
wahrscheinlich ein paar Stunden.
Ein wenig schneller wäre also angenehm. Ist aber jetzt auch nicht sooo
zeitkritisch. Kann ruhig etwas dauern. Muss also nicht in Assembler
geschrieben werden
Grüße ... Kiffi
Verfasst: 25.09.2008 11:44
von STARGÅTE
ich glaube hier ging es schon mal um "Ähnlichkeit"
[gelöst] String A ungefähr wie String B
Verfasst: 25.09.2008 12:00
von Kiffi
@STARGÅTE:
ah! 'Levenshtein Distance'. Damit kann ich schon mal was anfangen.
Dank Dir für den Link!
Grüße ... Kiffi
Verfasst: 25.09.2008 13:03
von STARGÅTE
wo wir gerade wieder dabei sind :
was haltet ihr von dieser Procedure :
Code: Alles auswählen
Procedure.f CompareString(String1$, String2$, Flags=0)
Protected n, i, TotalLength, Value.f, Position, Add.f
Protected Dim Length.l(1), Dim String.s(1)
String(0) = String1$ : String(1) = String2$
Length(0) = Len(String(0)) : Length(1) = Len(String(1))
TotalLength = Length(0)+Length(1)
For i = 0 To 1
For n = 1 To Length(i)
Chr$ = PeekS(@String(i)+n-1, 1)
Position = 0 : Pos = 0
Repeat
Pos = FindString(String((i+1)%2), Chr$, Pos+1)
If Abs(Pos-n) < Abs(Position-n)
Position = Pos
EndIf
Until Not Pos
If Position
Count1 = CountString(String((i+1)%2), Chr$)
Count2 = CountString(String(i), Chr$)
Add = 1-Abs(Count1-Count2)/(Count1+Count2)
Value + (Add-Abs(Position-n)/TotalLength*Add)
EndIf
Next n
Next i
ProcedureReturn Value/TotalLength
EndProcedure
Debug CompareString("Boot", "Moos")
Debug CompareString("Wort", "Mord")
Debug CompareString("Belchh", "Bllech")
Debug CompareString("Zuschnitt", "Zsuchnitt")
Debug CompareString("Regenwurm", "Gegenturm")
Debug CompareString("REGAL", "LAGER")
Debug CompareString("Bananen", "Ananas")
Debug CompareString("Hhhmmmmm", "Hhm")
50,0%
50,0%
71,2%
98,8%
77,8%
48,0%
55,9%
49,6%
ich finde die Ergebnisse ist ganz gut ...
wäre nett wenn jemand etwas "unpassendes" findet, sodass ich vllt etwas verbessern könnte...
Verfasst: 25.09.2008 15:22
von gnasen
hmm
CompareString("pfirsich", "lautsprecherboxen") = 32,4%
bis auf "s" und "ch" keine übereinstimmung.
Vllt sollte der Längenunterschied und/oder Distanz im Wort stärker einbezogen werden. Hab mir den Algo jetzt aber nicht genau angeschaut ^^
Verfasst: 25.09.2008 15:44
von STARGÅTE
naja:
CompareString("pfirsich", "lautsprecherboxen")
also es exestieren schon n paar mehr Übereinstimmungen, und Verschiebung wird berücksichtigt...
klar sind 32% viel bei diesen beiden Strings, aber was würdest du denn gerne erwarten ?
20% ? 10% ? ... 0 geht ja auf keinen fall ....
Verfasst: 25.09.2008 15:55
von gnasen
stimmt, doch mehr Übereinstimmungen.
Trotzdem müsste der Wert niedriger ausfallen. Es müsste mehr acht auf den Zusammenhang gelegt werden, wie ich schon sagte.
"abcdefg" sollte mit "aertbertcertdertfertgert" also fast nichts mehr zu tun haben (ist jetzt ein übertriebenes Beispiel)
Verfasst: 25.09.2008 16:04
von STARGÅTE
beim übertriebenen Beispiel erhalte ich 22%
aber wenn du dein Beispiel (was ja optisch 0% wäre) leicht abwandelst:
"abcdefg" "aertbertcertdertfertgert"
=>>
"abcdefg" "a---b---c---d---f---g---"
dann wäre es ja auch optisch wieder höher, ....
Das Problem was ich jetzt sehe ist: das man menschliche Verständnis für Ähnlichkeit nicht mit dem Computer-Ähnlich vergleichen kann, es wird wohl nie eine gute Procedure dafür geben ....