Sorry für schlechtes Englisch: (
Angenommen, ich kann die Daten von Rezepten und Zutaten in irgendeiner Weise vorläufig organisieren.
Wie kann ich effektiv Suche von Rezepten durch Benutzer bereitgestellten Zutaten, vorzugsweise sortiert nach max Match - so, erste gehende Rezepte, die maximal bereitgestellten ingridients und enthalten keine anderen ingrs, nach ihnen Rezepte, die weniger von bereitgestellten gesetzt und still keine anderen Ingrs, nach ihnen Rezepte mit minimalen zusätzlichen Anforderungen und so weiter?
Alles, worüber ich nachdenken kann, ist die Darstellung von Rezeptur-Ingredienzien wie Bitmasken, und die erforderliche Bitmaske mit allen Rezepten zu vergleichen, aber es ist offensichtlich ein schlechter Weg.
Und verwandte Dinge wie Levenstein Entfernung ich sehe nicht, wie man hier verwendet.
Ich glaube, es sollte eine ganz normale Aufgabe sein ...
Es hört sich an, als ob Sie über Sets sprechen - "verfügbare Zutaten" ist ein Set, und Sie möchten alle Rezepte finden, deren Zutaten eine Teilmenge davon bilden, geordnet nach Größe. Sets werden effizient als ausgeglichene Bäume oder Hashtables implementiert.
Es wird ein bisschen komplizierter, wenn Sie verschiedene Mengen von Zutaten ansprechen möchten.
Bearbeiten: Wenn Ihre Rezeptdaten in einer SQL-Datenbank gespeichert sind, sollte es eigentlich möglich sein, das Ganze effizient als SQL-Abfrage auszuführen (die interne Tabellen und Bäume verwenden wird). Aber es wird eine ziemlich komplexe Abfrage sein; Fragen Sie besser jemanden, der besser in SQL ist als ich (und natürlich ist Ihre tatsächliche Tabellenstruktur notwendig).
Eigentlich würde ich ein Werkzeug wie Lucene benutzen, da es schon mehr oder weniger weiß, was Sie brauchen. Ihre Zutaten wären Schlüsselwörter im Lucene-Index und die Rezepte wären die Dokumente. Sie könnten dann gegen den Lucene-Index suchen und es würde Ihnen alle passenden Rezepte geben und Ihnen sogar Vertrauensniveau sagen können.
Lucene ist Open Source mit Implementierungen für viele Sprachen einschließlich .NET, Java, PHP und vielen anderen. Weitere Informationen finden Sie unter . Es gibt einen Link auf dieser Seite für alle verwandten Projekte.
Nur für die Indizierung - ich mache ein Benchmarking, und der erste Ansatz, den ich getestet habe - ist die PostgreSQL-Realisierung, die Unterabfragen und den Intarray-Typ verwendet.
Also, ich habe eine traditionelle normalisierte Datenbank mit Tabellen
Rezepte (id, name, descr), pk (id) und ingridients (id, name , descr), pk (id)
r2i (rezept_id, ingridient_id), unique (rezept_id, ingridient_id) (scheint, dass ich diesen Index nicht brauche, ist er gleich der ganzen Tabelle)
name und descr Spalten gefüllt mit etwas Müll, nur um Tische größer zu machen ;-) Insgesamt füllte ich diese Tabellen mit 200 Zutaten, 5000 Rezepte und jedes Rezept hat 3 bis 10 Zutaten, insgesamt etwa 35.000 Zeilen in R2i.
Angenommen, ich möchte nach Rezepten für meine Zutat suchen 129,99,56,180
Die Abfrage sieht folgendermaßen aus:
Abfrage kostet etwa 7k (hängt von der Menge, die Sie suchen), aber auf meinem Windows-Test-Notebook-Maschine (c2duo, 2GB RAM) läuft es sehr schnell - sofort für das menschliche Auge:)
Es gibt ein Dokument zum Intarray-Typ.
Testen noch nicht abgeschlossen, ich habe zwei weitere Lösungen zu testen, + erhalten Sie einige Zahlen über die Geschwindigkeit.
Tags und Links algorithm design-patterns design