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

Algorithmes et structures de données Discussion :

Optimiser la recherche dans des fichiers


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre expérimenté
    Profil pro
    Inscrit en
    Septembre 2007
    Messages
    282
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2007
    Messages : 282
    Par défaut Optimiser la recherche dans des fichiers
    Bonjour, j'espère que c'est bien le bon endroit pour poster cette demande

    Problème : J'ai une sorte de base de données sous forme de fichiers (très nombreux) comportant chacun un grand nombre de ligne. Mon but est de trouver, avec une ligne donnée, le fichier de ma base dans lequel une ligne équivalente est présente. Bien entendu, peu importe la ligne en entrée, pour le moment tous les fichiers de la base sont parsés jusqu'à trouver (ou non) cette fameuse ligne. Résultat, quand je dois trouver 100 lignes il parcours 100 fois ma base de fichiers, ce qui fait non seulement des accès disques à répétition, mais également une perte de temps assez importante, et une utilisation CPU énorme.

    Question : Quel serait la meilleur façon de représenter cette base de donnée, afin de minimiser le temps de recherche et les ressources nécessaires, sachant qu'il est impossible à partir de la ligne recherchée de savoir si elle à plus de chance d'être dans tel ou tel fichier de la base.

    Merci d'avance à ceux qui répondrons.

  2. #2
    Expert confirmé

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Par défaut
    Tel que tu poses le probleme, je vois trois approches:
    - rechercher simultanement tes 100 lignes dans chaque fichier. C'est l'approche la plus simple mais elle suppose que tu peux rassembler les requetes.
    - batir une sorte d'index qui te permet de choisir les fichiers ou chercher.
    - changer complement de structure.

    Tu ne donnes pas assez d'information pour t'aider dans les deux dernieres approches.

  3. #3
    Membre expérimenté
    Profil pro
    Inscrit en
    Septembre 2007
    Messages
    282
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2007
    Messages : 282
    Par défaut
    D'abord merci de ta réponse. Ensuite, je vais préciser, un script va lire les logs de mon serveur qui fait du filtrage HTTP. Dans ces logs, il retrouve l'URL de tous les sites visités, il découpe alors cette chaine afin d'en extraire uniquement le domaine, du style "google.com" ou "developpez.net". Je dois alors définir dans quelle catégorie de site se trouve ce domaine. J'ai donc un nombre important de fichiers contenant des domaines, comme pirate.txt contenant un grand nombre de domaines de sites pirate, etc ...

    Maintenant pour savoir si "google.com" appartient à la catégorie "moteur de recherche" ou "pirate" il faut parcourir les deux fichiers texte et vérifier si le domaine est bien dedans. Cette opération est actuellement longue car il va fouiller tous les fichiers jusqu'à trouver le bon. Je cherche à optimiser cette recherche, et ceci peu passer par un changement total de la structure de donnée. C'est pourquoi je demande votre aide.

    Il ne me semble pas possible de "pré-catégoriser" le domaine, si ce n'est pour les sites fréquents comme google ou pages jaunes. Mais j'espère me tromper

  4. #4
    Membre très actif
    Avatar de edfed
    Profil pro
    être humain
    Inscrit en
    Décembre 2007
    Messages
    476
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : être humain

    Informations forums :
    Inscription : Décembre 2007
    Messages : 476
    Billets dans le blog
    1
    Par défaut
    que penses tu d'un systeme de fichier genre reiser fs?
    ce systeme est bien performant.
    une base de donnée, c'est un systeme de fichiers.

    ou alors, crée une liste d'index alphabetiques/groupes.
    les index, c'est des pointeurs, un pointeur, c'est une addresse memoire, ou un offset dans un fichier.

    cette structure est tres simple à creer et la recherche d'un mot est tres rapide.
    il suffit juste de connaitre la premiere lettre du mot recherché et le groupe à explorer, par contre, ça bouffe de la memoire, mais c'est tout de meme plus rapide qu'une recherche de mots dans un fichier sans savoir où il est...

    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
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
     
    ceci est du pseudo asm, mais c'est facile à comprendre
     
     
    group? c'est un id du groupe dans lequel est rangé l'url
    size, c'est la taille de la structure en octets.
    la base est composée de plusieurs structures:
     
    groupxxx c'est le nom du groupe, une structure où sont
    classés les pointeurs des url de cette structure.
     
    meta pour le classement alphabetique des url
     
    A, B, C ... pour classer les pointeurs de chaines pour chaque url
    et finalement, la chaine de carateres en question.
     
    groupcuisine:
    size dd ?
    dd bonnesrecettes.com
    dd j'aimelagalette.fr
    dd spaghettis.org
    dd ...
     
    groupmoteurderecherche:
    size dd ?
    dd google.com
    dd blackle.com
    dd ...
     
    meta:
    size dd ?
    dd A
    dd B
    dd C
    dd D
    dd..
    dd Z
     
    A:
    size dd ?
    dd alapage.fr,group?
    dd allomairie.fr,group?
    dd ..
     
    alapage.fr:
    db 'alapage.fr'0
    allomairie.fr:
    db 'allomairie.fr'0
     
    B:
    size dd ?
    dd bellesdusud.org,group?
    dd bonnesrecettes.com,group?
    dd blackle.com
    dd ...
     
    bellesdusud.org:
    db 'bellesdusud.org',0
    bonnesrecettes.com:
    db 'bonnesrecettes.com',0
    blackle.com:
    db 'blackle.com',0
    ...
    G:
    size dd ?
    dd google.com
    dd google.fr
    dd grossefaimdeloupjevaisallermanger.fr
    dd ...
    voila pour une structure de donnée bien rapide.
    les algorithmes pour l'utiliser en decoulent...

    voire comment faire une implementation en language de haut niveau... quoi qu'il en soit, le resultat, c'est des octets.

  5. #5
    Membre expérimenté
    Profil pro
    Inscrit en
    Septembre 2007
    Messages
    282
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2007
    Messages : 282
    Par défaut
    Merci pour ces infos, je vais me pencher plus en profondeur sur cette structure.

Discussions similaires

  1. Recherche dans des fichiers en dehors du workspace
    Par RMK68 dans le forum Eclipse C & C++
    Réponses: 0
    Dernier message: 15/01/2008, 10h39
  2. [VBS] recherche dans des fichiers Outlook msg
    Par calogerogigante dans le forum VBScript
    Réponses: 31
    Dernier message: 06/12/2007, 13h52
  3. [Débutant] Recherche dans des fichiers
    Par drcd dans le forum Oracle
    Réponses: 0
    Dernier message: 18/10/2007, 11h38
  4. Réponses: 6
    Dernier message: 26/12/2005, 00h48
  5. [XP] recherche dans des fichiers d'extension jsp
    Par drinkmilk dans le forum Windows XP
    Réponses: 5
    Dernier message: 20/10/2005, 08h55

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