IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage SQL Discussion :

[PostgreSQL 9.3] Recherche par mots clés pondérés sur un gros volume de données


Sujet :

Langage SQL

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Juillet 2014
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Santé

    Informations forums :
    Inscription : Juillet 2014
    Messages : 4
    Points : 1
    Points
    1
    Par défaut [PostgreSQL 9.3] Recherche par mots clés pondérés sur un gros volume de données
    Salut,

    Bloqué depuis quelques jours sur une tache, je fais appel à toi lecteur émérite et expert SQL.



    Tout d'abord un petit diagramme d'entités-relations

    Nom : DB.resize.png
Affichages : 454
Taille : 79,0 Ko

    Une archive peut comporter des archives fils. Pour chaque mot clé associé à une archive un poids est attribué et ce pour donner de l'importance au mot.

    Un exemple du contenu de la base


    Archive

    id code label father
    1 B28 Confidentiel
    2 B28.1 Zone nucléaire 1

    Association archive - mot clé

    id keyword_id archive_id weight
    1 1 1 10
    2 1 2 20
    3 2 2 30
    4 3 2 40

    Mots clés

    id label
    1 SECURITE
    2 ZONE
    3 NUCLEAIRE

    La demande


    L'objectif ici est de réaliser une recherche sur cette base.

    Scénario d'utilisation

    L'utilisateur saisit une chaine de caractère composée de mots du langage courant (français) ou de mots spécifiques. En fonction de ces derniers, une liste d'archives lui est retourné.

    Volumétrie

    La table d'archive est composée de 100 000 tuples, 80 000 pour la table de mots clés et 1 000 000 d'associations entre ces deux entités.

    Le raisonnement

    La logique

    Pour répondre au problème, différents facteurs sont à prendre en compte :

    • L'être humain peut se tromper dans l'orthographe d'un mot, l'accorder, le préfixer...
    • Le poids d'un mot lui donne de l'importance
    • Donner une plus-value aux archives comportent les x mots clés proches de ce que tape l'utilisateur


    Pour répondre au premier facteur j'utilise la distance de levenshtein entre le mot tapé par l'utilisateur et le mot clé, mais aussi la distance de levenshtein entre le double métaphone du mot tapé par l'utilisateur et le double métaphone du mot clé.

    Pour le second facteur, plus le poids est élevé plus le mot à de l'importance.


    D'un point de vue SQL

    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
    select f.id, f.code, f.label, min(f.dist) as distF, max(f.poid) as poidF
    from
    (
        select
            a.id,
            a.code,
            a.label,
            ( ( levenshtein(lower('Sécurité'), lower(k1.label)) + 1 ) + ( levenshtein(lower('Nucléaire'), lower(k2.label)) + 1 ) ) as dist,
            ( ka1.balance + kd2.balance ) as poid
     
        from archive a
     
        inner join assoc_kw_archive ka1
            on ka1.archive_id = a.id
        inner join keyword k1
            on k1.id = ka1.keywords_id
     
        inner join assoc_kw_archive ka2
            on ka2.archive_id = a.id
        inner join keyword k2
            on k2.id = ka2.keywords_id
     
        where levenshtein(dmetaphone('Sécurité'), dmetaphone(k1.label)) < 2
          and levenshtein(dmetaphone('Nucléaire'), dmetaphone(k2.label)) < 2
    ) as f
     
    group by f.id, f.code, f.label
    order by distF asc, poidF desc
    limit 10;
    Ayant tourné très longtemps sur différentes versions de la requête, mon esprit est maintenant embrouillé et je n'arrive plus à prendre de recul.

    Le problème

    Il est simple. En l'état cette requête fonctionne avec un mot clé, en revanche avec X mots clés elle est très longue (+ de 40 secondes). Normal me direz vous, je fais une jointure pour chaque mot donné par l'utilisateur, et sur 1 million d'associations c'est douloureux. Mais je n'arrive pas à trouver une solution où je donne une plus-value à un ensemble de mots clés proches de la chaine tapée par l'utilisateur.

    Conclusion

    Je fais appel à ta logique, l'exercice étant de trouver les archives en fonction de la chaine de caractères tapée par l'utilisateur.

    Exemple :

    recherche -> "Sécurité en zaunes nucléaires" (zaunes au lieu de zones, et aux pluriel alors qu'en base c'est au singulier)

    résultat -> Archives "D28.1 Zone nucléaire, D28 Confidentiel"

    Si t'as une piste, donnes, si t'as une autre solution de recherche (plein-text...) donnes, si t'as des remarques donnes, en fait donnes tout ce que t'as, je suis preneur

    Un grand merci pour ton aide par avance.

  2. #2
    Expert éminent sénior
    Homme Profil pro
    Responsable Données
    Inscrit en
    Janvier 2009
    Messages
    5 188
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Responsable Données

    Informations forums :
    Inscription : Janvier 2009
    Messages : 5 188
    Points : 12 744
    Points
    12 744
    Par défaut
    Bonjour,
    Je pense que tu devrais stocker dans la table keyword la "valeur de levenshtein", plutôt que de la calculer à la volée.
    Si en plus tu calcules cette valeur pour les mots saisis dans l'application, tu peux utiliser un index sur cette valeur, ce qui devrait grandement accélérer les recherches.

    Tatayo.

  3. #3
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Juillet 2014
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Santé

    Informations forums :
    Inscription : Juillet 2014
    Messages : 4
    Points : 1
    Points
    1
    Par défaut
    Salut,

    Merci pour ton aide. En revanche il est impossible de stocker en base la distance de levenshtein car elle dépend du mot saisi par l'utilisateur, ce qui n'est pas le cas du double métaphone pour le label du keyword. Par simplicité je n'est pas représenté ici cette colonne, mais elle bien présente dans la table avec un index dessus .

    Merci

  4. #4
    Expert éminent sénior
    Homme Profil pro
    Responsable Données
    Inscrit en
    Janvier 2009
    Messages
    5 188
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Responsable Données

    Informations forums :
    Inscription : Janvier 2009
    Messages : 5 188
    Points : 12 744
    Points
    12 744
    Par défaut
    Je ne dis pas de stocker la "distance" entre deux mots, mais la valeur de chaque mot, selon le calcul utilisé pour la distance de levenshtein. La distance n'étant que la différence entre les "valeurs" de 2 mots
    C'est ce qu'on fait chez nous, avec les noms des clients. Ainsi on peut faire une recherche phonétique, pour s'affranchir des fautes de frappes.
    La requête se fait alors en comparant la valeur du nom saisie avec celle associée au client, en triant sur la valeur absolue de l'écart.
    C'est plus rapide car la valeur est indexée, alors que dans ta requête il faut passer par une fonction, ce qui exclue l'utilisation d'un index.
    La recherche chez nous (pour plusieurs centaines de milliers de clients) est instantanée.

    Tatayo.

  5. #5
    Modérateur

    Profil pro
    dba
    Inscrit en
    Janvier 2010
    Messages
    5 643
    Détails du profil
    Informations personnelles :
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : dba

    Informations forums :
    Inscription : Janvier 2010
    Messages : 5 643
    Points : 13 092
    Points
    13 092
    Par défaut
    Bonjour,

    @Tatayo, j'ai un peu de mal à comprendre la logique. La distance de Levenshtein calcul le nombre de "manipulations" qu'il faut faire pour passer d'une chaine a l'autre, une manipulation étant soit une insertion, soit un suppression, soit un substitution de caractère. Dès lors, elle ne peut être calculée qu'en connaissant les deux chaines, et on ne peut pas calculer une valeur à partir d'un seul mot. N'y a-t-il pas confusion avec les soundex, qui consistent à calculer une valeur pour un mot en fonction de sa "phonétique", afin que deux mots ayant des prononciation semblables aient des valeurs proches ?
    Cela dit, ce serait une solution à envisager ici...

    @cjnet :
    Le fait que la requête soit rapide pour un mot laisse supposer que la recherche dans la table des mots clefs à partir d'un mot saisie reste acceptable.
    Par curiosité, combien de temps prends une simple requête telle que :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    SELECT *
    FROM keyword k1
    WHERE levenshtein(dmetaphone('Sécurité'), dmetaphone(k1.label)) < 2
    Cependant, un point n'est pas clair : est-ce que vous cherchez les archives qui sont rattachées à tous les mots clefs saisis, comme le laisse supposer votre requête (jointure interne + restriction dans le WHERE), ou cherchez vous également les archives correspondant à au moins un mot clef, et mettre en priorité dans le résultats les archives correspondant au plus grand nombre de mots clef ?

    Enfin, faire une jointure par mot clef n'est pas forcément une bonne idée, vous devrez écrire une requête différente par nombre de mots clefs saisis.

    Que donne ceci :
    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
     
    ;WITH mots(mot) as (
    	SELECT 'Sécurité' as mot
    	UNION ALL 
    	SELECT 'Nucléaire'
    )	
    SELECT f.id, f.code, f.label, min(f.dist) AS distF, max(f.poid) AS poidF
    FROM
    (
        SELECT
            a.id,
            a.code,
            a.label,
            mot,
            SUM(levenshtein(lower(mot), lower(k1.label)) + 1  ) AS dist,
            SUM( ka1.balance ) AS poid
        FROM archive a
     
        INNER JOIN assoc_kw_archive ka1
            ON ka1.archive_id = a.id
        INNER JOIN keyword k1
            ON k1.id = ka1.keywords_id
        INNER JOIN mots
            ON levenshtein(dmetaphone(mot), dmetaphone(k1.label)) < 2
    	GROUP BY 
            a.id,
            a.code,
            a.label,
            mot
    ) AS f
     
    GROUP BY f.id, f.code, f.label
    ORDER BY distF ASC, poidF DESC
    LIMIT 10;

  6. #6
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Juillet 2014
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Santé

    Informations forums :
    Inscription : Juillet 2014
    Messages : 4
    Points : 1
    Points
    1
    Par défaut
    Merci pour votre aide, je suis bloqué la dessus depuis tellement longtemps que je suis à la fois démoralisé et perdu sur cette tache. Mais votre coup de main me redonne la pêche alors merci !

    @aieeeuuuuu alors pour répondre à ta question, le temps d’exécution est d'environ 20ms pour un select avec restriction sur la distance de Levenshtein et ce sur une machine de dev (VM).

    cherchez vous également les archives correspondant à au moins un mot clef, et mettre en priorité dans le résultats les archives correspondant au plus grand nombre de mots clef ?
    C'est exactement ça mon problème!

    En faite, je cherche la liste d'archive qui correspond d'une part au mot clés saisies (avec lissage orthographique/distance de Levenshtein ou autres) et d'autre part, prendre en compte l'importance des mots (leurs poids) pour trier ma liste d'archive.

    Et en effet l'idée de faire une jointure par mot clé est d'une contraire à mon éthique sql (c'est vraiment pas propre) et de deux cette solution est lentes.

    En ce qui concerne ta requête, elle est vraiment plus efficace d'un point de vue performance. En revanche elle ne pondère pas la faite de retrouver les archives comportant plusieurs mots tapé par l'utilisateur :/.

  7. #7
    Modérateur

    Profil pro
    dba
    Inscrit en
    Janvier 2010
    Messages
    5 643
    Détails du profil
    Informations personnelles :
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : dba

    Informations forums :
    Inscription : Janvier 2010
    Messages : 5 643
    Points : 13 092
    Points
    13 092
    Par défaut
    Citation Envoyé par cjnet Voir le message
    En revanche elle ne pondère pas la faite de retrouver les archives comportant plusieurs mots tapé par l'utilisateur :/.
    C'est possible, en ajoutant par exemple COUNT(DISTINCT mot) AS NbMotsTrouves dans la sous requête, et en triant dessus.

    Mais je ne l'ai pas ajouté, car il faut définir votre ordre de priorité, et qu'il faut prendre en compte qu'avec cette requête, un mot clef saisi pourrait correspondre à plusieurs mots clefs différents dans la la table keyword du fait de la recherche floue.

    A vous donc de voir comment vous voulez pondérer chaque critère dans le tri du résultat. Car si vous prenez en compte en priorité la concordance avec le nombre de mots clefs saisi, dans votre exemple, "zone nucléaire" aura un meilleur score avec les mots clefs "dose sévérité" qu'avec les mots clefs "secteur nucléaire" (dose <=> zone ; sévérité<=> sécurité).

    Vous pouvez par exemple trier selon la somme du poids des mots divisés par la distance de Levenshtein (+ 1 pour éviter la division par zéro). Ainsi les mots bien orthographiés auront plus de valeur que les mots approximatifs, et le nombre de mots clefs trouvés (même approximatifs) sera également pris en compte...

  8. #8
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Juillet 2014
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Santé

    Informations forums :
    Inscription : Juillet 2014
    Messages : 4
    Points : 1
    Points
    1
    Par défaut
    Merci pour la réactivité @aieeeuuuuu, vraiment smart comme idée ! J'implémente la requête et je reviens vous dire ce que ça donne niveau pertinence. Encore merci pour votre aide !

  9. #9
    Rédacteur

    Avatar de SQLpro
    Homme Profil pro
    Expert bases de données / SQL / MS SQL Server / Postgresql
    Inscrit en
    Mai 2002
    Messages
    21 736
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Expert bases de données / SQL / MS SQL Server / Postgresql
    Secteur : Conseil

    Informations forums :
    Inscription : Mai 2002
    Messages : 21 736
    Points : 52 447
    Points
    52 447
    Billets dans le blog
    5
    Par défaut
    Implémenter un levenshtein dans une requête qui brasse potentiellement des centaines de millier de ligne est le plus sûr moyen d'avoir des performances lamentables.

    Si vous voulez des performances dans vos recherches "flous" il faut créer une table particulières avec des dégradation du mot (liste des lettres, désaccentuation, demi mots droits et gauche, voyelloconsono marquage....) et utiliser des algorithmes performant, comme le dico de knuth, ou l'inférence basique.
    A me lire : http://sqlpro.developpez.com/cours/s...aisons-motifs/

    A +
    Frédéric Brouard - SQLpro - ARCHITECTE DE DONNÉES - expert SGBDR et langage SQL
    Le site sur les SGBD relationnels et le langage SQL: http://sqlpro.developpez.com/
    Blog SQL, SQL Server, SGBDR : http://blog.developpez.com/sqlpro
    Expert Microsoft SQL Server - M.V.P. (Most valuable Professional) MS Corp.
    Entreprise SQL SPOT : modélisation, conseils, audit, optimisation, formation...
    * * * * * Expertise SQL Server : http://mssqlserver.fr/ * * * * *

  10. #10
    Expert éminent
    Avatar de StringBuilder
    Homme Profil pro
    Chef de projets
    Inscrit en
    Février 2010
    Messages
    4 146
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Chef de projets
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Février 2010
    Messages : 4 146
    Points : 7 388
    Points
    7 388
    Billets dans le blog
    1
    Par défaut
    Sinon, peut-être une solution d'apprentissage.

    Plutôt que de générer toutes les déclinaisons "une bonne fois pour toutes", les stocker au fur et à mesure de leur apparition dans une table.
    Puis calculer, la distance levenshtein avec chacun des mots clés déjà connus.
    Le hic, c'est que ça fait faire un produit cartésien sur une fonction potentiellement lourde. Donc prévoir peut-être un apprentissage par procédure automatique différée, et rejeter temporairement les mots inconnus.
    En revanche, une fois que le mot est connu, il n'y a plus qu'à lire les valeurs déjà calculées, qu'on peut donc indexer.
    On ne jouit bien que de ce qu’on partage.

  11. #11
    Expert éminent sénior
    Homme Profil pro
    Responsable Données
    Inscrit en
    Janvier 2009
    Messages
    5 188
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Responsable Données

    Informations forums :
    Inscription : Janvier 2009
    Messages : 5 188
    Points : 12 744
    Points
    12 744
    Par défaut
    OTAN pour moi*, après recherche ce n'est pas une distance de Leveinstein qu'on a utilisé, mais un phonex, avec l'algorithme présenté par SqlPro dans ce petit papier.

    On stocke dans la base le phonex du nom et du prénom du client (et on indexe les deux), et on fait une recherche avec le phonex du nom et du prénom saisi, ce qui nous permet non seulement de trouver très rapidement un client même si le nom et/ou le prénom est mal orthographié, mais en plus de trier le résultat en fonction de la "pertinence" du résultat. Et le tout va très vite, grâce aux indexes.
    En cherchant Jean, la recherche renvoie dans l'ordre Jean, Jeanne puis Jeannot.

    Tatayo.

    *: Mais je plaide les circonstances atténuantes, je suis en congé !

Discussions similaires

  1. Recherche par mot clés - Php -Mysql
    Par pod1978 dans le forum Requêtes
    Réponses: 8
    Dernier message: 22/09/2006, 14h01
  2. recherche par mots-clés dans base access
    Par syber72 dans le forum Access
    Réponses: 2
    Dernier message: 07/03/2006, 14h53
  3. [MySQL] recherche par mots clés
    Par spartan dans le forum PHP & Base de données
    Réponses: 4
    Dernier message: 16/02/2006, 17h11
  4. [Tableaux] Moteur de recherche par mot clés
    Par Nee dans le forum Langage
    Réponses: 4
    Dernier message: 20/01/2006, 12h30
  5. Recherche par mots clés
    Par legillou dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 17/06/2005, 11h56

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo