Il n'y a pas si longtemps, j'avais besoin d'implémenter une fonctionnalité qui avait déjà été implémentée par d'autres personnes et plus d'une fois, mais qui ne convenait pas à certaines caractéristiques. Dans ce cas, une sorte de structure de données était requise avec la possibilité de rechercher par une clé de chaîne ou plusieurs caractères initiaux de la clé. La clé est une chaîne de lettres latines dans tous les cas, des espaces et des chiffres.
D'autres implémentations ne convenaient pas, tout d'abord, à la mémoire consommée. Et en tout cas, une autre implémentation de l'arbre des préfixes ne sera pas superflue.
L'idée a probablement été inspirée par
cet article , car il a été décidé d'utiliser l'index bitmap pour indexer les liens vers les nœuds suivants dans le nœud.
Évidemment, le nombre de liens dans un nœud ne peut pas dépasser 63 (10 chiffres, 26 lettres dans chaque cas, plus un espace). Par conséquent, pour un index bitmap, un nombre 64 bits est utilisé à chaque nœud. Le bit défini dans n'importe quelle position signifie la présence du symbole et du nœud (sous-arbre) correspondants.
La distribution dans l'index bitmap est la suivante: les nombres de 0 à 9 occupent de 0 à 9 bits, les lettres az de 10 à 35 bits, les lettres AZ de 36 à 62 bits et un espace occupe 63 bits. Pour obtenir le numéro de bit, le code de caractère ASCII est simplement utilisé, réduit d'un certain nombre. Pour chaque plage de caractères, le nombre est différent: pour les chiffres 48 (la plage de chiffres dans les codes ASCII commence par 48), pour les lettres az 87 (la plage de lettres az commence par moins 10 bits déjà occupés par 10 chiffres) et ainsi de suite.
Le tableau correspondant est présenté ci-dessous.
Le nœud est représenté par le code ci-dessous:
type Trie struct { rw sync.RWMutex characters uint64 subTries []*Trie data interface{} }
Ainsi, chaque nœud stocke l'index bitmap des caractères suivants, une tranche avec des liens vers des sous-arbres et les données elles-mêmes. Je parlerai brièvement des mécanismes de recherche, d'insertion et de suppression.
Lors de la saisie de l'entrée, la clé traverse symboliquement l'arborescence, en partant du nœud racine. Pour chaque caractère de son code ASCII, le nombre de bits est calculé et, sur sa base, l'indice est calculé dans la tranche de liens (sous-essais) vers les sous-arbres. La valeur d'index est le nombre de bits avant le bit souhaité. Par exemple, nous avons un tel indice: 00 ... 101. Cela signifie que dans l'index bitmap, il y a des nombres 0 et 2. Ensuite, l'index pour le numéro 0 sera zéro, et pour le nombre 2, il sera 1, c'est-à-dire que les sous-essais stockeront 2 liens vers les sous-arbres: sous-essais [0] et sous-essais [1] .
Le code pour obtenir le numéro de bit du caractère:
func calcBitNum(char rune) (uint64, bool) {
Le code pour obtenir l'index du nœud pour le caractère:
func (trie *Trie) getSubTreeIndex(bitNum uint64) int { shifted := trie.characters << (64 - bitNum) return bits.OnesCount64(shifted) }
Le code pour obtenir le nœud pour le caractère donné:
func (trie *Trie) getSubTrie(char rune) (uint64, int, *Trie) { bitNum, _ := calcBitNum(char) subTrieId := trie.getSubTreeIndex(bitNum)
Insérer
Un arbre est parcouru pour insérer un élément. Si un caractère (et donc tous les suivants) est manquant, il est inséré dans l'index bitmap. Un sous-arbre est créé, le lien vers lequel est inséré à la bonne place des sous-essais de tranche (la bonne place est déterminée par le nombre de bits à celui souhaité). Lorsqu'ils ont atteint le dernier caractère de la clé, les données sont insérées dans le dernier sous-arbre.
Chercher
Pour effectuer une recherche, la clé "court" symboliquement dans l'arborescence. Dès qu'il est terminé, le résultat est renvoyé. S'il n'y a pas de données pour la clé, mais qu'il existe d'autres sous-arbres, les résultats sont sélectionnés parmi tous les sous-arbres suivants qui contiennent des données. La limite du nombre de données renvoyées peut être définie. Ainsi, il est possible de rechercher un seul nœud par la coïncidence de la clé entière, ou un ensemble de nœuds par la coïncidence de plusieurs caractères initiaux.
Effacer
La procédure de suppression s'est avérée plus compliquée (comme prévu) que les autres. Pour supprimer une clé, une arborescence est parcourue, au cours de laquelle les nœuds qui n'ont pas de données sont enregistrés dans une tranche distincte. Si un nœud contenant des données est trouvé, la tranche est remise à zéro et le passage à travers l'arborescence se poursuit. Autrement dit, la tranche de nœuds à supprimer doit contenir une séquence de nœuds qui ne contiennent pas de données. Si à la fin la tranche n'est pas vide, alors elle va dans l'ordre inverse et les bits correspondants sont supprimés de l'index bitmap et les nœuds sont supprimés.
Résumé
Le résultat est un arbre de préfixes qui est supérieur aux autres homologues en termes de vitesse et de consommation de mémoire (en moyenne, 30% de moins en mémoire et beaucoup plus rapide). De plus, je n'étais pas trop paresseux pour rendre possible des opérations multithread avec un arbre, ce qui augmente considérablement la productivité, en particulier dans les opérations de recherche. Bien sûr, la solution est assez spécialisée (limitation sous forme de caractères latins, de chiffres et d'un espace comme composants clés).
En fonction de l'objectif de l'arborescence des préfixes, cette solution peut être utilisée pour créer un dictionnaire, un index de recherche.
Je n'ai pas cité les codes d'insertion, de recherche et de suppression, afin de ne pas encombrer l'article, en plus, le code source est disponible
sur le github .