Anagrammes

Utilisation d'un programme Ruby pour créer un dictionnaire des anagrammes en français.

    Parenté :
  1. Programmation
  2. Anagrammes

Deux anagrammes sont deux mots qui contiennent les mêmes lettres. Ainsi, par exemple, « phare » et « harpe » sont deux anagrammes de cinq lettres.

J'ai jugé intéressant d'utiliser un script informatique pour recenser toutes les anagrammes présentes (« anagramme » est féminin !) dans une liste de mots.

Principe

Considérons comme données de départ un fichier texte contenant un très grand nombre de mots. De tels fichiers peuvent être trouvés assez facilement via sur le Web, car ils sont utiles aux hackers pour obtenir l'accès à des fichiers protégés par des mots de passe trop classiques.

J'ai scindé ce fichier en 23 fichiers distincts, numérotés de 3 à 25, en fonction de la longueur des mots : 3.txt contient les mots de 3 lettres, et ainsi de suite jusqu'à 25.txt qui contient les mots de 25 lettres (les anagrammes de deux lettres ne sont pas intéressantes, et les mots les plus longs de la langue françaises, « oto-rhino-laryngologistes » « anticonstitutionnellement » ont 25 lettres). Un programme réalisant une telle tâche est assez facile à écrire en Ruby. Je vous laisserai donc le soin de le faire. Au besoin, inspirez-vous du code ci-dessous.

Le programme ci-dessous va analyser un par un ces fichiers. Pour chaque mot rencontré, il va calculer une valeur qui ne dépend que des lettres qui composent le mot, et pas de leur ordre.

En effet, l'arithmétique nous apprend que la décomposition d'un nombre en produit de facteurs premiers est unique, à l'ordre près. L'idée est donc d'associer un nombre premier différent à chacune des 26 lettres de l'alphabet, puis de multiplier ces nombres en fonction des lettres qui composent chaque mot.

Pour faire simple, j'ai utilisé les 26 premiers nombres premiers (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 et 101), mais n'importe quel ensemble de 26 nombres premiers distincts peut bien sûr convenir.

Par exemple, si nous associons, comme je l'ai fait, 2 à « a » et 101 à « z », la valeur associée à « phare » est 53×19×2×61×11 et celle associée à « harpe » est 19×2×61×53×11. Ces deux valeurs sont égales et valent 1 351 394.

Tout mot composé des mêmes lettres que « phare » et « harpe » aura une valeur identique. Tout mot non-composé exclusivement de ces lettres aura une valeur différente.

L'utilisation de nombres premiers est essentielle. En effet, si nous choisissons des nombes quelconques, l'unicité de la décomposition n'est plus garantie. Ainsi, en associant 1 à « a » et 26 à « z », on voit clairement que « bb » et « ad » ont la même valeur, qui est 4, alors que ce ne sont pas des anagrammes.

Le découpage en différents fichiers selon la longueur des mots n'est en revanche pas important, il permet juste de diviser le calcul en autant d'étapes, ce qui peut être avantageux, car il peut être long si la bibliothèque contient de nombreux mots. En réalité, j'avais d'abord réalisé ce programme en CAML, et ses performances étaient fort médiocres (plusieurs minutes pour certaines longueurs de mots). La vitesse d'exécution de ce script Ruby est très satisfaisante : il traite les 23 fichiers (10 Mo de texte pur) en une vingtaine de secondes environ.

Enfin, il convient de remplacer tous les caractères diacritiques par les caractères de base, pour pouvoir ignorer les accents, les cédilles et les trêmas lors de la comparaison. De même, les mots sont convertis en minuscule pour ne pas tenir compte de la casse. De plus, j'ai ajouté un vingt-septième et un vingt-huitième caractères, « - » et « ' », pour obtenir des anagrammes de mots composés.

Programme

Ce code constitue mon premier programme Ruby. Le code source est ici :

#!/usr/bin/env ruby

Valeurs = {
	'a' => 2, 'à' => 2, 'â' => 2, 'ä' => 2, 'á' => 2, 'À' => 2, 'Â' => 2, 'Ä' => 2, 'Á' => 2,
	'b' => 3,
	'c' => 5, 'ç' => 5, 'Ç' => 5,
	'd' => 7,
	'e' => 11, 'é' => 11, 'è' => 11, 'ê' => 11, 'ë' => 11, 'É' => 11, 'È' => 11, 'Ê' => 11,
	'f' => 13,
	'g' => 17,
	'h' => 19,
	'i' => 23, 'î' => 23, 'ï' => 23, 'í' => 23, 'Î' => 23, 'Ï' => 23,
	'j' => 29,
	'k' => 31,
	'l' => 37,
	'm' => 41,
	'n' => 43,
	'o' => 47, 'ô' => 47, 'ö' => 47, 'ó' => 47, 'Ô' => 47, 'Ö' => 47,
	'p' => 53,
	'q' => 59,
	'r' => 61,
	's' => 67,
	't' => 71,
	'u' => 73, 'ù' => 73, 'û' => 73, 'ü' => 73, 'ú' => 73, 'Û' => 73, 'Ü' => 73,
	'v' => 79,
	'w' => 83,
	'x' => 89,
	'y' => 97,
	'z' => 101,
	'-' => 103,
	"'" => 107
}

def valeur(mot)
	res=1
	mot.each_byte do |c|
		lettre = c.chr.downcase
		if Valeurs[lettre]
			res *= Valeurs[lettre]
		else
			puts "Lettre inconnue : \"#{c}\""
		end
	end
	res
end

sortie = File.open('Sortie.txt', 'w')
for num in 3..25
	File.open("#{num}.txt") do |file|
		resultat = Hash.new
		file.each do |line|
			mot = line.chomp
			valeur = valeur(mot)
			if resultat[valeur]
				if !resultat[valeur].include?(mot)
					resultat[valeur].push(mot)
				end
			else
				resultat[valeur] = Array.new.push(mot)
			end
		end
		sortie.puts "\n== Mots de #{num} lettres =="
		resultat.sort {|a,b| b[1].length <=> a[1].length}.each do |valeur, mots|
			if mots.length > 1
				sortie.puts "* #{mots.length} : #{mots.join(', ')}"
			end
		end
	end
end

Il n'est sans-doute pas optimal, et peut certainement être encore amélioré. Son but principal était juste de tester le principe énoncé ci-dessus. En particulier, j'ai eu des problèmes pour traiter les fichiers encodés en UTF-8, mal géré par Ruby 1.8. J'ai dû abandonner cet encodage et convertir script et données en ISO-8859-15. Je réessaierai lorsque j'aurai Ruby 1.9 sous la main.

Résultats

Les couples d'anagrammes les plus long trouvés ont vingt lettres et sont :

La liste de mots initiale ne m'appartenant pas, je me refuse à la diffuser ici. Si vous désirez créer vos propres listes d'anagrammes, vous devrez chercher une liste sur Internet, ou la créer par vous-même.

La liste d'anagrammes (Sortie.txt) étant bien trop longue pour figurer dans cette page, je propose ci-dessous de télécharger un fichier zip la contenant. Elle est très longue et je ne l'ai donc pas relue. Il est possible qu'elle contienne des mots qui n'existent pas en français, en raison de la diversité des listes d'origine.

Téléchargement

Cette page en français a été créée par Peter à partir de sources multiples, 15 décembre 2003 et modifiée pour la dernière fois 25 août 2020. Son avancement est noté 2/3.