Effiziente Kartendatenstruktur zur Unterstützung der ungefähren Suche

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.

$n^{O(\sqrt{d})}$$O(d)$$n^{O(d^\epsilon)}$$3^{1/\epsilon}$$n$$d$$\ell_1$$\ell_1$

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 Regimen$\ell_1$

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.

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^\alpha)$$0 < \alpha < 1$$O(n^2)$$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.