Wydajna struktura danych mapy obsługująca przybliżone wyszukiwanie

Szukam struktury danych, która obsługuje efektywne przybliżone wyszukiwanie kluczy (np. Odległość Levenshteina dla ciągów znaków), zwracając możliwie najbliższe dopasowanie dla klucza wejściowego. Najlepszą strukturą danych, jaką do tej pory znalazłem, są drzewa Burkhard-Keller , ale zastanawiałem się, czy istnieją inne / lepsze struktury danych do tego celu.

Edycja: Więcej szczegółów mojej konkretnej sprawy:

• Ciągi zwykle mają dość dużą różnicę Levenshteina.
• Ciągi mają maksymalną długość około 20-30 znaków, ze średnią bliższą 10-12.
• Bardziej interesuje mnie wydajne wyszukiwanie niż wstawianie, ponieważ będę budować zestaw głównie statycznych danych, które chcę wydajnie wyszukiwać.

To, czego szukasz, to „przybliżone wyszukiwanie w sąsiedztwie” (ANNS) w odległości Levenshtein / edycja. Z teoretycznego punktu widzenia odległość edycji okazała się dotychczas stosunkowo trudna przy wyszukiwaniu w sąsiedztwie, afaik. Istnieje jednak wiele wyników, zobacz odniesienia w tym artykule Ostrovsky i Rabani . Jeśli chcesz rozważyć alternatywne wskaźniki odległości, dla których istnieją prostsze i lepsze rozwiązania, przejdź do następnego akapitu. W przypadku ANNS w odległości edycji istnieje wynik należący do Indyka , który pokazuje, jak zbudować strukturę danych o rozmiarze która odpowiada na każde zapytanie w czasie i zgłasza ciąg co najwyżej trzy razy dalej niż ciąg najbliższy ciągu zapytania (powoduje to uogólnienie do rozmiaru$n^{O(\sqrt{d})}$$O(d)$$n^{O(d^\epsilon)}$ i przybliżenie ). Tutaj jest liczbą łańcuchów, a jest maksymalną długością dowolnego łańcucha. Połączony powyżej artykuł Ostrovsky i Rabani poprawia ten wynik, mapując ciągi znaków na wektory, dzięki czemu odległość (rodzaj naturalnej odległości geometrycznej podobnej do odległości euklidesowej) między wektorami jest zbliżona do odległości edycji między odpowiadającymi ciągami (nazywa się to „osadzanie przy niskich zniekształceniach”). Po wykonaniu tej czynności można zastosować strukturę danych ANNS dla , która okazuje się bardziej wydajna (patrz następny akapit).$3^{1/\epsilon}$$n$$d$$\ell_1$$\ell_1$

Jeśli chcesz wziąć pod uwagę inne odległości, to haszowanie wrażliwe na lokalizację (LSH) ma świetną robotę. Hashowanie wrażliwe na lokalizację to technika zapoczątkowana przez Indyk i Motwani do rozwiązania problemu ANNS, w której punkty żyjące w przestrzeni o dużych wymiarach (czytaj długie wektory, długie łańcuchy itp.) Są haszowane w niewielką liczbę segmentów, dzięki czemu punkty są blisko siebie są mapowane na ten sam pojemnik z dużym prawdopodobieństwem, a punkty, które są daleko od siebie, są mapowane na różne pojemniki, również z dużym prawdopodobieństwem. W CACM znajduje się świetny i bardzo dostępny artykuł ankietowy autorstwa Indyka i Andoni . Ta technika jest prosta i szybka oraz wymaga niewielkiej przestrzeni; tam też jest kod (myślę, że artykuł prowadzi do kodu). Działa dobrze dla rzeczy takich jak odległość Hamminga (i w niektórych reżimach$\ell_1$ odległość) i odległość euklidesowa, odległość cosinus. Ponadto, Muthu i Sahinalp projektują schematy LSH dla bardzo naturalnego uogólnienia odległości edycji, odległości edycji bloku (gdzie niektóre operacje edycji mogą działać na bloku symboli).

Tego rodzaju pytanie dobrze pasuje do cstheory.SE . Istnieje pokrewne pytanie , ale wydaje się, że prosi o dokładne sąsiedztwo.

Struktury danych, którymi jesteś zainteresowany, to drzewa metryczne. Oznacza to, że obsługują wydajne wyszukiwanie w przestrzeniach metrycznych. Przestrzeń metryczna jest tworzona przez zbiór obiektów i zdefiniowaną wśród nich funkcję odległości spełniającą nierówność trójkąta. Celem jest zatem, biorąc pod uwagę zestaw obiektów i element zapytania, odzyskanie tych obiektów wystarczająco blisko zapytania.

Ponieważ problemy z wyszukiwaniem występują dosłownie wszędzie w informatyce, istnieje ogromna liczba różnych drzewek metrycznych. Można je jednak podzielić co najmniej na dwie grupy: oparte na osiach i oparte na klastrowaniu (i na pewno są też hybrydy). Dobrą ankietą jest E. Chavez i in., Searching in Metric Spaces, 2001 . Patrz na przykład Rozdział 5: Aktualne rozwiązania w przestrzeniach metrycznych, strona 283.

$O(n^\alpha)$$0 < \alpha < 1$$O(n^2)$$O(1)$

Chavez i in. daj również ładny przegląd innych drzew i naturalnie więcej referencji, jeśli któreś z nich wzbudzi twoje zainteresowanie. W praktyce wydajność różnych drzew jest często oceniana eksperymentalnie. Myślę, że to zależy w dużej mierze od struktury przestrzeni. Dlatego trudno jest powiedzieć, które drzewo byłoby najbardziej wydajne w twoim przypadku. Niemniej jednak uważam, że warto najpierw wybrać najłatwiejszy. Jeśli drzewa BK są najłatwiejsze do zbudowania, wypróbuj je najpierw. Jeśli nie spełniają twoich wymagań, zainwestuj czas (i być może czas programowania) w zebranie większej ilości faktów na temat twojej przestrzeni, które mogłyby pomóc ci w podejmowaniu bardziej świadomych decyzji.