Publicité
+ Répondre à la discussion
Page 2 sur 2 PremièrePremière 12
Affichage des résultats 21 à 30 sur 30
  1. #21
    Nouveau Membre du Club Avatar de floopi51
    Inscrit en
    octobre 2008
    Messages
    136
    Détails du profil
    Informations forums :
    Inscription : octobre 2008
    Messages : 136
    Points : 30
    Points
    30

    Par défaut

    Citation Envoyé par Trap D Voir le message
    Salut

    Mes données étaient rangées dans un gros fichier codé, (ça n'a aucune importance pour le traitement).
    Je faisais un tri alphabétique à partir de la première lettre, j'obtenais un premier index, puis un tri alphabétique à partir de la deuxième lettre etc. Les index renvoyaient à l'offset du mot dans le fichier. Pour accélérer encore la recherche, pour chaque index, je sauvegardais un tableau où étaient indiqués les offset dans l'index du premier mot débutant par a, par b pac c...
    Je trouvais ensuite les mots par une simple recherche dichotomique avec dejà 2 bornes correctes.
    Ok, merci. Comment as-tu procédé pour enregistrer tes index dans un fichier ?

  2. #22
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 558
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 558
    Points : 5 477
    Points
    5 477

    Par défaut

    J'ai enregistré les 2 niveaux de fichiers binaires, en fait 2 X 25 fichiers car la longueur maximale des mots utilisés était 25.
    Les tableaux d'index (le deuxième niveau d'index) sont chargés en mémoire, les premiers fichiers du premier niveau d'index sont gros, puis au fur et à mesure qu'on avance ils deviennent de plus en plus petits (moins de mots de 15 lettres, 16 lettres etc).
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  3. #23
    Nouveau Membre du Club Avatar de floopi51
    Inscrit en
    octobre 2008
    Messages
    136
    Détails du profil
    Informations forums :
    Inscription : octobre 2008
    Messages : 136
    Points : 30
    Points
    30

    Par défaut

    Citation Envoyé par Trap D Voir le message
    J'ai enregistré les 2 niveaux de fichiers binaires, en fait 2 X 25 fichiers car la longueur maximale des mots utilisés était 25.
    Les tableaux d'index (le deuxième niveau d'index) sont chargés en mémoire, les premiers fichiers du premier niveau d'index sont gros, puis au fur et à mesure qu'on avance ils deviennent de plus en plus petits (moins de mots de 15 lettres, 16 lettres etc).
    OK merci pour tes explications. je vois un peu mieux comment fonctionne l'indexation maintenant.
    Bon ben y'a plus K Je vais regarder comment je pourrais travailler avec un index.
    Entre temps, j'ai aussi trouvé un exemple de DAWG ici qui, d'après "la littérature" est très performant pour la recherche de texte.
    Donc 2 bonnes pistes à explorer.

  4. #24
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 558
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 558
    Points : 5 477
    Points
    5 477

    Par défaut

    Bon courage pour la suite.
    Pense à utiliser les facilités offertes par certaines fonctions qui permettent de comparer alphabétiquement les lettres accentuées.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  5. #25
    Membre Expert
    Homme Profil pro
    Inscrit en
    mars 2007
    Messages
    895
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : mars 2007
    Messages : 895
    Points : 1 196
    Points
    1 196

    Par défaut

    C'est sans doute un peu bourrin, mais j'ai simplement construit une hashtable de tous les sous-chaines de tous les mots, qui enregistre pour chaque sous-chaine la liste des mots auquel elle appartient.

    En Python:
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    from collections import defaultdict
    substringDict = defaultdict(list)
    
    def add_word(ssd, word):
        for i in range(len(word)):
            for j in range(i, len(word)):
                ssd[word[i:j+1]].append(word)
    
    for word in wordlist:   # wordlist contient la liste de mots
        add_word(substringDict, word)
    Avec une liste de 22740 mots de longueur moyenne de 8 caractères, j'ai:
    • nombre de sous-chaines uniques = 173047
    • nombre moyen de mots par sous-chaine = 39.5
    • utilisation mémoire = 24 MO, soit un peu plus d'1 KO par mot
    • temps pour construire le dictionnaire: environ 1 seconde

    Retrouver la liste des mots pour une sous-chaîne est très rapide (c'est juste un lookup dans une hashtable), et l'algo est très facile, mais cela prend pas mal de mémoire.

    La construction du dictionnaire (hashtable) est (en nombre d'étapes) O(n*m^2) où n est le nombre de mots et m est la longueur moyenne des mots. Si la longueur moyenne des chaînes à indexer est longue, cette approche risque de ne plus être praticable...

  6. #26
    Nouveau Membre du Club Avatar de floopi51
    Inscrit en
    octobre 2008
    Messages
    136
    Détails du profil
    Informations forums :
    Inscription : octobre 2008
    Messages : 136
    Points : 30
    Points
    30

    Par défaut

    Citation Envoyé par dividee Voir le message
    C'est sans doute un peu bourrin, mais j'ai simplement construit une hashtable de tous les sous-chaines de tous les mots, qui enregistre pour chaque sous-chaine la liste des mots auquel elle appartient.

    En Python:
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    from collections import defaultdict
    substringDict = defaultdict(list)
    
    def add_word(ssd, word):
        for i in range(len(word)):
            for j in range(i, len(word)):
                ssd[word[i:j+1]].append(word)
    
    for word in wordlist:   # wordlist contient la liste de mots
        add_word(substringDict, word)
    Avec une liste de 22740 mots de longueur moyenne de 8 caractères, j'ai:
    • nombre de sous-chaines uniques = 173047
    • nombre moyen de mots par sous-chaine = 39.5
    • utilisation mémoire = 24 MO, soit un peu plus d'1 KO par mot
    • temps pour construire le dictionnaire: environ 1 seconde

    Retrouver la liste des mots pour une sous-chaîne est très rapide (c'est juste un lookup dans une hashtable), et l'algo est très facile, mais cela prend pas mal de mémoire.

    La construction du dictionnaire (hashtable) est (en nombre d'étapes) O(n*m^2) où n est le nombre de mots et m est la longueur moyenne des mots. Si la longueur moyenne des chaînes à indexer est longue, cette approche risque de ne plus être praticable...
    Wouahou Merci !
    Par contre je ne connais pas le Python. (je travaille en C, Objective C, vaguement java) du coup je ne comprend pas en détail les différentes étapes du code. Tu pourrais me l'écrire en algo simple ?
    Quand tu dis que tu as enregistré toutes les sous-chaînes, le "motif" de base d'une sous-chaine c'est quoi ? une syllabe ?

  7. #27
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 081
    Points
    15 081

    Par défaut

    Citation Envoyé par floopi51 Voir le message
    Wouahou Merci !
    Par contre je ne connais pas le Python. (je travaille en C, Objective C, vaguement java) du coup je ne comprend pas en détail les différentes étapes du code. Tu pourrais me l'écrire en algo simple ?
    Quand tu dis que tu as enregistré toutes les sous-chaînes, le "motif" de base d'une sous-chaine c'est quoi ? une syllabe ?
    L'idée c'est de construire pour chaque sous-chaine possible la liste des mots dans laquelle la sous-chaine apparait.

    [sous_chaine1] = {mot1, mot2, mot3, ...}
    [sous_chaine2] = {mot4, mot5, mot6, ...}


    Pour cela, on énumère toutes les sous-chaines présente dans chaque mot, et on met à jour les listes.

    tortue

    [t] = {tortue}
    [o] = {tortue}
    [r] = {tortue}
    [t] // déja traité
    [u] = {tortue}
    [e] = {tortue}

    [to] = {tortue}
    [or] = {tortue}
    [rt] = {tortue}
    [tu] = {tortue}
    [ue] = {tortue}

    [tor] = {tortue}
    [ort] = {tortue}
    [rtu] = {tortue}
    [tue] = {tortue}

    ...

    turquoise

    [t] = {tortue, turquoise}
    [u] = {tortue, turquoise}
    [r] = {tortue, turquoise}
    [q] = {turquoise}
    [u] // déja traité
    [o] = {tortue, turquoise}
    ...

    [tu] = {tortue, turquoise}
    [ur] = {turquoise}
    ...
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  8. #28
    Nouveau Membre du Club Avatar de floopi51
    Inscrit en
    octobre 2008
    Messages
    136
    Détails du profil
    Informations forums :
    Inscription : octobre 2008
    Messages : 136
    Points : 30
    Points
    30

    Par défaut

    Citation Envoyé par pseudocode Voir le message
    L'idée c'est de construire pour chaque sous-chaine possible la liste des mots dans laquelle la sous-chaine apparait.

    [sous_chaine1] = {mot1, mot2, mot3, ...}
    [sous_chaine2] = {mot4, mot5, mot6, ...}


    Pour cela, on énumère toutes les sous-chaines présente dans chaque mot, et on met à jour les listes.

    ...
    OK merci ! Je comprend mieux maintenant.
    Par contre si je fais ça, mon index (c'est à dire ma liste de sous-chaines) va être énorme.
    Il va falloir que je retraite mon index pour l'alléger.

  9. #29
    Membre Expert
    Homme Profil pro
    Inscrit en
    mars 2007
    Messages
    895
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : mars 2007
    Messages : 895
    Points : 1 196
    Points
    1 196

    Par défaut

    Citation Envoyé par floopi51 Voir le message
    Par contre si je fais ça, mon index (c'est à dire ma liste de sous-chaines) va être énorme.
    Il va falloir que je retraite mon index pour l'alléger.
    Oui c'est assez gros, mais comme c'est stocké dans une table de hachage, l'accès est rapide. Les tables de hachage sont présentes dans la librairie standard de beaucoup de langages: HashMap en Java, hash_map dans la STL (C++). Je ne connais pas Objective C, mais apparemment ça existe aussi (NSDictionary). Sauf en C, qui ne possède pas grand chose comme conteneur standard

  10. #30
    Nouveau Membre du Club Avatar de floopi51
    Inscrit en
    octobre 2008
    Messages
    136
    Détails du profil
    Informations forums :
    Inscription : octobre 2008
    Messages : 136
    Points : 30
    Points
    30

    Par défaut

    Citation Envoyé par dividee Voir le message
    Oui c'est assez gros, mais comme c'est stocké dans une table de hachage, l'accès est rapide. Les tables de hachage sont présentes dans la librairie standard de beaucoup de langages: HashMap en Java, hash_map dans la STL (C++). Je ne connais pas Objective C, mais apparemment ça existe aussi (NSDictionary). Sauf en C, qui ne possède pas grand chose comme conteneur standard
    OK.
    Je ne veux pas utiliser l'objective C dans ce traitement. Je vais devoir construire une table de hash en C. Mais j'ai vu des exemples assez claires pour que je m'y retrouve.
    Merci.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •