Structure de données optimale pour un dictionnaire spécial

Question

Quelle structure de données est la meilleure en termes de complexité de calcul pour implémenter un dictionnaire d'éléments (key,val), qui doit supporter sólo les commandes suivantes :

1. Insert(key) - ajoute un élément (key,val) avec val=1
2. Increment(key) - incrémente la valeur de l'existant (key,val)
3. Find(key) - renvoie un val de (key,val)
4. Select(part_of_key) - retourne une liste de tous les éléments (key,val) si strstr(key,part_of_key)!=NULL sous la forme d'un nouveau dictionnaire du même type (sans allouer de nouvelle mémoire si possible) ; par exemple, si le dictionnaire est {(rouge,3), (bleu,4), (vert,1)}, alors Select(re)={(rouge,3), (vert,1)}.
5. Max(i) - renvoie un élément qui a la i-ième valeur maximale parmi tous les éléments ; par exemple, si le dictionnaire est {(rouge,3), (bleu,4), (vert,1)}, alors Max(1)=bleu, Max(2)=rouge, Max(3)=vert

Les clés sont des chaînes de caractères et les valeurs sont des nombres entiers positifs. Le nombre d'éléments du dictionnaire devrait être très important.

Je pense qu'il doit s'agir d'une synthèse de deux structures de données différentes. Mais est-ce que ça devrait être une table de hachage + un arbre binaire ou un tableau trié + un tableau trié ou autre chose ?

Answer 1

Une combinaison d'arbre équilibré (tel que l'arbre rouge-noir) et d'arbre de suffixes (ou tableau de suffixes).

• Arbre équilibré : opération 1, 2 (implémentée comme suppression + insertion), 3 et 5.
• Arbre des suffixes : opération 4.

NOTE : La table de hachage ne pourra pas supporter efficacement l'opération 5.

Je pense que vous aurez du mal à mettre en œuvre l'arbre des suffixes. Vous pourriez éventuellement utiliser L'implémentation C++ de l'algorithme d'Ukkonen par Mark Nelson Mais elle a des fuites de mémoire et est essentiellement un singleton, donc vous devrez la nettoyer avant qu'elle ne soit prête à être utilisée en production. Même après l'avoir corrigé, vous devrez l'ajuster pour qu'il fonctionne avec votre "autre" structure de données (qui est un arbre équilibré dans ma proposition) au lieu d'une grande chaîne simple.

Si vous effectuez l'opération 1 plus fréquemment que l'opération 4 et/ou si vous pouvez vivre avec l'opération 4 linéaire, je vous recommande de ne pas vous compliquer la vie avec l'arbre des suffixes et de simplement parcourir votre structure de données linéairement.

Answer 2

Pour les trois premières opérations, une table de hachage peut être une bonne idée.

Pour la 4ème opération (sélection d'une partie de la clé), vous devrez peut-être écrire la fonction de hachage différemment. Oui, la fonction de hachage qui a été utilisée pour trouver/calculer la valeur de hachage à partir de la clé donnée. Comme vous souhaitez prendre en charge la correspondance partielle et que votre clé est une chaîne, vous pouvez utiliser Suffix-tree ou trie.

Pour la cinquième opération (ith max élément), vous pouvez vouloir gérer un tas ou une liste de liens triés (ou une liste de sauts) qui interagit avec une table de hachage.

Vous devrez également voir différents cas d'utilisation et trouver quelle opération doit être optimisée. Par exemple : Si vous avez beaucoup de requêtes sur l'opération part_of_key, vous devriez utiliser une structure de type Suffix-tree/LC-trie et cela donnera de bons résultats. Cependant, votre opération de recherche ne sera peut-être pas rapide car elle prendra O(logN) au lieu d'une recherche constante.

En résumé, vous devez intégrer une table de hachage, un tas et un arbre de suffixes pour réaliser toutes les opérations.

Answer 3

Bien que la réponse exacte dépende de la fréquence de vos opérations, votre liste d'options devrait inclure un système de contrôle de la qualité. tableau de suffixes

Answer 4

Je pense qu'un tableau avec plusieurs raccourcis serait le mieux.

1-3 sont déjà pris en charge par un trie le plus rapidement possible (longueur de la clé).

Pour 4, j'ajouterais une table supplémentaire de 256 éléments à tous les nœuds de triage qui peuvent être saisis à partir de ce caractère. De cette façon, je peux effectuer une recherche rapide des parties de la chaîne, sans jamais construire ou stocker explicitement les suffixes comme dans un arbre de suffixes.

Pour 5, j'ajouterais une liste liée sur les feuilles, qui est mise à jour et triée lorsque des données sont insérées. Vous auriez peut-être besoin d'une autre référence à la tête de la liste et des backlinks dans le trie pour trouver la bonne valeur et obtenir la clé.

La complexité mémoire ne change pas par rapport au trie avec ces ajouts, puisqu'elle est limitée par le nombre de nœuds du trie. Cependant, le temps que prennent les insertions peut changer à cause du tri inefficace de la liste liée.

La structure finale devrait probablement être appelée un hash-leaf-trie. Mais je ne voudrais pas avoir à mettre en œuvre une telle bête.

Answer 5

Je pense qu'une base de données efficace sera une base de données modifiée. essai avec des liens bidirectionnels [ils peuvent aller des feuilles à la racine et reconstruire le mot], et chaque nœud terminal aura un champ "valeur" supplémentaire.
Vous aurez également besoin d'une carte multiple [c'est-à-dire une carte dans laquelle chaque valeur est un ensemble d'adresses].
Les clés seront disposées en forme d'arbre, et l'ensemble des valeurs sera basé sur le hachage. [En jave, cela devrait être quelque chose comme TreeMap<Integer,HashSet<Node>> ]

Pseudo-code : [enfin, très pseudo... il montre juste les idées générales pour chaque opération].

Insert(key):
1. Insert a word into the trie
2. add the value `1` to the terminating node.
3. add the terminating field to the multimap [i.e. map.add(1,terminating_node_address)]
Increment(key):
1. read the word in the trie, and store the value from the terminating node as temp.
2. delete the entree (temp,terminating_node_address) from the multimap.
3. insert the entree (temp+1,terminating_node_address) to the multimap.
4. increase the value of the terminating node's address by 1.
Find(key):
1. find the terminating node for the key in the trie, return its value.
Select(part_of_key):
1. go to the last node you can reach with part_of_key.
2. from this node: do BFS and retrieve all possible words [store them in an empty set you will later return].
Max(i):
1. find the i'th biggest element key in the multimap.
2. choose an arbitrary address, and return get the relevant terminating word node.
3. build the string by following the uplinks to the root, and return it.

les complexités :
let n soit le nombre de chaînes de caractères, k soit la valeur maximale, et S la longueur d'une chaîne de caractères.
Insérer : O(S) [l'insertion de trie est O(S)]. Le plus petit élément (1) de la carte peut être mis en cache, et peut donc être accessible en O(1).
Incrément : O(S+logk) : trouver la chaîne de caractères dans un trie est O(S), trouver la clé pertinente est O(logk), supprimer un élément d'un ensemble de hachage est O(1), trouver l'élément suivant dans l'arbre est également O(logk) [peut être O(1) en fait, pour un liste d'exclusion carte basée], et l'insertion d'une valeur est O(1). Notez qu'en liant le nœud à la clé pertinente dans la carte, la complexité de l'opération est de O(1). peut même être amélioré à O(S) puisque aucune recherche n'est réellement nécessaire.
Trouver : O(S) : il suffit de trouver dans la trie et de retourner la valeur.
Sélectionnez : O(S*n) Dans le pire des cas, vous devez récupérer tous les éléments, ce qui vous oblige à itérer la trie entière afin de trouver tous les mots.
Max : O(logk+S) : trouver une clé dans une carte triée, reconstituer le mot.

EDIT : Notez qu'ici, j'ai supposé que pour find(i) vous voulez le i'th distinct l'élément le plus important. Si ce n'est pas le cas, vous devrez modifier un peu l'ensemble et utiliser une multimap qui permet de dupliquer les clés [au lieu d'un ensemble comme valeur]. Cela rendra toutes les opérations basées sur l'arbre O(logn) au lieu de O(logk), toujours efficace à mon avis...