Algorithmie: faire un autocomplete

Discutez d'informatique ici !
Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

algorithmie: faire un autocomplete

par fatal_error » 12 Nov 2016, 21:46

hello,

Une ptite curiosité.
Je vous propose d'implémenter un autocomplete.

Pour rappel, un autocomplete c'est:
Je tape quelques caractères, et l'autocomplete me propose des suggestions en accord avec ce que j'ai tapé.
Nous allons simplifier le problème par:

Je tape k caractères: a_0a_1...a_{k-1} (a_i pris dans l'alphabet français)
l'autocomplète me propose les 10 premiers mots commençant par
a_0a_1...a_{k-1}
(éventuellement moins si y a moins de mots satisfaisant l'input)

* Par premier, nous entendons que les mots sont ordonnés par ordre lexical. (a < b, a < aa).

(Nous simplifions pour l'instant le pb pour ne pas se soucier des fautes de frappe, de datamining, user history et autres.)

note: on ne s'intéresse pas à comment on affiche les propositions ni comment on demande la saisie (stdin stdout sont suffisants); ce qui nous intéresse est la structure de donnée, l'algorithme d'insertion/modification, l'algorithme pour trouver les occurrences.

Pour avoir un jeu de données commun et vraisembable, partons de la liste de mots http://www.pallier.org/ressources/dicofr/dicofr.html

Le but premier est d'être le plus rapide possible en temps pour l'algorithme de recherche.

note: comme je vs vois venir, si vous décidez de faire les bourrins de la mémoire, alors majorons à 1Go l'espace de stockage disponible ;) (ce qui est inadmissible pour un usage classique mais soyons fous!).
la vie est une fête :)



Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: algorithmie: faire un autocomplete

par Ben314 » 12 Nov 2016, 22:20

Salut,
J'ai pas tout compris au problème (jusque là, rien de bien surprenant...) :
D'un coté tu parle d'algorithme d'insertion/modification où, concernant "l'insertion", je suppose qu'il s'agit de l'insertion de nouveaux mots dans le dictionnaire utilisé, mais je ne comprend pas bien ce que peut être la "modification" dans le contexte présent.
Et d'un autre coté, tu parle d'utiliser un dictionnaire contenant déjà plus de 300 000 mots (ce qui est déjà extrêmement gros) et j'imagine difficilement qu'on puisse rajouter quoi que ce soit à un tel dictionnaire.

Bref, peut tu préciser un peu plus ce que tu attend comme réponse...

Sinon, pour ce type de problème, à froid, j'aurais tendance à utiliser un arbre de recherche (éventuellement A.V.L.) avec sur chaque sommet une adresse correspondant dans un fichier (disque où mémoire) au premier mot commençant par ces lettres là.
Mais il faut un peu modifier la structure (du coté du fichier) si on veut pouvoir facilement faire des ajout/suppressions dans le dico. en temps raisonnable (sauf erreur, c'est faisable)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: algorithmie: faire un autocomplete

par fatal_error » 12 Nov 2016, 22:52

mais je ne comprend pas bien ce que peut être la "modification" dans le contexte présent.

Si tu manipules un arbre, lorsque tu insères un élément dans l'arbre, potentiellement tu dois modifier ton arbre (le rééquilibrer par exemple).

j'imagine difficilement qu'on puisse rajouter quoi que ce soit à un tel dictionnaire.


le but c'est de pouvoir proposer les 10 premiers mots "trouvés" dans le dictionnaire à la saisie des k caractères de l'utilisateurs.
Quand tu construis ta structure de données, tu vas insérer chacun des mots du dictionnaire dans ta propre structure (parce que le dictionnaire en l'état est une liste et trouver un élém dans une liste c'est pas le top). Le but n'est pas d'insérer des mots dans le dictionnaire, mais d'insérer chacun des mots de ce dictionnaire dans ta structure de données.

ex: en tapant test, je m'attends à ce que l'on me propose
Code: Tout sélectionner
~/Downloads$ grep -E '^test' liste.de.mots.francais.frgut.txt |head -n10
test
testa
testabilité
testabilités
testable
testables
testacé
testacée
testacées
testacelle
la vie est une fête :)

XENSECP
Habitué(e)
Messages: 6387
Enregistré le: 27 Fév 2008, 21:13

Re: algorithmie: faire un autocomplete

par XENSECP » 13 Nov 2016, 12:33

Salut,

J'ai fait un truc similaire dans un autre contexte.
Par contre j'ai pas compris ton histoire d'insertion... ton dictionnaire bouge beaucoup?

Bref moi j'ai fait une structure d'arbre:
Code: Tout sélectionner
t
|- e
   |- s
      |- t
         |- / (fin de mot)
         |- a
            |- / (fin de mot)
            |- b
...


Du coup une fois que tu as ta structure, c'est rapide à chercher car c'est déjà "indexé"...

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: algorithmie: faire un autocomplete

par Ben314 » 13 Nov 2016, 13:39

Si on doit insérer les 300 000 mots du dico. dans notre propre structure pour ensuite ne plus toucher à la structure, alors effectivement, j'utiliserais un A.B.R. dont les clef consisterais en de simple lettres (en descendant dans l'arbre, on reconstitue petit à petit le début du mot) et donc la partie donnée consisterait en une adresse (mémoire ou fichier) sur le premier mot du dictionnaire ayant ces lettres là comme premières lettre.
- Vu le principe, le dico. pourrait parfaitement être une juxtaposition de mot de longueur variables vu que les seuls accès séquentiels se feront sur au plus 10 mots consécutifs.
- La partie Arbre de la structure serait, me semble-t-il, la plus courte possible.

Si c'est pas clair ce que je raconte sur l'arbre, la descente s'effectuerait sur un principe du style :
- Si la lettre Y du noeud sur lequel on est n'est pas la même que celle X qu'on cherche actuellement (une des lettres tapées par l'utilisateur) alors on descend à droite ou a gauche selon que X<Y ou que X>Y.
- Si c'est la même, alors soit X est la dernière lettre tapée et on regarde les 10 mots du dico. à partir de l'adresse donnée par le noeud courant, soit X n'est pas la dernière et on prend comme nouveau X la lettre suivante tapée et on descend à droite où à gauche selon que X<"M" ou pas.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Valentin03
Membre Relatif
Messages: 429
Enregistré le: 23 Déc 2012, 15:08

Re: algorithmie: faire un autocomplete

par Valentin03 » 13 Nov 2016, 14:22

Salut, je vois qu'on trie des mots dans le coin, alors je mets ça là
https://mega.nz/#!8xYCiSwT
ça trie des mots selon plusieurs critères, y a le code, c'est du basic (pour les archéologues du code)
Au niveau code, je crois c'est une compilation de tout ce qu'il ne faut pas faire. Lol !
J'ai fait un exe dans un zip
Edit: Codé au "fil de l'eau" sans aucun plan ni préparation (d'où le bazar)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: algorithmie: faire un autocomplete

par Ben314 » 13 Nov 2016, 14:52

J'arrive pas à ouvrir ton lien, mais je sais pas si tu risque de faire quelque chose de bien utile en BASIC concernant ce type de problème et ce n'est pas un problème d'archaïsme, mais plutôt un problème de "richesse" du langage : le 'B' de BASIC, ça signifie "Beginner" et le BASIC, ça a pas trop été conçu pour faire autre chose que des trucs de débutant. En particulier, il n'y a pas de variables de type pointeurs dans ce langage (*) et ça limite drastiquement les types de structures que tu peut créer en BASIC.
Et si je précise que ce n'est pas un problème d'archaïsme, c'est que par exemple le Fortran bien plus ancien et bien sûr tout les langages machines depuis les premières machines permettent de gérer les pointeurs et donc de créer des structures de données complexes.

(*) Ou tout du moins dans les différentes version que j'ai manipulé au moins une fois dans ma vie, mais vu que mes dernières expériences dans ce langage, ça date pas mal, il y a éventuellement eu des modifications du standard depuis.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Valentin03
Membre Relatif
Messages: 429
Enregistré le: 23 Déc 2012, 15:08

Re: algorithmie: faire un autocomplete

par Valentin03 » 13 Nov 2016, 15:46

Ben314 a écrit:J'arrive pas à ouvrir ton lien

Essaie celui-ci le lien est à la fin du baratin
http://libertybasic.fr/forum/topic-414.php
Le basic a pas mal évolué avec le temps, mais c'est sûr que ça reste limité (et lent)
C'est pour s'amuser.

Edit et PS: Je n'ai pas la moindre idée de ce que tu appelle "structure de données"

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: algorithmie: faire un autocomplete

par fatal_error » 13 Nov 2016, 16:28

@xenscp
oui, c'est une idée immédiate. Mais si tu considères un mot tq
anticonstitu...
tu sais qu'il n'y a plus lieu de continuer à itérer sur chaque lettre après... donc tu crèes
1) des noeuds inutiles dans l'arbre (je peux comparer directement anticonstitutionnellement lettre à lettre dans la valeur storée sur le noeud anticonstitu ce qui est plus rapide que parcourir des noeuds)
2) une itération inutile car tu sais déjà qu'il n'y a plus qu'un seul candidat: si je suis sur anticonstitu, je peux déjà lister anticonstitutionnellement sans avoir à chercher les dix premiers résultats dans mon arbre alors que je sais qu'il n'y en a qu'un.

@ben314
je ne suis pas bien sur de comprendre ton arbre.
- Si la lettre Y du noeud sur lequel on est n'est pas la même que celle X qu'on cherche actuellement (une des lettres tapées par l'utilisateur) alors on descend à droite ou a gauche selon que X<Y ou que X>Y.
- Si c'est la même, alors soit X est la dernière lettre tapée et on regarde les 10 mots du dico. à partir de l'adresse donnée par le noeud courant, soit X n'est pas la dernière et on prend comme nouveau X la lettre suivante tapée et on descend à droite où à gauche selon que X<"M" ou pas.


Si on suppose notre dictionnaire réduit aux mots test et terre.
A quoi ressemble ton arbre?
Code: Tout sélectionner
            t
         e       ?
      r       s       ?
   r       t       ?
e       ?       ?       ?

Tu comptes storer le mot terre sur chaquun des r (au cas ou l'utilisateur s'arrête sur le premier r: ter, ou le deuxieme? terr), ainsi que terre et test sur le premier e (au cas l'utilisateur s'arrête sur te?)

Que se passe-t-il si nous avons également tera, et teru dans le dictionnaire?

@valentin03
très honnêtement, un code est pour moi important pour valider une réflexion, mais d'abord l'idée/théorie est plus importante. Enfin par dessus tout, il faut répondre au problème posé et ne pas déformer l'énoncé. Le but n'est pas de faire une application fenêtrée, pas plus que chercher des mots par la fin. Si je ne suis pas suffisamment clair, alors il vaut mieux me demander de préciser afin qu'on ne s'éparpille pas! thx
la vie est une fête :)

Valentin03
Membre Relatif
Messages: 429
Enregistré le: 23 Déc 2012, 15:08

Re: algorithmie: faire un autocomplete

par Valentin03 » 13 Nov 2016, 16:53

@ fatal_error
T'inquiète, ton énoncé est clair, il suffira de remettre les "égarés" dans le droit chemin
Qu'on propose des lettres de début ou de fin ne change pas trop le problème

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: algorithmie: faire un autocomplete

par Ben314 » 13 Nov 2016, 18:36

Concernant le fait qu'il n'y a plus qu'un seul mot commençant par les lettres données, il me semble que c'est pas vraiment un problème : rien n'impose à l'arbre d'être "de hauteur constante" donc on pourrait parfaitement avoir des noeuds "assez haut" sans fils droit ni gauche pour signifier qu'il n'y a rien à chercher en dessous.

Sinon, concernant l'arbre dans le cas des deux seuls mots TERRE et TEST, ça pourrait effectivement être celui que tu propose (ou d'autres : il y a évidement plusieurs arbres possibles) et je ne comptait stocker aucun mot dans l'arbre lui même, mais uniquement des adresse correspondant à un "vrai dico" qui, dans le cas présent ne contiendrait que "TERRE\0TEST\0" et uniquement deux adresses "valide", à savoir celles des T de début de TERRE et de TEST.
Ensuite,
- Le nœud contenant "t" du haut de l'arbre contiendrait l'adresse du T de TERRE et l'affichage des 10 mots suivants (éventuellement moins si les premières lettres ne correspondent pas à celles déjà tapé) conduirait à l'affichage de TERRE et de TEST.
- Le nœud contenant "s"contiendrait l'adresse du T de TEST et l'affichage donnerais TEST uniquement (c'est le dernier du dico).
- Les deux nœuds contenant "r" contiendrait l'adresse du T de TERRE et l'affichage donnerais TERRE uniquement (vu que le suivant TEST ne commence pas par les bonnes lettres)

Après, si la structure linéaire du dico pose un problème (si on prévoit des ajouts régulier par exemple), on peut la remplacer sans problème par une liste chainée (l'arbre permettant de retrouver les index).

Par contre, je pense qu'il y a un (gros) problème au niveau du coté binaire de l'arbre vu qu'à la descente, on ne peut pas distinguer les noeuds correspondant au fait qu'on a "trouvé la bonne lettre" de ceux uniquement là pour faire de la dichotomie. Par exemple sur l'arbre que tu propose, que l'on tape "TE" ou "E" tout seul, dans les deux cas on se retrouve au même endroit et évidement, c'est "pas glop"...
Donc il faudrait revoir la copie en prenant par exemple un arbre avec 26 arrêtes descendant de chaque noeud (ou moins s'il n'y a plus qu'un seul mot avec ces lettres de départ là)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Valentin03
Membre Relatif
Messages: 429
Enregistré le: 23 Déc 2012, 15:08

Re: algorithmie: faire un autocomplete

par Valentin03 » 13 Nov 2016, 19:24

Pour chercher dans un dico les mots commençant par "ter"
Soit on teste les trois premières lettres de tout le dico
Soit on découpe le dico en 26 parties (mots commençant par "a", par "b", par "c"...ext
Pour ne chercher que dans la partie des mots en "t"
Et on peut redécouper chacune des 26 parties en 26 autres pour la deuxième lettre, et ext...
Pas sûr que le temps gagné à la recherche soit supérieur au temps perdu au découpage.
Sauf à disposer d'un dico prédécoupé.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: algorithmie: faire un autocomplete

par fatal_error » 13 Nov 2016, 19:44

Par exemple sur l'arbre que tu propose, que l'on tape "TE" ou "E" tout seul, dans les deux cas on se retrouve au même endroit et évidement, c'est "pas glop"...
Donc il faudrait revoir la copie en prenant par exemple un arbre avec 26 arrêtes descendant de chaque noeud (ou moins s'il n'y a plus qu'un seul mot avec ces lettres de départ là)

c'est ce que j'ai pas reussi à expliciter avec tera et teru.
Concernant la dichotomie et les 26 arrêtes, il suffit de distinguer (enfoncage de portes) la dichotomie de la lettre suivante.
par exemple: pour un noeud (qui représente une lettre, par exemple le T qui pointe vers test), celui ci contient un ensemble de successeurs. au maximum 26...la recherche du successeur à choisir peut se faire un log_2 si on a choisi de stocker les successeurs dans un ensemble par exe. (autrement dit un arbre "indépendant" de celui du parcourt de lettre).

je pense qu'on peut faire un peu mieux en conservant ton idée.(par rapport aux pointeur de mot stocké sur chaque noeud) (cela se rapporte à la remarque faite à xenscp). par exemple, si toujours avec mon dico j'ai
test, terre
je saisie terrible.
le parcourt va exiger, t, puis e, puis r, puis r, puis retour: rien

En nb d'instructions, cela représente:
trouver les successeurs de t, e, r, r.
donc grosso 4log_2(26) ~ 18 instructions

il aurait été plus rapide de directement tester sur t:
terre==terrible
test==terrible
=>pas de mots donc terrible: false

de la même manière, il y a certains cas où un noeud ne devrait pas représenter une lettre mais une suite. (pour éviter un arbre "ligne droite", du genre terre. on aurait pu avoir:
te->rre
->st
ce qui permet lors du lookup de ter de directement faire
te (comparé en deux instructions(1 par lettre) ) puis r (log2(26))
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

Re: algorithmie: faire un autocomplete

par Ben314 » 13 Nov 2016, 21:28

La première partie de ton Laïus, la façon dont je la comprend, c'est un peu comme avec les différents algo. de tri récursifs, où arrivé à une certaine "toute petite" taille de sous-tableau à trier, on a tout intérêt à arrêter la récursivité et utiliser un tri plus basique pour ne pas gaspiller du temps en "traitement de récursivité".
C'est pas mal vrai "en pratique" et ça fourni des gain de temps non négligeables, mais sur le plan théorique, ça ne change pas la complexité des différents tris en terme de O(?)

Et concernant la deuxième partie, ça me semble plus ou moins le même problème (i.e. sur le plan théorique, on va rien gagner) avec en plus le problème de savoir si l'alourdissement "global" de la structure (pour permettre de stocker éventuellement plus d'une lettre sur chaque nœud de l'arbre) ne risque pas de nuire à l'efficacité dans certains cas où, vu le dictionnaire utilisé, il y a très peu de nœuds dans l'arbre contenant plus d'une lettre.
Donc là, l'éventuel gain risque fortement de dépendre du contenu du dico. employé ainsi que du nombre de lettres max que gère la structure arborescente.
Pour un "vrai" dico. de Français, ça doit sans doute être "pas mal mieux" du fait que l'on trouve dedans de très nombreux cas de mots qui, dés qu'on connait (par exemple) les 4 premières, on est quasi sûr des 4 suivantes alors qu'il y a encore pas mal de possibilités pour les lettres après la 8em. Mais je sais pas si c'est la même chose avec toutes les langues.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: algorithmie: faire un autocomplete

par fatal_error » 14 Nov 2016, 10:35

oui, le but étant néanmoins d'arriver à qqch de plus rapide possible.
Il ne s'agit pas ici de faire de l'assembleur (encore que garder en tete qu'une comparaison tableau c'est mieux qu'un déréférencement pointeur par lettre), mais la manière de stocker l'information est clairement un facteur important pour la recherche.
S'il s'agit de savoir dans quels cas la structure est "lourde", alors il faut voir "pourquoi" et exhiber dans quels cas on doit trouver une alternative!

ps:
...ne risque pas de nuire à l'efficacité dans certains cas où, vu le dictionnaire utilisé, il y a très peu de nœuds dans l'arbre contenant plus d'une lettre.

pour ca, il faut regarder... comme le dico est essentiellement composé de verbes connjugués, il y a beaucoup de radicaux et de fait de suites de lettres "répétées".
la vie est une fête :)

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 4 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite