Suche 'intelligenten' Suchalgorithmus

[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

[Batze]

Als ichs mal gesucht habe habe ich jedenfalls nichts gefunden. Allerdings ist das auch schon ne Weile her. Geht's denn um Geschwindigkeit?

[Kiffi]

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

[STARGÅTE]

ich glaube hier ging es schon mal um "Ähnlichkeit"

[gelöst] String A ungefähr wie String B

[Kiffi]

@STARGÅTE:

ah! 'Levenshtein Distance'. Damit kann ich schon mal was anfangen.
Dank Dir für den Link!

Grüße ... Kiffi

[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...

[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 ^^

[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 ....

[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)

[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 ....