Outils pour utilisateurs

Outils du site


tris_dictionnaire_francais

Tri et recherche rapide selon le dictionnaire français

(Modification le 28/2/2012: modif du code de la classe Compfr pour éviter des problèmes d'encodage dans le reste du code)

Problématique

Trier des mots avec Python, c'est facile, mais l'ordre que vous obtenez n'est pas en général celui d'un dictionnaire français, mais celui de la police de caractères utilisée. Par exemple, la majuscule “X” se trouve avant la minuscule “a”. Quand aux caractères accentués, ils se trouvent derrière les minuscules non accentuées: 'à' est donc après 'x'…

Il existe une méthode de base intégrée à Python pour faire ça. Je propose ici une adaptation un peu complétée qui répond à tous les cas que j'ai pu tester. Pour ces cas, j'ai pris comme référence l'excellent article suivant, qui traite des règles de tri des dictionnaires français (et un grand merci à nos cousins canadiens :-D ):

Code proposé pour le tri

on va créer une méthode de comparaison qui pourra être utilisée dans les arguments de la méthode sort:

import locale
 
class Compfr(object):
    """comparaison de 2 chaines selon le dictionnaire français"""
 
    def __init__(self, decod='utf-8'):
        self.decod = decod
        self.loc = locale.getlocale() # stocker la locale courante
        self.espinsec = u'\xA0' # espace insécable
 
    def __call__(self, v1, v2):
 
        # on convertit en unicode si nécessaire
        if isinstance(v1, str):
            v1 = v1.decode(self.decod)
        if isinstance(v2, str):
            v2 = v2.decode(self.decod)
 
        # on retire les tirets et les blancs insécables
        v1 = v1.replace(u'-', u'')
        v1 = v1.replace(self.espinsec, u'')
        v2 = v2.replace(u'-', '')
        v2 = v2.replace(self.espinsec, u'')
 
        locale.setlocale(locale.LC_ALL, '')
        comp = locale.strcoll(v1, v2)
        locale.setlocale(locale.LC_ALL, self.loc) #retour à la locale courante
 
        return comp # retour du résultat de la comparaison

Et voilà comment on va l'utiliser:

L = ['pèche', 'PÈCHE', 'pêche', 'PÊCHE', 'péché', 'PÉCHÉ', 'pécher', 'pêcher']
 
compfr = Compfr()
L.sort(cmp=compfr)
for mot in L:
    print mot

Ce qui donne à l'exécution (et qui est l'ordre correct):

pèche
PÈCHE
pêche
PÊCHE
péché
PÉCHÉ
pécher
pêcher

Si on est dans Python 3.x, l'argument cmp de sort() n'existe plus, mais grâce à cmp_to_key du module functools, on peut encore utiliser la même méthode de comparaison avec l'argument 'key'. Il suffira d'écrire:

from functools import cmp_to_key
 
L = ['pèche', 'PÈCHE', 'pêche', 'PÊCHE', 'péché', 'PÉCHÉ', 'pécher', 'pêcher']
 
compfr = Compfr()
L.sort(key=cmp_to_key(compfr))
for mot in L:
    print mot
 
pèche
PÈCHE
pêche
PÊCHE
péché
PÉCHÉ
pécher
pêcher

Tel que la classe Compfr() est définie, la liste est supposée être composée de mots encodés soit en unicode, soit en 'utf-8'. Si les mots non-unicode sont dans un autre encodage, on le donne à l'initialisation. Par exemple, si c'est 'cp1252' (=Windows), on écrit: compfr = Compfr('cp1252'). Dans tous les cas, les comparaisons sont faites en unicode.

Listes de test

Volà les listes utilisées pour les tests, issues de l'article de référence cité plus haut. Les mots se présentent déjà dans l'ordre correct, et le tri doit donc les renvoyer à l'identique. Mais rien ne vous empêche de changer l'ordre pour vérifier.

L = [u'surélévation', u'sûrement', u'suréminent', u'sûreté']
L = [u'cote', u'côte', u'Côte', u'coté', u'Coté', u'côté', u'Côté', u'coter']
L = [u'élève', u'élevé']
L = [u'gène', u'gêne']
L = [u'MÂCON', u'maçon']
L = [u'pèche', u'PÈCHE', u'pêche', u'PÊCHE', u'péché', u'PÉCHÉ', u'pécher', u'pêcher']
L = [u'relève', u'relevé', u'révèle', u'révélé']
L = [u'cadurcien', u'cæcum', u'caennais', u'cæsium', u'cafard', u'coercitif', u'cœur']
L = [u'vice-consul', u'vicennal', u'vice-président', u'vice-roi', u'vicésimal', u'vice' + u'\xA0' + u'versa', u'vice-versa']

NB: u'\xA0' est l'espace insécable.

Tri indexé selon le dictionnaire français

Dans ce cas, la liste initiale ne change pas, et on veut obtenir l'ordre du tri par l'intermédiaire d'un fichier d'index. Par exemple, le 3ème mot de la liste L sera trouvé grâce au fichier index ind, par L[ind[2]] et non L[2].

Voilà comment on trouve ce fichier d'index:

L = [u'cæcum', u'cadurcien', u'cæsium', u'caennais', u'coercitif', u'cafard', u'cœur']
 
ind = [i for i in xrange(0,len(L))] # permet d'avoir ind=[0,1,2,3,...]
compfr = Compfr()
ind.sort(cmp=compfr, key=lambda v: L[v]) # c'est l'index que l'on trie!
for i in xrange(0,len(L)):
    print i, ind[i], L[ind[i]]
print
 
0 1 cadurcien
1 0 cæcum
2 3 caennais
3 2 cæsium
4 5 cafard
5 4 coercitif
6 6 cœur

Et le résultat affiché est bien l'ordre correct.

Si on est avec Python 3.x, l'argument cmp n'existe plus et on utilise encore cmp_to_key du module functools:

from functools import cmp_to_key
 
L = [u'cæcum', u'cadurcien', u'cæsium', u'caennais', u'coercitif', u'cafard', u'cœur']
 
ind = [i for i in xrange(0,len(L))] # permet d'avoir ind=[0,1,2,3,...]
compfr = Compfr()
ind.sort(key=cmp_to_key(lambda v1,v2: compfr(L[v1],L[v2]))) # c'est l'index que l'on trie!
for i in xrange(0,len(L)):
    print i, ind[i], L[ind[i]]
print
 
0 1 cadurcien
1 0 cæcum
2 3 caennais
3 2 cæsium
4 5 cafard
5 4 coercitif
6 6 cœur

Recherche rapide par dichotomie dans une liste triée selon le dictionnaire français

Il suffit d'adapter la fonction de recherche par dichotomie pour qu'elle accepte d'utiliser la méthode de comparaison “compfr(v1,v2)” définie ci-dessus. On peut y ajouter, si nécessaire, une fonction affectée à key pour corriger chaque donnée avant la comparaison.

def dichot(x, L, comp=cmp, key=None):
    i, j = 0, len(L)-1
    if key == None:
        key = lambda c: c
    if comp(x,key(L[j]))>0:
        return [1,j]
    while i!=j:
        k=(i+j)//2
        if comp(x,key(L[k]))<1:
            j = k
        else:
            i = k+1
    if comp(x,key(L[i]))==0:
        return [0, i]
    return [-1, i]

Dans cette fonction, les paramètres en entrée sont les suivants:

  • x = chaîne à rechercher
  • L = liste triée
  • cmp = fonction de comparaison à utiliser (qui doit être la même que celle qui a servi au tri!)
  • key = fonction de conversion utile à ce qu'on recherche

Cette fonction renvoie une liste de 2 valeurs:

  • la 1ère est le critère de réussite
  • la 2ème est l'indice dans la liste.

Le critère de réussite est analogue au résultat de la fonction intégrée cmp(v1,v2): <0 si v1<v2; >0 si v1>v2; et =0 si v1==v2

  • Si la valeur x est trouvée dans la liste L, la fonction renvoie [0,i], i étant l'indice de la valeur trouvée dans L.
  • Si la valeur x ne se trouve pas dans la liste L:
    • si [-1,0] ⇒ la valeur cherchée x est inférieure à la valeur la plus petite de la liste
    • si [-1,i] avec i>0 ⇒ la valeur cherchée x se trouve entre la valeur d'indice i-1 et celle d'indice i
    • si [1,i] avec i==len(L)-1 ⇒ la valeur cherchée x est supérieure à la valeur la plus grande de la liste

En cas de doublon dans la liste:

  • si on cherche le doublon et qu'on le trouve, on trouve celui d'indice le plus faible
  • si on cherche une valeur juste inférieure au doublon, on trouve aussi le doublon d'indice le plus faible

Attention, le mot cherché n'est pas corrigé par key: il faut le corriger vous-même avant l'appel!

Recherche rapide par dichotomie dans une liste indexée triée

Dans une liste indexée triée, on va utiliser la même recherche par dichotomie:

L = [u'cæcum', u'cadurcien', u'cæsium', u'caennais', u'coercitif', u'cafard', u'cœur']
ind = [1,0,3,2,5,4,6]
 
print dichot(u"cæsium", ind, comp=compfr, key=lambda v: L[v])
[0, 3]

Ce qui est le résultat correct donné par [0, 3]:

  • 0 ⇒ le mot a été trouvé
  • 3 ⇒ il est là: L[ind[3]]=u'cæsium'

Avec Python 3.x, on utilise la même formule.


Amusez-vous bien!

tris_dictionnaire_francais.txt · Dernière modification: 2012/02/28 09:45 de tyrtamos

Outils de la page