Ich versuche, eine Methode zu entwickeln, um eine Entität mit einer Anzahl von Eigenschaften zu erstellen und nach ähnlichen Entitäten in der Datenbank zu suchen (so viele der Eigenschaften wie möglich in der richtigen Reihenfolge zu finden). Die Idee ist, dass es dann% davon zurückgibt, wie ähnlich es ist.
Die Reihenfolge der Eigenschaften sollte ebenfalls berücksichtigt werden, daher sind die Eigenschaften am Anfang wichtiger als die am Ende.
Zum Beispiel:
Punkt 1 - A, B, C, D, E
Punkt 2 - A, B, C, D, E
Wäre eine 100% Übereinstimmung
Punkt 1 - A, B, C, D, E
Punkt 2 - B, C, A, D, E
Dies wäre keine perfekte Übereinstimmung, da die Eigenschaften in einer anderen Reihenfolge sind
Punkt 1 - A, B, C, D, E
Punkt 2 - F, G, H, I, A
Wäre eine niedrige Übereinstimmung, da nur eine Eigenschaft gleich ist und sie sich in Position 5 befindet.
Dieser Algorithmus wird für Tausende und Abertausende von Datensätzen ausgeführt, sodass er leistungsstark und effizient sein muss. Irgendwelche Gedanken, wie ich das in PHP / MySQL schnell und effizient machen könnte?
Ich dachte über levenshtein nach, aber soweit ich das beurteilen kann, würde ich auch auf die Abstand zwischen zwei völlig verschiedenen Wörtern in Bezug auf die Rechtschreibung. Scheint nicht ideal für dieses Szenario zu sein, es sei denn, ich benutze es nur in der falschen Art.
Es könnte sein, dass es nur in MySQL möglich ist, vielleicht mit einer Volltextsuche oder so.
Dies scheint eine nette Lösung zu sein, die allerdings nicht für dieses Szenario entwickelt wurde . Vielleicht könnte Binär-Vergleich in irgendeiner Weise verwendet werden?
was ich tun würde, ist die Reihenfolge und den Wert der Eigenschaft in eine Zahl zu kodieren. Zahlen haben den Vorteil schneller Vergleiche.
Das ist eine allgemeine Idee und könnte noch etwas Arbeit brauchen, aber ich hoffe, dass es in irgendeiner Weise helfen würde.
Berechnen Sie für jede Eigenschaft eine Zahl (irgendeine Art von Hash) und multiplizieren Sie die Zahl, die die Reihenfolge der Darstellung der Eigenschaft für ein Element darstellt.
say item1 hat 3 Eigenschaften A, B und C.
Hash (A) = 123, Hash (B) = 345, Hash (C) = 456
multiplizieren Sie das dann mit der Reihenfolge der Erscheinung, vorausgesetzt, wir haben eine bekannte Anzahl von Eigenschaften:
(Hash (A) * 1.000,00) + (Hash (B) * 1.000) + (Hash (C) * 1) = Someval
Größe des Multiplikators kann optimiert werden, um Ihren Datensatz widerzuspiegeln. Sie müssen die Hash-Funktion identifizieren. Soundex vielleicht?
Das Problem ist jetzt auf eine Frage der Eindeutigkeit aufgrund von Hash-Kollisionen reduziert, aber wir können uns ziemlich sicher sein über Eigenschaften, die nicht übereinstimmen.
Außerdem hätte dies den Vorteil, dass relativ leicht überprüft werden kann, ob eine Eigenschaft in einem anderen Element in anderer Reihenfolge auftritt, indem die Größe des Multiplikators verwendet wird, um den Hashwert aus der generierten Zahl zu extrahieren.
HTH.
edit: Beispiel zum Überprüfen von Übereinstimmungen
gegebenes Element1 (a b c) und Element 2 (a b c). Der berechnete Hash der Elemente wäre gleich. Dies ist ein Best-Case-Szenario. keine weiteren Berechnungen sind erforderlich.
gegebenes Element1 (a b c) und Element 2 (d e a). berechneter Hash von Elementen ist nicht gleich. Fahren Sie damit fort, Eigenschaftenhashes aufzubrechen ...
sagen Sie eine Hash-Tabelle für Eigenschaften a = 1, b = 2, c = 3, d = 4, e = 5 mit 10 ^ n für Multiplikator. berechneter Hash für Element1 ist 123 und Element2 ist 451, zerlege den berechneten Hash für jede Eigenschaft und vergleiche für alle Kombinationen von Eigenschaften eine für jedes Element1 (die zu Element1 (1 2 3) wird) und Element2 (das zu Element2 wird (4 5 1 )). Dann berechne die Punktzahl.
Eine andere Betrachtungsweise wäre, die Eigenschaften einzeln zu vergleichen, außer dass Sie diesmal mit Zahlen anstelle der tatsächlichen Zeichenfolgenwerte spielen
Sie können aus verschiedenen Algorithmen zur Sequenzausrichtung Smith-Waterman . Tatsächlich scheint das, wonach Sie suchen, eine Beschreibung der Sequenzausrichtung zu sein. Ich bin jedoch unsicher, ob dies auch als SQL-Abfrage möglich ist.