Discussion :

[Snooky68]

Bonjour à tous,

J'ai un problème de taille!
J'explique la problématique:

Premièrement, nous avons un site internet avec des articles, chaque article peut être dans une ou plusieurs sections, une ou plusieurs sous sections, et une ou plusieurs catégorie! Suivant chaqu'un de ces trois éléments (que nous appelons un secteur) un article possède plusieurs questions que l'utilisateur peut renseigner (chaque question peut appartenir a plusieurs secteur)!

Deuxièmement, nous avons une page de recherche d'article! La recherche se fait suivant les questions, mais aussi suivant un champs 'quoi' et un champs 'ou'.

Le probléme c'est de faire la recherche suivant les questions! car Pour trouver les articles correspondant exactement au différente question/reponse on a trouvé un moyen.

Chaque réponse est booléenne, ainsi si on a quatre questions dons les deux première sont renseigné, on a la valeur 1100 => (en binaire) 3. Donc quand l'utilisateur fait la recherche on fait ce calcule simple et on recherche les articles qui on la valeur 3 (donc les même réponse)

Le problème c'est que pour 1000 réponse (pour plusieurs question bien sur) on peut obtenir des chiffres de 2^1000 ~= 1*10^300 possibilité! Ce dernier chiffre n'est pas gérable!

On a pensé a décomposé par question au lieux par réponse, mais impossible alors de faire un trie par pertinence! (un order by)

Quelqu'un a't'il déjà été confronté a ce genre d'extrême? Et comment résoudre le problème?

Merci beaucoup.

[pseudocode]

On a pensé a décomposé par question au lieux par réponse, mais impossible alors de faire un trie par pertinence! (un order by)

Ah ? Pourquoi ?

En SQL, une requête count(*) + GROUP BY sur la table de liaison article/question devrait fonctionner. Enfin, je ne suis pas un pro du SQL, mais il me semble.

[Nemerle]

Le problème c'est que pour 1000 réponse (pour plusieurs question bien sur) on peut obtenir des chiffres de 2^1000 ~= 1*10^300 possibilité! Ce dernier chiffre n'est pas gérable.

Salut, le problème c'est qu'on ne sait pas ce que tu veux faire?

[Snooky68]

Se que je veut faire c'est rechercher des articles suivant les question répondu ou non!

Donc... la personne qui rédige l'article choisie section, sous section, catégorie!
Puis, suivant ces trois éléments doit répondre a plusieurs questions! Du style: Quel est la langue de l'article. Pour quel ville s'applique l'article ...
Les réponses a ces question sont booléenne: ex: allemand => Oui, Anglais => Non, Paris=>Oui, Orléan=>Oui... etc!

Dans un second temps, un utilisateur lambda va faire une recherche d'article.
Il recherche suivant le 'quoi' (sujet de l'article) et suivant des questions:
quel langue pour l'article: Anglais => oui, allemand=> oui.....,
Quel ville: paris=>oui, allemand=>oui...

Chaque réponse possède une valeur binaire:
Réponse 1 = 1
Réponse2 = 2
Réponse3 = 4
Réponse4 = 8
....

Ainsi, quand un rédacteur crée un article et qu'il répond au question, suivant les réponse qu'il aurra donnée, l'article aurra une valeur.
Ex: Si pour l'article 1 il a répondu a la question 1, 2 et 4, l'article aurra la valeur 11! (binaire: 1+2+0+8)

Ainsi, quand un utilisateur fait une recherche, il répond au question, je calcule cette même valeur et la recherche dans la base d'article.

Et j'aurais donc les articles qui corresponde a la recherche!

Le problème:
Imaginons que j'ai 1000 réponses possibles sur l'ensemble des questions, j'aurrais donc, si un utilisateur répond a toute les questions, une valeur d'article qui serra de 2^1000.

Chiffre que je ne peut pas stocker!

pseudocode: Merci de ta participation, mais nous travaillons sur des tables de 300 000 article, un order by n'est pas possible! Bien trop long.

Nemerle: J'espère t'avoir renseigné!

[pseudocode]

Peut-on imaginer faire la requête en deux temps.

1. Chercher les articles candidats par un système analogue a ton bitmask. Par exemple en calculant des hash pour différentes combinaison de réponses (cf. Locality sensitive hashing)

2. Dans les articles candidats restant, faire un examen détaillé pour ne garder que les articles qui remplissent tous les critères (et les trier, noter, ... )

[Nemerle]

je n'y connait pas grand chose en base de données, mais j'ai 2 options:

- en SQL par exemple, la classe bigint permet d'aller jusqu'à 2^63, donc tu peux stocker tes 1000 réponses avec 16 champs

- mais surtout, pourquoi ne pas stocker tes mille réponses sous la forme d'une chaine de caractères? Ta base n'est pas énorme...

[Invité]

Bonjour,
J'essaye de voir le problème à l'envers.
Vous avez 300 000 articles, cela tient facilement sur 32 bits.
Lorsqu'un visiteur donne une réponses, c'est à dire un ensemble N de OUI ou NON, sur un nombre limité de questions, le nombre d'articles adressés sera un ensemble R limité, et probablement inférieur à N.
Si j'ai ben compris, les articles sont organisés en Section - SousSection - Catégorie. Ils devraient avoir un système d'adressage (clé) correspondant à cette organisation (directement ou indirectement).

S'il y a 1000 réponses, il ne peut pas y avoir 2^1000 possibilités, puisqu'il n'y a que 300 000 articles.
Par ailleurs, combien y a-t-il de questions différentes ? soit Q ce nombre.
Le nombre total que réponses possibles et différentes est 2^Q.
Mais comme un se trouve dans une hiérarchie à 3, c'est encore beaucoup moins.

Donc, le problème revient à établir une clé pour les articles qui donne une correspondance avec la réponse cherchée.

Autrement dit, je ne pense pas qu'il faille voir "toutes les possibilités théoriques", mais "arriver au résultat avec les informations disponibles".
Cela va dans le sens exposé par pseudocode, avec en plus une hiérarchie à 3 niveaux, puisque c'est le cas.

[pseudocode]

Cela va dans le sens exposé par pseudocode, avec en plus une hiérarchie à 3 niveaux, puisque c'est le cas.

Il n'y a pas de hiérarchie dans ce que j'ai proposé. Ce sont juste des clés de filtrages pour limiter le nombre de comparaisons détaillées à faire. Comparaisons qui peuvent être faites sur des chaines de caractères comme le préconise Nemerle.

[TropMDR]

Le problème c'est que pour 1000 réponse (pour plusieurs question bien sur) on peut obtenir des chiffres de 2^1000 ~= 1*10^300 possibilité! Ce dernier chiffre n'est pas gérable!

Ca donne l'impression que tu confonds un nombre et la quantité qu'il représente. Clairement, si tu avais 2^1000 "trucs" a géré, tu serais dans la mouise. Par contre, stocker un tel nombre, c'est 125 octets. Ca ne devrait plus faire vraiment peur ! Tu peux par exemple le stocker sous forme de chaîne de caractère, quitte à passer par un encodage en base64 par exemple (http://en.wikipedia.org/wiki/Base64 ) En revanche si tu fais ça, une recherche du type "tous les messages où la réponses est oui à la question 42" risquera d'être assez lente, puisqu'il faudra décoder pour chaque message et récupérer le 42ème bit. Pas trop d'indexation possible de la part du moteur de BDD.

[Invité(e)]

Bonjour,

Je ne pense pas que la solution de stocker toutes les informations d'un article dans un seul nombre soit pérenne.

En effet, comment doit se comporter le classement si des questions ou des réponses sont ajoutées ou enlevées de temps à autre ?

Plutôt qu'un seul grand nombre pour tout stocker, ne serait-il pas mieux de séparer ce qui est séparable ? (tableaux de nombres, base de données...)

[Snooky68]

Merci a tous,

En effet, la technique n'était pas la bonne!
J'ai trouvé une autre solution, simplement de mettre chaque liaison entre article et réponse dans une seul table (table a deux colonnes, les deux formants une clé unique!)

Puis utiliser une requête de la forme:

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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
SELECT  DISTINCT(v0.ARTICLE)
FROM `test` v0
INNER JOIN test v1 ON v1.ARTICLE = v0.ARTICLE
INNER JOIN test v2 ON v2.ARTICLE = v0.ARTICLE
INNER JOIN test v3 ON v3.ARTICLE = v0.ARTICLE
INNER JOIN test v4 ON v4.ARTICLE = v0.ARTICLE
INNER JOIN test v5 ON v5.ARTICLE = v0.ARTICLE
INNER JOIN test v6 ON v6.ARTICLE = v0.ARTICLE
WHERE (
v0.REPONSE =1
AND v1.REPONSE =2
AND v2.REPONSE =3
AND v3.REPONSE =4
AND v4.REPONSE =5
AND v5.REPONSE =6
AND v6.REPONSE =7
)
OR (
v0.REPONSE =1
AND v1.REPONSE =2
AND v2.REPONSE =3
AND v3.REPONSE =4
AND v4.REPONSE =5
AND v5.REPONSE =6
)
OR (
v0.REPONSE =1
AND v1.REPONSE =2
AND v2.REPONSE =3
AND v3.REPONSE =4
AND v4.REPONSE =5
)
OR (
v0.REPONSE =1
AND v1.REPONSE =2
AND v2.REPONSE =3
AND v3.REPONSE =4
)
OR (
v0.REPONSE =1
AND v1.REPONSE =2
AND v2.REPONSE =3
)
OR (
v0.REPONSE =1
AND v1.REPONSE =2
)
OR(
v0.REPONSE =1
)
LIMIT 0,10

Cette requête me donne des temps de réponse de 0.01 seconde sur une table de 5 000 000 d'enregistrement! Ensuite tout dépendra de la recherche effectué!

Mon problème à présent, c'est le LIMIT a la fin de la requête! Ce LIMIT fait que la requête n'est pas trop longue dans la plupart des cas, mais a cause de lui je n'est pas la totalité les réponses! Est-il possible d'approximer rapidement le nombre total de réponse?

Est-il possible aussi de limiter le temps d'exécution d'une requête? Imaginons, je lui dit que la requête ne prendra pas plus d'une seconde, si elle atteint une seconde elle renvoie se qu'elle a sans poursuivre!

Possible ou non?

Merci.

[Invité(e)]

Mon problème à présent, c'est le LIMIT a la fin de la requête! Ce LIMIT fait que la requête n'est pas trop longue dans la plupart des cas, mais a cause de lui je n'est pas la totalité les réponses! Est-il possible d'approximer rapidement le nombre total de réponse?

Je pense que tu peux chercher du coté du mot clef COUNT. Qui ne renvoie pas les éléments trouvés mais juste leur nombre.

Est-il possible aussi de limiter le temps d'exécution d'une requête? Imaginons, je lui dit que la requête ne prendra pas plus d'une seconde, si elle atteint une seconde elle renvoie se qu'elle a sans poursuivre!

Question à poser plutôt sur le forum concernant ta base de données. A mon avis, une base ne dispose pas forcement de ce genre de fioriture en interne, mais rien ne t'empêche de lancer une requête dans un thread secondaire et de l'ignorer s'il met trop de temps à s'exécuter.

[Snooky68]

Ok! Merci a tous!

J'ai déjà chercher sur COUNT, mais ma requete prend alors un temps fou!

Merci a tous, j'ouvrirais un autre poste dans la bonne section du forum!