Structure de données cartographiques efficace prenant en charge la recherche approximative

Je recherche une structure de données qui prend en charge des recherches approximatives efficaces de clés (par exemple, la distance de Levenshtein pour les chaînes), renvoyant la correspondance la plus proche possible pour la clé d'entrée. La structure de données la mieux adaptée que j'ai trouvée jusqu'à présent est celle des arbres de Burkhard-Keller , mais je me demandais s'il existe d'autres structures de données / meilleures à cet effet.

Edit: Quelques détails supplémentaires sur mon cas spécifique:

• Les cordes ont généralement une différence de Levenshtein assez importante.
• Les chaînes ont une longueur maximale d'environ 20-30 caractères, avec une moyenne plus proche de 10-12.
• Je suis plus intéressé par la recherche efficace que par l'insertion car je vais créer un ensemble de données principalement statiques que je souhaite interroger efficacement.

Ce que vous recherchez est une "recherche approximative du voisin proche" (ANNS) dans la distance Levenshtein / edit. D'un point de vue théorique, la distance d'édition s'est jusqu'à présent révélée relativement difficile pour les recherches auprès de voisins proches, afaik. Pourtant, il y a beaucoup de résultats, voir les références dans cet article Ostrovsky et Rabani . Si vous êtes prêt à envisager d'autres mesures de distance pour lesquelles il existe des solutions plus simples et meilleures, passez au paragraphe suivant. Pour ANNS dans la distance d'édition, il y a un résultat dû à Indyk , qui montre comment construire une structure de données de taille qui répond à toute requête dans le temps et rapporte une chaîne qui est au plus trois fois plus loin que la chaîne la plus proche de la chaîne de requête (cela se généralise à la tailleO(d)nO(dϵ)31/ϵndℓ1ℓ$n^{O(\sqrt{d})}$$O(d)$$n^{O(d^\epsilon)}$ et approximation ). Ici, est le nombre de chaînes et est la longueur maximale de toute chaîne. Le document Ostrovsky et Rabani que j'ai lié ci-dessus améliore ce résultat en mappant les chaînes aux vecteurs de sorte que la (une sorte de distance géométrique naturelle similaire à la distance euclidienne) entre les vecteurs se rapproche de la distance d'édition entre les chaînes correspondantes (c'est ce qu'on appelle une "intégration à faible distorsion"). Une fois cela fait, une structure de données ANNS pour peut être utilisée, et celles-ci s'avèrent plus efficaces (voir le paragraphe suivant).$3^{1/\epsilon}$$n$$d$$\ell_1$$\ell_1$

Si vous êtes prêt à considérer d'autres distances, le hachage sensible à la localité (LSH) fait un excellent travail. Le hachage sensible à la localisation est une technique mise au point par Indyk et Motwani pour résoudre le problème ANNS, où les points qui vivent dans un espace de grande dimension (lire de longs vecteurs, de longues chaînes, etc.) sont hachés en un petit nombre de compartiments afin que les points qui sont proches les uns des autres sont mappés dans le même bac avec une bonne probabilité et les points qui sont éloignés les uns des autres sont mappés sur des bacs différents, également avec une bonne probabilité. Il y a un excellent article d'enquête très accessible par Indyk et Andoni dans CACM . Cette technique est simple et rapide, et a un faible encombrement; il y a aussi du code (je pense que l'article renvoie au code). Cela fonctionne bien pour des choses comme la distance de Hamming (et dans certains régimes$\ell_1$ distance) et la distance euclidienne, la distance cosinus. En outre, Muthu et Sahinalp conçoivent des schémas LSH pour une généralisation très naturelle de la distance d'édition, la distance d'édition de bloc (où certaines opérations d'édition peuvent fonctionner sur un bloc de symboles).

Ce type de question convient parfaitement à cstheory.SE . Il y a là une question connexe , mais elle semble demander un voisin exact.

Les structures de données qui vous intéressent sont des arbres métriques. Autrement dit, ils prennent en charge des recherches efficaces dans les espaces métriques. Un espace métrique est formé par un ensemble d'objets et une fonction de distance définie parmi eux satisfaisant l'inégalité du triangle. Le but est alors, étant donné un ensemble d'objets et un élément de requête, de récupérer ces objets suffisamment près de la requête.

Étant donné que les problèmes de recherche sont littéralement partout en informatique, il existe une énorme quantité d'arbres métriques différents. Cependant, ils peuvent être divisés au moins en deux groupes: basés sur des pivots et basés sur des clusters (et il y a sûrement aussi des hybrides). Une bonne enquête est E. Chavez et al., Searching in Metric Spaces, 2001 . Voir par exemple le Chapitre 5: Solutions actuelles aux espaces métriques, page 283.

Dans le tableau 1, Chavez et al. considérons 16 arbres métriques différents. Ils présentent la complexité de l'espace, la complexité de la construction, la complexité de la requête revendiquée et le temps de requête CPU supplémentaire pour chacun (si connu). Si vous ne vous souciez pas trop de la complexité de la construction, la complexité de la requête pour l'arbre BK est , où fonction de la plage de recherche et de la structure de l'espace . Ou si vous n'avez pas un grand nombre d'éléments, jetez un œil à AESA (approximation de l'élimination de l'algorithme de recherche). Il est inacceptablement lent à construire et à stocker des espaces énormes ( temps et espace), mais il a été démontré expérimentalement qu'il avait le temps de requête.0 < α < 1 O ( n 2 ) O ( 1 $O(n^\alpha)$$0 < \alpha < 1$$O(n^2)$$O(1)$

Chavez et al. donne également un bon aperçu des autres arbres, et naturellement plus de références si quelqu'un en particulier suscite votre intérêt. En pratique, les performances de différents arbres sont souvent évaluées expérimentalement. Je pense que cela dépend beaucoup de la structure de l'espace. Par conséquent, il est difficile de dire quel arbre en particulier serait le plus efficace dans votre cas. Néanmoins, je pense que c'est une bonne idée d'aller d'abord avec le plus simple. Si les arbres BK sont les plus faciles à construire, essayez-les d'abord. S'ils ne répondent pas à vos besoins, investissez du temps (et peut-être du temps de programmation) pour rassembler plus de faits sur votre espace qui pourraient vous aider à prendre des décisions plus éclairées.