cerhu > comp.* > comp.algorithmes

Une Bévue (15/06/2010, 17h38)
voila j'essaie de construire un arbre de thread (enfilade) sur usenet.

ça se présente comme ça :

le post initial n'a pas de référence, c'est le noeud source.
ensuite chaque noeud est repéré par un "message_id" y compris le noued
source.

tous les messages d'une même enfilade ont un champs "références" qui
donne la liste des "message_id" entre lui-même et le post-souce compris.

par exemple après le post initial, les posts qui y répondent ont un seul
"message_id" correspondant au "message_id" du post-source.

les posts qui répondent à la première réponse ont deux "message_id" dans
leur champs références soit le message_id de leur prédécesseur et le
post-source et ainsi de suite.

donc je cherche un algo pour représenter ça sous forme d'arbre.

pour l'instant je pense procéder ainsi :

- étape 1
je cherche tous les messages qui ont une seule référence :
=> ce sont les noeuds fils du noeud source

- étape 2
j'ai maintenant n-noeuds fils, ceux obtenus à l'étape précédente.
dans le champs références, les message_id sont ordonnés du noeud
source vers le "fils" le plus lointain.
je pourrais donc supprimer de ces noeuds la référence au noeud source
qui est déjà prise en compte et donc je suis ramené à l'étape 1 (ie
chercher les messages qui ne contiennent qu'une seul référence) mais à
appliquer avec comme noeuds sources auxuliaires les n-noeuds fils
précédemment trouvés.
bien sûr j'élimine de la liste des messages les fils (ainsi que la
source) précédemment trouvés

qu'en pensez-vous ?

j'imagine de ce genre de "truc" est répertorié qqpart ?
Pascal J. Bourguignon (16/06/2010, 00h23)
unbewusst.sein (Une Bévue) writes:

[..]
> chercher les messages qui ne contiennent qu'une seul référence) mais à
> appliquer avec comme noeuds sources auxuliaires les n-noeuds fils
> précédemment trouvés.
> bien sûr j'élimine de la liste des messages les fils (ainsi que la
> source) précédemment trouvés
>> qu'en pensez-vous ?

> j'imagine de ce genre de "truc" est répertorié qqpart ?


Il suffit d'appliquer l'algorithme de recherche dans un arbre, en le
modifiant pour créer les noeuds manquant.

(defstruct node
label
children)

(defun add-child-to-node (node child)
(push child (node-children node))
child)

(defun insert-node-at-path (tree path)
(unless (null path)
(let ((child (find (first path) (node-children tree) :key (function node-label))))
(if (null child)
(insert-node-at-path (add-child-to-node tree (make-node :label (first path)))
(rest path))
(insert-node-at-path child (rest path))))))

(let ((root (make-node :label 'root)))
(insert-node-at-path root '(a b c))
(insert-node-at-path root '(a b d))
(insert-node-at-path root '(e f g))
(insert-node-at-path root '(e h))
root)

--> #S(NODE :LABEL ROOT
:CHILDREN (#S(NODE :LABEL E
:CHILDREN (#S(NODE :LABEL H
:CHILDREN NIL)
#S(NODE :LABEL F
:CHILDREN (#S(NODE :LABEL G
:CHILDREN NIL)))))
#S(NODE :LABEL A
:CHILDREN (#S(NODE :LABEL B
:CHILDREN (#S(NODE :LABEL D
:CHILDREN NIL)
#S(NODE :LABEL C
:CHILDREN NIL)))))))

Comme les Message-ID sont donnés dans l'ordre inverse, il faudra bien
sur reverser la liste des Message-ID avant de la passer à
insert-node-at-path.
Olivier Miakinen (16/06/2010, 01h31)
Le 15/06/2010 17:38, Une Bévue a écrit :
> voila j'essaie de construire un arbre de thread (enfilade) sur usenet.
> ça se présente comme ça :
> le post initial n'a pas de référence, c'est le noeud source.
> ensuite chaque noeud est repéré par un "message_id" y compris le noued
> source.


Oui.

> tous les messages d'une même enfilade ont un champs "références" qui
> donne la liste des "message_id" entre lui-même et le post-souce compris.


Attention, ceci n'est pas garanti. C'est censé être vrai tant qu'il n'y
a pas trop de MID successifs, mais quand la liste devient trop longue
les agents sont autorisés à en supprimer, pourvu qu'ils conservent (si
je me rappelle bien) au moins le premier et les trois derniers. Et puis
un utilisateur peut toujours envoyer n'importe quoi.

> par exemple après le post initial, les posts qui y répondent ont un seul
> "message_id" correspondant au "message_id" du post-source.


Oui.

> les posts qui répondent à la première réponse ont deux "message_id" dans
> leur champs références soit le message_id de leur prédécesseur et le
> post-source


Oui, en principe.

> et ainsi de suite.


Non, pas forcément « ainsi de suite ».

> donc je cherche un algo pour représenter ça sous forme d'arbre.
> [...]


J'ai quelques idées qui m'ont traversé l'esprit, mais rien dont je sois
sûr que cela fonctionne au mieux -- surtout sans boucler en cas de
références circulaires.

De toute manière...

> j'imagine de ce genre de "truc" est répertorié qqpart ?


.... oui, je l'imagine aussi. Ne serait-ce que dans les sources de divers
nouvelleurs, y compris par exemple Thunderbird et SeaMonkey.
Une Bévue (16/06/2010, 05h57)
Olivier Miakinen <om+news> wrote:

> Attention, ceci n'est pas garanti. C'est censé être vrai tant qu'il n'y
> a pas trop de MID successifs, mais quand la liste devient trop longue
> les agents sont autorisés à en supprimer, pourvu qu'ils conservent (si
> je me rappelle bien) au moins le premier et les trois derniers. Et puis
> un utilisateur peut toujours envoyer n'importe quoi.


Ah merci beaucoup pour cette info Kapitale )))

donc je me baserai uniquement sur le prédécesseur, qui doit y être,
nécessairement, sinon le post deviendrait orphelin.

a dire vrai je m'étais posé la question tout seul dans mon coin : ça va
finir par devenir long se référencement...

il y a deja tellement de baratin inutile dans les headers...

>> Oui.
>> Oui, en principe.
>> Non, pas forcément « ainsi de suite ».
>> J'ai quelques idées qui m'ont traversé l'esprit, mais rien dont je sois

> sûr que cela fonctionne au mieux -- surtout sans boucler en cas de
> références circulaires.


euh là, j'ai un doute qu'il puisse y avoir une référence circulaire ?

> De toute manière...
> > j'imagine de ce genre de "truc" est répertorié qqpart ?

> ... oui, je l'imagine aussi. Ne serait-ce que dans les sources de divers
> nouvelleurs, y compris par exemple Thunderbird et SeaMonkey.


Pascal Bourguignon m'a donné une soluce à traduire/digérer...
Une Bévue (16/06/2010, 05h57)
Pascal J. Bourguignon <pjb> wrote:

> Il suffit d'appliquer l'algorithme de recherche dans un arbre, en le
> modifiant pour créer les noeuds manquant.
>> (defstruct node

> label
> children) <snip />


bon je vais prendre le temps de digérer ça.

> Comme les Message-ID sont donnés dans l'ordre inverse, il faudra bien
> sur reverser la liste des Message-ID avant de la passer à
> insert-node-at-path.


euh l'ordre inverse suppose une référence d'ordre. en tk le premier
message id correspond à root, le dernier au message précédent.

merci bien !
Yliur (16/06/2010, 06h03)
> > J'ai quelques idées qui m'ont traversé l'esprit, mais rien dont je
> > sois sûr que cela fonctionne au mieux -- surtout sans boucler en
> > cas de références circulaires.

> euh là, j'ai un doute qu'il puisse y avoir une référence circulaire ?


Des messages de quelqu'un de malintentionné ?
Yliur (16/06/2010, 06h05)
Le Tue, 15 Jun 2010 17:38:33 +0200
unbewusst.sein (Une Bévue) a écrit :

> voila j'essaie de construire un arbre de thread (enfilade) sur usenet.
> ça se présente comme ça :
> le post initial n'a pas de référence, c'est le noeud source.
> ensuite chaque noeud est repéré par un "message_id" y compris le noued
> source.


Attention, il se peut que tu n'aies pas le noeud source de l'enfilade.
Quand tu reçois des messages d'un serveur, il se peut que le premier
message du fil ne soit plus sur le serveur et que tu n'obtiennes que
les suivants.
Une Bévue (16/06/2010, 08h53)
Yliur <yliur> wrote:

> > euh là, j'ai un doute qu'il puisse y avoir une référence circulaire ?

> Des messages de quelqu'un de malintentionné ?


ah oui, je vois, on peut, en postant imposer un champs "references"
provoquant la circularité, mouais.

il faut que je réfléchisse mais je pense que mon algo est immune à ça,
il ne se base pas sur les réfrérences MAIS uniquement sur le
prédécesseur (dernière référence dans la liste).

seul moyen d'éviter tout pb quand, comme me l'a indiqué Olivier
Miakinen, le client (ou le serveur?) ne transmettent qu'une partie des
références.
Une Bévue (16/06/2010, 08h53)
Yliur <yliur> wrote:

> Attention, il se peut que tu n'aies pas le noeud source de l'enfilade.
> Quand tu reçois des messages d'un serveur, il se peut que le premier
> message du fil ne soit plus sur le serveur et que tu n'obtiennes que
> les suivants.


ah oui, et il y a parfois des trous, dans l'enfilade.

c'est pas important pour moi car je ne me réfère jamais au noeud source
mais simplement au prédécesseur.

mon noeud (pseudo-)"source" étant le noeud choisi par l'utilisateur,
donc il existe bien car le header a été téléchargé du serveur.

cas d'école :

supposons que le noeud source ait disparu et qu'à la suite de ce noeud
source il y ait deux noeuds fils, dans mon cas, pour obtenir tout ce
qu'il reste de l'enfilade sur le serveur, l'utilisateur devra choisir
les deux fils, s'il n'en choisi qu'un il n'aura que le sous-arbre
relatif à ce fils.

en fait tout dépend du nombre de headers téléchargés.

comme mon algo, enfin une maquette hein, me semble OK, je vais passer à
une maquette de mon UI, je fais ça en html5 et compte utiliser n'importe
quel navigateur (comaptble HTML5) pour la visualisation.

mais bon, pour l'instant je ne gère pas les trous, càd le cas où un post
a été annulé dans une enfilade, il faut que je me trouve qqpart une
enfilade avec au moins un trou...

)))
Pascal J. Bourguignon (16/06/2010, 10h42)
unbewusst.sein (Une Bévue) writes:

> Pascal J. Bourguignon <pjb> wrote:
> <snip />
> bon je vais prendre le temps de digérer ça.
>> euh l'ordre inverse suppose une référence d'ordre. en tk le premier

> message id correspond à root, le dernier au message précédent.


Oui, enfin je veux dire que dans mon algorithme, le chemin (path),
doit aller de la racie à la feuille.

(J'avais cru comprendre que les Message-ID étaient donnés dans l'ordre
inverse, je n'ai pas vérifié et j'au pu mal comprendre).
Pascal J. Bourguignon (16/06/2010, 10h47)
Olivier Miakinen <om+news> writes:

> Le 15/06/2010 17:38, Une Bévue a écrit :
> Oui.
>> Attention, ceci n'est pas garanti. C'est censé être vrai tant qu'il n'y

> a pas trop de MID successifs, mais quand la liste devient trop longue
> les agents sont autorisés à en supprimer, pourvu qu'ils conservent (si
> je me rappelle bien) au moins le premier et les trois derniers.


Ah ah! Ça expliquerait pourquoi parfois certaines branches sont
détachées du thread...

Dans ce cas, il faudrait effectivement modifier mon algorithme.

Au lieu de chercher seulement parmis les fils directe du noeud, il
faudrait chercher dans tout le sous-arbre, et avant d'ajouter un
nouveau noeud, il faudrait le rechercher dans tous les sous arbres
parents, pour éventuellement déplacer un sous arbre mal placé...

> Et puis
> un utilisateur peut toujours envoyer n'importe quoi.


> J'ai quelques idées qui m'ont traversé l'esprit, mais rien dont je sois
> sûr que cela fonctionne au mieux -- surtout sans boucler en cas de
> références circulaires.


Si on nous envoit n'importe quoi, il faut effectivement faire
attention à celà.
[..]
Une Bévue (16/06/2010, 10h50)
Pascal J. Bourguignon <pjb> wrote:

> > euh l'ordre inverse suppose une référence d'ordre. en tk le premier
> > message id correspond à root, le dernier au message précédent.

> Oui, enfin je veux dire que dans mon algorithme, le chemin (path),
> doit aller de la racie à la feuille.


ouais, c'est comme ça aussi pour les message id sauf que tout le path
n'est pas nécessairement présent.

je n'utilise donc que le prédécesseur (père du noeund courant).
tth (16/06/2010, 11h43)
Olivier Miakinen a raconté :

> ... oui, je l'imagine aussi. Ne serait-ce que dans les sources de divers
> nouvelleurs, y compris par exemple Thunderbird et SeaMonkey.


Si je me souviens bien, c'est assez clair dans Slrn.
Paul Gaborit (16/06/2010, 14h00)
À (at) Wed, 16 Jun 2010 10:47:53 +0200,
pjb (Pascal J. Bourguignon) écrivait (wrote):

> Olivier Miakinen <om+news> writes:
>> Attention, ceci n'est pas garanti. C'est censé être vrai tant qu'il n'y
>> a pas trop de MID successifs, mais quand la liste devient trop longue
>> les agents sont autorisés à en supprimer, pourvu qu'ils conservent (si
>> je me rappelle bien) au moins le premier et les trois derniers.

> Ah ah! Ça expliquerait pourquoi parfois certaines branches sont
> détachées du thread...


Ne pas oublier non plus qu'on ne reçoit pas tous les messages au même
moment ni dans le bonne ordre. On peut recevoir un message de réponse
*avant* le message de question correspondant.
Une Bévue (16/06/2010, 14h09)
Paul Gaborit <Paul.Gaborit> wrote:

> Ne pas oublier non plus qu'on ne reçoit pas tous les messages au même
> moment ni dans le bonne ordre. On peut recevoir un message de réponse
> *avant* le message de question correspondant.


ouais, je fais un sort sur la date des messages.

Discussions similaires
[LISTE DES VOTANTS] Remplacement de fr.usenet.logiciels (modere) par fr.comp.usenet.serveurs et fr.comp.usenet.lecteurs-de-news (non moderes)

[AAD 2] Remplacement de fr.usenet.logiciels (modere) par fr.comp.usenet.serveurs et fr.comp.usenet.lecteur-de-news (non moderes)

Lomé [fut Re: [AAD 2] Remplacement defr.usenet.logiciels (modere) par fr.comp.usenet.serveurs et fr.comp.usenet.lecteur-de-news (non moderes)]

Construire un arbre en css


Fuseau horaire GMT +2. Il est actuellement 06h27. | Privacy Policy