anagrammes — Recherche d’anagrammes

Cet utilitaire permet de rechercher des anagrammes.

J’ai pu ainsi découvrir que « postulat lunaire » est une anagramme de mes prénom et nom.

Structure de données

Data dominates. If you’ve chosen the right data structures and organized things well, the algorithms will almost always be self­evident. Data structures, not algorithms, are central to programming.

—Rob Pike [Pike1989]

Note

Le détail de ces classes est décrit dans la partie dédiée : anagrammes.

Le dictionnaire des mots valides est stocké sous la forme d’un arbre, qui est décrit plus loin. Commençons par définir deux classes qui seront utilisées par la suite.

Classes diverses

La classe Alphabet définit un ensemble de lettres, avec répétition. Il est possible de soustraire un caractère à un tel objet :

>>> alpha = Alphabet("aabc")
>>> alpha - "b"
Alphabet("aac")

La classe Intervalle définit un intervalle. Ajouter (ou soustraire) un nombre à un intervalle applique l’opération deux deux bornes.

>>> Intervalle(1, 2) + 5
Intervalle(6, 7)
>>> Intervalle(-math.inf, 2) + 5
Intervalle(-math.inf, 7)

Dictionnaire arborescent

Un DictionnaireArborescent est stocké sous la forme suivante.

digraph {
    "#root#" [label="", shape=point];
    "#root#" -> "c";
"c" -> "ch";
"ch" -> "cha";
"cha" -> "chas";
"chas"[label="s", shape=doublecircle];
"cha" -> "chat";
"chat" -> "chatt";
"chatt" -> "chatte";
"chatte"[label="e", shape=doublecircle];
"chatt"[label="t", shape=circle];
"chat"[label="t", shape=doublecircle];
"cha"[label="a", shape=circle];
"ch" -> "chi";
"chi" -> "chie";
"chie" -> "chien";
"chien" -> "chienn";
"chienn" -> "chienne";
"chienne"[label="e", shape=doublecircle];
"chienn"[label="n", shape=circle];
"chien"[label="n", shape=doublecircle];
"chie"[label="e", shape=circle];
"chi"[label="i", shape=circle];
"ch"[label="h", shape=circle];
"c"[label="c", shape=circle];
"#root#" -> "n";
"n" -> "ne";
"ne" -> "net";
"net" -> "nett";
"nett" -> "nette";
"nette"[label="e", shape=doublecircle];
"nett"[label="t", shape=circle];
"net"[label="t", shape=doublecircle];
"ne" -> "nez";
"nez"[label="z", shape=doublecircle];
"ne"[label="e", shape=doublecircle];
"n" -> "ni";
"ni" -> "nic";
"nic" -> "nich";
"nich" -> "niche";
"niche" -> "nicher";
"nicher"[label="r", shape=doublecircle];
"niche"[label="e", shape=doublecircle];
"nich" -> "nicho";
"nicho" -> "nichoi";
"nichoi" -> "nichoir";
"nichoir"[label="r", shape=doublecircle];
"nichoi"[label="i", shape=circle];
"nicho"[label="o", shape=circle];
"nich"[label="h", shape=circle];
"nic"[label="c", shape=circle];
"ni" -> "nid";
"nid"[label="d", shape=doublecircle];
"ni"[label="i", shape=circle];
"n"[label="n", shape=circle];

}

Chaque nœud contient un dictionnaire (un dict au sens de la bibliothèque standard) dont les clefs sont les lettres, et les valeurs sont elles-mêmes des dictionnaires arborescent qui représentent les suffixes. Dans l’exemple illustré ci-dessus, en appellant NE le dictionnaire correspondant au préfixe ne :

  • NE["z"] est le dictionnaire arborescent qui contient le mot z ;
  • NE["t"] est le dictionnaire arborescent qui contient le mot tte.

De plus, chaque DictionnaireArborescent a un attribut DictionnaireArborescent.mot, qui est un booléen qui vaut True si et seulement si le nœud correspondant est un mot valide. Dans l’exemple ci-dessus, de tels nœuds sont représentés par des doubles cercles.

Algorithme

Sans contraintes

L’algorithme de recherche d’une unique anagramme (chercher les mots constitués d’exactement les lettres données en argument) ressemblerait à ceci.

def anagramme(self, alphabet):
   # Le nœud courant est un mot, et toutes les lettres ont été consommées
   if self.mot and not alphabet:
      yield ""

   # Pour chacun des suffixes (qui commencent par une lettre disponible), faire :
   for lettre in self.suffixes:
      if lettre not in alphabet:
         continue

      # Rechercher les anagrammes de l'alphabet (auquel on a retiré la lettre courante) dans les suffixes.
      for suffixe in self.suffixes[lettre].anagramme(alphabet - lettre):
         yield lettre + suffixe

Avec contraintes

L’algorithme est en fait un peu plus compliqué que cela, à cause des deux contraintes suivantes :

  • la taille des mots peut être limitée ;
  • le nombre de mots retourné peut être limité (il est possible de renvoyer, par exemple, un triplet de mots qui utilisent toutes les lettres demandées au lieu d’un simple mot).

La première méthode, DictionnaireArborescent._anagrammes(), recherche une seule anagramme des lettres de l’alphabet demandé. Par contre, elle n’itère pas simplement sur cette anagramme, mais sur le couple (mot, reste), où mot est le mot trouvé, et reste est l'alphabet des lettres inutilisées, qui pourront être utilisées, plus tard, pour former d’autres mots.

Puisque plusieurs mots peuvent être trouvés, il y a un risque de chercher plusieurs fois les mêmes mots. Par exemple, en cherchant les anagrammes de chienne, on pourra trouver d’abord chien et ne, puis ne et chien. C’est une perte de temps. Pour remédier à cela, un autre argument est passé à cette méthode : apres. Cet argument signifie que l’on ne recherche que des mots situés après cet argument dans l’ordre lexicographique du dictionnaire (ou il est simplement ignoré s’il vaut None). Cela assure deux choses :

  • les ensembles de mots trouvés le seront dans l’ordre alphabétique (par exemple chien et ne, plutôt que ne et chien) ;
  • plus important : chaque ensemble de mots ne sera cherché et trouvé qu’une seule fois.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
    def _anagrammes(self, alphabet, lettres, *, apres=None):
        """Recherche d'un seul mot formant une anagramme à `alphabet`.

        Cette fonction est une fonction similaire à :meth:`DictionnaireArborescent.anagramme`,
        mais de plus bas niveau.

        :param Alphabet alphabet: Lettres à utiliser pour former l'anagramme.
        :param Intervalle lettres: Nombre de lettres (par mot) acceptées.
        :param str apres: Si différent de ``None``,
            les anagrammes doivent être plus grandes que cet argument
            (dans l'ordre lexicographique).
        """
        if self.mot and lettres.mini <= 0:
            # On a trouvé un mot, qui est assez grand.
            yield ("", alphabet)
        if lettres.maxi < 0:
            # Le mot courant est trop long ; on ne trouvera plus de mot assez court.
            return

        if not apres:
            # Si ``apres`` n'est pas défini, on lui assigne une valeur arbitraire,
            # plus petite que toutes les autres qui seront rencontrées plus tard.
            # Tous les mots seront donc supérieurs à ``apres``.
            apres = [chr(0)]

        # Pour chacune des lettres possibles
        for debut in sorted(self.suffixes):

            # On exclut les cas impossibles :
            if debut not in alphabet:
                # La lettre n'est pas disponible dans l'aphabet
                continue
            if debut < apres[0]:
                # Le mot serait situé trop tôt dans le dictionnaire
                continue

            # Construction du mot après lequel on peut chercher
            if debut == apres[0]:
                suivant = apres[1:]
            else:
                suivant = None

            # Recherche des anagrammes dans les suffixes
            for (mot, reste) in self.suffixes[  # pylint: disable=protected-access
                debut
            ]._anagrammes(alphabet - debut, lettres - 1, apres=suivant):
                yield (debut + mot, reste)

Une fois que cette fonction de recherche d’un seul mot a été défini, nous pouvons rechercher plusieurs mots. Le principe est qu’après avoir cherché un mot, nous recherchons des anagrammes parmi les lettres restantes (en respectant les contraintes).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
    def _multi_anagrammes(self, alphabet, mots, lettres, *, apres=None):
        """Recherche de plusieurs mots formant une anagramme à l'argument `alphabet`.

        :param Alphabet alphabet: Lettres à utiliser pour former les anagrammes.
        :param Intervalle mots: Nombre de mots acceptés.
        :param Intervalle lettres: Nombre de lettres (par mot) acceptées.
        :param str apres: Si différent de ``None``,
            les anagrammes doivent être plus grandes que cet argument
            (dans l'ordre lexicographique).
        """

        if not alphabet:
            # Plus de lettres disponibles :
            # - soit on a trouvé une anagramme,
            # - soit on abandonne.
            if mots.mini <= 0:
                yield []
            return

        # Si l'on continue, nous auront plus de mots que la limite à respecter.
        # On abandonne.
        if mots.maxi == 0:
            return

        # Recherche d'anagrammes
        for (mot, reste) in self._anagrammes(alphabet, lettres, apres=apres):
            # Pour chacun des anagrammes trouvées,
            # on cherche des anagrammes avec les lettres restantes.
            for suite in self._multi_anagrammes(reste, mots - 1, lettres, apres=mot):
                yield [mot] + suite

Interface en ligne de commandes

Recherche simple

Ce module permet d’effectuer une recherche à la fois. La commande suivante va lister les anagrammes :

  • --dict aspell://fr : constitués de mots français (en utilisant le dictionnaire aspell, s’il est installé) ;
  • --mots 2 : en deux mots ;
  • --lettres 3: : chacun des mots ayant au moins trois lettres ;
  • Boris Vian : en utilisant ces lettres pour construire l’anagramme.
$ anagrammes search --dict aspell://fr --mots 2 --lettres 3: Boris Vian
…
bison ravi
…

Cette commande donne le résultat suivant.

Recherche des anagrammes.

usage: anagrammes [-h] [-a ACCENTS] [-m MOTS] [-l LETTRES] -d DICT
                  alphabet [alphabet ...]

Positional Arguments

alphabet Lettres (ou mots) dont on cherche des anagrammes.

Named Arguments

-a, --accents

Considère les lettres accentuées comme distinctes des lettres non accentuées.

Default: True

-m, --mots Nombres de mots de l’anagramme, sous forme d’intervalle (par défaut : autant que le nombre de mots donnés en argument).
-l, --lettres

Nombres de lettres de chaque mot, sous forme d’intervalle.

Default: :

-d, --dict Dictionnaire dans lequel aller chercher les mots, sous la forme d’un fichier de mots séparés par des espaces ou des sauts de ligne. Les autres caractères sont ignorés. Accepte aussi des arguments sous la forme “aspell://fr”, qui charge tous les mots de la langue “fr” connus du dictionnaire Aspell.

# Intervalles

Les intervalles sont de la forme : - 2:4 : entre 2 et 4 (inclus) ; - :4 : moins de 4 ; - 2: : au moins 2 ; - 3 : exactement 3; - : : indifférent.

Shell interactif

Le chargement d’un dictionnaire peut être assez long. Un shell permet de charger le dictionnaire une fois pour toute, et d’effectuer par la suite plusieurs recherche. Voici un exemple d’exécution arrivant au même résultat que la commande utilisée plus haut.

$ anagrammes shell
Recherche d'anagrammes : shell.
Tapez `help` pour afficher l'aide.
> load aspell://fr
> option mots 2
> option lettres 3:
> search Boris Vian
…
bison ravi
…
> exit
INFO:root:Terminé…