Bonjour,
La participation à ce
fil m'a suggéré qu'on pouvait utiliser le classement par ordre croissant des lettres d'un mot pour trouver toutes les anagrammes de ce mot.
En effet toutes les anagrammes d'un mot ont cette même signature. Ainsi, les lettres classées ACENR sont les mêmes pour les mots ANCRE, CANER, CARNE, CERNA, CRANE, CRENA, ECRAN, ENCRA, NACRE, RANCE.
La première difficulté a été de trouver une liste de mots français sous licence libre. J'ai retenu la contribution du site
Lexique au projet Gutemberg. Cette liste dépasse les 300 000 entrées (avec toutes les formes fléchies)… ce qui augurait mal de la suite de mon projet, ayant bien peur que les temps d'exécutions soient rédhibitoires.
J'ai commencé par supprimer tous les caractères accentués, car on n'en tient pas compte, classiquement, pour former des anagrammes. Cette première étape a été plus compliquée que prévue, du fait que dans la liste initiale (en txt), les caractères accentués étaient formés par l'agrégation du caractère normal avec le caractère diacritique correspondant, et non avec le seul caractère unicode accentué normal. La base du travail s'est faite avec la fonction SUBSTITUE(). Ensuite, bien sûr, j'ai remplacé la formule par la valeur obtenue et supprimé la liste de départ, de manière à éviter des recalculs inutiles.
Ensuite j'ai supprimé les doublons générés par la suppression des accents (sans accent, « cède » et « cédé » sont des doublons), ce qui m'a permis de supprimer plus de 10 000 entrés (3% environ). Pour repérer les doublons, j'ai opté (après quelques déboires) pour la formule la plus simple et la moins gourmande en calcul, une simple comparaison de ligne à ligne qui produisait VRAI ou FAUX. Une fois ces formules transformées en valeurs, il suffisait de faire un tri pour avoir tous les doublons en tête et les éliminer…
L'étape suivante a consisté à utiliser la formule de classement des caractères sur les 323 424 lignes restantes :
Code : Tout sélectionner
=SI(A1="";"";CONCAT(UNICAR(PETITE.VALEUR(UNICODE(STXT(MAJUSCULE(A1);LIGNE(INDIRECT("A1:A"&NBCAR(A1)));1));LIGNE(INDIRECT("A1:A"&NBCAR(A1)))))))
À ce stade, j'ai dû prévoir un fichier AOO distinct du fichier LibO, car sous AOO, la fonction CONCAT, qui doit concaténer une plage de valeurs, n'existe pas en standard, c'est une fonction supplémentaire embarquée dans le fichier (voir
ici, merci à
gerard24 !)
Bien sûr, après avoir généré les chaînes classées, j'ai remplacé les formules par les valeurs…
Il restait à mettre en œuvre cette base de données pour l'objectif initial : entrer un mot (en B1 de la feuille
Anagramme des fichiers joints), le débarrasser de ses accents, majuscules et traits d'union éventuels (en C1) et trouver la chaîne classée correspondante (en D1).
Ceci étant fait, la fonction SI() a assuré le repérage des mots ayant cette même chaîne et donc les n° de ligne correspondants, la fonction PETITE.VALEUR() les a remontés vers le haut et la fonction INDEX() a fourni les mots correspondants. La petite subtilité était de faire un test sur le mot entré en B1, qu'il n'apparaisse pas dans la liste des anagrammes. Cela donnait la formule matricielle (ici en B3 sous AOO) :
Code : Tout sélectionner
=SI(ESTERR(MAJUSCULE(INDEX(Dico.$A$1:$A$323424;PETITE.VALEUR(SI((Dico.$B$1:$B$323424=D$1)*(Dico.$A$1:$A$323424<>C$1);LIGNE(Dico.$B$1:$B$323424);"");LIGNE(A1)))));"";MAJUSCULE(INDEX(Dico.$A$1:$A$323424;PETITE.VALEUR(SI((Dico.$B$1:$B$323424=D$1)*(Dico.$A$1:$A$323424<>C$1);LIGNE(Dico.$B$1:$B$323424);"");LIGNE(A1)))))
Sous LibO, la formule est un peu plus compacte, du fait de l'emploi de la fonction SIERREUR().
Ce travail n'a d'autre ambition que de montrer les capacités de Calc sur des grandes quantités de données. Ici, il ne s'agit que de trouver la ou les anagrammes exactes d'un mot donné, pas l'anagramme d'une phrase ou les anagrammes partielles, chères à Étienne Klein (voir
ici). Il existe en ligne des générateurs d'anagrammes plus puissants (voir
ici).
En lien sur cjoint, les deux fichiers :
Ajout : J'ai poursuivi ma réflexion pour alléger les fichiers créés en explorant deux pistes :
- Première piste : supprimer tous les mots qui n'ont pas d'anagramme et qui alourdissent inutilement le fichier et le travail des fonctions de recherche ;
- Seconde piste : supprimer les redondances qui subsistent, comme le fait que la chaîne alphabétique classée (la « signature » d'une anagramme) est répétée autant de fois qu'il y a d'anagrammes pour cette signature.
Première piste :
Pour repérer les mots qui n’ont pas d’anagramme, si la liste de mots est triée par les chaînes en ordre alphabétique (signatures), ces mots sans anagramme doivent être seuls : la chaîne au-dessus et la chaîne au-dessous est différente, d'où l'idée d'utiliser la formule suivante (en colonne C, ici C2) : De cette manière, si le mot est sans anagramme, après transformation en valeur et tri descendant, tous les mots sans anagramme se retrouvent en haut, il est facile de les éliminer… il ne reste plus que 83 735 mots avec au moins une anagramme, au lieu de 323 424 mots dans la première version : on a allégé de 74 % !
Seconde piste :
Il s'agit de réorganiser le dictionnaire de telle sorte qu’il soit plus compact et moins redondant, en particulier pour éviter de répéter la signature pour tous les mots anagrammes. Pour cela j’ai utilisé une formule très simple (ici en C2) : qui comptait en colonne C le nombre d’anagrammes pour une chaîne donnée. L'idée était de concaténer les mots anagrammes sur la ligne du premier, de manière à pouvoir éliminer toutes les autres lignes, grâce à la formule (ici en D1) : Code : Tout sélectionner =CONCAT(SI(C1=1;INDIRECT("A"&LIGNE()&":"&"A"&LIGNE()+EQUIV(1;C2:C18;0)-1);""))
j’ai choisi un empan (une hauteur de plage) de 17 lignes pour trouver le prochain n°1, car le maximum d’anagrammes pour une chaîne est de 16. De toute façon, EQUIV() ne trouve que le premier 1 de l’empan.
Les mots anagrammes sont donc collés les uns à la suite des autres , sans séparateur, au niveau de chaque signature. Il n'y a pas besoin de séparateur, car tous les mots ont la même taille, c'est celle de la signature !
La fonction STXT(), sur la feuille Anagramme, n'aura aucun mal à isoler chacun d'eux…
Cette seconde piste m'a permis d'alléger mon fichier d'encore 27%, et, bien sûr, la réactivité y a trouvé son compte !
La leçon essentielle que je retire de ce travail est qu'il faut traquer sans relâche les redondances d'information dans un tableur, car on n'est pas guidé, comme dans un SGBD, par un schéma relationnel, par une structure optimisant les données…
Les versions LibO et AOO ci-dessous : |
Cordialement,
Jean-Louis
LibO 24.2.7.2 (x64 avec Java 1.8.0_421) et AOO 4.1.15 (avec Java x32 1.8.0_431), Windows 7 Édition Intégrale 64 SP1