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 : La Madeleine à la veilleuse de Georges de La Tour
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.
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 : La Madeleine à la veilleuse de Georges de La Tour
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:
Avec une liste de 22740 mots de longueur moyenne de 8 caractères, j'ai:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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)
- 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 ?
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.
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
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager