j'espère être sur le forum adéquat.. dans la négative, merci de ne pas me
taper et de m'indiquer le forum le plus adapté :-)
je souhaiterai développer pour mIRC (logiciel de t'chat sous windows) une
dll permettant d'analyser "à la volée" des phrases pour y détecter des
propos racistes, orduriers, ou des conotations sexuelles un peu trop
explicites.
je comptais faire plusieurs 'dictionnaires', et faire analyser la phrases en
fonction de chacun des dictionnaires selon un ordre de "gravité" des propos.
l'imagination et la bétise humaine étant sans limites, je ne connais pas par
avance le nombre de mots contenus dans chacun des dictionnaires (je table
cependant sur moins d'une centaine par dictionnaire sans grande certitude).
j'ai 3 problèmes :
1 - peu d'expérience en C++
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé
des "tables de hashage" (beaucoup de dictionnaires les utilisent à priori)
mais j'avoue ne pas en avoir saisie le mode de fonctionnnement (si quelqu'un
avait un exemple - très - simple) et donc sa mise en oeuvre.
3 - par rapport à la rapidité nécessaire pour cette application et le nombre
de mots "relativement" faible, est-ce la meilleure méthode de stockage et de
"parcours" ?
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Arnaud Meurgues
jmb wrote:
j'espère être sur le forum adéquat.. dans la négative, merci de ne pas me taper et de m'indiquer le forum le plus adapté :-)
fr.comp.algorithmes serait sans doute plus adapté, la question ne portant pas vraiment sur le langage C++.
j'ai 3 problèmes : 1 - peu d'expérience en C++
Normalement, ce problème là, avec la pratique, ça passe. :)
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé des "tables de hashage" (beaucoup de dictionnaires les utilisent à priori) mais j'avoue ne pas en avoir saisie le mode de fonctionnnement (si quelqu'un avait un exemple - très - simple) et donc sa mise en oeuvre. 3 - par rapport à la rapidité nécessaire pour cette application et le nombre de mots "relativement" faible, est-ce la meilleure méthode de stockage et de "parcours" ?
Une table de hachage n'est pas un mauvais choix. Son principe est le suivant : - on a un tableau de n éléments pour stocker m éléments (avec m plus petits que n) - On utilise une fonction de hachage qui associe à un objet à stocker une valeur. La fonction de hachage est en générale la partie la plus délicate dans l'algorithme. Mais il suffit d'utiliser des tables de hachages toute faites. - quand on veut stocker un objet (disons une chaîne de caractères), on le fait passer dans la fonction de hachage et la valeur obtenue donne l'index du tableau où il va être stocké.
De cette manière, rechercher si une chaîne est dans le tableau est très rapide : - on hache la chaîne (algorithme classiquement en o(t), t étant la longueur de la chaîne - on regarde à l'index t si la chaîne qui y est stockée est la même
Maintenant, il y a des problèmes induits par cette méthode : il n'y a pas de bijection entre les chaînes et les valeurs. Donc plusieurs chaînes différentes peuvent avoir la même valeur de hachage. C'est ce qu'on appelle une « collision ». Il existe plusieurs façons de les gérer. Mais c'est à cause de ces collisions que le tableau doit être sensiblement plus grand que le nombre d'éléments à stocker.
Mais si tu veux faire une recherche à la volée, il y a peut-être une autre structure qui pourrait être plus efficace : une structure d'arbre avec des noeuds correspondant aux lettres et des feuilles qui seraient les mots.
racine / a b / / r a o / / | b t l n b | | | | o a a b b u r r a a l b t l n e r i l a e s o n t n e e
Avec une telle structure, la recherche pourrait se faire au fur et à mesure de la frappe, sans attendre que le mot soit fini de taper.
Bon courage, Arnaud
jmb wrote:
j'espère être sur le forum adéquat.. dans la négative, merci de ne pas me
taper et de m'indiquer le forum le plus adapté :-)
fr.comp.algorithmes serait sans doute plus adapté, la question ne
portant pas vraiment sur le langage C++.
j'ai 3 problèmes :
1 - peu d'expérience en C++
Normalement, ce problème là, avec la pratique, ça passe. :)
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé
des "tables de hashage" (beaucoup de dictionnaires les utilisent à priori)
mais j'avoue ne pas en avoir saisie le mode de fonctionnnement (si quelqu'un
avait un exemple - très - simple) et donc sa mise en oeuvre.
3 - par rapport à la rapidité nécessaire pour cette application et le nombre
de mots "relativement" faible, est-ce la meilleure méthode de stockage et de
"parcours" ?
Une table de hachage n'est pas un mauvais choix. Son principe est le
suivant :
- on a un tableau de n éléments pour stocker m éléments (avec m plus
petits que n)
- On utilise une fonction de hachage qui associe à un objet à stocker
une valeur. La fonction de hachage est en générale la partie la plus
délicate dans l'algorithme. Mais il suffit d'utiliser des tables de
hachages toute faites.
- quand on veut stocker un objet (disons une chaîne de caractères),
on le fait passer dans la fonction de hachage et la valeur obtenue donne
l'index du tableau où il va être stocké.
De cette manière, rechercher si une chaîne est dans le tableau est très
rapide :
- on hache la chaîne (algorithme classiquement en o(t), t étant la
longueur de la chaîne
- on regarde à l'index t si la chaîne qui y est stockée est la même
Maintenant, il y a des problèmes induits par cette méthode : il n'y a
pas de bijection entre les chaînes et les valeurs. Donc plusieurs
chaînes différentes peuvent avoir la même valeur de hachage. C'est ce
qu'on appelle une « collision ». Il existe plusieurs façons de les
gérer. Mais c'est à cause de ces collisions que le tableau doit être
sensiblement plus grand que le nombre d'éléments à stocker.
Mais si tu veux faire une recherche à la volée, il y a peut-être une
autre structure qui pourrait être plus efficace : une structure d'arbre
avec des noeuds correspondant aux lettres et des feuilles qui seraient
les mots.
racine
/
a b
/ /
r a o
/ / |
b t l n b
| | | | o
a a b b u
r r a a l
b t l n e
r i l a
e s o n
t n e
e
Avec une telle structure, la recherche pourrait se faire au fur et à
mesure de la frappe, sans attendre que le mot soit fini de taper.
j'espère être sur le forum adéquat.. dans la négative, merci de ne pas me taper et de m'indiquer le forum le plus adapté :-)
fr.comp.algorithmes serait sans doute plus adapté, la question ne portant pas vraiment sur le langage C++.
j'ai 3 problèmes : 1 - peu d'expérience en C++
Normalement, ce problème là, avec la pratique, ça passe. :)
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé des "tables de hashage" (beaucoup de dictionnaires les utilisent à priori) mais j'avoue ne pas en avoir saisie le mode de fonctionnnement (si quelqu'un avait un exemple - très - simple) et donc sa mise en oeuvre. 3 - par rapport à la rapidité nécessaire pour cette application et le nombre de mots "relativement" faible, est-ce la meilleure méthode de stockage et de "parcours" ?
Une table de hachage n'est pas un mauvais choix. Son principe est le suivant : - on a un tableau de n éléments pour stocker m éléments (avec m plus petits que n) - On utilise une fonction de hachage qui associe à un objet à stocker une valeur. La fonction de hachage est en générale la partie la plus délicate dans l'algorithme. Mais il suffit d'utiliser des tables de hachages toute faites. - quand on veut stocker un objet (disons une chaîne de caractères), on le fait passer dans la fonction de hachage et la valeur obtenue donne l'index du tableau où il va être stocké.
De cette manière, rechercher si une chaîne est dans le tableau est très rapide : - on hache la chaîne (algorithme classiquement en o(t), t étant la longueur de la chaîne - on regarde à l'index t si la chaîne qui y est stockée est la même
Maintenant, il y a des problèmes induits par cette méthode : il n'y a pas de bijection entre les chaînes et les valeurs. Donc plusieurs chaînes différentes peuvent avoir la même valeur de hachage. C'est ce qu'on appelle une « collision ». Il existe plusieurs façons de les gérer. Mais c'est à cause de ces collisions que le tableau doit être sensiblement plus grand que le nombre d'éléments à stocker.
Mais si tu veux faire une recherche à la volée, il y a peut-être une autre structure qui pourrait être plus efficace : une structure d'arbre avec des noeuds correspondant aux lettres et des feuilles qui seraient les mots.
racine / a b / / r a o / / | b t l n b | | | | o a a b b u r r a a l b t l n e r i l a e s o n t n e e
Avec une telle structure, la recherche pourrait se faire au fur et à mesure de la frappe, sans attendre que le mot soit fini de taper.
Bon courage, Arnaud
Fabien LE LEZ
On Thu, 3 Jul 2003 09:14:30 +0200, "jmb" wrote:
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé des "tables de hashage"
Etant donné le faible nombre de mots dans le tableau (quelques milliers tout au plus), et la facilité avec laquelle on compare deux chaînes (la plupart du temps on ne compare que les quelques premiers caractères), un std::set<std::string> ne conviendrait-il pas ?
-- Tout sur fr.* (FAQ, etc.) : http://www.usenet-fr.net/fur/ et http://www.aminautes.org/forums/serveurs/tablefr.html Archives : http://groups.google.com/advanced_group_search http://www.usenet-fr.net/fur/usenet/repondre-sur-usenet.html
On Thu, 3 Jul 2003 09:14:30 +0200, "jmb" <CHAPEAUjm.b26@voila.fr>
wrote:
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé
des "tables de hashage"
Etant donné le faible nombre de mots dans le tableau (quelques
milliers tout au plus), et la facilité avec laquelle on compare deux
chaînes (la plupart du temps on ne compare que les quelques premiers
caractères), un std::set<std::string> ne conviendrait-il pas ?
--
Tout sur fr.* (FAQ, etc.) : http://www.usenet-fr.net/fur/
et http://www.aminautes.org/forums/serveurs/tablefr.html
Archives : http://groups.google.com/advanced_group_search
http://www.usenet-fr.net/fur/usenet/repondre-sur-usenet.html
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé des "tables de hashage"
Etant donné le faible nombre de mots dans le tableau (quelques milliers tout au plus), et la facilité avec laquelle on compare deux chaînes (la plupart du temps on ne compare que les quelques premiers caractères), un std::set<std::string> ne conviendrait-il pas ?
-- Tout sur fr.* (FAQ, etc.) : http://www.usenet-fr.net/fur/ et http://www.aminautes.org/forums/serveurs/tablefr.html Archives : http://groups.google.com/advanced_group_search http://www.usenet-fr.net/fur/usenet/repondre-sur-usenet.html
jmb
merci beaucoup pour vos explications et d'avoir pris le temps de détailler.
jm
"Arnaud Meurgues" a écrit dans le message de news: 3f03e7af$0$12467$
jmb wrote:
j'espère être sur le forum adéquat.. dans la négative, merci de ne pas me
taper et de m'indiquer le forum le plus adapté :-)
fr.comp.algorithmes serait sans doute plus adapté, la question ne portant pas vraiment sur le langage C++.
j'ai 3 problèmes : 1 - peu d'expérience en C++
Normalement, ce problème là, avec la pratique, ça passe. :)
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé
des "tables de hashage" (beaucoup de dictionnaires les utilisent à priori)
mais j'avoue ne pas en avoir saisie le mode de fonctionnnement (si quelqu'un
avait un exemple - très - simple) et donc sa mise en oeuvre. 3 - par rapport à la rapidité nécessaire pour cette application et le nombre
de mots "relativement" faible, est-ce la meilleure méthode de stockage et de
"parcours" ?
Une table de hachage n'est pas un mauvais choix. Son principe est le suivant : - on a un tableau de n éléments pour stocker m éléments (avec m plus petits que n) - On utilise une fonction de hachage qui associe à un objet à stocker une valeur. La fonction de hachage est en générale la partie la plus délicate dans l'algorithme. Mais il suffit d'utiliser des tables de hachages toute faites. - quand on veut stocker un objet (disons une chaîne de caractères), on le fait passer dans la fonction de hachage et la valeur obtenue donne l'index du tableau où il va être stocké.
De cette manière, rechercher si une chaîne est dans le tableau est très rapide : - on hache la chaîne (algorithme classiquement en o(t), t étant la longueur de la chaîne - on regarde à l'index t si la chaîne qui y est stockée est la même
Maintenant, il y a des problèmes induits par cette méthode : il n'y a pas de bijection entre les chaînes et les valeurs. Donc plusieurs chaînes différentes peuvent avoir la même valeur de hachage. C'est ce qu'on appelle une « collision ». Il existe plusieurs façons de les gérer. Mais c'est à cause de ces collisions que le tableau doit être sensiblement plus grand que le nombre d'éléments à stocker.
Mais si tu veux faire une recherche à la volée, il y a peut-être une autre structure qui pourrait être plus efficace : une structure d'arbre avec des noeuds correspondant aux lettres et des feuilles qui seraient les mots.
racine / a b / / r a o / / | b t l n b | | | | o a a b b u r r a a l b t l n e r i l a e s o n t n e e
Avec une telle structure, la recherche pourrait se faire au fur et à mesure de la frappe, sans attendre que le mot soit fini de taper.
Bon courage, Arnaud
merci beaucoup pour vos explications et d'avoir pris le temps de détailler.
jm
"Arnaud Meurgues" <arnaud@meurgues.non.fr.invalid> a écrit dans le message
de news: 3f03e7af$0$12467$626a54ce@news.free.fr...
jmb wrote:
j'espère être sur le forum adéquat.. dans la négative, merci de ne pas
me
taper et de m'indiquer le forum le plus adapté :-)
fr.comp.algorithmes serait sans doute plus adapté, la question ne
portant pas vraiment sur le langage C++.
j'ai 3 problèmes :
1 - peu d'expérience en C++
Normalement, ce problème là, avec la pratique, ça passe. :)
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu
parlé
des "tables de hashage" (beaucoup de dictionnaires les utilisent à
priori)
mais j'avoue ne pas en avoir saisie le mode de fonctionnnement (si
quelqu'un
avait un exemple - très - simple) et donc sa mise en oeuvre.
3 - par rapport à la rapidité nécessaire pour cette application et le
nombre
de mots "relativement" faible, est-ce la meilleure méthode de stockage
et de
"parcours" ?
Une table de hachage n'est pas un mauvais choix. Son principe est le
suivant :
- on a un tableau de n éléments pour stocker m éléments (avec m plus
petits que n)
- On utilise une fonction de hachage qui associe à un objet à stocker
une valeur. La fonction de hachage est en générale la partie la plus
délicate dans l'algorithme. Mais il suffit d'utiliser des tables de
hachages toute faites.
- quand on veut stocker un objet (disons une chaîne de caractères),
on le fait passer dans la fonction de hachage et la valeur obtenue donne
l'index du tableau où il va être stocké.
De cette manière, rechercher si une chaîne est dans le tableau est très
rapide :
- on hache la chaîne (algorithme classiquement en o(t), t étant la
longueur de la chaîne
- on regarde à l'index t si la chaîne qui y est stockée est la même
Maintenant, il y a des problèmes induits par cette méthode : il n'y a
pas de bijection entre les chaînes et les valeurs. Donc plusieurs
chaînes différentes peuvent avoir la même valeur de hachage. C'est ce
qu'on appelle une « collision ». Il existe plusieurs façons de les
gérer. Mais c'est à cause de ces collisions que le tableau doit être
sensiblement plus grand que le nombre d'éléments à stocker.
Mais si tu veux faire une recherche à la volée, il y a peut-être une
autre structure qui pourrait être plus efficace : une structure d'arbre
avec des noeuds correspondant aux lettres et des feuilles qui seraient
les mots.
racine
/
a b
/ /
r a o
/ / |
b t l n b
| | | | o
a a b b u
r r a a l
b t l n e
r i l a
e s o n
t n e
e
Avec une telle structure, la recherche pourrait se faire au fur et à
mesure de la frappe, sans attendre que le mot soit fini de taper.
merci beaucoup pour vos explications et d'avoir pris le temps de détailler.
jm
"Arnaud Meurgues" a écrit dans le message de news: 3f03e7af$0$12467$
jmb wrote:
j'espère être sur le forum adéquat.. dans la négative, merci de ne pas me
taper et de m'indiquer le forum le plus adapté :-)
fr.comp.algorithmes serait sans doute plus adapté, la question ne portant pas vraiment sur le langage C++.
j'ai 3 problèmes : 1 - peu d'expérience en C++
Normalement, ce problème là, avec la pratique, ça passe. :)
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé
des "tables de hashage" (beaucoup de dictionnaires les utilisent à priori)
mais j'avoue ne pas en avoir saisie le mode de fonctionnnement (si quelqu'un
avait un exemple - très - simple) et donc sa mise en oeuvre. 3 - par rapport à la rapidité nécessaire pour cette application et le nombre
de mots "relativement" faible, est-ce la meilleure méthode de stockage et de
"parcours" ?
Une table de hachage n'est pas un mauvais choix. Son principe est le suivant : - on a un tableau de n éléments pour stocker m éléments (avec m plus petits que n) - On utilise une fonction de hachage qui associe à un objet à stocker une valeur. La fonction de hachage est en générale la partie la plus délicate dans l'algorithme. Mais il suffit d'utiliser des tables de hachages toute faites. - quand on veut stocker un objet (disons une chaîne de caractères), on le fait passer dans la fonction de hachage et la valeur obtenue donne l'index du tableau où il va être stocké.
De cette manière, rechercher si une chaîne est dans le tableau est très rapide : - on hache la chaîne (algorithme classiquement en o(t), t étant la longueur de la chaîne - on regarde à l'index t si la chaîne qui y est stockée est la même
Maintenant, il y a des problèmes induits par cette méthode : il n'y a pas de bijection entre les chaînes et les valeurs. Donc plusieurs chaînes différentes peuvent avoir la même valeur de hachage. C'est ce qu'on appelle une « collision ». Il existe plusieurs façons de les gérer. Mais c'est à cause de ces collisions que le tableau doit être sensiblement plus grand que le nombre d'éléments à stocker.
Mais si tu veux faire une recherche à la volée, il y a peut-être une autre structure qui pourrait être plus efficace : une structure d'arbre avec des noeuds correspondant aux lettres et des feuilles qui seraient les mots.
racine / a b / / r a o / / | b t l n b | | | | o a a b b u r r a a l b t l n e r i l a e s o n t n e e
Avec une telle structure, la recherche pourrait se faire au fur et à mesure de la frappe, sans attendre que le mot soit fini de taper.
Bon courage, Arnaud
jmb
effectivement. je cherche peut-être à 'trop bien' faire. merci beaucoup pour votre réponse.
jm
"Fabien LE LEZ" a écrit dans le message de news:
On Thu, 3 Jul 2003 09:14:30 +0200, "jmb" wrote:
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé
des "tables de hashage"
Etant donné le faible nombre de mots dans le tableau (quelques milliers tout au plus), et la facilité avec laquelle on compare deux chaînes (la plupart du temps on ne compare que les quelques premiers caractères), un std::set<std::string> ne conviendrait-il pas ?
-- Tout sur fr.* (FAQ, etc.) : http://www.usenet-fr.net/fur/ et http://www.aminautes.org/forums/serveurs/tablefr.html Archives : http://groups.google.com/advanced_group_search http://www.usenet-fr.net/fur/usenet/repondre-sur-usenet.html
effectivement. je cherche peut-être à 'trop bien' faire. merci beaucoup pour
votre réponse.
jm
"Fabien LE LEZ" <gramster@gramster.com> a écrit dans le message de news:
34t7gvc6g35fqvh3dvd8n26q7inj5b2lgp@4ax.com...
On Thu, 3 Jul 2003 09:14:30 +0200, "jmb" <CHAPEAUjm.b26@voila.fr>
wrote:
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu
parlé
des "tables de hashage"
Etant donné le faible nombre de mots dans le tableau (quelques
milliers tout au plus), et la facilité avec laquelle on compare deux
chaînes (la plupart du temps on ne compare que les quelques premiers
caractères), un std::set<std::string> ne conviendrait-il pas ?
--
Tout sur fr.* (FAQ, etc.) : http://www.usenet-fr.net/fur/
et http://www.aminautes.org/forums/serveurs/tablefr.html
Archives : http://groups.google.com/advanced_group_search
http://www.usenet-fr.net/fur/usenet/repondre-sur-usenet.html
effectivement. je cherche peut-être à 'trop bien' faire. merci beaucoup pour votre réponse.
jm
"Fabien LE LEZ" a écrit dans le message de news:
On Thu, 3 Jul 2003 09:14:30 +0200, "jmb" wrote:
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé
des "tables de hashage"
Etant donné le faible nombre de mots dans le tableau (quelques milliers tout au plus), et la facilité avec laquelle on compare deux chaînes (la plupart du temps on ne compare que les quelques premiers caractères), un std::set<std::string> ne conviendrait-il pas ?
-- Tout sur fr.* (FAQ, etc.) : http://www.usenet-fr.net/fur/ et http://www.aminautes.org/forums/serveurs/tablefr.html Archives : http://groups.google.com/advanced_group_search http://www.usenet-fr.net/fur/usenet/repondre-sur-usenet.html
Fabien LE LEZ
On Thu, 3 Jul 2003 13:15:27 +0200, "jmb" wrote:
je cherche peut-être à 'trop bien' faire.
Peut-être... à part dans ta manière de répondre à l'envers (cf <http://www.giromini.org/usenet-fr/repondre.html>). Généralement, le mieux est d'implémenter des méthodes simples, même si elles paraissent trop lentes à première vue. Si à l'exécution, c'est effectivement trop lent, on peut lancer le profiler et s'occuper d'optimisation...
-- Tout sur fr.* (FAQ, etc.) : http://www.usenet-fr.net/fur/ et http://www.aminautes.org/forums/serveurs/tablefr.html Archives : http://groups.google.com/advanced_group_search http://www.usenet-fr.net/fur/usenet/repondre-sur-usenet.html
On Thu, 3 Jul 2003 13:15:27 +0200, "jmb" <CHAPEAUjm.b26@voila.fr>
wrote:
je cherche peut-être à 'trop bien' faire.
Peut-être... à part dans ta manière de répondre à l'envers (cf
<http://www.giromini.org/usenet-fr/repondre.html>).
Généralement, le mieux est d'implémenter des méthodes simples, même si
elles paraissent trop lentes à première vue. Si à l'exécution, c'est
effectivement trop lent, on peut lancer le profiler et s'occuper
d'optimisation...
--
Tout sur fr.* (FAQ, etc.) : http://www.usenet-fr.net/fur/
et http://www.aminautes.org/forums/serveurs/tablefr.html
Archives : http://groups.google.com/advanced_group_search
http://www.usenet-fr.net/fur/usenet/repondre-sur-usenet.html
Peut-être... à part dans ta manière de répondre à l'envers (cf <http://www.giromini.org/usenet-fr/repondre.html>). Généralement, le mieux est d'implémenter des méthodes simples, même si elles paraissent trop lentes à première vue. Si à l'exécution, c'est effectivement trop lent, on peut lancer le profiler et s'occuper d'optimisation...
-- Tout sur fr.* (FAQ, etc.) : http://www.usenet-fr.net/fur/ et http://www.aminautes.org/forums/serveurs/tablefr.html Archives : http://groups.google.com/advanced_group_search http://www.usenet-fr.net/fur/usenet/repondre-sur-usenet.html
kanze
Fabien LE LEZ wrote in message news:...
On Thu, 3 Jul 2003 09:14:30 +0200, "jmb" wrote:
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé des "tables de hashage"
Etant donné le faible nombre de mots dans le tableau (quelques milliers tout au plus), et la facilité avec laquelle on compare deux chaînes (la plupart du temps on ne compare que les quelques premiers caractères), un std::set<std::string> ne conviendrait-il pas ?
Ça dépend à la fois du processeur et de l'application. Sur Intel, j'ai trouvé qu'avec une fonction d'hachage convenable, le hash_map de G++ me donnait un gain d'environ 30% sur une table avec 75 entrées. Sur un Sparc, en revanche, avec 75 entrées, les deux étaient à peu près égal. (Pour toutes les mésures, voir http://www.gabi-soft.fr/code/Benchmarks/Hashcode/Analysis.txt.)
En ce qui concerne l'application -- s'il doit réagir à la vitesse que quelqu'un tape un message, il pourrait très bien se contenter d'une recherche linéaire, même pour plusieurs milliers d'éléments. Sinon, Arnaud a suggéré un « splay trie », qui serait effectivement l'algorithme optimal pour un traitement en temps réel, à fur et à mésure de la tape.
-- James Kanze GABI Software mailto: Conseils en informatique orientée objet/ http://www.gabi-soft.fr Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France, Tél. : +33 (0)1 30 23 45 16
Fabien LE LEZ <gramster@gramster.com> wrote in message
news:<34t7gvc6g35fqvh3dvd8n26q7inj5b2lgp@4ax.com>...
On Thu, 3 Jul 2003 09:14:30 +0200, "jmb" <CHAPEAUjm.b26@voila.fr>
wrote:
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu
parlé des "tables de hashage"
Etant donné le faible nombre de mots dans le tableau (quelques
milliers tout au plus), et la facilité avec laquelle on compare deux
chaînes (la plupart du temps on ne compare que les quelques premiers
caractères), un std::set<std::string> ne conviendrait-il pas ?
Ça dépend à la fois du processeur et de l'application. Sur Intel, j'ai
trouvé qu'avec une fonction d'hachage convenable, le hash_map de G++ me
donnait un gain d'environ 30% sur une table avec 75 entrées. Sur un
Sparc, en revanche, avec 75 entrées, les deux étaient à peu près
égal. (Pour toutes les mésures, voir
http://www.gabi-soft.fr/code/Benchmarks/Hashcode/Analysis.txt.)
En ce qui concerne l'application -- s'il doit réagir à la vitesse que
quelqu'un tape un message, il pourrait très bien se contenter d'une
recherche linéaire, même pour plusieurs milliers d'éléments. Sinon,
Arnaud a suggéré un « splay trie », qui serait effectivement
l'algorithme optimal pour un traitement en temps réel, à fur et à mésure
de la tape.
--
James Kanze GABI Software mailto:kanze@gabi-soft.fr
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, Tél. : +33 (0)1 30 23 45 16
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé des "tables de hashage"
Etant donné le faible nombre de mots dans le tableau (quelques milliers tout au plus), et la facilité avec laquelle on compare deux chaînes (la plupart du temps on ne compare que les quelques premiers caractères), un std::set<std::string> ne conviendrait-il pas ?
Ça dépend à la fois du processeur et de l'application. Sur Intel, j'ai trouvé qu'avec une fonction d'hachage convenable, le hash_map de G++ me donnait un gain d'environ 30% sur une table avec 75 entrées. Sur un Sparc, en revanche, avec 75 entrées, les deux étaient à peu près égal. (Pour toutes les mésures, voir http://www.gabi-soft.fr/code/Benchmarks/Hashcode/Analysis.txt.)
En ce qui concerne l'application -- s'il doit réagir à la vitesse que quelqu'un tape un message, il pourrait très bien se contenter d'une recherche linéaire, même pour plusieurs milliers d'éléments. Sinon, Arnaud a suggéré un « splay trie », qui serait effectivement l'algorithme optimal pour un traitement en temps réel, à fur et à mésure de la tape.
-- James Kanze GABI Software mailto: Conseils en informatique orientée objet/ http://www.gabi-soft.fr Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France, Tél. : +33 (0)1 30 23 45 16
Laurent Oget
"jmb" writes:
1 - peu d'expérience en C++
on est tous passe par la
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé des "tables de hashage" (beaucoup de dictionnaires les utilisent à priori) mais j'avoue ne pas en avoir saisie le mode de fonctionnnement (si quelqu'un avait un exemple - très - simple) et donc sa mise en oeuvre. 3 - par rapport à la rapidité nécessaire pour cette application et le nombre de mots "relativement" faible, est-ce la meilleure méthode de stockage et de "parcours" ?
tu n'es certainement pas le premier a avoir eu ce genre de probleme, et mon conseil est de ne pas reinventer la roue. berkeley DB a ete concu pour resoudre ce genre de problemes. profites-en. un petit google-age de "berkeley db" te donnera tous les renseignements necessaires. et "berkeley db windows" te rassurera pour ce qui est de la plateforme.
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé
des "tables de hashage" (beaucoup de dictionnaires les utilisent à priori)
mais j'avoue ne pas en avoir saisie le mode de fonctionnnement (si quelqu'un
avait un exemple - très - simple) et donc sa mise en oeuvre.
3 - par rapport à la rapidité nécessaire pour cette application et le nombre
de mots "relativement" faible, est-ce la meilleure méthode de stockage et de
"parcours" ?
tu n'es certainement pas le premier a avoir eu ce genre de probleme, et mon
conseil est de ne pas reinventer la roue. berkeley DB a ete concu pour resoudre
ce genre de problemes. profites-en. un petit google-age de "berkeley db" te
donnera tous les renseignements necessaires. et "berkeley db windows" te
rassurera pour ce qui est de la plateforme.
2 - la façon dont vont être stockés les mots à détecter. j'ai entendu parlé des "tables de hashage" (beaucoup de dictionnaires les utilisent à priori) mais j'avoue ne pas en avoir saisie le mode de fonctionnnement (si quelqu'un avait un exemple - très - simple) et donc sa mise en oeuvre. 3 - par rapport à la rapidité nécessaire pour cette application et le nombre de mots "relativement" faible, est-ce la meilleure méthode de stockage et de "parcours" ?
tu n'es certainement pas le premier a avoir eu ce genre de probleme, et mon conseil est de ne pas reinventer la roue. berkeley DB a ete concu pour resoudre ce genre de problemes. profites-en. un petit google-age de "berkeley db" te donnera tous les renseignements necessaires. et "berkeley db windows" te rassurera pour ce qui est de la plateforme.
