algorithme d'indexation de contacts

**tasnim86** · 21/02/2011, 16h27

bonsoir,

j'ai une BD qui contient une liste de contacts que je veux charger en mémoire pour la trier et y faire des traitements d'insertion, recherche (avec partial matching string) et suppression tout en la maintenant triée par ordre alphabétique
lors de ma recherche j'ai trouvé un certains nombre d'algo tel que HacheTable, Trie, PATRICIA, Judy,Ternary search tree...
J'aimerais bien que vous m'aider à choisir le bon algorithme en terme de complexité, temps de réponse, charge mémoire et s'il y en a d'autre criètes de choix ils seront les bienvenus!

**pseudocode** · 22/02/2011, 10h57

Il faudrait en savoir un peu plus pour définir une structure de données optimale.

Pour maintenir un structure triée, les structures de liste chainées sont très pratiques. Pour avoir un accès direct aux éléments, une hashtable est ce qu'il y a de mieux. On peut combiner les deux, soit en favorisant les accès directs(SortedSet/SortedMap, B+Tree, ...).

Pour les recherches partielles, la table de suffixes est très pratique.

**Graffito** · 23/02/2011, 00h52

Si le nombre de contacts est inférieur à quelques milliers, aucun problème de perfomance en perspective même avec les techniques les moins élaborées (tant qu'on n'enchaîne pas plusieurs centaines de modifications chaque seconde).

**tasnim86** · 23/02/2011, 09h43

en fait je m'explique encore plus,
mon algo doit être à la fois très performant et permettre la recherche des noms de contact (qui doivent être à leur tour stockés dans une structure de données optimisée) ayant un prefixe commun .
exemple: lorsque je tape "j" il doit me renvoier les noms qui commence par "j" comme "jean", "jannette",...

**pseudocode** · 23/02/2011, 11h25

Envoyé par tasnim86

en fait je m'explique encore plus,
mon algo doit être à la fois très performant et permettre la recherche des noms de contact (qui doivent être à leur tour stockés dans une structure de données optimisée) ayant un prefixe commun .
exemple: lorsque je tape "j" il doit me renvoier les noms qui commence par "j" comme "jean", "jannette",...

Si c'est juste une liste indexée est suffisante :
- Une liste chainée contenant les contacts dans l'ordre alphabétique.
- Un index des préfixes pointant vers le premier contact possible dans la liste chainée.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
Index1  Index2    Liste
---------------------------
                  ...
I ----> Ir -----> Irène
                  Irina
J ----> Ja -----> Jacques
                  Jannette
                  Jasmine
        Je -----> Jean
                  Jennifer
K ----> Ka -----> Kael
                  Karim
        Ke -----> Kerwan
                  Kevin
                  ...

**tasnim86** · 23/02/2011, 11h37

Envoyé par pseudocode

- Un index des préfixes pointant vers le premier contact possible dans la liste chainée.

merci mais c'est quoi la structure de données de l'index?
et puis combien d'index dans ce cas?

**pseudocode** · 23/02/2011, 12h06

Envoyé par tasnim86

merci mais c'est quoi la structure de données de l'index?

Le plus naturel semble être un arbre des préfixes possibles, ou chaque noeud pointe vers le premier contact de la liste. Si en plus tu maintiens l'ordre lexicographique pour chaque niveau (frère précédant/suivant), ca permet d'optimiser le parcours final de la liste de contact

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
     ______________
    |      |       |
    I      J       K
    |      |       |
    |     _|_     _|_
    |    |   |   |   |
    Ir   Ja  Je  Ka  Ke

et puis combien d'index dans ce cas?

Tu peux faire autant de niveau de profondeur que tu veux pour chaque branche. Le mieux étant de créer un nouveau niveau s'il y a trop de contacts pour le préfixe.

**tasnim86** · 23/02/2011, 12h15

une liste chainée pour les contacts et un arbre pour les index, ça ne consomme pas trop de mémoire?

y a pas une structure qui combine les deux ?

**pseudocode** · 23/02/2011, 12h19

Envoyé par tasnim86

une liste chainée pour les contacts et un arbre pour les index, ça ne consomme pas trop de mémoire?

La liste chainée, c'est uniquement pour optimiser les insertions/suppressions. Si ces opérations sont marginales, un tableau (ou plusieurs tableaux) est suffisant.

Un arbre de préfixes, ca ne coute pas très cher, meme si tu le fais sur 3 ou 4 niveaux.

y a pas une structure qui combine les deux ?

Le B+Tree

**tasnim86** · 23/02/2011, 13h23

Envoyé par pseudocode

Un arbre de préfixes, ca ne coute pas très cher, meme si tu le fais sur 3 ou 4 niveaux.
]

et si c'est pour 1000 contacts?

**pseudocode** · 23/02/2011, 14h05

Envoyé par tasnim86

et si c'est pour 1000 contacts?

??

Bah pour 1000 contacts une simple liste triée avec un index pour la 1ere lettre c'est largement suffisant. Ca fait en moyenne 40 contacts par lettre, une broutille.

**tasnim86** · 23/02/2011, 14h30

Envoyé par pseudocode

Bah pour 1000 contacts une simple liste triée avec un index pour la 1ere lettre c'est largement suffisant. Ca fait en moyenne 40 contacts par lettre, une broutille.

mais là, comme si tu considére que le prefixe ne peut être que la 1ère lettre du nom donc seulement le 1er caractère

**pseudocode** · 23/02/2011, 15h34

Envoyé par tasnim86

mais là, comme si tu considére que le prefixe ne peut être que la 1ère lettre du nom donc seulement le 1er caractère

L'index te donne juste le pointeur de début et le pointeur de fin de la zone de recherche (= tous les contacts qui commencent par la lettre indiquée).

A chaque fois que tu ajoutes une lettre, il faut avancer le le pointeur de début pour réduire la zone de recherche, en comparant le préfixe du contact avec le préfixe que tu as commencé à taper. C'est assez rapide car tu as peu de contacts à gérer.