Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

algorithme de tri de messages

Posté par
maccormick
26-06-09 à 14:58

Bonjour à tous,
Après avoir passer quelques jours face à moi même à essayer de me dépatouiller avec mon problème, je pense qu'il est plus que temps de vous demander de l'aide : à l'aide ! Car c'est vraiment le forum sur lequel j'en trouve le plus, de l'aide !
Voici le contexte (je travaille avec une bdd mysql et JAVA) : j'ai une liste de message décrits par :
id_message
sujet_message
date_message
(et aussi d'autres propriétés mais pas très importantes)
Je dois pouvoir classer les messages dans des conversations, selon le sujet du message, ce qui est normal, mais aussi selon la date. Par exemple, deux messages qui ont le même sujet et qui sont séparés de moins de x jours (où x est donné en paramètre) feront partie de la même conversation. Si le nombre de jours qui les séparent est supérieur à x, ils seront placés dans 2 conversations différentes.
J'ai pensé à plusieurs choses, mais rien ne me satisfait. La chose la plus évoluée que j'ai pondue, c'est de ranger les messages dans 2 tableaux, comparer chaque ligne du premier tableau avec tous les éléments du second tableau et de faire (pardon pour l'énoncé algorithmique, ça fait longtemps que je n'ai pas pratiqué les conventions !) :
si tab1_intitulé_sujet_x == tab2_intitulé_sujet_x
   si tab1_date_sujet_x <= tab2_date_sujet_x + paramètre
     je range dans un tableau à 3 entrées les clés de tab1_sujet_x, tab2_sujet_x, numéro_conversation
  sinon je continue
sinon je continue
cela marche très bien mais comment ensuite, si je retombe sur sujet x plus loin dans tab2, je retrouve la conversation que j'ai déjà affectée à sujet_x ?

J'espère que mon énoncé est compréhensible, sinon n'hésitez pas à me poser des questions pour éclaircissements !
Merci d'avance à vous tous, je suis vraiment en galère et ma tête explose (et je suis assez nul en algo aussi !)
bon courage

Posté par
erio
re : algorithme de tri de messages 26-06-09 à 16:05

Bonjour

Ce que je ne comprends pas bien dans ta règle, c'est que si l'on imagine que trois messages sur le même sujet soient envoyés à 5 jours d'intervalle :
message 1 : jour 0
message 2 : jour 5
message 3 : jour 10
et que le nombre de jours limite soit, par exemple, 7. Le message 1 et 2 seront placés dans la même conversation, le message 2 et 3 dans la même, mais pas les messages 1 et 3 ???

L'idée qui me vient, mais peut-être est-ce que je déforme le problème, c'est de dire qu'une conversation est une suite de messages sur un même sujet qui s'enchaînent avec un délai inférieur à un paramètre donné. Donc deux messages seront dans la même conversation si l'on trouve une suite de messages sur le même sujet qui s'enchaîne l'un à l'autre dans un temps inférieur au délai maximal. Si un message intervient sur un sujet et que cela intervient trop tard par rapport au dernier message de ce sujet, le nouveau message arrivant lance une nouvelle conversation... C'est ce qui me paraît plus logique, et du coup ça donne un algorithme :

Pas besoin de dupliquer la table. Tu crée juste une nouvelle table de conversations. Avec les champs :
+ ID conversation
+ sujet de la conversation
+ date du dernier message
+ liste des id des messages dans la conversation
Pour remplir la table, il faut toujours la ranger avec les dates de conversation les plus récentes en premier (ordre anti-chronologique? est-ce que c'est possible avec le langage d'accès aux bases de données, je ne sais pas). Ensuite, après avoir classé ta table de messages par ordre chronologique cette fois, tu prend chaque message :

pour chaque message dans la table des message
  pour chaque conversation dans la table des conversation
    si la date du dernier message dans la conversation + délai maximal
    est supérieure à la date de mon message
      alors je crée une nouvelle conversation
      (en effet, si j'ai classé par ordre anti-chrono,
      tout ce qui viendra après ne sera pas bon non plus)
      fin du traitement du message
    sinon, si le sujet est le même
      je rajoute le sujet à la conversation
      je change la date du dernier message dans la conversation
      fin du traitement du message
  fin de la boucle sur les conversations
  (je n'ai pas trouvé de conversation récente sur le même sujet)
  je crée une nouvelle conversation
fin du traitement du message
  
En plus, je système peut tourner en temps réel...

Posté par
maccormick
re : algorithme de tri de messages 27-06-09 à 08:48

Salut,
Oui, tu as parfaitement raison ! (je m'étais mal exprimé!)
Là on est samedi, donc je ne suis pas au boulot, mais j'essaye dès lundi parce que ça a l'air de tourner nickel ton algo !!
Merci encore !!

Posté par
erio
re : algorithme de tri de messages 27-06-09 à 13:49

Avec plaisir

Posté par
maccormick
re : algorithme de tri de messages 07-07-09 à 09:30

Salut,
Merci à toi erio ! En fait la solution était très simple : classer ma requête par ordre alphabétique d'intitulé du sujet puis par date, et de tester à chaque fois le sujet courant avec le précédent, bref, une bonne vieille requête ORDER BY !!
Merci encore et à+

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !