Effiziente Kartendatenstruktur zur Unterstützung der ungefähren Suche

25

Ich suche nach einer Datenstruktur, die eine effiziente ungefähre Suche nach Schlüsseln unterstützt (z. B. Levenshtein-Abstand für Zeichenfolgen), wobei die bestmögliche Übereinstimmung für die Eingabetaste zurückgegeben wird. Die am besten geeignete Datenstruktur, die ich bisher gefunden habe, sind Burkhard-Keller-Bäume , aber ich habe mich gefragt, ob es für diesen Zweck andere / bessere Datenstrukturen gibt.

Bearbeiten: Einige weitere Details zu meinem konkreten Fall:

  • Saiten haben normalerweise einen ziemlich großen Levenshtein-Unterschied.
  • Saiten haben eine maximale Länge von ca. 20-30 Zeichen, wobei der Durchschnitt bei 10-12 liegt.
  • Ich bin mehr an einer effizienten Suche als an der Einfügung interessiert, da ich eine Reihe größtenteils statischer Daten erstellen werde, die ich effizient abfragen möchte.
merijn
quelle
Gibt es Bedingungen für die Eingabezeichenfolge und die Größe der Anzahl der Elemente in der Map? Wie effizient muss das Einfügen in die Karte sein?
edA-qa mort-ora-y
mrm, soweit ich das beurteilen kann, sehen bk-bäume noch einen ziemlich großen teil des gesamten baumes an. Aber das könnte auf meiner Seite eine vorzeitige Optimierung sein, denke ich?
Merijn
3
Eng verbunden mit dem Punkt, dass es sich fast um ein Duplikat handelt: Effiziente Datenstrukturen zum Erstellen einer schnellen Rechtschreibprüfung
Raphael

Antworten:

18

nO(d)O(d)nO(dϵ)31/ϵnd11

Wenn Sie bereit sind, andere Entfernungen in Betracht zu ziehen, leistet Locality Sensitive Hashing (LSH) hervorragende Arbeit. Locality Sensitive Hashing ist eine von Indyk und Motwani entwickelte Technik zur Lösung des ANNS-Problems, bei der Punkte, die in einem hochdimensionalen Raum leben (lange Vektoren, lange Strings usw. lesen), in eine kleine Anzahl von Buckets gehasht werden, sodass auf diese Punkte verwiesen wird nahe beieinander sind, werden mit hoher Wahrscheinlichkeit auf dasselbe Fach abgebildet, und Punkte, die weit voneinander entfernt sind, werden mit hoher Wahrscheinlichkeit auf verschiedene Fächer abgebildet. In CACM gibt es einen großartigen und sehr leicht zugänglichen Umfrageartikel von Indyk und Andoni . Diese Technik ist einfach und schnell und hat einen geringen Platzbedarf. Es gibt dort auch Code (ich denke, der Artikel verlinkt auf den Code). Es funktioniert gut für Dinge wie Hamming Entfernung (und in bestimmten Regimen1

Diese Art von Frage passt gut zu cstheory.SE . Es gibt dort eine verwandte Frage , aber sie scheint nach einem genauen nahen Nachbarn zu fragen.

Sasho Nikolov
quelle
12

Die Datenstrukturen, an denen Sie interessiert sind, sind metrische Bäume. Das heißt, sie unterstützen eine effiziente Suche in metrischen Räumen. Ein metrischer Raum wird durch eine Menge von Objekten und eine dazwischen definierte Abstandsfunktion gebildet, die die Dreieckungleichung erfüllt. Das Ziel besteht dann darin, anhand einer Reihe von Objekten und eines Abfrageelements diese Objekte abzurufen, die nahe genug an der Abfrage liegen.

Da Suchprobleme buchstäblich überall in der Informatik auftreten, gibt es eine Vielzahl unterschiedlicher metrischer Bäume. Sie können jedoch in mindestens zwei Gruppen unterteilt werden: Pivot-basiert und Cluster-basiert (und es gibt sicherlich auch Hybriden). Eine gute Umfrage ist E. Chavez et al., Searching in Metric Spaces, 2001 . Siehe z. B. Kapitel 5: Aktuelle Lösungen für metrische Bereiche, Seite 299.

O(nα)0<α<1O(n2)O(1)

Chavez et al. Geben Sie auch einen schönen Überblick über die anderen Bäume, und natürlich mehr Referenzen, wenn eine bestimmte Ihr Interesse weckt. In der Praxis wird die Leistung verschiedener Bäume häufig experimentell bewertet. Dies hängt meiner Meinung nach stark von der Raumstruktur ab. Daher ist es schwer zu sagen, welcher Baum in Ihrem Fall am effizientesten ist. Trotzdem halte ich es für eine gute Idee, zuerst mit dem Einfachsten zu beginnen. Wenn BK-Bäume am einfachsten zu bauen sind, probieren Sie sie zuerst aus. Wenn sie Ihren Anforderungen nicht entsprechen, investieren Sie Zeit (und möglicherweise Programmierzeit) in das Sammeln weiterer Fakten über Ihren Bereich, die Sie bei fundierteren Entscheidungen unterstützen können.

Juho
quelle