Je parlais d’Advent of Code avec un collègue, on avait un petit leaderboard interne au boulot l’année dernière. Et je lui ai dit “tu devrais regarder betaveros, c’est l’un des meilleurs à Advent of Code, il a même conçu son propre langage appelé Noulith pour le résoudre, c’est vraiment impressionnant”.
Betaveros a écrit un article complet à ce sujet sur son blog, que j’ai déjà lu deux fois par le passé, et j’avais aussi lu quelques morceaux de l’implémentation en Rust l’année dernière pour mieux comprendre comment tout cela fonctionne. D’ailleurs, tout son blog est une véritable mine d’or remplie de connaissances impressionnantes.
Et comme j’ai récemment refait un peu le design de mon site, je suis retombé sur mon ancien article de 2011 sur l’implémentation du “Did you mean” de Peter Norvig en Java, OCaml, Python et aussi Elixir. Je me suis demandé si je pouvais réécrire l’algorithme en utilisant quelques fonctionnalités sympa de Noulith.
Noulith se décrit lui-même comme un langage destiné aux scripts rapides et un peu sales, avec une quantité déraisonnable de sucre syntaxique. Ça semble totalement approprié pour cet exercice.
L’algorithme reste inchangé, on construit une table de fréquences à partir d’un corpus puis on génère tous les mots situés à une modification de distance. Si aucun n’est connu, on essaie avec deux modifications et enfin parmi les candidats connus on choisit le plus fréquent.
Cliquer ici pour voir directement la version finale
Première version
La première version reste très proche de l’implémentation Python:
freq := frequencies(search_all(lower(read_file("big.txt")), "[a-z]+"));
alphabet := "abcdefghijklmnopqrstuvwxyz";
edits1 := \w -> (
splits := for (i <- 0 to len(w)) yield [w[:i], w[i:]];
set((for ((a,b) <- splits; if b) yield a$b[1:]) ++
(for ((a,b) <- splits; if len(b)>1) yield a$b[1]$b[0]$b[2:]) ++
(for ((a,b) <- splits; c <- alphabet; if b) yield a$c$b[1:]) ++
(for ((a,b) <- splits; c <- alphabet) yield a$c$b))
);
known := \xs -> set(xs filter (\x -> x in freq));
edits2 := \w -> set(for (x <- edits1(w); y <- edits1(x); if y in freq) yield y);
correct := \w -> (
candidates := known({w}) or known(edits1(w)) or edits2(w) or {w};
max(candidates, \a,b -> freq[a] <=> freq[b])
);
argv each (\w -> print(w$" -> Did you mean "$correct(w)$" ?"));
Même si elle est déjà assez compacte, cette version n’utilise encore que très peu de ce qui rend Noulith intéressant.
% time noulith v1.noul speling korrectud
speling -> Did you mean spelling ?
korrectud -> Did you mean corrected ?
noulith v1.noul speling korrectud 0.43s user 0.01s system 98% cpu 0.450 total
Utilisons les fonctionnalités de Noulith
Il y a plusieurs fonctionnalités de Noulith que l’on peut utiliser pour cet algorithme.
Par exemple, frequencies(...) construit directement le dictionnaire des fréquences, tandis que search_all(...) extrait les mots du corpus.
Ensuite, on peut remplacer la construction explicite de chaque découpage du mot par prefixes(w) zip reverse(suffixes(w)), puisque ces deux séquences nous donnent exactement la partie gauche et la partie droite du mot pour chacune des positions possibles.
La fonction zip peut aussi recevoir une fonction, donc au lieu de répéter for ((a,b) <- splits) quatre fois on peut traiter directement chaque paire avec zip(..., \a,b -> ...).
La suppression s’écrit simplement a $ b[1:], tandis que la transposition peut être écrite avec des slices sous la forme a $ b[1:2] $ b[:1] $ b[2:]. Cela signifie que l’on peut supprimer les conditions comme if b et if len(b) > 1, puisque les cas invalides vont simplement regénérer le mot original et que le set(...) final supprimera de toute façon les doublons.
Le remplacement et l’insertion sont également presque identiques, puisque leur seule différence est que l’on ajoute soit b[1:], soit b, donc l’opérateur de produit cartésien ** nous permet de générer les deux en une seule fois avec "abcdefghijklmnopqrstuvwxyz" ** [b[1:], b].
Les sets et les dictionnaires sont des concepts très proches dans Noulith, et && calcule leur intersection, ce qui signifie que freq && edits(w) remplace directement la fonction known(...) tout en conservant les fréquences de freq. Le second niveau de modifications devient simplement e flat_map edits, ce qui permet aussi de supprimer complètement la fonction edits2.
Enfin "abcdefghijklmnopqrstuvwxyz" peut s’écrire "a" to "z", ce qui est plutôt sympa.
Avec toutes ces fonctionnalités, le même algorithme devient :
freq := frequencies(search_all(lower(read_file("big.txt")), "[a-z]+"));
edits := \w -> set(flatten(zip(
prefixes(w), reverse(suffixes(w)),
\a,b -> [a$b[1:],a$b[1:2]$b[:1]$b[2:]] ++
(("a" to "z") ** [b[1:],b] map (\(c,t) -> a$c$t))
)));
correct := \w -> (
e := edits(w);
candidates := (freq&&{w}) or (freq&&e) or (freq&&set(e flat_map edits)) or {w};
max(candidates,\a,b -> freq[a] <=> freq[b])
);
argv each (\w -> print(w$" -> Did you mean "$correct(w)$" ?"));
Cette version fait 11 lignes, et surtout elle n’a plus de compréhension for explicite, plus de known, plus de edits2. Les indices servant à construire les découpages du mot et les conditions à l’intérieur de la génération des modifications ont également disparu.
% time noulith v2.noul speling korrectud
speling -> Did you mean spelling ?
korrectud -> Did you mean corrected ?
noulith v2.noul speling korrectud 0.43s user 0.02s system 98% cpu 0.458 total
Un peu de code golf
Réduisons maintenant les noms et le formatage tout en gardant quelque chose que je serais potentiellement prêt à lire :
freq:=frequencies(search_all(lower(read_file("big.txt")),"[a-z]+"));
edit:=\w->set(flatten(zip(prefixes(w),reverse(suffixes(w)),\a,b->[a$b[1:],a$b[1:2]$b[:1]$b[2:]]++(("a"to"z")**[b[1:],b] map(\(c,t)->a$c$t)))));
corr:=\w->(x:=edit(w);c:=(freq&&{w})or(freq&&x)or(freq&&set(x flat_map edit))or{w}; max(c,\a,b->freq[a]<=>freq[b]));
argv each(\w->print(w$" -> Did you mean "$corr(w)$" ?"));
Nous sommes maintenant à 4 lignes de code, soit 388 caractères.
% time noulith golf.noul speling korrectud
speling -> Did you mean spelling ?
korrectud -> Did you mean corrected ?
noulith golf.noul speling korrectud 0.44s user 0.02s system 99% cpu 0.460 total
Peut-on faire encore plus petit ?
Un petit peu 😜
L’application inversée de fonction de Noulith avec . permet de transformer le chargement du corpus en pipeline, donc frequencies(search_all(lower(read_file("big.txt")),"[a-z]+")) devient "big.txt".read_file.lower.search_all("[a-z]+").frequencies.
L’opérateur de produit cartésien ** est également n-aire, ce qui signifie que le remplacement et l’insertion peuvent être générés avec [a]**("a"to"z")**[b[1:],b] map join("") et ça permet d’éviter une lambda supplémentaire.
freq:="big.txt".read_file.lower.search_all("[a-z]+").frequencies;
edit:=\w->zip(w.prefixes,w.suffixes.reverse,\a,b->[a$b[1:],a$b[1:2]$b[:1]$b[2:]]++([a]**("a"to"z")**[b[1:],b] map join(""))).flatten.set;
corr:=\w->(x:=edit(w);c:=(freq&&{w})or(freq&&x)or(freq&&set(x flat_map edit))or{w};max(c,\a,b->freq[a]<=>freq[b]));
argv each(\w->print(w$" -> Did you mean "$corr(w)$" ?"));
Avec ces deux astuces nous sommes toujours à 4 lignes mais aussi avec 10 caractères de moins.
% time noulith golf.v2.noul speling korrectud
speling -> Did you mean spelling ?
korrectud -> Did you mean corrected ?
noulith golf.v2.noul speling korrectud 0.28s user 0.02s system 97% cpu 0.305 total
Une dernière astuce de Noulith
Il reste une dernière fonctionnalité de Noulith à laquelle j’ai pensé pour raccourcir la sélection du meilleur candidat. L’opérateur <=> est un opérateur de comparaison à trois résultats, et on permet de transformer cette comparaison pour qu’elle se fasse à partir d’une autre fonction, donc <=> on (\x -> freq[x]) compare deux mots en utilisant leur fréquence plutôt que les mots eux-mêmes.
Noulith expose aussi l’indexation sous la forme de l’opérateur !!, et ses règles d’application partielle permettent à freq(!!) de représenter la fonction qui indexe freq, ce qui est donc équivalent ici à \x -> freq[x]. On peut donc réduire le comparateur à <=> on freq(!!).
Version finale
On arrive donc à cette version finale en 3 lignes et 346 caractères :
freq:="big.txt".read_file.lower.search_all("[a-z]+").frequencies;
edit:=\w->zip(w.prefixes,w.suffixes.reverse,\a,b->[a$b[1:],a$b[1:2]$b[:1]$b[2:]]++([a]**("a"to"z")**[b[1:],b] map join(""))).flatten.set;
argv each(\w->(x:=edit(w);print(w$" -> Did you mean "$max((freq&&{w})or(freq&&x)or(freq&&set(x flat_map edit))or{w},<=> on freq(!!))$" ?")));
% time noulith final.noul speling korrectud
speling -> Did you mean spelling ?
korrectud -> Did you mean corrected ?
noulith final.noul speling korrectud 0.28s user 0.02s system 98% cpu 0.307 total
À ce stade on pourrait encore tout mettre sur une seule ligne physique puisque Noulith s’en moquerait complètement.
Bref, j’ai déjà passé beaucoup trop de temps là-dessus…
Bravo à betaveros pour ce petit langage vraiment intéressant et élégant.
Peut-être qu’il peut même faire encore mieux, donc si jamais tu lis ça par hasard, n’hésite surtout pas.
À la prochaine !