rechercher une sous-chaine dans un set de 40 000 noms

[floopi51]

Envoyé par Trap D

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 ?

[Trap D]

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).

[floopi51]

Envoyé par Trap D

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.

[Trap D]

Bon courage pour la suite.
Pense à utiliser les facilités offertes par certaines fonctions qui permettent de comparer alphabétiquement les lettres accentuées.

[dividee]

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...

[floopi51]

Envoyé par dividee

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 :

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 ?

[pseudocode]

Envoyé par floopi51

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}
...

[floopi51]

Envoyé par pseudocode

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.

[dividee]

Envoyé par floopi51

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

[floopi51]

Envoyé par dividee

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.