Code source du projet : https://github.com/Romb38/autoCemantix

Je crois vraiment qu’il faut que je sois en manque de sommeil pour publier (heure actuelle 03h20)

Enfin, il est grand temps de revenir sur cet algorithme de résolution de Cémantix. J’ai avancé après avoir écrit le premier article, et il est grand temps de prendre le temps de détailler tout ça.

Utiliser une méthode aléatoire

Honnêtement, je n’ai pas beaucoup expérimenté avec cette méthode (qui consiste à ajouter de temps en temps des mots aléatoires), mais les quelques avancées que j’ai pu faire ne changent pas drastiquement les temps de calculs (d’environ 4min sur Kopernic - ma machine de travail, et ~12min sur Newtoon, mon serveur sur lequel est également hébergé mon blog).

Trouver le bon dictionnaire

Je me suis rendu compte avec les itérations de l’algorithme que le filtrage des mots chaque jour est vite arrivé à une limite simple : le premier filtrage (retrait des pluriels, adverbes et autres) avait été trop fort. Ainsi l’algorithme cherchait parfois sur tout le dictionnaire sans rien trouver. Avec un temps de réflexion, j’ai eu l’idée de chercher le dictionnaire contenant les mêmes scores que le jeu Cémantix.

Alala, le problème d’écrire un article 1an après avoir fini son code, c’est les pertes de mémoire, ce qui suit est donc une reconstitution, inspirée de faits réels.

Donc, j’ai réutilisé mon code précédent pour obtenir les scores des mots amour, travail, animal, maison, politique d’un jour où je connaissais la solution :


# Vous trouverez les headers dans la partie 1

for word in ["amour", "travail", "animal", "maison", "politique"] :
    url = "https://cemantix.certitudes.org//score?n=1280"
    resp = requests.post(url, headers=headers, data="word=test".encode("utf-8"), timeout=30)
    print(word,resp.json()['s'])

Puis, j’ai téléchargé tous les dictionnaires de la page de Jean-Philippe Fauconnier et j’ai comparé les scores de similarité syntaxique obtenus pour trouver une correspondance exacte. J’ai fini (oui, ce fut le dernier testé, je m’en souviens) par tomber sur ce dictionnaire (frWac_no_postag_phrase_500_cbow_cut10) qui correspondait exactement.

Calculer en local

Avec les scores de similarité exacts, plus besoin d’interroger le site en permanence ! Il suffit de le lire chez nous. :)

Le principe de l’algorithme (nommons-le algorithme de triangulation) devient alors le suivant :

  1. Je demande à Cémantix les scores des mots [“amour”, “travail”, “animal”, “maison”, “politique”]
  2. Si ce n’est pas un de ces mots, alors je parcours mon dictionnaire.
  3. Je teste tous les mots avec le mot ‘amour’ et dès que l’un est à la bonne distance, je le teste avec le mot ’travail’, etc. jusqu’à ce qu’un mot coche toutes les cases.
  4. J’envoie ce mot à Cémantix pour vérifier que c’est le bon (et dans ce cas c’est toujours le bon).

Et voilà ! Avec cette approche, l’algorithme descend aux alentours de 5 secondes sur Kopernic, c’est beaucoup mieux (~12min -> 5 secondes) mais on peut aller plus loin :)

Quelques améliorations

Encore une fois, mille excuses pour l’imprécision des valeurs temporelles, ma mémoire me fait défaut et j’en suis le premier désolé.

Réduire le nombre de mots initiaux

Le coût temporel vient des requêtes HTTP actuellement. Donc plus on en enlève, mieux c’est ! Après quelques essais, je découvre que deux mots ne sont pas assez pour trouver la réponse, car ils provoquent beaucoup de faux positifs. C’est plutôt logique : pour trouver un point unique dans un repère, il nous faut a minima 3 points pour faire de la triangulation, sinon on se retrouve avec une infinité de solutions (ici je suis dans un ensemble fini, donc je finirais par trouver, mais c’est toujours trop). J’ai donc réduit ma liste à ‘amour’, ’travail’, ‘animal’ qui forment une base idéale pour trouver le mot.

Cette amélioration permet de descendre à trois secondes en moyenne sur Kopernic.

Parraléliser les requêtes

Dans la même veine que ‘HTTP c’est lourd quand même’, on peut envoyer nos trois requêtes en même temps pour gagner du temps. On perdra le temps de création de chaque thread, mais cela reste largement moins que le temps pris par des requêtes séquentielles.

Avec cela, on descend à 2,5 secondes en moyenne sur Kopernic.

Affiner le dictionnaire

Avec la nouvelle méthode de triangulation, on perd le tri du dictionnaire, je me suis donc résolu au pire et j’ai envoyé chaque mot à Cémantix (hors ceux déjà testés par l’itération précédente) pour savoir s’il connaissait ce mot ou non.

Side project possible : retrouver les règles de filtres utilisées par Cémantix pour trouver les mots qui étaient dedans ou non

Une fois mon dictionnaire filtré, le temps descend à ~2 s sur Kopernic. Ce dictionnaire est, par ailleurs, accessible dans le projet.

Descendre d’un étage

Actuellement mon code travaille sur des boucles python, pour faciliter le développement, mais si on utilisait numpy plutôt ? Numpy est codé en Cython, donc compilé et donc beaucoup plus rapide ! On cherche à faire de la triangulation, donc on passe un coup de similarité cosinus de NumPy et…

On passe en dessous de la seconde ! ~0,3 seconde de résolution sur Kopernic et entre 0,5 et 1sec en moyenne sur Newtoon.

Conclusion

  1. Ne pas écrire 1 an après avoir fini un projet
  2. On est en dessous de la seconde :)
  3. Si vous voulez avoir les solutions de Cémantix tous les matins, vous pouvez vous abonner à ce topic Ntfy

Et pour la suite ?

– Faire une page /now.

– Apprendre Elixir

– Apprendre Rust.

– Contribuer plus à différents projets !

Au plaisir,

Romb38 – Standouda